Лекция 17. Отношения между предикатами

[Admin]

Лекция 17. Отношения между предикатами

Как и формулы алгебры высказываний, предикаты могут быть равносильными, а могут следовать друг из друга. Несмотря на интуитивную ясность этих понятий, определим их строго. Начнём с равносильности.

***

Пусть \(  \large A  \) и \(  \large B \) - предикаты, определённые на множествах \(  \large M_1, M_2, \ldots, M_n  \), где \(  \large n \ge 1  \).

Определение 17.1. Предикаты \(  \large A \) и \(  \large B  \) называются равносильными, если для любых предметных постоянных \(  \large a_i \in M_i, \ i=1,2, \ldots, n  \), высказывания \(  \large A(a_1,a_2, \ldots, a_n)  \) и \(  \large B(a_1,a_2, \ldots, a_n)  \) имеют одинаковые истинностные значения.

Замечание 17.1. Учитывая определения множества истинности и равенства множеств, предикаты \(  \large A \) и \(  \large B  \) являются равносильными, если их множества истинности равны:

\(  \large \mathcal{A} = \mathcal{B}  \).

Замечание 17.2. Определение равносильности предикатов справедливо лишь для \(  \large n \ge 1  \). Если предикат является нульместным, то это либо высказывание, полученное подстановкой предметных постоянных вместо всех предметных переменных, либо высказывание, полученное связыванием кванторами всех предметных переменных, либо высказывание, полученное подстановкой предметных постоянных вместо части предметных переменных, при этом оставшиеся свободными переменные связаны кванторами. В этом случае определение 17.1 не работает, так как подстановка предметных постоянных в высказывание не имеет смысла. Нульместные предикаты (высказывания) будем считать равносильными, если они имеют одинаковые значения истинности.

Замечание 17.3. Очевидно, что любые два тождественно ложных предиката равносильны, поскольку их множества истинности пусты. Любые два тождественно истинных предиката равносильны, если они заданы на одном и том же наборе множеств \(  \large M_1,M_2, \ldots, M_n  \), поскольку множеством истинности обоих предикатов является декартово произведение этих множеств.

Замечание 17.4. Предикаты \(  \large A  \) и \(  \large B  \) не равносильны, если найдутся такие предметные постоянные \(  \large a_i \in M_i, \ i=1,2, \ldots, n  \), что значения истинности высказываний \(  \large A(a_1,a_2, \ldots, a_n)  \) и \(  \large B(a_1,a_2, \ldots, a_n)  \) различны. Высказывания (нульместные предикаты) не равносильны, если из истинностные значения не совпадают.

Замечание 17.5. Предикаты \(  \large A  \) и \(  \large B  \) не являются равносильными, если их множества истинности не равны:

\(  \large \mathcal{A} \not = \mathcal{B}  \).

Замечание 17.6. Если предикаты \(  \large A  \) и \(  \large B   \) равносильны, то пишут:

\(  \large A \Leftrightarrow B  \).

Если они не равносильны, используется следующее обозначение:

\(  \large A  \not \Leftrightarrow B  \).

Замечание 17.7. Два предиката могут быть равносильны на одном множестве и не равносильны на другом. Чтобы подчеркнуть тот факт, что предикаты \(  \large A  \) и \(  \large B  \) равносильны на некотором множестве \(  \large M  \), будем использовать такое обозначение:

\(  \large A \stackrel{M }{\Leftrightarrow} B  \).

Пример 17.1. Рассмотрим предикаты \(  \large 2x^3+5x^2+4x+1=0  \) и \(  \large 3x^3-x^2+7x-1=0  \), определённые на множестве целых чисел. Первый предикат обозначим через \(  \large A(x)  \), а второй - через \(  \large B(x)  \). Множеством истинности каждого из них является множество \(  \large M= \{ -1 \}  \). Значит, предикаты равносильны на множестве целых чисел:

\(  \large A(x) \stackrel{\mathbb{Z} }{\Leftrightarrow} B(x)  \).

Если рассматривать те же предикаты над множеством рациональных чисел, то они не равносильны:

\(  \large A(x)  \not \stackrel{\mathbb{Q}}{\Leftrightarrow} B(x)  \).

Они не равносильны, поскольку

\(  \large \mathcal{A}= \{ -\frac{1}{2}, -1 \}  \), \(  \large \mathcal{B}= \{ \frac{1}{3}, -1 \}  \).

[Admin]

Равносильность предикатов, их тождественная истинность и эквиваленция тесно связаны, как и в случае формулами логики высказываний. Эта связь показана в следующих теоремах.

