GS/CSE 6390A Knowledge Representation
Fall 2015
Department of Electrical Engineering and Computer Science,
York University
An InDepth Survey of Knowledge Representation and Reasoning
The course examines some of the techniques used to represent
knowledge in artificial intelligence, and the associated methods of
automated reasoning. The emphasis will be on the compromises involved
in providing a useful but tractable representation and reasoning
service to a knowledgebased system.
What's new:
 Dec 4: There were some errors in the version of assignment 4
originally posted. Please download the corrected version below,
which contains only 3 questions.
 Dec 2: Assignment 4 is out; it is due
by Dec 16 at 14:00  extended! A scan of the questions
from the textbook can be obtained by emailing the instructor.
 Dec 1: Test 2 will be on Dec 7 during class. It
will cover Chapter 9 and Chapters 11 to 14 inclusively of the Brachman
and Levesque textbook, as well as the other required
readings about Description Logics posted on the course website.
 Nov 16: Assignment 3 is out; it is due
by Dec 3 at 17:30  extended again! A scan of the questions
from the textbook can be obtained by emailing the instructor.
 Nov. 9: Slides and readings on Description Logics:
De Giacomo's slides on Description Logics and their use for reasoning about UML class diagrams  read at least pp. 126 and p. 32,
Horrocks and Sattler's slides on tableaux for ALC concept satisfiability  read these,
Horrocks and Sattler's slides on tableaux for ALC knowledge bases  read at least p. 2 & 3,
Baader and Sattler's paper Overview of Tableau Algorighms for Description Logics,
De Giacomo's slides on DLLite (Oct 5, 2010 talk at U of T)  read at least pp. 46, 13, 29, 30, 3638,
as well as
Calvanese et al's paper Conceptual Modeling for Data Integration which discussses much the same material. A more detailed reference is
Calvanese et al's Ontologies and Databases: The DLLite Approach.
Another useful reference on Description Logic is
Lutz's slides on
Reasoning in Description Logics: Expressive Power vs. Computational Complexity,
from his tutorial at KR 2010.
 Oct 21: Assignment 2 is out; it is due
by Nov 9 at 17:30  extended! A scan of the questions
from the textbook can be obtained by emailing the instructor.
 Oct 19: Test 1 will be on Oct 28 during class.
It will cover Chapter 1 to 6 inclusively of the Brachman and Levesque textbook.
 Sept 29: Assignment 1 is out; it is due
on Oct 14. A scan of the questions from the textbook can be
obtained by emailing the instructor.
 The first lecture is on Sept 14.
Instructor
Prof. Yves Lespérance
Office: LAS 3052A
Tel: 4167362100 ext. 70146
Email: lesperan "at" cse.yorku.ca
Lectures
Monday and Wednesday from 17:30 to 19:00 in VH 1005 (VH is Vari Hall).
Instructor Office Hours
Monday and Wednesday 16:00  17:00,
or by appointment.
Textbook
Ronald J. Brachman and Hector J. Levesque,
Knowledge Representation and Reasoning,
Elsevier/Morgan Kaufmann 2004, ISBN 1558609326
Purchasing the textbook is optional; lecture notes (slides) will be
distributed, which cover much of the material; textbook is on reserve at
Steacie Library.
Prerequisites
Knowledge of firstorder logic. Some knowledge of Prolog is helpful.
Evaluation
Assignements (4 @ 12.5% each)  50% 
Test 1  30% 
Test 2  20% 
Total  100% 
Tentative Schedule
 Week 1 (Sept 14) Chapter 1 Introduction.
Chapter 2 The Language of FirstOrder Logic.
 Week 2 (Sept 21) Chapter 3 Expressing Knowledge. Chapter 4 Resolution.
 Week 3 (Sept 28) Chapter 4 Resolution cont.
 Week 4 (Oct 5) Chapter 5 Reasoning with Horn Clauses.
 Week 5 (Oct 12) No class on Oct 12. Chapter 6 Procedural Control of Reasoning, Prolog.
 Week 6 (Oct 19) Chapter 9 Structured Descriptions, Description Logic, and Ontologies.
 Week 7 (Oct 26) Test 1. Chapter 9 Structured Descriptions, Description Logic, and Ontologies cont.
 Week 8 (Nov 2) Description Logic cont.
 Week 9 (Nov 9) Chapter 11 Defaults.
 Week 10 (Nov 16) Chapter 12 Vagueness, Uncertainty, and Degrees of Belief.
 Week 11 (Nov 23) Chapter 13 Explanations and Diagnosis. Chapter 14 Actions.
 Week 12 (Nov 30) Chapter 15 Planning.
 Week 13 (Dec 7) Test 2.
Additional References
On FirstOrder Logic:
Enderton, H.B.,
A Mathematical Introduction to Logic.
Academic Press, New York, 1972.
Tourlakis, G.,
Mathematical Logic.
Wiley, 2008.
A good Prolog text:
Clocksin, W.F. and Mellish, C.S.,
Programming in Prolog, (5th edition), Springer Verlag, New York, 2004.
On knowledge representation:
Baral, C.
Knowledge representation, reasoning, and declarative problem solving.
Cambridge University Press, Cambridge/New York, 2003.
Genesereth, M.R. and Nilsson, N.J.
Logical foundations of artificial intelligence.
Morgan Kaufmann, Los Altos, CA, 1987.
Van Harmelen, F., Lifschiltz, V., and Porter, B.
Handbook of Knowledge Representation.
Elsevier, Amsterdam, 2008.
On description logic:
Baader, F., Calvanese, D., McGuiness, D., Nardi, D., PatelSchneider, P.
The Description Logic Handbook, 2nd Edition.
Cambridge Univ. Press, Cambridge UK, 2007.
Lutz, C.
Reasoning in Descriprion Logics: Expressive Power vs. Computational Complexity,
slides from Tutorial at KR 2010.
On reasoning about action:
Reiter, R.,
Knowledge in Action: Logical Foundations for Specifying and Implementing
Dynamical Systems,
MIT Press, 2001.
York Library eCopy,
Book home page.
On AI:
Russell, S.J. and Norvig, P.,
Artificial Intelligence: A Modern Approach, 3rd edition
Prentice Hall, 2010.
Poole, D. and Mackworth, A.,
Artificial Intelligence: Foundations of Computational Agents,
Cambridge University Press, 2010.

Running SWIProlog on the York EECS Research System or Prism


To run Prolog execute the command pl. To exit enter
<CTRL>D
at the prompt.

Documentation is available
on the web.
Getting Prolog
About Prolog