Предок(X,Z) : — родитель(X,Z)

Второе правило для предиката предок сложнее, поскольку построение цепочки отношений родитель (см. рис.4.2b) может вызвать некоторые трудности. Если длина цепочки строго фиксирована, то можно построить правило, записав в теле через запятые всю последовательность отношений, например, так:

Рис. 4.2. Пример отношения предок:

(а) X – ближайший предок Z; (б) X – отдаленный предок Z;

(в) рекурсивная формулировка отношения предок.

предок(X,Z): — родитель(X,Y₁),

родитель(Y₁,Y₂),

родитель(Y₂,Y₃),

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

Такое правило можно будет использовать только для данной цепочки и не более. Существует, однако, корректная и элегантная формулировка отношения предок, которая будет работать для предков произвольной отдаленности. Ключевая идея здесь, — определить отношение предок через него самого. Такое определение называется рекурсивным. Рис.4.2в иллюстрирует эту идею.

Для всех X и Y,

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

существует Y такой, что

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

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

Предложение Пролога, имеющее тот же смысл, записывается так: