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

Problem 2

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