Back to practice exercises.
1: Background Reading
2: Learning Goals
 Define/read/write/trace/debug the BottomUp proof procedure
 Define/read/write/trace/debug the TopDown proof procedure
 Define/read/write/trace/debug the TopDown proof procedure as a search problem
 Represent simple domains in Datalog
 Apply TopDown proof procedure in Datalog
3: Directed Questions
 If KB is a knowledge base and g is a conjunction of atoms, what is meant by KB  g? [solution]
 Given a proof procedure, a knowledge base KB and a conjunction of atoms g, what is
meant by KB = g? [solution]
 Define what it means for a proof procedure to be sound. [solution]
 Define what it means for a proof procedure to be complete. [solution]
 What is the key idea of the bottomup proof procedure? [solution]
 How do you know when you have completed a successful derivation using the bottomup
proof procedure? [solution]
 How can the bottomup proof procedure show that there is no successful derivation? [solution]
 What is the key idea of the topdown proof procedure? [solution]
 How do you know when you have completed a successful derivation using the topdown
proof procedure? [solution]
 Give an example of an admissible heuristic for topdown search. [solution]
4: Exercise: Datalog
A university has asked you to write a program to help them determine whether or not to accept
students who have applied for admission. There are 3 basic pathways for a student to be accepted.
If a student is returning to the university after a time away and is in good academic standing
with no outstanding fees, they are accepted. Students who submit a complete application and
are qualified are also accepted. Students are qualified if they have high SAT scores as well as
good highschool transcripts. The university also has a legacy program, wherein children of
former graduates are qualified (though these student must still submit a complete application).
For brevity, let's only talk about 3 individuals: Sam is a former graduate and Chris is his son.
Chris has good highschool transcripts and he submitted a complete application. Laura is a
returning student in good academic standing.
 Give the knowledge base representing this problem, using unary predicates accepted,
returning, goodStanding, clearBalance, appComplete, qualified, legacyStudent,
highSAT, goodHS, and graduate, as well as the binary predicate child. The university
admissions officials should be able to provide queries such as accepted(chris) and get a
true or false answer. [solution]
 Load your KB in the deduction tool, and run the topdown derivation of the query accepted(chris) applied to your KB. [solution]
 Now run the query accepted(laura) and examine one of the failing topdown derivations of the query. [solution]
5: Learning Goals Revisited
 Define/read/write/trace/debug the BottomUp proof procedure
 Define/read/write/trace/debug the TopDown proof procedure
 Define/read/write/trace/debug the TopDown proof procedure as a search problem
 Represent simple domains in Datalog
 Apply TopDown proof procedure in Datalog
