Amarel, Saul (1971). On Representation of Problems of Reasoning
about Actions, in D. Michie (ed.), *Machine Intelligence 3*,
Edinburgh University Press, pp. 131-171.

Chandra, Ashok (1979). Personal conversation, August.

Davis, Martin (1980). Notes on the Mathematics of Non-Monotonic
Reasoning, *Artificial Intelligence 13* (1, 2), pp. 73-80.

Hayes, Patrick (1979). Personal conversation, September.

Hewitt, Carl (1972). *Description and Theoretical Analysis
(Using Schemata) of PLANNER: a Language for Proving Theorems and
Manipulating Models in a Robot*, MIT AI Laboratory TR-258.

McCarthy, John (1959). Programs with Common Sense, *Proceedings of
the Teddington Conference on the Mechanization of Thought Processes*, London: Her
Majesty's Stationery Office.
(Reprinted in this volume, pp. 000-000).

McCarthy, John and Patrick Hayes (1969). Some Philosophical
Problems from the Standpoint of Artificial Intelligence,
in B. Meltzer and D. Michie (eds), *Machine Intelligence 4*,
Edinburgh University.
(Reprinted in B. L. Webber and N. J. Nilsson (eds.),
*Readings in Artificial Intelligence*, Tioga, 1981, pp. 431-450;
also in M. J. Ginsberg (ed.), *Readings in Nonmonotonic Reasoning*, Morgan
Kaufmann, 1987, pp. 26-45.
Reprinted in (McCarthy 1990).

McCarthy, John (1977).
Epistemological Problems of Artificial Intelligence, *Proceedings
of the Fifth International Joint Conference on Artificial
Intelligence*, M.I.T., Cambridge, Mass.
(Reprinted in B. L. Webber and N. J. Nilsson (eds.), *Readings in Artificial
Intelligence*, Tioga, 1981, pp. 459-465;
also in M. J. Ginsberg (ed.), *Readings in Nonmonotonic Reasoning*, Morgan
Kaufmann, 1987, pp. 46-52.
Reprinted in (McCarthy 1990).

McCarthy, John (1979a).
Ascribing Mental Qualities to Machines
, *Philosophical Perspectives
in Artificial Intelligence*, Martin Ringle, ed., Humanities Press.
Reprinted in (McCarthy 1990).

McCarthy, John (1979b).
First Order Theories of Individual
Concepts and Propositions
in Michie, Donald (ed.) *Machine Intelligence 9*,
Ellis Horwood.
Reprinted in (McCarthy 1990).

McCarthy, John (1990).
*Formalizing Common Sense*, Ablex.

Reiter, Raymond (1980). A Logic for Default Reasoning,
*Artificial Intelligence 13* (1, 2), pp. 81-132.

Sussman, G.J., T. Winograd, and E. Charniak (1971).
*Micro-Planner Reference Manual, AI Memo 203*, M.I.T. AI Lab.

Circumscription and the nonmonotonic reasoning formalisms of McDermott and Doyle (1980) and Reiter (1980) differ along two dimensions. First, circumscription is concerned with minimal models, and they are concerned with arbitrary models. It appears that these approaches solve somewhat different though overlapping classes of problems, and each has its uses. The other difference is that the reasoning of both other formalisms involves models directly, while the syntactic formulation of circumscription uses axiom schemata. Consequently, their systems are incompletely formal unless the metamathematics is also formalized, and this hasn't yet been done.

However, schemata are applicable to other formalisms than circumscription. Suppose, for example, that we have some axioms about trains and their presence on tracks, and we wish to express the fact that if a train may be present, it is unsafe to cross the tracks. In the McDermott-Doyle formalism, this might be expressed

where the properties of the predicate *on* are supposed
expressed in a formula that we
may call *Axiom*(*on*). The **M** in (1) stands for ``is
possible''.
We propose to replace (1) and *Axiom*(*on*) by
the schema

where is a predicate parameter that can be replaced by any
predicate expression that can be written in the language being
used. If we can find a that makes the left hand side of
(2) provable, then we can be sure that *Axiom*(*on*)
together with *on*(*train*,*tracks*) has a model assuming that
*Axiom*(*on*) is consistent. Therefore, the schema (2)
is essentially a consequence of the McDermott-Doyle formula
(1). The converse isn't true. A predicate symbol may have
a model without there being an explicit formula realizing it.
I believe, however, that the schema is usable in all cases
where the McDermott-Doyle or Reiter formalisms can be practically
applied, and, in particular, to all the examples in their papers.

(If one wants a counter-example to the usability of the schema, one might look at the membership relation of set theory with the finitely axiomatized Gödel-Bernays set theory as the axiom. Instantiating in this case would amount to giving an internal model of set theory, and this is possible only in a stronger theory).

It appears that such use of schemata amounts to importing part of the model theory of a subject into the theory itself. It looks useful and even essential for common sense reasoning, but its logical properties are not obvious.

We can also go frankly to second order logic and write

Second order reasoning, which might be in set theory or a formalism
admitting concepts as objects rather than in second order logic,
seems to have the advantage that some of the predicate and function
symbols may be left fixed and others imitated by predicate parameters.
This allows us to say something like, ``For any interpretation of
*P* and *Q* satisfying the axiom *A*, if there is an interpretation in
which *R* and *S* satisfy the additional axiom *A*', then it is unsafe
to cross the tracks''. This may be needed to express common sense
nonmonotonic reasoning, and it seems more powerful than any of
the above-mentioned nonmonotonic formalisms including circumscription.

The train example is a nonnormal default in Reiter's sense, because we cannot conclude that the train is on the tracks in the absence of evidence to the contrary. Indeed, suppose that we want to wait for and catch a train at a station across the tracks. If there might be a train coming we will take a bridge rather than a shortcut across the tracks, but we don't want to jump to the conclusion that there is a train, because then we would think we were too late and give up trying to catch it. The statement can be reformulated as a normal default by writing

but this is unlikely to be equivalent in all cases and the nonnormal expression seems to express better the common sense facts.

Like normal defaults, circumscription doesn't deal with possibility directly, and a circumscriptive treatment of the train problem would involve circumscribing in the set of axioms. It therefore might not be completely satisfactory.

McDermott, Drew and Jon Doyle (1980). Nonmonotonic Logic I,
*Artificial Intelligence 13* (1, 2), pp. 41-72.

Reiter, Raymond (1980). A Logic for Default Reasoning,
*Artificial Intelligence 13* (1, 2), pp. 81-132.

Tue May 14 00:04:52 PDT 1996