Problem Set 5

Assigned: Oct. 11
Due: Oct. 18

Consider the following Datalog knowledge base:

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

Rules:
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?

Answer:

Combining rule 13 with fact 1 under the substitution X->charles Y->elizabeth gives the new fact
18. parent(elizabeth,charles).

Combining rule 13 with fact 2 under the substitution X->charles Y->philip gives the new fact
19. parent(philip,charles).

Combining rule 13 with fact 3 under the substitution X->anne, Y->elizabeth gives the new fact
20. parent(elizabeth,anne).

Combining rule 13 with fact 4 under the substitution X->anne, Y->philip gives the new fact
21. parent(philip,anne).

Combining rule 13 with fact 5 under the substitution X->william, Y->charles gives the new fact
22. parent(charles,william).

Combining rule 13 with fact 6 under the substitution X->harry, Y->charles gives the new fact
23. parent(charles,harry).

Combining rule 14 with facts 19, 8 under the substitution X->philip, Y->charles gives the new fact
24. father(philip,charles).

Combining rule 14 with facts 21, 8 under the substitution X->philip, Y->anne gives the new fact
25. father(philip,anne).

Combining rule 14 with facts 22, 10 under the substitution X->charles, Y->william gives the new fact
26. father(charles,william).

Combining rule 14 with facts 23, 10 under the substitution X->charles, Y->harry gives the new fact
27. father(charles,harry).

Combining rule 15.a with facts 23, 7 under the substitution X->elizabeth, Y->charles gives the new fact
28. mother(elizabeth,charles)

Combining rule 15.a with facts 25, 7 under the substitution X->elizabeth, Y->anne gives the new fact
29. mother(elizabeth,anne)

Combining rule 15.b with facts 3, 9 under the substitution X->anne, Y->elizabeth gives the new fact
30. daughter(anne,elizabeth).

Combining rule 16 with fact 1 under the substitution X->charles, Y->elizabeth gives the new fact
31. descendant(charles,elizabeth).

Combining rule 16 with fact 2 under the substitution X->charles, Y->elizabeth gives the new fact
32. descendant(charles,philip).

Combining rule 16 with fact 3 under the substitution X->anne, Y->elizabeth gives the new fact
33. descendant(anne,elizabeth).

Combining rule 16 with fact 4 under the substitution X->anne, Y->elizabeth gives the new fact
34. descendant(anne,philip).

Combining rule 16 with fact 5 under the substitution X->william, Y->charles gives the new fact
35. descendant(william,charles).

Combining rule 16 with fact 6 under the substitution X->harry, Y->charles gives the new fact
36. descendant(harry,charles).

Combining rule 17 with facts 5 and 31 under the substitution X->william, Y->charles, Z->elizabeth gives the new fact
37. descendant(william,elizabeth).

Combining rule 17 with facts 5 and 32 under the substitution X->william, Y->charles, Z->elizabeth gives the new fact
38. descendant(william,philip).

Combining rule 17 with facts 6 and 31 under the substitution X->harry, Y->charles, Z->elizabeth gives the new fact
39. descendant(harry,elizabeth).

Combining rule 17 with facts 6 and 32 under the substitution X->harry, Y->charles, Z->elizabeth gives the new fact
40. descendant(harry,philip).

Problem 2

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

Answer A:

Goal G0: father(Q,charles) matches rule 14 under substitution X1=Q, Y1=charles
   Subgoals: G1: parent(Q,charles) and G2: male(Q).
   
   Goal G1: parent(Q,charles) matches rule 13 under substitution Y2=Q, X2=charles.
      Subgoal: G3: child(charles,Q).

      Goal G3: child(charles,Q) matches fact 1 under substitution Q=elizabeth.
      G3 succeeeds
   G1 succeeds

   G2: male(elizabeth) fails.
   Return to G3.

      Goal G3: child(charles,Q) matches fact 2 under substitution Q=philip.
      G3 succeeds
   G1 succeeds

   Goal G2: male(philip) matches fact 8, succeeds.
G0 succeeds with Q=philip.

Answer B:

Goal G0: descendant(harry,philip)

G0 matches rule 16 under substitution X1=harry, Y1=philip.
     Subgoal G1: child(harry,philip)
     
     G1 fails. Return to G0.

G0 matches rule 17 under substitution X2=harry, Z1=philip.
    Subgoals G3: child(harry,Y2), G4: descendant(Y2,philip)

    G3: child(harry,Y2) matches fact 6 with Y2=charles. Succeeds

    G4: descendant(charles,philip) matches rule 16 under substitution X3=charles, Y3=philip
        Subgoal: G5: child(charles,philip).

        G5 matches fact 2.  Succeeds.
    G4 succeeds
G0 succeeds.