Question

Draw the derivation tree for the prolog query reach(a,x), where

reach(x,y) :- edge(x,y).
reach(x,y) :- reach(y,z), edge(z,x).
edge(x,y) :- edge1(x,y)
edge(x,y) :- edge1(y,x)
edge1(a,b).
edge1(b,c).

Answer 1

The derivation tree of the Prolog query 'reach(a,x)' shows that 'reach(a,b)' and 'reach(a,c)' are both true, using the provided rules and facts about edges in the graph representation.

Step-by-step explanation:

Creating a derivation tree for a Prolog query involves understanding how Prolog tries to satisfy the query by looking at the definitions of predicates and trying to match the query with the rules and facts available. The Prolog program provided defines reachability between nodes in a graph. We want to derive 'reach(a,x)', using the rules for 'reach', 'edge', and 'edge1'.

Derivation Tree:

1. 
   
3. 'reach(a,x)' is the query.
4. 
   
6. Using the rule 'reach(x,y) :- edge(x,y)'.
   
   • 
     
   • Look for 'edge(a,x)'.
   • 
     
   • 'edge(a,x)' can be derived from 'edge1(a,x)' or 'edge1(x,a)'.
   • 
     
   • From the facts, we have 'edge1(a,b)', so 'edge(a,b)' succeeds, making 'reach(a,b)' true.
   • 
     
   
   
7. 
   
9. Using the recursive rule 'reach(x,y) :- reach(y,z), edge(z,x)'.
   
   • 
     
   • Replace 'x' with 'a' and 'y' with 'x' to get 'reach(x,z), edge(z,a)'.
   • 
     
   • Now we need to satisfy 'reach(b,z)' to make 'edge(z,a)' work.
   • 
     
   • From the facts, 'edge1(b,c)' implies 'reach(b,c)' (using the non-recursive 'reach' rule), then we also have 'edge1(c,a)' from 'edge1(a,c)' due to the symmetric definition of 'edge', fulfilling 'edge(c,a)'.
   • 
     
   • This implies that 'reach(a,c)' is also true through 'reach(b,c) and edge(c,a)'.
   • 
     
   
   

Thus, the query 'reach(a,x)' can have x=b and x=c, as shown in the derivation tree that outlines these two successful branches.