On the Logic of Theory Change Iteration of KM-Update, Revised

1 Introduction

Belief revision focuses on how an agent changes her beliefs when she encounters new information inconsistent with her initial beliefs. The notable AGM postulates, proposed by Alchourr´on et al. [1985], became a standard framework to capture the rational behavior of belief revision. Katsuno and Mendelzon [1991b] proposed a characterization of all revision operators that satisfy AGM postulates in terms of total preorders over possible worlds.

∗Both are corresponding authors.

Belief update, another significant type of belief change, concentrates on how an agent will modify her beliefs about a dynamically-changing world in view of new information. As in belief revision, Katsuno and Mendelzon [1991a] proposed the KM postulates for regulating rational belief update, which models the process of update as a function of belief sets. Furthermore, they offered a semantic characterization based on partial preorders over possible worlds, and clarified the distinctions between update and revision from the modeltheoretic perspective. There is only one total preorder for the belief set K in belief revision. In contrast, in belief update, a collection of partial preorders is induced by K where each preorder is associated to each possible world satisfying K.

Although the AGM postulates were considered as a basic framework for belief revision, it is shown to be too permissive to exclude some unreasonable revision operators in the iteration [Darwiche and Pearl, 1997]. The reason can be attributed to the fact that it is comprised of merely a set of one-step postulates, failing to properly deal with the sequential new information in the process of iterated belief revision. To remedy this defect in belief revision, Darwiche and Pearl supplemented the AGM paradigm with four postulates (C1)- (C4) (called DP postulates) and use belief states to denote the belief of an agent instead of belief sets. Two different belief states may have the same belief sets, but not vice versa.

Likewise, we argue that the same problem as above exists for the KM postulates in belief update. In details, the KM framework is unable to regulate the preferences for subsequent updates during the iterated update process, leading to some counter-intuitive results. We use the following example to briefly illustrate the problem.

Example 1. Let us consider a table with two zones: left and right. There are a book, a cup and a toy on any side on the table. We denote by b (resp. c / t) the proposition "the book (resp. cup / toy) is on the left zone of the table".

Initially, everything is on the right zone, and hence the initial belief set K is ¬b ∧ ¬c ∧ ¬t. We first instruct a robot to move at least one of the book and the cup to the left zone, which is described as the new information ϕ = b∨c. Suppose that updated belief set K⋄ϕ is (b ↔ ¬c)∧¬t, that is, exactly one of the book and cup is on the left zone, and the toy is on the right zone. The robot is then given a fresh instruction to place the cup on the left, which is the new information φ = c. According to the KM postulates, it is acceptable that the updated belief set (K ⋄ ϕ) ⋄ φ becomes ¬b ∧ c. However, after updating by ϕ, the agent has believed that the toy was on the right zone. It seems unreasonable to require the agent to give up this belief after putting the cup on the left zone.

The two updated beliefs K ⋄ ϕ and (K ⋄ ϕ) ⋄ φ in the above example are both KM-compatible. Since the KM postulates do not constrain the update strategy after iteration, counter-intuitive results will emerge after multiple iterations.

One topic worth investigation is what will happen if we incorporate the iterated revision postulates above to a belief update scenario. Following the semantic characterization for every iterated postulate in belief revision, Ferm´e and Gonc¸alves [2023] integrated these postulates in belief update. However, Ferm´e and Gonc¸alves's approach has the following shortcomings. (1) Each belief state defined in [Ferm´e and Gonc¸alves, 2023] includes not only the belief set but also an update operator for belief sets, that is, a function mapping a belief set and a sentence to a new belief set. In contrast, a belief state defined in [Darwiche and Pearl, 1997] encodes the preference about possible worlds via faithful assignments and is associated with only the belief set. The revision operator for belief states modifies the preference about possible worlds, and do not rely on any revision operator for belief sets. Hence, the associated update operator of belief states in [Ferm´e and Gonc¸alves, 2023] is redundant. (2) The fundamental concept of the semantic definition is faithful complete assignments, that is, a function that maps each belief state to a complete collection of partial preorders. A complete collection of partial preorders is such that there is a unique partial preorder ≤w for every possible world w. However, in the semantic definition of update operators, it is unnecessary to consider the partial-preorders centered at the possible world that is not a model of the associated belief set. (3) The semantic definition of update operators for belief states [Ferm´e and Gonc¸alves, 2023] is based on the initial belief set rather than the most recent belief set. This obviously violates the desired property of iterated belief change including iterated belief revision. (4) DP postulates was defined for iterated belief revision. Ferm´e and Gonc¸alves chose DP postulates as the basis for iterated belief update, but did not discuss the rationale of any DP postulate within the update context.

