?- предок( пам, 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 таким образом, чтобы она соответствовала новому определению?
1.4. Как пролог-система отвечает на вопросы
В данном разделе приводится неформальное объяснение того, как пролог-система отвечает на вопросы.
Вопрос к системе — это всегда последовательность, состоящая из одной или нескольких целей. Для того, чтобы ответить на вопрос, система пытается достичь всех целей. Что значит достичь цели? Достичь цели — это значит показать, что утверждения, содержащиеся в вопросе, истинны в предположении, что все отношения программы истинны. Другими словами, достичь цели - это значит показать, что она логически следует из фактов и правил программы. Если вопрос содержит переменные, система должна к тому же найти конкретные объекты, которые (будучи подставленными вместо переменных) обеспечивают достижение цели. Найденные конкретизации сообщаются пользователю. Если для некоторой конкретизации система не в состоянии вывести цель из остальных предложений программы, то ее ответом на вопрос будет "нет".
Таким образом, подходящей интерпретацией пролог-программы в математических терминах будет следующая: пролог-система рассматривает факты и правила в качестве множества аксиом, а вопрос пользователя — как теорему; затем она пытается доказать эту теорему, т.е. показать, что ее можно логически вывести из аксиом.
Проиллюстрируем этот подход на классическом примере. Пусть имеются следующие аксиомы:
Все люди смертны.
Сократ — человек.
Теорема, логически вытекающая из этих двух аксиом:
Сократ смертен.
Первую из вышеуказанных аксиом можно переписать так:
Для всех X, если X — человек, то X смертен.
Соответственно наш пример можно перевести на Пролог следующим образом:
смертен( X) :- человек( X). % Все люди смертны
человек( сократ). % Сократ - человек
?- смертен( сократ). % Сократ смертен?
yes (да)
Более сложный пример из программы о родственных отношениях, приведенной на рис. 1.8:
?- предок( том, пат)
Мы знаем, что родитель( боб, пат) — это факт. Используя этот факт и правило пр1, мы можем сделать вывод, что утверждение предок( боб, пат) истинно. Этот факт получен в результате вывода — его нельзя найти непосредственно в программе, но можно вывести, пользуясь содержащимися в ней фактами и правилами. Подобный шаг вывода можно коротко записать
родитель( боб, пат) ==> предок( боб, пат)
Эту запись можно прочитать так: из родитель( боб, пат) следует предок( боб, пат) на основании правила пр1. Далее, нам известен факт родитель( том, боб). На основании этого факта и выведенного факта предок( боб, пат) можно заключить, что, в силу правила пр2, наше целевое утверждение предок( том, пат) истинно. Весь процесс вывода, состоящий из двух шагов, можно записать так:
родитель(боб, пат) ==> предок( боб, пат)
родитель(том, боб) и предок( боб, пат) ==>
предок( том, пат)
Таким образом, мы показали, какой может быть последовательность шагов для достижения цели, т.е. для демонстрации истинности целевого утверждения. Назовем такую последовательность цепочкой доказательства. Однако мы еще не показали как пролог-система в действительности строит такую цепочку.
Пролог-система строит цепочку доказательства в порядке, обратном по отношению к тому, которым мы только что воспользовались. Вместо того, чтобы начинать с простых фактов, приведенных в программе, система начинает с целей и, применяя правила, подменяет текущие цели новыми, до тех пор, пока эти новые цели не окажутся простыми фактами. Если задан вопрос
?- предок( том, пат).
система попытается достичь этой цели. Для того, чтобы это сделать, она пробует найти такое предложение в программе, из которого немедленно следует упомянутая цель. Очевидно, единственными подходящими для этого предложениями являются пр1 и пр2.
Рис. 1.9. Первый шаг вычислений. Верхняя цель истинна, если истинна нижняя.
Это правила, входящие в отношение предок. Будем говорить, что головы этих правил сопоставимы с целью.
Два предложения пр1 и пр2 описывают два варианта продолжения рассуждений для пролог-системы. Вначале система пробует предложение, стоящее в программе первым:
предок( X, Z) :- родитель( X, Z).
Поскольку цель — предок( том, пат), значения переменным должны быть приписаны следующим образом:
X = том, Z = пат
Тогда исходная цель предок( том, пат) заменяется новой целью:
родитель( том, пат)
Такое действие по замене одной цели на другую на основании некоторого правила показано на рис. 1.9. В программе нет правила, голова которого была бы сопоставима с целью родитель(том, пат), поэтому такая цель оказывается неуспешной. Теперь система делает возврат к исходной цели, чтобы попробовать второй вариант вывода цели верхнего уровня предок( том, пат). То есть, пробуется правило пр2:
