Knowledge Representation & Reasoning: 20232024
Lecturer  
Degrees  Schedule C1 (CS&P) — Computer Science and Philosophy Schedule C1 — Computer Science 
Term  Hilary Term 2024 (24 lectures) 
Overview
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. We will also discuss logics that depart from first order logic, in particular, temporal and 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 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.
Synopsis
PART 1: Basic logics for KRR
 Introduction to knowledgebased 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
PART 2: Datalog
 Expressive power and computational complexity of Datalog
 Reasoning algorithms for Datalog
 Temporal reasoning in extensions of Datalog
 Existential rules as an extension of Datalog
 Nonmonotonic negation and stable model semantics
 Correspondence between Datalog and Graph Neural Networks
PART 3: Description logics
 Description Logics as Knowledge Representation Languages
 Reasoning in Description Logics
 Lightweight description logics
 Ontologies and Ontology Languages.
 Other Decidable Fragments of First Order Logic for Knowledge Representation
Syllabus
Representing knowledge using logic. Fundamental tradeoff 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. Nonmonotonic logics.
Reading list
Primary Texts:
 Evgeny Dantsin, Thomas Eiter, Georg Gottlob, Andrei Voronkov, Complexity and Expressive Power of Logic Programming, 2001
 Dingmin Wang, Przemysław Wałęga, Pan Hu, Bernardo Cuenca Grau, Practical Reasoning in DatalogMTL, 2024
 Franz Baader, Ian Horrocks, Carsten Lutz, Uli Sattler, An Introduction to Description Logic, 2017
Classics:

Stephen A. Cook, The Complexity of TheoremProving Procedures, 1971

Alan M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, 1937

Michael Gelfond and Vladimir Lifschitz, The Stable Model Semantics for Logic Programming, 1988
Supplementary List:

Serge Abiteboul, Richard Hull, and Victor Vianu, Foundations of Databases, 1995

Frank van Harmelen, Vladimir Lifschitz and Bruce Porter (Eds), Handbook of Knowledge
Representation, 2008 
Christos H. Papadimitriou, Complexity Theory, 1994

Ewe Shöning, Logic for Computer Scientists, 2008
Feedback
Students are formally asked for feedback at the end of the course. Students can also submit feedback at any point here. Feedback received here will go to the Head of Academic Administration, and will be dealt with confidentially when being passed on further. All feedback is welcome.
Taking our courses
This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses
Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.