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

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

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

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

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

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

Пример.

M=N, P(x) – «число x кратно 5»;

– «Все натуральные числа кратны 5» ложно, т.е. ;

– «Существует натуральное число, кратное 5» истинно, то есть .

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

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

Пример.

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

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

2) – «Существует y, которое является делителем всякого x»;

3) – «Для всякого y существует x такое, что x делится на y»;

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

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

6) – «Для всякого x существует y такое, что x делится на y»;

7) – «Существует x такое, что для всякого y, x делится на y»;

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

Высказывания 1), 5), 7) ложны; а высказывания 2), 3), 4), 6), 8) истинны.