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

Над предикатами можно проделывать те же самые логические операции, что и над высказываниями: отрицание, конъюнкцию, дизъюнкцию, импликацию, эквивалентность. Рассмотрим эти операции в их связи с операциями над множествами.

Отрицание предиката

Определение 19.1. Отрицанием n-местного предиката [cbm]P(x_1,x_2,\ldots,x_n)[/cbm] , определенного на множествах [cbm]M_1,M_2,\ldots,M_n[/cbm] , называется новый n-местный предикат, определенный на тех же множествах, обозначаемый [cbm]\lnot P(x_1,x_2,\ldots,x_n)[/cbm] (читается: "неверно, что [cbm]P(x_1,x_2,\ldots,x_n)[/cbm] , который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых исходное высказывание превращается в ложное высказывание.

Другими словами, предикат [cbm]\lnot P(x_1,x_2,\ldots,x_n)[/cbm] таков, что для любых предметов [cbm]a_1\in M_1,a_2\in M_2,\ldots,a_n\in M_n[/cbm] высказывание [cbm]\lnot P(a_1,a_2,\ldots,a_n)[/cbm] является отрицанием высказывания [cbm]P(a_1,a_2,\ldots,a_n)[/cbm] .

Например, нетрудно понять, что отрицанием одноместного предиката " [cbm]x \leqslant 3[/cbm] ", определенного на множестве [cbm]\mathbb{R}[/cbm] , является одноместный предикат " [cbm]x>3[/cbm] ", определенный на том же множестве [cbm]\mathbb{R}[/cbm] . Отрицанием предиката "Река [cbm]x[/cbm] впадает в озеро Байкал" является предикат "Река [cbm]x[/cbm] не впадает в озеро Байкал" (оба одноместных предиката определены на множестве названий рек). Отрицанием предиката " [cbm]\sin^2x+\cos^2x=1[/cbm] " является предикат " [cbm]\sin^2x+\cos^2x\ne1[/cbm] " [cbm](x,y\in \mathbb{R})[/cbm] .

Теорема 19.2. Для n-местного предиката [cbm]P(x_1,x_2,\ldots,x_n)[/cbm] , определенного на множествах [cbm]M_1,M_2,\ldots,M_n[/cbm] , множество истинности его отрицания [cbm]\lnot P(x_1,x_2,\ldots,x_n)[/cbm] совпадает с дополнением множества истинности данного предиката: [cbm](\lnot P)^{+}= \overline{P^{+}}[/cbm] .

Здесь следует понимать, что дополнение рассматривается в множестве

[cbm]M_1\times M_2\times \ldots\times M_n[/cbm] , то есть [cbm](\lnot P)^{+}= M_1\times M_2\times \ldots\times M_n\setminus P^{+}[/cbm] .

Доказательство. Согласно определениям 19.1, 18.3 и определению дополнения множества имеем

[cbm]\begin{aligned}(\lnot P)^{+}&= \bigl\{(a_1,a_2, \ldots, a_n)\colon\, \lambda \bigl(P(a_1,a_2,\ldots, a_n)\bigr)=0\bigr\}=\\ &= \bigl\{(a_1,a_2,\ldots,a_n)\colon\, (a_1,a_2,\ldots,a_n)\notin P^{+}\bigr\}=\\ &= \overline{P^{+}}= (M_1\times M_2\times \ldots\times M_n)\setminus P^{+}, \end{aligned}[/cbm]
что и требовалось доказать.

Следствие 19.3. Отрицание предиката будет тождественно истинным тогда и только тогда, когда исходный предикат тождественно ложен.

Доказательство. В предыдущей лекции (пункт "Множество истинности предиката") тождественная истинность предиката выражена на языке множества истинности; она означает, что [cbm](\lnot P)^{+}= M_1\times M_2\times \ldots\times M_n[/cbm] . Подставим в это равенство значение для [cbm](\lnot P)^{+}[/cbm] из настоящей теоремы:

[cbm](M_1\times M_2\times \ldots\times M_n) \setminus P^{+}= M_1\times M_2\times \ldots\times M_n\,.[/cbm]

Вспоминая определение разности двух множеств и учитывая, что [cbm]P^{+}\subseteq M_1\times M_2\times \ldots\times M_n[/cbm] , заключаем, что [cbm]P^{+}=\varnothing[/cbm] . Значит, предикат [cbm]P(x_1,x_2,\ldots,x_n)[/cbm] тождественно ложен. Следствие доказано.


Рассмотрим еще один пример. Требуется выяснить, является ли предикат [cbm]O(f)\colon[/cbm] " [cbm]f[/cbm] — нечетная функция" отрицанием предиката [cbm]E(f)\colon[/cbm] " [cbm]f[/cbm] — четная функция" (оба одноместных предиката определены на множестве всех действительных функций одного действительного аргумента). Множество истинности [cbm]O^{+}[/cbm] предиката [cbm]O(f)[/cbm] не является дополнением множества истинности [cbm]E^{+}[/cbm] предиката [cbm]E(f)[/cbm] , потому что не всякая функция, не являющаяся четной, будет непременно нечетной. Другими словами, существуют функции, не являющиеся одновременно ни четными, ни нечетными (приведите пример!). Следовательно, предикат [cbm]O(f)[/cbm] не есть отрицание предиката [cbm]E(f)[/cbm] .

Замечание 19.4. В алгебре высказываний существенным было не содержание высказывания, а лишь его значение истинности, т.е. отождествлялись (не различались) между собой, с одной стороны, все истинные высказывания, а с другой — все ложные. В некотором смысле аналогичная ситуация имеется и в алгебре предикатов: здесь не различают равносильные предикаты. Подходя с такой точки зрения к определению 19.1 отрицания предиката, можем за отрицание данного предиката [cbm]P(x_1,x_2,\ldots,x_n)[/cbm] принять любой из равносильных предикатов, удовлетворяющих этому определению. Например, отрицанием предиката " [cbm]|x|>2[/cbm] ", заданного на [cbm]\mathbb{R}[/cbm] , является каждый из следующих (равносильных между собой) предикатов:

[cbm]|x|\leqslant 2,\qquad (x \geqslant -2)\lor (x \leqslant 2),\qquad x\in[-2;2],[/cbm]

а отрицанием предиката " [cbm]x^2 \geqslant 0[/cbm] ", также определенного на [cbm]\mathbb{R}[/cbm] (этот предикат тождественно истинный), является каждый из следующих предикатов:
[cbm]\sin{x}=2,\quad x^2<0,\quad e^x<0,\quad |x|<0[/cbm] и т.д.

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


Конъюнкция двух предикатов

Определение 19.5. Конъюнкцией "-местного предиката [cbm]P(x_1,x_2,\ldots,x_n)[/cbm] , определенного на множествах [cbm]M_1,M_2,\ldots,M_n[/cbm] , и m-местного предиката [cbm]Q(y_1,y_2,\ldots,y_m)[/cbm] , определенного на множествах [cbm]N_1,N_2,\ldots,N_m[/cbm] , называется новый (n+m)-местный предикат, определенный на множествах

[cbm]M_1,M_2,\ldots,M_n,\, N_1,N_2,\ldots,N_m[/cbm] , обозначаемый [cbm]P(x_1,x_2,\ldots,x_n)\land Q(y_1,y_2,\ldots,y_m)[/cbm]

(читается " [cbm]P(x_1,x_2,\ldots,x_n)[/cbm] и [cbm]Q(y_1,y_2,\ldots,y_m)[/cbm] "), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых оба исходных предиката превращаются в истинные высказывания.

Другими словами, предикат [cbm]P(x_1,x_2,\ldots,x_n)\land Q(y_1,y_2,\ldots,y_m)[/cbm] таков, что для любых предметов [cbm]a_1\in M_1,a_2\in M_2,\ldots,a_n\in M_n[/cbm] и [cbm]b_1\in N_1,b_2\in N_2,\ldots,b_m\in N_m[/cbm] высказывание [cbm]P(a_1,a_2,\ldots,a_n)\land Q(b_1, b_2, \ldots, b_n)[/cbm] является конъюнкцией высказываний [cbm]P(a_1,a_2,\ldots,a_n)[/cbm] и [cbm]Q(b_1, b_2, \ldots,b_m)[/cbm] .

Например, конъюнкцией двух одноместных предикатов " [cbm]x>-3[/cbm] " и " [cbm]x<3[/cbm] ", определенных на [cbm]\mathbb{R}[/cbm] , будет одноместный предикат " [cbm](x>-3)\lor (x<3)[/cbm] ", записываемый короче в виде: " [cbm]-3<x<3[/cbm] ", который равносилен предикату " [cbm]|x|<3[/cbm] " (см. замечание 19.4).

Другой пример. Конъюнкцией двух одноместных предикатов " [cbm]x=0[/cbm] " и " [cbm]y=0[/cbm] ", заданных на [cbm]\mathbb{R}[/cbm] , является двухместный предикат " [cbm](x=0)\lor (y=0)[/cbm] ", заданный на [cbm]\mathbb{R}^2[/cbm] , который равносилен предикату " [cbm]x^2+y^2=0[/cbm] ", определенному также на [cbm]\mathbb{R}^2[/cbm] .

Операцию конъюнкции можно применять к предикатам, имеющим общие переменные. В этом случае число переменных в новом предикате равно числу [cbm]n+m-k[/cbm] , где [cbm]n[/cbm] — число переменных первого предиката, [cbm]m[/cbm] — число переменных второго предиката, [cbm]k[/cbm] — число переменных общих для обоих предикатов. Именно таков первый из только что рассмотренных двух примеров. Более того, если оба предиката определены на одних и тех же множествах и зависят от одних и тех же переменных, то для них справедлива следующая теорема.


Теорема 19.6. Для n-местных предикатов [cbm]P(x_1,x_2,\ldots,x_n)[/cbm] и [cbm]Q(x_1,x_2,\ldots,x_n)[/cbm] , определенных на множествах [cbm]M_1,M_2,\ldots,M_n[/cbm] , множество истинности конъюнкции [cbm]P(x_1,x_2,\ldots,x_n)\land Q(x_1,x_2,\ldots,x_n)[/cbm] совпадает с пересечением множеств истинности исходных предикатов:

[cbm](P\land Q)^{+}= P^{+}\cap Q^{+}[/cbm]

Доказательство. Согласно определениям 19.5, 18.3 и определению пересечения множеств имеем

[cbm]\begin{aligned}(P\land Q)^{+}&= \bigl\{(a_1,a_2,\ldots, a_n)\colon\, \lambda\bigl(P(a_1, a_2, \ldots, a_n)\land Q(a_1,a_2, \ldots,a_n\bigl)\bigr)=1\bigr\}=\\[2pt] &= \bigl\{(a_1,a_2,\ldots,a_n)\colon\, \lambda\bigl(P(a_1,a_2,\ldots,a_n)\bigr)=1,\, \lambda\bigl(Q(a_1,a_2, \ldots,a_n)\bigl)=1\bigl\}=\\[2pt] &= \bigl\{(a_1,a_2,\ldots,a_n)\colon\, \lambda\bigl(P(a_1, a_2,\ldots, a_n)\bigr)= 1\bigr\}\,\cap\\ &\phantom{=~} \cap \bigl\{(a_1,a_2,\ldots,a_n)\colon\, \lambda\bigl(Q(a_1,a_2, \ldots, a_n)\bigr)=1\bigr\}=\\[2pt] &= P^{+}\cap Q^{+}.\end{aligned}[/cbm]

Следствие 19.7. Конъюнкция двух предикатов тождественно истинна тогда и только тогда, когда оба данных предиката тождественно истинны.

Доказательство. Согласно пункту "Множество истинности предиката", тождественная истинность предиката [cbm]P\land Q[/cbm] означает, что

[cbm](P\land Q)^{+}= M_1\times M_2\times \ldots\times M_n\,.[/cbm]

Тогда на основании теоремы [cbm]P^{+}\cap Q^{+}= M_1\times M_2\times \ldots\times M_n[/cbm] , т.е. пересечение двух подмножеств [cbm]P^{+}[/cbm] и [cbm]Q^{+}[/cbm] множества [cbm]M_1\times M_2\times \ldots\times M_n[/cbm] совпадает с самим этим множеством. Следовательно,

[cbm]P^{+}= Q^{+}= M_1\times M_2\times \ldots\times M_n\,,[/cbm]

а это означает, что предикаты [cbm]P[/cbm] и [cbm]Q[/cbm] тождественно истинны.

Значительный раздел школьной математики составляют системы уравнений и неравенств. При их решении используется теорема 19.6. Пусть, например, требуется решить систему неравенств [cbm]|x|<3,~ x \geqslant 2[/cbm] . Для этого нужно найти множество истинности предиката " [cbm](|x|<3)\land (x \geqslant 2)[/cbm] ", определенного на [cbm]\mathbb{R}[/cbm] . Используем теорему 19.6:

[cbm]\bigl((|x|<3)\land (x \geqslant 2)\bigr)^{+}= (|x|<3)^{+}\cap (x \geqslant 2)^{+}= (-3;3)\cap [2;+\infty)= [2;3).[/cbm]

Таким образом, решением данной системы является множество (полуинтервал) [cbm][2;3)[/cbm] .

Следует отметить, что в предикаты [cbm]P(x_1,x_2,\ldots,x_n)[/cbm] и [cbm]Q(x_1,x_2,\ldots,x_n)[/cbm] , о которых идет речь в теореме 19.6, некоторые предметные переменные могут в действительности не входить, т.е., как говорят, быть фиктивными. Это нужно понимать так, что значение истинности высказывания, в которое превращается данный предикат, не зависит от того, какие предметы подставляются вместо таких (фиктивных) переменных. При решении систем уравнений и неравенств данная ситуация встречается часто. Так, например, решения системы уравнений [cbm]\begin{cases}x+y=1,\\[-2pt] y+z=2,\\[-2pt] z+x=3\end{cases}[/cbm] образуют множество, состоящее из одной упорядоченной тройки чисел [cbm](1;0;2)[/cbm] , хотя первое уравнение не зависит от [cbm]z[/cbm] , второе — от [cbm]x[/cbm] , а третье — от [cbm]y[/cbm] .


Дизъюнкция двух предикатов

Определение 19.8. Дизъюнкцией n-местного предиката [cbm]P(x_1, x_2, \ldots, x_n)[/cbm] , определенного на множествах [cbm]M_1,M_2,\ldots,M_n[/cbm] , и m-местного предиката [cbm]Q(y_1,y_2,\ldots,y_m)[/cbm] , определенного на множествах [cbm]N_1,N_2,\ldots,N_m[/cbm] , называется новый (n+m)-местный предикат, определенный на множествах [cbm]M_1,M_2,\ldots,M_n[/cbm] и [cbm]N_1,N_2,\ldots,N_m[/cbm] , обозначаемый

[cbm]P(x_1, x_2, \ldots, x_n)\lor Q(y_1,y_2,\ldots,y_m)[/cbm]

(читается " [cbm]P(x_1, x_2, \ldots, x_n)[/cbm] или [cbm]Q(y_1,y_2,\ldots,y_m)[/cbm] "), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых в истинное высказывание превращается по меньшей мере один из исходных предикатов.

Другими словами, предикат [cbm]P(x_1, x_2, \ldots, x_n)\lor Q(y_1,y_2,\ldots,y_m)[/cbm] таков, что для любых предметов

[cbm]a_1\in M_1,a_2\in M_2,\ldots,a_n\in M_n[/cbm] и [cbm]b_1\in N_1,b_2\in N_2,\ldots,b_m\in N_m[/cbm]

высказывание [cbm]P(a_1, a_2, \ldots, a_n)\lor Q(b_1,b_2, \ldots, b_m)[/cbm] является дизъюнкцией высказываний [cbm]P(a_1, a_2, \ldots, a_n)[/cbm] и [cbm]Q(b_1,b_2,\ldots,b_m)[/cbm] .

Операцию дизъюнкции, как и операцию конъюнкции (см. абзац перед теоремой 19.6), можно применять, в частности к предикатам, имеющим общие переменные. Например, дизъюнкцией двух одноместных предикатов " [cbm]x[/cbm] — четное число" и " [cbm]x[/cbm] — простое число", определенных на [cbm]\mathbb{N}[/cbm] , является одноместный предикат, определенный на [cbm]\mathbb{N}:[/cbm] " [cbm]x[/cbm] — четное или простое число".

Дизъюнкцией одноместных предикатов " [cbm]x\ne0[/cbm] " и " [cbm]y\ne0[/cbm] ", определенных на [cbm]\mathbb{R}[/cbm] , является двухместный предикат " [cbm](x\ne0)\lor (y\ne0)[/cbm] ", определенный на [cbm]\mathbb{R}^2[/cbm] , который равносилен предикату " x^2+y^2\ne0" над [cbm]\mathbb{R}^2[/cbm] .


Следующая теорема аналогична теореме 19.6.

Теорема 19.9. Для n-местных предикатов [cbm]P(x_1, x_2, \ldots, x_n)[/cbm] и [cbm]Q(x_1, x_2, \ldots, x_n)[/cbm] , определенных на множествах [cbm]M_1,M_2,\ldots,M_n[/cbm] , множество истинности дизъюнкции [cbm]P(x_1, x_2, \ldots, x_n)\lor Q(x_1, x_2, \ldots, x_n)[/cbm] совпадает с объединением множеств истинности исходных предикатов:

[cbm](P\lor Q)^{+}= P^{+}\cup Q^{+}.[/cbm]

Доказательство аналогично доказательству теоремы 19.6, поэтому предлагаем провести его самостоятельно.

Следствие 19.10. Дизъюнкция двух предикатов есть выполнимый предикат тогда и только тогда, когда по меньшей мере один из данных предикатов выполним.

Доказательство. Согласно § 18 (пункт"Множество истинности предиката") выполнимость предиката [cbm]P\lor Q[/cbm] означает, что [cbm](P\lor Q)^{+}\ne \varnothing[/cbm] . Отсюда на основании теоремы 19.9 имеем [cbm]P^{+}\cup Q^{+}\ne \varnothing[/cbm] . Последнее возможно в том и только в том случае, если [cbm]P^{+}\ne\varnothing[/cbm] или [cbm]Q^{+}\ne \varnothing[/cbm] , т.е. если выполним предикат [cbm]P[/cbm] или выполним предикат [cbm]Q[/cbm] .

Следствие 19.11. Дизъюнкция двух предикатов тождественно ложна тогда и только тогда, когда оба данных предиката тождественно ложны.

Доказательство предлагается провести самостоятельно.

Например, пусть требуется решить уравнение [cbm]x^2-x-6=0[/cbm] , т. е. найти множество истинности этого предиката, определенного на [cbm]\mathbb{R}[/cbm] . Находим его, применяя теорему 19.9. Тогда

[cbm]\begin{aligned}\bigl\{x\colon\, x^2-x-6=0\bigr\}&= \bigl\{x\colon\, (x+2)(x-3)=0\bigr\}= \bigl\{x\colon\, (x+2=0)\lor (x-3=0)\bigr\}=\\ &= \{x\colon\, x+2=0\}\cup \{x\colon\, x-3=0\}= \{-2\}\cup \{3\}= \{-2;3\}.\end{aligned}[/cbm]

В другом примере дизъюнкция [cbm](x^2+y^2<0)\lor (xy=0)[/cbm] двух двухместных предикатов, определенных на [cbm]\mathbb{R}[/cbm] , есть выполнимый предикат, потому что выполним один из них: [cbm]xy=0[/cbm] (проверьте).


Свойства отрицания, конъюнкции и дизъюнкции предикатов

После введения трех операций над предикатами возникают вопросы: как они влияют на равносильность предикатов и каковы закономерности образования с помощью этих операций равносильных предикатов? Аналогичны вопросы для следования предикатов. Ответ дает следующая теорема.

Теорема 19.12. Если во всех формулах теоремы 3.2 под [cbm]P,\,Q,\,R[/cbm] понимать предикаты, определенные на соответствующих множествах, знак [cbm]\leftrightarrow[/cbm] всюду заменить знаком [cbm]\Leftrightarrow[/cbm] , а знак [cbm]\to[/cbm] — знаком [cbm]\Rightarrow[/cbm] , то получим верные утверждения о предикатах.

Доказательство. Рассмотрим, например, вторую из формул д) теоремы 3.2. Она превращается в следующее утверждение:

