ДОКАЗАТЕЛЬСТВО ТЕОРЕМ НА ОСНОВЕ ПРИНЦИПА РЕЗОЛЮЦИИ

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

Доказательство теорем на основе принципа резолюции было изобретено в середине 60-х годов, и тогда казалось, что тем самым решена и проблема вывода. Во второй полови­не 60-х годов многие работали над применением принципа резолюции к таким задачам, как разработка диалоговых систем, автоматическое составление программ и т. п. (Ти­пичным примером такого подхода может служить работа [Green, 1969].) Однако по причинам, о которых будет ска­зано ниже, все эти проекты потерпели провал, и сейчас, по-видимому, можно утверждать, что лишь немногие спе­циалисты в области ИИ все еще верят, что доказательство теорем на основе принципа резолюции позволит решить проблему вывода умозаключений.

Общая идея принципа резолюции состоит в том, чтобы свести все высказывания к специальной форме, называемой дизъюнктивной нормальной формой (clause form). Выраже­ние в дизъюнктивной форме (clause) — это просто список предикатов, причем считается, что они соединены связкой ИЛИ, и перед каждым из них допустимо отрицание. Так, уже упомянутое правило вывода "из А ИМПЛИЦИРУЕТ В и А следует В" представимо в форме:

НЕ: + ИЛИ В

В

где НЕ (А) и А взаимно уничтожаются.

Приведение высказываний к дизъюнктивной форме.

Можно доказать, что каждое высказывание ИППП предста­вимо в дизъюнктивной форме, но соответствующее доказа­тельство мы опускаем. Вместо этого мы покажем на простом примере, каким образом высказывание можно привести к дизъюнктивной форме. Мы начнем с высказывания, пример­но соответствующего утверждению о том, что все люди владеют собаками:

ДЛЯ ЛЮБОГО (х) (СУЩЕСТВУЕТ (у) (ЧЕЛОВЕК (х) ИМПЛИЦИРУЕТ (СОБАКА (у) И ВЛАДЕЕТ (х, у)))).

Первый шаг достаточно нетривиален: требуется заме­нить все кванторы существования так называемыми "функ­циями Сколема^и. Чтобы получить общее представление о функцияхСколема, попробуем разобраться, что, в сущности, означает приведенное высказывание. Как было указано, мы хотим выразить мысль "Все люди владеют собаками⁴⁴. Мы можем выразить эту мысль и несколько иначе, следующим образом: ’’Каждому человеку может быть сопоставлена со­бака, которой он владеет¹¹. Введем функцию ’’СОВАКА- ЧЕЛОВЕКА“ (она является функцией Сколема). Если а — человек, то значением функции СОБАКА-ЧЕЛОВЕКА (а) будет та собака, которой владеет а. В соответствии с этим рассматриваемое высказывание представимо в форме:

ДЛЯ ЛЮБОГО (х) (ЧЕЛОВЕК (х) ИМПЛИЦИРУЕТ (СОБАКА (СОБАКА-ЧЕЛОВЕКА (х)) и ВЛАДЕЕТ (х, СОБАКА-ЧЕЛОВЕКА (х)))).

Это высказывание имеет форму Сколема, оно означает ’’Ес­ли х — человек, то значением функции СОБАКА-ЧЕЛО­ВЕКА (х) является та собака, которой этот человек вла­деет".

Последующие шаги приведения высказывания к дизъ­юнктивной форме довольно просты. Отметим, что на данной стадии все переменные (в нашем случае переменная ”х“) связаны квантором всеобщности, поскольку мы заменили все кванторы существования функциями Сколема. Поэтому мы можем опускать квантор всеобщности, предполагая его наличие перед каждым высказыванием. Получаем:

ЧЕЛОВЕК (х) ИМПЛИЦИРУЕТ (СОБАКА (СОБАКА- ЧЕЛОВЕКА (х)) И ВЛАДЕЕТ (х, СОБАКА-ЧЕЛОВЕКА

(х))).

