Лекция: Логические и кванторные операции над предикатами
Отрицание предиката. Определение 19.1. Отрицанием п-местно-го предиката P(x1,..., xn ), определенного на множествах M1, ..., Mn, называется новый п-местный предикат, определенный на тех же множествах, обозначаемый P(x1,..., xn)(читается: «неверно, что P (x1,..., xn )»), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых исходное высказывание превращается в ложное высказывание..
Теорема 19.2. Для п-местного предиката P(x1,..., xn), определенного на множествах M1, ..., Mn, множество истинности его отрицания совпадает с дополнением множества истинности данного предиката: .
Следствие 19.3. Отрицание предиката будет тождественно истинным тогда и только тогда, когда исходный предикат тождественно ложен.
Замечание 19.4. В алгебре высказываний существенным было не содержание высказывания, а лишь его значение истинности, т.е. отождествлялись (не различались) между собой, с одной стороны, все истинные высказывания, а с другой — все ложные. В некотором смысле аналогичная ситуация имеется и в алгебре предикатов: здесь не различают равносильные предикаты. Подходя с такой точки зрения к определению 19.1 отрицания предиката, можем за отрицание данного предиката P(x1,..., xn)принять любой из равносильных предикатов, удовлетворяющих этому определению. Сделанное замечание следует иметь в виду при рассмотрении и остальных логических операций в настоящем параграфе.
Конъюнкция двух предикатов. Определение 19.5. Конъюнкцией п-местного предиката P(x1,..., xn), определенного на множествах M1, ..., Mn, и п-местного предиката Q(y1,..., yn), определенного на множествах N1, ..., Nn, называется новый (n + m)-местный предикат, определенный на множествах M1, ..., Mn , N1, ..., Nm, обозначаемый P(x1,..., xn)Ù Q(y1, ..., ym)(читается «P(x1,..., xn)и Q(y1, ..., ym)»), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых оба исходных предиката превращаются в истинные высказывания. Операцию конъюнкции можно применять к предикатам, имеющим общие переменные. В этом случае число переменных в новом предикате равно числу n + m — k, где п — число переменных первого предиката, т — число переменных второго предиката, k — число переменных общих для обоих предикатов. Именно таков первый из только что рассмотренных двух примеров. Более того, если оба предиката определены на одних и тех же множествах и зависят от одних и тех же переменных, то для них справедлива следующая теорема.
Теорема 19.6. Для п-местных предикатов P(x1,..., xn) и Q(x1,..., xn), определенных на множествах M1, ..., Mn, множество истинности конъюнкции P(x1,..., xn)Ù Q(x1, ..., xn)совпадает с пересечением множеств истинности исходных предикатов: (P Ù Q)+ = P+ ÇQ+ .
Следствие 19.7. Конъюнкция двух предикатов тождественно истинна тогда и только тогда, когда оба данных предиката тождественно истинны.
Следует отметить, что в предикаты P (x1,..., xn)и Q (x1,..., xn), о которых идет речь в теореме 19.6, некоторые предметные переменные могут в действительности не входить, т.е., как говорят, быть фиктивными. Это нужно понимать так, что значение истинности высказывания, в которое превращается данный предикат, не зависит от того, какие предметы подставляются вместо таких (фиктивных) переменных. При решении систем уравнений и неравенств данная ситуация встречается часто.
Дизъюнкция двух предикатов. Определение 19.8. Дизъюнкцией п-местного предиката P (x1,..., xn), определенного на множествах M1, ..., Mn, и m-местного предиката Q(y1,..., yn), определенного на множествах N1,...,Nm называется новый (n + m)-местный предикат, определенный на множествах M1, ..., Mn , N1, ..., Nm , обозначаемый P(x1,..., xn)Ú Q(y1, ..., ym)(читается «P(x1,..., xn)или Q(y1,..., yn)»), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых в истинное высказывание превращается по меньшей мере один из исходных предикатов. Операцию дизъюнкции, как и операцию конъюнкции, можно применять, в частности к предикатам, имеющим общие переменные. Например, дизъюнкцией двух одноместных предикатов «х — четное число» и «х — простое число», определенных на N, является одноместный предикат, определенный на N: «х — четное или простое число». Дизъюнкцией одноместных предикатов x ¹ 0» и « y ¹ 0», определенных на R, является двухместный предикат «(x ¹ 0)Ú (y ¹ 0)», определенный на R2. Следующая теорема аналогична теореме 19.6.
Теорема 19.9. Для п-местных предикатов P(x1,..., xn)и Q (x1,..., xn), определенных на множествах M1, ..., Mn, множество истинности дизъюнкции P(x1,..., xn)Ú Q(x1, ..., xn)совпадает с объединением множеств истинности исходных предикатов: (P Ú Q)+ = P+ ÈQ+
Следствие 19.10. Дизъюнкция двух предикатов есть выполнимый предикат тогда и только тогда, когда по меньшей мере один из данных предикатов выполним.
Следствие 19.11. Дизъюнкция двух предикатов тождественно ложна тогда и только тогда, когда оба данных предиката тождественно ложны.
Свойства отрицания, конъюнкции и дизъюнкции.После введения трех операций над предикатами возникают вопросы: как они влияют на равносильность предикатов и каковы закономерности образования с помощью этих операций равносильных предикатов? Аналогичны вопросы для следования предикатов. Ответ дает следующая теорема.
Теорема 19.12. Если во всех формулах теоремы 3.2 под Р, Q, R понимать предикаты, определенные на соответствующих множествах, знак о всюду заменить знаком Û, а знак ® — знаком Þ, то получим верные утверждения о предикатах.
Доказательство.Рассмотрим, например, вторую из формул д) теоремы 3.2. Она превращается в следующее утверждение: (P Ú (Q Ù R)) Û ((P Ú Q) Ù (P Ú R)), означающее равносильность предикатов PÚ (QÙ R) и (PÚ Q) Ù (PÚ R) независимо от предикатов Р, Q, R. Проверим, верно ли данное утверждение. В самом деле, каждый из двух предикатов при любой подстановке вместо предметных переменных конкретных предметов из соответствующих множеств превращается в такое высказывание, которое на основании тавтологии из теоремы 3.2, д имеет одинаковые значения истинности. На основании определения равносильности предикатов это и означает, что данные предикаты равносильны.
Импликация и эквивалентность двух предикатов.Импликация P (x1,..., xn)® Q (y1, ..., ym)определяется как такой предикат, что для любых предметов a1 ÎM1, a2 ÎM2, ..., an ÎMn и b1 Î N1, b2 Î N2, ..., bm Î Nm высказывание P (a1,..., an)® Q (b1,...,bm)является импликацией высказываний P(a1,..., an)и Q(b1,..., bm). Аналогично определяется эквивалентность двух предикатов. Нетрудно проверить, что импликация двух предикатов, зависящих от одних и тех же переменных, есть тождественно истинный предикат тогда и только тогда, когда ее заключение является следствием посылки, а эквивалентность тождественно истинна, если и только если исходные предикаты равносильны. Свойства этих операций над предикатами, подобно свойствам операций отрицания, конъюнкции и дизъюнкции над предикатами, получаются из соответствующих тавтологий.
Квантор общности.Известно, что для превращения одноместного предиката в высказывание нужно подставить вместо его переменной какой-нибудь конкретный предмет из области задания предиката. Имеется еще один способ для такого превращения — это применение к предикату операций связывания квантором общности или квантором существования. Каждая из этих операций ставит в соответствие одноместному предикату некоторое высказывание, истинное или ложное в зависимости от исходного предиката.
Определение 20.1. Операцией связывания квантором общности называется правило, по которому каждому одноместному предикату P(x), определенному на множестве М, сопоставляется высказывание, обозначаемое ("x)(P(x)) (читается: «для всякого [значения] х Р(х) [истинное высказывание]»), которое истинно в том и только в том случае, когда предикат Р(х) тождественно истинен, и ложно в противном случае,
При чтении высказывания ("x)(P(x)) слова в квадратных скобках могут опускаться. Высказывание ("x)(P(x)) называется универсальным высказыванием для предиката Р(х). Символ " происходит от первой буквы англ. all — «все». Сам символ ("x) также называют квантором общности по переменной х. В выражении ("x)(P(x)) переменная х уже перестает быть переменной в обычном смысле этого слова, т. е. вместо нее невозможно подставлять какие бы то ни было конкретные значения. Считают, что переменная х связанная, кажущаяся или немая. Такая ситуация уже встречалась в математике: переменные могут быть связаны не только квантором. Так, связанными являются переменные в следующих выражениях:
Это означает, что каждое из приведенных выражений не зависит от связанных переменных, т. е. сущность выражения не изменится, если связанную переменную обозначить любой другой буквой. Так, первое из трех выражений вне зависимости от переменной равно 2, второе равно 0, а третье — действительная полупрямая [0,+ ¥]. Если одноместный предикат P(x) задан на конечном множестве M = {a1, ..., am}, то нетрудно понять, что высказывание ("x)(P(x)) эквивалентно (имеет то же логическое значение) конъюнкции P (a1) Ù… Ù P (an). В самом деле, по определению 20.1 истинность высказывания ("x)(P(x)) означает, что предикат тождественно истинен, т.е. каждое из высказываний P(a1), ..., P (an), в которые этот предикат превращается, истинно. Последнее равносильно истинности конъюнкции P(a1) Ù… Ù P (a)n. Следовательно, для предикатов, заданных на конечном множестве, операция связывания квантором общности может быть выражена через конъюнкцию. Для предикатов, заданных на бесконечном множестве, такого сделать нельзя, и в этом случае операция связывания квантором общности является существенно новой. Можно подметить еще одну особенность операции связывания квантором общности по сравнению с операциями из предыдущего параграфа. Те операции ставили в соответствие одному или двум предикатам новый предикат, а операция связывания квантором общности сопоставляет предикату высказывание. На это можно сказать следующее. Во-первых, каждое высказывание для достижения большей общности сейчас и в дальнейшем можно рассматривать как предикат, содержащий 0 предметных переменных, т.е. как нульместный предикат. Во-вторых, мы пока применяли квантор общности лишь к одноместным предикатам. Переходим к рассмотрению вопроса о применении операции связывания квантором общности к предикатам с любым числом предметных переменных; такая операция предстанет операцией в полном смысле слова: предикатам она будет сопоставлять предикаты.
Определение 20.2. Операцией связывания квантором общности по переменной x1называется правило, по которому каждому п-местному ( n ³ 2) предикату ( ) P x1, ..., xn , определенному на множествах M1, ..., Mn ставится в соответствие новый (n -1)-местный предикат, обозначаемый ("x)(P(x1, a2, ..., an))(читается: «для всех x1 P (x1, ..., xn)»), который для любых предметов a2 ÎM2, ..., an ÎMn превращается в высказывание ("x)(P (x1, a2, ..., an)), истинное в том и только в том случае, когда одноместный предикат P(x1,a2 ,..., xn), определенный на множестве M1 тождественно истинен, и ложное в противном случае Заметим в заключение, что к (n -1)-местному предикату ("x)(P (x1, a2, ..., an)), зависящему от переменных x2,...,xn можно снова применить операцию связывания квантором общности по одной из свободных переменных. В результате получится (n — 2)-местный предикат и т. д.
Квантор существования.Как и в предыдущем пункте, начнем рассмотрение с операции связывания квантором существования, применяемой к одноместному предикату.
Определение 20.3. Операцией связывания квантором существования называется правило, по которому каждому одноместному предикату P(x), определенному на множестве М, ставится в соответствие высказывание, обозначаемое ($x)(P(x)) (читается: «существует [значение] х, такое, что Р(х) [истинное высказывание]»), которое ложно в том и только в том случае, когда P(x) тождественно ложен, и истинно в противном случае. Подобно выражению ("x)(P(x)), в выражении ($x)(P(x)) переменная х также перестает быть переменной в обычном смысле слова: это — связанная переменная.
Определение 20.4. Операцией связывания квантором существования по переменной x1 называется правило, по которому каждому п-местному ( n ³ 2) предикату ( ) P x1, ..., xn , определенному на множествах M1, ..., Mn, ставится в
соответствие новый (n -1)-местный предикат, обозначаемый ($x1)(P(x1, ..., an)), определенный на множестве M1, тождественно ложен, и истинное в противном случае. Заметим в заключение, что к (n -1)-местному предикату ($x1) (P(x1,...,an)), зависящему от переменных x2, ..., xn , можно снова применить одну из операций квантификации — квантор общности или квантор существования по одной из свободных переменных. В результате получим (n — 2)-местные предикаты.