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

Построение и анализ таблиц истинности логических выражений подготовка учащихся к итоговой аттестации решение ЕГЭ задание 2 Мазеева Т. А. учитель информатики МОУ «Средняя школа №3» г. Николаевск tanya-dima@yandex.ru mazeev221282@gmail.com

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

Надо знать: таблицы истинности функций, законы логики, формулы преобразования A → B = ¬ A  B или BA  ¬ (A  B) = ¬ A  ¬ B или BA  ¬ (A  B) = ¬ A  ¬ B или BA A → B = ¬ A  B или¬ (A  B) = ¬ A  ¬ B или¬ (A  B) = ¬ A  ¬ B или

Логические выражения, содержащие три переменных Задача 1 Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F. Какое выражение соответствует F? X Y Z F 1) ¬X  ¬Y  ¬Z 2) X  Y  Z 1 0 0 1 3) X  Y  Z 4) ¬X  ¬Y  ¬Z 0 0 0 1 1 1 1 0 Решение (вариант 2) Решение (вариант 1)

Решение (вариант 1) Перепишем ответы в других обозначениях: )3 )2 )1 ZYX ZYX ZYX )4 ZYX подставим заданные значения X, Y и Z в первую подставим заданные значения X, Y и Z во вторую подставим заданные значения X, Y и Z в третью подставим заданные значения X, Y и Z в четвертую    ZYX ZYX ZYX функцию функцию функцию функцию Y X Y Y Y X X X 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 X Y  ZYX   ZYX ZYX Результат первой строки 1 0 00 1 0 1 0 11 1 0 совпадает с соответствующим Результат не совпадает с 1 1 1 1 00 Результат так же не Результат первой строки Рассмотрим вторую строчку. значением F. Результат не совпадает Рассмотрим вторую строчку. соответствующим значением F. совпадает с совпадает с соответствующим с соответствующим Оставшиеся строчки можно не Результат второй строки соответствующим 00 0 0 значением F. Рассмотрим третью строчку. значением F. рассматривать, поскольку для совпадает с соответствующим значением F. Оставшиеся строчки правильного ответа все три значением F. Оставшиеся строчки Результат третьей строки рассматривать не будем. результата должны совпасть со рассматривать не будем. Таким образом все три результата совпадают со совпадает с соответствующим значениями функции F. значениями функции F, значит правильный ответ – 4) ¬X значением F.  ¬Y  ¬Z Z 1 1 1 0 Z Z Z Z 0 0 0 0 0 0 0 0 1 1 1 1 F F F F 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0

Решение (вариант 2) Перепишем ответы в других обозначениях: )3 )2 )1 ZYX ZYX ZYX )4 ZYX • в приведенной задаче в столбце F есть единственный нуль для комбинации • выражение, которое имеет единственный нуль для этой комбинации, это X Y Z F 1 0 0 1 0 0 0 1 1 1 1 0 Таким образом, правильный ответ 4) ¬X  ¬Y  ¬Z Еще пример задани я для данного вид а решения

содержащие три переменных Логические выражения, Задача 2 Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F. Какое выражение соответствует F? X Y Z F 1) ¬X  ¬Y  ¬Z 2) X  Y  Z 1 0 0 1 3) X  ¬Y  ¬Z 4) X  ¬Y  ¬Z 0 0 0 0 1 1 1 0 Решение (вариант 2)

Решение (вариант 2) Перепишем ответы в других обозначениях: • в приведенной задаче в столбце F есть единственный единицу для комбинации • выражение, которое имеет единственную единицу для этой комбинации, это X Y Z F 1 0 0 1 0 0 0 0 1 1 1 0 Таким образом, правильный ответ 3) X  ¬Y  ¬Z

Логические выражения, содержащие три переменных Задача 2 Логическая функция F задаётся выражением (¬z) x  x  y. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z? В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала – буква, соответствующая 1-му столбцу; затем – буква, соответствующая 2-му столбцу; затем – буква, соответствующая 3- му столбцу). Буквы в ответе пишите Решение (вариант 3) подряд, никаких разделителей Решение (вариант 1) Решение (вариант 4) между буквами ставить не нужно. Решение (вариант 2) Решение (вариант 5) ? 0 0 1 1 0 0 1 1 ? 0 0 0 0 1 1 1 1 ? 0 1 0 1 0 1 0 1 F 0 1 0 1 0 0 0 1

