Nonmonotonic Consequence Relations

Origin. Dov Gabbay, "Theoretical foundations for non-monotonic reasoning in expert systems" (in Krzysztof R. Apt, ed., Logics and Models of Concurrent Systems, Springer 1985), asked what minimal conditions a consequence relation must satisfy to represent a nonmonotonic logic and answered with three: reflexivity, cut, and weak monotonicity — the last renamed cautious monotony by David Makinson, whose "General theory of cumulative inference" (2nd International Workshop on Non-Monotonic Reasoning, Grassau 1988; LNCS, Springer 1989) independently developed the Tarski-style theory and gave Gabbay's postulates a semantics with a completeness proof. Sarit Kraus, Daniel Lehmann and Menachem Magidor, "Nonmonotonic reasoning, preferential models and cumulative logics" (Artificial Intelligence 44, 1990, 167–207), combined Gabbay's proof-theoretic line with the preference semantics Yoav Shoham had advocated and proved the representation theorems; Lehmann and Magidor, "What does a conditional knowledge base entail?" (Artificial Intelligence 55, 1992, 1–60), added the rational relations — rational monotony imported from the conditional axiom CV at Makinson's suggestion — and the rational closure. Makinson's Bridges from Classical to Nonmonotonic Logic (College Publications, 2005) is the monograph treatment.

Models. The abstract theory of consequence without monotony. A relation here is a set of conditional assertions α |~ β — read "if α, normally β" — in the metalanguage, and the theory studies it by the closure conditions it satisfies rather than only negatively, by the one rule it lacks — which is how Kraus, Lehmann and Magidor found the field describing it. The central finding is what survives the loss: cumulativity, the conjunction of cut and cautious monotony, which says that if α |~ β then α and α ∧ β have exactly the same consequences — a conclusion once drawn can be added to the premises without adding or removing anything else. Above that floor the postulates form a hierarchy, each level matched to a class of preference orders by a representation theorem, and the hierarchy is the instrument by which the concrete knowledge-representation systems — default logic, circumscription, autoepistemic logic, answer set programming — are measured. Those systems are individuated by their representation problems and live in Applications/Knowledge; here the induced relation itself is the object, placed in Structural because monotony is the consequence-level form of weakening as transitivity is of cut, making this subdivision the counterpart of Nontransitive.

Formalism.

Conditional assertions: α |~ β: α antecedent, β consequent. A consequence relation is a set of such assertions. Not a connective: |~ cannot be nested, negated, or quantified.

System C (cumulative) — Gabbay's floor: Reflexivity: α |~ α. Left Logical Equivalence: if ⊨ α ↔ β and α |~ γ, then β |~ γ. Right Weakening: if ⊨ α → β and γ |~ α, then γ |~ β. Cut: if α ∧ β |~ γ and α |~ β, then α |~ γ. Cautious Monotony: if α |~ β and α |~ γ, then α ∧ β |~ γ. Cautious monotony: adding a drawn conclusion removes no conclusions. Cut: adding it yields no new ones. Together: if α |~ β, the consequences of α and of α ∧ β coincide.

System CL: Loop: if α₀ |~ α₁, α₁ |~ α₂, …, αₖ₋₁ |~ αₖ, αₖ |~ α₀, then α₀ |~ αₖ. Assertions arranged in a loop are pairwise equivalent.

System P (preferential): Adds Or: if α |~ γ and β |~ γ, then α ∨ β |~ γ. Derived already in C: And, modus ponens in the consequent. Derived in P: proof by cases, the hard half of the deduction theorem (from α ∧ β |~ γ infer α |~ β → γ), and Loop. Equivalent axiomatization: Reflexivity, LLE, RW, And, Or, Cautious Monotony.

System R (rational): Adds Rational Monotony: if α |~ γ and α |/~ ¬β, then α ∧ β |~ γ. From P to R, each step strict: negation rationality < disjunctive rationality < rational monotony.

The monotonic end: CM = C + monotony: monotonic yet weaker than classical logic; stronger than CL, incomparable with P. M = C + contraposition: classical consequence.

What C rejects: Given C, monotony, transitivity and the easy half of the deduction theorem (from α |~ β → γ infer α ∧ β |~ γ) are equivalent; contraposition implies them. All four fail.

