Как построить таблицу истинности: пошаговое решение

Дано: формула $F = (A \vee B) \to (\neg A \wedge C)$ от трёх переменных. Найти: таблицу истинности со всеми промежуточными столбцами и наборы, на которых формула истинна.

Метод всегда один: перебрать все $2^3 = 8$ наборов значений переменных и посчитать формулу не целиком, а по частям, в порядке приоритета операций. Ответ: формула истинна ровно на трёх наборах - 000, 001 и 011, на остальных пяти ложна, то есть она выполнима, но тавтологией не является. Калькулятор сверху строит такую же таблицу для этой и ещё трёх формул: переключи значения переменных, и нужная строка подсветится.

Решение по шагам

Дано. Формула $F = (A \vee B) \to (\neg A \wedge C)$, переменные $A$, $B$, $C$.

Найти. Полную таблицу истинности и все наборы, где $F = 1$.

Шаг 1. Размер таблицы. Переменных три, каждая принимает два значения, поэтому число строк равно числу двоичных слов длины три:

$$2^n = 2^3 = 8.$$

Шаг 2. Наборы значений. Строки нумеруются от 0 до 7, а сам набор - это двоичная запись номера строки: 000, 001, 010, 011, 100, 101, 110, 111. Старший разряд отдаём переменной $A$, младший - переменной $C$. Такой порядок не обязателен математически, но он принят в учебниках, и с ним ни один набор не потеряется: столбец $A$ идёт четырьмя нулями и четырьмя единицами, столбец $B$ чередуется парами, столбец $C$ - по одному.

Шаг 3. Разбор формулы на операции. Внешняя операция здесь одна - импликация: скобки разделили формулу на посылку $A \vee B$ и следствие $\neg A \wedge C$. Значит, промежуточных столбцов будет три: $A \vee B$, $\neg A$ и $\neg A \wedge C$, а четвёртым идёт итог $F$. Всего в таблице $3 + 4 = 7$ столбцов.

Шаг 4. Столбец $A \vee B$. Дизъюнкция ложна только тогда, когда оба слагаемых ложны. Ноль получится в строках 000 и 001, где $A = 0$ и $B = 0$; во всех остальных шести строках стоит единица.

Шаг 5. Столбцы $\neg A$ и $\neg A \wedge C$. Отрицание просто переворачивает столбец $A$: единицы в первых четырёх строках, нули в последних четырёх. Конъюнкция $\neg A \wedge C$ истинна там, где одновременно $\neg A = 1$ и $C = 1$, то есть только в строках 001 и 011.

Шаг 6. Итоговый столбец. Импликация $X \to Y$ ложна ровно в одном случае - когда посылка истинна, а следствие ложно:

$$X \to Y = 0 \iff X = 1 \text{ и } Y = 0.$$

Подставляем $X = A \vee B$ и $Y = \neg A \wedge C$ построчно:

В строках 0 и 1 посылка ложна, и импликация автоматически истинна - это и есть главная ловушка задачи. В строке 3 истинны обе части, импликация снова даёт единицу. Начиная со строки 4 переменная $A$ равна единице, поэтому $\neg A \wedge C = 0$ при истинной посылке, и весь хвост таблицы обнуляется.

Ответ. Столбец $F$ сверху вниз: 1, 1, 0, 1, 0, 0, 0, 0. Формула истинна на наборах $(0,0,0)$, $(0,0,1)$ и $(0,1,1)$ и ложна на остальных пяти; она выполнима, но не тождественно истинна.

Сколько строк и столбцов должно получиться

Число строк зависит только от количества переменных и считается по формуле

$$N = 2^n,$$

где $n$ - число различных переменных в формуле. Две переменные дают 4 строки, три - 8, четыре - 16, пять - 32. Формулу легко обосновать: каждая переменная независимо принимает два значения, а наборы - это все двоичные слова длины $n$. Повторное вхождение переменной размер таблицы не меняет: в формуле $A \wedge (A \vee B)$ переменных всё равно две, а не три.

Число столбцов заранее не фиксировано - оно равно $n$ плюс количество операций, которые ты решил вынести в отдельные столбцы. Минимально допустимый вариант: переменные и итог. На практике в контрольных требуют развёрнутую таблицу, где каждой операции отвечает свой столбец: так видно ход решения, и преподаватель может найти, на каком именно шаге ошибка. Порядок наборов при этом стандартный - двоичный счёт снизу вверх от нулевой строки, потому что тогда номер строки совпадает с числом, записанным набором.

Порядок заполнения: приоритет операций задаёт очередь столбцов

