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

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

подготовка учащихся к итоговой аттестации

решение ЕГЭ задание 2

ФедотоваТ.В. учитель информатики

МОУ «Средняя школа №30» г. Волгограда

Надо знать:

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

Надо знать:

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

A → B = ¬ A  B или

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

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

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

Задача 1

Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F. Какое выражение соответствует F?

X

1

Y

0

Z

0

1

F

0

0

1

0

1

1

1

0

1) ¬X  ¬Y  ¬Z 2) X  Y  Z 3) X  Y  Z 4) ¬X  ¬Y  ¬Z

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

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

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

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

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

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

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

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

X

Y

1

0

0

Z

0

1

0

F

1

1

0

1

1

0

X

X

Y

Y

1

1

0

0

Z

Z

0

0

F

0

F

0

1

X

0

0

1

1

Y

1

1

0

1

1

0

0

1

1

1

Z

1

0

0

1

0

0

0

F

1

1

0

1

1

0

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

0

1

1

0

1

0

1

1

1

0

1

1

0

1

1

1

1

0

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

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

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

Оставшиеся строчки рассматривать не будем.

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

1

1

1

1

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

1

1

1

0

0

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

Оставшиеся строчки рассматривать не будем.

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

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

0

0

0

0

0

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

0

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

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

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

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

• в приведенной задаче в столбце F есть единственный нуль для комбинации

X

Y

1

0

0

Z

1

F

0

0

1

1

0

1

1

0

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

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

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

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

Задача 2

Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F. Какое выражение соответствует F?

X

1

Y

0

Z

0

1

F

0

0

1

0

1

1

0

0

1) ¬X  ¬Y  ¬Z 2) X  Y  Z

3) X  ¬Y  ¬Z 4) X  ¬Y  ¬Z

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

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

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

• в приведенной задаче в столбце F есть единственный единицу для комбинации

X

Y

1

0

0

Z

1

F

0

0

1

1

0

0

1

0

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

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

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

Задача 2

Логическая функция F задаётся выражением (¬ z )  x  x  y . Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z?

?

?

0

0

?

0

0

F

0

0

0

0

1

1

1

1

0

1

0

1

1

0

1

1

0

0

1

1

1

0

0

0

1

0

1

1

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

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

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

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

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

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

Решение (вариант 1: через полную таблицу)

запишем заданное выражение в более простых обозначениях:

Пусть

Ход решения:

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

Y

Z

?

0

?

0

0

?

0

0

F

0

0

1

0

1

1

0

1

1

0

0

1

1

1

0

0

1

1

0

1

1

0

0

1

0

1

1

X

Следовательно ,

Z – в первом столбце,

а Y – во втором

Ответ: ZYX

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

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

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

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

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

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

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

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

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

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

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

Z=1

Y=0

Решение (вариант 2: преобразование логического выражения, Дегтярева Е.В.)

Ход решения:

Используя законы алгебры логики, запишем заданное выражение:

по распределительному закону для операции «ИЛИ»

Y?Z

Y?Z

Х

1

?

2

0

?

0

?

0

F

0

0

1

0

1

1

?

2

0

?

3

0

0

?

4

0

0

F

0

5

0

1

1

0

0

6

1

1

1

7

0

1

1

0

0

0

1

8

1

0

1

1

1

0

0

1

0

1

1

Z

Y

X

1

?

2

?

0

3

?

0

0

F

0

0

4

0

1

0

1

5

0

6

0

1

1

1

0

7

0

1

1

8

1

0

1

0

0

1

1

1

0

0

1

0

1

1

1

?

2

?

0

3

0

X

0

4

F

0

0

0

0

1

1

0

1

0

1

0

1

1

Z

X

Y

Рассмотрим строки таблицы, где произведение равно 1

(это 2-я, 4-я и 8-я строки)

Ответ: ZYX

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

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

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

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

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

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

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

Решение (вариант 3: преобразование логического выражения, СДНФ, В.Н. Воронков)

1) Рассмотрим строки таблицы, где функция равна 1

2) Обозначим переменные

через a, b и с.

?

0

?

0

0

?

F

0

0

0

0

1

0

1

1

1

0

1

0

0

1

1

1

1

0

0

1

0

1

1

1

0

0

0

1

1

a

