Построение и анализ таблиц истинности логических выражений. Подготовка учащихся к итоговой аттестации, решение ЕГЭ: задание 2.

итоговой аттестации
решение ЕГЭ задание 2

ФедотоваТ.В. учитель информатики
МОУ «Средняя

школа №30» г. Волгограда

или
¬ (A ∧ B) = ¬ A ∨ ¬ B

или
¬ (A ∨ B) = ¬ A ∧ ¬ B или

 

 

таблицы истинности функций, законы логики, формулы преобразования

ниже логических выражений от трех аргументов: X, Y, Z. Дан

фрагмент таблицы истинности выражения F. Какое выражение соответствует F?

Задача 1

1) ¬X ∧ ¬Y ∧ ¬Z 2) X ∧ Y ∧ Z 3) X ∨ Y ∨ Z 4) ¬X ∨ ¬Y ∨ ¬Z

Решение (вариант 2)

Решение (вариант 1)

Y и Z в первую функцию
Результат не совпадает с соответствующим

значением F.
Оставшиеся строчки можно не рассматривать, поскольку для правильного ответа все три результата должны совпасть со значениями функции F.

1

0

1

0

0

1

подставим заданные значения X, Y и Z во вторую функцию

Результат так же не совпадает с соответствующим значением F.
Оставшиеся строчки рассматривать не будем.

0

1

0

подставим заданные значения X, Y и Z в третью функцию

Результат не совпадает с соответствующим значением F.
Оставшиеся строчки рассматривать не будем.

1

1

0

0

1

1

Результат первой строки совпадает с соответствующим значением F.

Рассмотрим вторую строчку.

подставим заданные значения X, Y и Z в четвертую функцию

 

1

0

0

Результат первой строки совпадает с соответствующим значением F.

Рассмотрим вторую строчку.

 

 

 

 

0

1

1

1

1

1

1

1

1

1

1

Результат второй строки совпадает с соответствующим значением F.

Рассмотрим третью строчку.

0

0

0

0

Результат третьей строки совпадает с соответствующим значением F.

Таким образом все три результата совпадают со значениями функции F, значит правильный ответ – 4) ¬X ∨ ¬Y ∨ ¬Z

нуль для комбинации
Перепишем ответы в других обозначениях:


выражение, которое имеет

единственный нуль для этой комбинации, это

 

Таким образом, правильный ответ 4) ¬X ∨ ¬Y ∨ ¬Z

 

Еще пример задания для данного вида решения

ниже логических выражений от трех аргументов: X, Y, Z. Дан

фрагмент таблицы истинности выражения F. Какое выражение соответствует F?

Задача 2

1) ¬X ∧ ¬Y ∧ ¬Z 2) X ∧ Y ∧ Z
3) X ∧ ¬Y ∧ ¬Z 4) X ∨ ¬Y ∨ ¬Z

Решение (вариант 2)

единицу для комбинации
Перепишем ответы в других обозначениях:

выражение, которое имеет

единственную единицу для этой комбинации, это

 

 

 

 

 

 

Таким образом, правильный ответ 3) X ∧ ¬Y ∧ ¬Z

(¬z)∧ x ∨ x ∧ y. Определите, какому столбцу таблицы

истинности функции F соответствует каждая из переменных x, y, z?

В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала – буква, соответствующая 1-му столбцу; затем – буква, соответствующая 2-му столбцу; затем – буква, соответствующая 3-му столбцу). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Решение (вариант 1)

Решение (вариант 2)

Решение (вариант 3)

Решение (вариант 4)

Решение (вариант 5)

простых обозначениях:
 
подставляем в эту формулу какое-нибудь значение (0 или 1)

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

Ход решения:

Пусть

 

Если X в первом столбце.

То F соответственно примет значения.

Получаем противоречия во второй и четвертой строках.

Если X во втором столбце.

То F соответственно примет значения.

Получаем противоречие во второй строке.

Если X в третьем столбце.

То F соответственно примет значения.

Противоречий не получено.

X

Таким образом переменная Х в третьем столбце.

 

 

 

Y

Следовательно,
Z – в первом столбце,
а Y – во втором

Ответ: ZYX

Z

В этой строке таблицы должно быть обязательно
Z=1
Y=0

логики, запишем заданное выражение:
по распределительному закону для операции «ИЛИ»
 
Ход решения:
Рассмотрим

строки таблицы, где произведение равно 1
(это 2-я, 4-я и 8-я строки)

Так как F=1, то во 2-й строке Х обязательно должно быть равно 1

Х

Y?Z

Y?Z

Поэтому Х может быть только в третьем столбце

В первых двух могут быть и Y, и Z

и из 4 строки, получаем, если F=1 и X=1,

то в первом столбце таблицы может быть только Z, во втором – Y, так как в противном случае получается сумма в скобках равная нулю

Исходя из формулы:

Z

X

Y

В 8-й строке убеждаемся в верности своих рассуждений

