Просмотр содержимого документа
«Построение и анализ таблиц истинности логических выражений. Подготовка учащихся к итоговой аттестации, решение ЕГЭ: задание 2.»
Построение и анализ таблиц истинности логических выражений
подготовка учащихся к итоговой аттестации
решение ЕГЭ задание 2
ФедотоваТ.В. учитель информатики
МОУ «Средняя школа №30» г. Волгограда
Надо знать:
условные обозначения логических операций и приоритет выполнения
Надо знать:
таблицы истинности функций, законы логики, формулы преобразования
A → B= ¬AB или
¬ (AB) = ¬ A¬ B или
¬ (AB) = ¬ 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) XYZ 3) XYZ 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) XYZ
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:
в первом (жёлтом) столбце таблицы задания находится z (одна единица)
в первом (жёлтом) столбце таблицы задания находится z (одна единица)
во втором (синем) столбце таблицы задания находится y (две единицы),
во втором (синем) столбце таблицы задания находится y (две единицы),
в последнем (зелёном) столбце таблицы задания находится x (все единицы).
в последнем (зелёном) столбце таблицы задания находится x (все единицы).
Ответ: ZYX
Логические выражения, содержащие более трёх переменных
Задача 1
Каждое логическое выражение A и B зависит от одного и того же набора из 5 переменных . В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 4 единицы . Каково минимально возможное число единиц в столбце значений таблицы истинности выражения AB ?
Решение
Решение:
полная таблица истинности каждого выражения с пятью переменными содержит 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 логических переменных:
X1¬X2X3¬X4X5
Сколько существует различных наборов значений переменных, при которых выражение ложно?
1) 1 2) 2 3) 31 4) 32
Логические выражения, содержащие более трёх переменных
Задача 4
Дан фрагмент таблицы истинности выражения F.
Какое выражение соответствует F?
1) ¬x1x2¬x3x4x5¬x6¬x7
2) ¬x1x2¬x3x4¬x5¬x6x7
3) x1¬x2x3¬x4x5x6¬x7
4) x1¬x2x3¬x4¬x5x6¬x7
x1
1
x2
x3
1
1
x4
0
0
0
x5
1
1
1
1
0
x6
0
1
x7
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
x1
1
x2
1
x3
1
1
x4
1
0
x5
0
0
0
1
0
1
F
1
1
1
1
0
1
Логические выражения, содержащие более трёх переменных
Задача 6
Александра заполняла таблицу истинности для выражения F. Она успела заполнить лишь небольшой фрагмент таблицы:
x1
x2
x3
0
1
x4
x5
x6
0
x7
1
x8
F
1
1
1
0
0
Каким выражением может быть F?
1) x1¬x2x3¬x4x5x6¬x7¬x8
2) x1x2x3¬x4¬x5¬x6¬x7¬x8
3) x1¬x2¬x3x4x5¬x6¬x7x8
4) x1¬x2x3¬x4¬x5¬x6¬x7¬x8
Логические выражения, содержащие более трёх переменных
Задача 7
Александра заполняла таблицу истинности для выражения F. Она успела заполнить лишь небольшой фрагмент таблицы: