Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


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

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


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


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


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


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


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


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


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


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

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


[math]\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}[/math]
что и требовалось доказать.

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


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


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

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




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


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


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

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

[math]\sin{x}=2,\quad x^2<0,\quad e^x<0,\quad |x|<0[/math] и т.д.

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




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


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


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

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


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


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


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


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




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


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

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


[math]\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}[/math]

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


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


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

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


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

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

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


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

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


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




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


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


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

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


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


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

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


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


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




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


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


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

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


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


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


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


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


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


[math]\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}[/math]

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




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


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


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


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


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

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




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


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


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

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


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

и т.д. Аналогично, из тавтологий теоремы 3.4 получаются равносильности, выражающие одни логические операции над предикатами через другие. Например,

a) [math](P\to Q)\Leftrightarrow (\lnot P\lor Q)[/math];
в) [math](P\land Q)\Leftrightarrow \lnot(\lnot P\land\lnot Q)[/math];
ж) [math](P\leftrightarrow Q)\Leftrightarrow \bigl((P\to Q)\land (Q\to P)\bigr)[/math]

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

Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved