Ррр. Основные понятия математической логики

• Название: Основные понятия математической логики
• Дата: 03.10.2022
• Размер: 2.23 Mb.
• Имя файла: ege15.doc
• Тип: Закон; #710566
• страница: 7 из 48

Ещё пример задания:

Р-25. Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число a, такое что выражение

( x & 125  1)  ((x & 34  2)  (x & a =0))

тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной x)?

Решение:

1. 
   используя результаты теоретической части, перепишем выражение в виде
   

где Z₁₂₄ = (x & 124 = 0), Z₁ = (x & 1 = 0), Z₂ = (x & 2 = 0), A = (x & a = 0)

2. 
   раскроем импликацию по формуле :
   

3. 
   применим закон де Моргана :
   

4. 
   перейдём к импликации, в которой нет выражений с инверсиями (операциями «НЕ»):
   

5. 
   преобразуем левую часть выражения:
   

так что

6. 
   используя свойство импликации , получаем
   

7. 
   представим числа в двоичной системе счисления:
   

124 = 1111100₂, 1 =1₂, 2 =10₂

8. 
   поскольку двоичная запись чисел 1 и 2 содержит единичные биты, которых нет в наборе единичных битов числа 124, имеем
   

в том смысле, что найдутся такие значения x, при которыхэти выражения ложны.

9. 
   тогда для истинности заданного выражения остаётся обеспечить истинность при всех x, а это условие будет выполняться тогда и только тогда, когда все единичные биты двоичной записи числа a входят во множество единичных битов числа 124 = 1111100₂; таким образом, минимальное подходящее положительное значение a – 2² = 4, а максимальное – 124.
   
10. 
    Ответ: 4.
    

Решение (программа на Python, Г.М. Федченко):

1. 
   программа на 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

2. 
   вариант без функции:
   

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

3. 
   Ответ: 4.