Prolog Language
派生木

プルーフツリー

プルーフツリー（検索ツリーまたは導出ツリー）は、Prologプログラムの実行を示すツリーです。このツリーは、Prologに存在する時系列のバックトラッキングプロセスを視覚化するのに役立ちます。ツリーのルートは初期クエリを表し、選択ポイントが発生すると分岐が作成されます。したがって、ツリー内のすべてのノードが目標を表します。 true / falseが必要な（一連の）目標に対して証明され、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) ）が 'ピーター（peter）'と一致しないmother_child(ellen,angie)