12.7. Кванторы
До сих пор неявно предполагалось, что каждая переменная связана квантором всеобщности, т. е. что она может принимать любое значение из своего множества значений. Часто приходится исследовать высказывания, относящиеся к квантору существования, т. е. утверждения, что при некотором х предикат
принимает значение истина.
Утверждения, содержащие кванторы существования, можно свести к утверждениям, содержащим только кванторы всеобщности, использовав для замены переменных, относящихся к квантору существования, сколемовские функции. Для этого сначала запишем в явной форме все кванторы, обозначая кванторы всеобщности и существования соответственно через
Расширение на комбинации кванторов очевидно. Для доказательства утверждения, что для каждого значения х существует некоторое значение у, при котором предикат
принимает значение истина, пишем
и выполняем следующий алгоритм:
(i) Составить список
переменных, связанных квантором всеобщности. Сначала список
пуст.
(ii) Пусть
— рассматриваемое предложение и
— индекс использующейся сколемовской функции
Сначала положить
(iii) Удалить кванторы, начиная с самого левого и применяя в зависимости от необходимости правила (а) или
(а) Если рассматривается квантор
то удалить его и добавить х к списку L.
(б) Если рассматривается квантор (
), то удалить его и заменить
во всем предложении С, термом
где
— переменные, находящиеся в этот момент в списке
Затем увеличить
на 1.
Для иллюстрации возьмем предложение
Кванторы
удаляются без изменения предложения
Тогда
Квантор
заменяем во всем предложении на
Затем удаляется
и С, принимает вид
Словами это можно выразить так:
Для всех значений
или
истинно, или существует функция
от
значение которой таково, что
ложно при всех значениях
Отрицание предложения с кванторами требует специального изучения. Рассмотрим высказывание с квантором всеобщности:
Отрицанием его является высказывание с квантором существования:
Существует некоторое значение х, для которого
истинно.
Для того чтобы осуществить отрицание высказывания, относящегося к квантору всеобщности, квантор существования заменяют на квантор всеобщности, а отрицание применяют к самому высказыванию:
Обратная операция также справедлива. Высказывание существует некоторое значение х, для которого
истинно
имеет отрицание
Символически это записывается так:
Читатель, возможно, заметил, что это правило дает логическую основу для примера из разд. 12.6.1. Там мы задавали вопрос:
Другая форма этого вопроса: „Существует ли некоторое место х, такое, что утверждение
истинно?". Формально мы стремимся получить
, или, что эквивалентно, опровергнуть
. Можно продемонстрировать такое рассуждение на примере (впервые предложенном Грином (1969)), очень похожем на пример из разд. 12.6.1. Пусть предикаты Р и
интерпретируются так:
Переменные х и у принимают значения из соответствующих пространств людей и мест их работы. Утверждается, что для каждого человека существует место, в котором он работает
и что Джон — человек