NONMONOTONIC REASONING—HISTORY AND REMARKS

John McCarthy, Stanford University mccarthy@stanford.edu http://www-formal.stanford.edu/jmc/ June 2, 2004

Nonmonotonic reasoning was needed for situation calculus.

PREHISTORY—NONMONOTONIC REASONING NOT TREATED EXPLICITLY

Predicate completion—Keith Clark Closed world assumption—Reiter Microplanner—Sussman and Winograd Prolog with negation as failure—Colmerauer Grumble about logic—Minsky HISTORY—NONMONOTONIC REASONING TREATED

EXPLICITLY

My 1977 paper had domain circumscription in it. [Not the minimal model, but a minimal model. Ashok Chandra pointed that out to me.] There was a workshop in 1978 at Stanford. 1980 special issue of AIJ.

• Non-monotonic logic—McDermott and Doyle

• Logic of defaults—Reiter • Circumscription—-McCarthy Auto-epistemic logic—Moore “Applications of circumscription to formalizing common sense”— McCarthy 1986 The early history ends in 1986. Reiter’s work on diagnosis. McIlraith also.

PREDICATE CIRCUMSCRIPTION—1986

∀x.¬ab aspect1 x ⊃ ¬flies x.  (1)
∀x.bird x ⊃ ab aspect1 x.  (2)

∀x.bird x ∧ ¬ab aspect2 x ⊃ flies x.  (3)

∀x.ostrich x ⊃ ab aspect2 x.  (4)
∀x.ostrich x ∧ ¬ab aspect3 x ⊃ ¬flies x.  (5)

ostrich(T im) ∧ bird(T weety).

Afterthought (2004): Need to circumscribe what can fly and what are birds and ostriches separately.

USES OF NONMONOTONIC REASONING

1. As a communication convention. Suppose A tells B about a situation involving a bird. If the bird cannot fly, and this is relevant, then A must say so. Whereas if the bird can fly, there is no requirement to mention the fact.

The proposed Common Business Communication Language (CBCL) (McCarthy 1982) must include nonmonotonic conventions about what may be inferred when a message leaves out such items as the method of delivery.

2. As a database or information storage convention. It may be a convention of a particular database that certain predicates have their minimal extension.

3. As a rule of conjecture.

4. As a representation of a policy. The example is Doyle’s “The meeting will be on Wednesday unless another decision is explicitly made”.

5. As a very streamlined expression of probabilistic information when numerical probabilities, especially conditional probabilities, are unobtainable.

6. Auto-epistemic reasoning. “If I had an elder brother, I’d know it”.

7. Both common sense physics and common sense psychology use nonmonotonic rules. An object will continue in a straight line if nothing interferes with it. A person will eat when hungry unless something prevents it.

HUMAN NONMONOTONIC REASONING

• Human reasoning compared to human speech. In speech we skate at the edge of ambiguity. That’s why descriptive linguistics is hard. Many ambiguities of speech are not reflected in a human’s internal reasoning. Van Benthem’s students used circumscription to treat exhaustive sentences.

• Most non-mathematical human reasoning is partly nonmmonotonic.

• I arrived in Vancouver at 6:30 pm, but didn’t leave for Whistler till 10 pm. That was because the road was closed until midnight. Is this the same as “I would have left earlier, but the road was closed.”

• Is “but” just used in communication or should sentences with “but” be included in an AI systems internal knowledge base?

• An argument: Taking into account only facts X, you jump to the conclusion that A, but if you also took into account facts Y, you would infer B.

PART OF A DIFFERENT SPEECH

• Computer scientists, through not paying attention to mathematical logic, are confused about many matters the logicians got right many decades ago.

• Ontology concerns what exists and does not include axioms. Common ontologies include individuals and unary predicates as objects but not relations as objects. The hierarchies are unary.

• The notation of first order logic is superior to the ad hoc notations that have been invented. Decideable subsets of first order logic are readily designated.

• XML isn’t a language but a notation. A language includes a set of predicate symbols that are intended to be given meaning.