12.7. Кванторы

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

Утверждения, содержащие кванторы существования, можно свести к утверждениям, содержащим только кванторы всеобщности, использовав для замены переменных, относящихся к квантору существования, сколемовские функции. Для этого сначала запишем в явной форме все кванторы, обозначая кванторы всеобщности и существования соответственно через Расширение на комбинации кванторов очевидно. Для доказательства утверждения, что для каждого значения х существует некоторое значение у, при котором предикат принимает значение истина, пишем

и выполняем следующий алгоритм:

(i) Составить список переменных, связанных квантором всеобщности. Сначала список пуст.

(ii) Пусть — рассматриваемое предложение и — индекс использующейся сколемовской функции Сначала положить

(iii) Удалить кванторы, начиная с самого левого и применяя в зависимости от необходимости правила (а) или

(а) Если рассматривается квантор то удалить его и добавить х к списку L.

(б) Если рассматривается квантор (), то удалить его и заменить во всем предложении С, термом

где — переменные, находящиеся в этот момент в списке Затем увеличить на 1.

Для иллюстрации возьмем предложение

Кванторы удаляются без изменения предложения Тогда Квантор заменяем во всем предложении на

Затем удаляется и С, принимает вид

Словами это можно выразить так:

Для всех значений или истинно, или существует функция от значение которой таково, что ложно при всех значениях

Отрицание предложения с кванторами требует специального изучения. Рассмотрим высказывание с квантором всеобщности:

Отрицанием его является высказывание с квантором существования:

Существует некоторое значение х, для которого истинно.

Для того чтобы осуществить отрицание высказывания, относящегося к квантору всеобщности, квантор существования заменяют на квантор всеобщности, а отрицание применяют к самому высказыванию:

Обратная операция также справедлива. Высказывание существует некоторое значение х, для которого истинно

имеет отрицание

Символически это записывается так:

Читатель, возможно, заметил, что это правило дает логическую основу для примера из разд. 12.6.1. Там мы задавали вопрос: Другая форма этого вопроса: „Существует ли некоторое место х, такое, что утверждение истинно?". Формально мы стремимся получить , или, что эквивалентно, опровергнуть . Можно продемонстрировать такое рассуждение на примере (впервые предложенном Грином (1969)), очень похожем на пример из разд. 12.6.1. Пусть предикаты Р и интерпретируются так:

Переменные х и у принимают значения из соответствующих пространств людей и мест их работы. Утверждается, что для каждого человека существует место, в котором он работает и что Джон — человек

Докажем т. е. что существует место, где работает Джон. Соответствующие предложения таковы:

Применяя правило отрицания, получаем для последнего предложения:

Применяя правила исключения кванторов к предложениям получаем

Применяя подстановку и разрешая с получаем

Пусть разрешая выводим пустое предложение Наше утверждение доказано.