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

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

- квантор существования по переменной

Пример

Имеем два одноместных предиката определенных на множестве N:    и   

Первый предикат – тождественно ложный, следовательно   –ложное высказывание.

Второй предикат – выполнимый, следовательно   – истинное высказывание.

Замечание

Если одноместный предикат P(x) задан на конечном множестве то высказываниеэквивалентно дизъюнкции.

Действительно, по определению    – высказывание имеет значение 0 (т.е. ложно), еслиP(x) – тождественно ложный предикат, т.е. любое из высказываний , в которое может превратиться предикат, ложно. А это означает ложность дизъюнкции.

В выражении , так же как и в, переменнаяx перестает быть переменной в обычном смысле слова: это – связанная переменная.

Предикат от n переменных и квантор существования

Определение. Операцией связывания квантором существования по переменной называется правило, по которому каждому n-местному предикату (n≥2) , определенному на множествах, сопоставляется новый (n-1)-местный предикат, обозначаемый , который для любых предметов, превращается в высказывание, ложное тогда и только тогда, когда одноместный предикат, определенный на множестветождественно ложен и истинен в противоположном случае, то есть:

Пример 1. Двухместный предикат , определенный наR. Применим к нему квантор существования по переменной x.

Получим одноместный предикат , зависящий от переменной y. Этот предикат превращается в истинное высказывание, если вместо него подставить конкретное число, т.е. является тождественно истинным предикатом.

Пример 2. Двухместный предикат , определенный наR. Применение квантора существования по любой переменной даст одноместный предикат, который будет тождественно ложным:

Замечание

К (n-1)-местному предикату , , можно снова применить квантор общности или квантор существования. Получим (n-2)-местные предикаты:

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

К этим предикатам опять применяем кванторные операции по переменной y, которые приведут к нульместному предикату (высказыванию) следующих видов:

Например, предикат , определенный на множествеN.

Применение кванторных операций к предикату P(x, y) приводит к 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» (истинное высказывание)

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