Главная > Интеллектуальные системы > Искусственный интеллект (Э. Хант)
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

12.7. Кванторы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

<< Предыдущий параграф Следующий параграф >>
Оглавление