Решение задач №18 с помощью таблиц истинностиЕдиного государственного экзамена

Решение задач №18 части В с помощью таблиц истинности Единого государственного экзамена

Учитель информатики Орлова Е.В

ТКМОУ «Хатангская средняя школа – интернат»

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

Что нужно знать :

условные обозначения логических операций

¬ A, не A (отрицание, инверсия)

A  B, A и B (логическое умножение, конъюнкция)

A  B, A или B (логическое сложение, дизъюнкция)

A → B импликация (следование)

таблицы истинности логических операций «И», «ИЛИ», «НЕ», «импликация»

операцию «импликация» можно выразить через «ИЛИ» и «НЕ»:

A → B = ¬ A  B или в других обозначениях A → B =

если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», и самая последняя – «импликация»

иногда полезны формулы де Моргана:

¬ (A  B) = ¬ A  ¬ B

¬ (A  B) = ¬ A  ¬ B

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

( X & 56 ≠ 0)  (( X & 48 = 0)  ( X & A ≠ 0)) [1]

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

Составим таблицу и переведем 56, 48, ( X & 56 ≠ 0) и ( X & 48 = 0) в биты двоичной записи

32

100000

16

56

1

8

10000

48

1

1000

4

1

X & 56 ≠ 0

1

1

2

100

X & 48 = 0

1

0

1

X & A

0

1

10

0

0

1

0

0

0

1

0

0

0

1

0

1

0

1

0

0

1

0

0

1

0

Согласно таблице подставим столбцы 5 и 6 строки в выражение [1] 1  (0  A ) и 1  (1  A ) Для того чтобы эти выражения приняли значение 1, необходимо, чтобы выполнилось третье условие: (X & A  0). Значит, A =1 тогда и только тогда, когда

( X & 56 ≠ 0)=1 и ( X & 48 = 0)=1

Ответ: наименьшее натуральное число A=1000 =8

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

( X & 35 ≠ 0)  (( X & 31 = 0)  ( X & A ≠ 0)) [1]

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

Составим таблицу и переведем 35, 31, ( X & 35 ≠ 0) и ( X & 31) = 0 в биты двоичной записи

32

100000

16

35

1

8

31

10000

0

1000

4

0

X & 35 ≠ 0

1

0

2

X & 31 = 0

1

100

10

1

0

1

0

X & A

1

1

1

0

1

1

0

0

0

1

1

0

0

1

0

1

0

1

0

0

0

0

Согласно таблице подставим 5 и 6 строки в выражение [1] 1  (0  A ) и 1  (1  A ),

для того чтобы это выражение приняло значение 1, необходимо, чтобы выполнилось условие: X & A  0

Значит, A =1 тогда и только тогда, когда ( X & 35 ≠ 0)=1 и ( X & 31 = 0)=1

Ответ: наименьшее натуральное число A=10000=32

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

( X & A ≠ 0)  (( X & 44 = 0)  ( X & 76 ≠ 0)) [1]

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

Составим таблицу и переведем 44, 76, ( X & 76 ≠ 0) и ( X & 44 = 0) в биты двоичной записи

44

64

0

32

76

1

1

X & 44 = 0

16

0

1

X & 76 ≠ 0

8

0

X & A

1

1

4

0

0

1

1

1

1

2

0

1

0

0

0

1

1

0

0

0

0

1

1

1

1

0

1

1

0

0

0

0

Согласно таблице подставим 4 и 5 строки в выражение [1] A  (1  1), А  (0  0 ), А  (0  1 ), для того чтобы это выражение приняло значение 1, необходимо, чтобы выполнилось условие: X & A  0.

Из таблицы видим наибольшее число 1101100=64+32+8+4=108

Ответ: наибольшее натуральное число A=108

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

( (X & 13 ≠ 0)  (X & 39 ≠ 0))  ((X & A ≠ 0)  (X & 13 ≠ 0))

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

Составим таблицу и переведем 13, 39, X & 13 ≠ 0 и X & 39 ≠ 0 в биты двоичной записи

32

13

16

39

0

1

8

0

X & 13 ≠ 0

1

4

0

X & 39 ≠ 0

0

1

0

2

0

1

X & A

0

1

1

0

1

0

1

0

1

0

1

0

1

1

0

1

1

1

1

0

1

Импликация истинна, если истинны левая и правая часть, Согласно таблице подставим 4 и 5 строки в выражение [1] A  (1  1), А  (0  0 ), А  (0  1 ), для того чтобы это выражение приняло значение 1, необходимо, чтобы выполнилось условие: X & A  0. Значит, A =1 тогда и только тогда, когда (X & 13 ≠ 0) = 1 и (X & 39 ≠ 0) = 1 следовательно согласно таблице имеем значение 101. Ответ: наименьшее натуральное число A=5

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

(( (X & 13 ≠ 0)  (X & A ≠ 0))  (X & 13 ≠ 0))  ((X & A ≠ 0)  (X & 39 = 0)) [1]

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

Составим таблицу и переведем 13, 39, ( X & 13 ≠ 0) и ( X & 39 = 0) в биты двоичной записи

32

13

0

16

39

8

1

X & 13 ≠ 0

0

4

X & 39 = 0

1

0

0

0

2

0

X & A

0

1

0

1

0

1

1

1

1

1

1

1

1

0

0

1

1

0

1

1

0

0

1

Подставим значения таблицы в выражение [1] и имеем:

(( 0  A )  0)  ( A  0) то выражение истинно при А=0

(( 0  A )  0)  ( A  1) то выражение истинно при А=1.

Из таблицы имеем 11101 значит А=16+8+4+1=29

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

(( (X & 13 ≠ 0)  (X & 39 = 0))  (X & 13 ≠ 0))  (X & A = 0)  (X & 13 = 0) [1]

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

Составим таблицу и переведем 13, 39, ( X & 13 ≠ 0), ( X & 39 = 0) и ( X & 13 = 0) в биты двоичной записи

32

13

39

16

0

8

1

0

X & 13 ≠ 0

X & 39 = 0

0

0

1

4

0

0

2

X & 13 = 0

0

1

X & A

1

1

0

1

1

1

1

1

1

1

1

1

0

0

0

1

0

0

1

0

1

0

1

1

1

0

1

Подставим значения 1 столбца таблицы в выражение [1] получим (0+0)  0) +(А*1) , А =1.

Подставим значения 2 столбца таблицы в выражение [1] получим (0+1)  0) +(А*1), А =0.

Подставим значения 3 столбца таблицы в выражение [1] получим (1+1)  1) +(А*1) А = 1

Подставим значения 4 столбца таблицы в выражение [1] получим (1+1)  1) +(А*0) А = 1

Получаем наибольшее натуральное число A= 101111=32+8+4+2+1=47

Источники:

http://kpolyakov.spb.ru/school/ege.htm

сайт К.Ю. Полякова, задания ege 18 №150-166

https://inf-ege.sdamgia.ru/

обучающая система Гущина Д.