A Constructive Approach to Independent and Evidence Retaining Belief Revision by General Information Sets

1 Introduction

Belief revision theory provides methods and axiomatic postulates for changing the minds of intelligent agents in a rational way, in particular, when the new information is in conflict with previously held beliefs. The seminal AGM theory [Alchourr´on et al., 1985] studied belief revision in a purely propositional scenario. Since then, various approaches have been proposed to extend this framework, going for iterated revision of more complex epistemic states and studying revision strategies given by conditionals (cf., e.g., [Darwiche and Pearl, 1997]). Recently, in particular the demand for independence of syntax which is responsible for considering information sets like {A,B} and {A ∧ B} as equivalent has been questioned since in the context of iterated revision, unwanted effects may occur (cf., e.g., [Delgrande and Jin, 2008]). This has raised interest in investigating multiple [Zhang, 2004], parallel [Delgrande and Jin, 2008] or simultaneous [Kern-Isberner, 2008] revision in which the new information is given by sets of propositions resp. conditionals. However, no consensus has been reached yet, and each new approach seems to set up a new framework.

This paper aims at providing some common ground for the theory of revising epistemic states by general information sets, i.e., sets of (conditional or propositional) sentences. So, given some prior epistemic state and some general information set, we will propose postulates that are mainly based on a principle of conditional preservation as stated in [KernIsberner, 2004], and on enforcing conditional beliefs in the posterior epistemic state. As a consequence of the principle of conditional preservation, each element of the information set is dealt with separately, thus distinguishing easily revisions by, e.g., {A, B} from those by {A ∧ B}. The postulate of enforcing conditional beliefs exploits ideas from [KernIsberner, 2002] originally proposed for default reasoning and generalizes postulates like independence [Jin and Thielscher, 2007] and evidence retainment [Delgrande and Jin, 2008] for the task of revising by conditionals. Both principles make use of the theory of conditional structures that has been proposed as a fundamental algebraic approach to guide belief revision and default reasoning [Kern-Isberner, 2004; 2001]. Despite its complex theoretical underpinning, the simple rationale behind this theory is to make interactions between different conditionals (and propositions) visible on possible worlds, and manageable for information processing. Moreover, conditional structures provide schemata for revisions from which a constructive method for revising epistemic states by general information sets is obtained which satisfies the above mentioned principle of conditional preservation, the novel enforcement postulate, and success. We will show that this is enough to cover all major postulates from related works [Darwiche and Pearl, 1997; Jin and Thielscher, 2007; Delgrande and Jin, 2008] thus achieving a concise but, at the same time, broad and general picture.

Taking also conditionals as inputs to the revision procedure into regard allows for a more general and realistic view on belief revision. Propositions can be taken as a special case of conditionals, so methods for revising by conditionals can also be used for revising by plausible propositions. Moreover, agents often change contexts in their environment which may change their conditional beliefs. For instance, when passing the border of a country we will usually adopt new traffic rules without forgetting how to drive a car. So, it must be emphasized here that the approach to be presented in this paper is also applicable to propositional, or parallel [Delgrande and Jin, 2008] belief revision tasks, as propositions are considered as conditionals with tautological antecedent here. We will also establish the connection between our approach to belief revision and nonmonotonic reasoning.

This paper is structured as follows: Section 2 recalls basic facts about the logical setting of our approach. The constructive approach is developed in section 3; this section also presents the novel enforcement postulate and its semantical characterization. Section 4 elaborates on general links to related work and goes into more detail for the connection to parallel belief revision. We conclude in section 5.

2 Preliminaries on logic and conditionals

Let L be a finitely generated propositional language, with atoms a, b, c, . . ., and with formulas A,B,C, . . .. For conciseness of notation, we will omit the logical and-connector, writing AB instead of A ∧ B, and overlining formulas will indicate negation, i.e. A means ¬A. Let Ω denote the set of possible worlds over L; Ω will be taken here simply as the set of all propositional interpretations over L. ω |= Ameans that the propositional formula A ∈ L holds in the possible world ω ∈ Ω. By slight abuse of notation, we will use ω both for the model and the corresponding conjunction of all positive or negated atoms.

