Равносильные высказывания основные равносильности

Обновлено: 22.12.2024

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

Пример

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

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

%%A%% %%B%% %%X = A \rightarrow B%%%%Y = \overline \rightarrow \overline%%
%%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. Закон коммутативности $$ \beginA \land B \equiv B \land A \\ A \lor B \equiv B \lor A \end $$
  3. Закон ассоциативности $$ \beginA \land (B \land C) \equiv (A \land B) \land C \\ A \lor (B \lor C) \equiv (A \lor B) \lor C \end $$
  4. Закон идемпотентности $$ \beginA \land A \equiv A \\ A \lor A \equiv A \end $$
  5. Закон дистрибутивности $$ \beginA \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 $$
  6. Законы де Моргана $$ \begin\overline \equiv \overline \lor \overline \\ \overline \equiv \overline \land \overline \end $$
  7. Закон двойного отрицания $$ \overline<\overline> \equiv A $$
  8. Закон непротиворечия $$ A \land \overline \equiv 0 $$
  9. Закон исключения третьего $$ A \lor \overline \equiv 1 $$
  10. Тождества $$ \beginA \land 1 \equiv A,

A \land 0 \equiv 0 \\ A \lor 0 \equiv A,

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

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

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

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

  1. Заменяем %%A \leftrightarrow B%% на %%A \leftrightarrow B \equiv (A \rightarrow B) \land (B \rightarrow A)%%.
  2. Заменяем %%A \rightarrow B%% на %%\overline \lor B%%.
  3. Заменяем %%A \land B%% на %%\overline <\overline\lor \overline>%%.

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

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

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

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

Читайте также: