Равносильность формул алгебры высказываний

Определение

Формулы алгебры высказываний $X$ и $Y$ называют равносильными (эквивалентными, тождественными), если при любых значениях переменных, входящих в эти формулы, значение истинности формул $X$ и $Y$ совпадают.

Пример

Пусть даны формулы $$X = A \rightarrow B, Y = \overline{B} \rightarrow \overline {A}.$$

Построим таблицу истинности для этих двух формул

Как видно из таблицы, истинностные значения данных формул совпадают при любых значениях $A$ и $B$, следовательно, эти две формулы равносильны. Равносильность формул $X$ и $Y$ записывается в виде $X \equiv Y$.

Теоремы о равносильности формул

Теорема. Справедливы следующие равенства формул.

1. Закон тождества $$A \equiv A$$
2. Закон коммутативности $$\begin{array}{c} A \land B \equiv B \land A \\ A \lor B \equiv B \lor A \end{array}$$
3. Закон ассоциативности $$\begin{array}{c} A \land (B \land C) \equiv (A \land B) \land C \\ A \lor (B \lor C) \equiv (A \lor B) \lor C \end{array}$$
4. Закон идемпотентности $$\begin{array}{c} A \land A \equiv A \\ A \lor A \equiv A \end{array}$$
5. Закон дистрибутивности $$\begin{array}{c} A \land (B \lor C) \equiv (A \land B) \lor (A \land C) \\ A \lor (B \land C) \equiv (A \lor B) \land (A \lor C) \end{array}$$
6. Законы де Моргана $$\begin{array}{c} \overline{A \land B} \equiv \overline{A} \lor \overline{B} \\ \overline{A \lor B} \equiv \overline{A} \land \overline{B} \end{array}$$
7. Закон двойного отрицания $$\overline{\overline{A}} \equiv A$$
8. Закон непротиворечия $$A \land \overline{A} \equiv 0$$
9. Закон исключения третьего $$A \lor \overline{A} \equiv 1$$
10. Тождества $$\begin{array}{l} A \land 1 \equiv A,~~~~~ A \land 0 \equiv 0 \\ A \lor 0 \equiv A,~~~~~ A \lor 1 \equiv 1, \end{array}$$

Где $1$ — тождественно истиннная формула, а $0$ — тождественно ложная формула.

Теорема дается без доказательства, так как эти формулы легко проверить, используя таблицы истинности.

Теорема. Справедливы следующие равносильности $$\begin{array}{l} A \rightarrow B \equiv \overline{B} \rightarrow \overline{A}, \\ A \rightarrow B \equiv \overline{A} \lor B, \\ A \leftrightarrow B \equiv (A \rightarrow B) \land (B \rightarrow A), \\ A \land B \equiv \overline {\overline{A} \lor \overline{B}}. \end{array}$$

Докажем тождество $A \land B = \overline {\overline{A} \lor \overline{B}}$, не используя таблиц истинности. Для этого рассмотрим правую часть тождества и приведем ее к левой. $\overline {\overline{A} \lor \overline{B}} \equiv \overline{\overline{A}} \land \overline{\overline{B}}$ по закону де Моргана. По закону двойного отрицания $\overline{\overline{A}} \equiv A$ и $\overline{\overline{B}} \equiv B$. Тогда $\overline{\overline{A}} \land \overline{\overline{B}} \equiv A \land B$, что в свою очередь и есть левая часть тождества.

Теорема. Для произвольной формулы существует равносильная ей формула, которая содержит только знаки отрицания и дизъюнкции.

Действительно, в произвольной формуле $X$ могут присутствовать знаки конъюнкции, импликации и эквиваленции. Избавимся от этих знаков, заменяя подформулы, содержащие эти знаки, на равносильные им по следующим правилам:

1. Заменяем $A \leftrightarrow B$ на $A \leftrightarrow B \equiv (A \rightarrow B) \land (B \rightarrow A)$.
2. Заменяем $A \rightarrow B$ на $\overline{A} \lor B$.
3. Заменяем $A \land B$ на $\overline {\overline{A} \lor \overline{B}}$.

Но использование только двух знаков очень неудобно, так как приводит к очень громоздким формулам, именно поэтому, обычно, используют три основных знака: отрицание, конъюнкция и дизъюнкция.

Обратная и противоположная теоремы

Пусть $T$ некоторая теорема, имеющая вид $$A \rightarrow B.$$

Назовем теорему $T = A \rightarrow B$ прямой теоремой. Составим следующие высказывания:

1. $T_1 = B \rightarrow A$ — обратная теорема для теоремы $T$.
2. $T_2 = \overline{A} \rightarrow \overline{B}$ — противоположная теорема для теоремы $T$.
3. $T_3 = \overline{B} \rightarrow \overline{A}$ — обратная для противоположной теоремы к теореме $T$.

Между этими теоремами есть следующие связи:

1. $T \equiv T_3$.
2. $T_1 \equiv T_2$.