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. ¬L(Flies(Tweety)) ∧ Bird(Tweety) → Flies(Tweety)

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

Metatheory. Default logic: computing extensions is Σ₂ᵖ-complete. Circumscription: entailment is Π₂ᵖ-complete. Multiple extensions create non-determinism. Preferential semantics axiomatized (System P). Rational closure is unique but may lose information. Non-monotonic ≠ inconsistency-tolerant (different issue).

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. Multiple extensions → no unique answer. Computational complexity high. Integration with learning unclear. Frame problem partially but not fully solved. No single "right" nonmonotonic logic. Human reasoning doesn't exactly match any formalism.