Iterated Belief Revision, Revised

1 Introduction

Belief revision is the process of changing the beliefs of an agent to accommodate new, more precise, or more reliable evidence that is possibly inconsistent with the existing beliefs. In situations where the new evidence is consistent with the existing beliefs, the two can just be merged; we call this mild revision. More interesting and complicated are situations where the evidence conflicts with the prior beliefs, in which case the agent needs to remove some of its currently held beliefs in order to accommodate the new evidence. This kind of revision is referred to as severe revision.

In the literature, the classical approach of belief revision is the AGM framework [Alchourr´on et al., 1985; G¨ardenfors and Makinson, 1988; G¨ardenfors, 1988]. Given an underlying logic language L, the beliefs of an agent are represented by a set of sentences in L (known as belief set) which is closed under logical consequence. New evidence is also a sentence in L, and a belief revision operator maps the current belief set and the new evidence to a revised belief set. To provide general design criteria for belief revision operators, Alchourr´on, G¨ardenfors, and Makinson (AGM) have developed a set of postulates [Alchourr´on et al., 1985]. The guiding principle is that of economy of information or minimal change of belief sets, which means not to give up currently held beliefs and not to generate new beliefs unless necessary.

For the incremental adaptation of beliefs, these postulates proved to be too weak [Darwiche and Pearl, 1994; 1997]. This has led to the development of additional postulates for iterated belief revision by Darwiche and Pearl (DP), among others.

Still, however, the two sets of postulates are too permissive in that they support belief revision operators which assume arbitrary dependencies among the pieces of information which an agent acquires along its way. A universal dependency among all new evidences has a drastic effect when the agent makes an observation which contradicts its currently held beliefs: The agent has to cancel everything it has learned up to this point [Nayak et al., 1996; 2003]. In this paper, we first give a formal analysis of this problem of implicit dependence, and then we present, as a solution, an Independence postulate for iterated belief revision. We give a representation theorem for our postulate and prove its consistency by defining a concrete belief revision operator. We also contrast the postulate of independence to the so-called Recalcitrance postulate of [Nayak et al., 1996; 2003] and argue that the latter is too strict in that it rejects reasonable belief revision operators.

The rest of the paper is organized as follows. In the next section, we recall the classical AGM approach in a propositional setting as formulated by [Katsuno and Mendelzon, 1991], followed by the approach of [Darwiche and Pearl, 1994] for iterated belief revision. In Section 3, we formally analyze the problem of the DP postulates to be overly permissive. In Section 4, we present an additional postulate to overcome this deficiency. We give a representation theorem for the postulate along with a concrete revision operator. We conclude in Section 5 with a detailed comparison to related work.

2 Preliminaries

It has been observed by many researchers that belief sets alone are not sufficient to determine a unique strategy for belief revision [G¨ardenfors and Makinson, 1988; Spohn, 1988]. Any concrete belief revision operator requires additional information concerning the firmness of different beliefs to determine the revision strategy. In particular, this (extra-logical) information should uniquely determine a set of conditional beliefs: An agent is said to hold a conditional belief α ≫ β (with α, β sentences in L) precisely when it will believe β after a revision with α [G¨ardenfors, 1988; Boutilier, 1993]. The Triviality Theorem of [G¨ardenfors and Makinson, 1988] shows that using the AGM postulates it is improper to include conditional beliefs into the belief sets. As a consequence, we need to distinguish a belief set (referred to as propositional beliefs) from a belief state (also called epistemic state). The latter contains, in addition to its belief set, the conditional beliefs which determine the revision strategy.

2.1 (Modified) KMPostulates

Katsuno and Mendelzon (KM) rephrased the AGM postulates for the propositional setting [Katsuno and Mendelzon, 1991]. The beliefs of an agent are represented by a sentence ψ in a finitary propositional language L. 1 Any new evidence is a sentence µ in L, and the result of revising ψ with µ is also a sentence (denoted as ψ ∗ µ) belonging to L.

