Материал предоставлен https://it.rfei.ru

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

Определение

Формулы алгебры высказываний %%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%%.
Проверка знаний. Формулы алгебры высказыванийПредикаты. Операции над предикатами