By introducing a new binary operator |, we obtain the set (L | L) = {(B|A) | A,B ∈ L} of conditionals over L. (B|A) formalizes "if A then B" and establishes a plausible connection between the antecedent A and the consequent B. Here, conditionals are supposed not to be nested, that is, antecedent and consequent of a conditional will be propositional formulas from L. Conditionals with tautological antecedents are taken as plausible statements about the world. Following De Finetti [DeFinetti, 1974], a conditional (B|A) can be verified (falsified) by a possible world ω iff ω |= AB (ω |= AB). If ω ̸|= A, then the conditional is not applicable to ω. A conditional (B|A) is said to be non-trivial if neither AB nor AB is contradictory.

A conditional (D|C) is a subconditional of (B|A), written as (D|C) ⊑ (B|A), iff CD |= AB and CD |= AB, i.e., iff verification resp. falsification of (D|C) implies verification resp. falsification of (B|A). A weak subconditional of (B|A) is a subconditional of (A ⇒ B|⊤) where ⇒ means material implication. It is straightforward to show that subconditionals are also weak subconditionals of the respective conditional. For different worlds ω1, ω2 ∈ Ω, (ω1|ω1 ∨ ω2) is called a basic conditional that is verified by ω1 and falsified by ω2.

Following [Katsuno and Mendelzon, 1991] and [Darwiche and Pearl, 1997], AGM revisions of epistemic states can be ensured by assuming faithful rankings (i.e., total preorders) that underly the epistemic states such that the revised beliefs can be computed from minimal models according to the ranking. In this paper, we take ordinal conditional functions as representations of such faithful rankings, resp., as representations of epistemic states: Ordinal conditional functions, OCFs, (also called ranking functions) are functions κ : Ω → N ∪ {∞} with κ-1 (0) ̸= ∅, expressing degrees of plausibility of propositional formulas A by specifying degrees of disbeliefs of their negations A (cf. [Spohn, 1988]). More formally, we have κ(A) := min{κ(ω) | ω |= A}. A proposition A is believed, in symbols κ |= A, iff κ(A) > 0. Degrees of plausibility can also be assigned to conditionals by setting κ(B|A) = κ(AB) - κ(A). A conditional (B|A) is accepted in the epistemic state represented by κ, written as κ |= (B|A), iff κ(AB) < κ(AB), i.e. iff AB is more plausible than AB. In particular, for a basic conditional (ω1|ω1 ∨ω2), we have κ |= (ω1|ω1 ∨ω2) iff κ(ω1) < κ(ω2). A set R = {(B1|A1), . . . , (Bn|An)} ⊆ (L | L) is consistent iff it has an OCF model, i.e. iff there is an OCF κ such that κ |= (Bi|Ai) for all i, 1 ⩽ i ⩽ n. κu is the uniform OCF with κu(ω) = 0 for all ω ∈ Ω. OCF's are semi-qualitative counterparts of probability distributions. Their plausibility degrees may be taken as order-of-magnitude abstractions of probabilities (cf. [Goldszmidt and Pearl, 1996]). Conditionals, epistemic states and AGM revision operators ∗ can be related by the Ramsey test [Ramsey, 1950]: κ |= (B|A) iff κ ∗ A |= B.

3 Enforcing revision based on conditional structures

The main contribution of this paper will be the proposal of (iterative) revision operators that take epistemic states (represented by ranking functions κ) and general information sets (consisting of plausible propositions and conditionals) and return revised epistemic states that accept all new pieces of information specified by the general information set and satisfy all major postulates (AGM [Alchourr´on et al., 1985], DP-postulates [Darwiche and Pearl, 1997], Independence [Jin and Thielscher, 2007], and Evidence Retainment [Delgrande and Jin, 2008]), when applied to the respective restricted framework (i.e., a single proposition, a single conditional, and sets of propositions).

Since plausible statements can be considered as conditionals with tautological antecedents, the formal specification of the basic technical revision task is given as follows:

Let R = {(B1|A1), . . . , (Bn|An)} ⊆ (L | L) be a finite set of conditionals, let κ be a prior epistemic state represented by an OCF. Specify revision operators ∗ that compute a revised OCF κ∗ = κ ∗ R by taking (somehow, to be further specified by postulates) prior and new information into account.