To avoid an inconsistency with their postulates for iterated revision, [Darwiche and Pearl, 1994; 1997] suggested to weaken the original KM postulates by regarding belief revision operators as functions on belief states (rather than on belief sets). This resulted in the Postulate (R*1)-(R*6) shown below.

For the sake of the simplicity, we will abuse notation by using interchangeably a belief state Ψ and its belief set Bel(Ψ). For example, Ψ and Ψ ∗ µ in Postulate (R*1) refer, respectively, to the current belief state and to the posterior belief state; and Ψ ∗ µ |= µ is just shorthand for Bel(Ψ ∗ µ) |= µ. The following are the (modified) KM postulates, which in turn are a reformulation of the AGM postulates:

• (R*1) Ψ∗ µ |= µ.
• (R*2) If Ψ∧ µ is satisfiable, then Ψ∗ µ ≡ Ψ∧ µ.
• (R*3) If µ is satisfiable, then Ψ∗ µ is also satisfiable.
• (R*4) If Ψ1 = Ψ2 and µ1 ≡ µ2, then Ψ1 ∗ µ1 ≡ Ψ2 ∗ µ2.
• (R*5) (Ψ∗ µ) ∧ φ |= Ψ∗ (µ ∧ φ).
• (R*6) If (Ψ ∗ µ) ∧ φ is satisfiable, then Ψ ∗ (µ ∧ φ) |= (Ψ ∗ µ) ∧ φ.

Darwiche and Pearl have given a representation theorem for Postulates (R*1)-(R*6) wrt. a revision mechanism based on total pre-orders over possible worlds:

Definition 2.1 Let W be the set of all worlds (interpretations) of a propositional language L. A function that maps each belief state Ψ to a total pre-order ≤Ψ on W is called a faithful assignment iff

• If w1,w2 |= Ψ, then w1 =Ψ w2.
• If w1 |= Ψ and w2 ̸|= Ψ, then w1 <Ψ w2.
• If Ψ = Φ, then ≤Ψ=≤Φ.

where w1 =Ψ w2 is defined as w1 ≤Ψ w2 and w2 ≤Ψ w1; and w1 <Ψ w2 means w1 ≤Ψ w2 and w2 ̸≤Ψ w1.

The intuitive meaning of w1 ≤Ψ w2 is that w1 is at least as plausible as w2 in Ψ.

1 We assume that the corresponding belief set Bel(ψ) contains all logical consequences of ψ.

Theorem 2.2 [Darwiche and Pearl, 1997] A revision operator ∗ satisfies Postulates (R*1)-(R*6) iff there exists a faithful assignment that maps a belief state Ψ to a total pre-order ≤Ψ such that

Here, Mods(µ) denotes the set of all models of µ, and min(Mods(µ), ≤Ψ) is the set of minimal elements of Mods(µ) wrt. the pre-order ≤Ψ.

2.2 DP Postulates

In order to allow for successive revisions, in each revision step it must be fully specified how the conditional beliefs are to be modified. Following the principle of economy of information, minimal change should also be applied to the conditional beliefs. Unfortunately, although the KM postulates put much emphasis on the preservation of propositional beliefs, they do not constrain the modification of conditional beliefs. Darwiche and Pearl have shown that the KM postulates alone are too weak to adequately characterize iterated belief revision, because they support unreasonable revision behaviors [Darwiche and Pearl, 1994]. To overcome this deficiency, they proposed these four additional postulates [Darwiche and Pearl, 1997]:

• (C1) If β |= µ, then (Ψ∗ µ) ∗ β ≡ Ψ∗ β.
• (C2) If β |= ¬µ, then (Ψ∗ µ) ∗ β ≡ Ψ∗ β.
• (C3) If Ψ∗ β |= µ, then (Ψ∗ µ) ∗ β |= µ.
• (C4) If Ψ∗ β ̸|= ¬µ, then (Ψ∗ µ) ∗ β ̸|= ¬µ.

