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

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

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

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

(x & 49  0)  ((x& 33 = 0)  (x&a 0))

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

Решение (1 способ):

1. 
   введём обозначения:
   

Z₄₉ = (x & 49 = 0), Z₃₃ = (x& 33 = 0), A = (x&a= 0)

2. 
   перепишем исходное выражение и преобразуем его, используя свойство импликации и закон де Моргана :
   

3. 
   переходим к импликации, избавляясь от инверсий:
   

4. 
   чтобы это выражение было истинным, нужно, чтобы множество единичных битов числа 33or a перекрывало множество единичных битов числа 49; с помощью a можно добавить недостающие биты:
   

33 = 100001

a = *1****

49 = 110001

5. 
   чтобы выбрать минимальное a, биты, обозначенные звездочками, примем равными нулю; получаем число 10000₂ = 16 = 2⁴.
   
6. 
   Ответ: 16.
   

Решение (2 способ, Н.Г. Неуймина, г. Екатеринбург):

1. 
   введём обозначения:
   

P = (X & 49  0), Q = (X & 33 = 0), A = (X & A  0)

2. 
   перепишем исходное выражение и преобразуем его, используя свойство импликации :
   

P  (Q  A) = + (Q  A) =

3. 
   чтобы формула была тождественно истинной для любых Х необходимо, чтобы при было А=1
   
4. 
   имеем тогда и только тогда, когда ;
   
5. 
   посмотрим, какими свойствами должен обладать X для того, чтобы было
   
6. 
   если , то есть, (X & 33 = 0), имеем
   

номер бита 5 4 3 2 1 0

X = 0bcde0

33 = 100001

X & 33 = 000000

это значит, что биты {5, 0} – нулевые

7. 
   если одновременно , то есть, (X & 49  0), имеем
   

номер бита 5 4 3 2 1 0

X = 0bcde0

49 = 110001

X & 49 = 0b0000

это значит, что бит 4 в X – обязательно ненулевой

8. 
   из 6 и 7 делаем вывод, что для выполнения условия A = (X & A  0) = 1 необходимо, чтобы, по крайней мере, бит 4 числа A был ненулевым (так как биты {3,2,1} в X могут быть нулевые!)
   
9. 
   поскольку нужно найти наименьшее подходящее A, получаем ответ 2⁴ = 16
   
10. 
    Ответ: 16.
    

Решение (3 способ, А.В. Лаздин, НИУ ИТМО):

1. 
   если X & 49 = 0, то исходное выражение истинно, независимо от значения числа А; значит, значение числа А влияет на решение задачи только при выполнении условия:
   

1. 
   X &49  0.
   

2. 
   тогда исходное выражение может быть представлено в виде:
   

1  ((X & 33 = 0)  (X & A  0)) (2)

3. 
   Для того чтобы это выражение было истинным, необходимо, чтобы выражение
   

(X & 33 = 0)  (X & A  0)

было истинным, при этом, если X & 33  0, то это выражение истинно независимо от значения числа А (импликация из 0 в 1).

4. 
   следовательно, значение числа А влияет на принимаемое исходным выражением значение только при одновременном соблюдении двух условий:
   

1. X & 49  0

2. X & 33 = 0

5. 
   исходное выражение принимает следующий вид:
   

1  (1  (X & A  0)) (3)

6. 
   для того чтобы это выражение приняло значение 1, необходимо, чтобы выполнилось третье условие:
   

3. X & A 0.

49₁₀ = 110001₂

33₁₀ = 100001₂

X 010000

7. 
   условия 1 и 2 выполняются, если пятый бит числа Х равен 1.
   
8. 
   значит условие № 3 выполняется, если пятый бит числа А равен 1
   
9. 
   число А минимально, если младшие разряды этого числа равны 0
   
10. 
    Ответ: 16.
    

Решение (4 способ, М.В. Кузнецова ):

1. 
   Введём обозначения:
   

P = (X & 49  0), Q = (X & 33  0), A = (X & A  0)

2. 
   Перепишем исходное выражение и преобразуем его, используя свойство импликации :
   

3. 
   Чтобы формула была тождественно истинной для любых Х необходимо, чтобы при было А=1, т.е .
   
4. 
   Значит, A =1 тогда и только тогда, когда .
   
5. 
   Запишем двоичное представление чисел 49 и 33, на их основе составим маски возможных значений числа х, таких, что . В маске «1» - соответствует возможному положению 1, «0» - обязательному положению 0 в двоичной записи числа х.
   

Номер бита	5	4	3	2	1	0
Вес разряда	32	16	8	4	2	1
Двоичная запись 49	1	1	0	0	0	1
Двоичная запись 33	1	0	0	0	0	1
Маска мин. х, для P=1 (x & 49 ≠ 0)	1	1	0	0	0	1
Маска мин. х, для =1 (x & 33 = 0)	0	1	1	1	1	0
A = (x & 49 ≠ 0) and (x & 33 = 0)	0	1	0	0	0	0

6. 
   Ответ: 16.