Assigned: Oct. 10

Due: Oct. 17

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

Facts:

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)

Rules

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

** Answer: **

Combining fact 1 with rule 12 with the bindings X=programming Y=os gives

Fact 16. precedes(programming,os).

Combining fact 2 with rule 12 with the bindings X=programming Y=algorithms gives

Fact 17. precedes(programming,algorithms).

Combining fact 3 with rule 12 with the bindings X=discretemath Y=algorithms gives

Fact 18. precedes(discretemath,algorithms).

Combining fact 4 with rule 12 with the bindings X=algorithms Y=ai gives

Fact 19. precedes(algorithms,ai).

Combining fact 5 with rule 12 with the bindings X=ai Y=learning gives

Fact 20. precedes(ai,learning).

Combining fact 6 with rule 12 with the bindings X=linearalgebra Y=learning gives

Fact 21. precedes(linearalgebra,learning).

Combining facts 2 and 19 with rule 13 with the bindings X=programming, Y=algorithms, Z=ai gives

Fact 22. precedes(programming,ai).Combining facts 3 and 19 with rule 13 with the bindings X=programming, Y=algorithms, Z=ai gives

Fact 23. precedes(discretemath,ai).Combining facts 4 and 20 with rule 13 with the bindings X=algorithms Y=ai, Z=learning gives

Fact 24. precedes(algorithms,learning).Combining facts 2 and 24 with rule 13 with the bindings X=programming Y=algorithms, Z=learning gives

Fact 25. precedes(programming,learning).Combining facts 3 and 24 with rule 13 with the bindings X=discretemath Y=algorithms, Z=learning gives

Fact 26. precedes(discretemath,learning).Combining facts 20 and 11 with rule 14 with the bindings U=ai, V=learning gives

Fact 27. take(ai).Combining facts 21 and 11 with rule 14 with the bindings U=linearalgebra, V=learning gives

Fact 28. take(linearalgebra).Combining facts 24 and 11 with rule 14 with the bindings U=algorithms, V=learning gives

Fact 29. take(algorithms).Combining facts 25 and 11 with rule 14 with the bindings U=programming, V=learning gives

Fact 30. take(programming).Combining facts 25 and 11 with rule 14 with the bindings U=discretemath, V=learning gives

Fact 31. take(discretemath).Combining facts 10, 7, and 31 with rule 15 with the bindings U=euler, C=discretemath gives

Fact 32. takewith(discretemath,euler).

** Answer: **

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 9 under the binding A=feynmann satisfies G1 Goal G2 "teaches(feynmann,B)" fails. Backtrack to G1. Combining G1 "goodteacher" with fact 10 under the binding A=euler satisfies G1 Combining G2 "teaches(euler,B)" with fact 7 under the binding B=discretemath satisfies G2. Combining G3 "take(discretemath)" with rule 14 under binding U=discretemath, gives the subgoals G4: precedes(discretemath,V). G5: take(V). Combining G4 "precedes(discretemath,V)" with rule 12 under binding X=discretemath, Y=V gives the subgoal G6: prereq(discretemath,V). Combining G6 "prereq(discretemath,V)" with fact 3 under binding V=algorithms satisfies G6. G4 is satisfied Combining G5 "take(algorithms)" with rule 14 under binding U=algorithms, gives the subgoals G7: precedes(algorithms,V1) G8: take(V1). Combining G7 "precedes(algorithms,V1)" with rule 12 under bindings X=algorithms, Y=V1 gives the subgoal G9: prereq(algorithms,V1) Combining G9 "prereq(algorithms,V1)" with fact 4 under binding V1=ai satisfies G9. G7 is satisfied Combining G8 "take(ai)" with rule 14 under binding U2=ai gives the subgoals G9: precedes(ai,V2). G10: take(V2). Combining G9 "precedes(ai,V2)" with rule 12 under X=ai, Y=V2 gives the subgoal G11: prereq(ai,V2). Combining G11 "prereq(ai,V2)" with fact 5 under the binding V2=learning satisfies G11 G9 is satisfied Combining G10 "take(learning)" with fact 11 satisfied G10 G8 is satisfied G5 is satisfied G3 is satisfied G0 is satisfied with A=discretemath, B=euler.