Логические операции над предикатами

Операции отрицания, конъюнкции, дизъюнкции, импликации естественным образом распространяются на предикаты.

Отрицание. Отрицанием предиката P называется предикат, который определен на том же множестве, что и P, и принимает значение «ложь», когда P истинен, и значение «истина», когда P ложен. Отрицание предиката P обозначается через P или через P. Областью истинности предиката P служит дополнение области истинности предиката P:

D_(P)=PD.

Пример.Отрицанием одноместного предиката P: x>5, определенного на множестве действительных чисел, служит предикат P: x≤5. Области истинности этих двух предикатов суть

D_P=(5;+∞) и D_(P)=(−∞;5].􀀀

Отрицание тождественно истинного предиката тождественно ложно, и обратно.

Конъюнкция.

Пусть P(x₁,x₂,…,x_n) – n-местный предикат, определенный на X₁×…×X_n, а Q(y₁,y₂,…,y_m) – m-местный предикат, определенный на Y₁×…×Y_m. Конъюнкцией предикатов P и Q, называется (n+m)-местный предикат, который определен на множестве X₁×…×X_n×Y₁×…×Y_m и истинен в том и только том случае, когда истинны оба предиката P и Q. Конъюнкция предикатов P и Q обозначается через P∧Q. Более точно:

(P∧Q)(x₁,x₂,…,x_n,y₁,y₂,…,y_n)=P(x₁,x₂,…,x_n)∧Q(y₁,y₂,…,y_n).

Операцию конъюнкции можно применять к предикатам, имеющим общие переменные (пусть их число равно k). В этом случае число переменных в предикате P∧Q равно n+m−k. Например, конъюнкцией предикатов P(x,y) и Q(y,z) является трехместный предикат P(x,y)∧Q(y,z). В частности, предикаты P и Q могут быть определены для одних и тех же переменных. В этом случае областью истинности предиката P∧Q служит пересечение областей истинности предикатов P и Q:

D_P∧Q = D_P∩D_Q.

Пример.Пусть P и Q – двухместные предикаты на множестве действительных чисел, определенные уравнениями:

P: x+y=3; Q: x–y=1.

Тогда конъюнкция P∧Q – это система двух уравнений. Ясно, что D_P∧Q = {(2;1)}. Область истинности предиката P∧Q представляет собой точку пересечения прямых, определенных уравнениями x+y=3, x–y=1, которые, в свою очередь, служат областями истинности предикатов P и Q.􀀀

Дизъюнкция.

Определение дизъюнкции аналогично определению конъюнкции. Дизъюнкцией n-местного предиката P(x₁,x₂,…,x_n) и m-местного предиката Q(y₁,y₂,…,y_m) называется (n+m)-местный предикат, определенный формулой

(P∨Q)(x₁,x₂,…,x_n,y₁,y₂,…,y_m)=P(x₁,x₂,…,x_n)∨Q(y₁,y₂,…,y_m).

Операцию дизъюнкции можно применять к предикатам, имеющим общие переменные. В частности, если предикаты P и Q определены для одних и тех же переменных, областью истинности предиката P∨Q служит объединение областей истинности предикатов P и Q: D_P∨Q = D_P∪D_Q.

Примеры.Одноместный предикат S, определенный на множестве действительных чисел неравенством x²+5x+6>0, является дизъюнкцией предикатов P: x< –3 и Q: x> –2. Имеем:

D_P = (−∞; –3); D_Q = (–2;+∞);

D_S = D_P∪D_Q = (−∞; –3) ∪ (–2;+∞).

Двухместный предикат x≤y является дизъюнкцией предикатов x<y и x=y.􀀀

Импликация.

Импликацией от n-местного предиката P(x₁,x₂,…,x_n) к m-местному предикату Q(y₁,y₂,…,y_m) называется (n+m)-местный предикат, определенный формулой

(P→Q)(x₁,x₂,…,x_n,y₁,y₂,…,y_n)=P(x₁,x₂,…,x_n)→Q(y₁,y₂,…,y_m).

Импликация P→Q тождественно истинна в том и только том случае, если Q принимает значение «истина» всякий раз, когда значение «истина» принимает P.

Для предикатов, определенных для одних и тех же переменных, тождественная истинность импликации P→Q означает, что D_P⊂D_Q.

Если импликация P→Q тождественно истинна, говорят, что предикат Q является следствием предиката P. В этом случае мы будем писать P⇒Q. Если P⇒Q и Q⇒P, предикаты P и Q называются равносильными. Для равносильных предикатов мы будем писать Р⇔Q.

Пример. На множестве действительных чисел имеем:

x>2⇒x²>4; x>2⇔(x²>4 ∧ x>0).

Свойства логических операций, сформулированные для высказываний, переносятся на операции с предикатами. Например,

(P→Q) ⇔ (Q→P); (P∨Q) ⇔ (P∧Q),

и т. п.