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

Таблица истинности — это математический инструмент, который позволяет определить значение сложного логического выражения при всех возможных комбинациях исходных данных. Формально, это таблица, где каждый столбец соответствует переменной или подформуле, а строки отражают уникальные наборы значений этих переменных (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}}}.$