This paper is intended to overcome the above shortcomings of Ferm´e and Gonc¸alves's approach. The main contributions are the following. We first adopt the original definition of belief states, proposed by Darwiche and Pearl [1997], within update context and modify the two postulates (U 4) and (U 8) defined in [Ferm´e and Gonc¸alves, 2023] as the update operator for belief sets occur explicitly in these two postulates. We then propose the notion of faithful collective assignments, that is, a function that maps each belief state to a collection of partial preorders which is centered at one possible world of the associated belief set. Furthermore, we give the new semantic definition of updating belief states, which is based on the possible worlds satisfying the most recent belief sets rather than the initial ones. We also provide the exact semantic characterizations via partial preorders for every DP postulate of iterated belief update. We offer some concrete examples to illustrate the motivation of the usage of DP postulates in iterated belief update. Finally, we analyze the compatibility between the DP iterated postulates and the modified KM postulates for belief update. We identify an update operator that satisfies (CU3) and (CU4). In particular, we show that each of (CU1) and (CU2) is inconsistent with the KM postulates.

2 Formal Preliminaries

Throughout this paper, we fix a finite set P of propositional variables. We define L to be the propositional language built from P, the connectives ¬, ∧ and ∨, and two Boolean constants ⊤ (truth) and ⊥ (falsity).

A propositional sentence ψ is complete, iff for every sentence φ ∈ L, ψ |= φ or ψ |= ¬φ. A propositional sentence ψ is consistent, iff there is no sentence φ ∈ L s.t. ψ |= φ and ψ |= ¬φ. A possible world w is a complete consistent set of literals over P, i.e., for every p ∈ P, either p ∈ w or ¬p ∈ w. We use M to denote the set of all possible worlds, and [ϕ] to denote the set of all possible worlds in which ϕ holds. For a finite set of worlds W, Form(W) denotes the sentence ∨w∈W (∧l∈w l). For ease of representation, we sometimes use w1, · · · ,wn to denote the set {w1, · · · ,wn}.

A (partial) preorder ≤ over M is a reflexive, transitive binary relation onM. A preorder is total if for all w,w′ ∈M, either w ≤ w′ or w′ ≤ w. We define < as the strict part of ≤, i.e., w < w′ iff w ≤ w′ and w′ ̸≤ w. We define ≈ as the symmetric part of ≤, i.e., w ≈ w′ iff w ≤ w′ and w′ ≤ w.

3 Background

In this section, we briefly review the axiomatic and semantic characterization of belief revision [Alchourr´on et al., 1985], iterated belief revision [Darwiche and Pearl, 1997], belief update [Katsuno and Mendelzon, 1991a] and iterated belief update [Ferm´e and Gonc¸alves, 2023].

3.1 Belief Revision

The original AGM paradigm models the notion of belief revision as a function that maps a belief set K and a sentence ϕ to a new belief set K ◦ ϕ. In this paper, a belief set is defined as a propositional sentence. However, the revision function over belief sets only differentiates what the agent believes and what she does not believe, but does not compare the plausibility degree of different information which the agent does not believe. This leads to improper behaviors of revision functions over belief sets on iterated belief revision [Darwiche and Pearl, 1997]. To fix this defect, Darwiche and Pearl proposed the notion of belief states (also referred to as epistemic states), redefined revision function on belief states, and reformulated the AGM postulates accordingly. Darwiche and Pearl did not provide a standard definition of belief states, and only required that each belief state S is associated with a belief set B(S). We use this abstract representation of the belief state herein.

The following are the modified AGM postulates which shift from belief sets to belief states and are originated from [Darwiche and Pearl, 1997].

• (R*1) B(S ◦ φ) |= φ.
• (R*2) If B(S) ∧φ is consistent, then B(S ◦ φ) ≡ B(S) ∧φ.
• (R*3) If φ is consistent, so is B(S ◦ φ).

Darwiche and Pearl provided a representation theorem for the modified AGM postulates based on the notion of faithful total preorders and faithful assignments proposed by Katsuno and Mendelzon [1991b]. Given a sentence φ, a total preorder ≤φ over M is faithful to φ, iff (1) w ≈φ w′ for every two possible worlds w,w′ ∈ [φ]; and (2) w <φ w′ for every two possible worlds w ∈ [φ] and w′ ∈ [¬φ]. A faithful assignment is a function that maps each belief state S to a total preorder ≤S that is faithful to B(S). The following is the representation theorem for the modified AGM postulates.

Theorem 1 ([Darwiche and Pearl, 1997]). A revision operator ◦ satisfies postulates (R*1)-(R*6) iff there is a faithful assignment that maps each belief state S to a total preorder ≤S s.t. [B(S ◦ φ)] =min([φ],≤S).

3.2 Iterated Belief Revision

In the AGM paradigm, there is no guidance on the relationship between the initial revision strategy and the subsequent one. To solve this problem, Darwiche and Pearl proposed DP postulates that describe rational iterated belief revision.

• (C1) If φ |= ϕ, then B((S ◦ ϕ) ◦ φ) ≡ B(S ◦ φ).
• (C2) If φ |= ¬ϕ, then B((S ◦ ϕ) ◦ φ) ≡ B(S ◦ φ).
• (C3) If B(S ◦ φ) |= ϕ, then B((S ◦ ϕ) ◦ φ) |= ϕ.
• (C4) If B(S ◦ φ) ̸|= ¬ϕ, then B((S ◦ ϕ) ◦ φ) ̸|= ¬ϕ.

