Consider the following Datalog knowledge base:
13. child(X,Y) => parent(Y,X).
14. parent(X,Y) ^ male(X) => father(X,Y).
15. parent(X,Y) ^ female(X) => mother(X,Y).
15. child(X,Y) ^ female(X) => daughter(X,Y).
16. child(X,Y) => descendant(X,Y)
17. child(X,Y) ^ descendant(Y,Z) => descendant(X,Z).
Combining rule 13 with fact 1 under the substitution X=charles Y=elizabeth gives the new factYou should not trace through the algorithms given in pseudo-code in the class notes.)
You should trace paths that do not lead to a solution as well as those that do. Assume that backward chaining is executed in Prolog order; that is, subgoals are satisfied in sequence from left to right in depth-first order; rules are considered in the order they are listed above. You should show how subgoals are created from goals and rules but you need not trace the detailed algorithms. For example, given the goal "daughter(X,elizabeth)" your answer would have the following form:
Goal G0: daughter(X,elizabeth) matches rule 15 creating two subgoals: Goals G1: child(X,elizabeth) and G2: female(X). Goal G1: child(X,elizabeth) matches fact 1 under binding X=charles. Succeeds Goal G2: female(charles) fails. Return to G1. Goal G1: child(X,elizabeth) matches fact 3 under binding X=anne. Succeeds Goal G2: female(anne) matches fact 9. Succeeds Goal G0 succeeds with X=anne.