***

Теорема 17.1. Предикаты \(  \large A  \) и \(  \large B  \) равносильны тогда и только тогда, когда предикат \(  \large A \leftrightarrow B  \) тождественно истинен.

Доказательство. Пусть \(  \large A  \) и \(  \large B \) - предикаты, определённые на множествах \(  \large M_1,M_2, \ldots, M_n  \).

1) Рассмотрим сначала случай, когда предикаты содержат не меньше одной предметной переменой. Если предикаты \(  \large A  \) и \(  \large B  \) равносильны, то, согласно определению равносильности предикатов, для любых \(  \large a_i \in M_i, \ i =1,2, \ldots, n  \), высказывания \(  \large A(a_1,a_2, \ldots, a_n)  \) и \(  \large B(a_1,a_2, \ldots, a_n)  \) имеют одинаковые истинностные значения. Следовательно, в силу определения эквиваленции, высказывание \(  \large A(a_1,a_2, \ldots, a_n) \leftrightarrow B(a_1,a_2, \ldots, a_n)  \) истинно, какими бы ни были \(  \large a_i \in M_i, \ i =1,2, \ldots, n  \). А это и означает, по определению тождественной истинности предиката, что предикат \(  \large A \leftrightarrow B  \) тождественно истинен.

Теперь рассмотрим случай, когда предикаты не содержат предметных переменных (являются нульместными предикатами, высказываниями). Если два нульместных предиката (высказывания) равносильны, то они одновременно истинны или ложны. Значит, высказывание \(  \large A \leftrightarrow B  \) истинно. Следовательно, нульместный предикат \(  \large A \leftrightarrow B  \) тождественно истинен.

2) Пусть предикаты имеют хотя бы одну предметную переменную. Если предикат \(  \large A \leftrightarrow B  \) тождественно истинен, то, согласно определению тождественной истинности предиката, для любых \(  \large a_i \in M_i, \ i =1,2, \ldots, n  \), высказывание \(  \large A(a_1,a_2, \ldots, a_n) \leftrightarrow B(a_1,a_2, \ldots, a_n)  \) истинно. Значит, по определению эквиваленции, высказывания \(  \large A(a_1,a_2, \ldots, a_n)  \) и \(  \large B(a_1,a_2, \ldots, a_n)  \) истинны и ложны одновременно, какими бы ни были  \(  \large a_i \in M_i, \ i =1,2, \ldots, n  \). Следовательно, по определению равносильности, \(  \large A \Leftrightarrow B  \).

Пусть теперь предикаты являются нульместными. Если предикат (высказывание) \(  \large A \leftrightarrow B  \) является тождественно истинным (высказывание истинно), то истинностные значения высказываний \(  \large A  \) и \(  \large B  \) совпадают. Следовательно, они равносильны. Теорема доказана.

Теорема 17.2. Предикаты \(  \large A  \) и \(  \large B  \) не являются равносильными тогда и только тогда, когда предикат \(  \large A \leftrightarrow B  \) опровержим.

Доказательство этой теоремы сводится к формализации предыдущей теоремы и применению к ней закона противоположности:

\(  \large P \leftrightarrow Q \simeq \overline{P} \leftrightarrow \overline{Q}  \).

Теорема доказана.

[Admin]

Определим следование предикатов, докажем связь этого понятия с импликацией и тождественной истинностью предикатов, а также с равносильностью предикатов.

***

Пусть \(  \large A_1, A_2, \ldots, A_k, B  \) - предикаты, которые определены на множествах \(  \large M_1, M_2 , \ldots, M_n  \), причём \(  \large n \ge 1  \).

Определение 17.2. Предикат \(  \large B  \) называется следствием предикатов \(  \large A_1,A_2, \ldots, A_k \), если для любых предметных постоянных \(  \large a_i \in M_i, \ i=1,2, \ldots, n  \), истинность высказываний \(  \large A_1(a_1,a_2, \ldots, a_n)   \), \(  \large A_2(a_1,a_2, \ldots, a_n)   \), \(  \large \ldots, A_k(a_1,a_2, \ldots, a_n)  \) влечёт истинность высказывания \(  \large B(a_1,a_2, \ldots, a_n)  \).

Замечание 17.8. Учитывая определения множества истинности, включения и пересечения множеств, предикат \(  \large B  \) является следствием предикатов \(  \large A_1,A_2, \ldots, A_k \), если пересечение множеств истинности предикатов \(  \large A_1, A_2, \ldots, A_k  \) является подмножеством множества истинности предиката \(  \large B  \):

