Две формулы логики предикатов \(A\) и \(B\) называются равносильными на области \(M\), если они принимают одинаковые логические значения при всех значениях входящих в них переменных, отнесенных к области \(M\).
Две формулы логики предикатов \(A\) и \(B\) называются равносильными, если они равносильны на всякой области.
Здесь, как в алгебре высказываний, для равносильных формул принято обозначение \(A \equiv B\).
Ясно, что все равносильности алгебры высказываний будут верны, если в них вместо переменных высказываний подставить формулы логики предикатов. Но, кроме того, имеют место равносильности самой логики предикатов. Рассмотрим основные из этих равносильностей.
Пусть \(A\) и \(B\) – переменные предикаты, а \(C\) – переменное высказывание. Тогда:
1. \( \overline{ \forall x A (x) } \) \(\equiv\) \(\exists x\) \(\overline {A(x)} \),
2. \(\overline{ \exists x A (x) }\) \(\equiv\) \(\forall x \overline{ A (x) } \),
3. \(\forall x A (x) \) \(\equiv\) \(\overline{ \exists x \overline{ A (x) }} \),
4. \(\exists x A (x) \) \(\equiv\) \(\overline{ \forall x \overline{ A (x) }} \),
5. \(\forall x A(x) \wedge \forall x B (x) \equiv \forall x \)\(\begin{bmatrix} A (x) \wedge B (x) \end{bmatrix}\),
6. \( C \wedge \forall x B (x) \equiv \forall x \)\(\begin{bmatrix} C \wedge B (x) \end{bmatrix}\),
7. \( C \vee \forall x B (x) \equiv \forall x \)\(\begin{bmatrix} C \vee B (x) \end{bmatrix}\),
8. \( C \rightarrow \forall x B (x) \equiv \forall x \)\(\begin{bmatrix} C \rightarrow B (x) \end{bmatrix}\),
9. \( \forall x \)\(\begin{bmatrix} B (x) \rightarrow C \end{bmatrix} \equiv \exists x B (x) \rightarrow C \),
10. \( \exists x \begin{bmatrix} A (x) \vee B (x) \end{bmatrix} \equiv \exists x A (x) \vee \exists x B (x) \),
11. \( \exists x \begin{bmatrix} C \vee B (x) \end{bmatrix} \equiv C \vee \exists x B (x) \),
12. \( \exists x \begin{bmatrix} C \wedge B (x) \end{bmatrix} \equiv C \wedge \exists x B (x) \),
13. \( \exists x A (x) \wedge \exists y B (y) \equiv \exists x \exists y \begin{bmatrix} A (x) \wedge B (y) \end{bmatrix} \),
14. \( \exists x \begin{bmatrix} C \rightarrow B (x) \end{bmatrix} \equiv C \rightarrow \exists x B (x) \),
15. \( \exists x \begin{bmatrix} B (x) \rightarrow C \end{bmatrix} \equiv \forall x B (x) \rightarrow C \).
Равносильность 1 означает тот простой факт, что, если не для всех \(x\) истинно \(A (x) \), то существует \(x\), при котором будет истиной \(\bar{A} (x)\).
Равносильность 2 означает тот простой факт, что, если не существует \(x\), при котором истинно \(A (x) \), то для всех \(x\) будет истиной \(\bar{A} (x)\).
Равносильности 3 и 4 получаются из равносильностей 1 и 2, соответственно, если от обеих их частей взять отрицания и воспользоваться законом двойного отрицания.
Докажем равносильность 5. Если предикаты \(A (x)\) и \(B (x)\) одновременно тождественно истинны, то будет тождественно истинными и предикаты \(A (x) \wedge B (x)\), а по-этому будут истинными высказывания:
То есть в этом случае обе части равносильности 5 принимают значение "истинна".
Пусть теперь хотя бы один из предикатов, например, \(A (x)\), будет не тождественно истинным. Тогда не тождественно истинным будет и предикат \(A (x) \wedge B (x)\), а по-этому ложными будут высказывания:
Докажем равносильность 8. Пусть переменное высказывание \(C\) принимает значение "ложь". Тогда тождественно истинным будет предикат \(C \rightarrow B (x)\) и, очевидно, истинными будут высказывания \( C \rightarrow \forall x B (x) \) и \( \forall x \begin{bmatrix} C \rightarrow B (x) \end{bmatrix} \), то есть в этом случае обе части равносильности 8 принимают одинаковые (истинные) значения.
Пусть теперь переменное высказывание \(C\) принимает значение "истина". Если при этом переменный предикат является тождественно истинным, то будет тождественно истинным и предикат \(C \rightarrow B (x)\), и значит, истинными будут высказывания \(\forall x B (x) \), \( C \rightarrow \forall x B (x) \), \(\forall x \begin{bmatrix} C \rightarrow B (x) \end{bmatrix} \), то есть и в этом случае обе части равносильности 8 принимают одинаковые (истинные) значения.
Если же предикат \(B (x)\) не является тождественно истинными, то не будет тождественно истинными и предикат \(C \rightarrow B (x)\), а по-этому ложными будут высказывания \(\forall x B (x) \), \(C \rightarrow \forall x B (x)\), \( \forall x \begin{bmatrix} C \rightarrow B (x) \end{bmatrix} \).
Следовательно, и здесь обе части равносильности 8 принимают одинаковые (ложные) значения. Этим исчерпывается доказательство равносильности 8.
Аналогично доказываются остальные из перечисленных равносильностей.
В заключение отметим, сто формула \( \forall x \begin{bmatrix} A (x) \vee B (x) \end{bmatrix} \) не равносильна формуле \( \forall x A (x) \vee \forall x B (x) \), а формула \( \exists x \begin{bmatrix} A (x) \wedge B (x) \end{bmatrix} \) не равносильна формуле \( \exists x A (x) \wedge \exists x B (x) \).
Пример 1. Доказать равносильность:
Решение. Для доказательства равносильности достаточно рассмотреть два случая:
1. Пусть предикаты \(A (x)\) и \(B (x)\) тождественно ложны. Тоrда будет тождественно ложным и предикат \( A (x) \vee B (x) \). При этом будут ложными высказывания \( \exists x ( A (x) \vee B (x) \)) и \(\exists x A (x) \vee \exists x B (x) \).
2. Пусть теперь хотя бы один из предикатов (например, \(A (x)\) ) не тождественно ложный. Тогда будет не тождественно ложным и предmcат \( A (x) \vee B (x) \). При этом будут истинными высказывания \( \exists x A (x) \) и \( \exists x ( A (x) \vee B (x)) \), а, значит, будут истинными и исходные формулы.
Следовательно, \( \exists x ( A (x) \vee B (x)) \equiv \exists x A (x) \vee \exists x B (x) \).
Пример 2. Доказать равносильность:
Решение. Рассмотрим два случая:
1. Пусть высказывание \(c \) ложно. Toгдa для любоrо предиката \(A (x)\) будет тождественно ложным высказывание \( c \wedge \forall x A (x) \) и предикат \( c \wedge A (x) \), и, следовательно, высказывание \( \forall x (c \wedge A (x)) \). Значит, в этом случае обе исходные формулы тождественно ложны.
2. Пусть теперь высказывание \( c\) истинно. Тогда, очевидно, значения исходных формул будут целиком зависеть от значений предиката \(A (x)\). Если \(A (x)\) - тождественно истинный предикат, то будет тождественно истинным и предикат \( c \wedge A (x) \), и, следовательно, будут тождественно истинными высказывания \( \forall x A (x) \), \( c \wedge \forall x A (x) \), \( \forall x (c \wedge A (x)) \),то есть тождественно истинны исходные формулы. Если же предикат \(A (x)\) не тождественно истинный, тогда будет не тождественно истинным предикат \( c \wedge A (x) \) , а высказывания \( \forall x A (x) \), \( c \wedge \forall x A (x) \), \( \forall x (c \wedge A (x)) \) будут ложными, то есть ложные значения принимают обе исходные формулы, что в итогe доказывает их равносильность.
