It is known that prominent fragments of propositional logic are not closed under standard belief change operators. That is, applying such operators to knowledge bases in a fragment may produce results that have no equivalent in the same language. However, the potential range of such a deviation has not been investigated yet. In this paper, we give a systematic study of this problem by considering four prominent change operators (Dalal, Satoh, Winslett, and Forbus) and three important fragments (1CNF, Krom, and Horn). While all operators are shown to be closed under the 1CNF fragment, we observe that for the other two fragments the behavior of the operators significantly differs. We expect our considerations on deviation to play an important role in the design of change operators for concrete Knowledge Representation formalisms.
Belief change [
An obstacle in the application of standard belief change procedures to languages that do not subsume propositional logic is the fact that results are not guaranteed to be expressible in the same language. As an example consider the Horn fragment and the revision of a knowledge base K = {a ∧ b} by formula µ = ¬a ∨ ¬b. Most belief change operators deliver the intuitive result that the outcome of this change should be equivalent to a ⊕ b; the latter cannot be expressed in Horn although K and µ are from this fragment.
Existing research that takes this as its starting point has taken several directions.
Papers in the spirit of [
In this paper we focus on certain fragments of propositional logic, namely the
1CNF, Krom and Horn fragment. Propositional fragments are of interest because: (i)
they are closely related to the original framework for belief change, hence best suited
to illustrate general principles, and (ii) some of these fragments serve as the basis for
popular formalisms in Knowledge Representation (e.g., Horn logic is the backbone of
DL-Lite). Our main aim is to investigate the interplay between these fragments and
established belief change operators (Dalal, Satoh, Winslett, Forbus). These four
operators are among the most well studied in the field, both with respect to their semantic
representation and their complexity in fragments [
Thus, what is required is a closer look into the behaviour of established operators
and the extent to which results can fall outside a given fragment. With the exception of
Dalal’s operator [
The rest of the paper is structured as follows. In Section 2 we present background notions. Section 3 presents our main results on the deviation of the 1CNF, 2CNF and Horn fragments. Section 4 provides a comparison between the ranges of the operators, and Section 5 offers conclusions and pointers to future work. 2
We write L for the language of propositional logic constructed from a finite alphabet U of atoms using standard connectives ∨, ∧, ¬, and constants , ⊥. An interpretation is a set of atoms (the ones set to true), and the set of all interpretations is W. The set of models of a formula ϕ is denoted by [ϕ]. If there is no danger of ambiguity, we write models as strings made up of their elements (e.g., abc instead of {a, b, c}). A knowledge base (knowledge base) is a finite set of formulas. We will usually identify a knowledge base K with ϕ∈K ϕ. The set of models of a knowledge base K is [K] = ϕ∈K [ϕ]. We write w u for the symmetric difference between interpretations w and u. If M, N ⊆ W, then M N = {w u | w ∈ M, u ∈ N }. We use w M or M w to abbreviate {w} M or M {w}, respectively. We write min ⊆(M) = {w ∈ M | ∃w ∈ M s.t. w ⊂ w}, and mincard(M) = {w ∈ M | ∃w ∈ M s.t. |w | < |w|}.
We define a fragment of propositional logic as a set of propositional formulas characterized by a closure property on the set of models. Thus, a mapping Cl : 2W → 2W is called a closure-operator if, for any M, N ⊆ W, it holds that (i) if M ⊆ N , then Cl (M) ⊆ Cl (N ), (ii) if |M| = 1, then Cl (M) = M and (iii) Cl (∅) = ∅. A fragment is a set F ⊆ L closed under conjunction (i.e., ϕ ∧ ψ ∈ F for any ϕ, ψ ∈ F ) for which there exists an associated closure-operator Cl such that (i) for all ϕ ∈ F , [ϕ] = Cl ([ϕ]) and (ii) for all M ⊆ W there is a ϕ ∈ F with [ϕ] = Cl (M). We denote the closureoperator Cl associated to a fragment F as Cl F . An F -knowledge base is a finite set K ⊆ F . A knowledge base K ⊆ L is F -expressible if there exists an F -knowledge base K , such that [K] = [K ]. A set of interpretations M is F -expressible if there exists an F -knowledge base K such that [K] = M.
Many well-known fragments of propositional logic are captured by this notion. To the Horn fragment (i.e., conjunctions of clauses with at most one positive literal) we associate the operator Cl Horn, defined as the fixed point of the function (M) = {w1 ∩ w2 | w1, w2 ∈ M}. The Krom, or 2CNF, fragment (i.e., conjunctions of clauses of length at most 2) is linked to the operator Cl 2CNF, defined as the fixed point of the function maj(M) = {maj3(w1, w2, w3) | w1, w2, w3 ∈ M}, where ternary majority maj3(w1, w2, w3) yields an interpretation containing those atoms true in at least two out of w1,w2 and w3. Finally, the 1CNF fragment (i.e., conjunctions of literals) has as its operator Cl 1CNF, defined as the fixed point of the function Fill(M) = {w1 ∩ w2, w1 ∪ w2 | w1, w2 ∈ M} ∪ {w3 | w1 ⊆ w3 ⊆ w2 and w1, w2 ∈ M}. Note that full classical logic is given via the identity closure operator Cl L(M) = M.
A revision operator ◦ maps a knowledge base K and a formula µ to a knowledge
base K ◦µ. We consider here four standard operators: Winslett (◦W ), Satoh (◦S ), Forbus
(◦F ) and Dalal (◦D) [
This example illustrates a relationship between the operators which holds more generally, namely that for any knowledge base K and formula µ, we have [K ◦D µ] ⊆ [K ◦S µ] ⊆ [K ◦W µ] and [K ◦D µ] ⊆ [K ◦F µ] ⊆ [K ◦W µ], while [K ◦S µ] and [K ◦F µ] are not necessarily in a subset relationship to each other. We will be interested in all formulas that can be obtained by applying an operator to knowledge bases in a given fragment. abcd b ac acd a cd abd ab Definition 1. For a revision operator ◦ and a fragment F ⊆ L, the image of ◦ with respect to F , denoted by ImF (◦), is defined as ImF (◦) = {K ◦ µ | K, µ ∈ F }.
It is straightforward to see that for any operator ◦ ∈ {◦D, ◦S , ◦F , ◦W } and any knowledge base K, it holds that [K ◦ K] = [K]. It follows that F ⊆ ImF (◦), for any fragment F . However, as the following example illustrates, revision can produce results falling outside a given fragment.
Example 2. Consider a knowledge base K = {a ∧ b ∧ c} with [K] = {abc}, and a formula µ = (¬a ∨¬b)∧(¬a∨¬c) ∧(¬b∨¬c) with [µ] = {∅, a, b, c}. We have that K and µ are in both the 2CNF and the Horn fragment. However, for all ◦ ∈ {◦D, ◦S , ◦F , ◦W } we get [K ◦ µ] = {a, b, c}. Since Cl 2CNF({a, b, c}) = Cl Horn({a, b, c}) = {∅, a, b, c}, we have that K ◦ µ is neither 2CNF- nor Horn-expressible. Thus, Horn ⊂ ImHorn(◦) and 2CNF ⊂ Im2CNF(◦).
Therefore the 2CNF and Horn fragments are not closed under any of the operators studied in this paper, though at this point we do not know anything more precise about what the image of these operators looks like. This motivates the following concept, which we study in the rest of the paper.
Definition 2. The deviation of ◦ from F is (i) total if ImF (◦) = L; (ii) partial if F ⊂ ImF (◦) ⊂ L; and (iii) zero if ImF (◦) = F .
Deviation is closely related to the notion of simplifiability [
Our results on deviation are summarized in Table 2, and the rest of the section is dedicated to justifying them. As mentioned in Section 2, F ⊆ ImF (◦) for any fragment F and all operators considered. In other words, it is non-F -expressible knowledge bases 1CNF 2CNF Horn zero zero zero zero total partial total partial partial partial partial partial K∗ that are crucial in determining the extent of an operator’s deviation, and which will occupy our attention in the following. In general, [K ◦ µ] ⊆ [µ], for any K, µ and ◦. Thus, if K and µ are assumed to be in some fragment F , we can only obtain K∗ if [µ] contains at least Cl F ([K∗]), and this is what we typically assume of µ. We present now results for the 1CNF, 2CNF and Horn fragments.
Let [P; I] = {P ∪ J | J ⊆ I}, where P ∩ I = ∅. Notice that if a knowledge base K is 1CNF-expressible, then [K] = [P; I], where P is the set of positive atoms in K and I is the set of atoms that make no appearance in K (and on which K is, so to speak, indifferent). For example, if U = {a, b, c, d, e} and K = {a ∧ b, ¬c}, then [K] = [{a, b}; {d, e}] and, with our usual abbreviation, we may write [K] = [ab; de]. We now show that in revising a 1CNF knowledge base K by a 1CNF formula µ, the table of symmetric differences [µ] [K] always yields models of some 1CNF formula. Lemma 1. If K1 and K2 are 1CNF-expressible, then [K1] [K 2] is 1CNF-expressible. Proof. With the notation just introduced, let [K1] = [P1; I1] and [K2] = [P2; I2]. We show, by double inclusion, that [P1; I1] [P 2; I2] = [(P1 P 2)\(I1 ∪ I2); I1 ∪ I2], which implies that [K1] [K 2] is 1CNF-expressible.
For one direction, take (P1 ∪ J1) (P 2 ∪ J2) ∈ [P1; I1] [P 1; I1], with Ji ⊆ Ii, for i ∈ {1, 2}. We show that (P1 ∪ J1) (P 2 ∪ J2) = (P1 P 2)\(I1 ∪ I2) ∪ ((I1 ∪ I2) ∩ ((J1 J 2)\(P1 P 2))).
“⊆” Take w ∈ (P1 ∪ J1) (P 2 ∪ J2) and without loss of generality assume that w ∈ (P1 ∪ J1)\(P2 ∪ J2). It follows that w ∈ P1 or w ∈ J1. Case 1. If w ∈ P1, then w ∈ P1 P 2. Since P1 ∩ I1 = ∅, it follows that w ∈/ I1 and w ∈/ I1 ∪ I2. We conclude that w ∈ (P1 P 2)\(I1 ∩ I2). Case 2. If w ∈ J1, then w ∈ J1 J 2. Second, w ∈ I1 and hence w ∈ I1 ∪ I2 and w ∈/ P1. Since w ∈/ P2, we get that w ∈/ P1 P 2 and thus w ∈ (J1 J 2)\(P1 P 2). We conclude that w ∈ (I1 ∪ I2) ∩ ((J1 J 2)\(P1 P 2)).
“⊇” Take w ∈ (P1 P 2)\(I1 ∪ I2) ∪ ((I1 ∪ I2) ∩ ((J1 J 2)\(P1 P 2))). To get the conclusion, we perform a case analysis as to whether w ∈ (P1 P 2)\(I1 ∪ I2) or w ∈ (I1 ∪ I2) ∩ ((J1 J 2)\(P1 P 2)).
For the other direction, take (P1 P 2)\(I1 ∪ I2) ∪ ((I1 ∪ I2) ∩ J ) ∈ [(P1 P2)\(I1 ∪ I2); I1 ∪ I2], where J ⊆ I1 ∪ I2. As above, we show by double inclusion that (P1 P 2)\(I1 ∪ I2) ∪ ((I1 ∪ I2) ∩ J ) = (P1 ∪ J1) (P 2 ∪ J2), where Ji = Ii ∩ (J (P 1 P 2)), for i ∈ {1, 2}.
If [K1] [K 2] is 1CNF-expressible, then it has a unique ⊆-minimal element, which is also cardinality-minimal. We identify, then, min⊆([K1] [K 2]) = mincard([K1] [K 2]) with this single element.
Example 3. If [K1] = {a, ab, ac, abc} and [K2] = {∅, b, c, bc}, then [K1] [K 2] = {∅, a, b, c, ab, ac, bc, abc}. We have that min⊆([K1] [K 2]) = mincard([K1] [K 2]) = {∅}, and write ∅ instead of {∅}.
In the following we use Lemma 1 to show that in the 1CNF fragment none of the operators can discriminate between {w1, w2} and {w1 ∩ w2, w1 ∪ w2}, i.e., no operator can select one pair while leaving the other out.
Lemma 2. If K and µ are 1CNF-expressible, then for any ◦ ∈ {◦D, ◦S, ◦F , ◦W } and any w1, w2 ∈ W, it holds that {w1, w2} ⊆ [K ◦ µ] iff {w1 ∩ w2, w1 ∪ w2} ⊆ [K ◦ µ]. Proof. We show the result for Winslett’s operator ◦W .
(“⇒”) If {w1, w2} ⊆ [K ◦W µ], take ui ∈ [K] such that wi u i = min⊆([µ] u i), for i ∈ {1, 2}. Then consider u3, u4 ∈ [K] such that (w1 ∩ w2) u 3 = min⊆((w1 ∩ w2) [K]) and (w 1 ∪ w2) u 4 = min⊆((w1 ∪ w2) [K]). This is shown in Table 3, with arrows indicating whether an element is minimal on a row or on a column. We now argue that (w1 ∩ w2) u 3 = min⊆([µ] u 3) and (w1 ∪ w2) u 4 = min⊆([µ] u 4). For that, we first show that (w1 ∩ w2) u 3 ⊆ w u 3, for some arbitrary w ∈ [µ]. We take an atom a ∈ (w1 ∩ w2) u 3 and do a case analysis.
Case 1. If a ∈ (w1 ∩ w2)\u3, then by assumption (w1 ∩ w2) u 3 = min⊆((w1 ∩ w2) [K]), and thus (w 1 ∩ w2) u 3 ⊆ (w1 ∩ w2) u 1. Since a ∈ w1 ∩ w2, we get that a ∈/ u1. With a ∈ w1, this entails that a ∈ w1 u 1. But w1 u 1 = min⊆([µ] u 1), so a ∈ w u 1. With a ∈/ u1, this implies that a ∈ w. Thus a ∈ w (w 1 ∩ w2) and hence (w1 ∩ w2) u 3 ⊆ w u 3. Case 2. If a ∈ u3\(w1 ∩ w2), then a ∈/ w1 or a ∈/ w2. Without loss of generality, assume a ∈/ w1. We again use the fact that (w1 ∩ w2) u 3 ⊆ (w1 ∩ w2) u 1 and conclude that a ∈ u1, which further entails that a ∈ w1 u 1. Then a ∈ w u 1, and thus a ∈/ w, which entails that a ∈ w u 3. With this we have shown that (w1 ∩ w2) u 3 = min⊆([µ] u 3). The proof that (w1 ∪ w2) u 4 = min⊆([µ] u 4) is similar.
(“⇐”) If {w1 ∩ w2, w1 ∪ w2} ⊆ [K ◦W µ], there exist u3, u4 ∈ [K] such that (w1 ∩ w2) u 3 = min⊆([µ] u 3) and (w1 ∪ w2) u 4 = min⊆([µ] u 4). Take u1, u2 ∈ [K] such that w1 u 1 = min⊆(w1 [K]) and w 2 u 2 = min⊆(w2 [K]). We then show that wi u i = min⊆([µ] u i), for i ∈ {1, 2}. Indeed, take an arbitrary w ∈ [µ] and an a ∈ w1 u 1 and consider the two possible cases. Case 1. If a ∈ w1\u1, then a ∈ w1 u 3 and hence a ∈/ u3. It follows that a ∈ (w1 ∪ w2) u 3 and therefore a ∈ w u 3 and a ∈ w, which entails a ∈ w u 1. Case 2. If a ∈ u1\w1, then a ∈ w1 u 3 and then a ∈ (w1 ∩ w2) u 3 and hence a ∈ w u 3. This leads to a ∈/ w and then to a ∈ w u 1. The proof for w2 u 2 is entirely similar.
The reasoning for ◦S, ◦F and ◦D is similar.
As we will show, what excludes non-1CNF-expressible knowledge bases from the
range of the studied operators turns out to be the presence of so called critical
interpretations [
← (w1 ∪ w2) u 4
[µ]
w2 ⊆ w1, and {w1, w2} ⊆ [K∗] or {w1 ∩ w2, w1 ∪ w2} ⊆ [K∗], but {w1, w2, w1 ∩
w2, w1 ∪ w2} ⊆ [K∗]. The relevant result is that if a knowledge base K∗ is
non-1CNFexpressible, then there exist w1, w2 ∈ Cl 1CNF([K∗]) critical with respect to K∗ [
Proof. Let K∗ be a knowledge base that is not 1CNF-expressible and assume existence of a 1CNF-expressible knowledge base K and a 1CNF formula µ such that [K ◦ µ] = [K∗], and where Cl 1CNF([K∗]) ⊆ [µ]. As mentioned, there are w1, w2 ∈ W critical with respect to K∗, thus {w1, w2} ⊆ [K ◦ µ] or {w1 ∩ w2, w1 ∪ w2} ⊆ [K ◦ µ]. From Lemma 2 it follows that {w1, w2, w1 ∩w2, w1 ∪w2} ⊆ [K ◦µ], which is a contradiction.
An intuitive way to think about belief change in the 1CNF fragment is through what happens on the syntactic level, a view not often afforded for other fragments. For all of the operators considered, we have that if there are literals in K which are negated by µ, those literals are swapped with their negations in K ◦ µ. Thus, if K = {a, b, c} and µ = ¬b ∧ ¬c ∧ ¬d, then K ◦ µ ≡ {a ∧ ¬b ∧ ¬c ∧ ¬d}. 3.2
We obtain that Dalal and Satoh’s operators can produce any propositional knowledge base, but that this is not true for Forbus and Winslett.
Theorem 2. The deviation of ◦D and ◦S from the 2CNF fragment is total.
Proof. In [
We illustrate this construction on a concrete example.
Example 4. Take a knowledge base K∗ with [K∗] = {ab, ac, bc}. We have Cl 2CNF([K∗]) = [K∗] ∪ {abc}, and to define K we introduce new variables x, y, z and take a 2CNFexpressible K such that [K] = {abyz, acxz, bcxy, abcxyz}. We have [K ◦S µ] = [K ◦D µ] = [K∗] (see Table 4).
[µ] ab [K∗] ac bacbc abyz
yz bcyz acyz cyz acxz bcxz
xz abxz bxz bcxy
abcxyz acxy abxy xy axy cxyz bxyz axyz xyz
Notice that in Example 4 we get [K ◦F µ] = [K ◦W µ] = {ab, ac, bc, abc}, so the construction in Theorem 2 does not work for ◦F and ◦W . Nonetheless, if we take a 2CNF-expressible knowledge base K with [K ] = {∅} we get that [K ◦F µ] = [K ◦W µ] = [K∗]. This shows that the deviation of ◦F and ◦W from 2CNF is not zero. As we show now, their deviation is not total either.
Theorem 3. The deviation of ◦W and ◦F from the 2CNF fragment is partial. Proof. We have already argued that the deviation of ◦F and ◦W from 2CNF is not zero. To show that it is not total, take a knowledge base K∗ such that its set of models is [K∗] = {a, b, c, ab, ac, bc}, with Cl 2CNF(K∗) = [K∗] ∪ {∅, abc}, and assume, first, that there is a 2CNF-expressible knowledge base K and a 2CNF-expressible formula µ such that Cl 2CNF(K∗) ⊆ [µ] and [K ◦W µ] = [K∗]. Then there are u1, u2, u3 ∈ [K] such that a u 1 = min⊆([µ] u 1), b u 2 = min⊆([µ] u 3) and c u 3 = min⊆([µ] u 3). It must hold that a ∈ u1, as otherwise ∅ u 1 ⊂ a u 1. It must also hold that b ∈/ u1, as otherwise ab u 1 ⊂ a u 1. In the same way it follows that c ∈/ u1. We repeat this argument for u2 and u3 and obtain the configuration in Table 5, where we abbreviate u1 ∪ {a} as a u1 , under the convention that if any of a, b or c does not make an appearance, that is because we know it cannot be there. Then neither of a, b or c is in maj3(u1, u2, u3) = u123 . It is straightforward to see, now, that we cannot have [K ◦W µ] = [K∗]. If there is some w ∈ [µ]\Cl 2CNF(K∗) such that w u 123 ⊂ ∅ u 123 , then none of the models of K∗ gets selected in × × × ∅ abc . . . ab u1 ab u1 ac u1 b u1 c u1 abc u1 a u1 bc u1 . . . [K ◦W µ]. If this is not the case, then ∅ u 123 ∈ min⊆([µ] u 123 ), which entails that ∅ ∈ [K ◦W µ]. This argument carries over to ◦F by replacing ⊆-minimality with cardinality-minimality. Example 2 shows that the operators considered do not stay in the Horn fragment, so their deviation is not zero. Here we show that their deviation is partial, by finding knowledge bases which never show up as the result of revision in the Horn fragment, using the operators in question.
Theorem 4. For any operator ◦ ∈ {◦D, ◦S , ◦F , ◦W }, the deviation of ◦ from the Horn fragment is partial.
Proof. Take a knowledge base K∗ such that [K∗] = {ab, a, b}. We show that K∗ ∈/ ImHorn(◦W ). Assume there exists a Horn formula µ such that Cl Horn(K∗) ⊆ [µ] and [K ◦W µ] = [K∗]. Then there are u1, u2 ∈ [K∗] such that a u 1 ∈ min⊆([µ] u 1) and b u 2 ∈ min⊆([µ] u 2). We must have a ∈ u1 (otherwise ∅ u 1 ⊂ a u 1), and also b ∈/ u1 (otherwise ab u 1 ⊂ a u 1). Similarly, we conclude that b ∈ u2 and a ∈/ u2. Since K is Horn-expressible, u1 ∩ u2 ∈ [K]. But then neither a nor b are in u1 ∩ u2. Table 6, with the notational convention used in the proof of Theorem 3, depicts this. It is now impossible to have [K ◦W µ] = [K∗]. Indeed, if there is some interpretation w ∈ [µ]\Cl Horn(K∗) such that w (u 1 ∩ u2) ⊂ ∅ (u 1 ∩ u2), then none of the models of K∗ are in [K ◦W µ]. If no such w exists, then ∅ ∈ min⊆([µ] (u 1 ∩ u2)) and therefore ∅ ∈ [K ◦W µ]. The argument carries over, with minor modifications, to the other operators. 4
Operators whose deviations are total can produce any propositional knowledge base. Things become more complicated when deviation is partial, since a knowledge base abcd [µ] [K∗] abcd × × ∅ . . .
ac u1 ∩ u2 bd u1 ∩ u2 bc u1 ∩ u2 ad u1 ∩ u2 ac u1 ∩ u2 . . . a [K∗] b [µ] ab acd u2
b u2 bcd u2
a u2 acd u2 . . . not obtainable with one operator may be obtainable with another. If this is the case, we would rightfully want to know it. In this section we present results on the differences between the images of our operators with respect to the Horn fragment.
ImHorn(◦F ) and K∗ ∈/ ImHorn(◦W ).
Proposition 1. If K∗ is a knowledge base with [K∗] = {abcd, ab, cd}, then K∗ ∈/ K∗ ∈/ ImHorn(◦F ).
Proof. Assume there exists a knowledge base K and formula µ, both Horn-expressible, such that Cl Horn([K∗]) ⊆ [µ] and [K ◦W µ] = [K∗]. Then there exist u1, u2 ∈ [K] such that ab u 1 ∈ min⊆([µ] u 1) and bc u 2 ∈ min⊆([µ] u 2). We infer that {a, b} ⊆ u1, since otherwise it would hold that ∅ u 1 ∈ min⊆([µ] u 1), which would imply that ∅ ∈ [K ◦W µ]. We also infer that {c, d} ⊆ u1, since otherwise it would hold that abcd u 1 ⊂ ab u 1, which contradicts the minimality of ab u 1. Thus, at most one of c and d can be in u1. Analogously, {c, d} ⊆ u2 and at most one of a and b is in u2. A case analysis now reveals that this implies that ∅ (u 1 ∩u2) ∈ min⊆([µ] (u 1 ∩u2)). In Table 7 this is illustrated for the case when c ∈ u1 and a ∈ u2. If there is an element w ∈ [µ]\Cl Horn(K∗) such that w (u 1 ∩ u2) ⊂ ∅ (u 1 ∩ u2), then not all the models of K∗ end up in [K ◦W µ], which is a contradiction. If there is no such element, then ∅ (u 1 ∩ u2) ∈ min⊆([µ] (u 1 ∩ u2)) and thus ∅ ∈ [K ◦W µ], which is also a contradiction. The other cases are analogous. It follows that K∗ ∈/ ImHorn(◦W ). The same argument applies if we replace ⊆-minimality with cardinality-minimality, so This shows that there is a knowledge base which cannot be obtained with either Forbus’ operator ◦F or Winslett’s operator ◦W , though as we show in the proof of Theorem 5, it can be obtained with Dalal’s operator ◦D and Satoh’s operator ◦S.
Proposition 2. If K∗ is a knowledge base with [K∗] = {abcde, ab, cd, e}, then K∗ ∈/ ImHorn(◦D).
Proof. If there are Horn-expressible K and µ such that Cl Horn([K∗]) ⊆ [µ] and [K ◦D µ] = {abcde, ab, cd, e}, then there must be u1, u2, u3, u4 ∈ [K] such that {abcd u1, ab u 2, cd u 3, e u 4} ⊆ mincard([µ] [K]). We conclude that at least three of {a, b, c, d, e} must be in u1; that {a, b} ⊆ u2 and at most one of {c, d, e} can be in u2; that {c, d} ⊆ u3 and at most one of {a, b, e} can be in u3; and e ∈ u4. A case analysis of Cl Horn(K) leads to a contradiction.
The knowledge base K∗ from Proposition 2 can be obtained with ◦D, as we show below. But we need one more observation to derive our results on the relations between operators.
Proposition 3. For any knowledge base K∗ such that {a, b, ab} ⊆ [K∗] and ∅ ∈/ [K∗], it holds that K∗ ∈/ ImHorn(◦D) ∪ ImHorn(◦S).
Proof. It is easy to see that the proof of Theorem 4 works for ◦D and ◦S and any knowledge base K∗ such that {a, b, ab} ⊆ [K∗] and ∅ ∈/ [K∗]. However, as we show in the proof of Theorem 5, it does not carry over to ◦F and ◦W .
The following result gathers these results into a unified image of the differences between the operators over the Horn fragment.
Theorem 5. For the operators we study, the following holds: – ImHorn(◦D) ⊆ ImHorn(◦W ) ∪ ImHorn(◦F ), – ImHorn(◦S) ⊆ ImHorn(◦D) ∪ ImHorn(◦W ) ∪ ImHorn(◦F ), – ImHorn(◦F ) ⊆ ImHorn(◦D) ∪ ImHorn(◦S), – ImHorn(◦W ) ⊆ ImHorn(◦S) ∪ ImHorn(◦D).
Proof. From Proposition 1, we know that a knowledge base K1∗ with [K∗] = {abcd, ab, cd} is in neither ImHorn(◦F ) nor in ImHorn(◦W ). However, a knowledge base K1 with [K1] = {abc, bcd, bc} and a formula µ1 with [µ1] = {abcd, ab, cd, ∅} are both Hornexpressible and [K1 ◦D µ1] = [K ◦S µ1] = [K1∗].1 Thus, K1∗ ∈ ImHorn(◦D) ∩ ImHorn(◦S). From Proposition 2 a knowledge base K2∗ with [K2∗] = {abcde, ab, cd, e} is not in ImHorn(◦S). However, if we take [K2] = {ace} and [µ2] = {abcde, ab, cd, ∅}, then [K2 ◦D µ2] = [K2∗] and thus K2∗ ∈ ImHorn(◦D). From Proposition 3 a knowledge base K3∗ with [K2∗] = {ab, a, b, d} is neither in ImHorn(◦D) nor in ImHorn(◦S). However, take [K3] = {abcd, abcd, bcd, cd} and [µ3] = {ab, a, b, d, ∅}. Then [K3 ◦F µ3] = [K3 ◦W µ3] = [K3∗] and thus K3∗ ∈ ImHorn(◦F ) ∩ ImHorn(◦W ).
The exact relationship between ImHorn(◦F ) and ImHorn(◦W ) is still open, as is the
question whether ImHorn(◦D) ⊂ ImHorn(◦S).
1 This constitutes a counterexample to Proposition 11 in [
We have presented results on the deviation of four major belief change operators from
well-known fragments of propositional logic. These results are summarised in Table 2
of Section 3. We have found that for the 1CNF fragment, deviation is uniformly zero.
The 1CNF fragment is ‘safe’, in that revision on 1CNF knowledge bases always
produces 1CNF-expressible results. Future work would look for general conditions that
make a fragment safe in this sense. For the 2CNF and Horn fragments deviation has
been found to range from partial to total. If it is important that the result be expressible
in the target language, some kind of repair (or refinement [