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

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

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

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

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


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

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


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


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


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


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


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


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


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


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

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


\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}

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


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


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


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

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




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


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


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

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


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

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




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


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


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

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


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


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


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


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




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


(P\land Q)^{+}= P^{+}\cap Q^{+}

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


\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}

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


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


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

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


P^{+}= Q^{+}= M_1\times M_2\times \ldots\times M_n\,,

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


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


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

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


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




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


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


P(x_1, x_2, \ldots, x_n)\lor Q(y_1,y_2,\ldots,y_m)

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


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


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

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


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


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




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


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


(P\lor Q)^{+}= P^{+}\cup Q^{+}.

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


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


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


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


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


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


\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}

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




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


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


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


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


\bigl(P\lor (Q\land R)\bigr)~ \Leftrightarrow~ \bigl((P\lor Q)\land (P\lor R)\bigr)

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




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


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


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

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


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

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


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

и так далее для любых предикатов P,\,Q,\,R.
Перейти на форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

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


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

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