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.

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

Problem 2

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

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.