Circumscription is a non‑monotonic logic formalism introduced by John McCarthy in the 1970s as a method for commonsense reasoning in artificial intelligence. It allows an agent to infer that the objects or predicates satisfying a given property are exactly those that can be proven to do so, thereby “circumscribing” the set of abnormal or exceptional cases. This technique enables default assumptions and minimal models, making it central to reasoning about incomplete information, default reasoning, and knowledge representation in AI.
1 Definition and formal foundation
1.1 Core idea: Minimization of abnormality
The fundamental intuition behind circumscription is that the world should be assumed to contain only those abnormalities that can be proven to exist. In commonsense reasoning, many statements hold only by default; for example, “birds can fly” is true for most birds but admits exceptions like penguins. Circumscription formalizes this by minimizing the extension of a set of “abnormality” predicates. A conclusion is considered valid if it holds in all models that are minimal with respect to these predicates—i.e., models where as few objects as possible are considered abnormal.
1.2 First‑order logic formulation
Circumscription is usually expressed in first‑order logic with an additional second‑order axiom that states that the extension of certain predicates is minimal. Two main forms exist: predicate circumscription and domain circumscription.
1.2.1 Predicate circumscription
Given a theory \(T\) and a set of predicates \(P_1,\dots,P_n\) to be minimized, the circumscription of \(P_i\) in \(T\) is the second‑order formula:
\[ T(P) \land \neg\exists P' [ T(P') \land (P' \prec P) ] \]
where \(P' \prec P\) means that \(P'\) is pointwise less than or equal to \(P\) and strictly smaller in at least one component. This asserts that the predicates \(P\) have the smallest possible extension consistent with \(T\).
1.2.2 Domain circumscription
Domain circumscription minimizes the universe of discourse itself, assuming that only those individuals that are explicitly mentioned or deducible from the theory exist. It is expressed by a second‑order axiom that says there is no smaller domain satisfying the theory. This form is less common than predicate circumscription but is used when the domain is left open.
1.3 Minimal models semantics
The semantics of circumscription is based on minimal models. A model \(M\) of a theory \(T\) is called minimal (with respect to a set of predicates) if there is no other model \(M'\) of \(T\) such that the extension of each minimized predicate in \(M'\) is a subset of its extension in \(M\) (with at least one proper inclusion). A formula is a consequence of the circumscription of \(T\) if it is true in all such minimal models of \(T\).
1.4 Relationship to negation as failure
Negation as failure (NAF) is a procedural mechanism used in logic programming: a negative literal \(\neg p\) is assumed true if \(p\) cannot be proved. Circumscription provides a semantic justification for NAF. In many cases, the minimal model of a logic program corresponds exactly to the circumscriptive interpretation of its clauses, making circumscription a foundational model for default negation.
2 Variants and extensions
2.1 Parallel circumscription
In parallel circumscription, several predicates are minimized simultaneously. The second‑order axiom is written for a tuple of predicates, and minimality is required for all of them together. This is the most common variant and is used when multiple abnormality predicates are needed.
2.2 Prioritized circumscription
Prioritized circumscription assigns a partial order to the predicates being minimized. Predicates with higher priority are minimized first, and lower‑priority predicates are minimized only among those models that are already minimal for the higher‑priority ones. This allows a hierarchy of defaults (e.g., strict rules override weaker ones).
2.3 Pointwise circumscription
Pointwise circumscription minimizes predicates not only globally but also with respect to each individual argument. For a binary predicate \(P(x,y)\), pointwise circumscription would try to minimize \(P(x,y)\) for each fixed value of \(x\) separately. This variant is useful in temporal reasoning where the set of events is minimized per time point.
2.4 Second‑order versus first‑order approximation
Full circumscription is a second‑order formalism, which is computationally powerful but often undecidable. Many applications use first‑order approximations, such as the “stable model semantics” or “circumscription without second‑order quantification” achieved by imposing syntactic restrictions (e.g., the theory being a set of Horn clauses with negation). These approximations sacrifice some expressiveness but gain tractability.
3 Applications in artificial intelligence
3.1 Default reasoning and non‑monotonic inference
Circumscription is a natural framework for default reasoning. A typical default rule, such as “normally, birds can fly,” is represented by a first‑order implication with an abnormality predicate: \(\text{Bird}(x) \land \neg \text{Ab}(x) \rightarrow \text{Flies}(x)\). Minimizing \(\text{Ab}\) yields the conclusion that any bird not known to be abnormal can fly. This allows the system to retract conclusions when new information about exceptions is added.
3.2 Frame problem and situation calculus
In the situation calculus, actions change the world, but most facts remain unchanged. Circumscription is used to formalize the commonsense law of inertia: things stay the same unless acted upon. By minimizing the predicate \(\text{Ab}(a,s,f)\) (meaning action \(a\) changes fluent \(f\) in situation \(s\)), one obtains that only explicit effects of actions are considered, solving the frame problem.
3.3 Diagnosis and abduction
In model‑based diagnosis, a system’s behavior is described by a set of first‑order formulas. Faulty components are assumed abnormal. Circumscribing the abnormality predicate yields a minimal set of components that must be faulty to explain the observed symptoms. This corresponds to abductive reasoning: the smallest explanation is preferred.
3.4 Natural language understanding
Circumscription supports the resolution of lexical and pragmatic ambiguities in natural language. For example, the interpretation of definite descriptions (“the king of France”) is often handled by domain circumscription, assuming that the intended referent exists unless proven otherwise. It also aids in resolving anaphora by minimizing the set of possible antecedents.
4 Relationship to other non‑monotonic logics
4.1 Comparison with default logic
Default logic, introduced by Raymond Reiter, represents defaults as inference rules of the form “if \(P\) and it is consistent to assume \(Q\), then conclude \(R\).” Circumscription and default logic are related but not identical. Circumscription typically yields a single set of minimal models, whereas default logic can produce multiple extensions. For certain classes of theories (e.g., normal defaults without prerequisites), they coincide, but in general they capture different intuitions about the meaning of default statements.
4.2 Comparison with autoepistemic logic
Autoepistemic logic formalizes the beliefs of a rational agent who introspects on what is known. It uses a modal operator to represent knowledge (e.g., \(\neg K p \rightarrow \neg p\)). Circumscription’s minimization of abnormality can be translated into a form of autoepistemic reasoning, but the two logics differ in their treatment of introspection and the closure of beliefs. Autoepistemic logic is better suited for representing explicit knowledge, while circumscription focuses on syntactic minimality.
4.3 Comparison with the closed‑world assumption
The closed‑world assumption (CWA) states that any positive literal not derivable from a database is considered false. The CWA is a special case of circumscription for Horn theories without existential quantifiers. In general, circumscription is more expressive because it can minimize predicates selectively and handle disjunctive information. The CWA corresponds to circumscribing all predicates simultaneously with domain closure.
4.4 Integration with answer‑set programming
Answer‑set programming (ASP) is a logic programming paradigm based on the stable model semantics. The stable models of a logic program correspond precisely to the minimal models of its circumscription (under a certain translation). Modern ASP solvers implement algorithms that compute circumscriptive models efficiently, making circumscription a theoretical backbone of practical ASP systems.
5 Practical implementations and computational aspects
5.1 Complexity of circumscription
Evaluating circumscription is computationally hard. The second‑order quantification can lead to undecidability in general, and even for first‑order approximations the problem is often at the second level of the polynomial hierarchy (e.g., \(\Sigma_2^P\)-complete). For propositional circumscription, the problem of checking whether a formula is a consequence of a circumscribed theory is co‑NP-complete (for restricted cases) or even harder.
5.2 Reduction to classical logic satisfiability
Despite its inherent complexity, circumscription can be reduced to classical satisfiability in some important cases. For finite propositional theories, the circumscription axiom can be encoded as a set of clauses using a “pure” second‑order quantifier elimination algorithm. This allows the use of standard SAT solvers to compute minimal models, although the reduction may blow up exponentially.
5.3 Tools and reasoning systems
Several reasoning systems support circumscription either directly or indirectly. The most prominent are ASP solvers (e.g., Clingo), which implement a form of circumscription via the stable model semantics. Prototype implementations for full circumscription include the Circ system and theorem provers that handle second‑order logic, such as LEO‑II. In recent years, circumscription has also been encoded in first‑order logic by using inductive definitions and fixpoint operators.
6 Limitations and critiques
6.1 Difficulty of second‑order quantification
The use of second‑order logic makes circumscription difficult to compute and reason about. Most automatic theorem provers cannot handle second‑order formulas directly, and human users find it hard to write and understand second‑order axioms. This has limited the adoption of circumscription to cases where it can be approximated by first‑order or propositional techniques.
6.2 Expressiveness versus tractability trade‑off
Circumscription offers a rich formalism for commonsense reasoning, but its high computational cost often forces users to choose weaker, more tractable variants. The trade‑off between expressiveness (e.g., handling default reasoning with multiple exceptions) and tractability (e.g., polynomial‑time reasoning for Horn theories) is a central challenge. Many AI applications prefer simpler non‑monotonic formalisms like NAF or default logic, which can be implemented more efficiently.
6.3 Alternatives and modern developments
Contemporary research has explored alternatives that retain some of circumscription’s insights while improving computational behavior. These include circumscription in description logics (for the Semantic Web), the use of inductive definitions in logic programming, and the family of “preferential” logics based on orderings of models. The rise of deep learning and neural‑symbolic methods has also shifted attention away from purely logical approaches. Nevertheless, circumscription remains an influential theoretical framework for understanding default reasoning and minimality in AI.