CS3411 Advanced Knowledge Based Systems
1999-2000 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 logic-based 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, McGraw-Hill, 1998
  - "Introduction to Mathematical Logic", by Elliott Mendelson, Chapman & Hall, 1997
  - "Mathematical Logic", by H.D. Ebbinghaus, J. Flum, and W. Thomas, Springer-Verlag, 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, 78-93 (1987) [paper version available].
  - B. Nebel. Reasoning and Revision in Hybrid Representation Systems. Lecture Notes in Artificial Intelligence 422, Springer-Verlag, 1990. Chapters 1 - 6.
  - Woods, W., Schmolze, J., `The KL-ONE Family', Computers and Mathematics with Applications, special issue: Semantic Networks in Artificial Intelligence, Vol 2-5, pp 133-177, 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 193-238, 1996.
  - Brachman, R., McGuinness, D., Patel-Schneider, P., Resnick, L., Borgida, A.. Living with CLASSIC: When and how to use a KL-ONE-like 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
  - Motivating the course
- 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 Object-Oriented 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:00-10:00, Room LF15,
Thursday, 12:00-13:00, Room LF14.
(Spare slot: Monday, 13:00-14:00, Room LF15)

Tuesday, 28 September, 14:00-15:00, Room LF14
Introductory lecture: Agents that Reason Logically
Thursday, 30 September, 12:00-13:00, Room LF15
Foundations of Propositional Logic
Thursday, 7 October, 9:00-10:00, Room LF15
Foundations of Propositional Logic (cont.)
Thursday, 7 October, 12:00-13:00, Room LF15
Deduction in Propositional Logic
Thursday, 14 October, 9:00-10:00, Room LF15
Deduction in Propositional Logic (cont.)
Thursday, 14 October, 12:00-13:00, Room LF15
Foundations of First Order Logic
Thursday, 21 October, 9:00-10:00, Room LF15
Foundations of First Order Logic (cont.)
Thursday, 21 October, 12:00-13:00, Room LF14
Foundations of First Order Logic (cont.)
Thursday, 28 October, 9:00-10:00, Room LF15
Foundations of First Order Logic (cont.)
Thursday, 28 October, 12:00-13:00, Room LF14
Foundations of First Order Logic (cont.)
Thursday, 11 November, 9:00-10:00, Room LF15
Using First Order Logic
Thursday, 11 November, 12:00-13:00, Room LF14
Using First Order Logic (cont.)
Thursday, 18 November: no lecture
Thursday, 18 November: no lecture
Monday, 22 November, 13:00-14:00, Room LF15
Individual class exercise (assessed), on propositional and first order logic.
Thursday, 25 November, 9:00-10:00, Room LF15
Using First Order Logic (cont.)
Thursday, 25 November, 12:00-13:00, Room LF14
Introduction to Structural Description Logics
Thursday, 2 December, 9:00-10:00, Room LF15
Correction of the class exercise
Thursday, 2 December, 12:00-13:00, Room LF14
Introduction to Structural Description Logics (cont.)
Monday, 6 December, 13:00-14:00, Room LF15
The minimal Structural Description Logic FL-
Thursday, 9 December, 9:00-10:00, Room LF15
The minimal Structural Description Logic FL- (cont.)
Thursday, 9 December, 12:00-13:00, Room LF14
Propositional Description Logics
Thursday, 16 December, 9:00-10:00, Room LF15
Propositional Description Logics (cont.)
Thursday, 16 December, 12:00-13: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

CS3411 Advanced Knowledge Based Systems 1999-2000 session