Skip to main content

Knowledge Representation & Reasoning:  2010-2011



Schedule B2Computer Science

Schedule B2Mathematics and Computer Science

Schedule BMSc in Computer Science



Students attending this course are expected to acquire a good understanding of the logical foundations of Knowledge Representation and Reasoning as well as to become familiar with current research trends in the field. The course requires some familiarity with propositional and first order logic.

Special emphasis is placed on decidable fragments of first order logic, which are suited for Knowledge Representation. These include, for example, the logics underlying ontology-based technologies and the Semantic Web.

The course will also discuss logics that depart from first order logic, such as non-monotonic logics.

Learning outcomes

  • Students satisfying the prerequisites are expected to understand the fundamental principles of logic-based Knowledge Representation;
  • be able to model simple domains in a logic-based language;
  • understand the notion of a reasoning service;
  • master the fundamentals of the reasoning algorithms underlying current systems;
  • understand the fundamental tradeoff between representation power and computational properties of a logic-based representation language;
  • be conversant with several widely used knowledge representation languages; and
  • understand how the theoretical material covered in the course is currently being applied in practice.


Students taking this course should have completed the first year Logic and Proof course (or an equivalent course in a different institution). Students would benefit from taking the third year Computational Complexity course as well as the second year Databases course; however, this is not a requirement.






1.- Introduction

The need for formal languages for representing (machine-understandable) knowledge. Reasoning services and logic-based reasoning. High level architecture of KR&R systems.


2- Propositional Logic

Syntax and semantics of propositional logic. Notions of satisfiability, validity, and entailment. Reasoning based on model enumeration. Normal forms.


3- Reasoning in Propositional Logic

Propositional resolution. The DPLL algorithm.


4 – Representing Knowledge in First Order Predicate Logic

Limitations of propositional logic for knowledge representation. Syntax and semantics of FOL. Representation of a domain using FOL with special emphasis on the knowledge engineering aspects.


5 and 6 – Reasoning in First Order Predicate Logic

Resolution and tableaux for FOL.  Undecidability of the satisfiability and validity problems.  Fundamental tradeoff between representation power and computational properties.




7 and 8. Horn Predicate Logic (Datalog)

Datalog as a KR language. SLD resolution and backwards chaining. Bottom-up reasoning, semi-naive evaluation. Computational properties. Connection with Prolog. Horn fragment of propositional logic and its computational properties.


9.  Description Logics and the Ontology Languages for the Semantic Web

Motivation via semantic networks and frame systems. The basic description logic ALC. Relevant reasoning problems. Extensions of ALC. The vision of the Semantic Web and the ontology languages OWL and OWL 2.


10 and 11 Reasoning in Description Logics

 Tableaux-based and resolution algorithms. Tree model property. Decidability and computational properties. Relationship with first-order tableaux and resolution.


12. Sub-boolean DLs

Motivation. Sub-boolean DLs and the OWL 2 Profiles. Reasoning in Sub-boolean DLs.


13 Recapitulation

Relationships and differences between fragments of FOL discussed thus far. Relationships between various reasoning problems in different logics. Relationship with Databases.




14 Non-monotonicity

Classical vs non-monotonic logic. Ways to achieve non-monotonicity.

Defaults, autoepistemic logic and circumscription.


15 Default reasoning

Operational semantics and default extensions. Normal default theories.


16 Non-monotonic extensions to Datalog

Non-monotonic reasoning and logic programming. Adding negation to Datalog. Stable and well-founded semantics.




Representing knowledge using logic. Reasoning techniques in propositional and first order logic. Fundamental tradeoff between representation power and computational properties.  Fragments of first order logic suited for Knowledge Representation.  Ontology languages for the Semantic Web. Non-monotonic logics.

Reading list

Relevant for Part 1:


  • Knowledge Representation and Reasoning. Ronald Brachman and Hector Levesque. The Morgan Kaufmann Series in Artificial Intelligence, 2004.
  • First Order Logic and Automated Theorem Proving. Melvin Fitting. Texts in Computer Science. 1995.
  • Handbook of Knowledge Representation. Frank van Harmelen, Vladimir Lifschitz and Bruce Porter (Eds). Foundations of Artificial Intelligence, 2008.


Relevant for Part 2:


  • The Description Logic Handbook: Theory, Implementation and Applications, 2nd Edition. Franz Baader, Diego Calvanese, Deborah L. MacGuinness, and Daniele Nardi. Cambridge University Press. 2007.
  • Foundations of Semantic Web Technologies. Chapman & Hall/ CRC Textbooks in Computing. Pascal Hitzler, Markus Kroetsch, and Sebastian  Rudolph, 2009.


Relevant for Part 3:


  • Nonmonotonic Reasoning. Grigoris Antoniou. The MIT Press, 1997.
  • Bridges Between Classical and Nonmonotonic Logic. David Makinson. Texts in Computing. 2005.