[cbm]\bigl(P\lor (Q\land R)\bigr)~ \Leftrightarrow~ \bigl((P\lor Q)\land (P\lor R)\bigr)[/cbm]

означающее равносильность предикатов [cbm]P\lor (Q\land R)[/cbm] и [cbm](P\lor Q)\land (P\lor R)[/cbm] независимо от предикатов [cbm]P,\,Q,\,R[/cbm] . Проверим, верно ли данное утверждение. В самом деле, каждый из двух предикатов при любой подстановке вместо предметных переменных конкретных предметов из соответствующих множеств превращается в такое высказывание, которое на основании тавтологии из теоремы 3.2 (пункт д) имеет одинаковые значения истинности. На основании определения равносильности предикатов это и означает, что данные предикаты равносильны.


Импликация и эквивалентность двух предикатов

Импликация [cbm]P(x_1, x_2, \ldots, x_n)\to Q(y_1, y_2, \ldots, y_m)[/cbm] определяется как такой предикат, что для любых предметов

[cbm]a_1\in M_1,~ a_2\in M_2,~ \ldots,~ a_n\in M_n[/cbm] и [cbm]b_1\in M_1,~ b_2\in M_2,~ \ldots,~ b_m\in M_m[/cbm]

высказывание [cbm]P(a_1, a_2, \ldots, a_n)\to Q(b_1, b_2, \ldots, b_m)[/cbm] является импликацией высказываний [cbm]P(a_1, a_2, \ldots, a_n)[/cbm] и [cbm]Q(b_1, b_2, \ldots, b_m)[/cbm] . Аналогично определяется эквивалентность двух предикатов. Нетрудно проверить, что импликация двух предикатов, зависящих от одних и тех же переменных, есть тождественно истинный предикат тогда и только тогда, когда ее заключение является следствием посылки, а эквивалентность тождественно истинна, если и только если исходные предикаты равносильны. Свойства этих операций над предикатами, подобно свойствам операций отрицания, конъюнкции и дизъюнкции над предикатами (см. теорему 19.12), получаются из соответствующих тавтологий теоремы 3.3. Так, если [cbm]P,\,Q,\,R[/cbm] — предикаты, то, например,

а) [cbm]\bigl(P\to (Q\to R)\bigr)\Rightarrow \bigl((P\to Q)\to (P\to R)\bigr)[/cbm] ;
д) [cbm]\bigl(\lnot Q\land (P\to Q)\bigr)\Rightarrow\lnot P[/cbm] ;
п) [cbm](P\leftrightarrow Q)\Leftrightarrow (Q\leftrightarrow P)[/cbm]

и т.д. Аналогично, из тавтологий теоремы 3.4 получаются равносильности, выражающие одни логические операции над предикатами через другие. Например,
a) [cbm](P\to Q)\Leftrightarrow (\lnot P\lor Q)[/cbm] ;
в) [cbm](P\land Q)\Leftrightarrow \lnot(\lnot P\land\lnot Q)[/cbm] ;
ж) [cbm](P\leftrightarrow Q)\Leftrightarrow \bigl((P\to Q)\land (Q\to P)\bigr)[/cbm]

и так далее для любых предикатов [cbm]P,\,Q,\,R[/cbm] .

Источник

Поделитесь с другими:

Если материал понравился Вам и оказался для Вас полезным, поделитесь им со своими друзьями!

Читать по теме:

Интересные статьи: