next up previous
Next: Some Formalizations and their Up: ARTIFICIAL INTELLIGENCELOGIC AND Previous: Introduction

Formalized Nonmonotonic Reasoning


It seems that fourth level systems require extensions to mathematical logic. One kind of extension is formalized nonmonotonic reasoning, first proposed in the late 1970s (McCarthy 1977, 1980, 1986), (Reiter 1980), (McDermott and Doyle 1980), (Lifschitz 1989a). Mathematical logic has been monotonic in the following sense. If we have tex2html_wrap_inline334 and tex2html_wrap_inline336 , then we also have tex2html_wrap_inline338 .

If the inference is logical deduction, then exactly the same proof that proves p from A will serve as a proof from B. If the inference is model-theoretic, i.e. p is true in all models of A, then p will be true in all models of B, because the models of B will be a subset of the models of A. So we see that the monotonic character of traditional logic doesn't depend on the details of the logical system but is quite fundamental.

While much human reasoning is monotonic, some important human common-sense reasoning is not. We reach conclusions from certain premisses that we would not reach if certain other sentences were included in our premisses. For example, if I hire you to build me a bird cage, you conclude that it is appropriate to put a top on it, but when you learn the further fact that my bird is a penguin you no longer draw that conclusion. Some people think it is possible to try to save monotonicity by saying that what was in your mind was not a general rule about birds flying but a probabilistic rule. So far these people have not worked out any detailed epistemology for this approach, i.e. exactly what probabilistic sentences should be used. Instead AI has moved to directly formalizing nonmonotonic logical reasoning. Indeed it seems to me that when probabilistic reasoning (and not just the axiomatic basis of probability theory) has been fully formalized, it will be formally nonmonotonic.

Nonmonotonic reasoning is an active field of study. Progress is often driven by examples, e.g. the Yale shooting problem (Hanks and McDermott 1986), in which obvious axiomatizations used with the available reasoning formalisms don't seem to give the answers intuition suggests. One direction being explored (Moore 1985, Gelfond 1987, Lifschitz 1989a) involves putting facts about belief and knowledge explicitly in the axioms
--even when the axioms concern nonmental domains. Moore's classical example (now 4 years old) is ``If I had an elder brother I'd know it.''

Kraus and Perlis (1988) have proposed to divide much nonmonotonic reasoning into two steps. The first step uses Perlis's (1988) autocircumscription to get a second order formula characterizing what is possible. The second step involves default reasoning to choose what is normally to be expected out of the previously established possibilities. This seems to be a promising approach.

(Ginsberg 1987) collects the main papers up to 1986. Lifschitz (1989c) summarizes some example research problems of nonmonotonic reasoning.

next up previous
Next: Some Formalizations and their Up: ARTIFICIAL INTELLIGENCELOGIC AND Previous: Introduction

John McCarthy
Mon Jun 26 17:50:09 PDT 2000