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

Операцией связывания квантором существования называется правило, по которому каждому одноместному предикату Р(х), определенному на множестве М, сопоставляется высказывание, обозначаемое , которое ложно в том и только в том случае, когда предикат Р(х) тождественно ложен, и истинно в противном случае, то есть

Словесным аналогом квантору существования $ является: «существует», «найдется» и т.п.

Подобно выражению , в выражении переменная х также перестает быть переменной в обычном смысле этого слова: это - связанная переменная.

Если одноместный предикат Р(х) задан на конечном множестве М = {a₁, a₂, …, a_n}, то высказывание эквивалентно дизъюнкции Р(а₁)Ú Р(а₂)Ú … Ú Р(а_n).

Пример. Пусть Р(х) – предикат «х – четное число», определенный на множестве N. Дать словесную формулировку высказыванию , определить его истинность.

Решение. Исходный предикат Р(х): «х – четное число» является переменным высказыванием: при подстановке конкретного числа вместо переменной х он превращается в простое высказывание, являющееся истинным или ложным, например при подстановке числа 5 – ложным, при подстановке числа 10 – истинным. Высказывание означает «во множестве натуральных чисел N существует четное число». Поскольку множество N содержит четные числа, то высказывание истинно.

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

Выше уже было сказано, что переменная, на которую навешен квантор, называется связанной, несвязанная квантором переменная называется свободной. Выражение, на которое навешивается квантор, называется областью действия квантора и все вхождения переменной, на которую навешен квантор, в это выражение являются связанными. На многоместные предикаты можно на разные переменные навешивать различные кванторы, нельзя на одну и ту же переменную навешивать сразу два квантора.

Пример. Пусть предикат Р(х, у) описывает отношение «х любит у» на множестве людей. Рассмотреть все варианты навешивания кванторов на обе переменные. Дать словесную интерпретацию полученных высказываний.

Решение. Обозначим предикат «х любит у» через ЛЮБИТ(х, у). Предложения, соответствующие различным вариантам навешивания кванторов, проиллюстрированы на рисунках, где х и у показаны на разных множествах, что является условностью и предпринято только для объяснения смысла предложений (реальные множества переменных х и у, очевидно, должны совпадать):

1.

- «для любого человека х существует человек у, которого он любит» или «всякий человек кого-нибудь любит».

2.

- «существует такой человек у, которого любит всякий человек х».

3.

- «все люди любят всех людей».

4.

- «существует человек, который кого-то любит» .

5.

- «существует человек, который любит всех людей».

6.

- «для всякого человека существует человек, который его любит» или «каждого человека кто-то любит».

Из приведенного выше примера можно сделать вывод о том, что перестановка кванторов общности и существования меняет смысл высказывания, т.е. кванторы общности и существования не обладают в общем случае свойством коммутативности. Итак, одноименные кванторы можно менять местами, разноименные кванторы менять местами нельзя.