Revising by an Inconsistent Set of Formulas

1 Introduction

The area of belief revision studies how an agent may incorporate new information about a domain into its set of beliefs. The original and best-known approach to belief revision is the so-called AGM approach [Alchourr´on et al., 1985; G¨ardenfors, 1988]. In this approach, an agent's belief state is characterised by a deductively-closed set of formulas, or belief set, K. The revision of K by formula φ, denoted K ∗ φ, is a belief set K′ such that φ ∈ K′ , and where K′ is consistent whenever φ is. Revision functions may be characterised in one of two ways: on the one hand, rationality criteria or postulates may be given that any "reasonable" revision function should satisfy; on the other hand, formal constructions for revision functions may be developed. Ideally, classes of functions conforming to a set of postulates are linked to a corresponding formal construction via a representation result.

Several assumptions about revision functions appear to be incontrovertible. First, it is assumed that the domain of application is static 1 and the task of revision is to improve an agent's knowledge about the domain. As well, a principle of informational economy requires that in changing its beliefs, an agent will retain as many of the old beliefs as possible. Furthermore, if one revises K by φ, φ is believed in the result, i.e. φ ∈ K ∗ φ. Thus in belief revision, the prerequisite question of whether the agent should accept φ has been resolved in favour of acceptance, and the issue is how the formula is to be incorporated into the belief corpus.

1 This is slightly misleading, but serves for our purposes. More

One aspect of revision not addressed in the AGM approach is that, even in an unchanging domain, an agent will typically receive not just a single item of information, but rather a sequence of items. (For example, an agent may be exploring a roomwhile leaving the room unaltered.) Subsequently, there has been a great deal of attention paid to iterated belief revision, which addresses logical relations among sequences of revisions. Hence, if an agent with belief set K were to receive the information that φ followed by μ, this would be represented by (K∗φ)∗μ. Crucially we would have μ ∈ (K∗φ)∗μ.

However, we suggest that these assumptions don't sit well together. First, if the domain is static then there is no a priori reason to prefer more recent information. That is, there may sometimes be a reason to prefer more recently received information but it is unreasonable to require that this is necessarily always the case. In fact, [Nayak et al., 2003] presents an approach where (K ∗ φ) ∗ μ is the same as K ∗ (φ ∧ μ) when φ∧μ is consistent. But what if φ∧μ is not consistent? There are two alternatives in this case, both of which we argue are unpalatable. First, one may preferentially accept the more recently received information. But again, if an agent is receiving independent reports about an unchanging domain, such an assumption is unjustified. Second, and worse, the agent may accept the conjunction φ∧μ, in which case it falls into inconsistency.

The approach presented here takes the view that in a static domain, the order in which formulas are received is irrelevant, and so revision should be with respect to the set of such formulas. Thus if the agent received the information that φ and then μ, the revision would be expressed as K ∗ {φ, μ}. While there has been previous work in revising by a set of formulas (see the next section), crucially, all such work assumes that if the set of formulas is inconsistent then the result of revision is an inconsistent belief set.

accurate is to say that the underlying language is static; see [Friedman and Halpern, 1999] or [Lang, 2006].

Our point of departure then is to address revision by a set of formulas S where S may be inconsistent. Consider for example where we wish to revise by a set of formulas {a ∧ b, a ∧ ¬b} or {a, b, ¬b} or {a, b ∧ ¬b}. Each set is inconsistent, but in each case an argument can be made for accepting a. We address this via an appeal to informational economy with respect to the set S for revision: If the agent is to incorporate S consistently into its belief corpus, but S cannot be consistently so incorporated, then maximal consistent subsets of S comprise suitable candidates for revision. Thus for the set {a, b, ¬b}, candidates for revision are {a, b} and {a, ¬b}. Moreover, there is a means in place for adjudicating among these candidate sets, in that an agent will have an implicit plausibility ordering over formulas as part of its belief state. We give a set of postulates for revision by a finite, possibly-inconsistent set of formulas, and a representation result is given in terms of faithful rankings. We suggest that this approach is interesting because it generalises the AGM framework. As well, we argue that iterated belief revision should in fact be treated as (uniterated) revision by a set of formulas.

The next section introduces terminology, and reviews the area of belief revision. Section 3 further motivates the approach and presents the formal details, while the next section discusses implications of the approach with respect to iterated revision. We finish with a brief conclusion.

2 Background

2.1 Formal Preliminaries

Let P = {a, b, c, . . .} be a fixed, finite set of propositional variables. L is the language of classical propositional logic over P, with the usual connectives ∧, ∨, ⊃, and ¬. The classical consequence relation is denoted ⊢. Cn(S) is the set of logical consequences of a set of formulas S, that is Cn(S) = {φ ∈ L | S ⊢ φ}. ⊤ stands for some arbitrary tautology, and ⊥ is defined to be ¬⊤.

A propositional interpretation (or possible world) is a mapping from P to {true, false}. The set of all interpretations is denoted by M. A model of a formula φ is an interpretation w that makes φ true according to the usual definition of truth, and is denoted by w |= φ. For W ⊆ M, we also write W |= φ if w |= φ for every w ∈ W. For a set of sentences S, Mod(S) is the set of all models of S. Mod({φ}) is also written as Mod(φ). For W ⊆ M, we denote by T (W) the set of sentences that are true in all elements of W, that is T (W) = {φ ∈ L | w |= φ for all w ∈ W}.

For sets of formulas S and S′ , S+S′ denotes the expansion of S by S′ , that is S+S′ = Cn(S∪S′ ). For formula φ, S+φ is defined to be S + {φ}. Formulas φ and ψ are logically equivalent, written φ ≡ ψ, iff φ ⊢ ψ and ψ ⊢ φ. This extends to sets of formulas by: S ≡ S′ iff S ⊢ φ for every φ ∈ S′ and S′ ⊢ ψ for every ψ ∈ S. Two sets of formulas S and S′ are strongly equivalent just if for every φ ∈ S there is φ′ ∈ S′ such that φ ≡ φ′ , and vice versa. A set of formulas S (or formula) is inconsistent if S ⊢ ⊥, and strongly inconsistent just if S ̸= ∅ and for every φ ∈ S, φ is inconsistent.

For a (finite) set of formulas S, ∧S is the conjunction of members of S, and S = {¬φ | φ ∈ S}. If S is a finite set of finite sets of formulas, define ∨S to be ∨S∈S ∧S. As a degenerate case, define ∨{∅} to be ⊥.

A total preorder ⪯ is a reflexive, transitive binary relation, such that either φ ⪯ ψ or ψ ⪯ φ for every φ, ψ. The strict part of ⪯ is denoted by ≺, that is, φ ⪯ ψ and ψ ̸⪯ φ. As usual, φ = ψ abbreviates φ ⪯ ψ and ψ ⪯ φ. Given a set S and total preorder ⪯ defined on members of S, we denote the set of minimal elements of S in ⪯ by min(S, ⪯).

2.2 Belief Revision

In the AGM approach, an agent's beliefs are modelled by a deductively closed set of formulas called a belief set. However, various researchers have subsequently argued that, in order to address iterated belief revision, it is more appropriate to consider belief states or epistemic states as objects of revision. An epistemic state K effectively encodes information regarding how the revision function itself changes under a revision. The belief set corresponding to belief state K is denoted Bel(K). A revision operator ∗ then maps a belief state K and formula φ to a revised belief state K ∗ φ. In the spirit of [Darwiche and Pearl, 1997], the AGM postulates for revision can be expressed as follows:

We will call a revision operator an AGM revision operator if it satisfies the reformulated AGM postulates. Katsuno and Mendelzon [1991] have shown that a necessary and sufficient condition for constructing an AGM revision operator is that a belief state K can induce, as its preferential information, a total preorder on the set of possible worlds.

Definition 1 A faithful assignment is a function that maps each belief state K to a total preorder ⪯K on M such that for any possible worlds w1, w2:

The resulting total preorder is referred to as the faithful ranking corresponding to, or induced by K. Intuitively, w1 ⪯K w2 if w1 is at least as plausible as w2.

It follows from the results of [Katsuno and Mendelzon, 1991] that a revision operator ∗ satisfies (K ∗ 1)-(K ∗ 8) iff there exists a faithful assignment that maps K to the faithful ranking ⪯K such that for any sentence φ: 2

2 Katsuno and Mendelzon deal with formulas instead of belief sets. Since the language is finite, this difference is immaterial. As well, their postulate set is more compact. We use the given definitions in order to adhere more closely to the original AGM approach.

2.3 Belief Change via Sets of Formulas