We will focus on consistent sets R, since revising by an inconsistent set of information should result in an inconsistent state of belief, if no aspects of consolidation or merging are taken into regard which we leave for future work. The crucial points with this task are, first, to take into account that conditionals are logically more complex than propositions and hence may require more sophisticated methods not provided by ideas from propositional revision, and, second, to treat each element of the general information set as an independent piece of information. For both requirements, the theory of conditional structures [Kern-Isberner, 2001; 2004] provides a suitable basis. Conditional structures are kind of footprints that sets of conditionals leave on possible worlds. They base on the three-valued approach to conditionals by De Finetti [DeFinetti, 1974], representing verification, falsification, and non-applicability by abstract symbols that are assigned to conditionals (or propositions) in a general information set. Since different conditionals are assigned different symbols, each conditional is treated as an independent piece of information.

More formally, let R = {(B1|A1), . . . , (Bn|An)} ⊆ (L | L) be a finite set of conditionals, and let a+1 , a-1 , . . . , a+n , a-n be distinct algebraic symbols that are used as generators of a (free abelian 1 ) group [Fine and Rosenberger, 1999] FR = 〈a+1 , a-1 , . . . , a+n , a-n 〉. In short, this group structure provides us with a multiplication (written as juxtaposition) that we can relate to the summation of κ-values, and with a 1 that symbolizes neutrality (i.e. non-applicability). Furthermore, free abelian ensures a parallel handling of the conditionals (without any order of application assumed) as well as independence between different conditionals (by forbidding cancellations between different symbols). For each i, 1 ⩽ i ⩽ n, we define a function σi = σ(Bi|Ai) : Ω → FR by setting

σi(ω) represents the manner in which the conditional (Bi|Ai) applies to the possible world ω. The function σR : Ω → FR,

describes the all-over effect of R on ω. σR(ω) is called the conditional structure of ω with respect to R. Since FR is a free (abelian) group, the conditional structures of worlds are uniquely determined by their σi-components and hence by their logical relation to each conditional: For any two worlds ω1, ω2, we have

Conditional structures also work for propositions Ai ≡ (Ai|⊤) ∈ R. Propositions can only be verified resp. satisfied, or falsified. There is no non-applicability in this case, so σi(ω) ∈ {a-i , a+i } for each ω. Nevertheless, conditional structures are helpful to distinguish between the effects of different pieces of information also in this case.

Example 1 Consider the following scenario described by the set R = {r1, . . . , r9}, where penguins (p), kiwis (k), and doves (d) are modelled as disjoint classes of birds (b) which usually fly (f), and typically have wings (w) and eyes (e) :

Assigning symbols a+i , a-i to any ri, we compute the following conditional structures for possible worlds:

Based on conditional structures, a principle of conditional preservation was proposed in [Kern-Isberner, 2004]. It controls conditional belief revision by claiming a balance between conserving conditional relationships in the prior epistemic state and establishing conditional relationships from the information set. To illustrate this, we state a simple consequence of this principle as the following property which will prove to be useful here:

1 Free abelian groups have no relations except for those induced by commutativity.

(SCondPres) claims that the relative amount of change between prior and posterior epistemic state only depends on the conditional structure of the respective world. As a general consequence of the principle of conditional preservation, the revised epistemic state follows a structure that assigns to each conditional in the new information set a constant parameter that represents the impact of each conditional in the revision process. When revising an ordinal conditional function κ by a set of conditionals R, it is proved in [Kern-Isberner, 2004] that revisions κ∗ = κ ∗ R of the form

with non-negative, integral parameters κ-i and a normalization constant κ0, satisfy the full principle of conditional preservation and hence also (SCondPres). Revisions of this kind are called c-revisions in [Kern-Isberner, 2004]. The parameters κ-i are numerical counterparts of the abstract symbols a-i whereas the a+i have no numerical impact by implicitly setting κ+i = 0. They have to be set according to general constraints on the outcome of the revision process, i.e. postulates in the spirit of the AGM-theory. A constraint that is typically applied in revision scenarios and will be used here to determine these parameters is success on the level of the conditionals in R:

(Success) κ∗R |= R, i.e., κ∗R |= (B|A) for all (B|A) ∈ R. For c-revisions κ∗ of the form (2), (Success) is satisfied iff for all i, 1 ⩽ i ⩽ n,

We will now follow ideas from [Kern-Isberner, 2002] and claim that, ceteris paribus and generally, falsification of conditionals should have a penalizing effect. To implement this, a partial ordering > between conditional structures of worlds is defined in the following way: For any possible worlds ω1, ω2 ∈ Ω, we define σR(ω1) > σR(ω2)

