next up previous contents
Next: What You Should Up: Prolog's Search Strategy Previous: A Simple Conjunction

Conjunctions and Disjunctions

We are now ready for the whole thing: let us go back to the set of rules as found in section 2.12 and some basic facts.

and consider the solution of the goal


Here is the standard AND/OR tree representation of the search space again:

and the goal succeeds.

Note that
  1. Both the subgoal healthy(jean) and woman(jean) have to succeed for the whole goal to succeed.
  2. We then return to the top level.

Now consider the top level goal of


The resolution process generates the subgoals healthy(joan) and woman(joan) from the first clause for happy/1. In all, Prolog tries three times to match healthy(joan) as there are three clauses for healthy/1. After failing healthy(joan), however, Prolog does not try to solve woman(joan) ---there is no point in doing so.

There is another way of trying to prove happy(joan) using the second clause of happy/1. The resolution process again generates subgoals --- wealthy(joan) and woman(joan)--- and wealthy(joan) fails. A third attempt is made but this founders as wise(joan) fails. Now back to top level to report the complete failure to satisfy the goal.

Now consider


as the top level goal.

Much more complicated. First, healthy(P) succeeds binding P to jim ( P/jim) but when the conjunctive goal woman(jim) is attempted it fails. Prolog now backtracksgif. It reverses along the path through the tree until it can find a place where there was an alternative solution.

Of course, Prolog remembers to unbind any variables exactly at the places in the tree where they were bound.

In the example we are using we again try to resolve the goal healthy(P) ---succeeding with P bound to jane. Now the conjunction can be satisfied as we have woman(jane). Return to top level with P bound to jane to report success. What follows is what appears on the screen:

?-  happy(P).



Prolog offers the facility to redo a goal ---whenever the top level goal has succeeded and there is a variable binding. Just type ``;'' followed by RETURN ---``;'' can be read as or. If possible, Prolog finds another solution. If this is repeated until there are no more solutions then we get the sequence of solutions:

It is worth trying to verify this.

Basically, trying to follow the behaviour of Prolog around the text of the program can be very messy. Seeing how Prolog might execute the search based on moving around the AND/OR tree is much more coherent but it requires some effort before getting the benefit.

next up previous contents
Next: What You Should Up: Prolog's Search Strategy Previous: A Simple Conjunction

Paul Brna
Mon May 24 20:14:48 BST 1999