\(  \large \mathcal{A_1} \cap \mathcal{A_2} \cap \ldots \cap \mathcal{A_k} \subseteq \mathcal{B}  \).

Предикат \(  \large B  \) является следствием предиката \(  \large A \), если множество истинности предиката \(  \large A  \) является подмножеством множества истинности предиката \(  \large B  \):

\(  \large \mathcal{A} \subseteq \mathcal{B}  \).

Замечание 17.9. Как и в случае с равносильностью, определение следования имеет смысл лишь при \(  \large n \ge 1  \). Если \(  \large A_1,A_2, \ldots, A_k,B  \) - нульместные предикаты, то следование будем понимать так: истинность высказываний \(  \large A_1,A_2, \ldots, A_k  \) влечёт истинность высказывания \(  \large B  \).

Замечание 17.10 Из тождественно ложного предиката следует любой предикат, поскольку пустое множество (множество истинности тождественно ложного предиката) является подмножеством любого множества. Тождественно истинный предикат следует из любого предиката, так как всякое множество есть подмножество универсального множества (множества истинности тождественно истинного предиката).

Замечание 17.11. Предикат \(  \large B  \) не является следствием предикатов \(  \large A_1,A_2, \ldots, A_k \), если найдутся такие предметные постоянные \(  \large a_i \in M_i, \ i=1,2, \ldots, n  \), что высказывания \(  \large A_1(a_1,a_2, \ldots, a_n)   \), \(  \large A_2(a_1,a_2, \ldots, a_n)   \), \(  \large \ldots, A_k(a_1,a_2, \ldots, a_n)  \) истинны, а высказывание \(  \large B(a_1,a_2, \ldots, a_n)  \) ложно. Нульместный предикат (высказывание) \(  \large B  \) не является следствием нульместных предикатов (высказываний) \(  \large A_1,A_2, \ldots, A_k \), если высказывания \(  \large A_1,A_2, \ldots, A_k \) истинны, а высказывание \(  \large B \) ложно.

Замечание 17.12. Предикат \(  \large B  \) не является следствием предикатов \(  \large A_1,A_2, \ldots, A_k  \), если пересечение множеств истинности предикатов \(  \large A_1, A_2, \ldots, A_k  \) не является подмножеством множества истинности предиката \(  \large B  \):

\(  \large \mathcal{A_1} \cap \mathcal{A_2} \cap \ldots \cap \mathcal{A_k} \not \subseteq \mathcal{B}  \).

Предикат \(  \large B  \) не является следствием предиката \(  \large A \), если множество истинности предиката \(  \large A  \) не является подмножеством множества истинности предиката \(  \large B  \):

\(  \large \mathcal{A} \not \subseteq \mathcal{B}  \).

Замечание 17.13. Если предикат \(  \large B  \) является следствием предикатов \(  \large A_1,A_2, \ldots, A_k  \), то используется такое обозначение:

\(  \large A_1,A_2, \ldots, A_k \Rightarrow B  \).

Толстая стрелка вновь используется  для того чтобы не путать следование предикатов с пропозициональной операцией - импликацией. Если предикат \(  \large B  \) не следует из предикатов \(  \large A_1,A_2, \ldots, A_k  \), то пишут

\(  \large A_1,A_2, \ldots, A_k \not \Rightarrow B  \).

Замечание 17.14. Чтобы показать, что предикат \(  \large B  \) следует из предикатов \(  \large A_1,A_2, \ldots, A_k  \) на множестве \(  \large M  \) используется обозначение

\(  \large A_1,A_2, \ldots, A_k \stackrel{M}{\Rightarrow} B  \).

Пример 17.2. Пусть \(  \large M= \{0,1,2, \ldots, 10 \}  \). Определим на этом множестве два предиката: \(  \large A(x)  \) означает "\(  \large x  \) делится на \(  \large 10  \)", \(  \large B(x)  \) означает "\(  \large x  \) делится на \(  \large 5  \)". Ясно, что множеством истинности первого предиката является \(  \large \mathcal{A}=\{ 0,10\}  \), а множеством истинности второго предиката - \(  \large \mathcal{B}=\{ 0,5,10\}  \). Предикат \(  \large B  \) следует из предиката \(  \large A  \), так как \(  \large \mathcal{A} \subseteq \mathcal{B}  \).

[Admin]

