Preferential Logic

Origin. Kraus, Lehmann, Magidor (1990). KLM framework. Ranked models. Non-monotonic consequence. Foundation of defeasible reasoning.

Models. Preferential structures. States with ordering. Most normal worlds. Conditional assertions. Ranked interpretations.

Formalism.

Preferential model: ⟨S, l, ≺⟩ where: S: states. l: S → 2^Atoms (labeling). ≺: strict partial order (preference). Minimal states satisfy conditionals.

Preferential consequence: α |~ β: "if α, normally β." True iff minimal α-states satisfy β. Non-monotonic. Defeasible.

KLM postulates: Reflexivity: α |~ α. Left Logical Equivalence: if ⊢ α ↔ β, then (α |~ γ iff β |~ γ). Right Weakening: if α |~ β and ⊢ β → γ, then α |~ γ. And: if α |~ β and α |~ γ, then α |~ β ∧ γ. Or: if α |~ γ and β |~ γ, then α ∨ β |~ γ. Cautious Monotonicity: if α |~ β and α |~ γ, then α ∧ β |~ γ.

Rational monotonicity: If α |~ γ and α |/~ ¬β, then α ∧ β |~ γ. Stronger than preferential. Ranked models.

System P: Preferential consequence relation. Characterized by preferential models. Weakest reasonable system.

System R: Adds rational monotonicity. Ranked models. Lexicographic closure.

Symbols.

Metatheory. Kraus, Lehmann and Magidor (1990) proved the representation theorem that fixes the subject: a consequence relation satisfies System P — reflexivity, left logical equivalence, right weakening, And, Or, cautious monotony and cut — if and only if it is generated by some preferential model ⟨S, l, ≺⟩ in which every satisfiable formula has a ≺-minimal state. That smoothness condition is not cosmetic; without it minimal states can fail to exist and completeness breaks. Dropping Or gives the weaker System C, characterized by cumulative models. Adding rational monotony gives System R, and Lehmann and Magidor (1992) proved that R is exactly the class of relations generated by ranked models, whose preference order is modular. System P coincides with Adams' probabilistic ε-semantics, so one relation has both a qualitative and a probabilistic characterization. Deciding whether a conditional is P-entailed by a finite conditional knowledge base is co-NP-complete, no harder than classical propositional entailment, and the rational closure of such a base is unique and computable with polynomially many satisfiability tests.

Applies to. Non-monotonic reasoning. Default logic. AI. Commonsense reasoning.

Limitations. System P licenses nothing across irrelevant additions: from bird |~ flies it does not follow that bird ∧ red |~ flies, so the weakest reasonable system is too weak for the inheritance it was built to explain. Rational monotony supplies exactly that step, but the rational closure it underwrites drowns exceptional subclasses — a penguin, being abnormal as a bird, forfeits every default birds inherit, including those to which penguins are no exception. Rationality is not preserved under intersection: the intersection of two rational consequence relations need only be preferential, so there is no canonical rational relation extending a conditional base without a further stipulation. The framework relates propositional formulas only; |~ is a relation in the metalanguage, not a connective, so conditionals cannot be nested, negated or quantified over. Nothing in a conditional knowledge base determines the preference order, which must come from a separate ranking construction.

© 2026 Lingenic LLC