Day 2: Tuesday, August 13th 2013

Introduction to Belief Revision

Belief revision is a topic of much interest in theoretical computer science and logic, and it forms a central problem in research into artificial intelligence. In simple terms: how do you update a database of knowledge in the light of new information? What if the new information is in conflict with something that was previously held to be true? 

Gärdenfors, “Belief Revision”

A logical approach to belief-revision has been proposed in the so-called AGM framework, where the beliefs of an agent are represented as a logically closed set of sentences of a particular language. A (new) belief-representing sentence gets introduced to the set and causes a belief change, which often leads to the necessity of removals to keep the beliefs consistent. AGM theory provides a set of axioms that put some rationality constraints on such revisions and allow the evaluation of various belief-revision policies. Presently, a direction of combining the belief-revision framework with modal logics of knowledge and belief gives us a way to investigate revisions in a more linguistically-detached way. We will look at these problems from a recently developed perspective of dynamic epistemic logic. The latter comprises a family of logics of explicit informational actions and corresponding knowledge and belief changes in agents. The information ow consisting of update actions performed in a stepwise manner can be de ned as transformations of models. Those transformations can be studied and analyzed explicitly by combining techniques from epistemic, doxastic, and dynamic logic.


In this lecture we will discuss the basics of several theories of belief change. The choice of the topics here is by the relevance for the remaining part of the course.  We will start with the AGM approach (Alchourrón et al. 1985): we will discuss its basic principles, the rationality constraints and some of the shortcomings. In the second part we will go through the possible world semantics for belief that is based on the implausibility ordering on possible worlds. We will discuss various revision methods that change the ordering and hence the belief (Spohn 1988). In the last part we will discuss plausibility states and models that build the semantics of epistemic doxastic logic. We will explain basic ideas of belief dynamics in dynamic epistemic and dynamic doxastic logic (Baltag et al. 1998, Baltag and Smets 2006, van Benthem 2007).


  1. Alchourrón, C.E., Gärdenfors, P., and Makinson, D. (1985). On the Logic of Theory Change: Partial Meet Contraction and Revision Functions, The Journal of Symbolic Logic, Vol. 50, pp. 510-530.
  2. Alchourrón, C.E., and Makinson, D. (1985). On the Logic of Theory Change: Safe Contraction, Studia Logica, Vol. 44, pp. 405-422.
  3. Baltag A., Moss, L.S., and Solecki, S. (1998). The Logic of Public Announcements, Common Knowledge and Private Suspicions. Proceedings of TARK’98, 43-56. 1998. Morgan Kaufmann Publishers.
  4. Baltag, A., and Smets S. (2006). Conditional Doxastic Models: A Qualitative Approach to Dynamic Belief Revision. G. Mints and R. de Queiroz (eds.),  Electronic Notes in Theoretical Computer Science, 165: 5-21.
  5. Van Benthem, J. (2007). Dynamic Logic for Belief Revision, Journal of Applied Non-Classical Logics 2007(2): 129-155.
  6. Spohn, W. (1988). Ordinal Conditional Functions: A Dynamic Theory of Epistemic States, Causation in Decision, Belief Change, and Statistics, Vol. II, Brian Skyrms and William L. Harper (eds.), Dordrecht: Kluwer.