Игошин Математическая логика и теория алгоритмов (1019110), страница 38
Текст из файла (страница 38)
если выполним предикат Р или выполним предикат Д. П Следствие 19.11. Дизьюнкция двух предикатов тождественно ложна тогда и только тогда, когда оба данных предиката тождественно ложны. Доказательство предлагается провести самостоятельно. Например, пусть требуется решить уравнение хл — х — 6 = О, т.е. найти множество истинности этого предиката, определенного на Тс Находим его, применяя теорему 19.9. Тогда (х: х' — х — 6 = О) = (х: (х+ 2)(х — 3) = О) = (х: (х + 2 = 0) ы ы (х — 3 = 0)) = (х:х+ 2 = 0) () (х: х — 3 = О) = (-2) 0 (3) = (-2, 3). В другом примере дизъюнкция (ха+ уз< 0) г (ху= 0) двух двухместных предикатов, определенных на Я', есть выполнимый преликат, потому что выполним один из них: ху = 0 (проверьте). Свойства отрицания, конъюнкции и дизъюпкции. После введения трех операций над предикатами возникают вопросы: как они влияют на равносильность предикатов и каковы закономерности 155 образования с помощью этих операций равносильных предикатов? Аналогичны вопросы для следования предикатов.
Ответ дает следующая теорема. Теорема 19.12. Если во всех формулах теоремы 3.2 под Р, О, Я понимать предикаты, определенные на соответствующих множествах, знак +-» всюду заменить знаком <=>, а знак -» — знаком =ь, то получим верные утверждения о предикатах. Доказательство. Рассмотрим, например, вторую из формул д) теоремы 3.2.
Она превращается в следующее угверждение: (Р ~ ((1 п п гс)) с=> ((Р ы О) и (Р ~ Я)), означающее равносильность предикатов Р ~ (Ц п Я) и (Р ~ Ц) л (Р г Я) независимо от предикатов Р, Ц, Я. Проверим, верно ли данное утверждение. В самом деле, каждый из двух предикатов при любой подстановке вместо предметных переменных конкретных предметов из соответствующих множеств превращается в такое высказывание, которое на основании тавтологии из теоремы 3.2, д имеет одинаковые значения истинности. На основании определения равносильности предикатов это и означает, что данные предикаты равносильны. П Импликация и эквивалентность двух предикатов.
Импликация Р(хь хг* ", х,) -» 0(уь уг, ..., у ) определяется как такой предикат, что для любых предметов а, е М„аг е Мг, ..., а„е М„и Ьг е Фь Ьг е Фг, ..., Ь е Ф,„высказывание Р(аь аг, ..., а„) -» Д(Ьг, Ьг, ..., Ь„) является импликацией высказываний Р(а,, а„..., а„) и Д(Ь„Ьг, ..., Ь ). Аналогично определяется эквивалентность двух предикатов. Нетрудно проверить, что импликация двух предикатов, зависящих от одних и тех же переменных, есть тождественно истинный предикат тогда н только тогда, когда ее заключение является следствием посылки, а эквивалентность тождественно истинна, если и только если исходные предикаты равносильны.
Свойства этих операций над предикатами„подобно свойствам операций отрицания, конъюнкции и дизъюнкцни над предикатамн (см. теорему 19.12), получаются нз соответствующих тавтологий теоремы 3.3. Так, если Р, ('г, Я вЂ” предикаты, то, например, а) (Р -» (Ц вЂ” » 11)) =ь ((Р— » О) -+ (Р -+ Я)); д) (-10 п (Р— » О)) =ь — Р; п) (Р +-+ О) с=> (Ц +-» Р) и т.д. Аналогично, из тавтологий теоремы 3.4 получаются равносильности, выражающие одни логические операции над предика- тами через другие. Например, а) (Р -+ Д) с=> (-Р ~ Ц); в) (Рп О) с=> — ( Рп-О); ж) (Р с-» Д) еь ((Р— » О) п (Ц -+ Р)) и так далее для любых предикатов Р, Д, 11.
156 ф 20. Кваиториые операции иад предикатами Рассмотренные в предыдущем параграфе операции над предикатами в определенном смысле аналогичны соответствующим операциям над высказываниями. Специфика природы предикатов позволяет ввести такие операции над ними, которые не имеют аналогов среди операций над высказываниями. Имеются в виду две кванторные операции над предикатами (или операции квантификации) — квантор общности и квантор существования, о которых и пойдет речь в настоящем параграфе. Кваитор общности. Известно, что для превращения одноместного предиката в высказывание нужно подставить вместо его переменной какой-нибудь конкретный предмет из области задания предиката.
Имеется еще один способ для такого превращения— это применение к предикату операций связывания квантором общности или квантором существования. Каждая из этих операций ставит в соответствие одноместному предикату некоторое высказывание, истинное или ложное в зависимости от исходного преди ката. Онределение 20.1. Операцией связывания квантором общности называется правило, по которому каждому одноместному предикату Р(х), определенному на множестве М, сопоставляется высказывание, обозначаемое (Ъх)(Р(х)) (читается: «для всякого (значения) х Р(х) 1истинное высказывание1»), которое истинно в том и только в том случае, когда предикат Р(х) тождественно истинен, и ложно в противном случае, (1, если Р(х) — тождественно истинный предикат, 10, если Р(х) — опровержимый предикат.
При чтении высказывания (ях)(Р(х)) слова в квадратных скобках могут опускаться. Высказывание (ях)(Р(х)) называется универсальным высказыванием для предиката Р(х). Символ Ч происходит от первой буквы англ. а!! — «все». Сам символ (ях) также называют квантором общности по переменной х. Например, рассмотрим два одноместных предиката на множестве У: «1 < х» и «к~30». Первый предикат тождественно истинный, поэтому применение к нему операции связывания квантором общности дает истинное высказывание: (ях)(1 < х) — «для всякого х число 1 не превосходит х». Второй предикат опровержим, поэтому операция связывания квантором общности, примененная к нему, дает ложное высказывание: ('Фх)(х)30) — «для любого х число х является делителем числа 30». В выражении (Чх)(Р(х)) переменная х уже перестает бьггь переменной в обычном смысле этого слова, т.е.
вместо нее невозможно псдставлять какие бы то ни было конкретные значения. Считают, 157 что переменная х связаяная, кажущаяся или немая. Такая ситуация уже встречалась в математике: переменные могут быть связаны не только квантором. Так, связанными являются переменные в следующих выражениях: г ! хЖс, 1пп -, (х: х > 0). о -и Это означает, что каждое из приведенных выражений не зависит от связанных переменных, т.е. сущность выражения не изменится, если связанную переменную обозначить любой другой буквой.
Так, первое из трех выражений вне зависимости от переменной равно 2, второе равно О, а третье — действительная полупрямая 1О; + (. Аналогично, высказывание ('о'х)(1 < х) может быть прочитано так: «! не превосходит всякое натуральное число«в и в таком виде оно вообще не содержит переменных. Если одноместный предикат Р(х) задан на конечном множестве М = (а„аг, ..., а ), то нетрудно понять, что высказывание (~Ух)(Р(х)) эквивалентно (имеет то же логическое значение) конъюнкции Р(а,) л Р(аг) л ... л Р(а„). В самом деле, по определению 20.1 истинность высказывания (ггх)(Р(х)) означает, что предикат тождественно истинен, т.е. каждое из высказываний Р(а,), Р(аг), ..., Р1,а«1, в которые этот предикат превращается, истинно. Последнее равносильно истинности конъюнкции Р(а,) г л Р(аг) л ... л Р(а„). Следовательно, для предикатов, заданных на конечном множестве, операция связывания квантором общности может быть выражена через конъюнкцию.
Для предикатов, заданных на бесконечном множестве, такого сделать нельзя, и в этом случае операция связывания квантором общности является существенно новой. Можно подметить еще одну особенность операции связывания квантором общности по сравнению с операциями из предыдущего параграфа. Те операции ставили в соответствие одному или двум предикатам новый предикат, а операция связывания квантором общности сопоставляет предикату высказывание.
На это можно сказать следующее. Во-первых, каждое высказывание для достижения большей общности сейчас и в дальнейшем можно рассматривать как предикат, содержащий 0 предметных переменных, т.е. как нульместный предикат. Во-вторых, мы пока применяли квантор общности лишь к одноместным предикатам. Переходим к рассмотрению вопроса о применении операции связывания квантором общности к предикатам с любым числом предметных переменных; такая операция предстанет операцией в полном смысле слова: предикатам она будет сопоставлять предикаты. !58 Определение 20.2. Операцией связывания нвантором общности по переменной х, называется правило, по которому каждому и-местному (и > 2) предикату Р(х„хь ..., х„), определенному на множествах М„Мп ..., М„, ставится в соответствие новый (и — 1)-местный предикат, обозначаемый ('Фх,КР(хь х„..., х„)) (читается: лля всех х, Р(хь хз, ..., х„)»), который для любых предметов аз е Мь ..., а„е М» превращается в высказывание (~Гх,)(Р(хп а,, ..., а„)), истинное в том и только в том случае, когда одноместный предикат Р(хь а,, ..., а„), определенный на множестве М„тождественно истинен, и ложное в противном случае.
Другими словами: 1, если Р(хп а„..., а„) — тождественно ~[(»х1)(Р(х~ аз ... а ))[ истинный предикат от х,, О, если Р(х„а,, ..., а„) — опровержимый предикат отх,. Например, рассмотрим двухместный предикат «у < х», определенный на множестве №. Применим к нему квантор общности по переменной х. Получим одноместный предикат (~ух)(у < х), зависящий от переменной у. Этот предикат может превратиться как в истинное высказывание (при у= 1), так и в ложное (при подстановке вместо у любых натуральных чисел, кроме 1). В другом примере двухместный предикат «(х+ у) з = х'+ 2ху+ уз», определенный на йз, тождественно истинен.
Поэтому применение к нему квантора общности по любой переменной, например по у, дает одноместный предикат (по х), который будет тождественно истинным («у)Их+ у)з = хз+ 2ху+ уз). Заметим в заключение, что к (и-!)-местному предикату ('вх,)(Р(хп хз, ..., х„)), зависящему от переменных хц ..., х„, можно снова применить операцию связывания квантором общности по одной из свободных переменных. В результате получится (и — 2)-местный предикат и т. д. Например, применив к одноместному предикату (»х)(у < х), где х, у в А, квантор общности по переменной у, получим нуль- местный предикат, т.е. высказывание (»у)(Чх)(у < х). Ясно, что полученное высказывание ложно, потому что предикат (Чх)(у < < х) опровержим. Применив квантор общности по переменной х к одноместному предикату из второго примера, получим истинное высказывание ('Фх)(Чу)((х+ у)з = хз+ 2ху+ уз).
Квантор существования. Как и в предыдущем пункте, начнем рассмотрение с операции связывания квантором существования, применяемой к одноместному предикату. Оиределеиие 20.3. Операцией связывания нвантором существова"ня называется правило, по которому каждому одноместному пред"кату Р(х), определенному на множестве М, ставится в соответствие высказывание, обозначаемое (Лх)(Р(х)) (читается: «существует 159 [значение] х, такое, что Р(х) [истинное высказывание]»), которое ложно в том и только в том случае, когда Р(х) тождественно ложен, и истинно в противном случае, т.е. (О, если Р(х) — тождественно ложный предикат, ).[(ЗхНР(х))] = ~ ' [1, еслиР(х) — выполнимый предикат.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
