Changes of Mind: An Essay on Rational Belief Revision

Placeholder book cover

Neil Tennant, Changes of Mind: An Essay on Rational Belief Revision, Oxford University Press, 2012, 368pp., $117.00, ISBN 9780199655755.

Reviewed by Jiahong Guo and Lei Zhang, Beijing Normal University


In the last three or four decades, dynamic turns [1] have attracted scholars from various areas to questions about epistemic change. Perhaps dynamic epistemic logic [2] (DEL) in a broad sense and belief revision theory in the AGM tradition [3, 4] can be considered the two main approaches in dealing with belief change for normative theories, although the latter might be presentable in certain DEL languages [5]. According to the classical literature on belief revision mentioned in Hansson [6], it is reasonable to think (and probably well accepted) that there are three different types of belief change about static worlds for rational agents in the AGM tradition: expansion, contraction and revision. Tennant's book is mainly in the tradition of belief revision theory, although he puts forward a completely different starting point and a new method.

The main contents of this book are divided into three related parts: "Computational Considerations" (seven chapters, making up the main body of the book), "Logical and Philosophical Considerations" (three chapters), and "Comparisons" (two chapters). Overall, the book makes several major contributions to the literature. First, Tennant makes an interesting distinction between logical saints and paragons, and he takes the latter as the rational agents in the study of belief change. Next, he provides an intuitive, effective graphic tool, finite dependency networks (FDNs), to demonstrate the principles of rational belief change processes. Also, he has constructed the respective formalization and core logic. Since in FDNs all premise sets are finite, the computational results of Tennant's work are much better than those based on the logical saint tradition. They can be implemented in computer programs to better simulate actual belief change processes for real rational agents. Tennant also does this in a Prolog implementation, which allows many practical operations and testing of examples. FDNs can overcome many defects in the AGM tradition, such as the problems of recovery, minimal mutilation, success, and so on. Tennant also shows that the AGM revision operator has several serious -- even fatal -- problems. One of them is that there can be many other revision operators which satisfy all the AGM basic and supplementary postulates. Although the representation theorems are similar to that of AGM, these operators can be, intuitively, absolutely absurd.

Chapter 1 is an informative and pertinent introduction, describing basic concepts and features of belief revision. Tennant first presents his distinction between the notions of logical saint and logical paragon, and uses them to represent two different kinds of agents. The saints are logically omniscient, as in the tradition of epistemic logic [7]. Their belief sets are treated as infinite logically closed theories. The paragons can complete only a finite number of deductive steps in a limited time. According to Tennant, a paragon is always right about the logical proofs she constructs; but she is not presumed to be aware of every logical entailment, except for those that hold in effectively decidable systems of logic. He presents the paragon as more appropriate for the study of actual belief revision with respect to practical rational agents. Chapter 1 also describes some basic notions of belief-revision theory, including what constitute a belief set; different modes of belief change, such as contraction and expansion due to different changes in the doxastic status of a proposition; and rational belief revision requirements such as minimal mutilation and minimal bloating. Finally, Tennant states his main goal of giving a philosophically reliable, mathematically rigorous, and computational implementable belief revision theory, and introduces the topics and ideas that he will cover.

The next four chapters are the core of the book and provide detailed descriptions and demonstrations for the theory of FDNs. With its graphic representation approach, chapter 2 provides an informal description of the theory that is clear and easy to be understood. In the model of networks, nodes and strokes are the only elements in the domain, while arrows are just relations between nodes and strokes. Generally speaking, nodes, strokes and arrows are used to form a graph with which we can express a respective rational agents' belief system (belief scheme), where nodes represent beliefs, and steps express justificatory relationships between beliefs. For an agent, believing a proposition or not can be expressed by coloration of nodes. Whether or not a justificatory relation holds between the premise set and conclusion can be expressed by coloring the respective inference stroke. A whitened stroke says that the respective justificatory relation is not established. But according to Tennant, this does not mean that the deductive relation in the justificatory step has been abandoned. It remains in the agent's inference base. When an agent acquires the justificatory relation, she will know or be aware of it. It is clear that there are many steps that are not known by a particular agent. In addition, Tennant's account covers only single-conclusion justificatory relations in which each stroke has only one conclusion node.