Darwiche and Pearl proved that postulates (C1)-(C4) correspond to the following semantics constraints (CR1)-(CR4) on possible worlds, respectively.

• (CR2) If w1,w2 ∈ [¬ϕ], then w1 ≤S w2 iff w1 ≤S◦ϕ w2.

Theorem 2 ([Darwiche and Pearl, 1997]). Let ◦ be a revision operator satisfying (R*1)-(R*6). Then, ◦ satisfies (Ci) iff the operator and its corresponding faithful assignment satisfies (CRi) for 1 ≤ i ≤ 4.

3.3 Belief Update

In the belief update literature, an agent is intended to modify her beliefs about a dynamically-changing environment in view of new information. Katsuno and Mendelzon [1991a] clarified the distinction between belief revision and update. Furthermore, following the AGM paradigm, they presented the KM postulates to characterize a family of rational belief update functions, which map a belief set K and a sentence φ to a new belief set K ⋄ φ.

• (U2) If K |= φ, then K ⋄ φ ≡ K.
• (U3) If both K and φ are consistent, so is K ⋄ φ.
• (U4) If φ ≡ ϕ, then K ⋄ φ ≡ K ⋄ ϕ.
• (U5) (K ⋄ φ) ∧ ϕ |= K ⋄ (φ∧ ϕ).
• (U6) If K ⋄ φ |= ϕ and K ⋄ ϕ |= φ, then K ⋄ φ≡K ⋄ ϕ.
• (U7) If K is complete, then (K⋄φ)∧(K⋄ϕ) |= K⋄(φ∨ϕ).

To describe the process of belief update, Katsuno and Mendelzon proposed the notion of faithful preorder associated with possible worlds. Formally, given a possible world w, a preorder ≤w over M is faithful to w, iff for every possible world w′ , w′ ̸= w only if w <w w′ . A faithful pointwise assignment is a function that maps each possible world w to a partial preorder that is faithful to w. The following theorem shows the semantic characterization of KM postulates.

Theorem 3 ([Katsuno and Mendelzon, 1991a]). An update operator ⋄ satisfies postulates (U1)-(U8) iff there is a faithful pointwise assignment that maps each possible world w to a partial preorder ≤w s.t. [K ⋄ φ] = ⋃ w∈[K] min([φ], ≤w).

3.4 Iterated Belief Update

Similarly to AGM paradigm, the KM framework ignores iterations in update process. To address this issue, Ferm´e and Gonc¸alves [2023] extended KM postulates for belief states so as to capture rational iterated update. In Ferm´e and Gonc¸alves's framework, each belief state S is associated to an initial belief set Bi(S), a most recent belief set B(S) and a belief update operator O(S) satisfying the KM postulates (U1)-(U8). The initial belief set Bi(Si φ1 · · · φn) is defined as B(Si) where Si is the initial belief state of Si φ1 · · · φn. The update operator for belief states satisfies the following two properties: (1) B(S φ) = B(S) ⋄ φ; and (2) if O(S1) = O(S2), then O(S1 φ) = O(S2 φ) .

• (U 1) B(S φ) |= φ.
• (U 2) If B(S) |= φ, then B(S φ) ≡ B(S).
• (U 3) If both B(S) and φ are consistent, so is B(S φ).
• (U 4) If B(S1) ≡ B(S2), O(S1) = O(S2) and φ ≡ ϕ, then B(S1 φ) ≡ B(S2 ϕ).
• (U 5) B(S φ) ∧ ϕ |= B(S (φ∧ ϕ)).

(U 7) If B(S) is complete, then B(S φ) ∧ B(S ϕ) |= B(S (φ∨ ϕ)).

A collection {≤w}w∈W of partial preorders is complete iff W = M. A faithful complete assignment is a function that maps each belief state S to a complete collection {≤Sw }w∈M of partial preorders s.t. each element ≤Sw is faithful to w.

Theorem 4 ([Ferm´e and Gonc¸alves, 2023]). An update operator satisfies postulates (U 1)-(U 8) iff there is a faithful complete assignment that maps each belief state S to a complete collection {≤Sw }w∈M of partial preorders s.t. [B(S φ)] = ⋃ min([φ], ≤Sw )1 .

The iterated postulates and their semantic characterization can be easily transferred to belief update. To distinguish the iterated postulates for belief update and revision, we use (CUi) for the iterated update version of (Ci) and (CRUi) for the semantic characterization of the postulate (CUi). For example, (CU1) is "If φ |= ϕ, then B((S ϕ) φ) ≡ B(S φ)" and (CRU1) is "If w1,w2 ∈ [ϕ], then w1 ≤Sw w2 iff w1 ≤S ϕ w w2."

Theorem 5 ([Ferm´e and Gonc¸alves, 2023]). Let be an update operator satisfying (U 1)-(U 8). Then, satisfies (CUi) iff the operator and its corresponding faithful complete assignment satisfies (CRUi) for 1 ≤ i ≤ 4.

4 ANewApproach to Iterated Belief Update

In this section, we propose a new approach to iterated belief update so as to cope with the first three shortcomings of Ferm´e and Gonc¸alves's approach mentioned in Introduction.

