Prolog Language
Дерево деривации
Поиск…
Доказательство
Дерево доказательств (также дерево поиска или дерево деривации) - это дерево, которое показывает выполнение программы Prolog. Это дерево помогает визуализировать хронологический процесс обратного отслеживания, присутствующий в Prolog. Корень дерева представляет собой начальный запрос, и ветви создаются, когда возникают точки выбора. Таким образом, каждый узел в дереве представляет собой цель. Филиалы становятся только листьями, когда для истинной / ложной доказаны требуемые цели (цели), а поиск в Прологе выполняется с первого взгляда вправо-вправо .
Рассмотрим следующий пример:
% Facts
father_child(paul,chris). % Paul is the father of Chris and Ellen
father_child(paul,ellen).
mother_child(ellen,angie). % Ellen is the mother of Angie and Peter
mother_child(ellen,peter).
% Rules
grandfather_grandchild(X,Y) :-
father_child(X,Z),
father_child(Z,Y).
grandfather_grandchild(X,Y) :-
father_child(X,Z),
mother_child(Z,Y).
Когда мы сейчас запросим:
?- grandfather_grandchild(paul,peter).
следующее дерево доказательств визуализирует процесс поиска по глубине:
?- grandfather_grandchild(paul,peter).
/ \
/ \
?- father_child(paul,Z1),father_child(Z1,peter). ?- father_child(paul,Z2),mother_child(Z2,peter).
/ \ / \
{Z1=chris} {Z1=ellen} {Z2=chris} {Z2=ellen}
/ \ / \
?- father_child(chris,peter). ?- father_child(ellen,peter). ?- mother_child(chris,peter). ?- mother_child(ellen,peter).
| | | / \
fail fail fail fail(*) success
(*) не работает для mother_child(ellen,angie)
где «angie» не соответствует «peter»,