Textbook of AI

Circumscription (McCarthy 1980) is a non-monotonic reasoning formalism. Given a logical theory $T$ and predicate $P$, the circumscription of $P$ in $T$ is the assertion that $P$'s extension is minimal subject to $T$. In effect: "$P$ holds only where it must".

Standard use: encode defaults via abnormality predicates. "Birds fly unless abnormal":

$$\forall x.\ \mathrm{Bird}(x) \wedge \neg \mathrm{Ab}(x) \rightarrow \mathrm{Flies}(x)$$

Circumscribing $\mathrm{Ab}$ minimises which entities are abnormal, defaults to "all birds fly" unless a specific entity is independently asserted abnormal.

Formal semantics: circumscribing $P$ in $T(P)$ means the only models considered are those in which the extension of $P$ is minimal among all models of $T(P)$. Equivalently, second-order axiom

$$T(P) \wedge \forall P'. (T(P') \wedge P' \subseteq P) \rightarrow P' = P$$

Strengths:

• Captures common-sense default reasoning naturally.
• Cleaner than negation-as-failure for some applications.
• Provides logical semantics for reasoning under incomplete information.

Weaknesses:

• Computational complexity: second-order logic is undecidable.
• Some seemingly-natural circumscriptions produce counter-intuitive results.
• Practical implementations require restricted forms (predicate completion, prioritised circumscription).

Circumscription was an important formalism in 1980s-1990s symbolic AI's attempts to formalise commonsense reasoning. Modern AI handles common sense statistically via LLMs rather than logically; circumscription is now mostly historical, though still relevant in some formal-verification and answer-set programming contexts.