НЕ (ЧЕЛОВЕК (х)) ИЛИ (СОБАКА (СОБАКА-ЧЕЛО­ВЕКА (х)) и ВЛАДЕЕТ (х, СОБАКА-ЧЕЛОВЕКА (х))).

На этой стадии высказывание имеет общий вид А ИЛИ (ВИС). Заменим это высказывание на два отдельных выска­зывания: А ИЛИ В и А ИЛИ С. (Читателю следует убедить­ся самостоятельно, что этим мы не изменили первоначаль­ный смысл высказывания.) В результате получаем два вы­сказывания:

(8) НЕ (ЧЕЛОВЕК (х)) ИЛИ СОБАКА(СОБАКА-ЧЕ- ЛОВЕКА (х))

(9) НЕ (ЧЕЛОВЕК (х)) ИЛИ ВЛАДЕЕТ (х, СОБАКА- ЧЕЛОВЕКА (х))

Грубо говоря, в (8) утверждается, что если х — человек, то значением функции СОБАКА-ЧЕЛОВЕКА (х) будет собака, а в (9) — что этой собакой владеет человек. Оба высказывания — (8) и (9) — имеют дизъюнктивную форму.

Использование принципа резолюции. Теперь, когда наше высказывание приведено к дизъюнктивной форме, легко дать примеры доказательств. Пусть нам известно, что Джон — человек:

(10) ЧЕЛОВЕК(ДЖОН)

Мы задаем вопрос: ’’Владеет ли Джон чем-нибудь?'*.

(11) СУЩЕСТВУЕТ (у) (ВЛАДЕЕТ(ДЖОН, у))

Чтобы ответить на этот вопрос, используя принцип резо­люции, мы предполагаем, что ответом на него является ”нет“, а затем пытаемся показать, что такой ответ приводит к про­тиворечию. Для доказательства противоречия мы исполь­зуем "пустой дизъюнкт“ (null clause). Это означает, что с помощью принципа резолюции мы постоянно приводим предложения к взаимному уничтожению: так, если мы до­кажем, что А — истинно и (НЕ А) — тоже истинно, то мы можем уничтожить А и НЕ А, получив ( ,), или пустой дизъюнкт. Поясним это на примере вывода (11). Отрицание

(11) имеет вид:

НЕ (СУЩЕСТВУЕТ (у) (ВЛАДЕЕТ (ДЖОН, у))).

Однако это высказывание представлено не в дизъюнктивной форме, в частности потому, что в нем имеется квантор су­ществования. Для приведения высказывания к дизъюнктив­ной форме используем правило (5), согласно которому

ДЛЯ ЛЮБОГО (х) (Р (х)) — то же самое, что НЕ (СУ­ЩЕСТВУЕТ (х) (НЕ (Р (х)))).

ДЛЯ ЛЮБОГО (у) (НЕ (ВЛАДЕЕТ (ДЖОН, (у)))) Снятием квантора всеобщности получаем (12):

(12) НЕ (ВЛАДЕЕТ (ДЖОН, (у)))

Теперь мы можем ’’резольвировать" (resolve) (12) и (9), то есть уцичтожить в них предложения вида А и НЕ А:

(9) НЕ (ЧЕЛОВЕК (х)) ИЛИ ВЛАДЕЕТ (х, СО­БАКА-ЧЕЛОВЕКА (х))

(12) НЕ (ВЛАДЕЕТ (ДЖОН, у))

Имея х = ДЖОН и СОБАКА-ЧЕЛОВЕКА (ДЖОН) = у, можно уничтожить два предложения с предикатом ВЛА­ДЕЕТ, в результате чего получаем (13):

(13) НЕ (ЧЕЛОВЕК (ДЖОН))

Таким образом, (13) — это то, что остается от (9) после унич­тожения предложения с ВЛАДЕЕТ и замены х на ДЖОН. Если теперь мы резольвируем (13) и (10), то получим нуле­вой дизъюнкт:

