Skip to main content

Knowledge Representation & Reasoning:  2017-2018



Schedule S1(CS&P)Computer Science and Philosophy

Schedule B2 (CS&P)Computer Science and Philosophy

Schedule S1Computer Science

Schedule B2Computer Science

Schedule S1(M&CS)Mathematics and Computer Science

Schedule B2Mathematics and Computer Science

Schedule BMSc in Computer Science



MSc students will be assessed by invigilated exam lasting approximately 3 hours in week 0 of TT.

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




  • Introduction to knowledge-based technologies and knowledge representation
  • Propositional Logic as a simple knowledge representation language
  • Reasoning in Propositional Logic
  • Representing Knowledge in First Order Predicate Logic
  • Reasoning in 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. 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.