Motivation and interpretation of these postulates can be found in [Darwiche and Pearl, 1994; 1997].

To provide formal justifications, Darwiche and Pearl have presented an extension of the above representation theorem for Postulates (C1)-(C4):

Theorem 2.3 [Darwiche and Pearl, 1997] Suppose that a revision operator satisfies Postulates (R*1)-(R*6). The operator satisfies Postulates (C1)-(C4) iff the operator and its corresponding faithful assignment satisfy:

• (CR1) If w1,w2 |= µ, then w1 ≤Ψ w2 iff w1 ≤Ψ∗µ w2.
• (CR2) If w1,w2 ̸|= µ, then w1 ≤Ψ w2 iff w1 ≤Ψ∗µ w2.
• (CR3) If w1 |= µ and w2 ̸|= µ, then w1 <Ψ w2 implies w1 <Ψ∗µ w2.
• (CR4) If w1 |= µ and w2 ̸|= µ, then w1 ≤Ψ w2 implies w1 ≤Ψ∗µ w2.

Furthermore, [Darwiche and Pearl, 1997] showed that their additional postulates are consistent with the (modified) KM postulates. They did so by defining a concrete revision operator which satisfies both (R*1)-(R*6) and (C1)-(C4).

2.3 Why Not Absolute Minimization?

A different approach to studying iterated belief revision is by defining concrete revision operators. For instance, [Boutilier, 1993] proposed a specific revision operator (known as natural revision) which satisfies the modified KM postulates and the following one:

As shown by [Darwiche and Pearl, 1997; Boutilier, 1996], postulate (CB) imposes absolute minimization on the change of conditional beliefs:

Theorem 2.4 Suppose that a revision operator satisfies Postulates (R*1)-(R6). The operator satisfies Postulate (CB) iff the operator and its corresponding faithful assignment satisfy

Condition (CBR) says that the agent should keep as much of the ordering information in Ψ as possible while satisfying the KM postulates. At first glance, therefore, it seems that Condition (CBR) complies with the principle of economy of information. However, Postulate (CB) is too radical since any severe revision necessarily cancels all previous evidences [Darwiche and Pearl, 1994; Zhang, 2004]. This suggests that absolute minimization of the change of conditional beliefs is overly strict and not desirable in general. It is easy to see that the DP postulates are a weakening of Postulate (CB), in the sense Postulate (CB) implies all of the DP postulates but not vice versa.

3 The Problem of Implicit Dependence

Although most counter-examples in [Darwiche and Pearl, 1997] against the KM postulates are solved by adding the DP postulates, several open problems remain. For instance, the DP postulates are consistent with (CB), hence they do not block counter-examples against natural revision, like the following [Darwiche and Pearl, 1997]:

Example 1 We encounter a strange new animal and it appears to be a bird, so we believe the animal is a bird. As it comes closer to our hiding place, we see clearly that the animal is red, so we believe that it is a red bird. To remove further doubts about the animal birdhood, we call in a bird expert who takes it for examination and concludes that it is not really a bird but some sort of mammal. The question now is whether we should still believe that the animal is red.

As argued in [Darwiche and Pearl, 1997], we have every reason to keep our belief that the animal is red, since birdhood and color are not correlated. However, natural revision enforces us to give up the belief of the animal's color: According to Postulate (CB), since bird∗red |= ¬(¬bird) it follows that (bird∗red)∗¬bird ≡ bird∗¬bird.

In being compatible with (CB), the DP postulates are not strong enough to guarantee that the belief of the animal's color is retained. This can be intuitively explained as follows: After observing the animal's color, we are actually acquiring a new conditional belief, namely, that the animal is red even if it were not a bird i.e., ¬bird ≫ red. However, the DP postulates do not enforce the acquisition of conditional beliefs. In the sequel, we first give a formal analysis of this weakness of the DP postulates, and then we present an additional postulate by which this problem is overcome.