Models: Cumulative model: ⟨S, l, ≺⟩ — states S, labelling l from states to nonempty sets of worlds, ≺ any binary relation, smooth. Smoothness: for each formula, every state satisfying it is ≺-minimal among those states or lies above one that is. Cumulative ordered model: ≺ a strict partial order. Preferential model: l assigns a single world to each state. Ranked model: ≺ modular — a ranking function r : S → Ω, Ω totally ordered, with s ≺ t iff r(s) < r(t). α |~ β holds in a model iff every ≺-minimal state satisfying α satisfies β.

Rational closure (Lehmann–Magidor): α exceptional for K iff the material counterparts α → β of K classically entail ¬α. C₀ = K; Cᵢ₊₁ = the assertions of Cᵢ with exceptional antecedent. rank(α) = least i such that α is not exceptional for Cᵢ. Closure: α |~ β iff rank(α) < rank(α ∧ ¬β), or α has no rank. Unique when it exists; exists for every finite K.

The structural reading: Monotony — from β |~ γ and ⊨ α → β infer α |~ γ — is the consequence-level form of weakening on the left, as transitivity is of cut. The now-usual cut (from α ∧ β |~ γ and δ |~ β infer α ∧ δ |~ γ) implies monotony; KLM's cut, with the second antecedent contained in the first, is close to Gentzen's Schnitt and does not. These relations keep reflexivity and that cut and drop monotony — strict-tolerant logic keeps weakening and drops cut.

Symbols.

Metatheory. Kraus, Lehmann and Magidor (1990) proved the representation theorems that fix the hierarchy: a relation satisfies C iff it is defined by a cumulative model, CL iff by a cumulative ordered model, and P iff by a preferential model — smoothness doing the work in each case, since it is exactly what the soundness of cautious monotony requires, a condition akin to the limit assumption of Stalnaker and Lewis in a more general setting. Lehmann and Magidor (1992) proved that a relation is rational iff it is defined by a ranked model, by a finite one when the language is finite, and that the theorem fails if the models are required to be well-founded. On finite bases preferential entailment coincides with Adams' probabilistic ε-entailment, and the coincidence fails for infinite bases (Lehmann–Magidor); on Horn assertions P proves no more than CL (KLM). Preferential entailment from a finite conditional base is co-NP-complete; entailment by all ranked models collapses back to preferential entailment, and the intersection of the rational extensions of a base is its preferential closure, so there is no least rational extension (Lehmann–Magidor). The rational closure answers this: unique when it exists, existing for every finite base, cumulative as an operation, and computable with O(n²) propositional satisfiability decisions — polynomial time outright on Horn assertions. Against the concrete systems the postulates discriminate sharply: circumscription satisfies cut and cautious monotony when the models to be considered are finite but fails negation rationality (KLM, by an example due to Lehmann, simplified by Ginsberg), hence rational monotony too; Reiter's default logic satisfies cut but fails cautious monotony even for normal defaults (Makinson 1989), so skeptical default consequence is not cumulative. The connection to conditional logic is exact and was KLM's own observation: P is the flat, non-nested fragment of the conditional system 𝒮 of Burgess, its rules matching the conditional axioms ID, RCEA, RCK, CSO and CA, with rational monotony matching CV; Craig Boutilier, "Conditional logics of normality: a modal approach" (Artificial Intelligence 68, 1994), rebuilt the preferential systems inside modal conditional logic.

Applies to. The postulates as the standard against which default logic, circumscription, autoepistemic logic and answer set programming are measured. Inference from conditional knowledge bases, through rational closure. Defeasible conditionals, as the flat fragment of conditional logic. The abstract side of the entries Default Logic, Circumscription, Preferential Logic and Answer Set Programming in Applications/Knowledge.

Limitations. The theory classifies relations and refuses to choose one: preferential entailment licenses nothing across irrelevant additions — from the base {p |~ q} the assertion p ∧ r |~ q does not follow — and since no least rational extension exists, the step from P to a usable rational relation is a construction, not a consequence of the postulates; Lehmann and Magidor's own second thesis asks only that any acceptable answer contain the rational closure. That closure lets no information about normal cases reach abnormal ones: a penguin, exceptional as a bird, loses every bird default including those to which penguins are no exception — the drowning problem, and Lehmann and Magidor left open the search for constructions with more inheritance. An infinite knowledge base may have no rational closure at all. The relation |~ lives in the metalanguage, so conditionals cannot be nested, negated or quantified, and the first-order case is left open by both founding papers. And the framework does not cover everything it was built to measure: skeptical default consequence fails cautious monotony, so for Reiter's logic the postulates are a standard it fails rather than a theory of it.

© 2026 Lingenic LLC