An account of how a rational agent should revise beliefs in the light of new evidence. This theory is set apart from previous belief revision theories by being computationally implementable, provides rigorous mathematical theory of dependency networks and formulates and investigates the complexity of algorithms for rational agents revising beliefs.



This is the first logically precise, computationally implementable, book-length account of rational belief revision. It explains how a rational agent ought to proceed when adopting a new belief - a difficult matter if the new belief contradicts the agent's old beliefs. Belief systems are modeled as finite dependency networks. So one can attend not only to what the agent believes, but also to the variety of reasons the agent has for so believing. The computational complexity of the revision problem is characterized. Algorithms for belief revision are formulated, and implemented in Prolog. The implementation tests well on a range of simple belief-revision problems that pose a variety of challenges for any account of belief revision. The notion of 'minimal mutilation' of a belief system is explicated precisely for situations when the agent is faced with conflicting beliefs. The proposed revision methods are invariant across different global justificatory structures (foundationalist, coherentist, etc.). They respect the intuition that, when revising one's beliefs, one should not hold on to any belief that has lost all its former justifications. The limitation to finite dependency networks is shown not to compromise theoretical generality. This account affords a novel way to argue that there is an inviolable core of logical principles. These principles, which form the system of Core Logic, cannot be given up, on pain of not being able to carry out the reasoning involved in rationally revising beliefs. The book ends by comparing and contrasting the new account with some major representatives of earlier alternative approaches, from the fields of formal epistemology, artificial intelligence and mathematical logic.