Prolog Language
व्युत्पन्न पेड़

प्रमाण वृक्ष

प्रूफ ट्री (सर्च ट्री या व्युत्पत्ति ट्री भी) एक ऐसा पेड़ है जो प्रोलोग प्रोग्राम के निष्पादन को दर्शाता है। यह पेड़ प्रोलॉग में मौजूद कालानुक्रमिक बैकट्रैकिंग प्रक्रिया की कल्पना करने में मदद करता है। पेड़ की जड़ प्रारंभिक क्वेरी का प्रतिनिधित्व करती है और पसंद बिंदु होने पर शाखाएं बनाई जाती हैं। पेड़ में प्रत्येक नोड इस प्रकार एक लक्ष्य का प्रतिनिधित्व करता है। शाखाएँ केवल तब छलावा बन जाती हैं जब या तो सही / गलत (आवश्यक) लक्ष्य (ओं) के लिए सही साबित हो जाता था और प्रोलॉग में खोज बाएं-से-सही गहराई-पहले फैशन में की जाती है।

निम्नलिखित उदाहरण पर विचार करें:

% 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) लिए विफल रहता है mother_child(ellen,angie) जहाँ 'angie' 'peter' से मेल नहीं खाता है