iff for each i, 1 ⩽ i ⩽ n, σi(ω1) = a-i implies σi(ω2) = a-i , and there is at least one i, 1 ⩽ i ⩽ n, such that σi(ω1) ∈ {a+i , 1} and σi(ω2) = a-i . That is, σR(ω1) > σR(ω2) iff ω2 falsifies more conditionals than ω1. So, for instance, in example 1, we have σR(pk dbfwe) = a+1 a-2 a+3 a+4 a+8 a+9 > a+1 a-2 a-3 a-8 a+9 = σR(pk dbfwe), but σR(pk dbfwe) and σR(pkd b fwe) are not comparable with respect to >.

Now, both conditional information from the prior epistemic state κ and the new information set R are used to enforce conditional beliefs in the revised epistemic state κ∗ = κ ∗ R:

This enforcement postulate claims that if ω2 falsifies more conditionals in R than ω1 (ceteris paribus and with respect to set inclusion) and is not more plausible than ω1 in the prior epistemic state, then it should definitely be less plausible than ω1 in the revised epistemic state.

We will illustrate how the concept of c-revisions together with the postulates of (Success) and (Enf) yield elaborate revisions in the scenario of example 1. We will also show how the machinery that has been developed so far can be used for inductive default reasoning.

Example 2 We continue example 1, so let R be given as above. First, we use the method of successful and enforcing c-revision for inductive nonmonotonic reasoning. Let ∗ be a c-revision operator yielding revisions as in (2) and satisfying (Success) and (Enf). Then κ1 = κu ∗ R is a new epistemic state of the form (2) that accepts all conditionals in R. The κ-i for this example have been calculated as the minimal non-negative integers that satisfy (3) (so that (Success) is ensured) and (Enf) (note that κu(ω) = 0 for all ω, so the partial order > on conditional structures can be implemented whenever applicable). For instance, we find that κ-3 = κ-4 = 1, and κ-1 = κ-2 = 2. In κ1, among others, the following conditionals are accepted: (f|k) (kiwis do not fly), (f|d), (w|d) (doves fly and have wings). Please note that no immediate connection between birds and the ability to fly is encoded in R, but just an indirect link via having wings. In particular, κ1 is undecided concerning penguins having wings, neither (w|p) nor (w|p) can be derived because wings are deemed crucial for flying, and penguins can not fly. However, from κ1 the agent can derive the beliefs that all birds - in particular kiwis and penguins - usually have eyes.

Now, we revise κ1 by the set S = {s1 = (w|d), s2 = (f|p)} after the fictitious observations that doves have no wings, and that penguins can fly. We compute κ2 = κ1 ∗ S in the same way as above. Based on this new epistemic state, the agent believes now that doves can not fly any more (κ2 |= (f|d)), but that penguins have wings (κ2 |= (w|p)). No belief concerning kiwis is affected by the revision, so the agent still holds the same beliefs about kiwis as in κ1.

The following theorem characterizes the semantic (Enf) postulate by exploiting the prior epistemic state and the explicitly given new conditional information:

Theorem 3 Let R = {(B1|A1), . . . , (Bn|An)} ⊆ (L | L) be a finite set of conditionals, let κ be an OCF. Let the revision operator ∗ be compatible with propositional AGM revision. Then the revision κ∗ = κ ∗R satisfies (Enf) iff it satisfies the postulate of conditional enforcement:

• (CondEnf) For any weak subconditional (B′i |A′i ) of one of the conditionals in R (i.e. (B′i |A′i ) ⊑ (Ai ⇒ Bi|⊤) for some i) such that
• no non-trivial subconditional (B′′ i |A′′ i ) of (B′i |A′i ) is rejected by κ, i.e., κ ̸|= (B′′ i |A′′ i ) for all (B′′ i |A′′ i ) ⊑ (B′i |A′i ), and
• for all other conditionals (Bj|Aj) in R, verification of (B′i |A′i ) implies satisfaction of (Bj|Aj), or falsification of (B′i |A′i ) implies falsification of (Bj|Aj), i.e., for all

j ̸= i, it holds that A′iB′i |= Aj ⇒ Bj or A′iB′i |= AjBj ,

it holds that κ ∗ R |= (B′i |A′i ).

