родитель( Y, Z).
На рис. 1.4 показано отношение сестра:
Для любых X и Y
X является сестрой Y, если
(1) у X и Y есть общий родитель, и
(2) X — женщина.
Рис. 1.4. Определение отношения сестра.
Граф на рис. 1.4 можно перевести на Пролог так:
сестра( X, Y) :-
родитель( Z, X),
родитель( Z, Y),
женщина( X).
Обратите внимание на способ, с помощью которого выражается требование "у X и Y есть общий родитель". Была использована следующая логическая формулировка: "некоторый Z должен быть родителем X и этот же самый Z должен быть родителем Y". По-другому, менее красиво, можно было бы сказать так: "Z1 - родитель X, Z2 - родитель Y и Z1 равен Z2".
Теперь можно спросить:
?- сестра( энн, пат).
Как и ожидается, ответ будет "yes" (да) (см. рис. 1.1). Мы могли бы заключить отсюда, что определенное нами отношение сестра работает правильно. Тем не менее в нашей программе есть маленькое упущение, которое обнаружится, если задать вопрос: "Кто является сестрой Пат?"
?- сестра( X, пат).
Система найдет два ответа, один из которых может показаться неожиданным:
X = энн;
X = пат
Получается, что Пат — сестра себе самой?! Наверное, когда мы определяли отношение сестра, мы не имели этого ввиду. Однако ответ Пролога совершенно логичен, поскольку он руководствовался нашим правилом, а это правило ничего не говорит о том, что, если X — сестра Y, то X и Y не должны совпадать. Пролог (с полным правом) считает, что X и Y могут быть одним и тем же объектом и в качестве следствия из этого делает вывод, что любая женщина, имеющая родителя, является сестрой самой себе.
Чтобы исправить наше правило о сестрах, его нужно дополнить утверждением, что X и Y должны различаться. В следующих главах мы увидим, как это можно сделать, в данный же момент мы предположим, что отношение различны уже известно пролог-системе и что цель
различны( X, Y)
достигается тогда и только тогда, когда X и Y не равны. Усовершенствованное правило для отношения сестра примет тогда следующий вид:
сестра( X, Y) :-
родитель( Z, X),
родители( Z, Y),
женщина( X),
различны( X, Y).
Некоторые важные моменты этого раздела:
• Пролог-программы можно расширять, добавляя в них новые предложения.
• Прологовские предложения бывают трех типов: факты, правила и вопросы.
• Факты содержат утверждения, которые являются всегда, безусловно верными.
• Правила содержат утверждения, истинность которых зависит от некоторых условий.
• С помощью вопросов пользователь может спрашивать систему о том, какие утверждения являются истинными.
• Предложения Пролога состоят из головы и тела. Тело — это список целей, разделенных запятыми. Запятая понимается как конъюнкция.
• Факты — это предложения, имеющие пустое тело. Вопросы имеют только тело. Правила имеют голову и (непустое) тело.
• По ходу вычислений вместо переменной может быть подставлен другой объект. Мы говорим в этом случае, что переменная конкретизирована.
Предполагается, что на переменные действует квантор всеобщности, читаемый как "для всех…". Однако для переменных, появляющихся только в теле, возможны и другие формулировки. Например,
имеетребенка( X) :- родитель( X, Y).
можно прочитать двумя способами:
(а) Для всех X и Y,
если X — отец Y, то
X имеет ребенка.
(б) Для всех X,
X имеет ребенка, если
существует некоторый Y, такой, что
X — родитель Y.
Упражнения
1.3. Оттранслируйте следующие утверждения в правила на Прологе:
(a) Всякий, кто имеет ребенка, — счастлив (введите одноаргументное отношение счастлив).
(b) Всякий X, имеющий ребенка, у которого есть сестра, имеет двух детей (введите новое отношение иметьдвухдетей).
1.4. Определите отношение внук, используя отношение родитель. Указание: оно будет похоже на отношение родительродителя (см. рис. 1.3).
1.5. Определите отношение тетя( X, Y) через отношение родитель и сестра. Для облегчения работы можно сначала изобразить отношение тетя в виде диаграммы по типу тех, что изображены на рис. 1.3.
1.3. Рекурсивное определение правил
Давайте добавим к нашей программе о родственных связях еще одно отношение — предок. Определим его через отношение родитель. Все отношение можно выразить с помощью двух правил. Первое правило будет определять непосредственных (ближайших) предков, а второе — отдаленных. Будем говорить, что некоторый является отдаленным предком некоторого Z, если между X и Z существует цепочка людей, связанных между собой отношением родитель-ребенок, как показано на рис.1.5. В нашем примере на рис. 1.1 Том — ближайший предок Лиз и отдаленный предок Пат.
Рис. 1.5. Пример отношения предок: (а) X — ближайший предок Z; (b) X — отдаленный предок Z.
Первое правило простое и его можно сформулировать так:
Для всех X и Z,
X — предок Z, если
X — родитель Z.
Это непосредственно переводится на Пролог как
предок( X, Z) :-
родитель( X, Z).
Второе правило сложнее, поскольку построение цепочки отношений родитель может вызвать некоторые трудности. Один из способов определения отдаленных родственников мог бы быть таким, как показано на рис. 1.6. В соответствии с ним отношение предок определялось бы следующим множеством предложений:
предок( X, Z) :-
родитель( X, Z).
предок( X, Z) :-
родитель( X, Y),
родитель( Y, Z).
предок( X, Z) :-
родитель( X, Y1),
родитель( Yl, Y2),
родитель( Y2, Z).
предок( X, Z) :-
родитель( X, Y1),
родитель( Y1, Y2),
родитель( Y2, Y3),
родитель( Y3, Z).
...
Рис. 1.6. Пары предок-потомок, разделенных разным числом поколений.
Эта программа длинна и, что более важно, работает только в определенных пределах. Она будет обнаруживать предков лишь до определенной глубины фамильного дерева, поскольку длина цепочки людей между предком и потомком ограничена длиной наших предложений в определении отношения.
Существует, однако, корректная и элегантная формулировка отношения предок — корректная в том смысле, что будет работать для предков произвольной отдаленности. Ключевая идея здесь — определить отношение предок через него самого. Рис 1.7 иллюстрирует эту идею:
Для всех 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).
