Кванторные операции над предикатами

Пусть имеется предикат P(x), определенный на множестве M. Если а – некоторый элемент из множества M, то подстановка его вместо x в предикат P(x) превращает этот предикат в высказывание P(а). Такое высказывание называется единичным. Наряду с образованием из предикатов единичных высказываний в логике предикатов рассматривается еще две операции, которые превращают одноместный предикат в высказывание.

1. Квантор всеобщности.

Пусть P(x) – предикат, определенный на множестве M. Под выражением "x P(x) понимают высказывание, истинное, когда P(x) истинно для каждого элемента x из множества M и ложное в противном случае. Это высказывание уже не зависит от x. Соответствующее ему словесное выражение будет «Для всякого x P(x) истинно». Символ " называют квантором всеобщности.

Переменную x в предикате P(x) называют свободной (ей можно придавать различные значения из M), в высказывании "x P(x) переменную x называют связанной квантором ".

2. Квантор существования.

Пусть P(x) – предикат, определенный на множестве M. Под выражением $x P(x) понимают высказывание, которое является истинным, если существует элемент x Î M, для которого P(x) истинно, и ложным в противном случае. Это высказывание уже не зависит от x. Соответствующее ему словесное выражение будет: «Существует x, при котором P(x) истинно». Символ $ называют квантором существования. В высказывании $x P(x) переменная x связана квантором $.

Приведем пример употребления кванторов. Пусть на множестве N натуральных чисел задан предикат P(x): «Число x кратно 5». Используя кванторы, из данного предиката можно получить высказывания: "x Î N P(x) – «Все натуральные числа кратны 5»; $x Î N P(x) – «Существует натуральное число, кратное 5». Очевидно, первое из этих высказываний ложно, а второе истинно.

Ясно, что высказывание "x P(x) истинно только в том единственном случае, когда P(x) – тождественно истинный предикат, а высказывание $x P(x) ложно только в том единственном случае, когда P(x) – тождественно ложный предикат.

Кванторные операции применяются и к многоместным предикатам. Пусть, например, на множестве M задан двухместный предикат P(x,y). Применение кванторной операции к предикату P(x,у) по переменной x ставит в соответствие двухместному предикату P(x,у) одноместный предикат "x P(x,y) (или одноместный предикат $x P(x,y)), зависящий от переменной y и не зависящий от переменной x. К ним можно применить кванторные операции по переменной y, которые приведут уже к высказываниям следующих видов:



"y"x P(x,y), $y"x P(x,y), "y$x P(x,y), $y$x P(x,y).

Например, рассмотрим предикат P(x,y): «x делится на y», определенный на множестве N. Применение кванторных операций к предикату P(x,y) приводит к восьми возможным высказываниям.

1. "y"x P(x,y) – «Для всякого y и для всякого x y является делителем x».

2. $y"x P(x,y) – «Существует y, который является делителем всякого x».

3. "y$x P(x,y) – «Для всякого y существует x такой, что x делится на любое y».

4. $y$x P(x,y) – «Существует y и существует x такие, что y является делителем x».

5. "x"y P(x,y) – «Для всякого x и для всякого y y является делителем x».

6. "x$y P(x,y) – «Для всякого x существует такой y, что x делится на y».

7. $x$y P(x,y) – «Существует x и существует y такие, что y является делителем x».

8. $x"y P(x,y) – «Существует x такой, что для всякого y x делится на y».

Легко видеть, что высказывания 1, 5 и 8 ложны, а высказывания 2, 3, 4, 6 и 7 истинны.

Из рассмотренных примеров видно, что в общем случае изменение порядка следования кванторов изменяет смысл высказывания, а значит, и его логическое значение (например высказывания 3 и 8).

Рассмотрим предикат P(x), определенный на множестве M = {a1, a2, …, an}, содержащем конечное число элементов. Если предикат P(x) является тождественно истинным, то истинными будут высказывания P(a1), P(a2),…, P(an). При этом истинными будут высказывание "x P(x) и конъюнкция P(a1)& P(a2)&…&P(an).

Если же хотя бы для одного элемента ak Î M P(ak) окажется ложным, то ложными будут высказывание "x P(x) и конъюнкция P(a1)& P(a2)&…&P(an). Следовательно, справедлива равносильность



"x P(x) º P(a1)& P(a2)&…&P(an).

Нетрудно показать, что справедлива и равносильность

$x P(x) º P(a1)Ú P(a2) Ú…ÚP(an).

Отсюда видно, что кванторные операции можно рассматривать как обобщение операций конъюнкции и дизъюнкции на случай бесконечных областей.


3925028048977050.html
3925093589782139.html
    PR.RU™