Knowledge Representation & Reasoning: 20102011
Lecturer 

Degrees 
Schedule B2 — Computer Science 
Term 
Hilary Term 2011 (16 lectures) 
Overview
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 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
1. Introduction
The need for formal languages for representing (machineunderstandable) knowledge. Reasoning services and logicbased 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.
PART 2: FRAGMENTS OF FIRST ORDER LOGIC
7 and 8. Horn Predicate Logic (Datalog)
Datalog as a KR language. SLD resolution and backwards chaining. Bottomup reasoning, seminaive 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
Tableauxbased and resolution algorithms. Tree model property. Decidability and computational properties. Relationship with firstorder tableaux and resolution.
12. Subboolean DLs
Motivation. Subboolean DLs and the OWL 2 Profiles. Reasoning in Subboolean DLs.
13 Recapitulation
Relationships and differences between fragments of FOL discussed thus far. Relationships between various reasoning problems in different logics. Relationship with Databases.
PART 3: NONMONOTONIC LOGICS
14 Nonmonotonicity
Classical vs nonmonotonic logic. Ways to achieve nonmonotonicity.
Defaults, autoepistemic logic and circumscription.
15 Default reasoning
Operational semantics and default extensions. Normal default theories.
16 Nonmonotonic extensions to Datalog
Nonmonotonic reasoning and logic programming. Adding negation to Datalog. Stable and wellfounded 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.