next up previous
Next: About this document Up: CIRCUMSCRIPTION-A FORM OF NONMONOTONIC Previous: REMARKS AND ACKNOWLEDGEMENTS

References

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

displaymath971

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

displaymath979

where tex2html_wrap_inline473 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 tex2html_wrap_inline473 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 tex2html_wrap_inline473 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

equation283

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

equation287

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 tex2html_wrap_inline1005 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.


next up previous
Next: About this document Up: CIRCUMSCRIPTION-A FORM OF NONMONOTONIC Previous: REMARKS AND ACKNOWLEDGEMENTS

John McCarthy
Tue May 14 00:04:52 PDT 1996