It is well known (see, e.g., [G¨ardenfors and Makinson, 1988]) that if a belief state Ψ suffices to uniquely determine a revision strategy that satisfies the AGM (or the KM) postulates, then the belief state determines a unique, total pre-order

≤Ψ (known as epistemic entrenchment) over L which satisfies certain conditions. Given an epistemic entrenchment, the corresponding belief revision operator is defined by the following condition: For any β,

Other forms of total pre-orderings on L have been proposed, e.g., [Rott, 1991; Williams, 1992]. All of these orderings require extra-logical information, that is, they cannot be determined by pure logical relations among the sentences. Although we focus on epistemic entrenchment, the analysis that follows does not depend on this specific ordering; it can be easily adapted to the approaches just mentioned.

To begin with, we define the notion of dependence between sentences wrt. a belief state as follows [Fari˜nas del Cerro and Herzig, 1996]:

Definition 3.1 A sentence β depends on another sentence µ in belief state Ψ precisely when Ψ |= β and Ψ∗¬µ ̸|= β. Two sentences µ, β are called dependent in Ψ if either µ depends on β or β depends on µ in Ψ.

Consider, now, a (non-tautological) new evidence µ. Whenever Ψ |= β, condition (C*) implies that if µ ≥Ψ µ ∨ β, then β is (implicitly) dependent on µ in Ψ. This kind of dependency could be problematic. In particular, it is possible that two initially independent sentences become, undesirably, dependent after a revision step. In Example 1, say, red becomes dependent on bird after revising by red if natural revision is used.

Epistemic entrenchment reveals that the problem of natural revision is that it assigns the lowest degree of belief to a new evidence without asserting conditional beliefs for independence. Thus the new evidence depends on all other beliefs which survive the revision process. This explains why severe revision always cancels all previous evidences.

4 A Postulate of Independence

The analysis in the previous section shows that in order to overcome the problem of implicit dependence, the revision operator must explicitly assert some conditional beliefs. It is easy to see that the DP postulates only require the preservation of conditional beliefs when a belief state Ψ is revised with µ: Postulates (C1) and (C2) neither require to add nor to remove certain conditional beliefs (namely, those conditioned on β) in case β |= µ or β |= ¬µ; Postulate (C3) requires to retain the conditional belief β ≫ µ; finally, Postulate (C4) requires not to obtain the new conditional belief β ≫ ¬µ. Since none of the DP postulates requires to make independence assumptions, a new postulates is necessary to avoid undesired dependencies.

The revision process may introduce undesirable dependencies in both directions. That is, it could be that the new evidence becomes dependent on existing beliefs, or the other way around. Prior to stating the new postulate, we show that the DP postulates impose some constraints on the retention of the independence information in one direction. In the presence of the KM postulates, Postulate (C2) implies the following:

This essentially means that if β is not dependent on the new evidence µ in Ψ, then it also does not depend on µ in Ψ ∗ µ.

In order to ensure the explicit assertion of independence information in the other direction, we propose the following postulate of Independence to complement the DP postulates:

Basically, Postulate (Ind) says that if the belief in β ⊃ ¬µ is not strongly held in Ψ, then µ does not depend on ¬β in Ψ ∗ µ.

Postulate (Ind) is sufficient to overcome the problem of implicit dependence, as can be shown by reconsidering Example 1. According to (Ind), (bird∗red)∗¬bird |= red, given that bird∗¬bird ̸|= ¬red. This shows that the new postulate blocks unreasonable behaviors which are admitted by the DP postulates. In Section 5, we will also argue that Postulate (Ind) is not overly strict.

In order to formally justify our new postulate, we will first provide a representation theorem along the line of Theorem 2.3. Thereafter, we will give a concrete belief revision operator which satisfies (Ind).

4.1 ARepresentation Theorem

