## Artificial Intelligence: Problem Set 4

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

### Problem 1

Show the results of applying forward chaining to this knowledge base.

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

### Problem 2

Show the results of backward chaining from the goal G0: "takewith(A,B)".

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