EECS 3401 3.0
Department of Electrical
Engineering & Computer Science,
Introduction to Artificial Intelligence and Logic Programming
Artificial Intelligence (AI) deals with how to build systems that can
operate in an intelligent fashion. In this course, we examine
fundamental concepts in AI: knowledge representation and reasoning,
search, constraint satisfaction, reasoning under uncertainty, etc. The
course also introduces logic programming, a programming paradigm based
on predicate logic, where one specifies problems in a declarative way
and one can use the language to search for a solution. Students will
learn how to develop programs in Prolog to solve AI problems.
The course covers the following topics:
- Introduction to Artificial Intelligence, intelligent agents.
- Logical representations, first-order logic syntax and semantics,
use in knowledge representation.
- Basics of logic programming and Prolog, syntax, backchaining procedure.
- Inference in first order logic, unification, resolution.
- Reasoning with Horn theories, SLDNF resolution, Prolog control
flow, backtracking, closed world assumption, negation as failure.
- Prolog lists, arithmetic.
- Uninformed search.
- Informed search.
- Constraint satisfaction and backtracking search.
- Game/adversarial search.
- Uncertain reasoning, Bayes Nets.
- Define the main objectives of artificial intelligence.
- Describe how first-order predicate logic forms the basis of logic programming.
- Write logic programs in Prolog.
- Use and modify heuristic state-space search algorithms such
as A*, RTA* and IDA*.
- Represent knowledge in a small domain using predicate logic
and use the representation to build a logical database for a
knowledge-based expert system.
- Describe and use some other AI techniques including backward
and forward chaining, Bayesian networks, game search and constraint satisfaction, grammars for natural language processing.
- Oct 15: The midterm test will be held on Oct. 30 during class. Stay tuned for more details about what is covered.
- Oct 15: see added alides on entailment in Lecture Transparencies for Week 2 below.
- Oct. 4: Assignment 1 is out; it is due Oct. 18 at 14:30.
- Classes start Sept. 11.
Prof. Yves Lespérance
Office: LAS 3052A
Tel: 736-2100 ext. 70146
Email: lesperan "at" cse.yorku.ca
Monday and Wednesday from 14:30 to 16:00 in CB 121 (CB is Chemistry Building).
Instructor Office Hours
Monday and Wednesday from 16:30 to 17:30, in LAS 3052A.
Russell, S.J. and Norvig, P.,
Artificial Intelligence: A Modern Approach, 3rd edition
Prentice Hall, 2010.
Authors' web site,
Publisher's web site.
Clocksin, W.F. and Mellish, C.S.,
Programming in Prolog, (5th edition), Springer Verlag, New York, 2004.
The textbooks are strongly recommended; they are available at the York University Bookstore.
General prerequisites; LE/EECS2011 3.00, SC/MATH1090 3.0.
Tentative Evaluation Scheme
| Assignements (4 @ 6% each)
| Midterm test || 26%|
| Final exam || 50%|
| Total|| 100%|
- Week 1 (Sept 11) Introduction & intelligent agents.
Logical representations, first-order logic syntax and semantics,
use in knowledge representation.
(R&N ch. 1, 2, 7, 8).
- Weeks 2 & 3 (Sept 18 & 25) Basics of logic programming and Prolog,
syntax, backchaining procedure, arithmetic, lists, I/O, recursive definitions, constraints solving, debugging. (C&M ch. 1, 2, 3.1-3.3, 5, and 8)
- Weeks 4 & 5 (Oct 2 & 9) Inference in first order logic, unification, resolution.
(R&N ch. 9).
- Week 6 (Oct 16) Reasoning with Horn theories, SLDNF resolution, Prolog
control flow, backtracking, closed world assumption, negation as failure
(R&N ch. 9 & C&M ch. 4 & 10). Assignment 1 due.
- Week 7 (Oct 23) Prolog control flow, negation as failure, cut,
2nd order features, tail recursion(C&M ch. 3, 4, 6, & 10).
- Week 8 (Oct 30) Uninformed search (R&N ch. 3, sec. 1-4).
- Week 9 (Nov 6) Informed search (R&N ch. 3, sec, 5 & 6 and ch. 4 sec. 1).
- Week 10 (Nov 13) Game/Adversarial Search (R&N ch. 5 sec. 1-3 & 7).
- Week 11 (Nov 20) Constraint satisfaction and backtracking search (R&N ch. 6)
- Week 12 (Nov 27) Uncertain Reasoning (R&N ch. 13-14).
- Week 13 (Dec 4) Review.
It is important that you look at the
departmental guidelines on academic honesty. Although you may discuss the general approach to solving a problem with other people, you should not discuss the solution in detail. You must not take any written notes away from such a discussion. Also, you must list on the cover page of your solutions any people with whom you have discussed the problems. The solutions you hand in should be your own work. While writing them, you may look at the course textbook and your own lecture notes but no other outside sources.
Readings and Lecture Transparencies
- Week 1 - Lecture 1 (Sept 11) Introduction & intelligent agents
Required Readings: Russell & Norvig Chapter 1 & 2.
- Week 1 - Lecture 2 (Sept 13) Knowledge Representation & First-Order Logic
Required Readings: Russell & Norvig Chapter 8 (Chapter 7 is optional).
additional slides on entailment from Brachman and Levesque (new!).
- Weeks 2 & 3 (Sept 18 & 25) Prolog Core Concepts and Notation
Required Readings: Clocksin & Mellish Chapters 1, 2, 3.1 to 3.3, 5, and 8.
zebra.swipl zebra logic puzzle example code (the zebra.pl file has been renamed zebra.swipl so that our web server will let you download it).
- Weeks 4 & 5 (Oct 2 & 9) Inference in First-Order Logic
Required Readings: Russell & Norvig Chapter 9.
Lecture transparencies (updated!).
- Week 6 (Oct 16) Reasoning with Horn Theories and Procedural Control of Reasoning
Required Readings: Russell & Norvig Chapter 9 and Clocksin & Mellish Chapter 4 & 10.
Optional Readings: Brachman and Levesque, Knowledge Representation and Reasoning, Chapters 5 & 6.
Lecture transparencies from Brachman and Levesque.
Other good AI textbooks:
Poole, D. and Mackworth, A.
Artificial Intelligence, Foundations of Computational Agents,
Cambridge University Press, 2010.
Poole, D., Mackworth, A., Goebel, R.
Computational Intelligence, A Logical Approach,,
Oxford University Press, New York, 1998.
Artificial Intelligence: A New Synthesis,,
Morgan Kaufmann, San Francisco, 1998.
On knowledge representation:
Ronald J. Brachman and Hector J. Levesque,
Knowledge Representation and Reasoning,
Elsevier/Morgan Kaufmann 2004, ISBN 1-55860-932-6
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.
On reasoning about action:
Knowledge in Action: Logical Foundations for Specifying and Implementing
MIT Press, 2001.
York Library eCopy,
Book home page.
Bratko, I. Prolog Programming for Artificial Intelligence 4th Edition,
Pearson Education Canada, 2012.
Sterling, L.S. and Shapiro, E.Y.
The Art of Prolog, Second Edition,
MIT Press, 1994.
Running SWI-Prolog in the Prism Lab
To run Prolog execute the command pl. To exit enter
at the prompt.
Documentation is available
on the web.