For the proof of the representation theorem, we need the following observation, which is a consequence of Theorem 2.2.

Observation 4.1 Suppose that a revision operator satisfies Postulates (R*1)-(R*6). If ̸|= ¬β, then Ψ∗β |= µ precisely when there exists a world w such that w |= µ ∧ β and w <Ψ w′ for any w′ |= ¬µ∧β, where ≤Ψ is the corresponding faithful assignment.

Theorem 4.2 Suppose that a revision operator satisfies Postulates (R*1)-(R*6). The operator satisfies Postulate (Ind) iff the operator and its corresponding faithful assignment satisfy:

Proof: "⇐": Assume Ψ∗β ̸|= ¬µ. FromObservation 4.1, it follows that for any world w |= β ∧ ¬µ, there exists another world w′ |= β ∧ µ such that w′ ≤Ψ w. Hence, since ≤Ψ is total, there must be a world w1 such that w1 |= µ ∧ β and w1 ≤Ψ w2 for any w2 |= ¬µ ∧ β. Condition (IndR) then implies that w1 <Ψ∗µ w2 for any w2 |= ¬µ ∧ β. Due to Observation 4.1, we have (Ψ∗µ)∗β |= µ.

"⇒": Assume w1 |= µ, w2 |= ¬µ, and w1 ≤Ψ w2. Let β be such that Mods(β) = {w1,w2}. From Theorem 2.2, it follows that w1 ∈ Mods(Ψ∗β). Hence Ψ∗β ̸|= ¬µ. Postulate (Ind) implies (Ψ ∗ µ) ∗ β |= µ. Due to Postulates (R*1) and (R*3), Mods((Ψ ∗ µ) ∗ β) = {w1}. From Theorem 2.2, it follows that w1 <Ψ∗µ w2. ✷

An immediate consequence of Theorem 2.3 and 4.2 is that Postulate (Ind) implies both (C3) and (C4). Theorem 4.2 also shows that Postulate (Ind) is not overly constrained: Condition (IndR) only requires to decrease the plausibility of the worlds violating the new evidence µ and not to decrease the plausibility of the worlds confirming µ.

4.2 Properties of the Independence Postulate

We suggest to use the KM postulates along with Postulates (C1), (C2), and (Ind) to govern iterated belief revision. To show that these postulates together are consistent, we present a concrete revision operator which satisfies all of them. The operator is based on Spohn's proposal of revising ordinal conditional functions [Spohn, 1988], which can be viewed as a qualitative version of Jeffrey's Rule of probabilistic conditioning [Goldszmidt, 1992].

An ordinal conditional function is a function k from a given set of worlds into the class of ordinals. Intuitively, the ordinals represent degrees of plausibility. The lower its ordinal, the more plausible is a world. An ordinal conditional function encodes both a belief set and the conditional beliefs. The belief set Bel(k) is the set of sentences which hold in all worlds of rank 0 (the smallest ordinal):

From now on, we use an ordinal conditional function and its belief set interchangeably; e.g., µ ∈ k means µ ∈ Bel(k), and k ∧ µ denotes ∧ Bel(k) ∧ µ. A ranking of worlds can be extended to a ranking of sentences as follows:

Put in words, the rank of a formula is the lowest rank of a world in which the formula does not hold. Hence, the higher the rank of a sentence, the firmer the belief in it. In fact, it is not hard to see that an ordinal conditional function k determines an epistemic entrenchment as follows:

Our belief revision operator allows to assign different plausibility degrees to new evidences; standard KM/DP revision is easily obtained as a special case by using a fixed value in all iterations [Darwiche and Pearl, 1997]. An ordinal conditional function k is revised according to new evidence µ with plausibility degree m > 0 as follows:

Assuming the same degree of plausibility for any new evidence, satisfiability of the KM postulates along with Postulates (C1), (C2), and (Ind) by the revision defined in (2) is an almost direct consequence of Theorem 2.2, 2.3, and 4.2. But we can even prove a stronger result with varying plausibility values m.

