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

Определение

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

Пример

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

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

%%A%%	%%B%%	%%X = A \rightarrow B%%	%%Y = \overline{B} \rightarrow \overline{A}%%
%%0%%	%%0%%	%%1%%	%%1%%
%%0%%	%%1%%	%%1%%	%%1%%
%%1%%	%%0%%	%%0%%	%%0%%
%%1%%	%%1%%	%%1%%	%%1%%

Как видно из таблицы, истинностные значения данных формул совпадают при любых значениях %%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%%.