Circumscription—A Form of Nonmonotonic Reasoning

John McCarthy’s circumscription paper proposes a way to reason from incomplete knowledge while allowing conclusions to be withdrawn. A planner may need to assume that a boat is usable without listing every possible obstacle, from missing oars to a leak. The qualification problem is that a rule specifying every condition for success becomes impractical, and further exceptions can still be imagined. Circumscription makes a selected assumption of completeness explicit.^[1]

Minimizing what the facts require

A predicate is a property or relation, such as being a block or preventing an action; its extension is the set of objects or tuples for which it holds. Given facts A involving a selected predicate P, predicate circumscription rules out a strictly smaller extension of P that would still satisfy A. In the paper’s model-theoretic treatment, the compared models keep the same domain and the other predicates fixed. This is minimality by set inclusion, rather than merely choosing the smallest numerical count.^[1]

The formal schema considers an alternative predicate Φ. If replacing P by Φ still satisfies A, and every tuple satisfying Φ also satisfies P, the schema requires the converse inclusion too. Thus Φ cannot be a proper subset of P. McCarthy proves that instances of this schema hold in models minimal in P; he also notes that minimal models do not always exist. This is a logical result under the stated semantics, rather than an evaluation of a deployed reasoning program.^[1]

For a simple example, suppose the facts assert that A, B, and C are blocks. Circumscribing the block predicate yields the conclusion that every block is one of those three. Ordinary first-order deduction from those assertions alone permits additional blocks; circumscription adds the completeness conjecture. The paper also distinguishes domain circumscription, which restricts which entities exist, and explains how it can be reduced to predicate circumscription.^[1]

Why conclusions can change

In the river-crossing puzzle, ordinary background knowledge permits use of the boat unless something prevents it. Circumscribing the prevention relation can support the conjecture that there is no unmentioned obstacle. Similarly, excluding unmentioned bridges restricts the available crossing plans. Once a bridge is explicitly added to the facts, the old conclusion that there is no bridge can no longer be drawn. This is nonmonotonic reasoning: more information can invalidate an earlier conclusion.^[1]

McCarthy distinguishes the convention of a puzzle from acting beside a real river. A puzzle normally excludes extra objects and alternatives; in an actual situation the same exclusion is a hypothesis. Reliability depends on what information the planner included before making it.^[1]

Representation and revision

The proposed reasoning program still needs domain-specific heuristics to choose which predicates and facts to circumscribe, and when to retract the resulting assumptions. Describing the same blocks world with different predicates—for example, a direct “on” relation, an “above” relation, or positions and heights—can produce different circumscriptive conclusions. Minimization therefore does not remove the design decisions about representation, relevance, or when to investigate further.^[1]

The paper was published in Artificial Intelligence 13 (1980), pages 27–39. The author-hosted reprint carries a 1986 header and a later addendum; McCarthy’s archive says his distinct 1986 Applications of Circumscription to Formalizing Common Sense Knowledge substantially supersedes this formalism, especially its treatment of variables not minimized. The 1980 publication and the later formalism should not be treated as interchangeable.^[1]

For Common-Sense Reasoning, the contribution is a precise account of selected, revisable completeness assumptions. Its connection to Outer Alignment remains limited: an agent’s assumptions about what can happen do not determine whose objectives it should pursue.