AC51026: Logical and Symbolic Artificial Intelligence
People:
- Dr .Jesse Hoey, Module Coordinator (jessehoey@computing.dundee.ac.uk)
- Joseph Devereux, Lab Tutor (josephdevereux@computing.dundee.ac.uk)
TIMETABLE:
Lectures will take place once per week in QM seminar room on
Tuesday 1400-1700hrs (2pm-5pm)
Lab sessions will be held in QM Lab 2 on
Tuesday 1100-1300 (11am-1pm)
Detailed Lecture Schedule (locations as above unless otherwise noted):
STRUCTURE
The course will consist of one 3-hour in-class session per week and one 2-hour lab session per week.
The course content will be delivered in a lecture format, with time for discussion. There will be 1-3 assignments per week. The first will usually be a short reading assignment that will be used primarily for discussion purposes. The second will be the lab assignment. The lab work will consist of hands-on problem solving using Prolog. The lab session can be used to interact with the lecturer or teaching assistants and ask questions specifically about Prolog programming. There will also be problem sets assigned.
In class sessions will be structured (roughly) as follows
- 30 min discussion of assignments from previous class (usually a reading assignment and problem assignment for the week). The idea is to get everyone thinking again about the course material, and to discuss a relevant issue.
- 60 min lecture
- 20 min. break
- 60 min. lecture
- 10 min. assignment of reading and problems for next class and lab
READINGS:
Primary Texts:
David Poole, Alan Mackworth and Randy Goebel, "Computational Intelligence: A Logical Approach"
(available from oup.co.uk - copies in the library)
Also see the book's website for additional information
And the useful and informative java applets on the CI-Space website
Ulf Nilsson and Jan Maluszynski, "Logic, Programming and Prolog (2ed)".
(avaiable free online)
Secondary Readings:
Ivan Bratko. "Prolog - Programming for AI", Addison Wesley, 1990 (2ed)
John Kelly, "The Essence of Logic", Prentice Hall, 1997
Hofstadter "Godel, Escher, Bach: and Eternal Golden Braid". Vintage 1980
Usage
The course will basically use Poole, Mackworth and Goebel as a guide for all material.
Nilsson and Malusznyski present a slightly more advanced treatment of the same subjects.
Bratko will be used for Prolog stuff
and Kelly will be used mainly for reference purposes in the logic stuff at the start of the course
Finally, Hofstadter will be used for additional readings and materials.
Assessment
- Two hour written examination in December
- All material is examinable (including labs and readings)
PROLOG
SWI-Prolog is available free online from
SWI.
It will be installed on the lab machines.
SWI-Prolog manuals are online at the same website.
COURSE OUTLINE
Lecture 1 - Introduction and Propositional Logic
Material:
Topics:
Overview and Applications Slides...Handouts
- AI overview
- Motivational examples from literature
- Discuss symbolic approaches to AI in general and constrast with emergent approaches (e.g. connectionist)
- Discuss in general monotonic/non-monotonic logics and their relationships to human reasoning
- Logical Reasoning and Artificial Intelligence and Human Intelligence and Human Reasoning.
- Overview of Class Material
Introduction to Logic Slides...Handouts
- Logical Connectives (and, or, not, if...then, if and only if, ...)
- Truth Tables
- Equivalences and Simplification (de Morgan's Laws)
- Modus Ponens
Laboratory
Problem Set
Reading:
Hofstadter Chap XVIII
Lecture 2 - Propositional Logic and Prolog
Material
- Kelly Chap 3.1-3.2
- Kelly Chap 4 (selected parts)
- Bratko Chap 1.1-1.2
Topics:
Propositional Logic Slides...Handouts
- Reductio Ad Absurdum
- Axiomatic Propositional Logic
Prolog Slides...Handouts
- Prolog introduction
- Facts and Queries
- Quantification
- Rules
- Recursive Rules
Laboratory
Problem Set
Reading
Hofstatder Chap 1
Lecture 3 - Definite Predicate Logic, Semantics and Prolog
Material:
- Poole Chap 2.1-2.6
- Nilsson Chap 1
Topics:
Predicates and Semantics Slides...Handouts
- Variables
- Logic Formulas
- Semantics, Models, Interpretations
- Ground Proofs (top-down bottom-up)
Proofs and SLD resolution Slides...Handouts
- Proofs with variables (SLD resolution)
- Adding functions (occurs check)
Advanced Prolog (Lists) Slides...Handouts
- Advanced Prolog
- Lists
- Operators
- Arithmetic
Laboratory:
Problem Set
Reading
Lecture 4- SLD Resolution
Material:
- Poole Chap 2.7-2.8
- Nilsson Chap 3
Topics:
SLD Resolution and Functions Slides...Handouts
- Top Down Proofs (SLD Resolution)
- Functions
- Starvation and Occurs Check
Laboratory:
Problem Set
Reading
Lecture 5 - Searching and Sorting
Material:
Topics:
Searching and Sorting Slides...Handouts
- Search in General
- Blind Search Strategies
- Heuristic Search
- Sorting
- Dynamic Programming
Laboratory:
Problem Set
Reading
Lecture 6 - Constraint Satisfaction
Material:
Topics:
CSPs Slides...Handouts
- Constraint Satisfaction
- Backtracking
- Generate and test
- Consistency and AC-3
- Hill Climbing
- Randomized Algorigthms
Laboratory:
Problem Set
Reading
Lecture 7 - Planning
Material:
Topics:
Planning Slides
- Cut
- Negation as Failure
- Situation Calculus
- STRIPS
- Planning as resolution
Laboratory:
Problem Set
Reading
Lecture 8 - Uncertainty
Material:
Topics:
Lecture 10-a Slides
- Random Variables
- Probability Semantics
- Bayes' Theorem
- Belief Networks
Laboratory:
Problem Set
Reading