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

Братко Иван

 родитель( 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 таким образом, чтобы она соответствовала новому определению?

1.4. Как пролог-система отвечает на вопросы

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

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

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

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

следующие аксиомы:

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

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

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

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

Первую из вышеуказанных аксиом можно переписать так:

 Для всех X, если X — человек, то X смертен.

Соответственно наш пример можно перевести на Пролог следующим образом:

смертен( X) :- человек( X). % Все люди смертны

человек( сократ). % Сократ - человек

?- смертен( сократ). % Сократ смертен?

yes

(да)

Более сложный пример из программы о родственных отношениях, приведенной на рис. 1.8:

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

Мы знаем, что

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

 — это факт. Используя этот факт и правило пр1, мы можем сделать вывод, что утверждение

предок( боб, пат)

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

родитель( боб, пат) ==> предок( боб, пат)

Эту запись можно прочитать так: из

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

следует

предок( боб, пат)

на основании правила пр1. Далее, нам известен факт

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

. На основании этого факта и выведенного факта

предок( боб, пат)

можно заключить, что, в силу правила пр2, наше целевое утверждение

предок( том, пат)

истинно. Весь процесс вывода, состоящий из двух шагов, можно записать так:

родитель(боб, пат) ==> предок( боб, пат)

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

и 

предок( боб, пат) ==>

 предок( том, пат)

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

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

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

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

Рис. 1.9. Первый шаг вычислений. Верхняя цель истинна, если истинна нижняя.

Это правила, входящие в отношение предок. Будем говорить, что головы этих правил сопоставимы с целью.