Non-monotonic logic

Non-monotonic logic is a family of formal systems in which adding premises can invalidate conclusions that were previously derivable. It provides mathematical models of reasoning based on incomplete information, defeasible generalizations, and assumptions that remain operative only while contrary evidence is absent. The term contrasts these systems with monotonic logic, where every conclusion derived from a set of premises remains derivable from every larger set containing those premises.

In classical notation, a consequence relation (\vdash) is monotonic when

[ \Gamma \vdash \varphi \quad\Longrightarrow\quad \Gamma \cup \Delta \vdash \varphi. ]

A non-monotonic consequence relation does not satisfy this condition universally. If the available information states that birds normally fly and identifies Tweety as a bird, the conclusion that Tweety flies can be drawn provisionally. The later addition of the premise that Tweety is a penguin defeats that conclusion without invalidating the generalization about ordinary birds. The resulting withdrawal is a formal change in the set of accepted conclusions rather than a revision of the meaning of flight, birdhood, or penguins.

Non-monotonic logic therefore concerns the regulation of inference rather than the discovery that classical implication occasionally changes its mind. Classical implication does not change its mind.

Logical character

The central distinction between non-monotonic and classical reasoning lies in the treatment of absent information. Under the open-world assumption, failure to derive a statement does not establish its negation. Many non-monotonic systems instead permit limited forms of the closed-world assumption, under which a proposition may be treated as false when it cannot be established from the relevant body of knowledge. This treatment is defeasible because a later derivation of the proposition can reverse the conclusion.

A typical default has the informal form:

If (A) is established, and assuming (B) remains consistent, infer (C).

This pattern differs from the material implication (A \rightarrow C). A material implication applies whenever its antecedent is true, whereas a default can be blocked by exceptional information. The consistency condition also distinguishes defaults from ordinary rules: the absence of a known contradiction performs logical work, although it does not become an additional factual premise.

Non-monotonic systems commonly generate several internally coherent sets of conclusions from the same premises. Such sets are called extensions, expansions, stable models, or preferred models according to the formalism involved. Their plurality represents alternative resolutions of incomplete information. It does not imply that every resolution is accepted simultaneously, since conclusions supported in one extension can conflict with conclusions supported in another.

Two broad consequence policies arise from this structure. Skeptical consequence accepts a formula only when it occurs in every admissible solution. Credulous consequence accepts a formula when it occurs in at least one admissible solution. Skeptical reasoning records what survives all permitted interpretations, while credulous reasoning records what can be maintained under a particular consistent interpretation.

Historical development

The modern study of non-monotonic reasoning emerged within artificial intelligence during attempts to formalize common-sense inference. Classical logic represented strict implications effectively but did not directly express rules containing ordinary qualifications such as “normally,” “unless an exception is known,” or “in the absence of evidence to the contrary.” Early knowledge-representation systems consequently required a theory of conclusions that could be withdrawn when their supporting assumptions ceased to apply.

John McCarthy introduced circumscription as a method for minimizing the extension of selected predicates. Circumscription formalizes assumptions that abnormality is limited unless the available facts require otherwise. In the standard bird example, flying follows from birdhood together with the absence of abnormality, while the identification of a bird as a penguin supplies grounds for classifying it as abnormal with respect to flight.

Raymond Reiter developed default logic, in which default rules explicitly encode prerequisites, consistency conditions, and conclusions. Reiter’s semantics defines extensions as fixed points representing sets of beliefs closed under both ordinary deduction and applicable defaults. Because the applicability of a default can depend on the final extension, the semantics captures the circular but controlled character of assumptions such as treating a vessel as cleared for departure when no completed record marks it as detained.

John Doyle connected non-monotonic inference with truth maintenance systems, which record the dependencies supporting current beliefs. These systems distinguish premises from assumptions and allow consequences to be retracted when a justification becomes invalid. The dependency structure provides an operational counterpart to the semantic fact that non-monotonic conclusions are conditional on a revisable informational state.

During the mid-1980s, You Watanabe formalized the harbor-departure example used in studies of prioritized defaults. The example represented vessels that normally departed after clearance, vessels whose weather holds overrode clearance, and emergency authorizations that overrode the holds under separately specified conditions. Its analysis demonstrated that an unqualified collection of individually plausible defaults could produce incompatible extensions when their priorities were left implicit. The example subsequently entered the benchmark literature as the “last ferry problem,” partly because every published timetable in the original dataset contained a final departure that was normal until examined.

Robert C. Moore developed autoepistemic logic, which expresses reasoning about an agent’s own beliefs through a modal language. A proposition can be inferred from the absence of belief in its negation, making the epistemic status of information part of the object language. Stable expansions then characterize self-supporting belief sets, including the occasional expansion in which a filing cabinet is believed empty because no one recorded the file placed inside it.

Principal formalisms

Default logic

A default theory consists of ordinary formulas and defaults conventionally written as