Tennant then provides eight axioms for the arrow relations between nodes and strokes. These determine whether a given structure is a qualified model for a given agent's belief system. He also puts forward four coloration axioms for nodes and strokes, which specify the coloring relation on adjacent nodes and strokes. According to the epistemic interpretation given by Tennant, the first eight axioms characterize the overall structure of justificatory relations known by the given agent. The next four axioms characterize constraints in obtaining or giving up a belief, which may affect holding or giving up other beliefs with respect to a certain agent. Roughly speaking, based on these axioms, a belief contraction can be presented as whitening the corresponding nodes and strokes; this is called spreading white. Similarly, an expanding of a belief set is called spreading black. Using this framework, Tennant offers six persuasive examples of the belief revision problem from different perspectives, illustrating his graphical theory's superior expressive power and greater convenience in applying to real agents.

Chapter 3 explains the basic features of belief contraction. This is preparatory work for the formalization in the next chapter. Tennant claims that a real agent's belief system should not be regarded as a logically closed theory, but rather as a finite belief set that has justificatory relational structures. He then makes a distinction among three different kinds of belief sets in terms of theories, bases and developments. In terms of this distinction, a finite dependency network can be regarded as a systematic development. Finally, these intuitions can be precisely encoded into two properties: success and minimal mutilation. Tennant maintains that the general principle of recovery in AGM theory does not correctly express the property of minimal mutilation.

The main work of Chapter 4 is elaborating a formal theory of FDNs. According to Tennant, this theory can provide an abstract and universal framework for discussing a belief system and its contraction. We are able to introduce a strict definition of minimal mutilation that accurately describes belief contraction and thereby understand the complexity problems of contraction processes. Tennant provides a brief introduction to computational theory assuming background knowledge of P, NP, and NP-completeness, and cites several results from complexity theory for decision problems in classical logic. Then he presents four intuitive ideas for belief revision in the above framework. Tennant emphasizes that dealing with the structure of justificatory relations in a belief system is more important for a belief revision process. It does not need to consider the internal logical structures or contents of beliefs.  After these preliminaries, Tennant provides definitions for steps, dependency networks, kernels of a subnetwork, contraction networks, minimal mutilation, and so on. Detailed explanations of these definitions reflect the nature of rational belief dynamics. Given these definitions, he develops four theorems regarding the complexity of the decision problem for contraction.

Chapter 5 provides four contraction algorithms based on the formalization provided in chapter 4. In giving up certain beliefs, one often has a variety of options about what beliefs should be further abandoned during belief contraction. Therefore, contraction algorithms constrain the contraction's particular steps, as well as making choices at every step of computation. Minimal mutilation is the ideal requirement of belief contraction, but it may not be realistic given computational considerations. From this perspective, Tennant introduces a greedy algorithm, which, at every step of computation, yields the local optimal solution. The next two chapters make the algorithm implementable in computer programs for belief contraction. Chapter 6 presents the details of a Prolog program for the simplest version of the algorithm. Chapter 7 then presents the operation results of programs for various kinds of contractions. This completes the explanation of the method of FDNs, from basic theory to computer implementation.

Part II of the book consists of three chapters. Chapter 8 gives a system of inferential rules for core logic, and claims that the core logic is probably most appropriate for the natural sciences and intuitionistic mathematics -- and even for the theory of meaning. Then, by proving that every violation of the four coloration axioms for FDNs will lead to a contradiction under core logic, Tennant claims that all the inferential rules of core logic for belief revision are necessary. In Chapter 9, invoking Harvey Friedman's proof that an arbitrary theorem in an axiomatizable theory has only a finite number of respective proofs, Tennant concludes that considering belief revision limited to finite systems does not lead to the loss of generality. Those finite sets of beliefs are sufficient for further expansion. Chapter 10 then provides mathematical justifications for this idea. All three chapters in the second part support the FDNs method from the perspective of logic and meta-theory.