Теорема 17.3. Предикат \(  \large B  \) является следствием предикатов \(  \large A_1,A_2, \ldots, A_k  \) тогда и только тогда, когда предикат \(  \large (A_1 \wedge A_2 \wedge \ldots \wedge A_k) \to B  \) тождественно истинен.

Доказательство. Пусть \(  \large A_1, A_2, \ldots, A_k,B  \) - предикаты, определённые на множествах \(  \large M_1,M_2, \ldots, M_n  \).

1) Пусть речь идёт о предикатах, имеющих хотя бы одну предметную переменную. Если предикат \(  \large B  \) является следствием предикатов \(  \large A_1,A_2, \ldots, A_k  \), то, согласно определению следования предикатов, для любых \(  \large a_i \in M_i, \ i=1,2, \ldots, n  \), истинность высказываний \(  \large A_1(a_1,a_2, \ldots, a_n) \), \(  \large A_2(a_1,a_2, \ldots, a_n)  \), \(  \large \ldots, A_k(a_1,a_2, \ldots, a_n)  \) влечёт истинность высказывания \(  \large B(a_1, \ldots ,a_n)  \). Тогда, учитывая определения конъюнкции и импликации, высказывание \(  \large (A_1(a_1, \ldots, a_n) \wedge \ldots \wedge A_k(a_1, \ldots, a_n)) \to B(a_1, \ldots ,a_n)  \) истинно, какими бы ни были \(  \large a_i \in M_i, \ i=1,2, \ldots, n  \). Но это и означает, согласно определению тождественной истинности предиката, что предикат \(  \large (A_1 \wedge A_2 \wedge \ldots \wedge A_k) \to B  \) тождественно истинен.

Если предикаты являются нульместными, то, следование высказывания \(  \large B  \) из высказываний \(  \large A_1, A_2, \ldots, A_k  \) означает, что из истинности высказываний \(  \large A_1 ,A_2, \ldots, A_k \) следует истинность высказывания. Значит, высказывание \(  \large (A_1 \wedge A_2 \wedge \ldots \wedge A_k) \to B  \) истинно (нульместный предикат тождественно истинен).

2) Рассмотрим предикаты, местность которых не меньше единицы. Если предикат \(  \large (A_1 \wedge \ldots \wedge A_k) \to B  \) тождественно истинен, то для любых \(  \large a_i \in M_i, \ i=1,2, \ldots, n  \), высказывание \(  \large (A_1(a_1, \ldots, a_n) \wedge \ldots A_k (a_1, \ldots, a_n)) \to B(a_1, \ldots, a_n)  \) истинно. По определению импликации и конъюнкции, это означает, что истинность высказываний \(  \large A_1(a_1,a_2, \ldots, a_n) \), \(  \large A_2(a_1,a_2, \ldots, a_n)  \), \(  \large \ldots, A_k(a_1,a_2, \ldots, a_n)  \) влечёт истинность высказывания \(  \large B(a_1, \ldots ,a_n)  \). А это и означает, в силу определения, что предикат \(  \large B  \) следует из предикатов \(  \large A_1, A_2, \ldots A_k  \).

Пусть теперь речь идёт о нульместных предикатах (высказываниях). Если высказывание \(  \large (A_1 \wedge A_2 \wedge \ldots \wedge A_k) \to B  \) истинно, то истинность высказываний \(  \large A_1,A_2, \ldots, A_k  \) влечёт истинность высказывания \(  \large B  \). Это означает, что высказывание \(  \large B  \) следует из высказываний \(  \large A_1,A_2, \ldots, A_k  \). Теорема доказана.

Теорема 17.4. Предикат \(  \large B  \) не является следствием предикатов \(  \large A_1,A_2, \ldots, A_k  \) тогда и только тогда, когда предикат \(  \large (A_1 \wedge A_2 \wedge \ldots \wedge A_k) \to B  \) опровержим.

Доказательство. Чтобы доказать данную теорему, достаточно формализовать предыдущую теорему и применить к ней закон противоположности. Теорема доказана.

Теорема 17.5. Предикаты \(  \large A  \) и \(  \large B  \) равносильны тогда и только тогда, когда \(  \large A   \) является следствием \(  \large B  \) и \(  \large B  \) является следствием \(  \large A  \).

