правил. Первое правило будет определять непосредственных (ближайших) предков, а второе - отдаленных. Будем говорить, что некоторый является отдаленным предком некоторого Z, если между X и Z существует цепочка людей, связанных
Рис. 1. 5. Пример отношения предок:
(а) X -
между собой отношением родитель-ребенок, как показано на рис.1.5. В нашем примере на рис. 1.1 Том - ближайший предок Лиз и отдаленный предок Пат.
Первое правило простое и его можно сформулировать так:
Для всех 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.
Предложение Пролога, имеющее тот же смысл,
