|
Основные понятия математической логики
Ещё пример задания: Р-24. Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число a, такое что выражение ( (x & 28 0) (x & 45 0)) ((x & 48 =0) (x & a 0)) тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной x)? Решение:
Введём обозначения:
Z28 = (x & 28 = 0), Z45 = (x& 45 = 0), Z48 = (x& 48 = 0), A = (x&a= 0)
перепишем исходное выражение и преобразуем его, используя свойство импликации:
перейдем к импликации, используя закон де Моргана:
преобразуем выражение в правой части по формуле , выполнив поразрядную дизъюнкцию (операцию ИЛИ):
28 = 011100
45 = 101101
or 45 = 111101 = 61
получаем
для того, чтобы выражение было истинно для всех x, нужно, чтобы двоичная запись числа 48 or a содержала все единичные биты числа 61. Таким образом, с помощью числа a нужно добавить те единичные биты числа 61, которых «не хватает» в числе 48:
48 = 110000
a = **11*1
61 = 111101
биты, обозначенные звездочками, могут быть любыми.
поскольку нас интересует минимальное значение a, все биты, обозначенные звездочкой, можно принять равными нулю. получается A = 23 + 22 + 20 = 13 Ответ: 13.
Ещё пример задания (М.В. Кузнецова): Р-23. Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наибольшее натуральное число a, такое что выражение (( (x & a 0) (x & 12 0)) ((x & a =0) (x & 21 0))) ((x & 21 0) (x & 12 =0)) тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X)? Решение:
Введём обозначения:
Z12 = (X & 12 = 0), Z21 = (X & 21 = 0), A = (X &a= 0)
перепишем исходное выражение и преобразуем его, используя свойство импликации:
Выражение в первой скобке упрощаем, используя следствие из распределительного закона
Полученное выражение также можно упростить, используя ещё одно следствие из распределительного закона
перейдем к импликации, избавившись от инверсии:
поскольку множество единичных битов числа 21 = 101012 не входит во множество единичных битов числа 12 = 11002, импликация ложна для некоторых x; поэтому нужно обеспечить истинность выражения выражение истинно при условии, что множество единичных битов числа a входит во множество единичных битов числа 12, поэтому в двоичной записи числа a ненулевыми могут быть только биты в разрядах 2 и 3 поэтому amax = 23 + 22 = 12. Ответ: 12.
Решение (программа на Python, Г.М. Федченко):
программа на Python, полный перебор:
def f( x, a ):
return ( ((x & a != 0) and (x & 12 == 0)) <= \
((x & a == 0) and (x & 21 != 0)) ) or \
(x & 21 == 0) and (x & 12 == 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 )
вариант без функции:
for a in range(1, 1000):
OK = 1
for x in range(1,1000):
OK *= ( ((x & a != 0) and (x & 12 == 0)) <= \
((x & a == 0) and (x & 21 != 0)) ) or \
(x & 21 == 0) and (x & 12 == 0)
if not OK: break
if OK:
print( a )
Ответ: 12.
|
|
|