§ 2.3. Таблицы истинности логических выражений

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

Таблица истинности логического выражения перечисляет все возможные наборы значений переменных, которые в него входят, и для каждого набора указывает, чему равно всё выражение. Набор — это строка из нулей и единиц, по одному значению на каждую переменную. Верхняя строка таблицы называется шапкой: в ней подписаны столбцы.

Строить таблицу удобно по плану из восьми шагов. 1) Сосчитать переменные выражения; их число обозначают n. Переменная, записанная несколько раз, считается один раз. 2) Установить порядок операций. Сначала выполняется то, что стоит в скобках, а вне скобок действует приоритет: инверсия, затем конъюнкция, затем дизъюнкция. 3) Сосчитать операции: каждый знак ¬, ∧ или ∨ — отдельная операция. 4) Найти число столбцов: переменные плюс операции. 5) Заполнить шапку: сначала переменные, затем операции в порядке из шага 2. Последний столбец — всё выражение. 6) Найти число строк без шапки: m = 2ⁿ. Две переменные дают 4 набора, три — 8, четыре — 16. 7) Выписать наборы. Каждый набор — n-разрядное двоичное число, а все вместе они — числа от 0 до 2ⁿ − 1 по возрастанию. 8) Заполнять таблицу по столбцам слева направо: новый столбец вычисляют по таблице нужной операции из уже готовых столбцов.

Пример 1. Построим таблицу истинности выражения (A ∨ B) ∧ ¬A. Решение. Переменных две, A и B, поэтому n = 2. Скобка выполняется первой, значит, первая операция — дизъюнкция A ∨ B. Вне скобок стоят ¬ и ∧; инверсия старше, поэтому вторая операция ¬A, а конъюнкция идёт последней. Операций три, столбцов 2 + 3 = 5, строк 2² = 4.