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

Две формулы алгебры высказываний $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})$