Решение (вариант 1: через полную таблицу) запишем заданное выражение в более простых обозначениях: Ход решения: подставляем в эту формулу Следовательно, какое-нибудь значение (0 Z – в первом столбце, или 1) одной из а Y – во втором переменных, и пытаемся Ответ: определить, в каком столбце она записана. ZYX Если X в третьем Если X во втором столбце. Получаем Если X в первом столбце. То F соответственно примет То F соответственно Получаем Противоречий не Таким образом То F соответственно В этой строке таблицы должно  столбце. противоречия во значения. примет значения. переменная Х в противоречие во получено. примет значения. быть обязательно второй и четвертой второй строке. третьем столбце. Z=1 строках. Y=0 Пусть Z ? 0 0 0 0 1 1 1 1 Y ? 0 0 1 1 0 0 1 1 X ? 0 1 0 1 0 1 0 1 F 0 1 0 1 0 0 0 1 XYZ

Решение (вариант 2: преобразование логического выражения, Дегтярева Е.В.) Ход решения: Используя законы алгебры логики, запишем заданное выражение: YZXYXXZF   Рассмотрим строки Ответ: таблицы, где ZYX произведение равно 1 YZXF (это 2-я, 4-я и 8-я строки)  Исходя из формулы: В 8­й строке убеждаемся в верности  и из 4 строки, получаем, если F=1 и  своих рассуждений YZXF  X=1,      111 111 по распределительному закону для операции «ИЛИ» F F F F 0 0 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 0 то в первом столбце таблицы  может быть  0 только Z, во втором – Y, так как в противном  0  случае получается сумма в скобках равная нулю 1 1  101  Х Y?Z Y?Z ? ? ? Y X Z ? ? ? ? ? ? X Z Y X ? ? 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 Так как F=1, то во 2-й Поэтому Х может быть В первых двух могут быть и Y, и Z 1 0 1 1 0 1 1 0 1 строке Х обязательно только в третьем 0 0 1 0 1 0 должно быть равно 1 столбце 1 1 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 3 3 3 4 4 4 5 5 6 6 7 7 8 8 ХY?ZY?ZZXYZXY

Решение (вариант 3: преобразование логического выражения, СДНФ, В.Н. Воронков) 1) Рассмотрим строки таблицы, где функция равна 1 2) Обозначим переменные  ? ? ? F c b F через a, b и с. 0 0 0 0 1 1 0 3) Построим логическое  1 0 0 1 1 1 1 выражение для заданной  функции: 0 1 0 0 1 1 1 1 1 0 1  cbacbacbaF 0 0 1 0 4) Упрощаем это выражение, используя законы алгебры логики: 5) Сравнивая полученное выражение с заданным  1 0 1 0   xzF yx ( cba cbcba cbacbacbaF ) 1 1 0 0 6) находим, что a = z, b = y и c = x  cbba ( ) ) ( cbb cba cbca ( 1 1 1 1 Ответ: ZYX  cbaa ) cba  cba  cba  a 0 0 1 ba ()

Решение (вариант 4: сопоставление таблиц истинности, М.С. Коротков) b 0 1 1 Z c F F 0 0 1 1 3) Сравнивая столбцы  1 0 1 1 интересующих нас строк,  определяем, что c = x (все три  0 0 1 1 единицы в сиреневых ячейках), b = y  1 0 (один ноль и две единицы) и a = z  (два ноля и единица). 1 0 1 0 0 1 1 1 Y 0 0 1 1 0 0 1 1 X 0 0 0 0 1 1 1 1 1) Рассмотрим строки таблицы, где  функция равна 1, обозначив  переменные через a, b и с 2) сопоставим эти строки с теми  строками таблицы истинности  заданной функции xzF  yx , где F = 1 a 0 0 1 Ответ: ZYX