Доказательство. Если предикаты \(  \large A  \) и \(  \large B  \) равносильны, то, согласно определению равносильности предикатов, их множества истинности равны: \(  \large \mathcal{A} = \mathcal{B}  \). Значит, по определению равенства множеств, \(  \large \mathcal{A} \subseteq \mathcal{B}  \) и \(  \large \mathcal{B} \subseteq \mathcal{A}  \), а это и означает, что предикат \(  \large A  \) следует из предиката \(  \large B  \), и наоборот (в силу определения следования предикатов). Докажем в обратную сторону. Пусть \(  \large A \Rightarrow B  \) и \(  \large B \Rightarrow A  \). Значит, \(  \large \mathcal{A} \subseteq \mathcal{B}  \) и \(  \large \mathcal{B} \subseteq \mathcal{A}  \). Следовательно, \(  \large \mathcal{A} = \mathcal{B}  \). Тогда предикаты равносильны. Теорема доказана.

[Admin]

Введя понятие равносильности предикатов (в том числе и нульместных, высказываний), мы можем доказать, что универсальное высказывание для предиката \(  \large A(x)  \), определённого на множестве \(  \large M=\{a_1,a_2, \ldots, a_n \}  \), можно выразить через конъюнкцию единичных высказываний, а экзистенциальное высказывание для того же предиката на том же множестве можно выразить через дизъюнкцию единичных высказываний. Иногда говорят о том, что квантор общности (существования) выражается через конъюнкцию (дизъюнкцию) на конечном множестве.

***

Теорема 17.6. Высказывание \(  \large \forall x A(x)  \) равносильно на множестве \(  \large M= \{a_1,a_2, \ldots , a_n\}  \) высказыванию \(  \large \bigwedge\limits_{k=1}^n A(a_k)  \).

Доказательство. Нульместные предикаты равносильны, согласно определению, если и только если они имеют одинаковые истинностные значения. Ниже будут использованы определения квантора общности, тождественно истинного предиката, опровержимого предиката и конъюнкции. Пусть высказывание \(  \large \forall x A(x)  \) истинно. Оно истинно тогда и только тогда, когда предикат \(  \large A(x)  \) тождественно истинен. Поскольку данный предикат задан на множестве \(  \large M  \), состоящем из \(  \large n  \) элементов, тождественная истинность этого предиката эквивалентна истинности всех высказываний \(  \large A(a_1) , A(a_2), \ldots, A(a_n) \). Тогда истинна и конъюнкция этих высказываний. Пусть теперь высказывание \(  \large \forall x A(x)  \) ложно. Значит, предикат \(  \large A(x)  \) опровержим (хотя бы одно из высказываний \(  \large A(a_1) , A(a_2), \ldots, A(a_n) \) ложно). Следовательно, ложна и конъюнкция этих высказываний. Итак,

\(  \large \forall x A(x) \stackrel{M}{\Leftrightarrow} \bigwedge\limits_{k=1}^n A(a_k)  \),

что и требовалось доказать. Теорема доказана.

Теорема 17.7. Высказывание \(  \large \exists x A(x)  \) равносильно на множестве \(  \large M= \{a_1,a_2, \ldots , a_n\}  \) высказыванию \(  \large \bigvee\limits_{k=1}^n A(a_k)  \).

Доказательство. Будем использовать определения равносильности нульместных предикатов (высказываний), квантора существования, выполнимого предиката, тождественно ложного предиката и дизъюнкции. Высказывание \(  \large \exists x A(x)  \) истинно тогда и только тогда, когда предикат \(  \large A(x)  \) выполним. Так как данный предикат задан на множестве \(  \large M  \), которое состоит из \(  \large n  \) элементов, выполнимость данного предиката эквивалентна истинности хотя бы одного из высказываний \(  \large A(a_1) , A(a_2), \ldots, A(a_n) \). Значит, истинна и дизъюнкция этих высказываний. Пусть теперь высказывание \(  \large \exists x A(x)  \) ложно. Следовательно, предикат \(  \large A(x)  \) тождественно ложен (все высказывания \(  \large A(a_1) , A(a_2), \ldots, A(a_n) \) ложны). Тогда ложна и дизъюнкция этих высказываний. Итак,

\(  \large \exists x A(x) \stackrel{M}{\Leftrightarrow} \bigvee\limits_{k=1}^n A(a_k)  \),

что и требовалось доказать. Теорема доказана.

Замечание 17.15. Пусть \(  \large M= \{a_1,a_2, \ldots ,a_m \}  \). Аналогично можно доказать, что

\(  \large \forall x_1 A(x_1,x_2, \ldots, x_n) \stackrel{M}{\Leftrightarrow} \bigwedge\limits_{k=1}^m A(a_k,x_2, \ldots x_n)  \),

