101

Ответ не зависит от порядка в силу того, что система получит для вопроса дизъюнкт:

родитель(X,Y) родитель(том,X), который равносилен дизъюнкту:

родитель(том,X) родитель(X,Y). На третий вопрос система ответит

Х= боб Y = эни;

Х= боб Y = пат

Пользователь ПРОЛОГа может совершенно не знать метод резолюций. Система сама находит ответы.

§13. Введение и использование правил в ПРОЛОГе

Вкачестве расширения рассмотренной в § 12 программы на ПРОЛОГе введем отношение дети, которое обратно отношению родитель. Можно было бы определить дети тем же способом, что и родитель, т.е. представив описок:

дети (лиз, том). дети (боб, пам).

итак далее. Однако это отношение можно определить проще, использовав, тот факт, что оно обратно отношению родитель, которое уже определено. Такой способ основан на следующем логическом утверждении:

Для всех Х и Y

Y дети Х, если

Х является родителем Y.

Соответствующее прологовское предложение с тем же смыслом имеет

вид:

дети (Y,Х): - родитель (Х,Y).

(3.20)

Приведенное прологовское предложение (3.20) называется правилом. Предложение

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

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

К рассмотренной в параграфе 12 программе добавим еще предложение (3.20). Спросим полученную программу, является ли Лиз отпрыском Тома?

? - дети (лиз, том).

Предложение (3.20) на языке логики имеет вид: родитель(Х,Y) дети(Y,X).

Преобразуем последнее выражение в дизъюнкт:

102

родитель(Х,Y) дети(Y,Х).

(3.21)

Вопрос к системе преобразуется в дизъюнкт:

дети (лиз, том).

(3.22)

Из (3.21) и (3.22) получим:

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

Далее, используя предложение (дизъюнкт) (3.12) получим пустой дизъюнкт, следовательно, система ответит

YES (да).

§ 14. Рекурсивное задание правил в ПРОЛОГе

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

Первое правило простое и его можно сформулировать так:

Для всех Х и Z

X - предок Z, если

X - родитель Z.

Это переводится на Пролог в виде предложения

предок(Х,Z): - родитель(X,Z).

Второе правило сложнее. Один из способов определения отдаленных родственников задать их следующим множеством предложений

предок(X,Z):-

родитель(Х,Z).

предок(Х,Z): - родитель(X,Y), родитель(Y,Z).

предок(X,Z):-

родитель(X,Y1), родитель(Y1,Y2), родитель(Y2,Z).

--------------------------

103

предок(Х,Z):- родитель(Х,Y1),

родитель(Y1,Y2), родитель(Y2,Y3),

родитель(Y3,Z).

Эта программа длинна и, что важнее, работает только в определенных пределах. Она будет обнаруживать предков лишь до определенной глубины фамильного дерева.

Существует компактная и корректная формулировка отношения предок, которая работает на любую глубину. Ключевая идея для этого: определить отношение предок через него самого, т.е. ввести рекурсивное определение. Это определение будет следующим:

Для всех X и Z

Х- предок Z, если существует Y, такой, что

(1)Х -родитель Y и

(2)Y -предок Z.

Предложение ПРОЛОГа, имеющее тот же смысл, записывается в виде:

предок(X,Z):-

родитель(Х,Y), предок(Y,Z).

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

предок(Х,Z): - родитель(Х,Z).

предок(X,Z):-

родитель(Х,Y), (3.23)

предок(Y,Z).

Отметим, что рекурсивное задание правил проводится не единственным образом. Так предложение (3.23) можно заменить, например, на следующие

предок(X,Y): -

родитель(Х,Y).

предок(X,Z): -

предок(X,Y), предок(Y,Z).

Если к рассмотренной в параграфе 12 программе добавить предложение (3.23), то полученную программу можно, например, спросить:

«Кто потомки Пам?» На Прологе этот вопрос запишем в виде:

104

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

Система ответит

X=боб;

X=эни;

X=пат;

X=джим

Выясним как получает программа ответ. Предложения (3.23) записываются в виде:

родитель(X,Z) предок(X,Z), родитель(X,Y)&предок(Y,Z) предок(X,Z).

Преобразовав эти формулы получим:

родитель(X,Z) предок(X,Z),	(3.24)
родитель(X,Y) предок(Y,Z) предок(X,Z).	(3.25)
Вопрос к системе преобразуется к виду
предок(пам,X) ANS(X).	(3.26)

Для получения ответа используется предложения (дизьюнкты) (3.10)- (3.15) и дизъюнкты (3.24)-(3.26).

Непосредственный потомок для Пам выявится, если из (3.25) и (3.26) получить бинарную резольвенту:

родитель(пам,Z) ANS(Z).

(3.27)

Затем получим ANS(боб) как бинарную резольвенту из (3.27) и (3.10). Потомки второго уровня (внуки Пам) выявятся в результате

получения следующих резольвент

родитель(пам,Y) предок(Y,X) ANS(X),

(3.28)

которое получено из (3.25) и (3.26),

родитель(X,Y) родитель(пам,X) ANS(Y),

(3.29)

которое получено из (3.28) и (3.24),

	родитель(боб,Y)		ANS(Y),	(3.30)

получено из (3.29) и (3.10). Далее имеем: ANS(эни) -получено из (3.30) и (3.13), ANS(пат) -получено из (3.30) и (3.14).