Логическая равносильность формул

Определение. Формулы $\Phi, Psi$ называются логически равносильными (или просто равносильными), если они принимают одинаковые логические значения при любых истинностных значениях их переменных. Это равносильно условию $|=\Phi \Leftrightarrow \Psi$

Для обозначения логически эквивалентных формул используется символическая запись $\Phi = \Psi$, или $\Phi \cong \Psi$.

$\Phi = \Psi$ однознач. $|= \Phi \Leftrightarrow \Psi$

Такие выражения называются логическими равенствами или просто равенствами формул.

Лемма 1. Справедливы следующие равенства формул:

1. $X \lor (Y \lor Z) = (X \lor Y) \lor Z, X \land (Y \land Z) = (X \land Y) \land Z$ — свойства ассоциативности дизъюнкции и конъюнкции
2. $X \lor Y = Y \lor X$, $X \land Y = Y \land X$ — свойства коммутативности дизъюнкции и конъюнкции
3. $X \lor X = X$, $X \land X = X$ — свойства идемпотентности
4. $X \land (Y \lor Z) = (X \land Y) \lor (X \land Z)$, $X \lor (Y \land Z) = (X \lor Y) \land (X \lor Z)$ — законы дистрибутивности конъюнкции относительно дизъюнкции и дизъюнкции относительно конъюнкции
5. $\lnot (X \land Y) = \lnot X \lor \lnot Y$, $\lnot(X \lor Y) = \lnot X \land \lnot Y$ — законы де Моргана
6. $(X \land Y) \lor X = X$, $(X \lor Y) \land X = X$ — законы поглощения
7. $\lnot \lnot X = X$ — закон двойного отрицания
8. $X \Rightarrow Y = \lnot X \lor Y$, $X \Rightarrow Y = \lnot(X \land \lnot Y)$ — взаимосвязь импликации с дизъюнкцией и конъюнкцией
9. $X \Leftrightarrow Y = (\lnot X \lor Y) \land (X \lor \lnot Y)$, $X \Leftrightarrow Y = (X \land Y) \lor (\lnot X \land \lnot Y)$ — взаимосвязь равносильности с дизъюнкцией и конъюнкцией