Skip to main content

Knowledge Representation & Reasoning:  2018-2019



Schedule S1(CS&P)Computer Science and Philosophy

Schedule S1Computer Science

Schedule S1(M&CS)Mathematics and Computer Science

Schedule BMSc in Computer Science



The course provides an introduction to the field. The main focus will be on decidable fragments of first order logic that are well suited for knowledge representation. We explore how such logics can be used to represent knowledge, identify relevant reasoning problems and show how these can be used to support the task of constructing suitable representations. We will also consider the computational properties of these logics, and study algorithms for solving the relevant reasoning problems. Finally, we will also discuss logics that depart from first order logic, such as non-monotonic logics.

The lectures for this course are recorded, and the recordings released at the end of each week of term. Please click here to access the recordings.

Learning outcomes

  • Students satisfying the prerequisites are expected to understand the fundamental principles of logic-based Knowledge Representation;
  • be able to model simple application 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 trade-off 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 Introduction to Formal 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.



  • Introduction to knowledge-based technologies and knowledge representation
  • Propositional Logic as a simple knowledge representation language
  • Representing Knowledge in First Order Predicate Logic
  • Limitations of Propositional and First Order Predicate Logic


  • Description Logics as Knowledge Representation Languages
  • Reasoning in Description Logics
  • Lightweight description logics.
  • Horn Fragments of First Order Logic. Rule-based Knowledge Representation and Reasoning
  • Ontologies and Ontology Languages.
  • Other Decidable Fragments of First Order Logic for Knowledge Representation


  • Classical vs non-monotonic logic. Ways to achieve non-monotonicity.
  • Stable Model Semantics


Representing knowledge using logic. Fundamental trade-off between representation power and computational properties.  Fragments of first order logic suited for Knowledge Representation. Reasoning algorithms and implementations, and how reasoning is used to support knowledge representation. Ontology languages for the Semantic Web. Non-monotonic logics.

Reading list




Primary Text

  • An Introduction to Description Logic. Franz Baader, Ian Horrocks, Carsten Lutz, Uli Sattler

Supplementary List

  • Handbook of Knowledge Representation. Frank van Harmelen, Vladimir Lifschitz and Bruce Porter (Eds). Foundations of Artificial Intelligence, 2008.
  • Foundations of Semantic Web Technologies. Chapman & Hall/ CRC Textbooks in Computing. Pascal Hitzler, Markus Kroetsch, and Sebastian  Rudolph, 2009.
  • Logic for Computer Scientists.  Uwe Schoning.  Modern Birkäuser Classics, Reprint of the 1989 edition.