Default Logic

Origin. Raymond Reiter introduced default logic (1980). A formalization of non-monotonic reasoning: conclusions that hold "by default" and can be retracted when contradicting information arrives. Part of the broader study of non-monotonic logics (circumscription, autoepistemic logic). Models commonsense reasoning where we reason with incomplete information.

Models. Defeasible inference. "Birds typically fly" — conclude flying unless you know otherwise. Unlike classical logic, adding premises can retract conclusions. Defaults are rules that apply when their prerequisites are met and nothing contradicts their justification.

Formalism.

Default rule: α : β₁, ..., βₙ ───────────── γ

Meaning: If α is believed, and each βᵢ is consistent with beliefs, then conclude γ.

• α: prerequisite (what must be known)
• β₁, ..., βₙ: justifications (what must be consistent)
• γ: consequent (what to conclude)

Example: Bird(x) : Flies(x) ───────────────── Flies(x)

"If x is a bird, and it's consistent that x flies, conclude x flies."

Default theory: A pair (D, W) where:

• W: set of first-order formulas (facts)
• D: set of default rules

Extension: A set of beliefs E closed under:

1. Classical consequence of W
2. Application of defaults whose prerequisites are in E and justifications are consistent with E

A default theory may have zero, one, or multiple extensions.

Types of defaults:

• Normal default: α : β / β (justification = consequent)
• Semi-normal: α : β ∧ γ / γ
• Non-normal: more complex justifications

Closed-world assumption as default: : ¬P(x) ──────── ¬P(x)

"If P(x) is not provable, assume ¬P(x)."

Skeptical vs credulous reasoning:

• Skeptical: believe only what's in ALL extensions
• Credulous: believe what's in SOME extension

Symbols.

Metatheory. Not all default theories have extensions (inconsistent defaults). Multiple extensions represent alternative reasonable conclusions. Checking if a formula is in some/all extensions is hard (Σ₂ᵖ-complete for credulous, Π₂ᵖ-complete for skeptical). Normal default theories always have extensions. Non-monotonic: adding facts can invalidate defaults.

Applies to. Commonsense reasoning. Incomplete databases (closed-world reasoning). Legal reasoning (defeasible rules). Diagnosis (assume normal unless evidence of fault). Planning under incomplete information. Agent beliefs with uncertainty.

Limitations. Multiple extensions are semantically natural but computationally challenging. Which extension is "correct" may be unclear. Priorities among defaults require extensions (prioritized default logic). Interaction with classical logic can be subtle. The formalism doesn't specify how to choose among extensions. Computationally expensive for large theories.

© 2026 Lingenic LLC