Theorem 4.3 For any m > 0, the belief revision operator defined by (2) satisfies all KM postulates (R*1)-(R*6), where Bel(Ψ) and Ψ ∗ µ are, respectively, identified with ∧ Bel(k) and k∗µ,m.

Lemma 4.4 Let k be an arbitrary ordinal conditional function and µ a new evidence with plausibility degree m, then for any non-tautological sentence β,

Theorem 4.5 For arbitrary m1,m2 > 0, the belief revision operator defined by (2) satisfies the following conditions: 2

• (EC1) If α |= µ, then (k∗µ,m1 )∗α,m2 ≡ k∗α,m2 .
• (EC2) If α |= ¬µ, then (k∗µ,m1 )∗α,m2 ≡ k∗α,m2 .
• (EInd) If there exists m such that k∗¬β,m ̸|= ¬µ, then (k∗µ,m1 )∗¬β,m2 |= µ

Proof: If |= ¬α, Condition (EC1) holds trivially. Assume that α |= µ and ̸|= ¬α. By (2),

Likewise,

Since α |= µ, for any w |= α we have k∗µ,m1 (w) = k(w) - k(¬µ) by (2). Since µ ⊃ ¬α ≡ ¬α and ̸|= ¬α, it follows from Lemma 4.4 that k∗µ,m1 (¬α) = k(¬α) - k(¬µ). Hence, (4) is equivalent to

This and (3) implies (k∗µ,m1 )∗α,m2 ≡ k∗α,m2 . Condition (EC2) can be proved analogously.

We prove Condition (EInd) by contradiction. To begin with, from the assumption that k∗¬β,m ̸|= ¬µ it follows that ̸|= β and ̸|= µ ⊃ β. Furthermore, there exists w such that k∗¬β,m(w) = 0, w |= ¬β ∧ µ, and k(w) = k(β). With the help of (1), this implies k(β) = k(µ ⊃ β).

Now assume that (k∗µ,m1 )∗¬β,m2 ̸|= µ. It follows that there exists w′ such that (k∗µ,m1 )∗¬β,m2 (w′ ) = 0, w′ |= ¬β ∧ ¬µ, and k∗µ,m1 (w′ ) = k∗µ,m1 (β). Since k(w) = k(β) and w′ |= ¬β, we have k(w′ ) ≥ k(w). Hence by (2), k∗µ,m1 (w′ ) = k(w′ ) + m1 > k(β). But from Lemma 4.4 it follows that k∗µ,m1 (β) ≤ k(β), since ̸|= β and ̸|= µ ⊃ β. This contradicts k∗µ,m1 (w′ ) = k∗µ,m1 (β). ✷

Theorem 4.3 and 4.5 show that Postulate (Ind) is consistent with the KM and DP postulates. On the other hand, (Ind) does not follow from these postulates, which can be seen by the fact that (Ind) is incompatible with (CB), the postulate that characterizes natural revision.

It is worth mentioning that revisions based on ordinal conditional functions are particularly suitable for implementations of belief revision. For instance, [Jin and Thielscher, 2004] presented a method (and its implementation) for revision of belief bases which is equivalent to the belief revision defined by (2).

5 RelatedWork and Conclusions

The first DP approach [Darwiche and Pearl, 1994] seemed excessively strong because one of the postulates, (C2), is inconsistent with the classical AGM framework, as pointed out by [Freund and Lehmann, 1994]. Apart from the solution by [Darwiche and Pearl, 1997], namely, to use a modified version of KM (which we followed in this paper), several other proposals were made to overcome the inconsistency. For instance, Lehmann proposed a different way of weakening the AGM postulates accompanied by quite different additional postulates for iterated revision, in which a belief state consists of a sequence of revision sentences [Lehmann, 1995]. Nayak et al. suggested to retain the original AGM framework and to consider a belief revision operator as a unary function (associated with a belief state). The idea is to view belief revision as dynamic, in the sense that the operator evolves after each step [Nayak et al., 1996; 2003]. On the other hand, one point has been generally accepted, namely, that iterated belief revision should not be considered as a purely set-theoretical change of belief sets but as an evolution of belief states, which encapsulate beliefs with some kind of information of the firmness of beliefs [Zhang, 2004].

