1 Introduction and Historical Context

Non‑monotonic reasoning is a branch of logic that permits conclusions to be withdrawn when new information is added. In classical (monotonic) logic, once a conclusion is derived from a set of premises, it remains valid regardless of any further premises. Non‑monotonic logics abandon this property to better capture the tentative, defeasible nature of human common‑sense reasoning, where people routinely draw conclusions that they later revise in light of new evidence.

1.1 Motivation from Common‑Sense Reasoning

Everyday reasoning is saturated with defaults: birds normally fly, most adults work during the day, and objects typically fall when dropped. These generalizations are useful but admit exceptions (e.g., a penguin is a bird that does not fly). Classical logic cannot gracefully model such exceptions without explicit qualification of every rule. Non‑monotonic reasoning emerged to handle this “frame problem” and the broader challenge of representing knowledge that is incomplete or subject to revision.

1.2 Early Work in the Late 20th Century

The formal study of non‑monotonic reasoning began in earnest around 1980, when several foundational formalisms were proposed nearly simultaneously.

1.2.1 McCarthy’s Circumscription (1980)

John McCarthy introduced circumscription as a logical method for minimizing the set of objects that satisfy a predicate. The idea is that “things are as normally as possible” – a default assumption that only the explicitly known abnormal individuals are abnormal. Circumscription uses second‑order logic to enforce minimal models, enabling representations like “birds fly unless they are abnormal in some respect.”

1.2.2 Reiter’s Default Logic (1980)

Raymond Reiter proposed default logic, which adds default rules of the form “if α is believed and it is consistent to believe β, then conclude γ.” A default theory consists of a set of first‑order formulas (facts) and a set of default rules. The semantics is defined through *extensions* – maximal sets of sentences that are closed under the defaults and the facts. This formalism became one of the most influential in the field.

1.2.3 Moore’s Autoepistemic Logic (1985)

Robert C. Moore developed autoepistemic logic to model the reasoning of an agent who reflects on her own knowledge. It uses a modal operator □ to mean “is known” and allows conclusions such as “if I don’t know that p, then I assume not p.” The semantics relies on *stable sets* – sets of formulas that are maximally consistent with the agent’s introspective knowledge.

2 Core Principles and Formal Definitions

2.1 Monotonicity vs. Non‑monotonicity

The central distinction between monotonic and non‑monotonic reasoning is the effect of adding premises.

2.1.1 Classical Monotonic Logic Overview

In classical propositional or first‑order logic, if a sentence φ is a logical consequence of a set of premises Γ (denoted Γ ⊨ φ), then for any superset Δ ⊇ Γ, it still holds that Δ ⊨ φ. This property – monotonicity – ensures that conclusions are permanent. It works well for mathematics but poorly for domains where knowledge is default‑based.

2.1.2 The Added Premise Problem and Defeasibility

Non‑monotonic logics introduce *defeasibility*: a conclusion may be overturned by new information. For example, from “Tweety is a bird” one may defeasibly infer “Tweety flies.” Adding “Tweety is a penguin” retracts that conclusion. This added‑premise problem is the hallmark of non‑monotonic reasoning and motivates the development of formalisms that allow revision.

2.2 Default Rules and Extensions

Default rules are the primary mechanism for encoding typical situations.

2.2.1 Closed‑World Assumption

A common practical default is the Closed‑World Assumption (CWA): if a fact is not known to be true, assume it is false. This is ubiquitous in database systems and logic programming. The CWA is itself a non‑monotonic rule – adding a new positive fact can invalidate earlier negative conclusions.

2.2.2 Default Theory Structure

A default theory (D, W) consists of a set W of first‑order formulas (the known facts) and a set D of default rules. Each default is written as α : β₁, …, βₙ / γ, where α is the prerequisite, βᵢ are justifications, and γ is the consequent. Intuitively: if α is known and each βᵢ is consistent with what is known, then conclude γ. An *extension* of the theory is a deductively closed set of sentences that includes W and is closed under applicable defaults, while also respecting consistency constraints.

2.3 Fixed‑Point Semantics

Many non‑monotonic formalisms can be understood via fixed‑point constructions, where conclusions are defined as the minimal sets satisfying certain properties.

2.3.1 Minimal Models and Stable Models

In circumscription, minimal models are those that minimize the extension of designated predicates. In logic programming, the *stable model semantics* (Gelfond and Lifschitz, 1988) defines answer sets as fixed points of a reduct operator. A stable model is a set of atoms that is exactly the set of conclusions derivable from the program when every negated atom is interpreted via the model itself.

2.3.2 Answer Set Programming (ASP) Roots

