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

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 отыскивает столько от­ветов, сколько потребует пользователь (в пределах возможного).