Логические выражения и таблицы истинности

Логическое выражение связывает несколько условий с помощью операций «и», «или», «не» и других. Его результат зависит от того, какие условия истинны, а какие ложны. Таблица истинности показывает результат для каждого сочетания значений. Если результат уже известен, по таблице можно найти значения переменных, при которых он получается.

Переменные и логическая функция

В логике 1 означает истину, 0 означает ложь. Например, высказывание «7 больше 3» имеет значение 1, а «7 меньше 3» — значение 0.

Логическая переменная принимает значение 0 или 1. Буквы x, y и z обозначают переменные, а знаки между ними — операции. При вычислении одной строки во все места с одинаковой буквой подставляется одно и то же значение.

Набор значений — это значения всех переменных, взятые вместе. Например: x = 1, y = 0, z = 1. Логическая функция F для каждого набора даёт один результат: 0 или 1. Запись F(x, y, z) перечисляет переменные функции, а формула показывает, как получить результат.

Основные операции

Отрицание \neg A, или "не A", меняет значение на противоположное: \neg 0 = 1, \neg 1 = 0. Если A = 1, то \neg A = 0. При этом значение самой переменной A остаётся равным 1.

• Конъюнкция A \land B, или «A и B», равна 1 только при A = 1 и B = 1.
• Дизъюнкция A \lor B, или «A или B», равна 1, если хотя бы одно из значений равно 1. При двух единицах результат также равен 1.
• Импликация A \to B читается «если A, то B». Она равна 0 только при A = 1 и B = 0.
• Эквивалентность A \equiv B равна 1, когда значения A и B совпадают. Для этой операции также используется знак ↔.

Буквы A и B здесь могут обозначать и отдельные переменные, и целые выражения. Например, в (x \lor y) \land z сначала вычисляется x \lor y. Затем полученное значение и z соединяются операцией «и».

Почему импликация ложна только в одном случае

Смысл A \to B: если A истинно, B тоже должно быть истинно. При A = 1 и B = 0 это требование нарушено, поэтому импликация равна 0. При A = 1 и B = 1 оно выполнено, и импликация равна 1.

Если A = 0, требование «если A, то B» не нарушается ни при B = 0, ни при B = 1. Поэтому в обоих случаях импликация равна 1. В частности, из A \to B = 1 не следует, что сами A и B равны 1: они могут оба равняться 0.

Направление меняет результат. При A = 1 и B = 0 выражение A \to B равно 0, а B \to A равно 1. Поэтому перестановка частей импликации может изменить всю функцию.

Порядок вычислений

Скобки задают порядок вычислений. Если скобок нет, в школьной записи обычно действует приоритет операций: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность. Если в условии указаны другие правила или обозначения, применяются они.

Например, \neg x \lor y \land z означает (\neg x) \lor (y \land z). В записи \neg (x \lor y) отрицание относится ко всему выражению в скобках: сначала вычисляется x \lor y, затем 0 меняется на 1 или 1 на 0.

В цепочке x \to y \to z нужно отдельно знать, какую импликацию выполнять первой. Записи (x \to y) \to z и x \to (y \to z) могут давать разные результаты. Порядок здесь задают скобки или правило из условия.

Построение полной таблицы истинности

У каждой из n переменных два возможных значения, поэтому всего существует 2^n наборов. Для трёх переменных это 8 наборов, для четырёх — 16. В полной таблице каждый набор записан ровно один раз. Например, для x, y, z удобно перечислить строки по порядку от 000 до 111: так легче не пропустить ни одну.

Для функции F = (x \to y) \land z сначала вычисляется x \to y в отдельном столбце. Затем к этому результату и значению z применяется операция «и». Полученное значение F записывается в последний столбец.

В строке 101 импликация равна 0, потому что x = 1, y = 0. Поэтому F = 0 \land 1 = 0. В строке 001 импликация равна 1 и z = 1, поэтому F = 1 \land 1 = 1. Промежуточные столбцы помогают проверить вычисления по шагам.

Полная таблица и её фрагмент

Фрагмент — это часть строк полной таблицы. В нём могут быть только строки с F = 0, только с F = 1 или строки с разными результатами. По числу строк фрагмента нельзя определить число переменных: часть строк просто не показана.

«Все строки с F = 1» не обязательно означает полную таблицу. Например, у функции выше F = 1 только на трёх наборах: 001, 011, 111. В полной таблице есть ещё пять строк с F = 0. Строки в условии могут идти в любом порядке.

Пустая клетка во фрагменте означает неизвестное значение: 0 или 1. При заполнении пропусков числа из условия остаются на своих местах, а формула в каждой строке должна давать указанное значение F. Если по условию строки различны, они должны отличаться хотя бы одним значением переменной и после заполнения.

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

Равносильные преобразования

Равносильные выражения дают одинаковый результат на каждом наборе значений переменных. Одно можно заменить другим, не меняя значения функции. Более удобная запись иногда помогает быстрее понять, когда получится 0 или 1.

• A \to B = \neg A \lor B. Справа результат равен 0 только при A = 1 и B = 0, как и у импликации.
• \neg (A \land B) = \neg A \lor \neg B. Если A и B не равны 1 одновременно, хотя бы одно из них равно 0.
• \neg (A \lor B) = \neg A \land \neg B. Если не выполнено ни одно из двух условий, оба имеют значение 0.
• \neg \neg A = A. Двойное отрицание возвращает исходное значение.

Две формулы с отрицанием скобок называются законами де Моргана. Отрицание перед скобками заменяется отрицанием каждой части, а операция между ними меняется: «и» на «или», «или» на «и». Сохранение прежней операции даёт ошибку. Например, при A = 1 и B = 0 выражение \neg (A \lor B) равно 0, а \neg A \lor \neg B равно 1.

Выражение \neg x \land y \land \neg z равно 1 только для набора 010: нужны x = 0, y = 1 и z = 0 одновременно. В формуле (\neg x \land y \land \neg z) \lor (x \land \neg y \land z) две скобки соединены операцией «или». Первая равна 1 на наборе 010, вторая — на наборе 101. Значит, вся формула равна 1 на этих двух наборах, а на остальных равна 0.

Пример преобразования отрицаний есть в задании EGE-02-0004 ↗. В части \neg(\neg z \lor w) закон де Моргана переносит отрицание к каждой части и заменяет ИЛИ на И:

\neg(\neg z \lor w) = (\neg\neg z) \land \neg w.

Затем убирается двойное отрицание:

(\neg\neg z) \land \neg w = z \land \neg w.

Полученная запись сразу показывает, что эта часть равна 1 при z = 1 и w = 0. Отрицание \neg w осталось: цель преобразования — удобная запись, а не исчезновение всех знаков НЕ.

Применение в заданиях

Как по формуле определить, какая переменная стоит в каждом столбце таблицы? Почему после заполнения пропусков нужно сравнить строки между собой?

Эти вопросы разобраны на примерах в статье «Задание №2. Восстановление столбцов таблицы истинности».