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

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

Отрицание. Отрицанием предиката 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),

и т. п.

Кванторы

Квантор существования.

Всякому одноместному предикату P(x) на множестве X поставим в соответствие высказывание, обозначаемое через ∃xP(x) (читается «существует x такой, что P(x)»). Высказывание ∃xP(x) истинно, если область истинности предиката P не пуста, и ложно в противном случае. Таким образом, ∃xP(x) истинно, если в множестве X найдется хотя бы один элемент a, для которого P(a) истинно. Знак ∃ называется квантором существования. Про переменную x в высказывании ∃xP(x) говорят, что она связана квантором существования.

Примеры. Высказывания

∃x(x²+1=0), ∃x(2^x <0)

ложны; высказывания

∃x(x²+5x+6=0), ∃x(2^x >1000) истинны (мы считаем уравнения и неравенства предикатами на множестве действительных чисел).􀀀

Кванторы существования применяются не только к одноместным предикатам. Например, пусть P(x,y) – двухместный предикат на множестве X. Зафиксируем значение y=b. Тогда, считая P(x,b) одноместным предикатом от переменной x, можно составить высказывание ∃xP(x,b). Сопоставляя каждому b значение истинности этого высказывания, мы получаем одноместный предикат, зависящий от переменной y. Этот предикат обозначается через ∃xP(x,y). В этом предикате переменная x считается связанной, а переменная y – свободной. Аналогично определяется ∃yP(x,y). Подобные определения можно распространить и на предикаты большего числа переменных.

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

x²+px+q=0.

Предикат

∃x (x²+px+q=0)

двухместный, он зависит от переменных p и q. Значения p и q, при которых уравнение имеет решения, превращают его в истинное высказывание. Этот предикат равносилен предикату p²−4q≥0, так что можно записать

∃x (x²+px+q=0) ⇔ p²−4q≥0.􀀀 Квантор общности.

Всякому одноместному предикату P(x) на множестве X поставим в соответствие высказывание, обозначаемое через ∀xP(x) (читается «для любого x P(x)»). Высказывание ∀xP(x) истинно, если область истинности предиката P совпадает с множеством X, и ложно в противном случае. Таким образом, ∀xP(x) истинно, если P(a) истинно для всех элементов a из множества X. Знак ∀ называется квантором общности. Про переменную x в высказывании ∀xP(x) говорят, что она связана квантором общности.

Примеры. Относительно действительных чисел высказывания

∀x (x²+1>0), ∀x (x² −1=(x−1)(x+1))

истинны; высказывания

∀x (x²+5x+6=0), ∀x (2^x >1000)

ложны.􀀀

Так же, как и кванторы существования, кванторы общности применяются не только к одноместным предикатам. Например, пусть P(x,y) – двухместный предикат на множестве X. Тогда ∀xP(x,y) – это одноместный предикат. Он принимает значение «истина» для y=b, если истинно высказывание ∀xP(x,b).

Применяя к предикату P(x,y) кванторы в разном порядке, можно получить следующие высказывания:

∀x∀yP(x,y), ∀y∀xP(x,y), ∀x∃yP(x,y), ∀y∃xP(x,y), ∃x∃Py(x,y), ∃y∃xP(x,y), ∃x∀yP(x,y), ∃y∀xP(x,y).

Первые два высказывания в каждой строчке имеют одинаковые значения истинности:

[∀x∀yP(x,y)] = [∀y∀xP(x,y)], [∃x∃yPy(x,y)] = [∃y∃xP(x,y)].

Значения истинности высказываний ∀x∃yP(x,y) и ∃y∀xP(x,y) (так же, как и высказываний в оставшейся паре), вообще говоря, различны.

Пример. Для предиката y>x² на множестве действительных чисел имеем:

[∀x∀y y>x²]=0; [∃x∃y y>x²]=1;

[∀x∃y y>x²]=1; [∃y∀x y>x²]=0.􀀀

Пусть P(x) – произвольный предикат на конечном множестве X, состоящем, например, из двух элементов a и b. Тогда

∀xP(x)≅P(a)∧P(b); ∃xP(x)≅P(a)∨P(b).

Применяя отрицание и воспользовавшись законами де Моргана, получаем:

[(∀xP(x))] = [(P(a)∧P(b))] = [P(a)∨P(b)] = [∃x(P(x))];

[(∃xP(x))] = [(P(a)∨P(b))] = [P(a)∧P(b)] = [∀x(P(x))].

Нетрудно видеть, что подобные равенства верны для предикатов на произвольном множестве X (не обязательно конечном):

[(∀xP(x))] = [х∃x(P(x))]; [(∃xP(x))] = [∀x(P(x))]. Эти равенства называют законами де Моргана для кванторов.

В математической практике распространены так называемые ограниченные кванторы.

Ограниченный квантор существования. Запись ∃Q(x)P(x) служит сокращением для ∃x(Q(x)∧P(x)). Высказывание ∃Q(x)P(x) истинно, если среди объектов, обладающих свойством Q, найдется объект, обладающий свойством P. Например, утверждение «существует отрицательное число, квадрат которого больше двух» может быть записано в виде ∃x<0 x²>2.

Ограниченный квантор общности. Запись ∀Q(x)P(x) служит сокращением для ∀x(Q(x)→P(x)). Высказывание ∀Q(x)P(x) истинно, если P(x) истинно для всех x, обладающих свойством Q. Например, утверждение «квадрат любого числа из промежутка [–2;2] не превосходит четырех» может быть записано в виде ∀x∈[–2;2] x²≤4. Равносильным образом это может быть записано так же, как ∀|x|≤2 x²≤4.

Не нашли, что искали? Воспользуйтесь поиском: