-
Logical AI, the background to representing information in logic. An overview
of what will be covered in the course, and what homeworks, papers etc.
are required.
First order logic, model theory, proof theory. Second order logic, Henkin
models. Theorem Provers, PVS.
Enderton's "A Mathematical Introduction to Logic" provides a good introduction
to logic in general. It is a little light on higher order logic, which
we will use a lot. However, luckily there is little to know.
We shall need to use the PVS theorem prover. Using theorem provers
is an art, which takes time to learn, but which is very valuable. PVS is
actually quite easy to use, after initial teething pains.
-
The situation calculus and the event calculus: The two main formalisms
for reasoning about change.
McCarthy and Hayes. The limitations of the situation calculus. Reiter's
foundation axioms, categoricity. Representing actions. Kowalski's event
calculus. Linear vs branching time.
For this class the basic references are McCarthy and Hayes, Some
Philosophical Problems from the Standpoint of AI, Knowledge
In Action a draft of a book by Ray Reiter. Some
contributions to the metatheory of the situation calculus a overview
paper by Fiora Pirri and Ray Reiter, and Combining
Narratives by John McCarthy and Tom Costello. Event
Calculus Revisited by Murray Shanahan.
-
The frame problem: A major problem of logical AI. Its monotonic solution.
Frame axioms. The Yale Shooting Problem. Hayes's objections. Generating
successor state axioms in presence of domain constraints.
The main papers here are McCarthy and Hayes, Some
Philosophical Problems from the Standpoint of AI, Ray Reiter's A
simple solution to the frame problem (sometimes).
Leora Morgenstern has a overview paper on problems with solutions to
the frame problem, The Problem with Solutions to
the Frame Problem.
-
Planning and prediction in temporal formalisms.
Goal regression, implementation in theorem provers. Examples.
Axiomatization of the Blocksworld.
Theory put into PVS.
-
Non-monotonic reasoning: why we need it? (elaboration tolerance). Various
basic forms of circumscription, domain/predicate/formula. Handout
Definitions, model theory, soundness and "completeness". Minimal
model semantics.
-
The expressive power of circumscription. The complexity of circumscription.
Handout
Meaning of minimizing a formula. Characterization of expressive power
of different variants. NP hierarchy, and complexity.
-
How to reduce circumscription to first order logic. Two methods, DLS
and SCAN.
-
Pointwise circumscription and Chronological minimization. Handout about action. There were also
photocopies of Vladimir's Lifschitz's Pointwise Circumscription paper,
and some pages (451-459) from Vol 4. of the Handbook of logic in artificial
intelligence. (The chapter by Shoham and Sandewall.)
-
Domain formula circumscription. Bossu and Seigel and the limit assumption. Handout
- Ways of making circumscription satisfiability preserving. Cofinal circumscription. Handout
-
Circumscription and the frame problem. Solutions by Baker, Lin and Reiter.
The projection problem: Solutions by Lin and Reiter, Giunchiglia and Costello.
-
Splitting theories to reduce casual reasoning to projection, Giunchiglia
and Lifschitz.
-
Non-monotonic consequence relations
-
Defeasable logic and conditional logic
-
Default logic and the necessary modifications to make it cumulative.
-
Auto-epistemic logic
-
Belief revision as proposed by AGM
-
Belief update and its relationship to theories of action.
-
Counterfactuals (McCarthy and Costello, Pearl, Lewis, Stalnaker, Ginsberg's
approaches)
-
Intentional phenomena: Names of formulas and abstract syntax. The paradoxes
of syntactic modality. Perlis's and others approach to truth predicates
and these paradoxes.
-
Contexts, lifting axioms. Modal logic approaches to context.