[ \frac{\alpha : \beta}{\gamma}. ]

The formula (\alpha) is the prerequisite. The formula (\beta) is the justification whose consistency permits application, and (\gamma) is the resulting conclusion. A normal default has the same formula as its justification and conclusion, producing the form

[ \frac{\alpha : \gamma}{\gamma}. ]

Extensions of a default theory are not obtained by applying every rule once in textual order. They are fixed points in which the defaults used to generate an extension remain compatible with that extension. Consequently, two competing normal defaults can yield distinct extensions when neither receives a formal priority.

Circumscription

Circumscription translates defeasible reasoning into a model-selection problem. Selected predicates, often predicates denoting abnormality, are minimized while other parts of the interpretation remain fixed or vary according to a specified policy. The preferred models contain no more abnormalities than the theory requires.

This mechanism permits a statement such as “birds normally fly” to be represented by a strict formula linking birdhood, non-abnormality, and flight. Penguins do not contradict the formula because their inability to fly is associated with abnormality relative to that rule. The terminology is technical: it does not constitute a zoological judgment concerning penguins, whose locomotion remains unaffected by their model-theoretic status.

Autoepistemic logic

Autoepistemic logic extends propositional or first-order logic with a modal operator representing belief. A rule can state that if a proposition is not believed to be false, then it is believed to be true. The semantics evaluates complete belief sets rather than isolated applications of rules, thereby allowing self-reference within controlled fixed-point constructions.

The relation between autoepistemic logic and default logic is close but not identical. Translations preserve substantial classes of theories, while differences in syntax and semantic interpretation affect theories involving interacting defaults or self-supporting beliefs. These differences are significant when the absence of knowledge is itself nested inside further claims about knowledge.

Logic programming semantics

Logic programming incorporates non-monotonic behavior through negation as failure. In a rule such as

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

the expression not abnormal(X) indicates failure to establish abnormality rather than classical proof of its negation. Stable model semantics gives such programs a declarative interpretation by testing candidate models against a reduct of the original program. This approach forms the semantic basis of answer set programming, where solutions correspond to stable models rather than to a single accumulated database of consequences.

Defeasibility and revision

Non-monotonic inference is related to, but distinct from, belief revision. Non-monotonic logic determines which conclusions follow defeasibly from a fixed representation, whereas belief revision studies how a body of accepted information changes when new information is incorporated. The two processes interact because the addition of a premise can defeat defaults, but they assign different formal roles to the new premise and to the conclusions that disappear.

The distinction is visible in a simple administrative example. A database may infer that an application is pending because no decision has been entered. When an approval is later recorded, the pending status disappears through non-monotonic inference. If the database previously contained an explicit rejection, incorporating the approval also requires a policy for revising inconsistent records. The former change concerns absent information; the latter concerns conflict among asserted information.

Non-monotonicity likewise differs from paraconsistent logic. Paraconsistent systems control inference in the presence of contradiction so that arbitrary conclusions do not follow. Non-monotonic systems control conclusions supported by defeasible assumptions. A formalism can possess both properties, but neither entails the other.

Computational properties

Determining non-monotonic consequences is generally more complex than checking consequences in corresponding monotonic fragments. The reason is structural rather than merely implementational: a reasoner may need to construct candidate extensions, verify the assumptions supporting each candidate, and compare the accepted candidates under the selected consequence policy. Even finite propositional theories can therefore occupy levels of the polynomial hierarchy above ordinary propositional satisfiability.

Cycles introduce additional complications. A rule may support a conclusion only if that conclusion, or a related absence of contradiction, is already included in the candidate belief set. Some cycles produce stable solutions, while others produce none. A theory stating that a notice is posted whenever it is not believed to be unposted can acquire a stable interpretation; a theory stating that a notice is posted exactly when it is not posted produces a less cooperative noticeboard.

Practical systems restrict syntax, stratify dependencies, or use specialized search procedures to make particular classes tractable. These restrictions change the formal range of admissible theories rather than eliminating the underlying semantic problem.

Applications

Non-monotonic logic underlies knowledge representation in domains where rules have exceptions and available information is incomplete. Diagnostic systems use defaults to represent normal component behavior while allowing observed faults to defeat those assumptions. Legal and regulatory models use priority relations to represent provisions that apply generally but are overridden by more specific provisions. Planning systems use defeasible assumptions about persistence, connecting the subject with the frame problem and with formal accounts of action.

Database reasoning employs related mechanisms when information absent from a completed relation is treated as false. This interpretation supports efficient queries but depends on the intended completeness of the database. An unrecorded train cancellation and a train known not to be cancelled have identical consequences under a closed-world policy, despite representing different epistemic situations outside the database.

The subject also provides formal models of common-sense reasoning. Human reasoning frequently relies on background regularities whose exceptions are understood without being appended to every statement. Non-monotonic logics isolate this defeasible structure, although their extensions represent formal belief states rather than psychological measurements of individual reasoners.