In belief revision, the result of a contraction should be a logically closed set (closure) such that the input is not inferred (success). Traditionally, these two postulates depend on the same consequence operator. The present work investigates the consequences of using two different consequence operators for each of these desiderata: the classic Cn to compute success and a second weaker operator to compute the closure. We prove a representation theorem and some other properties for the new contraction.
Belief revision is the branch of knowledge representation that deals with the dynamics of epistemic states. In their seminal paper [Alchourro´n et al., 1985], Alchourro´n, Ga¨rdenfors and Makinson proposed to represent the epistemic state of an agent as a logically closed set of propositions called belief sets. The authors focus on three main epistemic operations over belief sets: expansion, contraction and revision. Expansion is the simple addition of a proposition to the epistemic state, contraction is the removal of a proposition and revision is the consistent addition of a proposition. Each of this operations is characterized by a set of rationality postulates.
Consider, for example, the following postulates for contraction: = Cn(K (success) If 2= Cn(K satisfied). Hence, in belief base contraction there is a distinction between the sentences in the base and the sentences inferred from the base. Especially in computer science, belief base revision is very useful since computing the logical closure of a set may be hard if possible at all.
Operations in belief bases, however, have some undesirable properties due to the fact that equivalent sentences may be treated differently. In the present work we explore the consequences of keeping both closure and success where the consequence operations in these two postulates do not necessarily coincide. More precisely, we assume that closure is guaranteed only for a weaker consequence operation. This weaker notion of consequence may be easy to compute and at the same time useful to avoid some undesirable consequences of belief base operations.
Throughout this paper, we consider the language of classical propositional logic, closed under the usual boolean connectives.
We call consequence operator a function that takes sets of formulas into sets of formulas. A consequence operator C is Tarskian if and only if it satisfies: (inclusion) A
C(A) (idempotence) C(A) = C(C(A)) (monotonicity) If A
B then C(A)
C(B)
notes the associated relation: A ` stands for 2 Cn(A).
Lowercase Latin letters (p, q, r) stand for atoms, lowercase Greek letters ( ; ) stand for formulas, uppercase Latin letters (A, B, K) stand for sets of formulas.
The rest of the paper is structured as follows. A brief overview of classical belief revision is given in Section 2. Section 3 presents pseudo-contractions, the kind of operation we are exploring in this paper. In Section 4, we describe our proposal, depicting it with examples in Section 5. Section 6 highlights some previous works that are related to ours. We delineate our conclusions in Section 7. Proofs for theorems and propositions are found in the Appendix. 2
In the AGM paradigm [Alchourro´n et al., 1985], belief states are typically represented by sets of sentences closed under logical consequence, the so-called belief sets. Three change operations were initially defined: expansion, contraction and revision. Expansion is the simple addition of a new sentence, followed by logically closing the resulting set, i.e, K + =
of operations, all delimited by rationality postulates that they should satisfy. Let K be a belief set and and be formulas. The original AGM basic postulates for contraction are:
or 62 Cn(K ) interchangeably in the success postulate.
AGM revision is usually defined from contraction and expansion by means of the Levi identity:
K = (K : ) + Therefore, in this paper we will focus on contraction.
Besides defining rationality postulates for contraction, Alchourro´ n et al.[1985] have also proposed a construction for a contraction operation. Partial meet contraction is based on the notion of a remainder set, the set of all maximal subsets that do not imply the element that is to be contracted. Formally:
set B? is such that X 2 B? a formula. The remainder if and only if: X X 0
B, 2= Cn(B0), but 2 Cn(B0 [ f g)
Furthermore, we have the following representation theorem: Theorem 4 [Hansson, 1992b] An operation is a partial meet contraction over belief bases if and only if it satisfies the postulates of success, inclusion, relevance and uniformity.
For logically closed sets, both characterizations are
equivalent
Contraction operators on belief sets can be generated from operations on belief bases. As an example, one can define a contraction operator for belief sets as K = Cn(B ), where K = Cn(B) and is a base contraction operator. If is a partial meet base contraction, satisfies five of the six AGM postulates, but not recovery.
In [Hansson, 1989] a weakening of the inclusion postulate was proposed, called logical inclusion.
(logical inclusion) Cn(B )
Cn(B)
Hansson has suggested to call operations that satisfy success and logical inclusion pseudo-contractions.
Nebel has proposed a pseudo-contraction for bases that generates a contraction that satisfies all the six AGM postulates [Nebel, 1989].
Definition 5 Let V B be the conjunction of all elements of B. Nebel’s pseudo-contraction for the set B is the operator such that for all sentences : B =
B T (B? ) [ f ! V Bg if 2 Cn(;) otherwise
Although the belief set operation generated from Nebel’s pseudo-contraction satisfies all the AGM postulates, it adds unnecessary information to the base. As shown in [Ribeiro and Wassermann, 2008], it suffices to add f ! V B0g, where B0 = B nT (B? ). As already noted in [Ribeiro and Wassermann, 2008], there is no other intuition behind Nebel’s operation than maintaining recovery, a postulate which has been deemed as polemic already since the 80’s [Makinson, 1987].
In this work we want to further explore the possibility of working with belief bases with logical inclusion, allowing for some syntax independence without having to resort to belief sets. 4
As stated earlier, the direct application of partial meet contraction over closed belief sets and over belief bases creates problems of practical (computational infeasibility) and theoretical (syntax dependence) nature, respectively. One of the aims of this study is to assess the effects of doing the traditional partial meet contraction on belief bases closed by a consequence operation that is between the classical consequence operator and the identity (i.e., the base itself). Hence, we will assume that this operator (here called Cn ) is Tarskian.
We will study the properties of the application of the partial meet contraction over a set closed under Cn , i.e., the operator defined as: Definition 6 Let B be a set of sentences, Cn a function from sets of sentences to sets of sentences and a selection function for Cn (B). The operator is such that, for all sentences :
Notice that B = T (Cn (B)? ) = Cn (B) , where is the partial meet contraction. Since satisfies the postulates of success, inclusion, relevance and uniformity, it follows directly (details in the Appendix) that satisfies success and: (inclusion ) B
Cn (B) (relevance ) If B0 such that B 2 Cn(B0 [ f g) 2 Cn (B) n (B
B0 Cn (B), ), then there is a 2= Cn(B0), but (uniformity ) If for all B0 only if 2 Cn(B0), then B Cn (B), = B
For several applications it is important that the construction satisfies the original success postulate, and not only a starred version of it: (success ) If Corollary 7 If Cn is Tarskian and satisfies subclassicality, then an operation that satisfies success, inclusion , relevance and uniformity also satisfies logical inclusion, logical relevance and uniformity.
With a proof that is very similar to that of the
representation theorem for partial meet contraction on bases
From this theorem and the previous corollary, it also follows: Corollary 9 If Cn is Tarskian and satisfies subclassicality, then satisfies success, logical inclusion, logical relevance and uniformity.
It is interesting that we have here a set of postulates that are independent from Cn . Nonetheless, these postulates do not characterize the operation, and are in general weaker than the postulates with . Hansson’s logical inclusion postulate is quite reasonable for base operations, as it brings syntactic independence, although with inclusion we already have a degree of independence, and with better preservation of the original set (since Cn is subclassical), and, depending on the chosen Cn , we avoid the complexity problem we have with the closure of Cn.
Another desirable property in rational contraction operations is relative closure [Hansson, 1991].
(relative closure) B \ Cn(B )
B
This property is a consequence of the postulate of relevance, which does not satisfy. Nevertheless, relative closure is satisfied, given the condition that Cn is Tarskian.
relative closure. operator satisfies
Kernel contraction [Hansson, 1994] is an alternative construction for contraction, which instead of considering maximal sets not implying a given formula as in partial meet contraction, considers minimal sets implying it. It works by finding the minimal sets (called -kernels) that imply the element being contracted and then selecting at least one element of each -kernel to remove from the belief base. The operation is characterized by the same postulates as partial meet contraction on bases, except for relevance, which is weakened to core-retainment:
(core-retainment) If 2 B n (B such that B0 B, 2= Cn(B0), but ), then there is a B0 2 Cn(B0 [ f g)
Kernel contraction may have erratic behaviour due to its non-satisfaction of relevance [Hansson, 1999]. For instance, consider the logically independent sentences p and q, and let A = fp; p _ q; p $ qg. The kernel contraction A (p ^ q) = fpg is possible, whereas partial meet contraction cannot have this outcome. As observed by Hansson, it is not sensible to give up p _ q, since p was kept.
Would the weakening of relevance to relevance or logical relevance be enough so as to make these behaviours show up in the operator? Kernel contraction does not satisfy any of these last two postulates. Furthermore, Hansson had already noticed that the lack of relative closure also contributes to these unnecessary removals in contraction. The operator , as shown above, satisfies relative closure.
A property of our pseudo-contraction is enforced closure . (enforced closure ) B = Cn (B ) Proposition 11 If Cn is Tarskian and satisfies subclassicality, an operator that satisfies inclusion and relevance also satisfies enforced closure .
Whenever A Cn (A), this postulate will imply that vacuity is not satisfied, which is an essential postulate in the point of view of rational contractions (that respect the principle of minimal change). It has as effect that the belief base will always end up closed by Cn after the contraction, even though the original base was not closed.
Nevertheless, our construction does satisfy a weaker form of vacuity: (vacuity ) If 2= Cn(B), then B = Cn (B) Proposition 12 If Cn is Tarskian and satisfies subclassicality, an operator that satisfies inclusion and relevance also satisfies vacuity .
Corollary 13 If Cn is Tarskian and satisfies subclassicality, then the operator satisfies enforced closure and vacuity .
A simple way to restore vacuity is to redefine the erator in the following manner: opDefinition 14 Let B be a set of sentences, Cn a function from sets of sentences to sets of sentences and a selection function for Cn (B). The operator 0 is such that, for all sentence :
The proof of the observation above is not given, but can be trivially obtained from theorem 8, corollary 7 and proposition 10. Note that relevance and logical relevance were lost.
Although we have attained vacuity, we have only partly gotten rid of enforced closure (just when 2= Cn(B)).
If on one hand logical inclusion seems to make more sense than inclusion for base contractions, by allowing some syntactic independence, effects such as enforced closure illustrate the need to refrain from careless additions of sentences in the contraction. Here we should mention the postulate of core-addition [Ribeiro and Wassermann, 2008]:
(core-addition) If 2 (B B n (B ) and a B0 B but ! 0 2 Cn(B0 [ f g).
) n B, then there is a 0 2 such that ! 0 2= Cn(B0)
Any operator satisfying inclusion will satisfy this postulate trivially. If we break f ! V Bg into the set of sentences f ! j 2 Bg, Nebel’s pseudo-contraction will not satisfy core-addition. Clearly the operator does not satisfy it also (neither does 0 ), and it does not satisfy vacuity as well. In the effort to fix these two problems, the operations of general partial-meet pseudo-contraction and -partial-meet pseudo-contraction, proposed in [Ribeiro and Wassermann, 2008], seem to be viable solutions. 5
In this section we are going to show some concrete examples of Cn functions that can be useful in the solution of practical problems. The first example we mention is the Cleopatra example, adapted from [Ribeiro and Wassermann, 2008]. Example 1 Consider a language with three propositional letters, p, q and r and a belief base B = fp ^ qg, where p stands for Cleopatra had a son and q, Cleopatra had a daughter. If we want to contract by p, applying a partial meet contraction produces B p = ;. This is not always the expected result, because the loss of faith in the belief that Cleopatra had a son also made us lose faith in the belief that she had a daughter.
With the classic partial meet construction for bases we would have B?p = f;g, so the selection function needs to choose f;g, causing the overall contraction process to produce ; as final result.
On the other hand, if we take B to represent the belief set K = Cn(B), then K contains both p and q and the belief that Cleopatra had a daughter (q) may survive the contraction, i.e., we may have q 2 K p. But then we would also have q _ r, r ! q and many other irrelevant formulas in the resulting set, since it is closed under Cn.
Let us consider an intermediate consequence operator: Cn1(A) = f j ^
2 A or ^ 2 A or ^ ^
We can use Cn1 with the operator to solve the problem of the preceding example. In this case, we have Cn1(B) = fp ^ q; p; qg and Cn1(B)?p = ffqgg, hence the selection function would choose the whole remainder set, ffqgg, and, accordingly, B p = fqg.
Although the usefulness of this consequence operation is dubious, its use already brings better results than the typical base contraction in some cases, as in the former example. Example 2 Suppose I believe that the town of Juazeiro do
the state of Pernambuco is located in Brazil (p ! b). Speaking with a colleague, I found that this town is not located in his state (Pernambuco), that is, I contract j ! p from my base. The outcome is B (j ! p) = fp ! bg. So, I no longer know whether Juazeiro do Norte is located in Brazil.
In this example, as well as in the previous one, one can blame the poor codification of the belief base for the problems. The knowledge that Juazeiro do Norte is located in Brazil, if obvious, perhaps would be individually justified, and so it would deserve to be explicitly in the base. At this point the syntactic independence dilemma reappears. In some cases we want to have it, but without having to generate infinitely many derivative sentences with little utility.
However, when working with ontologies, for instance, it is possible that the user does not want to make explicit every possible relationship, trusting the transitivity of some properties (i.e., he would be more concerned with his ontology on the knowledge level than on the syntactic level). One may also want a knowledge base with little redundancy.
Again, neither the belief base nor the belief set approach would give us the desired result.
Returning to the foregoing example, we could use a Cn2 that adds to the base the transitive closure of !:
Cn2(A) = A [ f 1 !
; 1 ! !
In that case, we would have Cn2(B) = B [ fj ! bg, what results in Cn2(B)?(j ! p) = ffp ! b; j ! bgg. As in the last example, the selection function must choose the only member of the remainder set, therefore B (j ! p) = fp ! b; j ! bg. It is interesting to note that we could also use here Cn20 (B) to be the set of all Horn consequences of B.
The following example was adapted from [Hansson, 1993]. Example 3 Suppose I believe, for good and independent reasons, that Andy is son of the mayor (a) and Bob is son of the mayor (b). Then I hear the mayor say: “I certainly have nothing against our youth studying abroad. My only son did it for three years”. I then have to retract a ^ b from my base B = fa; bg. But it is reasonable to retain a belief that either Andy or Bob is the son of the mayor, i.e., the result of the contraction should be fa _ bg.
The remainder set for the operation above is B?(a ^ b) = ffag; fbgg. So, the resulting partial meet contraction is either a , fbg or ;, the first two being odd since we do not seem to f g have reasons to prefer a over b or vice-versa.
In the same paper where he presented the example above, Hansson has done an extensive study of partial meet contraction on disjunctively closed bases. If we define Cn3(A) as the disjunctive closure of A, as defined by Hansson, that is, Cn3(A) is the set of sentences that are either elements of A or disjunctions of elements of A, we can manage to get the desired result.
Cn3(A) = A [ fW ij i 2 Ag
We have Cn3(B) = fa; b; a _ bg. Then, the remainder set is Cn3(B)?(a ^ b) = ffa; a _ bg; fb; a _ bgg, and so the selection function may choose both sets, producing the expected result in the lack of evidence for a or b: B (a ^ b) = fa _ bg.
Consider now the case where the language has three propositional letters (a, b, and c). If we take the belief set K =
not hard to see that there are two remainder sets containing fa; a _ b; a _ c; b _ cg, fb; a _ b; a _ c; b _ cg and hence, these two formulas may survive contraction, even if the original set did not mention c. There have been several attempts in the literature to study AGM-like contraction operations based on different consequence operations.
Concerning belief bases, Hansson and Wassermann 2002
have shown that the original representation results for
characterizing partial meet contraction only depended on the
underlying logic being compact and monotonic. The main
difference from what we are proposing in this paper is that the
underlying consequence operator C is used for computing the
remainder sets and everywhere in the postulates. So, for
example, if we take as underlying logic one for approximate
reasoning, as suggested in [Chopra et al., 2001], the
remainders will be different than the ones we use for our
operation. If the approximation is done from below
More recently, there has been a series of papers considering Horn Contraction [Delgrande, 2008; Booth et al., 2011; Delgrande and Wassermann, 2013], which again, replace all classical reasoning by Horn reasoning. Contraction of belief sets has also been studied for non-classical logics [Ribeiro et al., 2013; Ribeiro, 2013] along the same lines of the work on belief bases.
The approach of [Meyer, 2001] is similar to ours in the fact that it “weakens” the formulas that must be removed from the base, thus it is also a pseudo-contraction. However, their purpose is different since they do not take computational costs into account (they define base contraction from theory contraction, using logical closure), whereas it is one of our main concerns in this paper.
The closest proposal to the one described in this paper is the idea of disjunctively closed belief bases, proposed by Hansson [1993], where a single closure is studied, the one we used in Example 3.
To the best of our knowledge, [Ribeiro and Wassermann, 2008] was the first proposal where general alternative consequence operations are used only to extend the set of formulas being considered on contraction. The present work follows the line of [Ribeiro and Wassermann, 2008] (even borrowing the Cn notation), but with a different focus. While the idea there was to study forms of recovery, here we are interested in characterizing partial meet operations where the initial belief state is closed under some subclassical consequence operator. 7
In this paper, we have proposed an operation of pseudocontraction, denoted by . We have provided a characterization of this operation in terms of postulates which were adapted from the classical ones to use subclassical operators of consequence, which we denote by Cn .
One of the drawbacks of the construction of is that it satisfies enforced closure , i.e., the result of contraction is always closed under Cn , causing to violate vacuity.
We have found a way to partially circumvent the problem by defining the 0 operator. We have also noted that it would be worthwhile that the operator could satisfy the postulate of core-addition, that avoid needless inclusions. Finally, we conclude that these two flaws would be possibly amended by the use of the pseudo-contractions proposed in [Ribeiro and Wassermann, 2008].
Despite these problems, we have shown some practical examples of use of this operator in which it does better than the direct application of partial meet contraction for bases. The practical usefulness of this operator is limited on isolation, but the importance of the study of its properties can be better understood in the context of the pseudo-contraction operators suggested in [Ribeiro and Wassermann, 2008].
Future work involves exploring the use of different Cn to model real problems encountered in reasoning with ontologies and with Horn theories.
Proof of Theorem 8:
Construction-to-postulates: We know that A = T (Cn (A)? ) = Cn (A) , where is the partial meet contraction. We also know that satisfies success, inclusion, relevance and uniformity. So, we have: If Cn (A)
Postulates-to-construction: This part is is almost trivially obtained from the proof of the representation theorem for partial meet contraction for bases, which can be found in [Hansson, 1999].
Let be an operation for A that satisfies success, inclusion , relevance and uniformity . From the last proof and corollary 7 we conclude that also satisfies logical relevance and uniformity. Let be a function such that: If Cn (A)?
= ;, then (Cn (A)? ) = fCn (A)g.
Otherwise (Cn (A)? ) = fX 2 Cn (A)? j A
Xg We need to show that (1) is a well-defined function, (2) is a selection function and (3) T (Cn (A)? ) = A for all .
Part 1: For to be a well-defined function, for all and , if Cn (A)? = Cn (A)? , we must have T (Cn (A)? ) = T (Cn (A)? ). Suppose that Cn (A)? = Cn (A)? . It follows from observation 1.39 in [Hansson, 1999] that any subset of Cn (A) implies if and only if it implies . By uniformity, Cn (A) = Cn (A) . By the definition of we have (Cn (Cn (A))? ) = (Cn (Cn (A))? ). Since Cn is Tarskian, by idempotence, the result follows.
Part 2: For to be a selection function it remains to be proven that if Cn (A)? is not empty, then (Cn (A)? ) is not empty as well. Then, assuming Cn (A)? 6= ;, we know that there is at least one X 2 Cn (A)? , and we must show that at least one of these X contains A . Since Cn (A)? is not empty, 2= Cn(;), and by success, 2= Cn(A ). By inclusion , A Cn (A), then, by the upper bound property [Alchourro´n and Makinson, 1981], there is an A0 such that A A0 and A0 2 Cn (A)? .
since there is no A0 such that 2= Cn(A0), no element is in
We know that Cn (A)? = ;, then T (Cn (A)? ) = Cn (A). We need to show that Cn (A) A . By relevance , we know that Cn (A) n A = ;, then Cn (A) A .
Case 2, 2= Cn(;). Cn (A)? is non-empty and by part 2, (Cn (A)? ) is non-empty as well. Since
A T (Cn (A)? ). We need to show that T (Cn (A)? ) A .
Take " 2= A . If " 2= Cn (A), obviously " 2= T (Cn (A)? ). If " 2 Cn (A) n A , then by relevance there is an A0 such that A A0 Cn (A), 2= Cn(A0) but 2 Cn(A0 [ f"g). It follows from the upper bound property that there is an A00 such that A A00 and A00 2 Cn (A)? . From A A00, 2 Cn(A0 [ ") and " 2 A00 we conclude that 2 Cn(A00), so we must have " 2= A00. By our definition of , A00 2 (Cn (A)? ), and since " 2= A00, we conclude that " 2= T (Cn (A)? ).
Proof of Proposition 10: We know that A = Cn (A) , where is the partial meet contraction. Since partial meet satisfies relative closure [Hansson, 1999],
this we have Cn (A) \ Cn(A ) A . By the inclusion property of Cn (which is Tarskian) and set theory we get A \ Cn(A ) Cn (A) \ Cn(A ).
Proof of Proposition 11: Since Cn is Tarskian, by inclusion, A Cn (A ). We want to show that Cn (A ) A . Suppose by contradiction that
and idempotence of Cn we obtain 2 Cn (A) n A . Relevance guarantees that there is an A0 such that A A0 Cn (A), 2= Cn(A0) but 2 Cn(A0 [ f g).
of Cn, 2 Cn(A0). So, we have Cn(A0) = Cn(A0 [ f g), which is a contradiction.
Proof of Proposition 12: Assume 2= Cn(B).
By inclusion we already have B Cn (B). To finish the proof it is sufficient to prove that Cn (B) n (B ) = ;.
such that B B0 Cn (B) and 2 Cn(B0 [ f g).
Cn (B) Cn(B) and then by monotony and idempotence of Cn we have Cn(B0 [ f g) Cn(B). Since 2= Cn(B) by assumption, we cannot have such .