Две формулы алгебры логики \(A\) и \(B\) называются равносильными, если они принимают одинаковые логические значения на любом наборе значений входящих в формулы элементарных высказываний.
Равносильность формул обозначают знаком \(\equiv\), а запись \(A \equiv B\) означает, что формулы \(A\) и \(B\) равносильными.
Например, равносильны формулы:
$$\bar{\bar{x}} \equiv x,$$
$$x \vee x\equiv x,$$
$$(x \wedge \bar{x}) \vee y\equiv y.$$
Формула \(A\) называется тождественно ложной, если она принимает значение 0 при всех значениях входящих в нее переменных.
Например, тождественно ложна формула \(x \wedge \bar{x}\). Ясно, что отношение равносильности рефлексивно, симметрично и транзитивно.
Между понятиями равносильности и эквивалентности существует связь: если формулы \(A\) и \(B\) равносильны, то формула \(A \leftrightarrow B\) - тавтология, и обратно, если формула \(A \leftrightarrow B\) - тавтология, то формулы \(A\) и \(B\) равносильны.
Важнейшие равносильности алгебры логики можно разбить на три группы.
1. Основные равносильности:
1. \(x \wedge x \equiv x\) - закон идемпотентности;
2. \(x \vee x \equiv x\) - закон идемпотентности;
3. \(x \wedge u \equiv x\);
4. \(x \vee u \equiv x\);
5. \(x \wedge l \equiv l\);
6. \(x \vee l \equiv x\);
7. \(x \wedge \bar{x} \equiv l\) - закон противоречия;
8. \(x \vee \bar{x} \equiv u\) - закон исключенного третьего;
9. \(\bar{\bar{x}} \equiv x\) - закон снятия двойного отрицания;
10. \(x \wedge ( y \vee x) \equiv x\) - закон поглощения;
11. \(x \vee (y \wedge x) \equiv x\) - закон поглощения.
Докажем одно из законов поглощения. Рассмотрим формулу \(A \equiv x \wedge (y \vee x)\). Если в этой формуле \(x = 1\) то, очевидно, \(y \vee x = 1\) и тогда \(x \wedge ( y \vee x) = 1\) как конъюнкция двух истинных высказываний. Пусть теперь в формуле \(A\) \(x = 0\). Но тогда по определению операции конъюнкции будет ложной конъюнкция \(x \wedge ( y \vee x)\). Итак, во всех случаях значения формулы \(A\) совпадают со значениями \(x\), а по-этому \(A \equiv x\).
2. Равносильности, выражающие одни логические операции через другие:
1. \(x \leftrightarrow y \equiv (x \rightarrow y) \wedge ( y\rightarrow x)\);
2. \(x \rightarrow y \equiv \bar{x} \vee y\);
3. \(\overline{(x \wedge y)} \equiv \bar{x} \vee \bar{y}\);
4. \(\overline{(x \vee y)} \equiv \bar{x} \wedge \bar{y}\);
5. \(x \wedge y \equiv \overline{ (\bar{x} \vee \bar{y})}\);
6. \(x \vee y \equiv \overline{ (\bar{x} \wedge \bar{y})}\).
Ясно, что равносильности 5 и 6 получаются из равносильностей 3 и 4 соответственно, если от обеих частей последних взять отрицания и воспользоватся законом снятия двойного отрицания. Таким образом, в доказательстве нуждаются первые четыре равносильности. Докажем первую из них.
Так как при одинаковых логических значениях \(x\) и \(у\) истинными являются формулы \(x \leftrightarrow y\), \(x \rightarrow y\), \(y \rightarrow x\), то истинной будет и конъюнкция \((x \rightarrow y) \wedge (y \rightarrow x)\). Следовательно, в этом случае обе части равносильности имеют одинаковые истинные значения.
Пусть теперь \(x\) и \(у\) имеют различные логические значения. Тогда будут ложными эквивалентность \(x \leftrightarrow y\) и одна из двух импликаций \(x \rightarrow y\) или \(y \rightarrow x\). По при этом будет ложной и конъюнкция \(( x \rightarrow y) \wedge (y \rightarrow x)\). Таким образом, в этом случае обе части равносильности имеют одинаковые логические значения.
Аналогично доказываются остальные три равносильности.
Из равносильностей этой группы следует, что всякую формулу алгебры логики можно заменить равносильной ей формулой, содержащей только две логические операции: конъюнкция и отрицание или дизъюнкцию и отрицание.
Однако существуют операции, с помощью которых может быть выражена любая из пяти логических операций, которыми мы пользуемся. Такой операцией является, например, операция "Штрих Шеффера. Эта операция обозначается символом \(x \mid y\) и определяется следующей таблицей истинности:
х у \(x \mid y\)
1 1
1 0
0 1
0 0
Очевидно, имеют место равносильности:
1. \(\bar{x} \equiv x\mid x\);
2. \(x \wedge y \equiv (x \mid y) \mid (x \mid y)\).
Из этих двух равносильностей следует, что всякая формула алгебры логики может быть заменена равносильной формулой, содержащей только операцию "Штрих Шеффера".
3. Равносильности, выражающие основные законы алгебры логики:
1. \(x \wedge y \equiv y \wedge x\) - коммутативность конъюнкции;
2. \(x \vee y \equiv y \vee x\) - коммутативность дизъюнкции;
3. \(x \wedge ( y \wedge z)\equiv (x \wedge y) \wedge z\) - ассоциативность конъюнкции;
4. \(x \vee ( y \vee z) \equiv ( x \vee y) \vee z\) - ассоциативность дизъюнкции;
5. \(x \wedge ( y \vee z) \equiv ( x \wedge y) \vee ( x \wedge z)\) - дистрибутивность конъюнкции относительно дизъюнкции;
6. \(x \vee ( y \wedge z) \equiv ( x \vee y) \wedge ( x \vee z)\) - дистрибутивность дизъюнкции относительно конъюнкции.
Пример 1. Доказать равносильность \(\overline{( x \rightarrow y)} \equiv x \wedge \bar{y}\).
Решение. Для доказательства равносильности подвергнем ее левую часть равносильным преобразованиям:
$$( \overline {x \rightarrow y)} \equiv ( \overline{\bar{x} \vee y ) }\equiv \bar{\bar{x}} \wedge \bar{y} \equiv x \wedge \bar{y}.$$
Пример 2. Упростить формулу \(A \equiv ( \overline{x \vee y} \rightarrow \bar{x} \vee y) \wedge y\).
Решение. Подвергнем формулу \(A\) равносильным преобразованием:
Пример 3. Доказать, что формула \(A \equiv x \rightarrow ( y \rightarrow x)\) тождественно истинна.
Решение. Подвергнем формулу \(A\) равносильным преобразованиям:
