Иван Братко - Программирование на языке Пролог для искусственного интеллекта

Для всех X и Z,

X — предок Z, если

существует Y, такой, что

(1) X — родитель Y и

(2) Y — предок Z.

Предложение Пролога, имеющее тот же смысл, записывается так:

предок( X, Z) :-

родитель( X, Y),

предок( Y, Z).

Теперь мы построили полную программу для отношения предок, содержащую два правила: одно для ближайших предков и другое для отдаленных предков. Здесь приводятся они оба вместе:

предок( X, Z) :-

родитель( X, Z).

предок( X, Z) :-

родитель( X, Y),

предок( Y, Z).

Рис. 1.7. Рекурсивная формулировка отношения предок.

Ключевым моментом в данной формулировке было использование самого отношения предокв его определении. Такое определение может озадачить - допустимо ли при определении какого-либо понятия использовать его же, ведь оно определено еще не полностью. Такие определения называются рекурсивными . Логически они совершенно корректны и понятны; интуитивно это ясно, если посмотреть на рис. 1.7. Но будет ли в состоянии пролог-система использовать рекурсивные правила? Оказывается, что пролог-система очень легко может обрабатывать рекурсивные определения. На самом деле, рекурсия — один из фундаментальных приемов программирования на Прологе. Без рекурсии с его помощью невозможно решать задачи сколько-нибудь ощутимой сложности.

Возвращаясь к нашей программе, можно теперь задать системе вопрос: "Кто потомки Пам?" То есть: "Кто тот человек, чьим предком является Пам?"

?- предок( пам, X).

X = боб;

X = энн;

X = пат;

X = джим

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

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

При рассмотрении рис. 1.8 следует учесть два новых момента: первый касается понятия "процедура", второй — комментариев в программах. Программа, приведенная на рис. 1.8, определяет несколько отношений — родитель, мужчина, женщина, предоки т.д. Отношение предок, например, определено с помощью двух предложений. Будем говорить, что эти два предложения входят в состав отношения предок. Иногда бывает удобно рассматривать в целом все множество предложений, входящих в состав одного отношения. Такое множество называется процедурой .

родитель( пам, боб). % Пам - родитель Боба

родитель( том, боб).

родитель( том, лиз).

родитель( бoб, энн).

родитель( боб, пат).

родитель( пат, джим).

женщина( пам). % Пам - женщина

мужчина( том). % Том - мужчина

мужчина( боб).

женщина( лиз).

женщина( энн).

женщина( пат).

мужчина( джим).

отпрыск( Y, X) :- % Y - отпрыск X, если

родитель( X, Y). % X - родитель Y

мать( X, Y) :- % X - мать Y, если

родитель( X, Y), % X - родитель Y и

женщина( X). % X - женщина

родительродителя( X, Z) :-

% X - родитель родителя Z, если

родитель( X, Y), % X - родитель Y и

родитель( Y, Z). % Y - родитель Z

сестра( X, Y) :- % X - сестра Y

родитель( Z, X),

родитель( Z, Y) % X и Y имеют общего родителя

женщина( X, Y), % X - женщина и

различны( X, Y). % X отличается от Y

предок( X, Z) :- % Правило пр1: X - предок Z

родитель( X, Z).

предок( X, Z) :- % Правило пр2: X - предок Z

родитель( X, Y),

предок( Y, Z).

Рис. 1.8. Программа о родственных отношениях.

На рис. 1.8 два предложения, входящие в состав отношения предок, выделены именами "пр1" и "пр2", добавленными в программу в виде комментариев . Эти имена будут использоваться в дальнейшем для ссылок на соответствующие правила. Вообще говоря, комментарии пролог-системой игнорируются. Они нужны лишь человеку, который читает программу. В Прологе комментарии отделяются от остального текста программы специальными скобками " /*" и " */". Таким образом, прологовский комментарий выглядит так

/* Это комментарий */

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

% Это тоже комментарий

1.6. Рассмотрим другой вариант отношения предок:

предок( X, Z) :-

родитель( X, Z).

предок( X, Z) :-

родитель( Y, Z),

предок( X, Y).

Верно ли и такое определение? Сможете ли Вы изменить диаграмму на рис. 1.7 таким образом, чтобы она соответствовала новому определению?

В данном разделе приводится неформальное объяснение того, как пролог-система отвечает на вопросы.

Вопрос к системе — это всегда последовательность, состоящая из одной или нескольких целей. Для того, чтобы ответить на вопрос, система пытается достичь всех целей. Что значит достичь цели? Достичь цели — это значит показать, что утверждения, содержащиеся в вопросе, истинны в предположении, что все отношения программы истинны. Другими словами, достичь цели - это значит показать, что она логически следует из фактов и правил программы. Если вопрос содержит переменные, система должна к тому же найти конкретные объекты, которые (будучи подставленными вместо переменных) обеспечивают достижение цели. Найденные конкретизации сообщаются пользователю. Если для некоторой конкретизации система не в состоянии вывести цель из остальных предложений программы, то ее ответом на вопрос будет "нет".

Таким образом, подходящей интерпретацией пролог-программы в математических терминах будет следующая: пролог-система рассматривает факты и правила в качестве множества аксиом, а вопрос пользователя — как теорему ; затем она пытается доказать эту теорему, т.е. показать, что ее можно логически вывести из аксиом.

Проиллюстрируем этот подход на классическом примере. Пусть имеются следующие аксиомы:

Все люди смертны.

Сократ — человек.

Теорема, логически вытекающая из этих двух аксиом:

Сократ смертен.