The idea of changing an agent's beliefs with respect to a set of formulas isn't new. [Fuhrmann and Hansson, 1994] surveys multiple contraction, and proposes package contraction for removing a set of formulas from a belief set. Similarly, the contraction introduced by [Zhang et al., 1997] studies how to contract a belief set so that it is consistent with a set of formulas, while [Ferm´e et al., 2003] examines a construction for multiple contraction in a belief base. Set revision (also called multiple revision) is developed in [Zhang and Foo, 2001; Peppas, 2004], although these papers primarily study infinite sets. A postulate set may be given as follows, analogous to the postulate set in [Peppas, 2004] but adapted for belief states; we refer to this set as the (AGM) set revision postulates. We use ⊗ to denote a revision operator, where ⊗ maps a belief state K and a finite nonempty set of formulas S to a revised belief state K ⊗ S.

None of these approaches are concerned with relations among subsets of formulas after revision. An approach that does deal with this issue is so-called parallel revision [Delgrande and Jin, 2008]. The idea is that in revising by a set of formulas S, if some members of S are subsequently found to be false, the remaining elements of S (where logically possible) will remain believed to be true. Thus, assuming that a, b, and c are logically independent, one would obtain that a ∈ Bel ((K ∗ {a, b, c}) ∗ {¬c}). The set revision postulates are extended by the following postulate: 3

(K⊗PP) expresses the condition that after revising by a set of formulas, and then by the negations of some of those formulas, the remaining formulas, where possible, will persist in being believed to be true. The following condition on a faithful ranking is provided, analogous to (K⊗PP).

A representation result is provided:

Theorem 1 A revision operator ⊗ satisfies (K ⊗ 1) - (K ⊗ 8), and (K ⊗ PP) iff there is a faithful assignment whose corresponding faithful ranking ⪯K satisfies (PP), and where for any finite set of sentences S:

3 [Delgrande and Jin, 2008] also had a postulate to deal with revision by the empty set. Here we simply exclude this case.

In the next section, after we present our approach for revising by a possibly-inconsistent set of formulas, we suggest that this approach augmented by the conditions for parallel revision (K ⊗ PP )/(PP)) constitute a suitable basic approach for revising by a set of formulas.

Finally, in set revision, revision by φ ∧ ψ is treated differently from revision by {φ, ψ}. This distinction between a conjunction and its set of conjuncts has been explored in [Konieczny et al., 2005], where comma is treated an additional propositional connective. However, their goals (to study this extension of propositional logic) are quite different from our's here.

3 Revising by an Inconsistent Set of Formulas 3.1 Intuitions

In any extant approach to revision by a set of formulas, as with the AGM approach, if the set for revision is inconsistent then the resulting belief set is also inconsistent. This is due to the fact that in a revision K ∗ S, the success postulate (K ⊗ 2) requires that every element of S be believed. Informally however it seems that, if a set S is inconsistent, then one still may be able to do more with respect to revision.

Consider again the assumptions underlying AGM belief revision that we discussed. Our interpretation of success, as given in (K ∗ 2), is that in a revision K ∗ φ the agent has elected to accept φ. The formula φ is some report, observation, or similar piece of information about the domain. In the set-based approach, the agent has received several such pieces of information, and the agent is presumably prepared to accept any of these individual items of information. However, if these items conflict, then a truly rational agent will not accept all items (and so fall into inconsistency) but rather will treat the items as candidates for inclusion in its belief set. If we apply an analogue of the principle of informational economy to the set of input formulas S, then an agent will in some fashion incorporate a maximal number of such candidate items of information into its belief set. Consider the following example:

Example 1

Each set is inconsistent, but intuitively the sets carry different information. In the first case, the agent has received two reports, that a ∧ b and a ∧ ¬b. Clearly both formulas cannot be simultaneously and consistently accepted. Nor is it rational to accept both formulas. This might suggest that one merge the input formulas in some fashion (as for example in [Konieczny and Pino P´erez, 2002]). However we suggest that such a step is not necessary, nor even appropriate: If the agent had any information about how to select among input formulas, then this would be reflected in its epistemic state. Thus the agent already has sufficient resources to determine what aspects of S1 to incorporate: For formulas a ∧ b and a ∧ ¬b, the faithful ranking ⪯K associated with the agent's epistemic state indicates which formula is more plausible, according to the agent. Thus if the minimal a ∧ b worlds were ranked below the minimal a ∧ ¬b worlds, then this would provide a solid rationale for the revision to be characterised by the minimal a ∧ b worlds. And if the minimal a ∧ b and a ∧ ¬b worlds were at the same rank, then the agent's revised beliefs would be characterised by the union of these worlds.

