Knowledge Representation & Reasoning: 20172018
Lecturer 

Degrees 
Schedule S1(CS&P) — Computer Science and Philosophy Schedule B2 (CS&P) — Computer Science and Philosophy Schedule S1 — Computer Science Schedule B2 — Computer Science Schedule S1(M&CS) — Mathematics and Computer Science 
Term 
Hilary Term 2018 (16 lectures) 
Overview
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 ontologybased technologies and the Semantic Web.
The course will also discuss logics that depart from first order logic, such as nonmonotonic logics.
Learning outcomes
 Students satisfying the prerequisites are expected to understand the fundamental principles of logicbased Knowledge Representation;
 be able to model simple application domains in a logicbased 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 logicbased 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.
Prerequisites
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.
Synopsis
PART 1: KR&R WITH PROPOSITIONAL AND FIRST ORDER LOGIC
 Introduction to knowledgebased 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
PART 2: FRAGMENTS OF FIRST ORDER LOGIC
 Description Logics as Knowledge Representation Languages
 Reasoning in Description Logics
 Lightweight description logics.
 Horn Fragments of First Order Logic. Rulebased Knowledge Representation and Reasoning
 Ontologies and Ontology Languages.
 Other Decidable Fragments of First Order Logic for Knowledge Representation
PART 3: NONMONOTONIC LOGICS
 Classical vs nonmonotonic logic. Ways to achieve nonmonotonicity.
 Stable Model Semantics
Syllabus
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. Nonmonotonic 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.