CS3411
Advanced Knowledge Based Systems
19992000 session
Lecturer: Enrico Franconi
Assessment: 2 hours examination (75%) + an individual class exercise (25%)
Aims and objectives
By the end of this module students will have acquired a method for
designing knowledge bases and knowledge based systems and agents. The
emphasis will be on a rigorous approach to knowledge representation
and building ontologies. It is assumed that students are already
familiar with the elements of logics and artificial intelligence.
The course is divided in three major parts. The first part of the
course will review the basic concepts of classical first order
predicate logic, and will give the student the ability to model
reality using classical logic. At the end of the first part there will
be an assessed class exercise.
The second part briefly surveys the standard technologies for
ontological engineering and knowledge representation, reviewed from a
logical perspective.
The third part of the course will present the most popular logicbased
knowledge representation formalism, namely Description Logics. The
simplest Description Logic will be deeply analysed from the logical
point of view. Several extensions and uses of Description Logics will
be briefly introduced at the end.
Illustrations of practical examples will be given.
Reading List
 Main reference book:
 "Artificial Intelligence: A Modern Approach", (parts I &
III) by Stuart Russell and Peter Norvig, Prentice Hall, 1995
 Additional readings from the following collections:
 Part on propositional and first order logic (use one of the
following):
 "Logic", Schaum's Outlines by J. Nolt, D. Rohatyn, and A. Varzi,
McGrawHill, 1998
 "Introduction to Mathematical Logic", by Elliott Mendelson,
Chapman & Hall, 1997
 "Mathematical Logic", by H.D. Ebbinghaus, J. Flum, and W. Thomas,
SpringerVerlag, 1984
 "A Mathematical Introduction to Logic", by Herbert Enderton,
Academic Press, 1972
 Part on Description Logics:

H. J. Levesque and
R. J. Brachman. Expressiveness and tractability in knowledge
representation and reasoning. Computational Intelligence journal 3,
7893 (1987) [paper version available].
 B. Nebel. Reasoning and Revision in Hybrid
Representation Systems. Lecture Notes in Artificial Intelligence
422, SpringerVerlag, 1990. Chapters 1  6.
 Woods, W., Schmolze, J.,
`The KLONE Family', Computers and Mathematics with Applications,
special issue: Semantic Networks in Artificial Intelligence, Vol 25,
pp 133177, 1992 [paper version available].

Donini, F., Lenzerini,
M., Nardi, D., Schaerf, A., `Reasoning
in Description Logics', in: Principles of Knowledge Representation
and Reasoning, edited by G. Brewka; Studies in Logic, Language and
Information, CLSI Publications, pp 193238, 1996.

Brachman, R., McGuinness,
D., PatelSchneider, P., Resnick, L., Borgida, A.. Living with
CLASSIC: When and how to use a KLONElike language. In: Principles of
Semantic Networks, edited by John Sowa, Morgan Kaufmann, 1991
[paper version available].
 Enrico Franconi. A complete
course on Description Logics.
 Additional optional readings:
 "Principles of Semantic Networks: Explorations in the
Representation of Knowledge", by John Sowa (Editor), Morgan Kaufman,
1991
 "Semantic Networks in Artificial Intelligence", by Fritz Lehmann
(Editor), Pergamon Press, 1992
 "Readings in Knowledge Representation", by Ronald Brachman and
Hector Levesque (Editors), Morgan Kaufman, 1985
 "Inheritance Hierarchies in KR and programming Languages", by
Maurizio Lenzerini, Daniele Nardi, and Maria Simi (Editors), Wiley,
1991
Syllabus
 Part on propositional and first order logic
 Agents that Reason Logically
 Representation, Reasoning, and Logic
 Foundations of Propositional Logic
 Deduction in Propositional Logic
 Foundations of First Order Logic
 Using First Order Logic
 Part on Description Logics
 Knowledge Representation at work: Description Logics
 Structural Description Logics
 The need for a Logic
 Examples from ObjectOriented languages
 The simplest Structural Description Logic: FL
 Propositional Description Logics
 Adding Expressivity to Description Logics
 Instances and Knowledge Bases
 Reasoning with Knowledge Bases
Lectures and course slides
Thursday, 9:0010:00, Room LF15,
Thursday, 12:0013:00, Room LF14.
(Spare slot: Monday, 13:0014:00, Room LF15)
 Tuesday, 28 September, 14:0015:00, Room LF14
Introductory
lecture: Agents that Reason Logically
 Thursday, 30 September, 12:0013:00, Room LF15
Foundations
of Propositional Logic
 Thursday, 7 October, 9:0010:00, Room LF15
Foundations of Propositional Logic (cont.)
 Thursday, 7 October, 12:0013:00, Room LF15
Deduction
in Propositional Logic
 Thursday, 14 October, 9:0010:00, Room LF15
Deduction in Propositional Logic (cont.)
 Thursday, 14 October, 12:0013:00, Room LF15
Foundations
of First Order Logic
 Thursday, 21 October, 9:0010:00, Room LF15
Foundations of First Order Logic (cont.)
 Thursday, 21 October, 12:0013:00, Room LF14
Foundations of First Order Logic (cont.)
 Thursday, 28 October, 9:0010:00, Room LF15
Foundations of First Order Logic (cont.)
 Thursday, 28 October, 12:0013:00, Room LF14
Foundations of First Order Logic (cont.)
 Thursday, 11 November, 9:0010:00, Room LF15
Using
First Order Logic
 Thursday, 11 November, 12:0013:00, Room LF14
Using First Order Logic (cont.)
 Thursday, 18 November: no lecture
 Thursday, 18 November: no lecture
 Monday, 22 November, 13:0014:00, Room LF15
Individual class exercise (assessed),
on propositional and first order logic.
 Thursday, 25 November, 9:0010:00, Room LF15
Using First Order Logic (cont.)
 Thursday, 25 November, 12:0013:00, Room LF14
Introduction
to Structural Description Logics
 Thursday, 2 December, 9:0010:00, Room LF15
Correction of the class exercise
 Thursday, 2 December, 12:0013:00, Room LF14
Introduction to Structural Description Logics (cont.)
 Monday, 6 December, 13:0014:00, Room LF15
The minimal Structural Description Logic FL
 Thursday, 9 December, 9:0010:00, Room LF15
The minimal Structural Description Logic FL (cont.)
 Thursday, 9 December, 12:0013:00, Room LF14
Propositional
Description Logics
 Thursday, 16 December, 9:0010:00, Room LF15
Propositional Description Logics (cont.)
 Thursday, 16 December, 12:0013:00, Room LF14
Knowledge Bases in
Description Logics
Resources
 A glossary
for first order logic
 cardTAP:
an online propositional logic reasoner
 Bertrand,
a tableaux based prover for propositional and first order
logic for the Macintosh. Ideal to learn: it shows the proof tree.
franconi@cs.man.ac.uk