Подготовка к ЕГЭ, задание 2, часть 1. Построение таблиц истинности и логических схем
Рекомендации по выполнению задания. Необходимо повторить темы «Логические значения, операции и выражения», «Таблицы истинности» (особенно таблицы истинности для конъюнкции и дизъюнкции). Для лучшего понимания выполняемого здесь разбора темы и решения задач в ней рекомендуется повторить тему "Значение логического выражения (ОГЭ, задания 3 и 8)" на данном сайте, подробно рассматриваемую при подготовке к ОГЭ. Презентация "Основы математической логики, 10-11 класс" на данном сайте - в помощь.
Типичные ошибки и рекомендации по их предотвращению. Игнорирование прямо указанного в условии задания требования, что заполненная таблица истинности не должна содержать одинаковые строки. Это приводит к внешне правдоподобному, но на самом деле неверному решению.
Дополнительные логические операции
-
Импликация (А → В), или следование — бинарная логическая связка, по своему применению приближенная к союзам «если…, то…». Синоним: следование.
Эта операция является сокращенной записью выражения (¬А ˅ В) или же (¬А & ¬В) ˅ (А & В) - если упростите второе выражение, то получите приведенное здесь первым.
Импликация дает исключение № 3 в логике:
Импликация ложна, когда из истины следует ложь:
( А → В = 0 при А=1 и В=0 ).
- Логическая эквиваленция А ≡ В , или равносильность (обозначается знаками ↔ или ≡ ) — логическое выражение, которое является истинным тогда, когда оба простых логических выражения имеют одинаковую истинность. Эквиваленция А≡B равна 1 тогда и только тогда, когда оба значения одновременно равны 0 или одновременно равны 1.
- Исключающее ИЛИ А ⊕ В , или сложение по модулю два (XOR) – логическая операция, обратная эквиваленции. Результат ее выполнения равен 1 только при разных значениях операндов.
Эту операцию нередко сравнивают с дизъюнкцией потому, что они очень похожи по свойствам и обе имеют сходство с союзом «или» в повседневной речи. Сравните правила для этих операций:
¬А ∨ B истинно, если истинно A или B, или оба сразу («хотя бы один из двух»);
¬А ⊕ B истинно, если истинно A или B, но не оба сразу («только один из двух»). Операция ⊕ исключает вариант «оба сразу» и по этой причине называется исключающим «ИЛИ».
Иногда для упрощения выражений полезны формулы де Моргана:
¬ (A ∧ B) = ¬ A ∨ ¬ B
¬ (A ∨ B) = ¬ A ∧ ¬ B
Порядок выполнения логических операций: если в выражении нет скобок, сначала выполняются все операции «НЕ», затем в следующем порядке: «И», «ИЛИ», «импликация» и самая последняя – «эквивалентность». Можно запомнить закономерность: порядок выполнения логических операций зависит от количества букв в их названии).
Таблица истинности выражения определяет его значения при всех возможных комбинациях исходных данных. Если известна только часть таблицы истинности, соответствующее логическое выражение однозначно определить нельзя, поскольку частичной таблице могут соответствовать несколько разных логических выражений (не совпадающих для других вариантов входных данных).
Количество разных логических функций, удовлетворяющих неполной таблице истинности, равно 2k, где k – число отсутствующих строк. Например, полная таблица истинности выражения с тремя переменными содержит 23=8 строчек, если заданы только 6 из них, то можно найти 28 - 6 = 22 = 4 разных логических функции, удовлетворяющие этим 6 строчкам (но отличающиеся в двух оставшихся).
Построим таблицу истинности для всех рассматриваемых нами действий:
Данная таблица построена для всех рассматриваемых нами действий. В ней много правил, но всего три исключения, выделенных красным цветом:
А & В = 1, когда все операнды истинны;
А V В = 0, когда все операнды ложны;
А → В = 0 при А = 1 и В = 0.
При вычислении логических выражений следует помнить, что логические операции выполняются в следующем порядке: НЕ, И, ИЛИ, ИМПЛИКАЦИЯ, ЭКВИВАЛЕНЦИЯ и ИСКЛЮЧАЮЩЕЕ ИЛИ. Как и в математике, скобки могут поменять последовательность выполнения операций.
При этом любая операция, которая выполняется последней, может поменять результат, а операция НЕ, стоящая перед скобками, "переворачивает" результат, полученный в скобках (то есть истина преаращается в ложь, а ложь - в истину).
Применяя все выше сказанное, будем вычислять значение логического выражения от последней операции к первой, используя только два исключения и не открывая скобки. Для этого решение задач начиаем с анализа столбца значений результата F, определяем в нем исключение и далее уже решаем.
При решении задач будем использовать таблицы истинности выражения, которые состоят из строк со всеми возможными комбинациями значений переменных, то есть они полностью определяют значение выражения.
В общем случае таблицы истинности имеют размер 2N строк комбинаций для N независимых логических переменных.
Целью данного урока является обучение составлению и анализу таблиц истинности для различных логических выражений, что мы рассмотрим далее на примерах различных задач в заданиях, соответствующих порядку заданий по теме.
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
Задача 1
Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.
Дан фрагмент таблицы истинности выражения F:
Какое выражение соответствует F?
Решение:
Необходимо выбрать такое выражение, результат выполнения которого будет равен значению F в таблице.
Так как в таблице F = 0 в двух строках таблицы, а F = 1 – только в одной, то будем искать выражение, в котором все действия – операция И, в которой y и z заданы с инверсией. Этому соответствует выражение 3.
Ответ: 3
Задача 2
Дан фрагмент таблицы истинности выражения F:
Какое выражение соответствует F?
Решение:
Так как в таблице F= 0 в двух строках таблицы, а F = 1 –только в одной, то будем искать выражение, в котором все действия связаны операцией И, а также х3, х5 и х7 заданы с инверсией. Этому соответствует выражение 1.
Ответ: 1
Задача 3
Дан фрагмент таблицы истинности выражения F:
Одно из приведенных ниже выражений истинно при любых значениях переменных x1, x2,x3, x4, x5. Укажите это выражение.
Решение.
Последней операцией во всех приведенных выражений является импликация, в которой результат равен 0 в единственном случае: 1®0 = 0. Нужно найти выражение, результат выполнения которого при заданных во всех строках таблицы соответствует заданному там же значению F.
Выражения 1) и 2) будут равны 0 в третьей строке таблицы, а выражение 4) – в первой, где F=1. И только результат выражения 3) во всех строках таблицы соответствует заданному.
Ответ: 3
Задача 4
Дан фрагмент таблицы истинности выражения F:
Какое выражение соответствует F?
1) (х1 ᴧ x2) v (x3 ᴧ x4) v (x5 ᴧ x6)
2) (х1 ᴧ x3) v (x3 ᴧ x5) v (x5 ᴧ x1)
3) (х2 ᴧ x4) v (x4 ᴧ x6) v (x6 ᴧ x2)
4) (х1 ᴧ x4) v (x2 ᴧ x5) v (x3 ᴧ x6)
Решение.
Во всех приведенных вариантов выражений последними вычисляемыми действиями будут операции ИЛИ, тогда F = 0, если выражения во всех трех скобках равны нулю.
Однако внутри скобок все выражения – операция И, а она равна 0 тогда, когда оба множества в ней не будут равны 1. Тогда остается найти такую строку в заданных выражениях, где это условие соблюдается во всех строках таблицы, и это будет выражение 2.
Ответ: 2
Задача 5 (пробник из Демоверсии - 2021)
Миша заполнял таблицу истинности функции F = (x ∨ y) ∧ ¬(y ≡ z) ∧ ¬w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z. В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Решение
Последнее действие здесь – И, тогда все части выражения истинны. При этом однозначно, что переменная w=0 (это столбец 4 в заданной таблице, т.к. только он не содержит единиц) и z<>x. Составим таблицу истинности для заданного выражения, записав условие ¬ (z=x) как z<>x.
Удалив все лишние строки, получаем:
Тогда из строки 1 получаем w в четвертом столбце (все значения w=0). Первый столбец в заданной таблице с одной единицей соответствует переменной z. Тогда в третьем столбце будет переменная х, которая в одной строке вместе с w равна единице. И второй столбец остается за переменной у.
Программа на Python:
В результате выполнения программы получаем таблицу:
0 1 0 0
1 0 0 1
1 1 0 0
и проводим анализ результатов, как и выше.
Ответ: zyxw
Задача 6 (№ 85 Джобс 07.09.2020)
Логическая функция F задаётся выражением (x ≡ ¬z) → ((x ∨ w) ≡ y). На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки.
Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x,y,z,w. В ответе напишите буквы x,y,z,w в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Решение
Последнее действие здесь – ИЛИ, тогда обе части выражения истинны. Тогда однозначно получаем w=1, что соответствует третьему столбцу заданной таблицы.
Построим таблицу истинности для заданного выражения:
Удалим ненужные строки и столбцы, получим:
Программа на Python:
Здесь возможен второй вариант написания выражения F - через импликацию «<=» :
f = (x == (not(z))) <= ((x or w) == y)
В результате выполнения программы получаем таблицу:
0 0 1 1
0 1 0 1
1 0 0 0
1 0 1 0
и проводим анализ результатов, как и выше.
Ответ: xwyz
© 2018–2024 Звездина Вера Алексеевна, v_zvezdina@mail.ru
