Основные понятия математической логики
 Скачать 2.35 Mb.
|
Ещё пример задания:Р-25. Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число a, такое что выражение( x & 125 1) ((x & 34 2) (x & a =0))тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной x)?Решение: используя результаты теоретической части, перепишем выражение в виде  где Z124 = (x & 124 = 0), Z1 = (x & 1 = 0), Z2 = (x & 2 = 0), A = (x & a = 0) раскроем импликацию по формуле  : применим закон де Моргана  : перейдём к импликации, в которой нет выражений с инверсиями (операциями «НЕ»):    преобразуем левую часть выражения:  так что  используя свойство импликации  , получаем представим числа в двоичной системе счисления: 124 = 11111002, 1 =12, 2 =102 поскольку двоичная запись чисел 1 и 2 содержит единичные биты, которых нет в наборе единичных битов числа 124, имеем  в том смысле, что найдутся такие значения x, при которыхэти выражения ложны. тогда для истинности заданного выражения остаётся обеспечить истинность  при всех x, а это условие будет выполняться тогда и только тогда, когда все единичные биты двоичной записи числа a входят во множество единичных битов числа 124 = 11111002; таким образом, минимальное подходящее положительное значение a – 22 = 4, а максимальное – 124.Ответ: 4. Решение (программа на Python, Г.М. Федченко): программа на Python, полный перебор: def f( x, a ): return (x & 125 != 1) or ((x & 34 == 2) <= (x & a == 0)) for a in range(1, 1000): OK = True for x in range(1,1000): if not f(x, a): OK = False break if OK: print( a ) break вариант без функции: for a in range(1, 1000): OK = 1 for x in range(1,1000): OK *= (x & 125 != 1) or ((x & 34 == 2) <= (x & a == 0)) if not OK: break if OK: print( a ) break Ответ: 4. |