Similarly with S2: Intuitively there is no reason to not incorporate c into the agent's belief corpus, and while it cannot incorporate both b and ¬b, it seems that it should accept the more plausible of b, ¬b. This suggests that if the least {b, c} worlds are more plausible than the least {¬b, c} worlds, then these worlds should characterise the revision. If the least {b, c} worlds are as plausible as the least {¬b, c} worlds, then revision would be characterised by their union. In either case, the result would be a consistent belief set in which c is believed. This line of argument has the consequence that for revision by a set S, one should consider the maximal consistent subsets of S as candidate sets for revision, and then select the most plausible worlds among these various subsets to characterise the revision. Thus, in the case of S3, which of the candidate formulas will be accepted depends on how the agent ranks their plausibility. It may be that a ∧ b is believed, or a is believed and b is not. As well, if ¬a is believed then so is b. In any case, in the resulting belief state, at least a ∨ b will be believed.

3.2 The Approach

We start by reviewing the definition of the set of maximum consistent subsets of a set of formulas.

Definition 2 Let S be a nonempty set of formulas. Con(S), the set of maximum consistent subsets of S, is given as follows. S1 ∈ Con(S) iff

1. S1 ⊆ S.
2. S1 ̸⊢ ⊥.
3. For any S2 where S1 ⊂ S2 ⊆ S, we have S2 ⊢ ⊥. The following results are straightforward.

Proposition 1

1. Con(S) = {S} iff S ̸⊢ ⊥.
2. Con(S) = {∅} iff ∀φ ∈ S, φ is inconsistent.

We next characterise set-based revision. Consider the following set of postulates which extend the AGM set postulates (K⊗1)-(K⊗8) to allow for inconsistent sets. The numbering reflects that of the AGM set postulates; for example (K⊗ 1) is the first AGM set revision postulate while (K ⊗ 2′ ) is a variation on (K ⊗ 2). We will refer to the following as the extended set revision postulates.

Postulates:

With regards (K⊗ 2′ ), consider the following example. Example 2c ∈ Bel(K ∗ {a, b, ¬b, c}).

Formulas entailed by all maximum consistent subsets of S (e.g. c and c∨d respectively) are believed following revision. As well, a is believed following each revision in the example.

A consequence of (K⊗3′ ), (K⊗4′ ) is the following:

Proposition 2

(K⊗5′ ) deals with the situation in which every formula in S is inconsistent. The decision that Bel (K ∗ S) is also inconsistent in this case is arbitrary; one could equally well argue that a rational agent would reject incorporating any inconsistent information, on the grounds that it is impossible. Hence by this argument the belief set should remain unchanged. On the other hand, one might decide that Bel (K∗S) should be inconsistent, since this is closer to the original AGM approach. For this reason, and because it makes the representation result tidier, we elect to have Bel (K ∗ S) be inconsistent when S is strongly inconsistent.

It can be noted that (K⊗6) and (K⊗6′ ) are independent.

Example 4

We have that Bel(K ⊗ {a, b}) ≡ Bel(K ⊗ {a ∧ b}) by (K ⊗ 6), while (K ⊗ 6′ ) has nothing to say in this case. (K ⊗ 6′ ) asserts that Bel (K ⊗ {a ∧ b, ¬a}) ≡ Bel (K ⊗ {a ∧ (a ⊃ b), ¬a}) while (K ⊗ 6) is inapplicable.

The proviso S1 ̸⊢ ⊥ for (K ⊗ 7′ ) and (K ⊗ 8′ ) basically makes these postulates the same as their counterparts (K⊗7) and (K ⊗ 8).

We also obtain the following factoring result for maximum consistent sets:

Proposition 3

The case where S ≡ S1 ≡ S2 is trivial. Otherwise S is inconsistent, but there are two maximum consistent subsets. Factoring states that revision is a function of these two maximum consistent subsets. This result also generalises via a straightforward induction:

Proposition 4

This postulate set can be tied to faithful assignments via an extension of the Katsuno and Mendelzon [1991] result:

Theorem 2 A revision operator ⊗ satisfies the extended set postulates iff there exists a faithful assignment that maps K to the faithful ranking ⪯K such that for any finite set of formulas S:

Finally, we can combine this approach with that of [Delgrande and Jin, 2008] to obtain a suggested "preferred" basic approach to revising by a set of formulas:

Theorem 3 A revision operator ⊗ satisfies the extended set postulates together with (K ⊗ PP) iff there is a faithful assignment whose corresponding faithful ranking ⪯K satisfies (PP), and where for any finite set of sentences S:

This in turn yields a revision operator on sets of formulas in which inconsistency of a set of formulas is handled appropriately and, for future revisions, elements of the set are retained where possible.

We also obtain the result:

Proposition 5

So revising by a set of formulas and then by one of the maximum consistent subsets gives the same belief set as revising by that maximum consistent subset.

