Artificial Intelligence: Problem Set 4

Assigned: Oct. 10
Due: Oct. 17

Consider the following Datalog knowledge base, which describes course prerequisites.

1. prereq(programming,os).
2. prereq(programming,algorithms).
3. prereq(discretemath,algorithms).
4. prereq(algorithms,ai).
5. prereq(ai,learning).
6. prereq(linearalgebra,learning).
7. teaches(euler,discretemath).
8. teaches(mccarthy,ai).
9. goodteacher(feynmann).
10. goodteacher(euler).
11. take(learning)

12. prereq(X,Y) => precedes(X,Y).
13. prereq(X,Y) ^ precedes(Y,Z) => precedes(X,Z).
14. precedes(U,V) ^ take(V) => take(U).
15. goodteacher(P) ^ teaches(P,C) ^ take(C) => takewith(C,P).

Problem 1

Show the results of applying forward chaining to this knowledge base. You need only show the way in which facts and rules are combined to give new facts; you need not trace through the details of the algorithms. For example,
Combining fact 1 with rule 12 with the bindings X=programming Y=os gives
Fact 16. precedes(programming,os).

Problem 2

Show the results of backward chaining from the goal G0: "takewith(A,B)". 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

Combining G0 with rule 15 under the bindings C=A, P=B, gives the subgoals
    G1: goodteacher(B).
    G2: teaches(B,A).
    G3: take(A)

    Combining G1 "goodteacher" with fact 19 under the binding A=feynmann satisfies G1

    Goal G2 "teaches(feynmann,B)" fails.
    Backtrack to G1.

    Combining G1 "goodteacher" with fact 19 under the binding A=euler satisfies G1