2 Note that, as before, we abuse notation by simply writing k ∗µ,m instead of ∧ Bel(k∗µ,m) etc.

The problem of the DP postulates to be overly permissive was already studied by Nayak et al., [1996; 2003]. They suggested to strengthen the DP postulates by the following socalled postulate of Conjunction:

It is easy to see that (Conj) implies another postulate, which they called postulate of Recalcitrance:

In the following, we argue that Postulate (Conj), while strengthening the DP postulates, is overly strict. To this end, we show that even Postulate (Rec) is too strong. The latter says that, as long as β ⊃ ¬µ is not a tautology, it should be canceled after a successive revision by µ followed by β, no matter how strong the initial belief in β ⊃ ¬µ. A simple example shows that this behavior is not reasonable:

Example 2 All her childhood, Alice was taught by her parents that a person who has told a lie is not a good person. So Alice believed, initially, that if Bob has told a lie then he is not a good person. After her first date with Bob, she began to believe that he is a good guy. Then a reliable friend of Alice warns her that Bob is in fact a liar, and Alice chooses to believe her. Now, should Alice still believe that Bob is a good guy?

According to Postulate (Rec), Alice should not challenge Bob's morality and still believe he is good, and hence to disbelieve what her parents taught her. But it is at least as reasonable to give up the belief that Bob is good. This shows that Postulate (Rec) is too strict a criterion for belief revision operators.

With regard to the postulate we have proposed in this paper, it is easy to see that (Ind) is a weakening of Postulate (Rec). This raises the question whether Postulate (Ind) weakens too much. Let us consider an example, taken from [Nayak et al., 1996], which, at first glance, seems to show that this is indeed the case.

Example 3 Our agent believes that Tweety is a singing bird. However, since there is no strong correlation between singing and birdhood, the agent is prepared to retain the belief that Tweety sings even after accepting the information that Tweety is not a bird, and conversely, if the agent were to be informed that Tweety does not sing, she would still retain the belief that Tweety is a bird. Imagine that the agent first receives the information that Tweety is in fact not a bird, and later learns that Tweety does not sing.

Nayak et al. claimed that it is only reasonable to assume that the agent should, in the end, believe that Tweety is a nonsinging non-bird. Indeed, with Ψ ≡ singing ∧ bird it follows from Postulate (Rec) that (Ψ ∗ ¬bird) ∗ ¬singing |= ¬bird, since ̸|= ¬singing ⊃ bird. Postulate (Ind), on the other hand, does not apply in this case. But the behavior which is claimed to be the only reasonable one is not generally justified. Suppose, for example, the agent initially believes firmly that ¬singing ⊃ bird. It is then possible, after revising by ¬bird, that the belief in ¬singing ⊃ bird is stronger than the belief in ¬bird. In this case, after further revising by ¬singing, the agent believes that Tweety is a bird after all.

In [Zhang, 2004], it has also been argued that Postulate (Rec) is too radical because only those revision operators are admissible which assign the highest belief degree to the new evidence. This can be considered a further justification of our Postulate (Ind). Moreover, it is easy to verify that Postulate (Ind) is satisfied by all revision operators with memory [Konieczny and P´erez, 2000].

We have formally justified our new postulate by a representation theorem and a concrete revision operator which satisfies both (Ind) and KM/DP. Other concrete revision operators have been proposed, e.g., in [Williams, 1995], which also use ordinal conditional functions. The main difference is that these operators do not satisfy the Independence postulate.