Belief Revision

Origin. Alchourrón, Gärdenfors, and Makinson introduced AGM theory (1985). Formalizes rational belief change. Three operations: expansion (adding belief), contraction (removing belief), revision (adding belief while maintaining consistency). Foundational for AI knowledge base maintenance and epistemology.

Models. Rational belief change. Agents have belief sets (logically closed). New information may conflict with existing beliefs. Revision prioritizes new information while minimizing change. Contraction removes beliefs while preserving as much as possible. Epistemic entrenchment orders beliefs by how firmly held.

Formalism.

Belief set: K = Cn(K) (closed under logical consequence) K ⊆ L (set of sentences)

Three operations:

Expansion K + φ = Cn(K ∪ {φ})
Contraction K - φ (remove φ, close)
Revision K * φ = (K - ¬φ) + φ (Levi identity)

AGM postulates for revision:

Closure: K * φ = Cn(K * φ)
Success: φ ∈ K * φ
Inclusion: K * φ ⊆ K + φ
Vacuity: if ¬φ ∉ K, then K * φ = K + φ
Consistency: K * φ is consistent if φ is consistent
Extensionality: if φ ↔ ψ, then K * φ = K * ψ 7-8. Superexpansion and subexpansion (for conjunctions)

Epistemic entrenchment: φ ≤ ψ means ψ is at least as entrenched as φ. Less entrenched beliefs are contracted first.

Iterated revision: Darwiche-Pearl postulates extend AGM to sequences of revisions.

Symbols.

Symbol	Unicode	Name	Meaning
K	—	Belief set	Agent's beliefs
+	—	Expansion	Add belief
-	—	Contraction	Remove belief
*	—	Revision	Add consistently
Cn	—	Closure	Logical consequence
≤	U+2264	Entrenchment	Belief ordering
⊥	U+22A5	Absurdity	Inconsistency

Metatheory. Representation theorem: AGM revision corresponds to selection functions on possible worlds. Epistemic entrenchment characterizes contraction. Grove's sphere semantics provides model-theoretic foundation. Complexity depends on base logic: for propositional knowledge bases, deciding K ∗ φ ⊨ ψ is Π₂ᵖ-complete under most of the standard operators (Eiter and Gottlob 1992), not coNP-complete — coNP is the cost of deduction from the unrevised base, and revision adds an alternation by quantifying over the maximal consistent remnants. Dalal's operator is the outlier at Θ₂ᵖ = P^NP[log n], since its cardinality-minimality can be resolved by binary search over an NP oracle.

Applies to. Database update and maintenance. AI reasoning under changing information. Philosophy of science (theory change). Legal reasoning (precedent and amendment). Preference change modeling. Multi-agent belief dynamics.

Limitations. Assumes logical omniscience (beliefs closed under consequence). Static: doesn't model belief over time intrinsically. Single-agent focus; multi-agent extensions complex. Entrenchment orderings must be specified. Iterated revision theory still developing. Computational cost for large belief bases.