Nonmonotonic Logic

Origin. McCarthy introduced circumscription (1980). Reiter developed default logic (1980). McDermott and Doyle on nonmonotonic modal logic (1980). Addresses common-sense reasoning: conclusions may be retracted given more information. Central to AI knowledge representation.

Models. Defeasible conclusions. Classical logic: more premises → more conclusions (monotonic). Nonmonotonic: new information may invalidate old conclusions. "Birds fly" + "Tweety is a bird" → "Tweety flies." + "Tweety is a penguin" → withdraw "Tweety flies." Formalizes default reasoning.

Formalism.

Default Logic (Reiter): Default rule: α : β / γ "If α is provable and β is consistent, conclude γ."

Extensions: maximal consistent sets of conclusions. Multiple extensions possible (floating conclusions).

Circumscription (McCarthy): Minimize predicate P: assume P is false except where forced true. CIRC[T; P] = T ∧ ∀P'. [T(P'/P) ∧ P' ⊆ P → P ⊆ P']

"Abnormal" minimized: Ab(Tweety) only if proved.

Autoepistemic Logic: Modal operator L for "I believe." Fixed point: what a rational agent would believe. Bird(Tweety) ∧ ¬L(¬Flies(Tweety)) → Flies(Tweety) The negation inside L is essential: "if I do not believe Tweety doesn't fly, conclude it flies." Dropping it gives ¬L(Flies) → Flies, which has no stable expansion at all — believing the conclusion destroys its own premise.

Preferential semantics (KLM): Conditional φ |~ ψ: "normally, if φ then ψ." Preferential models: more normal worlds preferred. Axioms: reflexivity, left logical equiv, right weakening, cautious monotony, cut, OR.

Rational closure: Extend conditionals maximally while consistent. Rank worlds by abnormality.

Symbols.

Symbol	Unicode	Name	Meaning
\|~	—	Conditional	Normally
α : β / γ	—	Default	If α, β consistent, then γ
L	—	Believes	Modal belief
CIRC	—	Circumscription	Minimize extension
Ab	—	Abnormal	Exception predicate
≺	U+227A	Preference	More normal
∀	U+2200	Universal quantifier	Second-order quantifier in CIRC
⊆	U+2286	Subset	Comparison of predicate extensions
¬	U+00AC	Negation	Negated belief and negated abnormality
∧	U+2227	Conjunction	Joins premises in the schemas
→	U+2192	Material conditional	Object-language implication
P'	—	Predicate variable	Competing extension in the circumscription axiom

Metatheory. In the propositional case the major formalisms all sit at the second level of the polynomial hierarchy, one level above classical satisfiability, and for one reason: an extension or a minimal model must be guessed and then verified, and the verification is itself co-NP. Gottlob (1992) settled default logic: deciding whether a propositional default theory has an extension, and whether a formula lies in some extension, is Σ₂ᵖ-complete, while skeptical membership in every extension is Π₂ᵖ-complete; autoepistemic logic has the same pair of bounds. Eiter and Gottlob (1993) showed propositional circumscriptive inference Π₂ᵖ-complete. First-order circumscription is genuinely second-order and its consequence relation is not recursively enumerable, so no finitary complete proof system exists for it. Against these computational results stands the abstract theory: Kraus, Lehmann and Magidor (1990) proved that System P — reflexivity, left logical equivalence, right weakening, And, Or, cautious monotony and cut — is sound and complete for preferential models, and that adding rational monotony characterizes ranked models, whose consequence relations admit a unique rational closure.

Applies to. Common-sense reasoning in AI. Legal reasoning (default rules with exceptions). Diagnostic reasoning. Planning with incomplete information. Natural language understanding (Gricean reasoning). Inheritance networks. Ontology exception handling.

Limitations. Non-normal default theories can have no extension at all, in which case every formula follows vacuously on the skeptical reading, and theories with several extensions leave the choice between them undetermined by the theory. Makinson showed Reiter's default logic is not cumulative: adding a conclusion drawn from a theory back into the theory as a premise can change which extensions exist, so the consequence relation is not even well behaved under its own outputs. Circumscription can be inconsistent for a consistent theory whenever no model is minimal, since a descending chain of extensions leaves nothing to select; and it forces a modelling decision — which predicates are minimized, which vary, which are fixed — that the formalism itself supplies no principle for. System P is too weak to license any inference across irrelevant additions, and rational closure, which fixes that, drowns exceptional subclasses, stripping them of defaults they should inherit. Nonmonotonicity is orthogonal to inconsistency tolerance: these logics still explode from a contradiction.