Таблицы истинности сложных выражений

Таблица истинности — это honest-способ проверить логическое выражение: перебрать все наборы значений переменных и посчитать результат для каждого.

Таблица истинности логического выражения — это таблица, где в каждой строке записан один из возможных наборов значений переменных, а в столбце результата — значение всего выражения на этом наборе. Если переменных n, то таблица содержит 2^n строк.

Зачем это нужно? Логические выражения встречаются повсюду: в условиях if, в SQL-запросах, в схемах из логических элементов, в задачах ЕГЭ. Иногда выражение выглядит запутанным, и «прикинуть в уме», когда оно истинно, не получается. Таблица истинности убирает догадки: мы честно перебираем все случаи и видим ответ целиком.

Сколько строк: правило 2 в степени n

Каждая логическая переменная принимает ровно два значения: 0 (ложь) или 1 (истина). Если переменных две, наборов 2 · 2 = 4. Если три — 2 · 2 · 2 = 8. В общем виде для n переменных получается 2^n строк.

Видно, что таблица растёт очень быстро: уже для 10 переменных это 1024 строки. Поэтому вручную обычно работают с 2–4 переменными, а для большего поручают перебор компьютеру.

Порядок наборов: считаем в двоичной системе

Чтобы ничего не пропустить и не повторить, наборы выписывают в строгом порядке — как двоичные числа от 0 до 2^n − 1. Для трёх переменных A B C это даёт ровно такую последовательность:

000
001
010
011
100
101
110
111

Каждая следующая строка — это предыдущая плюс единица в двоичной системе. Такой порядок гарантирует, что встретятся все 8 наборов и ни один дважды. Самый правый столбец (C) меняется в каждой строке, средний (B) — через две, левый (A) — через четыре.

Промежуточные столбцы: разбиваем по приоритету

Сложное выражение считают не сразу, а по частям. Сначала выполняются операции с высоким приоритетом, потом с низким. Порядок такой:

1. Отрицание ¬ (НЕ) — самое сильное;
2. Конъюнкция ∧ (И);
3. Дизъюнкция ∨ (ИЛИ);
4. Импликация → и эквивалентность ≡ — самые слабые.

Скобки, как в арифметике, меняют порядок и считаются в первую очередь. Для каждого «кусочка» выражения заводят отдельный столбец — так ошибиться почти невозможно.

Полный разбор примера: (A ∨ B) ∧ ¬C

Возьмём выражение F = (A ∨ B) ∧ ¬C. В нём три переменные, значит 8 строк. Разобьём его на части по приоритету: сначала посчитаем A ∨ B (в скобках) и ¬C (отрицание), а потом соединим их операцией ∧.

Заполняем промежуточные столбцы, двигаясь слева направо. В таблице ниже хорошо видно, как из простых столбцов собирается итоговый F:

Разберём одну строку подробно, например A=1, B=0, C=1. Считаем: A ∨ B = 1 ∨ 0 = 1; ¬C = ¬1 = 0; итог F = 1 ∧ 0 = 0. Сходится с таблицей.

Считаем таблицу кодом

Перебрать все наборы вручную долго и легко ошибиться. Питон делает это за нас: itertools.product([0,1], repeat=3) выдаёт ровно те 8 наборов в нужном порядке. Запустите код — он построит ту же самую таблицу для F = (A ∨ B) ∧ ¬C и выведет промежуточные столбцы.

from itertools import product

print(f"{'A':>2}{'B':>3}{'C':>3} | {'A∨B':>4}{'¬C':>4} | {'F':>3}")
print("-" * 28)

for A, B, C in product([0, 1], repeat=3):
    a, b, c = bool(A), bool(B), bool(C)
    AB = a or b          # дизъюнкция
    nC = not c           # отрицание
    F = AB and nC        # конъюнкция двух частей
    print(f"{A:>2}{B:>3}{C:>3} | {int(AB):>4}{int(nC):>4} | {int(F):>3}")

В выводе вы увидите единицы в столбце F ровно в трёх строках — 010, 100 и 110. Это и есть наборы, при которых выражение истинно. Чтобы проверить другое выражение, поменяйте строку с F — структура перебора останется прежней.

Тавтология, противоречие, выполнимость

Когда таблица готова, по столбцу результата выражения делят на три класса.

Тавтология — выражение истинно на всех наборах (в столбце результата только единицы). Пример: A ∨ ¬A.
Противоречие — выражение ложно на всех наборах (только нули). Пример: A ∧ ¬A.
Выполнимое выражение — истинно хотя бы на одном наборе (есть хоть одна единица).

Наше F = (A ∨ B) ∧ ¬C — выполнимое: в столбце есть и нули, и единицы. Оно не тавтология (есть нули) и не противоречие (есть единицы). Любая тавтология тоже выполнима, а вот противоречие — единственный класс, который выполнимым не является.

Как найти наборы, при которых выражение истинно

Это самый частый вопрос в задачах. Алгоритм прост: построить таблицу и выписать те строки, где в столбце результата стоит 1. Для F = (A ∨ B) ∧ ¬C таких строк три:

• A=0, B=1, C=0
• A=1, B=0, C=0
• A=1, B=1, C=0

Закономерность видна сразу: F истинно, когда C = 0 и при этом хотя бы одна из A, B равна 1. Именно так таблица истинности превращает запутанную формулу в понятное словесное условие.

Частые ошибки

• Пропуск или повтор наборов. Выписывайте их строго как двоичные числа от 000 до 111 — тогда все 2^n строк появятся ровно по разу.
• Неверный приоритет. ¬ считают раньше ∧, а ∧ — раньше ∨. Если сомневаетесь — ставьте скобки и заводите отдельный столбец.
• Путаница тавтологии и выполнимости. Тавтология — все единицы; выполнимость — хотя бы одна. Это разные вещи.
• Игнор скобок. (A ∨ B) ∧ ¬C и A ∨ (B ∧ ¬C) дают разные таблицы — скобки считаются первыми.

Коротко

• Для n переменных в таблице 2^n строк; наборы выписывают как двоичные числа по порядку.
• Сложное выражение считают по частям: отрицание, потом И, потом ИЛИ; скобки — в первую очередь. Каждой части — свой столбец.
• Тавтология — всегда истинно, противоречие — всегда ложно, выполнимое — истинно хотя бы раз.
• Чтобы найти, когда выражение истинно, выписывают строки с 1 в столбце результата.