(13) НЕ (ЧЕЛОВЕК (ДЖОН))

(10) ЧЕЛОВЕК (ДЖОН)

( )

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

Ответ на пять вопросов. Теперь, после краткого экскур­са в область ИППП, попытаемся выяснить, как может по­мочь ИППП при ответе на пять вопросов, сформулирован­ных в начале статьи.

СЕМАНТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ. Может ли ИППП задать нужные нам предикаты? По существу, не может. Как мы видели, ИППП допускает использование любых предикатов, которые мы выберем, накладывая на них лишь немногие ограничения. Так, ИППП не дает рекомендаций относительно того, следует ли иметь в семан­тическом представлении предикат ПРОДАВАТЬ (w, х, у, z), означающий, что w дал х у‘у за z, или надо разбивать ПРОДАВАТЬ на более мелкие семантические элементы. Один из возможных способов разбиения предложен Р. Шен­ком (см. статью Скрэгга в наст, сб.):

(14) ПЕРЕДАВАТЬ (w, w, х, у) (w являлся деятелем в передаче х от себя к у)

(15) ПЕРЕДАВАТЬ (у, у, z, w) (у дает z w) КАУЗИРОВАТЬ ((14), (15))

((14) и (15) взаимообусловлены) КАУЗИРОВАТЬ ((15), (14))

(Строго говоря, два высказывания с предикатом КАУЗИРО­ВАТЬ не являются правильными выражениями ИППП, однако их легко преобразовать в правильные выражения.) Итак, единственный ответ, который дает ИППП, состоит в том, что полезно использовать такие единицы, как И, ИЛИ и НЕ, но в остальных отношениях ИППП ничем не помогает исследователю.

ПРИМЕНЕНИЕ УМОЗАКЛЮЧЕНИЙ. Какие реко­мендации относительно того, когда и каким образом выво­дить умозаключения, дает ИППП? На этот вопрос трудно ответить однозначно, поскольку здесь возможна опреде­ленная вариативность, однако общая идея, вытекающая из ИППП, состоит в том, что вывод умозаключений можно начинать только при поступлении конкретного вопроса. На данном этапе изложения это ограничение не кажется важ­ным, однако несколько позже мы увидим, что оно весьма существенно.

ОРГАНИЗАЦИЯ. Как мы находим место хранения нужных нам фактов в ИППП? На этот вопрос мы вообще не получаем никакого ответа. Доказывая, что Джон чем- либо владеет, мы не объяснили, почему мы используем имен­но данные сведения, а не какие-то другие. Причина этого состоит в том, что ИППП вообще и доказательство теорем на основе принципа резолюции, в частности, весьма далеки от этой темы. В действительности этот вопрос очень важен, и к нему мы скоро вернемся.

МЕХАНИЗМ ВЫВОДА УМОЗАКЛЮЧЕНИЙ. Пред­положим, что мы каким-то образом нашли нужные нам фак­ты. Тогда помогает ли ИППП использовать их? На этот во­прос ответ, несомненно, положителен, особенно если исполь­зовать принцип резолюции. Единственный способ исполь­зования принципа резолюции состоит в выведении новых фактов с помощью операции сравнения известных фактов. Когда мы доходим до этой задачи, мы видим, что ИППП представляет собой, по преимуществу, теорию механизма вывода умозаключений.

СОДЕРЖАНИЕ. ИППП ничего не говорит о том, каки­ми именно сведениями о мире мы должны располагать. Единственная связь между ИППП и содержательными све­дениями о мире состоит в том, что некоторые факты трудно, если вообще возможно, записать на языке ИППП.

Суммируя сказанное, можно заключить, что ИППП спо­собно предложить сильный аппарат вывода умозаклю-

Чеций, но не дает почти никаких рекомен­даций относительно семантического представления. Как мы видели, основная проблема, связанная с ИППП, состоит в том, что на большинство интересующих нас во­просов это исчисление не дает ответа.