Knowledge Representation and Reasoning 2010-2011

The module describes how knowledge can be represented symbolically and manipulated in an automated way by reasoning programs. It will be based on the following textbook: Ronald Brachman and Hector Levesque. Knowledge Representation and Reasoning. Elsevier, 2004. There are several copies in the Jubilee Library, location Q387 BRA.

Hector Levesque's on-line lecture slides based on the book
local copy

Last year web page (including previous exam papers and answers)

Lectures

• Lecture 1 (Introduction, what are knowledge based systems)
• Lecture 2: syntax of first-order logic, started on interpretations. See Levesque's slides 18-27 , textbook chapter 2.1 - 2.3.2.
• Lecture 3: semantics of first-order logic, entailment. See Levesque's slides 28-34 , textbook the rest of chapter 2.
• Lecture 4: more about entailment; how to check if entailment holds. If have time will start chapter 3, slides 35-45.
• Lecture 5: finish talking about the barber exercise . Expressing knowledge: chapter 3, slides 35-45.
  Answer to the barber exercise
• Alpine club exercise
  Answer to the Alpine club exercise
• Lecture 6: will go through the Alpine club exercise
• Lecture 7: resolution (chapter 4, slides 46-55).
  Exercise on reduction to CNF
  Answer to the propositional CNF exercise
• Lecture 8: resolution continued. Started on reduction to clausal form for first-order logic.
  Exercise on propositional resolution
  Answer to the exercise on propositional resolution
• Lecture 9 (Monday the 25th of October): first-order resolution. See slides 56-70
  Exercise 1 on resolution
  Exercise 2 on resolution: prove using resolution that there is an Alpine club member who is a climber but not a skier.
  Answer to both exercises
• Lecture 10 (Thursday the 28th of October): finish first-order resolution. Here is a summary and a summary of equality axioms .
• Lecture 11: Horn clauses, SLD derivations. Chapter 5 or Levesque's slides 79-87.
• Lecture 12: backward chaining. Procedural control of reasoning. Prolog. Chapter 6, slides 88-90 and 91-100.
• Lecture 13: forward chaining, production systems. End of chapter 5 (forward chaining algorithm), chapter 7. Slides 89, 103-118.
  As an exercise, do question 4(b) from 2008 exam
  Answers to the 2008 exam
• Lecture 14: Life cycle of a knowledge based system. Knowledge acquisition. Decision tables. Java Rules API and Jess. (SEM questionnaires response.) Lecture slides
  Exercise: question 5(b) from 2007 exam
  Answers to the 2007 exam
  Exercise: question 4(d) from 2008 exam
  Answers to the 2008 exam
• Lecture 15: Description logic. Chapter 9, slides 138-163.
  Summary of technical definitions and an exercise
  Answer to the exercise
• Lecture 16: Description logic continued.
• Lecture 16: Description logic continued: interpretations, entailment, subsumption, satisfaction, taxonomy computation. See slides 138-163. (Algorithms for subsumption and taxonomy not in the exam.)
  OWL ontology language (just for background) and a lot more readable presentation by Ian Horrocks on the latest version of OWL with translations between OWL syntax and DL syntax and diagram re presentations.
• Lecture 17 (25 November): Non-monotonic reasoning. Chapter 11, slides 178-201. Handout (also covers the next lecture). I fixed a typo in the handout in the paragraph about CWA: KB+ should include KB as well as the set of negated atoms.
• Lecture 18: same handout as for the previous lecture.
  Exercise: question 5 (a-d) in 2009 exam.
  2009 answers
  Exercise: question 6 in 2008 exam
  2008 answers
• Lecture 19: Bayesian networks. Chapter 12, slides 202-216. SET questionnaires.
  Handout with an exercise
  Answer to the exercise