Problem Set 3

Assigned: Sept. 24
Due: Oct. 1.

Consider the following Datalog knowledge base:

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

Rules:
13. parent(X,Y) ^ parent(Y,Z) => grandparent(X,Z).
13. grandparent(X,Y) ^ male(X) => grandfather(X,Y).
14. grandparent(X,Y) ^ female(X) => grandmother(X,Y).
15. parent(X,Y) => ancestor(X,Y).
16. parent(X,Y) ^ ancestor(Y,Z) => ancestor(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 facts 1 and 5 under the substitution X=philip, Y=charles, Z=william gives the new fact
17. grandparent(philip,william).
You should not trace through the algorithms given in pseudo-code in the class notes.)

Solution

(NOTE: The above lists two rules 13. We will distinguish them as rules 13.A and 13.B.)

17. grandparent(philip,william) from rule 13.A with facts 1 and 5, under substitution X=philip, Y=charles, Z=william.

18. grandparent(philip,harry) from rule 13.A with facts 1 and 6, under substitution X=philip, Y=charles, Z=harry.

19. grandparent(elizabeth,william) from rule 13.A with facts 2 and 5, under substitution X=elizabeth, Y=charles, Z=william.

20. grandparent(elizabeth,harry) from rule 13.A with facts 2 and 6, under substitution X=elizabeth, Y=charles, Z=harry.

21. grandfather(philip,william) from rule 13.B with facts 17 and 8, under substitution X=philip, Y=william.

22. grandfather(philip,harry) from rule 13.B with facts 18 and 8, under substitution X=philip, Y=harry.

21. grandmother(elizabeth,william) from rule 14 with facts 19 and 7, under substitution X=elizabeth, Y=william.

22. grandmother(elizabeth,harry) from rule 14 with facts 19 and 7, under substitution X=elizabeth, Y=harry.

23. ancestor(elizabeth,charles). From rule 15 with fact 1 under substitution X=elizabeth, Y=charles.

24. ancestor(philip,charles). From rule 15 with fact 2 under substitution X=philip, Y=charles.

25. ancestor(elizabeth,anne).From rule 15 with fact 3 under substitution X=elizabeth, Y=anne.

26. ancestor(philip,anne). From rule 15 with fact 4 under substitution X=philip, Y=anne.

27. ancestor(charles,william). From rule 15 with fact 5 under substitution X=charles, Y=william.

28. ancestor(charles,harry). From rule 15 with fact 6 under substitution X=charles, Y=harry.

29. ancestor(elizabeth,william). From rule 16 with facts 1 and 27 under substitution X=elizabeth, Y=charles, Z = william.

30. ancestor(elizabeth,harry). From rule 16 with facts 1 and 28 under substitution X=elizabeth, Y=charles, Z = harry.

31. ancestor(philip,william). From rule 16 with facts 2 and 27 under substitution X=philip, Y=charles, Z = william.

32. ancestor(philip,harry). From rule 16 with facts 2 and 28 under substitution X=philip, Y=charles, Z = harry.

Problem 2

Show how backward chaining can be used to prove the goals:
(A) grandfather(philip,harry).
(B) ancestor(elizabeth,william).

Solution A

Goal G0: grandfather(philip,harry).
    Match with rule 13.B under substitution X0=philip, Y1 is harry.
    Subgoals: G1: grandparent(philip,harry), G2=male(philip)
  
    Subgoal: G1: grandparent(philip,harry)
              Match with rule 13.A under substitution X1=philip, Z1=harry.
              Subgoals: G3: parent(philip,X1), G4: parent(X1,harry).

.           Subgoal: G3: parent(philip,X1)
          Match with fact 2 under substitution X1=charles.
          G3 succeeds.

      Subgoal: G4: parent(charles,harry))
           Match with fact 6.
           G4 succeeds
      G1 succeeds

      Subgoal: G2: male(philip)     
       Match with fact 8.
     G2 succeeds
G0 succeeeds.

Solution B

Goal G0: ancestor(elizabeth,william)
    Match with rule 15 under substitution X=elizabeth, Y=william.
    Subgoal: G1: parent(elizabeth,william)

    Goal G1: parent(elizabeth,william)
    G1 fails

    Return to G0
    Match with rule 16 under substitution X1=elizabeth, Z1=william.
    Subgoals: G2 : parent(elizabeth,Y1), G3: ancestor(Y1,william)

    Subgoal: G2 : parent(elizabeth,Y1)
      Match with fact 1 under substitution Y1=charles.
      Succeeds with Y1=charles.

    Subgoal: G3: ancestor(charles,william).
      Match with rule 15 under substitution X2=charles, Y2=william.
      Subgoal: G4: parent(charles,william)

      Subgoal: G4: parent(charles,william)
         Match with fact 5.
         G4 succeeds.
     
      G3 succeeds

G0 succeeds.