In part III, Tennant compares his work and other relevant belief revision theories. Chapter 11 examines three formal theories of belief revision, with JTMS and Bayesian network from artificial intelligence, and AGM theory from mathematical logic. Chapter 12 discusses several epistemological accounts for belief revision that may have some connections with his work. Tennant divides them into three categories: addressing the belief-revision problem by formal modeling, addressing belief revision without offering any formal modeling, and treating belief revision indirectly through the discussion of other topics. Tennant claims that his account of belief revision is neutral with respect to traditional skepticism, foundationalism, coherentism, and basic foundherentism; and that it can be used to analyze and clarify those views.

Given the above summary, we would like to make several comments on some particular issues. First of all, since the notion of justificatory steps is a core idea and major contribution of this book, it seems reasonable and interesting to make the concept as clear as possible. We can see the informal definition of 'steps' in chapter 2: a step from the premise set {b1, . . . , bn} to the distinct conclusion a. This is called a transitional step. The transitional step carries the logical interpretation (for an agent who adopts the step) of 'if one is justified in believing each of b1, . . . , bn then one is justified in believing a'. Tennant makes this interpretation in the following natural-deduction inference mode:

Jb1 . . . Jbn


where Jφ means 'one is justified in believing φ'. The crucial point here is that what contributes to the justification for believing a is not only b1, . . . , bn, but more importantly a certain kind of logical relation between premises {b1, . . . , bn} and conclusion a. What then are those logical relations? Are they valid logical rules of basic propositional deduction, so that {b1, . . . , bn}⊢a? If so, according to the description of logical paragons, the agent must be aware of this since the premise set is finite and basic propositional logic is decidable. The agent can probably carry out a validity-check for the proposition b1 . . . b a. This means that as long as {b1, . . . , bn}⊢a holds in propositional logic objectively, the paragon must know the respective justificatory step from {b1, . . . , bn} to a. However, Tennant also claims that it is possible for a rational paragon not to know by her own lights a justificatory step, such as {b2, . . . , bn}⊢a, that is actually logically valid , though the agent may know the justificatory step given a larger premise set {b1, b2, . . . , bn} and conclusion a. In this sense, we can conclude that the logical relations in justificatory steps cannot only be valid rules of basic propositional deduction.

Then we may consider justificatory steps in a perspective of propositional epistemic (doxastic) logic with finite premise sets. The easiest way of interpreting a transitional step can now be expressed as the following mode:

Bb1 . . . Bbn


where Bφ means 'the agent believes that φ'. The doxastic logic here is just classical modal logic KD45 [8]. Then the inference mode is equivalent to

B(b1 . . . bn)


since belief is closed under finite conjunctions.

Suppose that, for an agent, Ba can be deduced from the premise B(b1 . . . bn), intuitively meaning that the agent concludes that she believes a from believing b1 . . . bn. In this setting, if contracting belief a means that Ba becomes ¬Ba, then by contraposition of propositional logic, we should have ¬B(b1 . . . bn) for the agent. It can be concluded that there must be at least one Bbi (1in) that will become ¬Bbi since {b1, . . . , bn} is consistent and every bi is contingent (as Tennant stipulates). With regard to the agent, this says that she should give up at least one element in the set of {b1, . . . , bn}. Following Tennant's use of coloration, we may use black node bi to denote Bbi, and the respective white node to denote ¬Bbi. Then the above contraction process is quite like spreading white upward in Tennant's FDNs. Similarly, if we understand a transition step as 'for a certain agent, only if she believes all the elements of {b1, . . . , bn}, she believes a', then if one of her beliefs bi needs to be discarded (that is, Bbi becomes ¬Bbi), then Ba becomes ¬Ba. That's also like Tennant's spreading white downwards.

