Nonmonotonic Reasoning

Nonmonotonic reasoning is reasoning in which adding information can invalidate a previously warranted conclusion without requiring the withdrawal of the original premises. It formalizes provisional inference: conclusions are accepted under assumptions about what normally happens, what is not known, or which possibilities are preferred. The subject is central to knowledge representation and reasoning in artificial intelligence, especially the representation of incomplete knowledge and rules with exceptions. It encompasses several distinct logical frameworks rather than a single universally accepted calculus. (sciencedirect.com)

Monotonicity and defeasible conclusions

In classical logic, logical consequence is monotonic. If a set of premises $\Gamma$ entails a proposition $\varphi$, adding premises preserves that entailment:

A nonmonotonic consequence relation, often written $\mathrel{\sim}$, need not satisfy this condition. There may be propositions for which

“Nonmonotonic” means that such a loss of consequence is possible, not that every addition of information changes the conclusions. (u.cs.biu.ac.il)

A standard illustration concerns birds and flight. Suppose a knowledge base states that Tweety is a bird and that birds normally fly. It may provisionally conclude that Tweety flies. Learning that Tweety is a penguin defeats this conclusion, while leaving intact the fact that Tweety is a bird. Merely withdrawing “Tweety flies” is not equivalent to deriving its negation; the latter requires additional support, such as a rule that penguins do not fly. This illustrates defeasible reasoning: an inference can be warranted yet remain subject to defeat. (u.cs.biu.ac.il)

Historical development

The field developed through attempts to represent commonsense reasoning in computer programs. Jon Doyle’s 1979 work on truth maintenance systems described mechanisms for recording the reasons behind beliefs and revising assumption-dependent conclusions. In 1980, Raymond Reiter introduced default logic, while John McCarthy published circumscription, establishing two influential approaches to formal nonmonotonic inference. (sciencedirect.com)

Robert C. Moore’s 1985 treatment of autoepistemic logic formalized reasoning about an agent’s own beliefs. Michael Gelfond and Vladimir Lifschitz introduced stable-model semantics for logic programs in 1988. In 1990, Sarit Kraus, Daniel Lehmann, and Menachem Magidor developed a systematic study of nonmonotonic consequence relations and preferential models, commonly called the KLM framework. These developments connected rule-based, epistemic, and model-theoretic approaches without making their semantics identical. (sciencedirect.com)

Principal frameworks

Default logic

Default logic supplements ordinary background statements with rules whose applicability depends on consistency. In Reiter’s notation, a default has the form

Its prerequisite is $\alpha$, its justifications are $\beta_1,\ldots,\beta_n$, and its conclusion is $\gamma$. Roughly, it licenses $\gamma$ when $\alpha$ is established and the justifications remain consistent with the resulting body of beliefs. Applicability is therefore not merely a check against the initial facts. (sciencedirect.com)

For example,

expresses a default that a bird flies unless that supposition is contradicted. A default theory can have several extensions: alternative, self-consistent sets of conclusions generated by its facts and defaults. Some theories have no extension. These possibilities make extension selection and the treatment of conflicting defaults part of the semantics. (sciencedirect.com)

Circumscription

Circumscription represents default assumptions by minimizing selected predicates in models of a theory. For instance, a rule can state that birds fly unless they are abnormal in a relevant respect:

Minimizing the abnormality predicate favors interpretations with as few exceptions as the explicit information permits. Additional facts can force exceptions and change the conclusions supported by the preferred models. (www-formal.stanford.edu)

The specification matters: a circumscription must identify what is minimized, what is held fixed, and what may vary. McCarthy’s 1986 formulation refined these distinctions and applied minimization to inheritance hierarchies and reasoning about actions. Circumscription thus changes which models count as relevant, rather than simply adding exception-sensitive rules to an otherwise unchanged consequence relation. (www-formal.stanford.edu)

Autoepistemic logic

Autoepistemic logic concerns an agent’s reasoning about its own beliefs. It uses a belief operator, conventionally $L$, so that $L\varphi$ means that $\varphi$ is believed. A formula such as

expresses an epistemic default: if $t$ is a bird and the agent does not believe that $t$ cannot fly, conclude that it flies. The absence of a belief is distinct from an explicit belief in the opposite proposition. The semantics uses stable expansions, which reconcile the theory with assumptions about what the agent believes and does not believe. (sciencedirect.com)

Logic programming and stable models

Logic programming provides another setting for nonmonotonic inference. A rule may contain negation as failure, represented schematically as:

flies(X) :- bird(X), not abnormal(X).