4.1 Modified Update Postulates on Darwiche and Pearl's Belief States

To overcome the first shortcoming, we directly adopt the original definition of belief states proposed in [Darwiche and Pearl, 1997]. Only (U 4) and (U 8) of modified KM postulates utilizes the associated update operator. We therefore redefine these two postulates in the following.

Postulate (U 4∗ ) is identical with (R*4). If belief states S1 and S2 are identical, then they must lead to the same belief state when updating equivalent new information. Postulates

1 We remark that, in Theorem 3.4 of [Ferm´e and Gonc¸alves, 2023], the semantic definition of the update operator uses the most recent belief set B(S) rather than the initial one Bi(S). However, after carefully examining the proof of the representation theorem for iterated update postulates (Proof of Theorem 3.5 in [Ferm´e and Gonc¸alves, 2023]), we confirm that the correct definition is based on Bi(S), in line with the proof of the Master thesis [Gonc¸alves, 2015] that is the preliminary version of the paper [Ferm´e and Gonc¸alves, 2023].

(U8) and (U 8∗ ) both aim to achieve the distributive law of the update operator over disjunction although they look quite different at first glance. This is because the disjunction connective cannot directly apply to belief state. We illustrate the shift from (U8) to (U 8∗ ) in the following. Since K ≡ ∨ w∈[K] Form(w), we can obtain postulate (U8')

equivalent to (U8) via iteratively applying (U8).

According to postulate (U8'), the update of any belief set K reduces to the update of each [K]-possible world. The update operator takes a belief state and a sentence as input. In order to describe the update of each possible world wi of B(S), we choose a belief state Si such that the model of its associated belief set B(Si) is exactly wi. Hence, postulate (U 8∗ ) coincides with (U8) and (U8').

4.2 Semantics of Belief Update over Belief States

We hereafter define the notion of faithful collective assignments that map each belief state S to a collection {≤Sw }w∈[B(S)] of partial preorders. We remark that the set {≤Sw }w∈[B(S)] is incomplete and contains no partial preorders centered at any possible world w /∈ [B(S)]. We therefore use faithful collective assignments instead faithful complete ones as the basis of semantics of belief update so as to solve the second shortcoming. For ease of presentation, we use ≤S for a collection {≤Sw }w∈[B(S)] of partial preorders.

Definition 1. A faithful collective assignment is a function that maps each belief state S to a collection ≤S of partial preorders s.t. for each belief state S and each possible world w ∈ [B(S)], we have that

• each preorder ≤Sw is faithful to w; and
• there is a belief state S′ s.t. B(S′ ) ≡ Form(w) and ≤Sw=≤S′ w .

The first condition of faithful collective assignments is the same as the faithful property of faithful pointwise assignment in belief update. The second condition divides a belief state S into a collection of belief states such that the updated belief set S φ is equivalent to the disjunction of the belief set S′ φ. This ensures postulate (U 8∗ ) is satisfied.

We point out the difference among faithful assignments for (iterated) belief revision, faithful pointwise assignments for belief update, faithful collective assignments and faithful complete assignments for iterated belief update. A faithful assignment assigns each belief state to a single total preorder and a faithful pointwise assignment maps each possible world to a single partial preorder. In contrast, a faithful collective assignment associates each belief state with a collection of partial preorders. In addition, a faithful complete assignment maps each belief state with a complete set of partial preorders.

Theorem 3 can be extended to the modified KM postulates and faithful collective assignments.

Theorem6. An update operator satisfies postulates (U 1)- (U 3), (U 4∗ ), (U 5)-(U 7) and (U 8∗ ) iff there is a faithful collective assignment that maps each belief state S to

It is observed from Theorem 6 that the semantics employs the most recent belief set B(S) rather than the initial one Bi(S), and hence addresses the third shortcoming.

4.3 Semantics Characterization of Iterated Belief Update on New Semantics

We offer the model-theoretic characterization of each DP iterated postulate based on the new semantics of belief update.

(CRU1∗ ) For every N ⊆ [ϕ], the following hold

(CRU2∗ ) For every N ⊆ [¬ϕ], the following hold

(CRU3∗ ) For every N ⊆ M s.t. min(N,≤Sw ) ⊆ [ϕ] holds for every w ∈ [B(S)], we have min(N,≤S ϕ w′ ) ⊆ [ϕ] for every w′ ∈ [B(S ϕ)].

We hereafter illustrate the relationship between postulate (CU1) and its model-theoretic characterization. Postulate (CU1) can be split into two parts:

Suppose that [φ] = N and w′′ ∈ [B(S φ)]. Since φ |= ϕ, N ⊆ [ϕ]. According to Postulate (CU1Forth), w′′ ∈ [B((S ϕ) φ)]. By the semantics defined in Theorem 6, w′′ ∈ [B(S φ)] iff w′′ ∈ min(N,≤Sw ) for a world w ∈ [B(S)]. Similarly, w′′ ∈ [B((S ϕ) φ)] iff w′′ ∈ min(N,≤S ϕ w′ ) for a world w′ ∈ [B(S ϕ)]. Therefore, postulate (CU1Forth) corresponds to the forth condition of semantics (CRU1∗ ). We can infer that postulate (CU1Back) corresponds to the back condition of (CRU1∗ ) in a similar way. (CRU2∗ ) acts similarly to (CRU1∗ ) except that it focuses on the subset of possible worlds of ¬ϕ. The semantics (CRU3∗ ) (resp. (CRU4∗ )) states that for every set N of possible worlds, if all of the minimal elements of N w.r.t. the collection ≤S of preorders satisfy (resp. falsify) ϕ, then such property should be retained after updating by the new information ϕ.

Although each iterated update postulate is identical to the corresponding iterated revision one, the semantics for iterated postulates in belief update is distinct from that in belief revision. In contrast to belief revision, which is based on a single preorder, an update strategy is defined as a collection of preorders. We formalize the iterated update strategy in terms of the minimal elements of preorders. When both of the initial and updated collection of preorders contains a single preorder, the semantics for each iterated update postulate matches with that for the corresponding iterated revision one.

The theorem below provides the correspondence between each of the above postulates and its corresponding semantics, based on faithful collective assignments.

Theorem 7. Let be an update operator satisfying (U 1)- (U 3), (U 4∗ ), (U 5)-(U 7) and (U 8∗ ). Then, satisfies (CUi) iff the operator and its corresponding faithful collective assignment satisfies (CRUi∗ ) for 1 ≤ i ≤ 4.

5 Examples for DP Postulates in Iterated Belief Update

In this section, to avoid the final limitation of Ferm´e and Gonc¸alves's approach, we provide several examples to justify the rationale of each DP postulate in iterated belief update.

Example 2 (Postulate (CU1)). Let us continue Example 1. Let P = {b, c, t} and M = {w0, . . . ,w7}. The definition of each possible world is shown in Table 1, in which an occurrence of ⊤ (resp. ⊥) indicates that the positive (resp. negative) literal of the corresponding proposition is in the possible world. For example, all of the three cells of the rows "book", "cup" and "toy" and the column "w0" are ⊥, meaning that they are all on the right zone of the table in the possible world w0.

We provide a KM-compatible update operator characterizing the update manner shown in Example 1 as follows. The initial belief state S that is associated with the belief set B(S) ≡ ¬b ∧ ¬c ∧ ¬t ≡ Form(w0), is assigned to the set ≤S of partial preorders with one element ≤Sw0 .

Then, with the emergence of the new information ϕ = b ∨ c, the updated belief state S ϕ picks the belief set B(S ϕ) ≡ (b ↔ ¬c) ∧ ¬t ≡ Form(w2,w4). To be specific, the assigned collection ≤S ϕ of two preorders are as below.

Subsequently, as the robot is informed to place the cup on the left zone, a new information φ = c occurs. The two worlds w2 and w3 are the minimal element satisfying φ w.r.t. ≤S ϕ w2 and ≤S ϕ w4 , respectively. According to the semantics of the update operator (cf. Theorem 6), we have that B((S ϕ) φ) ≡ Form(w2,w3) ≡ ¬b ∧ c, discarding unjustifiably the belief that the toy is on the right zone.

Example 3 (Postulates (CU2)). We use the previous example to justify postulate (CU2). Let us consider the following KM-compatible update operator. Initially, the belief set B(S) ≡ ¬b ∧ ¬c ∧ ¬t ≡ Form(w0). The associated partial preorder ≤Sw0 of the belief state S is:

Now, a robot is instructed to put the book and the cup on the opposite zone and put the toy on the right zone, described as ϕ = (b ↔ ¬c) ∧ ¬t. From the semantics of the update operator, the updated belief set B(S ϕ) is (b ↔ ¬c) ∧ ¬t ≡ Form(w2,w4), that is, only one of the book and cup is on the left zone, and the toy must be on the right zone. Then, the updated belief state S ϕ is assigned the collection ≤S ϕ of two partial preorders listed below.

Subsequently, the robot is informed to put the book and the cup on the same zone, which is described as new information φ = b ↔ c. Clearly, the minimal elements satisfying φ w.r.t. ≤S ϕ w2 (resp. ≤S ϕ w4 ) are possible worlds w6 and w7 (resp. w0 and w1). By the semantics of the update operator, the updated belief set B((S ϕ) φ) becomes b ↔ c ≡ Form(w0,w1,w6,w7). However, as the agent has believed, after the update by ϕ, that the toy was on the right zone, it seems irrational to require the agent to give up this belief.

As φ |= ¬ϕ, according to postulate (CU2), we can deduce that B((S ϕ) φ) ≡ B(S φ) ≡ ¬b ∧¬c ∧¬t. In this way, it preserves the belief about the toy.

Example 4 (Postulate (CU3)). Consider the scenario where an alarm is in a warehouse. When the alarm sounds, it means a fire breaks out. The proposition a and f denotes that "the alarm sounds" and "the warehouse catches fire", respectively. Let P = {a, f} and M = {w0, . . . , w3}. Each possible world is defined in Table 2. Initially, the belief set B(S) is ¬a ∧ ¬f ≡ Form(w0), meaning that neither the alarm sounds nor the warehouse catches fire. The belief state S is associated with the following preorder ≤Sw0 .

At some point, some workers smoke, causing a fire in the warehouse, which is described as the new information ϕ = f . The updated belief set B(S ϕ) is ¬a ∧ f ≡ Form(w1), that is, the alarm does not sound but the fire is in the warehouse. Then, the updated belief state S ϕ is assigned to the set ≤S ϕ of preorders with one element ≤S ϕ w1 .

Subsequently, the alarm sounds, which is described as new information φ = a. Obviously, the minimal elements satisfying φ are possible worlds w2 and w3. It follows from the semantics of the update operator that the updated belief set B((S ϕ) φ) ≡ a ≡ Form(w2,w3). However, after updating by ϕ, we believe that there is a fire in the warehouse. It seems unreasonable to give up this belief now when the alarm is also sounding.

As mentioned before, the alarm sounds only when there is a fire, hence B(S a) |= f holds. We infer from postulate (CU3) that B((S ϕ) φ) |= ϕ, allowing to preserve the belief ϕ = f in the belief set B((S ϕ) φ).

Example 5 (Postulate (CU4)). Consider a scenario similar to Example 2. The initial belief set B(S) is ¬c ∧ ¬t ≡ Form(w0,w4). The belief state S is associated with the set ≤S of partial preorders that contains two elements ≤Sw0 and ≤Sw4 .

A robot first moves the book to the left zone and hence the new information ϕ = b. Then, it is believed that the book is on the left zone, that is, the updated belief set B(S ϕ) ≡ b ∧¬c ∧¬t ≡ Form(w4). The associated partial preorder ≤S ϕ w4 of the belief state S ϕ is:

The robot is subsequently instructed to put the cup on the left zone, which is described as the new information φ = c. Accordingly, we get that the updated belief set B((S ϕ) φ) becomes ¬b ∧ c ∧ ¬t ≡ Form(w2). However, because B(S ϕ) ≡ b ∧ ¬c ∧ ¬t, we have no reason to believe that the book is on the right zone.

Since B(S φ) ̸|= ¬ϕ, postulate (CU4) can be used to rule out the above irrational behaviour. Postulate (CU4) requires B((S ϕ) φ) ̸|= ¬ϕ, forbidding the unreasonable belief ¬ϕ=¬b to be a consequence of the new belief set.

6 (In)compatibility Results

In this section, based on the new semantics of belief update, we are going to analyze the compatibility between the iterated update and the modified KM postulates.

We hereafter provide a concrete update operator satisfying the modified KM postulates. Given a possible world w and a sentence ϕ s.t. w ∈ [ϕ], we divide the entire set M of possible worlds into three hierarchies: Hw,ϕ 0 = {w}, Hw,ϕ 1 = [ϕ] \ {w} and Hw,ϕ 2 = [¬ϕ].

Definition 2. Let S be a belief state associated with a belief set B(S) and a collection ≤S of preorders over possible worlds. Let ϕ be a sentence. The operator 1 is defined as:

The above two conditions impose the constraints on the updated belief set B(S 1 ϕ) and the subsequent update strategy ≤S 1 ϕ , respectively. Clearly, condition (1) is the same as the semantics of the update operator. As a result, the operator 1 satisfies postulates (U 1)-(U 3), (U 4∗ ), (U 5)-(U 7) and (U 8∗ ), hence being a KM-compatible update operator. Condition (2) assigns to every possible world w satisfying B(S 1 ϕ) a partial preorder ≤S 1 ϕ w . To be specific, the preorder ≤S 1 ϕ w exactly characterizes a binary relation over possible worlds M divided into three hierarchies: Hw,ϕ 0 , Hw,ϕ 1 and Hw,ϕ 2 . That is, (1) the possibleworldw is themost preferable, followed by the ones satisfying the new information ϕ, and finally the remaining ones falsifying ϕ; and (2) every two possible worlds in [ϕ]\{w} (resp. [¬ϕ]) are equally plausible.

Recalling the scenario in Example 5, we illustrate the specific update process of the operator 1 as follows.

Example 6. The initial belief state S is associated with the belief set [B(S)] = {w0,w4} and a collection ≤S of partial preorders as follows.

• w0 <Sw0 w4 <Sw0 w1,w2,w3,w5,w6,w7.
• w4 <Sw4 w0 <Sw4 w1,w2,w3,w5,w6,w7.

The new information ϕ = b corresponds to the set of possible worlds {w4,w5,w6,w7}. Clearly, the minimal elements satisfying ϕ w.r.t. ≤Sw0 and ≤Sw4 are both the posssible world w4. By the semantics of the update operator, we get that B(S 1 ϕ) ≡ Form(w4) ≡ b ∧ ¬c ∧ ¬t. According to the definition of 1, the updated belief state S 1 ϕ would be assigned to a collection ≤S 1 ϕ of preorders.

As seen above, the possible worlds of M are splitted into three hierarchies: (1) the most preferable ones Hw4,ϕ 0 = {w4} are exactly the current belief set, stating that only the book is on the left zone; (2) the second most preferable ones Hw4,ϕ 1 = {w5,w6,w7} are the other three possible worlds satisfying ϕ, stating that the book and at least one of the cup and the toy are on the left zone; (3) the least preferable ones Hw4,ϕ 2 = {w0,w1,w2,w3} are the possible worlds falsifying ϕ, stating that the book is not on the left zone.

Finally, the newly acquired information φ = c corresponds to the set of possible worlds {w2,w3,w6,w7}. The minimal elements satisfying φ w.r.t. ≤S 1 ϕ w4 are the two possible worlds w6 and w7. Hence, the final updated belief set B((S 1 ϕ) 1 φ) = Form(w6,w7), which argues that both the book and cup are on the left zone.

The following theorem confirms the compatibility results between two iterated postulates and the KM postulates.

Theorem 8. The update operator 1 satisfies postulates (CU3) and (CU4).

In the seminal paper [Darwiche and Pearl, 1997], it is proved that all of the DP postulates for iterated revision are compatible with the AGM paradigm (a basic framework for belief revision). Unfortunately, we can not draw a similar conclusion in the context of belief update. The following theorem shows that neither postulate (CU1) nor (CU2) is compatible with the KM postulates.

Theorem 9. There are a belief state S associated with a collection ≤S of partial preorders and a sentence φ s.t. no update operator satisfies (U 1)-(U 3), (U 4∗ ), (U 5)-(U 7) and (U 8∗ ) along with (CU1) (resp. (CU2)).

Proof. We first consider postulate (CU1). We will construct a belief state S associated with a collection ≤S of partial preorders and a sentence ϕ s.t. there does not exist any collection ≤S ϕ of partial preorders s.t. ≤S and ≤S ϕ satisfy (CRU1∗ ).

Let P = {p1, p2, p3} and M = {w1, . . . , w8}2 . Let S be a belief state with its associated belief set [B(S)] = {w1, w2} and its assigned partial preorders ≤Sw1 and ≤Sw2 as follows.

Let ϕ = Form(w3,w4,w5,w6). By the semantics of the update operator, [B(S ϕ)] = {w3}. The collection ≤S ϕ contains only one partial preorder ≤S ϕ w3 . Assume that the forth part of (CRU1∗ ) holds. That is, for every N ⊆ [ϕ], w ∈ [B(S)] and w′′ ∈ min(N,≤Sw ), there is w′ ∈ [B(S ϕ)] s.t. w′′ ∈ min(N,≤S ϕ w′ ). We will show that the back part of (CRU1∗ ) does not hold, that is, there is N3 ⊆ [ϕ], w′ ∈ [B(S ϕ)] andw′′ ∈ min(N3,≤S ϕ w′ ) s.t. w′′ /∈ min(N3,≤Sw ) holds for every w ∈ [B(S)].

Let N0 = {w4, w5}, N1 = {w5, w6} and N2 = {w4, w6}. Since N0 ⊆ [ϕ], w4 ∈ min(N0,≤Sw1 ), by the assumption above, we have w4 ∈ min(N0,≤S ϕ w3 ). Similarly, as w5 ∈ min(N0,≤Sw2 ), we have w5 ∈ min(N0,≤S ϕ w3 ). It holds that w5 ̸<S ϕ w3 w4 and w4 ̸<S ϕ w3 w5. Therefore, w4 and w5 are either equivalently plausible (w4 ≈S ϕ w3 w5) or incomparable (w4 ̸≈S ϕ w3 w5 and w5 ̸≈S ϕ w3 w4) w.r.t. ≤S ϕ w3 . Similarly, since N1 ⊆ [ϕ], w5 ∈ min(N1,≤Sw2 ) and w6 ∈ min(N1, ≤Sw1 ), we get that w5 and w6 are either equivalently plausible or incomparable w.r.t. ≤S ϕ w3 . In addition, as N2 ⊆ [ϕ], w4 ∈ min(N2, ≤Sw1 ) and w6 ∈ min(N2, ≤Sw2 ), we get that w4 and w6 are either equivalently plausible or incomparable w.r.t. ≤S ϕ w3 .

Let N3 = {w4,w5,w6}. Clearly, N3 ⊆ [ϕ]. It can be verified that min(N3,≤S ϕ w3 ) = {w4,w5,w6}, hence w6 ∈ min(N3,≤S ϕ w3 ). By the back part of (CRU1∗ ), we get that w6 ∈ min(N3,≤Sw1 ) or w6 ∈ min(N3,≤Sw2 ). However, neither w6 ∈ min(N3,≤Sw1 ) nor w6 ∈ min(N3,≤Sw2 ), which is a contradiction.

The proof for (CU2) is similar to the above case except that we take into consideration ϕ = Form(w3).

The incompatibility is due to the following reason. On the one hand, each of postulates (CU1) and (CU2) requires that B((S ϕ) φ) ≡ B(S φ), that is, the two belief states S φ and (S ϕ) φ should associate with the same belief set given a specific new information φ. On the other hand, it is possible that [B(S)] ̸= [B(S ϕ)]. In this case, their assigned collection ≤S and ≤S ϕ have different numbers of partial preorders, resulting in two different belief sets which S φ and (S ϕ) φ have.

2 We remark that this proof holds no matter what the truth assignment on each possible world wi is. Hence, we do not fix a truth assignment on each world.

7 Discussions

Examples 2-5 justify the rationality of the DP postulates in iterated update scenario. In the following, we provide a counterexamples to (CU2).

Example 7 (Postulate (CU2)). We simplify Example 2, and the only items on the table are a book and a cup. Initially, the book and the cup can be found in any zone of the table, that is, the initial belief set B(S) is ⊤. We first instruct a robot to move the book and the cup to the left zone, which is described as the new information ϕ = b ∧ c. The updated belief set B(S ϕ) is therefore b ∧ c. The new instruction to place the cup on the right zone, which is the new information φ = ¬c, is issued to the robot. There is no reason to abandon the proposition b stating that the book is on the left zone, however, imposed by (CU2), we have B((S ϕ) φ) = B(S φ) = ¬c.

Example 7 show that (CU2) leads to counterintuitive results which they aim to avoid, respectively. Postulate (CU2), however, are able to rule out inadequate update behaviors as shown in Example 3. We remark that although the DP postulates are controversial in iterated belief revision 3 , they still are the cornerstone of iterated belief change. Many subsequent work on iterated belief change are based on the DP postulates. For example, belief contraction is a type of belief change that studies the problem of how to remove a certain information from a belief set. A revision operator can be obtained from a contraction operator via the Levi identity [Levi, 1978] and vice versa via the Harper identity [Harper, 1976]. Chopra et al. [2008] proposed four postulates for iterated belief contraction via slightly modifying the DP postulates. Booth and Chandler [2019] considered the four postulates as the benchmark of iterated belief contraction and use them to evaluate their proposed iterated contraction operators. Reasoning about actions, an important topic of knowledge representation and reasoning, studies the change of agents' beliefs due to the effect of action. Belief revision were incorporated into the situation calculus, a well-known framework of reasoning about actions [Shapiro et al., 2011; Fang and Liu, 2013; Schwering et al., 2017]. These works considered the DP postulates as key properties of iterated belief revision and verified the satisfaction of the DP postulates by their approaches so as to demonstrate the advantage of their approaches. Hence, the four postulates (CU1)-(CU4) we propose in this paper is a cornerstone of the subsequent research to iterated belief update.

3 The criticism comes from convincing counterexamples in which the DP postulates cause counterintuitive results. Meyer [2001] and Stalnaker [2009] put forward counterexamples to postulate (C1). Several counterexamples to postulate (C2) are provided by Cantwell [1999] and Konieczny and Pino P´erez [2000]. In addition, postulate (C2) was discussed by Lehmann [1995], Delgrande et al. [2006] and Jin and Thielscher [2007]. Hansson [2016] offered two counterexamples to (C3) and (C4), respectively.

8 Conclusions

In this paper, we have investigated the iteration of belief update. Inspired by Darwiche and Pearl, we have presented a modification of the KM postulates framework over belief states. With the help of belief states, we have migrated the DP postulates for iterated revision to the belief update scenario, contributing to four iterated update postulates. Furthermore, we have offered the exact semantic characterizations based on partial preorders for each of the resulting postulates. At last, the (in)compatibility results between the iterated update postulates and the KM postulates are provided. We have showed that, unlike in revision, each of postulates (CU1) and (CU2) for iterated update is incompatible with the KM postulates.

Despite being the most influential approach to iterated belief revision, the DP postulates are still too liberal to rule out unintended revision operators. To strengthen the DP postulates, some additional postulates are proposed, for example, natural (Nat) postulate [Boutilier, 1996], lexicographic (Lex) postulate [Nayak et al., 2003], and independence (Ind) postulate [Booth and Meyer, 2006; Jin and Thielscher, 2007]. Ferm´e and Gonc¸alves [2023] extended these strengthened iterated revision postulates to belief update scenario, yielding iterated update postulates (U-Nat), (U-Lex) and (U-Ind). Based on our proposed update framework, we have studied their semantic characterization and proved the representation theorem. The (in)compatibility results between them and the KM postulates are also analyzed. In particular, we have shown that both (U-Lex) and (UInd) are consistent with the KM postulates while (U-Nat) is inconsistent with the KM postulates. Due to space limitation, these results will be presented in a longer version of the paper.

Acknowledgements

This paper was supported by National Natural Science Foundation of China (Nos. 62276114, 62077028 and 62176103), the Guangdong Basic and Applied Basic Research Foundation (No. 2023B1515120064), the Key Laboratory of Smart Education of Guangdong Higher Education Institutes, Jinan University (No. 2022LSYS003), the Guangdong-Macao Advanced Intelligent Computing Joint Laboratory (No. 2020B1212030003), the Science and Technology Planning Project of Guangzhou (No. 2024A04J9896), and the Fundamental Research Funds for the Central Universities, Jinan University (No. 21623202).