Форум » Логические выражения » вопрос Битовые операции в задачах КИМ ЕГЭ по информатике. Часть II » Ответить
вопрос Битовые операции в задачах КИМ ЕГЭ по информатике. Часть II
natalja27: пример 5 из документа (http://kpolyakov.spb.ru/download/bitwise2.pdf). Формулировка задания "Определите наименьшее натуральное число a, такое что выражение ..." почему тогда ответ 43, а не 1? и какой закон используется, чтобы преобразовать Z19*неZ38+(Z43->(A*Z43) к Z43->((A*Z43)+(Z19*неZ38))
Ответов - 9
dbaxps: Выдержка из примера 5 Bitwise2.pdf В силу утверждений 3 и 2, множество единичных битов числа a or 43 должно входить во множество единичных битов числа 43. Поэтому число a может содержать единичные биты только в тех разрядах, где они есть в двоичной записи числа 43. Таким образом, a(max) = 43. Кроме этого, можно использовать и другие значения a, все единичные биты которых входят во множество единичных битов числа 43: это 1, 2, 3, 8, 9, 10, 11, 32, 33, 34, 35, 40, 41, 42 и 43. Чтобы ясно понимать пример 5 Вам надо внимательно прочесть теорию
Поляков: natalja27 пишет: почему тогда ответ 43, а не 1? Там опечатка, конечно. Ищется наибольшее число A. Спасибо, исправлено. какой закон используется, чтобы преобразовать Z19*неZ38+(Z43->(A*Z43) к Z43->((A*Z43)+(Z19*неZ38)) Просто свойство импликации. C + (A->B) = C + not A + B = not A + (C + B) = A -> (C + B).
MEA: Поляков пишет: Просто свойство импликации. C + A->B = C + not A + B = not A + (C + B) = A -> (C + B). Подозреваю, что скобки потеряны. Импликация выполняется после дизъюнкции С+A->B=not (C+A) +B= not C * not A +B
Поляков: MEA пишет: Подозреваю, что скобки потеряны. Импликация выполняется после дизъюнкции С+A->B=not (C+A) +B= not C * not A +B Да, конечно. Спасибо, поправил.
MEA: Рекомендую для решения метод http://kpolyakov.spb.ru/download/mea18bit.pdf Он проще. Используются только основные законы никаких дополнительных свойств
Ирина С: пример 8 из документа выше: Z23 ⋅ Z45 + A ⋅ Z23 = Z23 + Z45 + A ⋅ Z23 = (Z23 + A)⋅(Z23 + Z23 ) + Z45 = Z23 + A + Z45 = A → (Z23 + Z45). Почему к последней скобке нельзя применить утверждение 8 как в примере 7? тогда получится A → Z23 & 45 и решая дальше A → Z5
MEA: Метод решения в http://kpolyakov.spb.ru/download/mea18bit.pdf понятнее, т.к. использует только взаимнооднозначные переходы и не требует заучивания дополнительных свойств
dbaxps: =================================================== Утверждению 8. Если сумма слева истинна для некоторого "х" то Z(K)(x) + Z(M)(x) = Z(M&N)(х) =================================================== Z(K)(x) -это предикаты ,а не выссказывания. Пример 7 :- Если Z(46)(x)+Z(18)(x) = False , то нет проблемы 0 => Whatever = True То есть можно считать Z(46)(x)+Z(18)(x) = True и тогда Z(46)(x)+Z(18)(x) = Z(46&18)(x) и можно применить Утверждение 8. Пример 8:- Выражение в правой части импликации может быть ложно для некоторого х ∃ x : Z(23)(x) + Z(45)(x) = False Утверждение 8 применить нельзя
dbaxps: E(23)*E(45) => E(A)*E(23) ≡ 1 ¬E(23) + ¬E(45) + E(A)*E(23) ≡ 1 ¬E(23) + ¬E(45) + E(A) ≡1 Отсюда A(min) = 23 Но это абсолютно то же самое, что и (E(23) => E(A)) + (E(23) => ¬E(45)) ≡ 1 с учетом Теоремы 1 (Двойственность с Bitwise2) Для истинности ∀ х : E(k)(x) => E(m)(x), иными словами E(k)=>E(m) ≡ 1, необходимо и достаточно, чтобы множество единичных битов "k" полностью входило во множество единичных битов "m" Я начну построение теории в стиле Bitwise2 с Теоремы 1
полная версия страницы