Answer Set Programming (ASP) is a declarative programming paradigm based on stable models. It emerged from the integration of logic programming with non‑monotonic reasoning. ASP allows the representation of defaults, constraints, and preferences, and has become a practical tool for solving combinatorial search problems.

3 Major Formalisms

3.1 Default Logic

Default logic (Reiter, 1980) is one of the most studied and applied non‑monotonic systems.

3.1.1 Normal vs. Semi‑Normal Defaults

A default is *normal* if its justification and consequent are identical (α : γ / γ). Normal defaults are simpler and always yield extensions, but they can be too permissive. *Semi‑normal* defaults have the form α : β ∧ γ / γ, where β is an additional constraint. They offer more control but may lack extensions.

3.1.2 Extensions and Preferred Extensions

A default theory may have zero, one, or many extensions. Multiple extensions correspond to multiple plausible worlds. Techniques like *preferred extensions* or *prioritized defaults* impose an ordering to select the most plausible one.

3.2 Circumscription

McCarthy’s circumscription is formulated in second‑order logic.

3.2.1 Predicate and Domain Circumscription

*Predicate circumscription* minimizes the extension of a given predicate (e.g., Ab(normal)). *Domain circumscription* minimizes the domain of discourse. The result is a sentence that says: “the only objects that are abnormal are those that must be abnormal according to the given axioms.”

3.2.2 Minimality and Abnormality

Circumscription defines a preference relation on models: a model M is preferred over N if the extension of the minimized predicate in M is a subset of that in N. The circumscribed theory is the set of formulas true in all minimal models. This captures the intuition that abnormal objects are as rare as possible.

3.3 Autoepistemic Logic

Autoepistemic logic (Moore, 1985) models an agent’s introspective reasoning.

3.3.1 Stable Sets and Introspective Belief

A set S of formulas is *stable* if it is deductively closed and satisfies two conditions: (i) if φ ∈ S then □φ ∈ S (positive introspection); (ii) if φ ∉ S then ¬□φ ∈ S (negative introspection). These stable sets represent the coherent beliefs of a rational agent.

3.3.2 Relation to Default Logic

Autoepistemic logic is closely related to default logic. Every default theory can be translated into an autoepistemic theory, and vice‑versa, under certain conditions. The stable sets of autoepistemic logic correspond roughly to extensions of default logic.

3.4 Defeasible Reasoning and Argumentation

A different line of work focuses on argumentation as a mechanism for handling conflicting defaults.

3.4.1 Defeasible Rules and Strict Rules

Defeasible logics (e.g., Nute, 1994) distinguish between *strict rules* (which cannot be defeated) and *defeasible rules* (which can be overridden by stronger counter‑arguments). For example, “birds fly” is a defeasible rule; “penguins do not fly” is a strict rule that trumps it.

3.4.2 Argumentation Frameworks (Dung’s Theory)

Dung (1995) proposed abstract argumentation frameworks consisting of arguments and attacks. An argument is acceptable if it is not attacked, or if all its attackers are themselves defeated. Various semantics (stable, preferred, grounded) define sets of collectively acceptable arguments. This purely abstract model has been used to unify many non‑monotonic systems.

4 Computational Aspects and Complexity

4.1 Decision Problems and Complexity Classes

Non‑monotonic reasoning is typically harder than classical deduction.

4.1.1 Complexity of Default Logic Inference

Deciding whether a formula belongs to at least one extension (brave reasoning) is Σ₂ᴾ‑complete; deciding membership in all extensions (cautious reasoning) is Π₂ᴾ‑complete. These high complexities reflect the need to check for consistency and fixed points.

4.1.2 Complexity of ASP (Answer Set Programming)

Answer set existence for propositional logic programs is NP‑complete. For more expressive programs (with disjunction, negation, or cardinality constraints) complexity can rise to Σ₂ᴾ‑complete. Despite this, modern ASP solvers handle many practical instances efficiently.

4.2 Algorithms and Implementations

4.2.1 System DLV and Clingo

Two major ASP systems are DLV (Datalog with Disjunction) and Clingo (based on the grounder Gringo and solver Clasp). They compile a logic program into a propositional form, then use SAT‑like or CDCL (Conflict‑Driven Clause Learning) algorithms to compute answer sets.

4.2.2 SAT‑based Approaches for Circumscription

Circumscription can be reduced to propositional satisfiability by iteratively checking minimal models. Tools like CIRC2SAT encode the circumscription axioms into SAT instances, enabling the use of state‑of‑the‑art SAT solvers.

5 Applications in Artificial Intelligence

5.1 Knowledge Representation and Reasoning

5.1.1 Representing Defaults in Expert Systems

Expert systems often embed non‑monotonic rules to handle exceptions. For instance, a medical diagnosis system may assume “if a patient has a fever, default diagnosis is infection” but retract that if a more specific test returns negative.