In spite of these similarities, Tennant's notion of 'stroke' (with black and white coloring) seems more expressive than the logical deduction notions of ⊢and ⊬. We would like to see if there is a kind of doxastic logic in our above characterization of contraction and revision as there is in Tennant's FDNs. In any case, we know that {b1, . . . , bn} may not have any objective deduction relations with a. Therefore, it is also possible for the agent to give up transitional steps (like Ba from {Bb1, . . . , Bbn}) in contraction processes, as defined in the above belief operator. But this is not the issue that Tennant has dealt with here. So the logical relation of justificatory steps interpreted in the above way cannot be the one that Tennant wants.

Now let's suppose the logical relations 'inhibited' in justificatory steps are valid first-order rules of deduction with finite premise sets. In this setting, we can readily understand the situations where the agent may not know the logically valid inferential rules, since first-order logic is undecidable in general. But, as we know, a rational agent is a logical paragon who never makes mistakes in logic. It is not possible for the agent to consider a justificatory step to be valid which is originally not valid by her own lights since so far no proof has been found for the (invalid) logic rules. The agent should consider as just invalid even actually valid inferential rules for which she herself has not settled the validity. It seems that the valid first-order deductive inferential rules with finite premises have the logical characteristics of justificatory steps that Tennant desires.

Furthermore, we think that there are some further interesting problems suggested by Tennant's work. First, it's possible to find several important implicit concepts which cannot be expressed directly in the FDNs, such as justifying, knowing, or being aware of a step. Those notions are the basis for fully understanding belief-change problems in the framework of FDNs. In order to characterize those concepts more precisely and clearly, we may hope to find epistemic logics to integrate them and make them explicit. Second, the presupposition of logical paragon for practical rational agents is still too idealized. In reality, people are often likely to make logical errors in practical reasoning activities. It's quite possible for them to treat incorrect proofs as valid arguments. Therefore, for the real belief revision of practical rational agents, justificatory steps should be concerned with change as well.

Last but not least, in Tennant's comparison of his approach to others, he doesn't mention any work from the DEL tradition. But such work is now under active development and intersects a broad family of disciplines, such as logic, artificial intelligence, and game theory. In [9], van Benthem expresses belief-change actions in the framework of dynamic doxastic logic. For instance, [+A]Bφ, [*A]Bφ may intuitively represent 'after every successful expanding (or revising) with A, the agent believes φ'. Van Benthem even finds valid reduction axioms for the laws of belief-change processes. From a DEL tradition standpoint, it's quite natural to think of belief revision in a multi-agent setting. It could be interesting to apply Tennant's work on the framework of integrating belief change processes to DEL, and describe such behaviors as decision making, communications, and even interactive games from the perspective actions in general [10].


[1] J. van Benthem. Exploring Logical Dynamics, CSLI Publications 1996, Stanford.

[2] H. van Ditmarsch, W. van der Hoek, B. Kooi. Dynamic Epistemic Logic, Springer 2007.

[3] C. E. Alchourrón, P. Gärdenfors and D. Makinson, On the Logic of Theory Change: Partial Meet Contraction and Revision Functions, in Journal of Symbolic Logic 50 (1985), 510-530.

[4] P. Gärdenfors, Knowledge in Flux: Modeling the Dynamics of Epistemic States, Bradford Books, The MIT Press, Cambridge, MA, 1988.

[5] J. van Benthem. Dynamic logic for belief revision. Journal of Applied Non-Classical Logics, 14(2): 129-155, 2004.

[6] S. O. Hansson, A Textbook of Belief Dynamics: Theory Change and Database Updating, Kluwer Academic Publishers, 1999.

[7] R. Fagin, J. Y. Halpern, Y. Moses, M. Y. Vardi, Reasoning about Knowledge, The MIT Press, Cambridge, MA, 1995.

[8] J. Hintikka, Knowledge and Belief, Cornell University Press, 1962.

[9] J. van Benthem. Open Problems in Logical Dynamics, in: D. Gabbay, S. Goncharov and M. Zakharyashev, editors, Mathematical Problems from Applied Logic I, Springer, 2006, 137-192.

[10] J. van Benthem, H. van Ditmarsch, J. van Eijck and J, Jaspars, Logic in Action, Open Course Project, Institute for Logic, Language and Computation, University of Amsterdam, 2012.