Consider the following examples, where ⊗ is a revision operator as given in Theorem 3.

Example 5

The first part of the example illustrates the basic approach in parallel revision. The second part shows that this extends to the case of inconsistent sets. The last part is interesting, in that there are revision operators in which a ∧ b ∈ Bel(K ⊗

{a ∧ b, a ∧ ¬b}); however, even in this case, in subsequently revising by ¬b, a is retained. On the other hand, there are revision functions where a ̸∈ Bel(K ⊗ {a ∧ b, ¬b}), and similarly in subsequently revising by ¬b.

As noted in [Delgrande and Jin, 2008], the basic approach to parallel revision doesn't fully address iterated revision. In fact [Delgrande and Jin, 2008] augments the basic approach with that of [Jin and Thielscher, 2007] to obtain an approach to parallel revision that also handles iterated revision appropriately. While one could do the same here, with this or another approach to iterated revision, we suggest that in fact that such an iterated revision operator would play only a minor role with respect to maintaining an agent's corpus of beliefs. We develop this thesis in the next section.

4 Belief Change and the Role of Iterated Revision

Consider again assumptions underlying classical AGM revision, and how they are interpreted in the present framework. Most pertinently, AGM revision assumes that:

1. The underlying domain (or: domain language) is static.
2. The agent receives a sequence of input formulas for revision about this (static) domain.
3. Each formula for revision is accepted.
4. Implicitly all input formulas have equal weight. This is a consequence of the success postulate; for example for contingent φ, one will never have φ ∈ K ∗ φ ∗ ¬φ.

In the present approach, we also assume the first two points. However, then things differ: if a domain is static, and there is a sequence of formulas that an agent has (tentatively) decided to accept, there is no reason that the most recent must be accepted. Thus, if the order in which formulas are accepted is irrelevant, then the input to revision should be the set of such formulas. This set then consists of formulas that individually the agent would accept. Since it is not rational to accept all formulas if the set is inconsistent, and since an agent would want to accept a maximal amount of information, the set of maximal consistent subsets of the input set constitute candidate sets for revision. Furthermore, the agent has sufficient information to adjudicate among these maximum consistent subsets, as given by its associated faithful ranking, which assigns a plausibility level to every formula.

We emphasize this difference in approaches since it leads to a very different view of so-called iterated belief revision: a revision sequence K ∗ φ1 ∗ . . . ∗ φn is more appropriately regarded as the uniterated revision K⊗{φ1, . . . , φn}. In theory then there is no need for iterated revision as understood in the belief change community.

So does this mean that there is no role for iterated revision? Arguably, there is a role, but it is a pragmatic one. In the set revision approach, an agent will need to successively recompute a new belief state based on an increasing set of input formulas. That is, if the agent has computed K⊗S, and then receives a new item of information φ, it will need to compute K ⊗ (S ∪ {φ}). Clearly, the process of computing a revision over all input formulas each time a new formula is received will be expensive. Thus from a practical point of view, after a sufficient number of input formulas have been received, one may elect to "compile" these formulas into a new belief state, and so adopt a state K′ given by K ⊗ S. Then further inputs would again be collected into another set, and revision computed with respect to K′ . The advantage of the extended approach, as given in Theorem 3, is that for (K ⊗ S) ⊗ S′ , elements of S will be retained in the subsequent revision by S′ unless specifically contradicted by S′ .

5 Conclusion

This paper has presented an approach to belief revision in which consequences of the assumption of an underlying static domain are explored. In particular, we argue that the success postulate is too strong when there is more than one formula for revision. Instead we suggest that revision should be set-based, and that an agent will revise its corpus of beliefs by the set of input formulas that it has received. Given that the agent's full knowledge about the domain is encoded in its epistemic state, then this along with a principle of informational economy has the consequence that for revision by a set S, one should consider the maximal consistent subsets of S as candidate sets for revision, and then select the most plausible worlds among these various subsets to characterise the revision. This suggests in turn that "one shot" AGM setbased revision is in fact of primary interest, and that iterated revision plays a relatively minor role.

In the approach, input formulas are effectively given the same weight, in that they are all candidates for acceptance. However, in general, formulas may come with different degrees of reliability; for example, an agent may have information that a report of φ is more likely to be correct than one of ψ. This notion of reliability is distinct from the agent's plausibility ordering on formulas. Hence an interesting direction for future research concerns dealing with formulas with different degrees of reliability, and reconciling such an implicit ordering on observations with the plausibility ordering implicit in the agent's ranking function on worlds.