=Paper=
{{Paper
|id=Vol-1928/paper6
|storemode=property
|title=Deviation in Belief Change on Fragments of Propositional Logic
|pdfUrl=https://ceur-ws.org/Vol-1928/paper6.pdf
|volume=Vol-1928
|authors=Adrian Haret,Stefan Woltran
|dblpUrl=https://dblp.org/rec/conf/ki/HaretW17
}}
==Deviation in Belief Change on Fragments of Propositional Logic==
https://ceur-ws.org/Vol-1928/paper6.pdf
Proceedings of the KI 2017 Workshop on Formal and Cognitive Reasoning
Deviation in Belief Change on Fragments of
Propositional Logic�
Adrian Haret and Stefan Woltran
DBAI group, TU Wien, A-1040, Vienna, Austria
{haret,woltran}@dbai.tuwien.ac.at
Abstract. 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.
1 Introduction
Belief change [1, 11] occupies a central role in understanding the logic of modifying
a knowledge base. The framework it provides allows formalization and comparison of
various types of change, such as revision [15] and update [14]. Classical results in the
field assume that the language in which knowledge is expressed subsumes propositional
logic, but recent work has been increasingly focused on change in more specialized
formalisms, suitable for use in concrete applications because of the kinds of things they
can express, or their attractive computational properties [6, 19, 7, 20].
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 [6] have studied how standard postulates have to be adapted
such that representation theorems [1, 11] can be given for the Horn fragment. Another
approach has looked into repairing inexpressible results like the one sketched above, in
order to make them fit into the language of interest [2, 3]. Finally, the design of novel
�
This work was supported by the Austrian Science Fund (FWF) under grants P25521, P30168.
64
Proceedings of the KI 2017 Workshop on Formal and Cognitive Reasoning
change operators, tailored specifically for fragments, has also been subject of recent
research [8, 13].
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 oper-
ators are among the most well studied in the field, both with respect to their semantic
representation and their complexity in fragments [9, 16, 4].
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 [12], this has not yet been done. To this end, we introduce a measure
for the degree to which a fragment is transformed through application of the studied
operators. We call this measure the deviation of a revision operator from a particular
fragment, and provide results on the deviation of established operators from the above-
mentioned fragments. Our results indicate whether the range of possible results of an
operator applied to a fragment is restricted to a subset of full propositional logic rea-
sonably close to the original fragment, or if, by contrast, any propositional base can be
obtained. Another issue is whether there exists any fragment which is closed under the
operators and this, as we shall see, holds for the 1CNF fragment. We also show, through
a comparative analysis, that different operators applied to the same fragment deviate in
different ways. In other words, understanding deviation sheds light on the differences
between major revision operators and on the expressiveness of the fragments consid-
ered. We expect considerations of this kind to play in important role in the design of
change operators for concrete Knowledge Representation formalisms.
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 Background
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|}.
65
Proceedings of the KI 2017 Workshop on Formal and Cognitive Reasoning
We define a fragment of propositional logic as a set of propositional formulas char-
acterized 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 closure-
operator 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 liter-
als) 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 ) [18, 17, 10, 5]. These operators are defined as follows:
[K ◦W µ] = {w ∈ [µ] | ∃u ∈ [K] such that w�u ∈ min⊆ ([µ] � u)},
[K ◦S µ] = {w ∈ [µ] | ∃u ∈ [K] such that w�u ∈ min⊆ ([µ] � [K])},
[K ◦F µ] = {w ∈ [µ] | ∃u ∈ [K] such that w�u ∈ mincard ([µ] � u)},
[K ◦D µ] = {w ∈ [µ] | ∃u ∈ [K] such that w�u ∈ mincard ([µ] � [K])}.
Example 1. Consider a knowledge base K with [K] = {abcd, a} and a formula µ
with [µ] = {acd, bd, a}. For K ◦ µ, consult [µ] � [K] depicted in Table 1. We have
that [K ◦D µ] = {acd}, since acd � abcd is cardinality-minimal in the whole table;
[K ◦S µ] = {acd, bd}, since acd � abcd and bd � abcd are ⊆-minimal in the whole
table; [K ◦F µ] = {acd, b}, since acd � abcd is cardinality-minimal on the abcd-
column, and b � a is cardinality-minimal on the a-column; [K ◦W µ] = {acd, bd, b},
since acd � abcd and bd � abcd are ⊆-minimal on the abcd-column, and b � a is
⊆-minimal on the a-column.
This example illustrates a relationship between the operators which holds more gen-
erally, 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.
66
Proceedings of the KI 2017 Workshop on Formal and Cognitive Reasoning
[K]
� �� �
� abcd a
acd b cd
[µ] bd ac abd
b acd ab
Table 1. Revision: ⊆-minimal elements in grey, cardinality-minimal elements in bold font
Definition 1. For a revision operator ◦ and a fragment F ⊆ L, the image of ◦ with
respect to F, denoted by Im F (◦), is defined as Im F (◦) = {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 ⊆ Im F (◦), 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 for-
mula µ = (¬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 ⊂ Im Horn (◦)
and 2CNF ⊂ Im 2CNF (◦).
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 Im F (◦) = L; (ii) partial if F ⊂
Im F (◦) ⊂ L; and (iii) zero if Im F (◦) = F.
Deviation is closely related to the notion of simplifiability [12], which we briefly
recall here. For a fragment F and an operator ◦, a knowledge base K ∗ ⊆ L is F -
simplifiable w.r.t. ◦ if there exists an F -knowledge base K and µ ∈ F, such that [K ◦
µ] = [K ∗ ]. It should be mentioned, however, that existing results on simplifiability
apply only to Dalal’s operator. These results can be translated to our setting as follows:
the deviation of ◦D is (i) total for 2CNF, (ii) partial for Horn, and (iii) zero for 1CNF.
Our results in Section 3 confirm these findings, though the reasoning proceeds along a
different route.
3 Main results
Our results on deviation are summarized in Table 2, and the rest of the section is dedi-
cated to justifying them. As mentioned in Section 2, F ⊆ Im F (◦) for any fragment F
and all operators considered. In other words, it is non-F -expressible knowledge bases
67
Proceedings of the KI 2017 Workshop on Formal and Cognitive Reasoning
1CNF 2CNF Horn
S
◦ zero total partial
◦D zero total partial
◦F zero partial partial
◦W zero partial partial
Table 2. Precise results on deviation
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.
3.1 The 1CNF fragment
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 ]�[K2 ] 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 ] � [P2 ; I2 ] = [(P1 � P2 )\(I1 ∪ I2 ); I1 ∪ I2 ],
which implies that [K1 ] � [K2 ] is 1CNF-expressible.
For one direction, take (P1 ∪ J1 ) � (P2 ∪ J2 ) ∈ [P1 ; I1 ] � [P1 ; I1 ], with Ji ⊆ Ii ,
for i ∈ {1, 2}. We show that (P1 ∪ J1 ) � (P2 ∪ J2 ) = (P1 � P2 )\(I1 ∪ I2 ) ∪ ((I1 ∪
I2 ) ∩ ((J1 � J2 )\(P1 � P2 ))).
“⊆” Take w ∈ (P1 ∪ J1 ) � (P2 ∪ 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 � P2 . Since P1 ∩ I1 = ∅, it follows that w ∈ / I1 and w ∈
/ I1 ∪ I2 . We conclude
that w ∈ (P1 � P2 )\(I1 ∩ I2 ). Case 2. If w ∈ J1 , then w ∈ J1 � J2 . Second, w ∈ I1
and hence w ∈ I1 ∪ I2 and w ∈ / P1 . Since w ∈/ P2 , we get that w ∈
/ P1 � P2 and thus
w ∈ (J1 � J2 )\(P1 � P2 ). We conclude that w ∈ (I1 ∪ I2 ) ∩ ((J1 � J2 )\(P1 � P2 )).
“⊇” Take w ∈ (P1 � P2 )\(I1 ∪ I2 ) ∪ ((I1 ∪ I2 ) ∩ ((J1 � J2 )\(P1 � P2 ))). To
get the conclusion, we perform a case analysis as to whether w ∈ (P1 � P2 )\(I1 ∪ I2 )
or w ∈ (I1 ∪ I2 ) ∩ ((J1 � J2 )\(P1 � P2 )).
For the other direction, take (P1 � P2 )\(I1 ∪ I2 ) ∪ ((I1 ∪ I2 ) ∩ J ) ∈ [(P1 �
P2 )\(I1 ∪ I2 ); I1 ∪ I2 ], where J ⊆ I1 ∪ I2 . As above, we show by double inclusion
that (P1 � P2 )\(I1 ∪ I2 ) ∪ ((I1 ∪ I2 ) ∩ J ) = (P1 ∪ J1 ) � (P2 ∪ J2 ), where
Ji = Ii ∩ (J � (P1 � P2 )), for i ∈ {1, 2}.
68
Proceedings of the KI 2017 Workshop on Formal and Cognitive Reasoning
If [K1 ] � [K2 ] is 1CNF-expressible, then it has a unique ⊆-minimal element, which
is also cardinality-minimal. We identify, then, min⊆ ([K1 ]�[K2 ]) = mincard ([K1 ]�[K2 ])
with this single element.
Example 3. If [K1 ] = {a, ab, ac, abc} and [K2 ] = {∅, b, c, bc}, then [K1 ] � [K2 ] =
{∅, a, b, c, ab, ac, bc, abc}. We have that min⊆ ([K1 ] � [K2 ]) = mincard ([K1 ] � [K2 ]) =
{∅}, 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 � ui = min⊆ ([µ] � ui ),
for i ∈ {1, 2}. Then consider u3 , u4 ∈ [K] such that (w1 ∩ w2 ) � u3 = min⊆ ((w1 ∩
w2 ) � [K]) and (w1 ∪ w2 ) � u4 = 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 ) � u3 = min⊆ ([µ] � u3 ) and (w1 ∪ w2 ) � u4 = min⊆ ([µ] � u4 ).
For that, we first show that (w1 ∩ w2 ) � u3 ⊆ w � u3 , for some arbitrary w ∈ [µ]. We
take an atom a ∈ (w1 ∩ w2 ) � u3 and do a case analysis.
Case 1. If a ∈ (w1 ∩ w2 )\u3 , then by assumption (w1 ∩ w2 ) � u3 = min⊆ ((w1 ∩
w2 ) � [K]), and thus (w1 ∩ w2 ) � u3 ⊆ (w1 ∩ w2 ) � u1 . Since a ∈ w1 ∩ w2 , we get that
a∈/ u1 . With a ∈ w1 , this entails that a ∈ w1 � u1 . But w1 � u1 = min⊆ ([µ] � u1 ),
so a ∈ w � u1 . With a ∈ / u1 , this implies that a ∈ w. Thus a ∈ w � (w1 ∩ w2 )
and hence (w1 ∩ w2 ) � u3 ⊆ w � u3 . 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 ) � u3 ⊆ (w1 ∩ w2 ) � u1 and conclude that a ∈ u1 , which further entails
that a ∈ w1 � u1 . Then a ∈ w � u1 , and thus a ∈ / w, which entails that a ∈ w � u3 .
With this we have shown that (w1 ∩ w2 ) � u3 = min⊆ ([µ] � u3 ). The proof that
(w1 ∪ w2 ) � u4 = min⊆ ([µ] � u4 ) is similar.
(“⇐”) If {w1 ∩ w2 , w1 ∪ w2 } ⊆ [K ◦W µ], there exist u3 , u4 ∈ [K] such that
(w1 ∩ w2 ) � u3 = min⊆ ([µ] � u3 ) and (w1 ∪ w2 ) � u4 = min⊆ ([µ] � u4 ). Take
u1 , u2 ∈ [K] such that w1 � u1 = min⊆ (w1 � [K]) and w2 � u2 = min⊆ (w2 � [K]).
We then show that wi � ui = min⊆ ([µ] � ui ), for i ∈ {1, 2}. Indeed, take an arbitrary
w ∈ [µ] and an a ∈ w1 � u1 and consider the two possible cases. Case 1. If a ∈ w1 \u1 ,
then a ∈ w1 � u3 and hence a ∈ / u3 . It follows that a ∈ (w1 ∪ w2 ) � u3 and therefore
a ∈ w � u3 and a ∈ w, which entails a ∈ w � u1 . Case 2. If a ∈ u1 \w1 , then
a ∈ w1 � u3 and then a ∈ (w1 ∩ w2 ) � u3 and hence a ∈ w � u3 . This leads to a ∈ /w
and then to a ∈ w � u1 . The proof for w2 � u2 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 inter-
pretations [12], which we recapitulate here in an equivalent, though more concise for-
mulation: w1 , w2 ∈ W are critical with respect to a knowledge base K ∗ if w1 �⊆ w2 ,
69
Proceedings of the KI 2017 Workshop on Formal and Cognitive Reasoning
[K]
� �� �
� u1 u2 u3 u4
w1 w 1 � u1 ↑
w2 ↓ w 2 � u2
... ↓
[µ] w1 ∩ w2 ← (w1 ∩ w2 ) � u3 →
w 1 ∪ w2 ← (w1 ∪ w2 ) � u4
w w � u 3
...
Table 3. The “⇒” direction for ◦W in Lemma 2: arrows indicate area where shaded element is
⊆-minimal.
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-1CNF-
expressible, then there exist w1 , w2 ∈ Cl 1CNF ([K ∗ ]) critical with respect to K ∗ [12].
Theorem 1. For any operator ◦ ∈ {◦D , ◦S , ◦F , ◦W }, the deviation of ◦ from the 1CNF
fragment is zero.
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 The 2CNF fragment
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 [12] it is shown constructively that any propositional knowledge base is
in Im 2CNF (◦D ). We show here that the same construction also works for ◦S . Thus,
take a non-2CNF-expressible knowledge base K ∗ such that [K ∗ ] = {w1 , . . . , wn }
and a formula µ such that [µ] = Cl 2CNF ([K ∗ ]). Let X = {x1 , . . . , xn } be a set
of n atoms that do not appear in K ∗ , and K be a knowledge base such that [K] =
Cl 2CNF ({w1 ∪ {x2 , . . . , xn }, . . . , wn ∪ {x1 , . . . , xn−1 }}). Then, for i ∈ {1, . . . , n},
we have that min⊆ ([µ] � [K]) = {X\{xi } | i ∈ {1, . . . , n}}, where X\{xi } =
70
Proceedings of the KI 2017 Workshop on Formal and Cognitive Reasoning
wi � (wi ∪ (X\{xi })). To see why this holds, assume there exists wj ∈ [µ] and
wk ∪(X\Y ) ∈ [K] such that wj �(wk ∪(X\Y )) ⊂ X\{xi }, for some i ∈ {1, . . . , n}.
Then it must be the case that wj � wk = ∅, and X\Y ⊂ X\{xi }. This last fact entails
that {xi } ⊂ Y , but such an element does not exist in [K].
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 2CNF-
expressible K such that [K] = {abyz, acxz, bcxy, abcxyz}. We have [K ◦S µ] =
[K ◦D µ] = [K ∗ ] (see Table 4).
[K]
� �� �
� abyz acxz bcxy abcxyz
ab yz bcxz acxy cxyz
[K ∗ ] ac bcyz xz abxy bxyz
[µ]
bc acyz abxz xy axyz
× abc cyz bxz axy xyz
Table 4. Construction for the 2CNF fragment: ⊆-minimal elements are highlighted in grey,
elements that must not end up in the result are marked with ×.
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 � u1 = min⊆ ([µ] � u1 ), b � u2 = min⊆ ([µ] � u3 ) and c � u3 =
min⊆ ([µ] � u3 ). It must hold that a ∈ u1 , as otherwise ∅ � u1 ⊂ a � u1 . It must
also hold that b ∈ / u1 , as otherwise ab � u1 ⊂ a � u1 . 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 u�1 ∪ {a} as a�u�1 �, 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 ) = �u�123 �. 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
71
Proceedings of the KI 2017 Workshop on Formal and Cognitive Reasoning
[K]
� �� �
� a�u�1 � b�u�2 � c�u�3 � �u�123 �
a ab�u�1 � ab�u�2 � ac�u�3 � a�u�123 �
b ab�u�1 � �u�2 � bc�u�3 � b�u�123 �
c ac�u�1 � bc�u�2 � �
�u3 � c�u�123 �
[K ∗ ]
ab b�u�1 � a�u�2 � abc�u3 � ab�u�123 �
�
[µ]
ac c�u�1 � abc�u�2 � a�u�3 � ac�u�123 �
bc abc�u�1 � c�u�2 � b�u�3 � bc�u�123 �
× ∅ a�u�1 � b�u�2 � c�u�3 � �u�123 �
× abc bc�u�1 � ac�u�2 � ab�u�3 � abc�u�123 �
× ... ... ... ... ...
Table 5. K ∗ ∈
/ Im 2CNF (◦F ) and K ∗ ∈
/ Im 2CNF (◦W )
[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.
3.3 The Horn fragment
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 ∗ ∈ /
Im Horn (◦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 � u1 ∈ min⊆ ([µ] � u1 ) and
b � u2 ∈ min⊆ ([µ] � u2 ). We must have a ∈ u1 (otherwise ∅ � u1 ⊂ a � u1 ), and also
b∈ / u1 (otherwise ab � u1 ⊂ a � u1 ). 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 � (u1 ∩ u2 ) ⊂ ∅ � (u1 ∩ u2 ), then none of the
models of K ∗ are in [K ◦W µ]. If no such w exists, then ∅ ∈ min⊆ ([µ] � (u1 ∩ u2 ))
and therefore ∅ ∈ [K ◦W µ]. The argument carries over, with minor modifications, to
the other operators.
4 Comparison over the Horn fragment
Operators whose deviations are total can produce any propositional knowledge base.
Things become more complicated when deviation is partial, since a knowledge base
72
Proceedings of the KI 2017 Workshop on Formal and Cognitive Reasoning
[K]
� �� �
� a�u�1 � b�u�2 � �u�1 ∩ u�2 �
a �u�1 � ab�u�2 � a�u�1 ∩ u�2 �
[K ∗ ] b ab�u�1 � �u�2 � b�u�1 ∩ u�2 �
[µ] ab b�u�1 � a�u�2 � ab�u�1 ∩ u�2 �
× ∅ a�u�1 � b�u�2 � �u�1 ∩ u�2 �
× ... ... ... ...
Table 6. K ∗ ∈
/ Im Horn (◦), for any of the operators
[K]
� �� �
� abc�u�1 � acd�u�2 � ac�u�1 ∩ u�2 �
abcd d�u�1 � b�u�2 � bd�u�1 ∩ u�2 �
[K ∗ ] ab c�u�1 � bcd�u�2 � bc�u�1 ∩ u�2 �
[µ] cd abd�u�1 � a�u�2 � ad�u�1 ∩ u�2 �
× ∅ abc�u�1 � acd�u�2 � ac�u�1 ∩ u�2 �
× ... ... ... ...
Table 7. K ∗ ∈
/ Im Horn (◦F ) and K ∗ ∈
/ Im Horn (◦W )
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.
Proposition 1. If K ∗ is a knowledge base with [K ∗ ] = {abcd, ab, cd}, then K ∗ ∈
/
Im Horn (◦F ) and K ∗ ∈
/ Im Horn (◦W ).
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 � u1 ∈ min⊆ ([µ] � u1 ) and bc � u2 ∈ min⊆ ([µ] � u2 ). We infer that
{a, b} ⊆ u1 , since otherwise it would hold that ∅ � u1 ∈ min⊆ ([µ] � u1 ), which would
imply that ∅ ∈ [K ◦W µ]. We also infer that {c, d} �⊆ u1 , since otherwise it would hold
that abcd � u1 ⊂ ab � u1 , which contradicts the minimality of ab � u1 . 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 ∅�(u1 ∩u2 ) ∈ min⊆ ([µ]�(u1 ∩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 � (u1 ∩ u2 ) ⊂ ∅ � (u1 ∩ u2 ), then not all the
models of K ∗ end up in [K ◦W µ], which is a contradiction. If there is no such element,
then ∅ � (u1 ∩ u2 ) ∈ min⊆ ([µ] � (u1 ∩ u2 )) and thus ∅ ∈ [K ◦W µ], which is also
a contradiction. The other cases are analogous. It follows that K ∗ ∈ / Im Horn (◦W ).
The same argument applies if we replace ⊆-minimality with cardinality-minimality, so
K∗ ∈ / Im Horn (◦F ).
73
Proceedings of the KI 2017 Workshop on Formal and Cognitive Reasoning
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 ∗ ∈
/
Im Horn (◦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 � u2 , cd � u3 , e � u4 } ⊆ 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 ∈
∗ D S
/ Im Horn (◦ ) ∪ Im Horn (◦ ).
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 ◦ and ◦W .
F
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:
– Im Horn (◦D ) �⊆ Im Horn (◦W ) ∪ Im Horn (◦F ),
– Im Horn (◦S ) �⊆ Im Horn (◦D ) ∪ Im Horn (◦W ) ∪ Im Horn (◦F ),
– Im Horn (◦F ) �⊆ Im Horn (◦D ) ∪ Im Horn (◦S ),
– Im Horn (◦W ) �⊆ Im Horn (◦S ) ∪ Im Horn (◦D ).
Proof. From Proposition 1, we know that a knowledge base K1∗ with [K ∗ ] = {abcd, ab, cd}
is in neither Im Horn (◦F ) nor in Im Horn (◦W ). However, a knowledge base K1 with
[K1 ] = {abc, bcd, bc} and a formula µ1 with [µ1 ] = {abcd, ab, cd, ∅} are both Horn-
expressible and [K1 ◦D µ1 ] = [K ◦S µ1 ] = [K1∗ ].1 Thus, K1∗ ∈ Im Horn (◦D ) ∩
Im Horn (◦S ). From Proposition 2 a knowledge base K2∗ with [K2∗ ] = {abcde, ab, cd, e}
is not in Im Horn (◦S ). However, if we take [K2 ] = {ace} and [µ2 ] = {abcde, ab, cd, ∅},
then [K2 ◦D µ2 ] = [K2∗ ] and thus K2∗ ∈ Im Horn (◦D ). From Proposition 3 a knowledge
base K3∗ with [K2∗ ] = {ab, a, b, d} is neither in Im Horn (◦D ) nor in Im Horn (◦S ). How-
ever, take [K3 ] = {abcd, abcd, bcd, cd} and [µ3 ] = {ab, a, b, d, ∅}. Then [K3 ◦F µ3 ] =
[K3 ◦W µ3 ] = [K3∗ ] and thus K3∗ ∈ Im Horn (◦F ) ∩ Im Horn (◦W ).
The exact relationship between Im Horn (◦F ) and Im Horn (◦W ) is still open, as is the
question whether Im Horn (◦D ) ⊂ Im Horn (◦S ).
1
This constitutes a counterexample to Proposition 11 in [12].
74
Proceedings of the KI 2017 Workshop on Formal and Cognitive Reasoning
5 Conclusion and future work
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 pro-
duces 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 [2]) is required. Our results
thus complement existing work on refinements, as they reveal when, and to which ex-
tent, such repairs are needed. On the other hand, if an application allows the result to be
expressed in a richer language, then we would be interested in knowing whether results
that cannot be obtained with one operator could be obtained with another. This applies
to cases when deviation is partial, and is especially complicated for the Horn fragment.
In Section 4 we have clarified some of the relationships between images with respect
to the Horn fragment, but the question of whether there is any knowledge base that
can be obtained with Dalal but not with Satoh, and the relationship between the images
of Forbus and Winslett, on the other, are still open and left for future work. Also left
for future work is the relationship between the images of Forbus and Winslett in the
2CNF fragment. To get a clearer idea of the images of these operators with respect to
the more complicated fragments such as Horn, we would also consider the complexity
of deciding whether a given knowledge base is in the image of an operator.
References
[1] Alchourrón, C.E., Gärdenfors, P., Makinson, D.: On the Logic of Theory Change: Partial
Meet Contraction and Revision Functions. J. Symb. Log. 50(2), 510–530 (1985)
[2] Creignou, N., Papini, O., Pichler, R., Woltran, S.: Belief revision within fragments of propo-
sitional logic. J. Comput. Syst. Sci. 80(2), 427–449 (2014)
[3] Creignou, N., Papini, O., Rümmele, S., Woltran, S.: Belief Merging within Fragments of
Propositional Logic. ACM Trans. Comput. Log. 17(3), 20:1–20:28 (2016)
[4] Creignou, N., Pichler, R., Woltran, S.: Do Hard SAT-Related Reasoning Tasks Become
Easier in the Krom Fragment? In: Proc. of IJCAI 2013). pp. 824–831 (2013)
[5] Dalal, M.: Investigations into a Theory of Knowledge Base Revision. In: Proc. of IJCAI
1988. pp. 475–479 (1988)
[6] Delgrande, J.P., Peppas, P.: Belief revision in Horn theories. Artif. Intell. 218, 1–22 (2015)
[7] Delgrande, J.P., Schaub, T., Tompits, H., Woltran, S.: A Model-Theoretic Approach to Be-
lief Change in Answer Set Programming. ACM Trans. Comput. Log. 14(2), 14:1–14:46
(2013)
[8] Diller, M., Haret, A., Linsbichler, T., Rümmele, S., Woltran, S.: An Extension-Based Ap-
proach to Belief Revision in Abstract Argumentation. In: Proc. of IJCAI 2015. pp. 2926–
2932 (2015)
[9] Eiter, T., Gottlob, G.: On the Complexity of Propositional Knowledge Base Revision, Up-
dates, and Counterfactuals. Artif. Intell. 57(2-3), 227–270 (1992)
[10] Forbus, K.D.: Introducing Actions into Qualitative Simulation. In: Proc. of IJCAI 1989. pp.
1273–1278 (1989)
75
Proceedings of the KI 2017 Workshop on Formal and Cognitive Reasoning
[11] Gärdenfors, P.: Knowledge in Flux: Modelling the Dynamics of Epistemic States. The MIT
Press, Cambridge, MA (1988)
[12] Haret, A., Mailly, J., Woltran, S.: Distributing Knowledge into Simple Bases. In: Proc. of
IJCAI 2016. pp. 1109–1115 (2016)
[13] Haret, A., Rümmele, S., Woltran, S.: Merging in the Horn Fragment. In: Proc. of IJCAI 15.
pp. 3041–3047 (2015)
[14] Katsuno, H., Mendelzon, A.O.: On the Difference between Updating a Knowledge Base
and Revising It. In: Proc. of KR 1991). pp. 387–394 (1991)
[15] Katsuno, H., Mendelzon, A.O.: Propositional Knowledge Base Revision and Minimal
Change. Artif. Intell. 52(3), 263–294 (1992)
[16] Liberatore, P., Schaerf, M.: Belief Revision and Update: Complexity of Model Checking.
J. Comput. Syst. Sci. 62(1), 43–72 (2001)
[17] Satoh, K.: Nonmonotonic Reasoning by Minimal Belief Revision. In: FGCS. pp. 455–462
(1988)
[18] Winslett, M.: Updating Logical Databases. Cambridge University Press (1990)
[19] Zhuang, Z.Q., Pagnucco, M., Zhang, Y.: Definability of Horn Revision from Horn Contrac-
tion. In: Rossi, F. (ed.) Proc. of IJCAI 2013). pp. 1205–1211. IJCAI/AAAI (2013)
[20] Zhuang, Z., Wang, Z., Wang, K., Qi, G.: DL-Lite Contraction and Revision. J. Artif. Intell.
Res. (JAIR) 56, 329–378 (2016)
76