Problem Set 5

Assigned: Oct. 11
Due: Oct. 18

Consider the following Datalog knowledge base:

1. child(charles,elizabeth).
2. child(charles,philip).
3. child(anne,elizabeth).
4. child(anne,philip).
5. child(william,charles).
6. child(harry,charles).
7. female(elizabeth).
8. male(philip).
9. female(anne)
10. male(charles).
11. male(william).
12. male(harry).

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).

Problem 1

What new facts can be inferred using forward chaining? (You should explain how facts are combined with the rules to get new facts; e.g.
Combining rule 13 with fact 1 under the substitution X=charles Y=elizabeth gives the new fact
18. parent(elizabeth,charles).
You should not trace through the algorithms given in pseudo-code in the class notes.)

Problem 2

Show how backward chaining can be used to prove the goals:
(A) father(Q,charles).
(B) descendant(harry,philip).

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.