Решение (вариант 5: М.В. Кузнецова, через приведение к СДНФ) ее ( ое ое ае ае xzF ие  yx Соверш нная дизъюнкт вная норм льная ф рма (СДНФ) — это         задана в виде ДНФ (дизъюнктивной  1) Функция   3) Каждая конъюнкция в СДНФ соответствует строке таблицы  ие такая ДНФ (дизъюнкт вная норм льная ф рма), которая  нормальной формы), которую не сложно привести к СДНФ,  истинности, в которой F=1. Используя полученную СДНФ, делаем  удовлетворяет трём условиям: используя известные тождества алгебры логики: a ∙ 1 = a  и   вывод: в таблице истинности имеется 3 строки, где F=1, заполним их: •в ней нет одинаковых элементарных конъюнкций 1 aa F z y x   4) В таблице, приведенной в  •в каждой конъюнкции нет одинаковых пропозициональных букв 1 0 1 1  zyx 2) Каждую конъюнкцию дополним недостающей переменной: задании, рассмотрим строки, где  •каждая элементарная конъюнкция содержит каждую  ? F=1:  ? 1 1 0 0 F    zxF zyx zyx zyx z yx y ( ) y zyx пропозициональную букву из входящих в данную ДНФ  1 1 1 1  zyx пропозициональных букв, причём в одинаковом порядке. 1 1 0  zyx zyx zyxF СДНФ: 0 1 1 5) Сравнивая столбцы этих таблиц,  1 1 1 делаем выводы: ? zyx 0 1 1 z ) в первом (жёлтом) столбце таблицы задания  во втором (синем) столбце таблицы  в последнем (зелёном) столбце таблицы  находится z (одна единица) задания находится y (две единицы), задания находится x (все единицы). Ответ: ZYX

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

Решение: нуля A = 0 и B = 1 1. полная таблица истинности каждого выражения с пятью переменными содержит 25 = 32 строки 2. в каждой таблице по 4 единицы и по 28 (= 32 – 4) 3. выражение A  B=0 тогда и только тогда, когда 4. минимальное количество единиц в таблице истинности выражения A  B будет тогда, когда там будет наибольшее число нулей, то есть в наибольшем количество строк одновременно A = 0 и B = 1 5. по условию A = 0 в 28 строках, и B = 1 в 4 Ответ: 28 строках, поэтому выражение A  B может быть равно нулю не более чем в 4 строках, оставшиеся

Логические выражения, содержащие более трёх переменных таблицы истинности Задача 2 Дан фрагмент выражения F: Укажите число различных строк полной таблицы истинности этого выражения, в которых значение x1 не совпадает с F. максимально возможное для x1 x2 x3 x4 x5 F 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 0 1 0

Логические выражения, содержащие более трёх переменных Задача 3 Дано логическое выражение, зависящее от 5 логических переменных: X1  ¬X2  X3  ¬X4  X5 Сколько существует различных наборов значений переменных, при которых выражение ложно? 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 x2 x3 x4 x5 x6 x7 F 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 0 1 0 0 Решение

Решение: перепишем выражения в других обозначениях:  x xx x 1)1 7 2 4    1)2 x x x 6  1)3 xx x x 7 6   1)4 x x x 6 x x 3  x 3 x 3  x 3 x 5  x 6 x 5 x 5  4 x x 7 x 5 x 7   x 2 4 4 2 2 1. поскольку в столбце F есть два нуля, это не может быть  3. остальные переменные инвертировать  2. для того, чтобы в последней строке таблицы получилась  4. видим, что эти условия в точности совпадают с  выражение, включающее только операции «ИЛИ» (логическое  не нужно, так как они равны 1  единица, нужно применить операцию «НЕ» (инверсию) к  выражением 1, это и есть правильный ответ сложение), потому что в этом случае в таблице был бы только  переменным, значения которых в этой строке равны нулю,  x один ноль, поэтому варианты 2 и 4 отпадают: то есть к x1, x3, x6 и x7; 3   1)2 x  x x 1)1 xx 6 7    x 1)4 x x x 5 x 7 x 4  2 x 5 x 6 x 7 x 6 x 3 x 3 x 5       x x 4 2 2 4 x1 1 1 0 x2 1 0 1 x3 x4 1 0 0 1 1 0 x5 1 1 1 x6 1 1 0 x7 1 0 0 F 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 1 0 x2 1 1 0 x3 1 0 1 x4 0 1 1 x5 0 1 1 F 1 0 1

Логические выражения, содержащие более трёх переменных Задача 6 Александра заполняла таблицу истинности для выражения F.  Она успела заполнить лишь небольшой фрагмент таблицы:  x1 x2 x3 x4 x5 x6 x7 x8 F   1 0 1 0   0     1   1               0 1             Каким выражением может быть 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

Логические выражения, содержащие более трёх переменных Задача 7 Александра заполняла таблицу истинности для выражения F. Она  успела заполнить лишь небольшой фрагмент таблицы:  x1 x2 x3 x4 x5 x6 x7 x8 F   0 1 1 1         Каким выражением может быть 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 1   1       0             0 1