Circumscription

Origin. John McCarthy introduced circumscription (1980) as a formalization of the closed-world assumption and non-monotonic reasoning. "Minimize the extension of abnormality predicates." A form of default reasoning via model-theoretic minimization. Influential in AI knowledge representation alongside default logic and autoepistemic logic.

Models. Reasoning with minimal models. Classical logic can't express "typically" or "unless otherwise stated." Circumscription adds a preference for models where certain predicates have minimal extensions. "Birds fly unless abnormal; assume minimal abnormality." Conclusions hold in all minimal models, not all models.

Formalism.

Basic idea: Given theory T and predicate P to minimize, prefer models where P's extension is smallest (⊆-minimal).

Circumscription of P in T: CIRC[T; P] = T + "P has minimal extension consistent with T"

Second-order formulation: CIRC[T; P] ≡ T(P) ∧ ¬∃P'[T(P') ∧ P' ⊂ P]

"T holds, and there's no smaller P' that also satisfies T."

Prioritized circumscription: Minimize P₁ first, then P₂ among P₁-minimal models, etc. CIRC[T; P₁ > P₂ > ... > Pₙ]

Variable predicates: Some predicates minimized, some fixed, some allowed to vary. CIRC[T; P₁,...,Pₙ; Z₁,...,Zₘ] Minimize P's, allow Z's to vary, fix others.

Example — Birds fly:

Bird(x) ∧ ¬Ab(x) → Flies(x)
Bird(Tweety)
Bird(Opus) ∧ Penguin(Opus)
Penguin(x) → Ab(x)

Circumscribe Ab: minimal abnormality. Result: Ab(Opus), ¬Ab(Tweety), Flies(Tweety), ¬Flies(Opus).

Pointwise circumscription: For each individual separately, assume normality unless forced otherwise.

Formula circumscription: Minimize formulas, not just predicates.

Symbols.

Symbol	Unicode	Name	Meaning
CIRC	—	Circumscription	Minimization operator
Ab	—	Abnormality	Predicate to minimize
⊂	U+2282	Proper subset	Strictly smaller extension
⊆	U+2286	Subset	Smaller or equal extension
>	—	Priority	Minimize first
∃P	—	Second-order ∃	Quantify over predicates
min	—	Minimal	Minimal extension

Metatheory. Circumscription is second-order; checking if φ follows from CIRC[T; P] is undecidable in general. For propositional case: Π₂ᵖ-complete. Circumscription can be reduced to first-order in some cases (when predicate completion works). Related to default logic but model-theoretic rather than proof-theoretic. Parallel/prioritized circumscription gives different results.

Applies to. Commonsense reasoning. Default reasoning. Diagnosis (minimize faults). Planning (minimize changes, frame problem). Legal reasoning (exceptions are minimized). Knowledge representation with closed-world assumptions.

Limitations. Second-order, computationally expensive. What to minimize is a modeling choice — wrong choices give wrong conclusions. Multiple minimization policies (parallel, prioritized, pointwise) give different results. Unlike default logic, no explicit representation of defaults. Interactions between minimized predicates are subtle. Less intuitive than explicit default rules.