Circumscription — A Form of Non-Monotonic Reasoning (1980)
Reference: John McCarthy (1980). “Circumscription — A Form of Non-Monotonic Reasoning.” Artificial Intelligence 13(1-2): 27-39. The author-hosted PDF (2004 reformatting) adds a 1996 addendum; file is mccarthy-circumscription1980.pdf. Disambiguated from the 1986 sequel Circumscription - Applications to Formalizing Common Sense Knowledge which introduces formula circumscription and the abnormality predicate. URL
Summary
McCarthy’s landmark treatment of the qualification problem: any common-sense rule (e.g. “a rowboat can be used to cross a river”) is subject to an open-ended list of possible defeaters (no oars, a leak, cannibals, a sea monster) that cannot plausibly be enumerated in advance. Standard first-order logic is monotonic — adding premises never removes conclusions — so it cannot support the everyday inference “no defeater mentioned, therefore none present.”
Circumscription is a formally specified rule of conjecture that licenses jumping to the conclusion that the objects (or tuples) shown to satisfy a predicate P are the only ones that do. Adding a sentence “There is a bridge upstream” then legitimately retracts the original conclusion — non-monotonicity is thus built in at the rule-of-conjecture level, not by weakening the logic itself. The paper explains predicate circumscription, shows how domain circumscription (minimal inference) is a special case, works through the missionaries-and-cannibals puzzle to show how circumscription blocks sea-monster-style pedantry, and connects the technique to default reasoning (Reiter), to THNOT in MICROPLANNER (Sussman et al.), and to McCarthy’s broader project of formalising common-sense knowledge in logic.
Together with Ascribing Mental Qualities to Machines and First Order Theories of Individual Concepts and Propositions, this is one of the three pillars of McCarthy’s logicist programme. Its non-monotonic commitment is directly inherited by the CBCL proposal (partial-understanding messages) and by Elephant 2000’s treatment of commitments and speech-act preconditions.
Key Ideas
- The qualification problem: common-sense rules have unbounded implicit preconditions that cannot be enumerated.
- Monotonicity of FOL is the obstacle; circumscription is a rule of conjecture over FOL, not a modification of its proof theory.
- Predicate circumscription: the tuples shown to satisfy P are all the tuples that do.
- Domain circumscription (minimal inference) subsumed as a special case.
- Non-monotonicity at the level of conjecture rather than entailment — new facts retract conjectures without breaking soundness of FOL.
- “Common-sense knowledge must be expressed in a form that says a boat crosses rivers unless something prevents it” — ontology must admit prevention-entities.
Connections
Conceptual Contribution