The conditional enforcement postulate claims that any weak subconditional of any (Bi|Ai) ∈ R (and hence any subconditional obtained by strengthening the antedent) is enforced in the revised epistemic state κ∗R iff there is no evidence to the contrary neither due to the prior epistemic state κ (as specified by condition (1)) nor from the other conditionals in R (as specified by (2)). Note that Theorem 3 holds for general condtional revision operators, not only for c-revisions.

Proof of Theorem 3. First, we assume that (Enf) holds. Let (B′i |A′i ) be a weak subconditional of (Bi|Ai) ∈ R as specified in the theorem. We have to show κ ∗ R |= (B′i |A′i ), i.e., κ ∗ R(A′iB′i ) < κ ∗ R(A′iB′i ). Let ω1, ω2 ∈ Ω be such that ω1 |= A′iB′i and ω2 |= A′iB′i . Then (ω1|ω1 ∨ ω2) is a (non-trivial) subconditional of (B′i |A′i ). By condition (1) of (CondEnf), we have κ ̸|= (ω1|ω1 ∨ ω2) which is equivalent to κ(ω1) ⩽ κ(ω2). Consider now σR(ω1) and σR(ω2). Due to ω1 |= A′iB′i and ω2 |= A′iB′i , we have σi(ω1) = a+i and σi(ω2) = a-i . For all other j ̸= i, if A′iB′i |= Aj ⇒Bj, then σi(ω1) ̸= a-i . If A′iB′i ̸|= Aj ⇒ Bj, then A′iB′i |= AjBj by condition (2) of (CondEnf). In this latter case, σi(ω2) = a-i . So, σR(ω1) > σR(ω2). Together with κ(ω1) ⩽ κ(ω2), (Enf) now implies κ ∗ R(ω1) ⩽ κ ∗ R(ω2), and therefore κ ∗ R(A′iB′i ) < κ ∗ R(A′iB′i ).

For the other direction, we presuppose that (CondEnf) holds, and we have to show the validity of (Enf). So, let ω1, ω2 ∈ Ω such that σR(ω1) > σR(ω2) and κ(ω1) ⩽ κ(ω2). In order to show κ∗ (ω1) < κ∗ (ω2), we prove the equivalent statement κ∗ |= (ω1|ω1 ∨ ω2). By exploiting the prerequisite σR(ω1) > σR(ω2), we find in particular, that there must be an index i such that σR(ω1) must be a+i or 1, and σR(ω2) = a-i . Hence ω1 |= Ai ⇒ Bi and ω2 |= AiBi, so (ω1|ω1 ∨ ω2) is a weak subconditional of (Bi|Ai) ∈ R. Since (ω1|ω1 ∨ ω2) has no non-trivial subconditionals except for itself, and κ ̸|= (ω1|ω1 ∨ ω2) due to κ(ω1) ⩽ κ(ω2), (1) of (CondEnf) is satisfied. Next, let j ̸= i. Again thanks to σR(ω1) > σR(ω2), we have that whenever σj(ω1) = a-j (in which case ω1 ̸|= Aj ⇒ Bj), then σj(ω2) = a-j must also hold, i.e., ω2 |= AjBj is ensured by σR(ω1) > σR(ω2) in this case. So, (ω1|ω1 ∨ ω2) is a conditional that fulfills all requirements specified in the prerequisites of (CondEnf), and so (CondEnf) postulates κ∗ |= (ω1|ω1 ∨ ω2). ✷

In summary, as a powerful set of postulates that should guide the revision of epistemic states (given by ordinal conditional functions) by sets of (propositional and conditional) beliefs, we propose a principle of conditional preservation, as specified in [Kern-Isberner, 2004] and implemented by crevisions of the form (2), together with (Success) and (Enf) (resp. (CondEnf)). A straightforward consequence of Theorem 3 is the following proposition:

Proposition 4 Let R = {(B1|A1), . . . , (Bn|An)} ⊆ (L | L) be a finite set of conditionals, let κ be an OCF. If the revision κ∗ = κ ∗ R satisfies (Enf) then for any conditional (Bi|Ai) in R, and for any strengthening A |= Ai of its antecedent such that κ ∗ A′ ̸|= Bi for any further strengthening A′ |= A, and such that for all j ̸= i, ABi |= Aj ⇒ Bj or ABi |= AjBj, it holds that (κ ∗R) ∗ A |= Bi.