Столбцы заполняются не слева направо по записи формулы, а в порядке, в котором операции вычисляются. Порядок приоритета такой: сначала выражения в скобках, затем отрицание $\neg$, потом конъюнкция $\wedge$, потом дизъюнкция $\vee$, дальше импликация $\to$ и в самом конце эквивалентность $\leftrightarrow$. Подробный разбор с примерами лежит в статье про приоритет логических операций.

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

Значения операций удобно держать в голове как короткие правила, а не как отдельные таблички. Конъюнкция истинна только при обеих единицах, дизъюнкция ложна только при обоих нулях, импликация ложна только в случае «из истины ложь», эквивалентность истинна при совпадении значений. Четыре правила закрывают почти любую формулу базового курса.

Что читают по готовой таблице

Готовая таблица сразу отвечает на несколько типовых вопросов, и ради них её обычно и строят.

Классификация формулы. Если в столбце $F$ одни единицы, формула тождественно истинна (тавтология); одни нули - тождественно ложна (противоречие); есть и то и другое - формула выполнима, но не общезначима. Наш пример относится к третьему случаю: три единицы из восьми.

Равносильность двух формул. Строишь обе таблицы на одном наборе переменных и сравниваешь итоговые столбцы: совпали во всех строках - формулы равносильны. Именно так в одну строчку проверяются законы де Моргана и правило $A \to B = \neg A \vee B$.

Каноническая форма. По строкам с единицей собирается совершенная дизъюнктивная нормальная форма: у нас это строки 000, 001 и 011, то есть $F = (\neg A \wedge \neg B \wedge \neg C) \vee (\neg A \wedge \neg B \wedge C) \vee (\neg A \wedge B \wedge C)$. Механика перехода от строки к минтерму разобрана в материале про СДНФ, а по полученной формуле уже собирается логическая схема из элементов И, ИЛИ, НЕ.

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

• Импликацию считают как конъюнкцию. Строки 0 и 1 в нашей таблице дают единицу именно потому, что посылка ложна. «Из лжи следует что угодно» - не оговорка, а определение: ноль в столбце импликации бывает только при паре «1 и 0».
• Теряют строки. При трёх переменных строк обязано быть восемь, при четырёх - шестнадцать. Если выписывать наборы наугад, а не двоичным счётом, один-два набора обычно пропадают, и ответ становится неполным.
• Считают формулу целиком в уме. Без промежуточных столбцов ошибка в середине выражения не ловится вообще: итог не с чем сверить. Отдельный столбец на операцию стоит одной колонки, но экономит переделку всей таблицы.
• Игнорируют скобки и приоритет. Запись $A \vee B \wedge C$ означает $A \vee (B \wedge C)$: конъюнкция сильнее дизъюнкции. Посчитанное слева направо выражение даёт другой столбец и другой ответ.
• Путают порядок разрядов. Если столбец $A$ чередуется через один, а $C$ идёт четвёрками, таблица остаётся верной, но перестаёт совпадать с ответом в методичке построчно. Держи старший разряд за первой переменной.
• Отрицание применяют не к тому. $\neg A \wedge C$ и $\neg (A \wedge C)$ - разные столбцы: в первом случае отрицается только $A$, во втором вся конъюнкция. Черта или скобка сверху определяет область действия.

FAQ

Сколько строк в таблице истинности для 4 переменных? Шестнадцать: $2^4 = 16$. Общее правило - $2^n$ строк для $n$ переменных, независимо от того, сколько операций в формуле и сколько раз каждая переменная в неё входит.

Обязательно ли выписывать промежуточные столбцы? Формально нет, требуется только итог. Но в проверочных работах развёрнутую таблицу почти всегда просят: она показывает ход решения, и при ошибке в одном столбце остальные остаются зачтёнными.

Как понять, что формула тождественно истинна? Посмотреть на итоговый столбец: если в нём нет ни одного нуля, формула истинна на любом наборе значений, то есть является тавтологией. Если нет ни одной единицы - это противоречие.

В каком порядке перебирать наборы значений? Стандарт - двоичный счёт от 000 до 111, при котором номер строки совпадает с числом, записанным набором. Любой другой порядок формально допустим, но сверять такой ответ с методичкой неудобно.

Коротко

1. Считаем число строк: $N = 2^n$, где $n$ - количество различных переменных. Для $(A \vee B) \to (\neg A \wedge C)$ это $2^3 = 8$.
2. Выписываем наборы двоичным счётом от 000 до 111, старший разряд - первой переменной.
3. Разбираем формулу на операции по приоритету (скобки, $\neg$, $\wedge$, $\vee$, $\to$, $\leftrightarrow$) и заводим столбец на каждую.
4. Заполняем столбцы снизу дерева вверх; последней считается внешняя операция - она и даёт столбец $F$.
5. Ответ примера: $F$ равно 1, 1, 0, 1, 0, 0, 0, 0 - формула истинна на наборах 000, 001 и 011, выполнима, но не тавтология.