The expression not abnormal(X) is default negation, not an ordinary assertion of classical negation. Its treatment requires a semantics for the program as a whole. (cs.utexas.edu)

Under stable-model semantics, a candidate set $M$ of atoms determines a reduct. For a finite ground normal program, rules containing a default-negated atom belonging to $M$ are removed; the remaining default-negated conditions are then erased. The candidate is stable if it equals the least model of the resulting positive program. A program may have zero, one, or several stable models. This semantics underlies answer set programming, a declarative approach to knowledge-intensive search problems. (cs.utexas.edu)

Preferential consequence relations

Preferential semantics evaluates conclusions in the most preferred, or most normal, situations compatible with the premises. A conditional

holds when the relevant preferred $\alpha$-situations satisfy $\beta$. Adding information can change which situations are preferred, thereby defeating an earlier conclusion. The KLM framework connects semantic model conditions with structural properties of inference. It identifies several families of consequence relations rather than treating the failure of monotonicity as a sufficient description of reasoning behavior. (sciencedirect.com)

Alternative conclusions and controlled inference

When a theory admits multiple extensions, expansions, or stable models, two important reasoning policies are available:

• Credulous reasoning accepts a proposition if it belongs to at least one admissible outcome.
• Skeptical reasoning accepts it only if it belongs to every admissible outcome.

These policies answer different questions: whether a conclusion is supported by some coherent interpretation, or whether it survives all such interpretations. Cases with no admissible outcome require an explicit convention, because universal quantification over an empty collection can otherwise yield vacuous acceptance. (academic.oup.com)

Abandoning monotonicity does not require abandoning all structural discipline. KLM-style systems study properties such as cautious monotony: if $\alpha$ supports both $\beta$ and $\gamma$, then explicitly adding the already accepted conclusion $\beta$ should preserve $\gamma$. Together with a corresponding cut property, this supports cumulativity: making an accepted conclusion explicit does not change the conclusions. Such principles distinguish controlled defeasibility from arbitrary changes of belief. (u.cs.biu.ac.il)

Applications and implementation

Nonmonotonic reasoning supports the formalization of ordinary expectations without enumerating every possible exception. One application is the frame problem: representing what remains unchanged after an action. Persistence can be treated as a default, overridden by information about an action’s effects. Another is the qualification problem, in which an action’s success may depend on indefinitely many unstated conditions. Defaults allow normal circumstances to be assumed without treating them as exceptionless facts. (www-formal.stanford.edu)

Answer set programming develops these ideas into a computational paradigm. A problem is described by rules and constraints, and solutions are represented by answer sets. Its solver mechanisms draw on techniques associated with Boolean satisfiability, rather than simply following rules in their written order. Truth maintenance systems address a complementary implementation concern: retaining justifications so that conclusions depending on defeated assumptions can be revised and explained. (cs.utexas.edu)

Limitations and semantic choices

Nonmonotonic reasoning does not uniquely determine which defaults should prevail. Different formalisms express different commitments about consistency, normality, ignorance, and admissible belief states. Even closely related default and autoepistemic approaches use different semantic operators; a translation between them must therefore preserve a specified notion of consequence rather than merely reproduce similar-looking rules. (arxiv.org)

The choice of representation also affects results. Selecting predicates for minimization, permitting particular assumptions, or choosing skeptical rather than credulous inference can alter what follows. Recording these choices is essential to interpreting a system’s conclusions: a default conclusion is supported relative to its formal assumptions, not guaranteed to be true in every situation. (www-formal.stanford.edu)

Computational complexity is a further limitation. For unrestricted propositional Reiter default logic, deciding whether an extension exists and whether a proposition belongs to some extension are $\Sigma_2^P$-complete; deciding whether it belongs to every extension is $\Pi_2^P$-complete. These are worst-case results for specified reasoning tasks, not a single complexity classification for all nonmonotonic systems. They show that the difficulty of selecting coherent assumptions can exceed that of ordinary propositional consequence checking. (academic.oup.com)

References

1. Circumscriptionwww-formal.stanford.edu
2. Semantical Considerations on Nonmonotonic Logiciiif.library.cmu.edu
3. Vladimir Lifschitz: Selected Papers Published before 1996cs.utexas.edu
4. Nonmonotonic Reasoning, Preferential Models and Cumulative Logicsu.cs.biu.ac.il
5. Applications of Circumscription to Formalizing Common Sensewww-formal.stanford.edu
6. Applications of Circumscription to Formalizing Common Sense Knowledgewww-formal.stanford.edu
7. Thirteen Definitions of a Stable Modelcs.utexas.edu
8. What Is Answer Set Programming?cs.utexas.edu