Программа:
$\text{parent(alice, bob).}$ $\text{parent(bob, carol).}$ $\text{ancestor(X,Y) :- parent(X,Y).}$ $\text{ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).}$
Запрос:
$?-\text{ancestor(alice, Who).}$
Пошагово (SLD, глубинный поиск слева направо):
1) Пробуем первый вариант правила-основы $\text{ancestor(X,Y) :- parent(X,Y).}$. Унификация с $\text{ancestor(alice, Who)}$ даёт подстановку $\{X/alice,Y/Who\}$. Требуется факт $\text{parent(alice, Who)}$. Факт $\text{parent(alice, bob)}$ соответствует, получаем первый ответ
$\{Who/bob\}$ (то есть Who = bob).
2) При запросе следующих решений Prolog откатывается и пробует второй вариант правила
$\text{ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).}$.
Унификация даёт $\{X/alice,Y/Who\}$. Нужно сначала $\text{parent(alice,Z)}$ — это даёт $\{Z/bob\}$. Теперь остаётся решить $\text{ancestor(bob, Who)}$.
3) Для $\text{ancestor(bob, Who)}$ сначала снова применяется правило-основа $\text{ancestor(X,Y):-parent(X,Y)}$. Требуется $\text{parent(bob, Who)}$, есть факт $\text{parent(bob, carol)}$, получаем второй ответ
$\{Who/carol\}$ (то есть Who = carol).
4) Дальнейший бэктрекинг: альтернатив для $\text{ancestor(bob, Who)}$ и для $\text{parent(alice,Z)}$ исчерпались (второй вариант порождает требование $\text{ancestor(carol, ...)}$, которое не выполняется), поэтому новых решений нет.
Итого ответы выдаются в порядке:
1) $Who=bob$ 2) $Who=carol$
Порядок и наличие именно этих ответов объясняются стратегией поиска Prolog (глубинный DFS, слева направо) и структурой правил (сначала прямой родитель, затем рекурсивный шаг через промежуточного предка).