\(  \large \exists x_1 A(x_1,x_2, \ldots, x_n)  \stackrel{M}{\Leftrightarrow}  \bigvee\limits_{k=1}^m A(a_k,x_2, \ldots x_n)  \).

Замечание 17.16. В случае задания предикатов на бесконечных множествах кванторы не выражаются через пропозициональные операции.

[Admin]

Пример 17.3. Пусть предикат \(  \large A(x,y)  \) задан на множестве \(  \large M=\{a,b \}  \). Избавимся от кванторов в высказывании \(  \large \exists x \forall y A(x,y)  \).

Сначала выразим квантор существования через дизъюнкцию:

\(  \large  \exists x \forall y A(x,y) \stackrel{M}{\Leftrightarrow} \forall y A(a,y) \vee \forall y A(b,y)  \).

Теперь выразим квантор общности через конъюнкцию:

\(  \large \forall y A(a,y) \vee \forall y A(b,y) \stackrel{M}{\Leftrightarrow} (A(a,a) \wedge A(a,b)) \vee (A(b,a) \wedge A(b,b))  \).

Итак, высказывание, полученное связыванием кванторами обоих предметных переменных двуместного предиката, мы выразили в виде дизъюнкции конъюнкций.

Пример 17.4. Докажем, что нульместные предикаты (высказывания) \(  \large (\forall x) (\exists y)(A(x,y)) \) и \(  \large (\exists x) (\forall y) (A(x,y)) \) равносильны, если предикат \(  \large A(x,y)  \) определён на множестве \(  \large M  \), состоящем из одного элемента.

Пусть \(  \large  M = \{a \} \). Тогда получим:

1) \(  \large (\forall x)(\exists y) (A(x,y)) \stackrel{M}{\Leftrightarrow} (\exists y) (A(a,y)) \stackrel{M}{\Leftrightarrow} A(a,a)  \),

2) \(  \large (\exists x)(\forall y) (A(x,y)) \stackrel{M}{\Leftrightarrow} (\forall y) (A(a,y)) \stackrel{M}{\Leftrightarrow} A(a,a)  \).

Итак, получили одно и то же высказывание. Следовательно, данные высказывания равносильны на любом одноэлементном множестве.

Пример 17.5. Найдём предикат, равносильный предикату \(  \large \forall x A(x,y) \vee \exists z \forall x B(x,z)  \), но не содержащий кванторов, если предикаты \(  \large A  \) и \(  \large B  \) определены на множестве \(  \large M=\{a,b,c \}  \).

Сначала избавимся от кванторов общности в обоих членах дизъюнкции:

\(  \large \forall x A(x,y) \stackrel{M}{\Leftrightarrow} A(a,y) \wedge A(b,y) \wedge A(c,y)  \),

\(  \large \forall x B(x,z) \stackrel{M}{\Leftrightarrow} B(a,z) \wedge B(b,z) \wedge B(c,z)   \).

Теперь избавимся от квантора существования во втором члене дизъюнкции:

\(  \large \exists z \forall x B(x,z) \stackrel{M}{\Leftrightarrow} (B(a,a) \wedge B(b,a) \wedge B(c,a)) \vee (B(a,b) \wedge B(b,b) \wedge B(c,b)) \vee (B(a,c) \wedge B(b,c) \wedge B(c,c))  \).

Значит, одноместный предикат

\(  \large \forall x A(x,y) \vee \exists z \forall x B(x,z)    \)

равносилен на множестве \(  \large M  \) одноместному предикату

\(  \large (A(a,y) \wedge A(b,y) \wedge A(c,y)) \vee (B(a,a) \wedge B(b,a) \wedge B(c,a)) \vee   \)

\(  \large \vee (B(a,b) \wedge B(b,b) \wedge B(c,b)) \vee (B(a,c) \wedge B(b,c) \wedge B(c,c))  \).

[Admin]

Докажем две теоремы, которые позволяют упростить конъюнкцию (дизъюнкцию) предикатов, если один из них является тождественно истинным (тождественно ложным).

***

Теорема 17.8. Конъюнкция предиката \(  \large A(x_1,x_2, \ldots, x_n)  \) и тождественно истинного предиката равносильна предикату \(  \large A(x_1,x_2, \ldots, x_n)  \).

Доказательство.

Теорема доказана.

Теорема 17.9. Дизъюнкция предиката \(  \large A(x_1,x_2, \ldots, x_n)  \) и тождественно ложного предиката равносильна предикату \(  \large A(x_1,x_2, \ldots, x_n)  \).

Доказательство.

Теорема доказана.