Игошин Математическая логика и теория алгоритмов (1019110), страница 37
Текст из файла (страница 37)
Отрицанием предиката «гйпгх+ созгх = 1» является предикат «з)п ~х+ сов~хе 1» (х1 у е А). Теорема 19.2. Для п-местного предиката Р(хп хп ..., х„), опредеенного на множествах Мь Мъ ..., М„, множество истинности его отрицания - Р(хь хъ ..., х„) совпадает с дополнением множества истинности данного предиката: ( Р)'= Р'.
(Здесь следует понимать, что дополнение рассматривается в множестве М, х Мз х ... х М„, т.е. ( Р)" = (М, х Мг х ... х М„) ~ Р'.) 151 До к аз ател ьст во. Согласно определениям 19.1, 18.3 и определению дополнения множества имеем ( Р)' = Наь аь ..., а,): Х(Р(аь аг, а„)) = О) = =Напав..., а): (аьаз, ..., а) в Р'1 = Р' =(М,х Мгх, хМ) '~ Р', что и требовалось доказать.
П Следствие 19.3. Отрицание предиката будет тождественно истинным тогда и только тогда, когда исходный предикат тождественно ложен. Доказательство. В 8 18 (пункт «Множество истинности предиката») тождественная истинность предиката выражена на языке множества истинности; она означает, что (- Р)' = М, х Мг х ... х М„. Подставим в это равенство значение для (- Р) из настоящей теоремы: (М~ х Мг х ... х М«), Р = М~ х Мг х ...
х М». Вспоминая определение разности двух множеств (см. э" 8) и учитывая, что Р+ <- М, х М, х ... х М„, заключаем, что Р' = Я. Значит, предикат Р(х„х„..., х,) тождественно ложен. Следствие доказано. П Рассмотрим еще один п р и м е р. Требуется выяснить, является ли предикат 0(1); «1' — нечетная функция» отрицанием предиката ЕЦ): «Г" — четная функция» (оба одноместных предиката определены на множестве всех действительных функций одного действительного аргумента).
Множество истинности О+ предиката 0(1') не является дополнением множества истинности Е' предиката Е(1'), потому что не всякая функция, не являющаяся четной, будет непременно нечетной. Другими словами, существуют функции, не являющиеся одновременно ни четными, ни нечетными (приведите пример!). Следовательно, предикат 0(1) не есть отрицание предиката Е(1'). Замечание 19.4. В алгебре высказываний существенным было не содержание высказывания, а лишь его значение истинности, т.е. отождествлялись (не различались) между собой, с одной стороны, все истинные высказывания, а с другой — все ложные.
В некотором смысле аналогичная ситуация имеется и в алгебре предикатов: здесь не различают равносильные предикаты. Подходя с такой точки зрения к определению !9.1 отрицания предиката, можем за отрицание данного предиката Р(х„хм ..., х„) принять любой из равносильных предикатов, удовлетворяющих этому определению.
Например, отрицанием предиката «~х~ > 2», заданного на А, является каждый из следующих (равносильных между собой) предикатов: «)х( < 2», «(х > -2) ы (х < 2)», «х в 1-2, 2]», а отрицанием предиката «х' > 0», также определенного на А (этот предикат тождественно истинный), является каждый из следующих предикатов: «гйп х = 2», «хг < 0», «е" < 0», «)х! < 0» и т.д.
152 Сделанное замечание следует иметь в виду при рассмотрении и остальных логических операций в настоящем параграфе. Конъюнкция двух предикатов. Определение 19.5. Конъюнкцией и-местного предиката Р(х„хг, ..., х„), определенного на множествах Мь Мг, ..., М„, и т-местного предиката 0(у„у„..., у„), определенного на множествах 1чь Фг, ..., Ьг, называется новый (п+ т)-местный предикат, определенный на множествах Мь Мг, ..., М», гчн 1уг, ..., Ф, обозначаемый Р(хо хг, ..., х„) л 0(уь уг, ..., у ) (читается «Р(х„х, ..., х,) и 0(уг, уъ ..., у )»), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых оба исходных предиката превращаются в истинные высказывания.
Другими словами, предикат Р(х„х„..., х„) л 0(уь уг, -, у ) таков, что лля любых предметов а, е Мь аг в Мг, ..., а„е М„и Ь, е Ж„Ьг е )уг, ..., Ь„я Ф высказывание Р(а„а„..., а„) л 0(Ь„ Ь,, ..., Ь ) является конъюнкцией высказываний Р(а,, а,, ..., а„) и 0(Ь,, Ь, ..., Ь ). Например, конъюнкцией двух одноместных предикатов «х > -3» и «х< 3», определенных на Я, будет одноместный предикат «(х >-3) л л (х < 3)», записываемый короче в виде: « — 3 < х < 3», который равносилен предикату «(х! < 3» (см. замечание 19.4). Другой пример. Конъюнкцией двух одноместных предикатов «х = О» и «у = О», заданных на А, является двухместный предикат «(х = О) л (у = О)», заданный на Яг, который равносилен предикату «х'+ уг = О», определенному также на яг.
Операцию конъюнкции можно применять к предикатам, имеющим общие переменные. В этом случае число переменных в новом предикате равно числу и+ т — к, где п — число переменных первого предиката, т — число переменных второго предиката, 1с— число переменных общих для обоих предикатов.
Именно таков первый из только что рассмотренных двух примеров. Более того, если оба предиката определены на одних и тех же множествах и зависят от одних и тех же переменных, то для них справедлива следующая теорема. Теорема 19.б. Ди п-местных предикатов Р(х„хг, ..., х„) и 0(хг, хп, х„), определенных на множествах М„Мг, ..., М„, множество истинности конъюнкции Р(х„хг, ..., х„) л 0(хг, хг, ..., х„) совпадает с пересечением множеств истинности исходных предикатов: (Р л 0) = Р' П 0'. Доказательство. Согласно определениям 195, !83 и опРеделению пересечения множеств имеем (Р л 0)' = ((а„аг, ..., а„): Х(Р(ан аг, ..., а„) л 0(аь а,, ..., а )) = Ц = Иа„аг, ..., а ): ЦР(аг, аг, ..., а ) = ! и л(0(аь аг, ..., а„)) = Ц = ((а„аг, ..., а„): Х(Р(аь аг, ..., а„) = Ц П П ((ап аг, ..., а„): Х(0(а„аг, ..., а„)) = Ц = Р' П 0'.
!53 Следствие 19. 7. Коньюнкция двух предикатов тождественно истинна тогда и только тогда, когда оба данных предиката тождественно истинны. Доказательство. Согласно з 18 (пункт«Множество истинности предиката») тождественная истинность предиката Р л Ц означает, что (Р л Ц)' = М, х Мг х „. х М„. Тогда на основании теоремы Р' П 0' = М, х Мг х ...
х М„, т.е. пересечение двух подмножеств Р'и Ц'множества М, х Мгх ... х М„совпадает с самим этим множеством. Следовательно, Р' = Ц' = М, х М, х ... х М„, а это означает, что предикаты Р и Ц тождественно истинны. П Значительный раздел школьной математики составляют системы уравнений и неравенств.
При их решении используется теорема 19.6. Пусть, например, требуется решить систему неравенств 1х~ < 3, х > 2. Для этого нужно найти множество истинности предиката «((х! < 3) л (х > 2)», определенного на А. Используем теорему 19.6: ((/х! < 3) л (х > 2))" = (/х/ < 3)' П (х > 2)' = )-3, 3[ П [2, + [ = [2, 3[. Таким образом, решением данной системы является множество (полуинтервал) [2, 3[. Следует отметить, что в предикаты Р(х„хь ..., х,) и 0(хь хь, х„), о которых идет речь в теореме 19.6, некоторые предметные переменные могут в действительности не входить, т.е., как говорят, быть фиктивными.
Это нужно понимать так, что значение истинности высказывания, в которое превращается данный предикат, не зависит от того, какие предметы подставляются вместо таких (фиктивных) переменных. При решении систем уравнений и неравенств данная ситуация встречается часто. Так, например, решения системы уравнений х+ у = 1, у+ г = 2, г+ х = 3 образуют множество, состоящее из одной упорядоченной тройки чисел (1, О, 2), хотя первое уравнение не зависит от г, второе — от х, а третье — от у.
Дизъюнкдия двух предикатов. Определение 19.8. Дизьюнкцией и-местного предиката Р(х„хь ..., х.), определенного на множествах Мп Мг, ..., М„, и т-местного предиката Д(уь уп ..., у ), определенного на множествах Фп Ф„..., Ф„, называется новый (и+т)-местный предикат, определенный на множествах М„ Мь ..., М„, Фь Уь ..., Ф„, обозначаемый Р(хь хъ ..., х„)ч 0(у„у„..., у ) (читается «Р(х„хг, ..., х„) или Д(уо уп ...„у )»), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых в истинное высказывание превращается по меньшей мере один из исходных предикатов, Другими словами, предикат Р(хь хъ ..., х„) ч О(уь у, ..., у ) таков, что для любых предметов а, я Мо аг я Мп ..., а„я М„и Ь1 я Фь Ьг я Фъ ..., Ь е Ф высказывание Р(ао аь ..., а„) ч О(Ьь 154 ьъ ..., Ь ) является дизъюнкцией высказываний Р(а„аъ ..., а„) и 0(Ь„б„..., Ь„). Операцию дизъюнкции, как и операцию конъюнкции (см.
абзац перед теоремой 19.6), можно применять, в частности к предикатам, имеющим общие переменные. Например, дизъюнкцией двух одноместных предикатов «х — четное число» и «х — простое число», определенных на Ф, является одноместный предикат, определенный на У: «х — четное или простое число». Дизъюнкцией одноместных предикатов «х и 0» и «у е 0», определенных на Я, является двухместный предикат «(х ~ 0) ы (у в 0)», определенный на Я~, который равносилен предикату «ха+ уг ~ 0» над Я'. Следующая теорема аналогична теореме 19.6.
Теорема 19.9. Для и-местных предикатов Р(х„хъ ..., х„) и 0(хь х,, ..., х„), определенных на множествах Мь Мъ ..., М„, множество истинности дизьюнкции Р(х„хъ ..., х„) ы 0(хь х,, ..., х„) совпадает с обьединением множеств истинности исходных предикатов: (Р ы 0)' = Р+ Ц Д". Д о к а з а т е л ь с т в о аналогично доказательству теоремы 19.6, поэтому предлагаем провести его самостоятельно. П Следствие 19.10.
Дизьюнкция двух предика тов есть вы олнимый предикат тогда и только тогда, когда по меньшей мере один из данных предикатов выполним. Доказательство. Согласно В!8 (пункт«Множество истинности предиката») выполнимость предиката Р ы (г означает, что (Р ы Ц)'в И. Отсюда на основании теоремы 19.9 Р' (з' Д' в И. Последнее возможно в том и только в том случае, если Р' в И или 0' и И, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