This proposition has interesting consequences for investigating monotonicity in nonmonotonic reasoning. Applying a successful, enforcing c-revision operator ∗ to the uniform OCF κu (with κu(ω) = 0 for all ω ∈ Ω) and to a set of conditionals R gives rise to an inductive default inference relation similar to system Z [Goldszmidt and Pearl, 1996], setting C |∼ R D iff (κu∗R)∗C |= D, or (κu∗R) |= (D|C), respectively (see example 2). In particular, (Success) ensures that Ai |∼ R Bi for all conditionals (Bi|Ai) ∈ R. Since κu does not accept any nontrivial conditional beliefs, the first presupposition in proposition 4 which a strengthening A of Ai has to satisfy is vacuous (since R is assumed to be consistent). So only the second presupposition applies, stating that also A|∼ RBi for A |= Ai if for all j ̸= i, ABi |= Aj ⇒ Bj, or ABi |= AjBj. For instance, in example 2, the inference dbwe |∼ R f (dove birds with wings and eyes can also fly) can be directly derived from the knowledge base R. Note that the inference relation |∼ R also complies with system P and rational monotonicity [Goldszmidt and Pearl, 1996], since it is based on an ordinal conditional function, and satisfies advanced postulates like specificity, irrelevance, property inheritance (hence drowning problems are avoided), ambiguity preservation, and duplication stability, since it implements reasoning based on conditional structures (for further information, please see [Kern-Isberner, 2002]).

4 Related work

As one of the first and most important approaches to extend AGM-theory towards epistemic states Ψ and iterated revision operators ∗, and to also take issues of conditional preservation into regard, [Darwiche and Pearl, 1997] proposed four new postulates (DP-postulates) for iterated revision. In [KernIsberner, 2004] it is proved that c-revisions are AGM revisions (when applied to a single proposition) and satisfy all DP-postulates.

Three of these DP-postulates have been widely accepted but the second one (C2) has been intensely debated:

For instance, Delgrande and Jin [Delgrande and Jin, 2008] found this postulate to be the culprit for so-called "drowning problems" which are caused by the suppression of effects of some pieces of information by other pieces of information so that they can not have a proper impact on the resulting belief state. In particular, these authors argue that the generalization of (C2) for sets of propositions, as proposed by [Zhang, 2004] is completely inappropriate. However, exploring (C2) for conditional beliefs, its relevance becomes apparent: (C2) claims that if B |= ¬A then (Ψ∗A) ∗B |= C iff Ψ∗B |= C, so using the connection between revision and conditionals via the Ramsey test, we have (Ψ ∗ A) |= (C|B) iff Ψ |= (C|B) - revising by A should leave conditional beliefs intact the antecedent of which is disjoint from A, which makes perfect sense. (C2) has been generalized to revision by a single conditional belief in [Kern-Isberner, 2001].

The problems that Delgrande and Jin encountered in [Delgrande and Jin, 2008] are principally caused by taking the information sets {A, B} and {A∧B} to be equivalent, ignoring the independence of each piece of information. So, they propose an approach to revise epistemic states K by sets of propositional formulas S, called parallel belief revision and denoted by K ⊗ S. The aim of their framework is to allow for the explicit representation of individual items of new information. For instance, in K ⊗ {α, β}, α and β represent individual items of information while in K⊗ {α ∧ β}, their coincidence is taken as one piece of information. This means that in that framework, b ∈ Bel(K ⊗ {a, b} ⊗ {¬a}) but b ̸∈ Bel(K ⊗ {a ∧ b} ⊗ {¬a}). Delgrande and Jin demand that all formulas of S should be established individually such that in case of further revision all items in S against which no evidence exists should be retained. This demand is formalized by their postulate of evidence retainment, the equivalent semantical condition of which on a faithful ranking ⪯K is given as follows:

(Ret⊗R) If S|ω2⊂S|ω1 then ω1⪯Kω2 implies ω1 ≺K⊗S ω2 with S|ω = {α ∈ S | ω |= α}. The independence postulate of [Jin and Thielscher, 2007] covers the case |S| = 1. In addition to (Ret⊗R), Delgrande and Jin extend two of the DP-postulates, (C3) and (C4) [Darwiche and Pearl, 1997], for parallel belief revision in the following semantical characterization:

Delgrande and Jin conclude that an adequate operator for parallel belief revision should satisfy the AGM postulates generalized to sets, (Ret⊗R), (PC3⊗R) and (PC4⊗R).

