Most approaches to iterated belief revision are accompanied by some motivation for the use of the proposed revision operator (or family of operators), and typically encode enough information in the epistemic state of an agent for uniquely determining one-step revision. But in those approaches describing a family of operators there is usually little indication of how to proceed uniquely after the first revision step. In this paper we contribute towards addressing that deficiency by providing a formal framework which goes beyond (...) the first revision step in two ways. First, the framework is obtained by enriching the epistemic state of an agent starting from the following intuitive idea: we associate to each world x two abstract objects x⁺ and x⁻, and we assume that, in addition to preferences over the set of worlds, we are given preferences over this set of objects as well. The latter can be considered as meta-information encoded in the epistemic state which enables us to go beyond the first revision step of the revision operator being applied, and to obtain a unique set of preferences over worlds. We then extend this framework to consider, not only the revision of preferences over worlds, but also the revision of this extended structure itself. We look at some desirable properties for revising the structure and prove the consistency of these properties by giving a concrete operator satisfying all of them. Perhaps more importantly, we show that this framework has strong connections with two other types of constructions in related areas. Firstly, it can be seen as a special case of preference aggregation which opens up the possibility of extending the frame-work presented here into a full-fledged framework for preference aggregation and social choice theory. Secondly, it is related to existing work on the use of interval orderings in a number of different contexts. (shrink)

This paper extends earlier work by its authors on formal aspects of the processes of contracting a theory to eliminate a proposition and revising a theory to introduce a proposition. In the course of the earlier work, Gardenfors developed general postulates of a more or less equational nature for such processes, whilst Alchourron and Makinson studied the particular case of contraction functions that are maximal, in the sense of yielding a maximal subset of the theory (or alternatively, of one of (...) its axiomatic bases), that fails to imply the proposition being eliminated. In the present paper, the authors study a broader class, including contraction functions that may be less than maximal. Specifically, they investigate "partial meet contraction functions", which are defined to yield the intersection of some nonempty family of maximal subsets of the theory that fail to imply the proposition being eliminated. Basic properties of these functions are established: it is shown in particular that they satisfy the Gardenfors postulates, and moreover that they are sufficiently general to provide a representation theorem for those postulates. Some special classes of partial meet contraction functions, notably those that are "relational" and "transitively relational", are studied in detail, and their connections with certain "supplementary postulates" of Gardenfors investigated, with a further representation theorem established. (shrink)

This paper is concerned with formal aspects of the logic of theory change, and in particular with the process of shrinking or contracting a theory to eliminate a proposition. It continues work in the area by the authors and Peter Gärdenfors. The paper defines a notion of safe contraction of a set of propositions, shows that it satisfies the Gärdenfors postulates for contraction and thus can be represented as a partial meet contraction, and studies its properties both in general and (...) under various natural constraints. (shrink)

In some recent papers, the authors and Peter Gärdenfors have defined and studied two different kinds of formal operation, conceived as possible representations of the intuitive process of contracting a theory to eliminate a proposition. These are partial meet contraction (including as limiting cases full meet contraction and maxichoice contraction) and safe contraction. It is known, via the representation theorem for the former, that every safe contraction operation over a theory is a partial meet contraction over that theory. The purpose (...) of the present paper is to study the relationship more finely, by seeking an explicit map between the component orderings involved in each of the two kinds of contraction. It is shown that at least in the finite case a suitable map exists, with the consequence that the relational, transitively relational, and antisymmetrically relational partial meet contraction functions form identifiable subclasses of the safe contraction functions, over any theory finite modulo logical equivalence. In the process of constructing the map, as the composition of four simple transformations, mediating notions of bottom and top contraction are introduced. The study of the infinite case remains open. (shrink)

Abstract: The paper provides a general account of value relations. It takes its departure in a special type of value relation, parity, which according to Ruth Chang is a form of evaluative comparability that differs from the three standard forms of comparability: betterness, worseness and equal goodness. Recently, Joshua Gert has suggested that the notion of parity can be accounted for if value comparisons are interpreted as normative assessments of preference. While Gert's basic idea is attractive, the way he develops (...) it is flawed: His modeling of values by intervals of permissible preference strengths is inadequate. Instead, I provide an alternative modeling in terms of intersections of rationally permissible preference orderings. This yields a general taxonomy of all binary value relations. The paper concludes with some implications of this approach for rational choice. (shrink)

Prioritized bases, i.e., weakly ordered sets of sentences, have been used for specifying an agent’s ‘basic’ or ‘explicit’ beliefs, or alternatively for compactly encoding an agent’s belief state without the claim that the elements of a base are in any sense basic. This paper focuses on the second interpretation and shows how a shifting of priorities in prioritized bases can be used for a simple, constructive and intuitive way of representing a large variety of methods for the change of belief (...) states—methods that have usually been characterized semantically by a system-of-spheres modeling. Among the methods represented are ‘radical’, ‘conservative’ and ‘moderate’ revision, ‘revision by comparison’ in its raising and lowering variants, as well as various constructions for belief expansion and contraction. Importantly, none of these methods makes any use of numbers. (shrink)

