Определение отношений на основе фактов

Prolog — это язык программирования для символических, нечисловых вычисле­ний. Он особенно хорошо приспособлен для решения проблем, которые касаются объектов и отношений между объектами. На рис. 1.1 приведен подобный пример: семейные отношения. Тот факт, что Том является одним из родителей Боба, можно записать на языке Prolog следующим образом: parent { torn, bob).

В данном случае в качестве имени отношения выбрано слово parent; torn и bob являются параметрами этого отношения. По причинам, которые станут понятными позже, такие имена, как tor., записываются со строчной буквой в начале. Все дерево семейных отношений, показанное на рис. 1.1, определено с помощью следующей программы Prolog:

parent (pam_r bob). parent f tom, bob). parent! torn, liz|I. parent! bob, ann). parent; bob, pat). parent! pat, jim).

Эта программа состоит из шести предложений, каждое из которых объявляет один факт об отношении parent. Например, факт parent (tom, bob) представляет собой конкретный экземпляр отношения parent. Такой экземпляр называют также связью. В целом отношение определяется как множество всех своих экземпляров.

 

Рис. 1.1. Дерево семейных от­ношений

После передачи соответствующей программы в систему Prolog последней можно задать некоторые вопросы об отношении parent, например, является ли Боб одним из родителей Пэт? Этот вопрос можно передать системе Prolog, введя его на терми­нале:?- parent! bob, pat).

Обнаружив, что это — факт, о существовании которого утверждается в програм­ме, Prolog отвечает: yes

После этого можно задать еще один вопрос: 7- parent(liz, pat).

Система Prolog ответит: no

поскольку в программе нет упоминания о том, что Лиз является одним из родителей Пэт. Система ответит также "по" на вопрос?- parent (torn, ben). поскольку в программе даже не встречалось имя Бэн.

Кроме того, системе можно задать более интересные вопросы. Например, кто яв­ляется родителями Лиз? 1- parent! X, liz).

На этот раз Prolog ответит не просто "yes" или "по", а сообщит такое значение X, при котором приведенное выше утверждение является истинным. Поэтому ответ бу­дет таковым: X= t от

Вопрос о том, кто является детьми Боба, можно сообщить системе Prolog сле­дующим образом:?- parent! bob, X).

На этот раа имеется больше одного возможного ответа. Система Prolog вначале выдаст в ответ одно решение:

Глава 1. Введение в Prolog

X — aim

Теперь можно потребовать у системы сообщить еще одно решение {введя точку с запятой), и Prolog найдет следующий ответ:

X - pat

Если после этого будут затребованы дополнительные решения, Prolog ответит "по", поскольку все решения уже исчерпаны.

Этой программе может быть задан еще более общий вопрос о том, кто является чьим родителем? Этот вопрос можно также сформулировать иным образом: Найти X и if, такие, что X является одним иэ родителей X,

Этот вопрос может быть оформлен на языке Prolog следующим образом:?- parent (х, Y).

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

X • раш

Y - bob; X «torn Y- bob; X = torn

Y = lia;

Чтобы прекратить вывод решений, достаточно нажать клавишу <Enter> вместо точки с запятой.

Этой программе, рассматриваемой в качестве примера, можно задать еще более сложный вопрос, например, спросить о том, кто является родителями родителей Джима (дедушками и бабушками). Поскольку в программе непосредственно не пре­дусмотрено использование соответствующего отношения grandparent, этот запрос необходимо разбить на следующие два этапа (рис. 1.2).

1. Кто является одним из родителей Джима? Предположим, что это - некоторый объект Y.

2. Кто является одним из родителей.' Предположим, что это - некоторый объ­ект X

Parent

/\7\ grandparent

parent /

/

Pitc. 1.2. Отношение grandparent, выраженное как композиция двух отношений parent

Подобный сложный запрос записывается на языке Prolog как последовательность двух простых:?- parent (Y, jim), parent (X, Y).

Ответ должен быть следующим: х - bob Y = pat

Часть I. Язык Prolog

Этот составной запрос можно прочитать таким образом: найти такие X и Y, кото­рые удовлетворяют следующим двум требованиям: parent (Y, jim} и parent (X, У)

Если же будет изменен порядок следования этих двух требований, то логический смысл всего выражения останется тем же: parent! X_r У) и parent(Y, jim)

Безусловно, такое же действие может быть выполнено и в программе Prolog, по­этому запрос:

?- parent! X, Y), parent С У, jim).

выдаст тот же результат.

Аналогичным образом, программе можно задать вопрос о том, кто является вну­ками Тома:

?- parent! torn, X), parent; X, Y).

Система Prolog ответит следующим образом:

х = bob Y - ann; X =bob Г = pat

Могут быть также заданы и другие вопросы, например, имеют ли Энн и Пэт об­щих родителей. Эту задачу также можно разбить на два этапа.

1. Кто является одним из родителей Энн (X)?

2. Является ли (тот же) X одним из родителей Пэт?

Поэтому соответствующий вопрос в языке Prolog выглядит следующим образом:?- parent!" X, ann), parent! х, pat).

Ответом на него является; X = bob

Рассматриваемый пример программы позволяет проиллюстрировать перечислен­ные ниже важные понятия.

• В языке Prolog можно легко определить отношение, такое как parent, задавая л-злементные кортежи объектов, которые удовлетворяют этому отношению.

• Пользователь может легко запрашивать систему Prolog об отношениях, опре­деленных в программе.

• Программа Prolog состоит из предложений. Каждое предложение оканчивается
точкой.

• Параметрами отношений могут быть (кроме всего прочего) определенные объ­екты, или константы (такие как torn и ann), а также объекты более общего ха­рактера (такие как X и Y). Объекты первого типа, применяемые в рассматри­ваемой программе, называются атомами. Объекты второго типа называются переменными,

• Вопросы к системе состоят из одной или нескольких целей. Последова­тельность целей, такая как

parent! X ann}, parent! X, pat)

означает конъюнкцию целей:

X является одним из родителей Энн и

X является одним из родителей Пэт.

Слово "цель" (goal) используется для обозначения таких вопросов потому, что система Prolog воспринимает вопросы как цели, которых необходимо достичь.

• Ответ на вопрос может быть положительным или отрицательным, в зависимо­
сти от того, может ли быть достигнута соответствующая цель или нет. В слу-

Глава 1. Введение в Prolog

чае положительного ответа считается, что соответствующая цель была дости­жимой и что цель достигнута. В противном случае цель была недостижимой и не достигнута.

• Если вопросу соответствует несколько ответов, Prolog отыскивает столько от­ветов, сколько потребует пользователь (в пределах возможного).