To match the framework of Delgrande and Jin, we consider the propositional case of our proposed conditional revision operator. Thus, let R = {(A1|⊤), . . . , (An|⊤)} with Ai ≡ (Ai|⊤). In this restricted setting we have σi(ω) = a+i if ω |= Ai and σi(ω) = a-i if ω |= Ai. In the notation of Delgrande and Jin, the correspondence to our framework is easily seen by σR(ω) = ∏Ai∈R|ω a+i ∏Ai∈R\R|ω a-i , so that we have σR(ω1) > σR(ω2) iff R|ω2 ⊂ R|ω1. With this direct connection to the approach of Delgrande and Jin we obtain the following result.

Proposition 5 Let R = {(A1|⊤), . . . , (An|⊤)} be a finite set of propositional conditionals, let κ be an OCF, and let κ ∗ R be a c-revision that satisfies (Enf). Then κ ∗ R satisfies (Ret⊗R), (PC3⊗R) and (PC4⊗R).

Proof of Proposition 5. The satisfaction of (Ret⊗R) and the proper subset case for the precondition of (PC3⊗R) and (PC4⊗R) follow directly from (Enf). For the case of R|ω1 = R|ω2 for (PC3⊗R) and (PC4⊗R) it follows from the satisfaction of (SCondPres) by c-revisions that κ∗ (ω1) - κ(ω1) = κ∗ (ω2) - κ(ω2) and especially that κ(ω1) ⩽ κ(ω2) implies κ∗ (ω1) ⩽ κ∗ (ω2) and κ(ω1) < κ(ω2) implies κ∗ (ω1) < κ∗ (ω2). Hence (PC3⊗R) and (PC4⊗R) are satisfied. ✷

The approach we present in this paper is therefore a constructive approach and a conditional generalization of a parallel, and iterated, belief revision operator that satisfies all desirable properties of parallel belief revision. Actually, both evidence retainment and independence postulate more than simple independence: They claim that each piece of information should have a noticeable impact on the resulting epistemic state (that is largely independent of the impact of other pieces of information). So, they are both in conflict with a postulate called stability that has been considered in [KernIsberner, 2001], requiring that Ψ∗A = Ψ if Ψ |= A. Stability claims that no difference should be made between implicitly derived and explicitly stated beliefs. Hence, the postulate of independence [Jin and Thielscher, 2007] rather addresses the difference between these two types of belief, stating that one expects the explicit beliefs to be enforced if there is no reason against it. Evidence retainment does exactly the same for pieces of information that are independent in that they are given by different propositions. Conditional structures represent each piece of explicitly given information by algebraic symbols, therefore implementing both independence and explicitness of information, but leaving the exploration of logical and numerical (or preferential) constraints to the principle of conditional preservation (which is able to handle much more complicated relationships between conditional structures than those shown in (SCondPres)). The enforcement postulate (CondEnf) comes on top of that, as an independent postulate, claiming the thorough establishing of conditional beliefs with respect to subconditionals. It is immediately seen from its semantical characterization in (Enf) that (CondEnf) generalizes independence and evidence retainment for conditional beliefs. Analogous to independence and evidence retainment, this principle makes a strong difference between explicit and implicit beliefs.

5 Conclusion

In this paper, we present principles and a constructive approach to iterative belief revision of epistemic states by sets of (propositional or conditional) sentences. In more detail, exploiting ideas from [Kern-Isberner, 2002] concerning default reasoning for the tasks of belief revision gives rise to an enforcement postulate that demands for establishing conditional beliefs also for strengthenings of the antecedents. We combine this with a principle of conditional preservation that has been proposed in [Kern-Isberner, 2004] and yields a schema for revision operations as the basis for our constructive approach. In this way, our approach implements both an in-depth control of conditional dependencies, due to the principle of conditional preservation, and an in-depth enforcement of conditional dependencies. Actually, it is this latter principle that underlies the ideas of independence [Jin and Thielscher, 2007] and evidence retainment [Delgrande and Jin, 2008] set up for revising by (sets of) propositions. Together with the success postulate, the postulates of conditional preservation and enforcement are shown to cover also the advanced postulates for iterated revision proposed in [Darwiche and Pearl, 1997; Jin and Thielscher, 2007; Delgrande and Jin, 2008]. As part of our future work, we will extend the proposed framework by considering inconsistent sets of information that will be consolidated by merging operations before revision.