5.1.2 Handling Exceptional Knowledge

Default logic allows a knowledge base to include both general rules and specific exceptions. When contradictory information arises, the system can revise its beliefs gracefully.

5.2 Natural Language Understanding

5.2.1 Presupposition and Implicature

Many natural language phenomena, such as presupposition accommodation and conversational implicatures, are naturally modeled as non‑monotonic inferences. Listeners assume that speakers are cooperative and that the world is normal, retracting those assumptions only when forced by the discourse.

5.2.2 Commonsense Entailment

Determining whether a sentence is a plausible consequence of a text often requires default reasoning. For example, “John dropped the glass” normally entails “the glass broke”, but this conclusion can be defeated if the context mentions a special unbreakable glass.

5.3 Planning and Diagnostic Reasoning

5.3.1 Non‑monotonic Causal Reasoning

In AI planning, the frame problem is addressed by non‑monotonic causal laws: actions typically only change affected properties, and all other properties remain as they were (the “commonsense law of inertia”). This is formalized using circumscription or default logic.

5.3.2 Model‑Based Diagnosis

Diagnostic systems use non‑monotonic reasoning to infer that a component is faulty if it violates its expected behavior. The diagnosis problem is to find a minimal set of abnormal components that explains the observed symptoms – a direct application of circumscription.

6 Relationships to Other Logical Paradigms

6.1 Probabilistic Reasoning and Bayesian Networks

6.1.1 Qualitative vs. Quantitative Uncertainty

Non‑monotonic logic handles *qualitative* uncertainty – it reasons about typicality without numeric probabilities. Bayesian networks, in contrast, provide *quantitative* degrees of belief. Some work explores bridging these approaches, e.g., using default rules to derive qualitative constraints in probabilistic models.

6.1.2 Connection to Possibility Theory

Possibility theory, developed by Zadeh and Dubois & Prade, offers a graded alternative that can encode default rules. A possibility distribution ranks possible worlds; a default “if A then B” corresponds to the constraint that worlds where A∧¬B are less plausible than those where A∧B. This links to non‑monotonic reasoning via rankings.

6.2 Logic Programming and Negation as Failure

6.2.1 Stable Semantics for Logic Programs

The stable model semantics (Gelfond & Lifschitz) gave a clean non‑monotonic interpretation to negation‑as‑failure (NAF) in logic programming. A rule “p ← q, not r” is read as: if q is true and it is not provable that r is true, then p is true. This is a default rule with justification not r.

6.2.2 Well‑Founded Semantics

An alternative to stable semantics is the well‑founded semantics (Van Gelder, Ross, Schlipf), which defines a three‑valued model (true, false, undefined). It is more computationally tractable (polynomial time) but less expressive in representing multiple extensions.

7.1 Integration with Machine Learning

7.1.1 Neural‑Symbolic Approaches

Recent research aims to combine neural networks with non‑monotonic reasoning. For example, neural systems can learn rules from data, which are then refined by a symbolic reasoner that can retract conclusions when they conflict with new observations.

7.1.2 Learning Default Rules from Data

Inductive logic programming and statistical relational learning can automatically discover default rules (e.g., “most birds fly”). The challenge is to ensure that learned defaults are coherent and admit efficient non‑monotonic inference.

7.2 Temporal Non‑Monotonic Reasoning

7.2.1 Reasoning about Action and Change

The frame problem is a classic temporal non‑monotonic issue. Extensions of event calculus and situation calculus use circumscription or defaults to state that properties persist unless an action changes them.

7.2.2 Event Calculus and Non‑Monotonic Extensions

The event calculus (Kowalski & Sergot) has been augmented with default rules to handle concurrent actions, continuous change, and narrative contexts. Non‑monotonic reasoning is essential for deciding when a fluent ceases to hold.

8 Notable Criticisms and Limitations

8.1 Complexity and Scalability Issues

Most non‑monotonic formalisms have high computational complexity (NP‑hard or higher). This limits their application to large‑scale real‑world systems. Heuristics and approximations are often necessary, but they may sacrifice completeness.

8.2 Multiple Extensions and Ambiguity

Default theories often possess multiple extensions, each representing a different plausible world. Determining which extension to adopt can be ambiguous, and there is no universally accepted criterion for choosing among them. This can make non‑monotonic systems unpredictable in practice.

8.3 Lack of a Unified Framework

Despite many formalisms (default logic, circumscription, autoepistemic logic, argumentation), no single framework has emerged as the standard. Each has its own syntax and semantics, and translations between them are often cumbersome. This fragmentation hinders the development of general‑purpose non‑monotonic reasoning engines.