Таблица истинности — это математический инструмент, который позволяет определить значение сложного логического выражения при всех возможных комбинациях исходных данных. Формально, это таблица, где каждый столбец соответствует переменной или подформуле, а строки отражают уникальные наборы значений этих переменных (0 — «ложь», 1 — «истина»). Последний столбец показывает итоговый результат выражения, что делает таблицы незаменимыми для анализа логических закономерностей, проверки равносильности формул и выявления тавтологий или противоречий.
Представьте, что вы проектируете цифровую схему, анализируете условие в программе или проверяете корректность математического доказательства. Во всех этих сценариях таблицы истинности становятся вашим главным помощником. Они не только упрощают работу с булевой алгеброй, но и раскрывают, как комбинации операций конъюнкции, дизъюнкции, отрицания, импликации и эквивалентности влияют на итоговый результат.
Ознакомившись с данной статьей, вы научитесь:
— строить таблицы для многоуровневых формул с приоритетом операций;
— определять равносильность логических выражений;
— анализировать тождественно истинные и ложные формулы.
Рассмотрим комплексные логические выражения: более сложные высказывания или формулы алгебры логики, которые получаются из простейших, базовых высказываний. Готовы погрузиться в мир логических операций и научиться видеть закономерности за сложными выражениями? Тогда начинаем!
Алгоритм построения таблиц истинности
Алгоритм построения таблиц истинности для таких формул будет иметь следующие этапы.
- Шаг 1. В первом столбце таблицы записываем все возможные комбинации значений переменных. Каждая комбинация представляет собой уникальный набор значений переменных. В общем случае, если переменных $n$, то различных $n$-мерных наборов переменных существует $2^{n}$.
Замечание. Комбинации переменных в столбцах будем располагать в порядке возрастания соответствующего бинарного числа (таблицы 2.2.1 и 2.2.2).
- Шаг 2. Вычисляем значение формулы на каждом наборе. Любая рассматриваемая логическая формула является комбинацией элементарных высказываний и может быть вычислена последовательно, при помощи подстановок определенных ранее значений.
Замечание. Учитывайте приоритет операций при построении таблиц истинности: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция. Используйте скобки для изменения порядка операций: действия в скобках выполняются в первую очередь.
Теоретический материал
Логическое выражение или формула, которая является истинной при любых значениях, входящих в неё переменных, называется тождественно истинной или тавтологией.
Математическая запись: $\forall x_{1},x_{2},\ldots,x_{n}$ формула $F\left( x_{1},x_{2},\ldots,x_{n} \right) = 1$.
Тождественно ложная формула или противоречие (контрадикция или антиномия) — это логическое выражение, которое всегда возвращает ложь, независимо от значений переменных, входящих в это выражение.
Математическая запись: $\forall x_{1},x_{2},\ldots,x_{n}$ формула $F\left( x_{1},x_{2},\ldots,x_{n} \right) = 0$.
Две формулы математической логики будут считаться равносильными, если они на любом наборе входящих в формулу аргументов примут одинаковые значения. Для обозначения равносильности формул используют значок $\equiv$.
Формулы алгебры логики принято обозначать большими латинскими буквами, но на практике также используются маленькие буквы или просто указывается логическое выражение.
Практический материал
2.4.1. Построить таблицу истинности для формулы $H\left( x_{1},x_{2} \right) = \left( x_{1} \rightarrow x_{2} \right) \land \left( \overline{x}_{1} \vee x_{2} \right)$.
Решение.
- Составляем все возможные комбинации переменных $x_{1}$ и $x_{2}$: 00, 01, 10, 11.
- Определяем значение импликации $x_{1} \rightarrow x_{2}$ для каждой комбинации.
- Определяем значение $\overline{x}_{1}$ и дизъюнкции $\overline{x}_{1} \vee x_{2}$ для каждой комбинации.
- Определяем конъюнкцию этих двух выражений, чтобы получить итоговое значение $H\left( x_{1},x_{2} \right)$.
- Записываем результаты в таблицу истинности.
Таблица 2.4.1 — Таблица истинности для формулы $H\left( x_{1},x_{2} \right)$
| $x_{1}$ | $x_{2}$ | $\overline{x}_{1}$ | $x_{1} \rightarrow x_{2}$ | $\overline{x}_{1} \vee x_{2}$ | $\left( x_{1} \rightarrow x_{2} \right) \land \left( \overline{x}_{1} \vee x_{2} \right)$ |
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 |
2.4.2. Построить таблицу истинности для формулы $H_{1}\left( x_{1},x_{2} \right) = \left( x_{1} \land \overline{x}_{2} \right) \vee \left( x_{2} \rightarrow x_{1} \right)$.
2.4.3. Построить таблицу истинности для формулы $H_{2}\left( x_{1},x_{2} \right) = \overline{x_{1} \vee x_{2}} \leftrightarrow \left( x_{1} \oplus x_{2} \right)$.
2.4.4. Построить таблицу истинности для формулы $H_{3}\left( x_{1},x_{2} \right) = \left( x_{1} \rightarrow \overline{x}_{2} \right) \land \left( \overline{x}_{1} \vee x_{2} \right)$.
2.4.5. Построить таблицу истинности для формулы $F\left( x_{1},x_{2},x_{3} \right) = x_{1} \land x_{2} \vee \overline{x}_{3}$.
Решение.
- Составляем все возможные комбинации переменных $x_{1}, x_{2}, x_{3}$, их будет $2^{3} = 8$, (000, 001, 010, 011, 100, 101, 110, 111).
- Определяем приоритет выполнения операций и вычисляем значения каждой комбинации переменных: вычисляем значение $x_{1} \land x_{2}$ для каждого набора; вычисляем значение $\overline{x}_{3}$ для каждого набора; вычисляем значение $x_{1} \land x_{2} \vee \overline{x}_{3}$, зная значения $x_{1} \land x_{2}$ и $\overline{x}_{3}$.
- Записываем результаты в таблицу истинности.
Таблица 2.4.2 — Таблица истинности для формулы $F\left( x_{1},x_{2},x_{3} \right)$
| $x_{1}$ | $x_{2}$ | $x_{3}$ | $x_{1} \land x_{2}$ | $\overline{x}_{3}$ | $x_{1} \land x_{2} \vee \overline{x}_{3}$ |
| 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 1 |
2.4.6. Построить таблицу истинности для формулы $F_{1}\left( x_{1},x_{2},x_{3} \right) = \overline{x_{1} \vee x_{2}} \rightarrow x_{3}$.
2.4.7. Построить таблицу истинности для формулы $F_{2}\left( x_{1},x_{2},x_{3} \right) = \left( x_{1} \rightarrow x_{2} \right) \oplus x_{3}$.
2.4.8. Построить таблицу истинности для формулы $F_{3}\left( x_{1},x_{2},x_{3} \right) = \left( x_{1} \land x_{2} \right) | x_{3}$.
2.4.9. Построив таблицу истинности, сравните следующие логические формулы и определите, являются ли они равносильными:
$f_{1}\left( x_{1},x_{2} \right) = x_{1} \rightarrow x_{2}$;
$f_{2}\left( x_{1},x_{2} \right) = \overline{x}_{1} \vee x_{2}$.
Решение.
Определяем значение наборов переменных. Вычисляем значения формул $f_{1}$ и $f_{2}$ на каждом наборе. Для $f_{1}$ вычислим значение операции импликация; для $f_{2}$ сначала найдем отрицание: $\overline{x}_{1}$, потом — дизъюнкцию: $\overline{x}_{1} \vee x_{2}$. Строим совместную таблицу истинности для $f_{1}$ и $f_{2}$.
Таблица 2.4.3 — Таблица истинности для формул $f_{1}$ и $f_{2}$
| $x_{1}$ | $x_{2}$ | $\overline{x}_{1}$ | $x_{1} \rightarrow x_{2}$ | $\overline{x}_{1} \vee x_{2}$ |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 |
Два крайних столбца, соответствующие формулам $f_{1}$ и $f_{2}$ совпадают для каждого набора переменных $x_{1}$ и $x_{2}$, это позволяет сделать вывод, что данные формулы равносильны.
2.4.10. Построив таблицу истинности, сравните следующие логические формулы и определите, являются ли они равносильными:
$f_{1}\left( x_{1},x_{2} \right) = \overline{\overline{p \land q}} \rightarrow (p \land q)$;
$f_{2}\left( x_{1},x_{2} \right) = \left( \overline{p} \vee \overline{q} \right) \rightarrow \left( \overline{p} \vee \overline{q} \right)$.
Решение.
При определении значений формул важно учесть приоритет операций и тот факт, что в первую очередь выполняются операции в скобках.
Для формулы $f_{1}$ последовательно выполняются операции: конъюнкция, двойное отрицание и импликация.
Для формулы $f_{2}$ — отрицание, дизъюнкция и импликация.
Таблица 2.4.4 — Таблица истинности для формулы $f_{1}$
| $p$ | $q$ | $p \land q$ | $\overline{p \land q}$ | $\overline{\overline{p \land q}}$ | $\overline{\overline{p \land q}} \rightarrow (p \land q)$ |
| 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 |
Таблица 2.4.5 — Таблица истинности для формулы $f_{2}$
| $p$ | $q$ | $\overline{p}$ | $\overline{q}$ | $\overline{p} \vee \overline{q}$ | $\left( \overline{p} \vee \overline{q} \right) \rightarrow \left( \overline{p} \vee \overline{q} \right)$ |
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 |
Формулы равносильны, так как их значения совпадают. Обратите внимание, что формулы $f_{1}$ и $f_{2}$ являются тождественно истинными.
2.4.11. Построив таблицу истинности, сравните следующие логические формулы и определите, являются ли они равносильными:
$f_{1}\left( x_{1},x_{2} \right) = (p \leftrightarrow q) \land \left( \overline{p \leftrightarrow q} \right)$;
$f_{2}\left( x_{1},x_{2} \right) = (p \oplus q) \land \left( \overline{p \oplus q} \right)$.
Решение.
Для формулы $f_{1}$ сначала выполняются операции в скобках — это эквивалентность и отрицание эквивалентности, потом конъюнкция.
Для формулы $f_{2}$ последовательно выполняются операции в скобках: строгая дизъюнкция, отрицание строгой дизъюнкции; и в последнюю очередь — конъюнкция.
Таблица 2.4.6 — Таблица истинности для формулы $f_{1}$
| $p$ | $q$ | $p \leftrightarrow q$ | $\overline{p \leftrightarrow q}$ | $(p \leftrightarrow q) \land \left( \overline{p \leftrightarrow q} \right)$ |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 |
Таблица 2.4.7 — Таблица истинности для формулы $f_{2}$
| $p$ | $q$ | $p \oplus q$ | $\overline{p \oplus q}$ | $(p \oplus q) \land \left( \overline{p \oplus q} \right)$ |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 |
Формулы равносильны, так как их значения совпадают. Обратите внимание, что формулы $f_{1}$ и $f_{2}$ являются тождественно ложными.
2.4.12. Построив таблицу истинности, сравните следующие логические формулы и определите, являются ли они равносильными:
$f_{1}\left( x_{1},x_{2} \right) = x_{1} \leftrightarrow \left( \overline{x}_{1} \vee x_{2} \right)$;
$f_{2}\left( x_{1},x_{2} \right) = \left( x_{1} \land \overline{x}_{2} \right) \vee \left( \overline{x}_{1} \land x_{2} \right)$.
2.4.13. Построив таблицу истинности, сравните следующие логические формулы и определите, являются ли они равносильными:
$f_{1}(p,q) = (p \downarrow q) \downarrow (p \downarrow q)$;
$f_{2}(p,q) = p \vee q$.
2.4.14. Построив таблицу истинности, сравните следующие логические формулы и определите, являются ли они равносильными:
$f_{1}(A,B) = A \leftrightarrow B$;
$f_{2}(A,B) = (A \rightarrow B) \land (B \rightarrow A)$.
2.4.15. Построив таблицу истинности, сравните следующие логические формулы и определите, являются ли они равносильными:
$f_{1}\left( x_{1},x_{2},x_{3} \right) = x_{1} \leftrightarrow x_{2} \land x_{3}$;
$f_{2}\left( x_{1},x_{2},x_{3} \right) = \left( \overline{x}_{1} \vee x_{2} \land x_{3} \right) \land \left( \overline{x}_{2} \vee \overline{x}_{3} \vee x_{1} \right)$.
Решение.
Учитывая приоритет операций для формулы $f_{1}$ сначала выполняется конъюнкция, потом эквиваленция.
Таблица 2.4.8 — Таблица истинности для формулы $f_{1}$
| $x_{1}$ | $x_{2}$ | $x_{3}$ | $x_{2} \land x_{3}$ | $f_{1}$ |
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 |
Для формулы $f_{2}$ сначала выполняем операции в первой скобке: отрицание ($\overline{x}_{1}$), конъюнкция ($x_{2} \land x_{3}$) и дизъюнкция ($\overline{x}_{1} \vee x_{2} \land x_{3}$); потом — операции второй скобки: отрицание ($\overline{x}_{2}, \overline{x}_{3}$) и дизъюнкция ($\overline{x}_{2} \vee \overline{x}_{3} \vee x_{1}$); в последнюю очередь — конъюнкция двух скобок.
Таблица 2.4.8 — Таблица истинности для формулы $f_{2}$
| $x_{1}$ | $x_{2}$ | $x_{3}$ | $\overline{x}_{1}$ | $x_{2} \land x_{3}$ | $\overline{x}_{1} \vee x_{2} \land x_{3}$ | $\overline{x}_{2}$ | $\overline{x}_{3}$ | $\overline{x}_{2} \vee \overline{x}_{3}$ | $\overline{x}_{2} \vee \overline{x}_{3} \vee x_{1}$ | $f_{2}$ |
| 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
Из таблиц видно, что формулы равносильны.
2.4.16. Построив таблицу истинности, сравните следующие логические формулы и определите, являются ли они равносильными:
$f_{1}\left( x_{1},x_{2},x_{3} \right) = \left( x_{1} \rightarrow x_{2} \right) \oplus \left( \overline{x}_{1} \downarrow x_{3} \right)$;
$f_{2}\left( x_{1},x_{2},x_{3} \right) = \left( \overline{x}_{1} \downarrow x_{2} \right) \oplus \left( \left( x_{1} \oplus x_{2} \right) \land \overline{x}_{3} \right)$.
Решение.
Вычисляем значения формулы $f_{1}$: выполняем операции в скобках — импликацию, отрицание и стрелку Пирса, далее находим строгую дизъюнкцию выражений в скобках.
Таблица 2.4.9 — Таблица истинности для формулы $f_{1}$
| $x_{1}$ | $x_{2}$ | $x_{3}$ | $x_{1} \rightarrow x_{2}$ | $\overline{x}_{1}$ | $\overline{x}_{1} \downarrow x_{3}$ | $f_{1}$ |
| 0 | 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 1 |
Сравним полученные значения со значениями формулы $f_{2}$ на этих же наборах переменных.
Вычисляем значения формулы $f_{2}$: выполняем операции в первой скобке: отрицание и стрелку Пирса; потом — операции второй скобки: отрицание, строгую дизъюнкцию (так как она выделена скобками), конъюнкцию; в последнюю очередь — строгую дизъюнкцию выражений первой и второй скобок.
Таблица 2.4.10 — Таблица истинности для формулы $f_{2}$
| $x_{1}$ | $x_{2}$ | $x_{3}$ | $\overline{x}_{1}$ | $\overline{x}_{1} \downarrow x_{2}$ | $x_{1} \oplus x_{2}$ | $\overline{x}_{3}$ | $\left( x_{1} \oplus x_{2} \right) \land \overline{x}_{3}$ | $f_{2}$ |
| 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
Функции $f_{1}$ и $f_{2}$ не являются равносильными, так как их значения различны на наборах: 000, 001, 011, 100, 101, 111.
2.4.17. Построив таблицу истинности, сравните следующие логические формулы и определите, являются ли они равносильными:
$f_{1}\left( x_{1},x_{2},x_{3} \right) = x_{1} \land \left( x_{2} \land x_{3} \right)$;
$f_{2}\left( x_{1},x_{2},x_{3} \right) = \overline{\overline{x}_{1} \vee \left( \overline{x}_{2} \vee \overline{x}_{3} \right)}$.
2.4.18. Построив таблицу истинности, сравните следующие логические формулы и определите, являются ли они равносильными:
$f_{1}(p,q,r) = p \downarrow (q \downarrow r)$;
$f_{2}(p,q,r) = p \vee \overline{(q \vee r)}$.
2.4.19. Построив таблицу истинности, сравните следующие логические формулы и определите, являются ли они равносильными:
$f_{1}(p,q,r) = (p \vee q) | (q \vee r)$;
$f_{2}(p,q,r) = \overline{(p \vee q) \land (q \vee r)}$.
Задания для самостоятельной работы
2.7.4. Построить таблицу истинности для формулы:
$H\left( x_{1},x_{2} \right) = \text{(}x_{1}\ |\ \overline{x}_{2}\text{)}.$
2.7.5. Построить таблицу истинности для формулы:
$H\left( x_{1},x_{2} \right) = \overline{x_{1} \land x_{2}} \oplus x_{2}.$
2.7.6. Построить таблицу истинности для формулы:
$H\left( x_{1},x_{2} \right) = \left( x_{1} \downarrow x_{2} \right) \vee \overline{x}_{1}.$
2.7.7. Построить таблицу истинности для формулы:
$F_{3}\left( x_{1},x_{2},x_{3} \right) = \overline{x_{1} \vee \left( x_{2} \land x_{3} \right)}.$
2.7.8. Построить таблицу истинности для формулы:
$F_{3}\left( x_{1},x_{2},x_{3} \right) = \left( x_{1} \rightarrow x_{2} \right) \downarrow x_{3}.$
2.7.9. Построить таблицу истинности для формулы:
$F_{3}\left( x_{1},x_{2},x_{3} \right) = \left( x_{1} \middle| x_{2} \right) \vee \left( x_{2} \land x_{3} \right).$
2.7.10. Построив таблицу истинности, сравните следующие логические формулы и определите, являются ли они равносильными:
$f_{1}\left( x_{1},x_{2} \right) = x_{1} \leftrightarrow \left( x_{1} \land \overline{x}_{2} \right);$
$f_{2}\left( x_{1},x_{2} \right) = \left( x_{1} \land \overline{x}_{2} \right) \vee \left( \overline{x}_{1} \land x_{2} \right).$
2.7.11. Построив таблицу истинности, сравните следующие логические формулы и определите, являются ли они равносильными:
$f_{1}(p,q) = (p\ |\ q)\ |\ (p\ |\ q);$
$f_{2}(p,q) = p \land q.$
2.7.12. Построив таблицу истинности, сравните следующие логические формулы и определите, являются ли они равносильными:
$f_{1}(A,B) = A \leftrightarrow B;$
$f_{2}(A,B) = (A \land B) \vee \left( \overline{A} \land \overline{B} \right).$
2.7.13. Построив таблицу истинности, сравните следующие логические формулы и определите, являются ли они равносильными:
$f_{1}\left( x_{1},x_{2},x_{3} \right) = x_{1} \land \left( \overline{x}_{1} \land x_{3} \right);$
$f_{2}\left( x_{1},x_{2},x_{3} \right) = \overline{\overline{x}_{1} \vee \left( \overline{\overline{x}}_{1} \vee \overline{x}_{3} \right)}.$
2.7.14. Построив таблицу истинности, сравните следующие логические формулы и определите, являются ли они равносильными:
$f_{1}(p,q,r) = (p\ |\ q)\,|\ (p\,|\, r);$
$f_{2}(p,q,r) = \overline{(p \land q)}\ |\,\overline{(p \land r)}.$
2.7.15. Построив таблицу истинности, сравните следующие логические формулы и определите, являются ли они равносильными:
$f_{1}(p,q,r) = p\ |\ (q\ \downarrow r);$
$f_{2}(p,q,r) = \overline{p \land \overline{\overline{q \vee r}}}.$