Z

X

Y

Ответ: ZYX

строки таблицы, где функция равна 1
2) Обозначим переменные
через a,

b и с.

3) Построим логическое выражение для заданной функции:

4) Упрощаем это выражение, используя законы алгебры логики:

5) Сравнивая полученное выражение с заданным

6) находим, что a = z, b = y и c = x

Ответ: ZYX

таблицы, где функция равна 1, обозначив переменные через a, b

и с

2) сопоставим эти строки с теми строками таблицы истинности заданной функции

, где F = 1

3) Сравнивая столбцы интересующих нас строк, определяем, что c = x (все три единицы в сиреневых ячейках), b = y (один ноль и две единицы) и a = z (два ноля и единица).

Ответ: ZYX

задана в виде ДНФ (дизъюнктивной нормальной формы),

которую не сложно привести к СДНФ, используя известные тождества алгебры логики: a ∙ 1 = a и

Каждую конъюнкцию дополним недостающей переменной:

СДНФ:

3) Каждая конъюнкция в СДНФ соответствует строке таблицы истинности, в которой F=1. Используя полученную СДНФ, делаем вывод: в таблице истинности имеется 3 строки, где F=1, заполним их:

4) В таблице, приведенной в задании, рассмотрим строки, где F=1:

5) Сравнивая столбцы этих таблиц, делаем выводы:

в первом (жёлтом) столбце таблицы задания находится z (одна единица)

во втором (синем) столбце таблицы задания находится y (две единицы),

в последнем (зелёном) столбце таблицы задания находится x (все единицы).

Ответ: ZYX

Соверше́нная дизъюнкти́вная норма́льная фо́рма (СДНФ) — это такая ДНФ (дизъюнкти́вная норма́льная фо́рма), которая удовлетворяет трём условиям:
в ней нет одинаковых элементарных конъюнкций
в каждой конъюнкции нет одинаковых пропозициональных букв
каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в данную ДНФ пропозициональных букв, причём в одинаковом порядке.

того же набора из 5 переменных. В таблицах истинности каждого

из этих выражений в столбце значений стоит ровно по 4 единицы. Каково минимально возможное число единиц в столбце значений таблицы истинности выражения A ∨ ¬B?

Логические выражения, содержащие более трёх переменных

Задача 1

Решение

= 32 строки
в каждой таблице по 4 единицы и по

28 (= 32 – 4) нуля
выражение A ∨ ¬B=0 тогда и только тогда, когда A = 0 и B = 1
минимальное количество единиц в таблице истинности выражения A ∨ ¬B будет тогда, когда там будет наибольшее число нулей, то есть в наибольшем количество строк одновременно A = 0 и B = 1
по условию A = 0 в 28 строках, и B = 1 в 4 строках, поэтому выражение A ∨ ¬B может быть равно нулю не более чем в 4 строках, оставшиеся 32 – 4 = 28 могут быть равны 1

Решение:

Ответ: 28

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

значение x1 не совпадает с F.

Логические выражения, содержащие более трёх переменных

Задача 2

5 логических переменных:
X1 ∧ ¬X2 ∧ X3 ∧ ¬X4 ∧

X5
Сколько существует различных наборов значений переменных, при которых выражение ложно?
1) 1 2) 2 3) 31 4) 32

Задача 3

¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧

¬x6 ∧ ¬x7
2) ¬x1 ∨ x2 ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ ¬x6 ∨ x7
3) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7
4) x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ ¬x7

Логические выражения, содержащие более трёх переменных

Задача 4

Решение

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

нуля, это не может быть выражение, включающее только операции «ИЛИ» (логическое сложение), потому что в этом случае в таблице был бы только один ноль, поэтому варианты 2 и 4 отпадают:

для того, чтобы в последней строке таблицы получилась единица, нужно применить операцию «НЕ» (инверсию) к переменным, значения которых в этой строке равны нулю, то есть к x1, x3, x6 и x7;

видим, что эти условия в точности совпадают с выражением 1, это и есть правильный ответ

Ответ: 1

F.
Одно из приведенных ниже выражений истинно при любых значениях

переменных x1, x2,x3, x4, x5. Укажите это выражение.
1) F(x1,x2,x3,x4,x5)→x1
2) F(x1,x2,x3,x4,x5)→x2
3) F(x1,x2,x3,x4,x5)→x3
4) F(x1,x2,x3,x4,x5)→x4

Задача 5

заполнить лишь небольшой фрагмент таблицы:
Каким выражением может быть F?
1)

x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ ¬x8
2) x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ ¬x8
3) x1 ∧ ¬x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7 ∧ x8
4) x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ ¬x8

Логические выражения, содержащие более трёх переменных

выражения F. Она успела заполнить лишь небольшой фрагмент таблицы:
Задача

7

Каким выражением может быть F?
1) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ ¬x8
2) x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ ¬x8
3) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7 ∧ ¬x8
4) x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ ¬x8