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

Две формулы алгебры высказываний $A$ и $B$ называются равносильными или эквивалентными, если они принимают одинаковые логические значения на любом наборе значений входящих в формулы элементарных высказываний.

Равносильность формул будем обозначать знаком $\equiv$, а запись $A\equiv B$ означает, что формулы $A$ и $B$ равносильны.

Например, равносильны формулы:

$\overline { \overline { X } } \equiv X$,

$X\vee X\equiv X$,

Тождественно истинная формула

Формула $A$ называется тождественно истинной { или тавтологией } , если она принимает значение 1 при всех значениях входящих в нее переменных.

Например, тожественно истинны формулы $X\vee \overline { X } $, $X\rightarrow (Y\rightarrow X)$

Тождественно ложная формула

Формула $A$ называется тождественно ложной { или противоречием } , если она принимает значение 0 при всех значениях входящих в нее высказываний.

Например, тождественно ложна формула $X\wedge \overline { X } $

Выполнимая формула

Формула $A$ называется выполнимой, если она принимает значение 1 при всех значениях входящих в нее высказываний.

Например, выполнима формула $X\vee \overline { X } $

Ясно, что отношение равносильности рефлексивно, симметрично и транзитивно.

Группы равносильностей

Между понятиями равносильности и операцией $\leftrightarrow$ существует следующая связь: если формулы $A$ и $B$ равносильны, то формула $A\leftrightarrow B$ - тавтология, и обратно, если формула $A\leftrightarrow B$ - тавтология, то формулы $A$ и $B$ равносильны.

Важнейшие равносильности алгебры высказываний можно разбить на следующие группы.

Равносильности алгебры Буля

Закон двойного отрицания: $\overline { \overline { X } } \equiv X$

Коммутативность: $X\wedge Y\equiv Y\wedge X$; $X\vee Y\equiv Y\vee X$

Ассоциативность: $X\wedge (Y\wedge Z)\equiv (X\wedge Y)\wedge Z$; $X\vee (Y\vee Z)\equiv (X\vee Y)\vee Z$

Дистрибутивность $\wedge$ относительно $\vee$: $X\wedge (Y\vee Z)\equiv (X\wedge Y)\vee (X\wedge Z)$; $(X\vee Y)\wedge Z\equiv (X\wedge Z)\vee (Y\wedge Z)$

Дистрибутивность $\vee $ относительно $\wedge $: $X\vee (Y\wedge Z)\equiv (X\vee Y)\wedge (X\vee Z)$; $(X\wedge Y)\vee Z\equiv (X\vee Z)\wedge (Y\vee Z)$

Законы де Моргана: $\overline { X\wedge Y } \equiv \overline { X } \vee \overline { Y } $; $\overline { X\vee Y } \equiv \overline { X } \wedge \overline { Y } $

Законы поглощения: $X\wedge (Y\vee X)\equiv X$; $X\vee (Y\wedge X)\equiv X$

Законы идемпотентности: $X\wedge X\equiv X$; $X\vee X\equiv X$

Свойства констант: $X\wedge 1\equiv X$; $X\vee 1\equiv 1$; $X\wedge 0\equiv 0$; $X\vee 0\equiv X$

Закон противоречия: $X\wedge \overline { X } \equiv 0$

Закон исключения третьего: $X\vee \overline { X } \equiv 1$

Равносильности, выражающие одни логические операции через другие

$X\leftrightarrow Y\equiv (X\rightarrow Y)\wedge (Y\rightarrow X)$

$X\leftrightarrow Y\equiv (\overline { X } \vee Y)\wedge (\overline { Y } \vee X)$

$X\leftrightarrow Y\equiv (X\wedge Y)\wedge (\overline { Y } \wedge \overline { X } )$

$X\rightarrow Y\equiv \overline { X } \vee Y$

$X\wedge Y\equiv \overline { \overline { X } \vee \overline { Y } } $

$X\vee Y\equiv \overline { \overline { X } \wedge \overline { Y } } $

$X | Y\equiv \overline { X\cdot Y } $

$X \downarrow Y\equiv \overline { X\vee Y } $

$X \rightarrow Y\equiv \overline { X } \vee Y$

$X \bigoplus Y\equiv (X \cdot \bar { Y } )\vee (\bar { X } \cdot Y)$

$X \sim Y\equiv \overline { X \bigoplus Y } \equiv (XY)\vee (\bar { X } \bar { Y } )$