b

0

c

0

0

1

F

1

1

1

1

1

1

1

1

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

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

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

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

Ответ: ZYX

Решение (вариант 4: сопоставление таблиц истинности, М.С. Коротков)

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

X

a

0

0

Y

b

0

0

0

Z

0

c

0

0

F

0

1

F

1

1

0

1

1

1

1

0

1

1

1

1

0

0

1

1

0

0

1

1

0

0

1

0

1

1

1

1

0

0

1

1

1

1

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

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

, где F = 1

Ответ: ZYX

Решение (вариант 5: М.В. Кузнецова, через приведение к СДНФ)

Соверше́нная дизъюнкти́вная норма́льная фо́рма (СДНФ) — это такая ДНФ (дизъюнкти́вная норма́льная фо́рма), которая удовлетворяет трём условиям:

• в ней нет одинаковых элементарных конъюнкций
• в каждой конъюнкции нет одинаковых пропозициональных букв
• каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в данную ДНФ пропозициональных букв, причём в одинаковом порядке.

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

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

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

x

y

1

z

1

1

0

1

0

F

0

1

1

1

1

1

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

?

0

?

?

0

0

1

F

1

1

1

1

1

1

1

1

СДНФ:

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

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

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

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

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

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

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

Ответ: ZYX

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

Задача 1

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

Решение

Решение:

• полная таблица истинности каждого выражения с пятью переменными содержит 2 5 = 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

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

Задача 2

Дан фрагмент таблицы истинности для выражения F:

Укажите максимально возможное число различных строк полной таблицы истинности этого выражения, в которых значение x1 не совпадает с F.

x1

0

x2

1

x3

0

1

x4

0

0

0

1

x5

1

0

0

1

F

1

1

0

0

1

1

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

Задача 3

Дано логическое выражение, зависящее от 5 логических переменных:

X 1  ¬X 2  X 3  ¬X 4  X 5

Сколько существует различных наборов значений переменных, при которых выражение ложно?

1) 1 2) 2 3) 31 4) 32

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

Задача 4

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

Какое выражение соответствует F?

1) ¬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

x1

1

x 2

x 3

1

1

x 4

0

0

0

x 5

1

1

1

1

0

x 6

0

1

x 7

1

1

F

1

1

1

0

0

0

0

0

1

Решение

Решение:

перепишем выражения в других обозначениях:

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

• остальные переменные инвертировать не нужно, так как они равны 1

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

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

x1

x 2

1

1

x 3

1

0

x 4

0

0

x 5

1

1

1

x 6

1

0

0

1

x 7

1

1

1

F

1

1

0

0

0

0

0

1

Ответ: 1

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

Задача 5

Дан фрагмент таблицы истинности выражения 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

x 1

1

x 2

1

x 3

1

1

x 4

1

0

x 5

0

0

0

1

0

1

F

1

1

1

1

0

1

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

Задача 6

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

x1

x2

x3

0

1

x4

x5

x6

0

x 7

1

x 8

F

1

1

1

0

0

Каким выражением может быть F?

1) x 1  ¬ x 2  x 3  ¬ x 4  x5  x6  ¬ x 7  ¬ x 8

2) x 1  x 2  x 3  ¬ x 4  ¬ x5  ¬ x6  ¬ x 7  ¬ x 8

3) x 1  ¬ x 2  ¬ x 3  x 4  x5  ¬ x6  ¬ x 7  x 8

4) x 1  ¬ x 2  x 3  ¬ x 4  ¬ x5  ¬ x6  ¬ x 7  ¬ x 8

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

Задача 7

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

x1

x2

0

x3

1

x4

x5

x6

0

1

x 7

x 8

1

F

0

1

1

1

Каким выражением может быть F?

1) x 1  ¬ x 2  x 3  ¬ x 4  x5  x6  ¬ x 7  ¬ x 8

2) x 1  x 2  x 3  ¬ x 4  ¬ x5  ¬ x6  ¬ x 7  ¬ x 8

3) ¬ x 1  x 2  ¬ x 3  x 4  x5  ¬ x6  ¬ x 7  ¬ x 8

4) x 1  ¬ x 2  x 3  ¬ x 4  ¬ x5  ¬ x6  ¬ x 7  ¬ x 8