In the middle of the 1980s, logical tools were discovered that make it possible to model changes in belief and knowledge in entirely new ways. These logical tools turned out to be applicable both to human beliefs and to the contents of databases. This is the first textbook in this new area. It contains both discursive chapters with a minimum of formalism and formal chapters in which proofs and proof methods are presented. By using different selections from the formal section (...) the book can be used on all levels of University education. (shrink)

A sentence A is epistemically less entrenched in a belief state K than a sentence B if and only if a person in belief state K who is forced to give up either A or B will give up A and hold on to B. This is the fundamental idea of epistemic entrenchment as introduced by Gärdenfors (1988) and elaborated by Gärdenfors and Makinson (1988). Another distinguishing feature of relations of epistemic entrenchment is that they permit particularly simple and elegant (...) construction recipes for minimal changes of belief states. These relations, however, are required to satisfy rather demanding conditions. In the present paper we liberalize the concept of epistemic entrenchment by removing connectivity, minimality and maximality conditions. Correspondingly, we achieve a liberalization of the concept of rational belief change that does no longer presuppose the postulates of success and rational monotony. We show that the central results of Gärdenfors and Makinson are preserved in our more flexible setting. Moreover, the generalized concept of epistemic entrenchment turns out to be applicable also to relational and iterated belief changes. (shrink)

This paper reorganizes and further develops the theory of partial meet contraction which was introduced in a classic paper by Alchourron, Gardenfors, and Makinson. Our purpose is threefold. First, we put the theory in a broader perspective by decomposing it into two layers which can respectively be treated by the general theory of choice and preference and elementary model theory. Second, we reprove the two main representation theorems of AGM and present two more representation results for the finite case that (...) "lie between" the former, thereby partially answering an open question of AGM. Our method of proof is uniform insofar as it uses only one form of "revealed preference", and it explains where and why the finiteness assumption is needed. Third, as an application, we explore the logic characterizing theory contractions in the finite case which are governed by the structure of simple and prioritized belief bases. (shrink)

In contrast to other prominent models of belief change, models based on epistemic entrenchment have up to now been applicable only in the context of very strong packages of requirements for belief revision. This paper decomposes the axiomatization of entrenchment into independent modules. Among other things it is shown how belief revision satisfying only the 'basic' postulates of Alchourrón, Gärdenfors and Makinson can be represented in terms of entrenchment.

One of the main tools in the study of nonmonotonic consequence relations is the representation of such relations in terms of preferential models. In this paper we give an unified and simpler framework to obtain such representation theorems.

The 1985 paper by Carlos Alchourrón (1931–1996), Peter Gärdenfors, and David Makinson (AGM), "On the Logic of Theory Change: Partial Meet Contraction and Revision Functions" was the starting-point of a large and rapidly growing literature that employs formal models in the investigation of changes in belief states and databases. In this review, the first twentyfive years of this development are summarized. The topics covered include equivalent characterizations of AGM operations, extended representations of the belief states, change operators not included in (...) the original framework, iterated change, applications of the model, its connections with other formal frameworks, computatibility of AGM operations, and criticism of the model. (shrink)

The 1985 paper by Carlos Alchourrón, Peter Gärdenfors, and David Makinson, “On the Logic of Theory Change: Partial Meet Contraction and Revision Functions” was the starting-point of a large and rapidly growing literature that employs formal models in the investigation of changes in belief states and databases. In this review, the first twenty-five years of this development are summarized. The topics covered include equivalent characterizations of AGM operations, extended representations of the belief states, change operators not included in the original (...) framework, iterated change, applications of the model, its connections with other formal frameworks, computatibility of AGM operations, and criticism of the model. (shrink)

Nonmonotonic logics were created as an abstraction of some types of common sense reasoning, analogous to the way classical logic serves to formalize ideal reasoning about mathematical objects. These logics are nonmonotonic in the sense that enlarging the set of axioms does not necessarily imply an enlargement of the set of formulas deducible from these axioms. Such situations arise naturally, for example, in the use of information of different degrees of reliability. This book emphasizes basic concepts by outlining connections between (...) different formalisms of nonmonotonic logic, and gives a coherent presentation of recent research results and reasoning techniques. It provides a self-contained state-of-the-art survey of the area addressing researchers in AI lo. (shrink)

SUGGESTED COURSES Introductory level A (Requires very little background in logic .): 4: -9 - - -7 -2 Introductory level B: -9,:+-+ -,2:+,2: -,3:20+-22+ -7 -2 ...

One of the main tools in the study of nonmonotonic consequence relations is the representation of such relations in terms of preferential models. In this paper we give an unified and simpler framework to obtain such representation theorems.

Modern belief revision theory is based to a large extent on partial meet contraction that was introduced in the seminal article by Carlos Alchourrón, Peter Gärdenfors, and David Makinson that appeared in 1985. In the same year, Alchourrón and Makinson published a significantly different approach to the same problem, called safe contraction. Since then, safe contraction has received much less attention than partial meet contraction. The present paper summarizes the current state of knowledge on safe contraction, provides some new results (...) and offers a list of unsolved problems that are in need of investigation. (shrink)

An extended review of what is known about the formal behaviour of nonmonotonic inference operations, including those generated by the principal systems in the artificial intelligence literature. Directed towards computer scientists and others with some background in logic.