=Paper=
{{Paper
|id=Vol-1423/paper8
|storemode=property
|title=Between Belief Bases and Belief Sets: Partial Meet Contraction
|pdfUrl=https://ceur-ws.org/Vol-1423/DARe-15_8.pdf
|volume=Vol-1423
|dblpUrl=https://dblp.org/rec/conf/ijcai/SantosRW15
}}
==Between Belief Bases and Belief Sets: Partial Meet Contraction==
https://ceur-ws.org/Vol-1423/DARe-15_8.pdf
Between Belief Bases and Belief Sets: Partial Meet Contraction
Yuri D. Santos and Marcio M. Ribeiro and Renata Wassermann
University of São Paulo - Brazil
yurids@ime.usp.br marciomr@usp.br renata@ime.usp.br
Abstract satisfied). Hence, in belief base contraction there is a dis-
tinction between the sentences in the base and the sentences
In belief revision, the result of a contraction should inferred from the base. Especially in computer science, be-
be a logically closed set (closure) such that the in- lief base revision is very useful since computing the logical
put is not inferred (success). Traditionally, these closure of a set may be hard if possible at all.
two postulates depend on the same consequence Operations in belief bases, however, have some undesirable
operator. properties due to the fact that equivalent sentences may be
The present work investigates the consequences of treated differently. In the present work we explore the conse-
using two different consequence operators for each quences of keeping both closure and success where the conse-
of these desiderata: the classic Cn to compute suc- quence operations in these two postulates do not necessarily
cess and a second weaker operator to compute the coincide. More precisely, we assume that closure is guaran-
closure. We prove a representation theorem and teed only for a weaker consequence operation. This weaker
some other properties for the new contraction. notion of consequence may be easy to compute and at the
same time useful to avoid some undesirable consequences of
1 Introduction belief base operations.
Throughout this paper, we consider the language of classi-
Belief revision is the branch of knowledge representation that
cal propositional logic, closed under the usual boolean con-
deals with the dynamics of epistemic states. In their semi-
nectives.
nal paper [Alchourrón et al., 1985], Alchourrón, Gärdenfors
We call consequence operator a function that takes sets of
and Makinson proposed to represent the epistemic state of an
formulas into sets of formulas. A consequence operator C is
agent as a logically closed set of propositions called belief
Tarskian if and only if it satisfies:
sets. The authors focus on three main epistemic operations
over belief sets: expansion, contraction and revision. Expan- (inclusion) A ⊆ C(A)
sion is the simple addition of a proposition to the epistemic
state, contraction is the removal of a proposition and revision (idempotence) C(A) = C(C(A))
is the consistent addition of a proposition. Each of this oper-
ations is characterized by a set of rationality postulates. (monotonicity) If A ⊆ B then C(A) ⊆ C(B)
Consider, for example, the following postulates for con- Cn denotes the classical consequence operator and ` de-
traction: notes the associated relation: A ` α stands for α ∈ Cn(A).
(closure) K − α = Cn(K − α) Lowercase Latin letters (p, q, r) stand for atoms, lower-
case Greek letters (α, β) stand for formulas, uppercase Latin
(success) If α ∈
/ Cn(∅), then α ∈
/ Cn(K − α) letters (A, B, K) stand for sets of formulas.
The rest of the paper is structured as follows. A brief
Closure guarantees the resulting epistemic state to be rep-
overview of classical belief revision is given in Section 2.
resented as a logically closed set of propositions, i.e., the re-
Section 3 presents pseudo-contractions, the kind of operation
sult of contracting a belief set is also a belief set. Success
we are exploring in this paper. In Section 4, we describe our
guarantees that the removed proposition α is no longer im-
proposal, depicting it with examples in Section 5. Section 6
plied by the new belief set, unless it is a tautology.
highlights some previous works that are related to ours. We
Hansson in [Hansson, 1992a] suggests a generalization of
delineate our conclusions in Section 7. Proofs for theorems
the AGM framework where the epistemic state is not nec-
and propositions are found in the Appendix.
essarily closed under logical consequences. Although in his
work epistemic states are represented as arbitrary sets of sen-
tences called belief bases (i.e. closure is not necessarily sat- 2 AGM Paradigm
isfied), the removal of a sentence in contraction is still eval- In the AGM paradigm [Alchourrón et al., 1985], belief states
uated against the closure of the belief base (i.e. success is are typically represented by sets of sentences closed under
logical consequence, the so-called belief sets. Three change (uniformity) If for all B 0 ⊆ B, α ∈ Cn(B 0 ) if and only if
operations were initially defined: expansion, contraction and β ∈ Cn(B 0 ), then B − α = B − β
revision. Expansion is the simple addition of a new sentence,
Furthermore, we have the following representation theo-
followed by logically closing the resulting set, i.e, K + α =
rem:
Cn(K ∪ {α}). In the case of contraction, we have a class
of operations, all delimited by rationality postulates that they Theorem 4 [Hansson, 1992b] An operation is a partial meet
should satisfy. Let K be a belief set and α and β be formulas. contraction over belief bases if and only if it satisfies the pos-
The original AGM basic postulates for contraction are: tulates of success, inclusion, relevance and uniformity.
(closure) K − α = Cn(K − α) For logically closed sets, both characterizations are equiv-
alent (this is true for classical logics, for other cases, cf.
(success) If α 6∈ Cn(∅), then α 6∈ K − α [Ribeiro et al., 2013]) in the sense that all initial AGM pos-
tulates are consequence of the postulates for bases [Hansson,
(inclusion) K − α ⊆ K 1999].
(vacuity) If α 6∈ K, then K − α = K 3 Pseudo-Contractions
Contraction operators on belief sets can be generated from
(recovery) K ⊆ (K − α) + α operations on belief bases. As an example, one can define a
contraction operator for belief sets as K ÷ α = Cn(B − α),
(extensionality) If Cn(α) = Cn(β), then K − α = K − β where K = Cn(B) and − is a base contraction operator. If
− is a partial meet base contraction, ÷ satisfies five of the six
Note that in the presence of closure, we can use α 6∈ K −α AGM postulates, but not recovery.
or α 6∈ Cn(K − α) interchangeably in the success postulate. In [Hansson, 1989] a weakening of the inclusion postulate
AGM revision is usually defined from contraction and ex- was proposed, called logical inclusion.
pansion by means of the Levi identity:
(logical inclusion) Cn(B − α) ⊆ Cn(B)
K ∗ α = (K − ¬α) + α Hansson has suggested to call operations that satisfy suc-
Therefore, in this paper we will focus on contraction. cess and logical inclusion pseudo-contractions.
Besides defining rationality postulates for contraction, Al- Nebel has proposed a pseudo-contraction for bases that
chourrón et al.[1985] have also proposed a construction for generates a contraction that satisfies all the six AGM postu-
a contraction operation. Partial meet contraction is based on lates [Nebel, 1989].
the notion of a remainder set, the set of all maximal subsets
V
Definition 5 Let B be the conjunction of all elements of
that do not imply the element that is to be contracted. For- B. Nebel’s pseudo-contraction for the set B is the operator
mally: − such that for all sentences α:
Definition 1 Let B be a set and α a formula. The remainder
set B⊥α is such that X ∈ B⊥α if and only if:
B if α ∈ Cn(∅)
B−α= T V
• X⊆B γ(B⊥α) ∪ {α → B} otherwise
• X0α Although the belief set operation generated from Nebel’s
• For all sets Y , if X ⊂ Y ⊆ B, then Y ` α pseudo-contraction satisfies all the AGM postulates, it adds
unnecessary information to the base. As shown in [Ribeiro
Definition 2 A function γ is a selection function for the set V 0
and Wassermann, 2008], it suffices to add {α → B },
B if and only if:
where B 0 = B\ γ(B⊥α). As already noted in [Ribeiro and
T
• If B⊥α 6= ∅ then ∅ =
6 γ(B⊥α) ⊆ B⊥α Wassermann, 2008], there is no other intuition behind Nebel’s
• Otherwise, γ(B⊥α) = {B} operation than maintaining recovery, a postulate which has
been deemed as polemic already since the 80’s [Makinson,
Definition 3 Let γ be a selection function for a set of sen- 1987].
tences B. The partialTmeet contraction of B by a sentence α In this work we want to further explore the possibility of
is given by B − α = γ(B⊥α). working with belief bases with logical inclusion, allowing for
The partial meet operation previously defined can be ap- some syntax independence without having to resort to belief
plied directly over belief bases, in such a way that it satisfies sets.
the following postulates:
(success) If α ∈
/ Cn(∅), then α ∈
/ Cn(B − α) 4 Between Belief Sets and Belief Bases
As stated earlier, the direct application of partial meet con-
(inclusion) B − α ⊆ B traction over closed belief sets and over belief bases creates
problems of practical (computational infeasibility) and the-
(relevance) If β ∈ B \ (B − α), then there is a B 0 such oretical (syntax dependence) nature, respectively. One of
that B − α ⊆ B 0 ⊆ B, α ∈
/ Cn(B 0 ), but α ∈ Cn(B 0 ∪ {β}) the aims of this study is to assess the effects of doing the
traditional partial meet contraction on belief bases closed With a proof that is very similar to that of the representa-
by a consequence operation that is between the classical tion theorem for partial meet contraction on bases (which can
consequence operator and the identity (i.e., the base itself). be found in [Hansson, 1999]), we can prove the following
Hence, we will assume that this operator (here called Cn∗ ) is representation theorem:
Tarskian.
We will study the properties of the application of the par- Theorem 8 Provided that Cn∗ is Tarskian, subclassical and
tial meet contraction over a set closed under Cn∗ , i.e., the compact, an operation is a −∗ operator if and only if it satis-
operator defined as: fies success, inclusion∗ , relevance∗ and uniformity∗ .
Definition 6 Let B be a set of sentences, Cn∗ a function from From this theorem and the previous corollary, it also fol-
sets of sentences to sets of sentences and γ a selection func- lows:
tion for Cn∗ (B). The operator −∗ is such that, for all sen- Corollary 9 If Cn∗ is Tarskian and satisfies subclassicality,
tences α: then −∗ satisfies success, logical inclusion, logical relevance
\ and uniformity.
B −∗ α = γ(Cn∗ (B)⊥α)
It is interesting that we have here a set of postulates that
Notice that B −∗ α = γ(Cn∗ (B)⊥α) = Cn∗ (B) −γ α,
T
are independent from Cn∗ . Nonetheless, these postulates do
where −γ is the partial meet contraction. Since −γ satisfies not characterize the operation, and are in general weaker than
the postulates of success, inclusion, relevance and unifor- the postulates with ∗ . Hansson’s logical inclusion postulate
mity, it follows directly (details in the Appendix) that −∗ sat- is quite reasonable for base operations, as it brings syntactic
isfies success and: independence, although with inclusion∗ we already have a
(inclusion∗ ) B − α ⊆ Cn∗ (B) degree of independence, and with better preservation of the
original set (since Cn∗ is subclassical), and, depending on
(relevance∗ ) If β ∈ Cn∗ (B) \ (B − α), then there is a the chosen Cn∗ , we avoid the complexity problem we have
B such that B − α ⊆ B 0 ⊆ Cn∗ (B), α ∈
0
/ Cn(B 0 ), but with the closure of Cn.
0 Another desirable property in rational contraction opera-
α ∈ Cn(B ∪ {β})
tions is relative closure [Hansson, 1991].
(uniformity∗ ) If for all B 0 ⊆ Cn∗ (B), α ∈ Cn(B 0 ) if and
only if β ∈ Cn(B 0 ), then B − α = B − β (relative closure) B ∩ Cn(B − α) ⊆ B − α
For several applications it is important that the construction This property is a consequence of the postulate of rele-
satisfies the original success postulate, and not only a starred vance, which −∗ does not satisfy. Nevertheless, relative clo-
version of it: sure is satisfied, given the condition that Cn∗ is Tarskian.
(success∗ ) If α ∈ / Cn∗ (B − α)
/ Cn(∅), then α ∈ Proposition 10 If Cn∗ is Tarskian, the −∗ operator satisfies
relative closure.
We want that the sentence to be contracted ceases to be
logically (classically) implied by the resulting set after the Kernel contraction [Hansson, 1994] is an alternative con-
contraction. In this case, the role of the logic Cn∗ is just to struction for contraction, which instead of considering maxi-
give a degree of syntactic independence to the operation. mal sets not implying a given formula as in partial meet con-
As our purpose here is to make the contraction on a set traction, considers minimal sets implying it. It works by find-
closed by a Cn∗ that does not generate as many consequences ing the minimal sets (called α-kernels) that imply the element
as the classic Cn, the following property is desirable: α being contracted and then selecting at least one element of
each α-kernel to remove from the belief base. The operation
(subclassicality) Cn∗ (A) ⊆ Cn(A) is characterized by the same postulates as partial meet con-
Clearly, if Cn∗ (A) = A (identity), we have that −∗ is the traction on bases, except for relevance, which is weakened to
usual operation of partial meet contraction on bases. Simi- core-retainment:
larly, for all Tarskian Cn∗ that also satisfies subclassicality,
applying −∗ to belief sets (i.e., K = Cn∗ (K) = Cn(K)) (core-retainment) If β ∈ B \ (B − α), then there is a B 0
yields the usual AGM partial meet contraction on belief sets. such that B 0 ⊆ B, α ∈
/ Cn(B 0 ), but α ∈ Cn(B 0 ∪ {β})
Following the same idea as logical inclusion, in [Ribeiro Kernel contraction may have erratic behaviour due to its
and Wassermann, 2008] we have a weakening of relevance: non-satisfaction of relevance [Hansson, 1999]. For instance,
(logical relevance) If β ∈ B \ (B − α), then there is a consider the logically independent sentences p and q, and let
B 0 such that B − α ⊆ B 0 ⊆ Cn(B), α ∈ / Cn(B 0 ), but A = {p, p ∨ q, p ↔ q}. The kernel contraction A − (p ∧ q) =
0
α ∈ Cn(B ∪ {β}) {p} is possible, whereas partial meet contraction cannot have
this outcome. As observed by Hansson, it is not sensible to
The next corollary follows: give up p ∨ q, since p was kept.
Corollary 7 If Cn∗ is Tarskian and satisfies subclassical- Would the weakening of relevance to relevance∗ or logi-
ity, then an operation that satisfies success, inclusion∗ , cal relevance be enough so as to make these behaviours show
relevance∗ and uniformity∗ also satisfies logical inclusion, up in the −∗ operator? Kernel contraction does not satisfy
logical relevance and uniformity. any of these last two postulates. Furthermore, Hansson had
already noticed that the lack of relative closure also con- Any operator satisfying inclusion
V will satisfy this postulate
tributes to these unnecessary removals in contraction. The trivially. If we break {α → B} into the set of sentences
operator −∗ , as shown above, satisfies relative closure. {α → β | β ∈ B}, Nebel’s pseudo-contraction will not sat-
A property of our pseudo-contraction is enforced closure∗ . isfy core-addition. Clearly the −∗ operator does not satisfy
it also (neither does −0∗ ), and it does not satisfy vacuity as
(enforced closure∗ ) B − α = Cn∗ (B − α) well. In the effort to fix these two problems, the operations of
general partial-meet pseudo-contraction and ∆-partial-meet
Proposition 11 If Cn∗ is Tarskian and satisfies subclassical- pseudo-contraction, proposed in [Ribeiro and Wassermann,
ity, an operator that satisfies inclusion∗ and relevance∗ also 2008], seem to be viable solutions.
satisfies enforced closure∗ .
Whenever A ⊂ Cn∗ (A), this postulate will imply that 5 Examples
vacuity is not satisfied, which is an essential postulate in the In this section we are going to show some concrete examples
point of view of rational contractions (that respect the princi- of Cn∗ functions that can be useful in the solution of practi-
ple of minimal change). It has as effect that the belief base cal problems. The first example we mention is the Cleopatra
will always end up closed by Cn∗ after the contraction, even example, adapted from [Ribeiro and Wassermann, 2008].
though the original base was not closed.
Example 1 Consider a language with three propositional
(vacuity) If α ∈
/ Cn(B), then B − α = B letters, p, q and r and a belief base B = {p ∧ q}, where p
stands for Cleopatra had a son and q, Cleopatra had a daugh-
Nevertheless, our construction does satisfy a weaker form
ter. If we want to contract by p, applying a partial meet con-
of vacuity:
traction produces B − p = ∅. This is not always the expected
(vacuity∗ ) If α ∈
/ Cn(B), then B − α = Cn∗ (B) 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
Proposition 12 If Cn∗ is Tarskian and satisfies subclassical- daughter.
ity, an operator that satisfies inclusion∗ and relevance∗ also With the classic partial meet construction for bases we
satisfies vacuity∗ . would have B⊥p = {∅}, so the selection function needs to
Corollary 13 If Cn∗ is Tarskian and satisfies subclassicality, choose {∅}, causing the overall contraction process to pro-
then the operator −∗ satisfies enforced closure∗ and vacuity∗ . duce ∅ as final result.
On the other hand, if we take B to represent the belief set
A simple way to restore vacuity is to redefine the −∗ op- K = Cn(B), then K contains both p and q and the belief that
erator in the following manner: Cleopatra had a daughter (q) may survive the contraction, i.e.,
Definition 14 Let B be a set of sentences, Cn∗ a function we may have q ∈ K − p. But then we would also have q ∨ r,
from sets of sentences to sets of sentences and γ a selection r → q and many other irrelevant formulas in the resulting set,
function for Cn∗ (B). The operator −0∗ is such that, for all since it is closed under Cn.
sentence α: Let us consider an intermediate consequence operator:
Cn∗1 (A) = {α | α ∈ A or for any formulas β, δ,
B if α ∈
/ Cn(B) α ∧ β ∈ A or β ∧ α ∈ A or β ∧ α ∧ δ ∈ A}
B −0∗ α =
γ(Cn∗ (B)⊥α) otherwise
T
We can use Cn∗1 with the −∗ operator to solve the problem
of the preceding example. In this case, we have Cn∗1 (B) =
Observation 15 The −0∗ operator satisfies success, {p ∧ q, p, q} and Cn∗1 (B)⊥p = {{q}}, hence the selection
inclusion∗ , uniformity∗ and vacuity. If Cn∗ is Tarskian function would choose the whole remainder set, {{q}}, and,
and subclassical, −0∗ also satisfies logical inclusion, accordingly, B −∗ p = {q}.
uniformity and relative closure. Although the usefulness of this consequence operation is
The proof of the observation above is not given, but can be dubious, its use already brings better results than the typical
trivially obtained from theorem 8, corollary 7 and proposition base contraction in some cases, as in the former example.
10. Note that relevance∗ and logical relevance were lost. Example 2 Suppose I believe that the town of Juazeiro do
Although we have attained vacuity, we have only partly Norte is located in the state of Pernambuco (j → p) and that
gotten rid of enforced closure∗ (just when α ∈ / Cn(B)). the state of Pernambuco is located in Brazil (p → b). Speak-
If on one hand logical inclusion seems to make more sense ing with a colleague, I found that this town is not located in
than inclusion for base contractions, by allowing some syn- his state (Pernambuco), that is, I contract j → p from my
tactic independence, effects such as enforced closure∗ illus- base. The outcome is B − (j → p) = {p → b}. So, I no
trate the need to refrain from careless additions of sentences longer know whether Juazeiro do Norte is located in Brazil.
in the contraction. Here we should mention the postulate of
core-addition [Ribeiro and Wassermann, 2008]: In this example, as well as in the previous one, one can
blame the poor codification of the belief base for the prob-
(core-addition) If β ∈ (B − α) \ B, then there is a β 0 ∈ lems. The knowledge that Juazeiro do Norte is located in
B \ (B − α) and a B 0 ⊆ B − α such that α → β 0 ∈
/ Cn(B 0 ) Brazil, if obvious, perhaps would be individually justified,
0 0
but α → β ∈ Cn(B ∪ {β}). and so it would deserve to be explicitly in the base. At this
point the syntactic independence dilemma reappears. In some 6 Related Work
cases we want to have it, but without having to generate in- There have been several attempts in the literature to study
finitely many derivative sentences with little utility. AGM-like contraction operations based on different conse-
However, when working with ontologies, for instance, it is quence operations.
possible that the user does not want to make explicit every Concerning belief bases, Hansson and Wassermann 2002
possible relationship, trusting the transitivity of some proper- have shown that the original representation results for char-
ties (i.e., he would be more concerned with his ontology on acterizing partial meet contraction only depended on the un-
the knowledge level than on the syntactic level). One may derlying logic being compact and monotonic. The main dif-
also want a knowledge base with little redundancy. ference from what we are proposing in this paper is that the
Again, neither the belief base nor the belief set approach underlying consequence operator C is used for computing the
would give us the desired result. remainder sets and everywhere in the postulates. So, for ex-
Returning to the foregoing example, we could use a Cn∗2 ample, if we take as underlying logic one for approximate
that adds to the base the transitive closure of →: reasoning, as suggested in [Chopra et al., 2001], the remain-
Cn∗2 (A) = A ∪ {α1 → α2 | for some β, ders will be different than the ones we use for our −∗ opera-
α1 → β, β → α2 ∈ A}. tion. If the approximation is done from below (cf. [Schaerf
and Cadoli, 1995]), then each element of the approximate re-
In that case, we would have Cn∗2 (B) = B ∪ {j → b}, mainder will contain an element of the classical remainder.
what results in Cn∗2 (B)⊥(j → p) = {{p → b, j → b}}. Success will also be computed in terms of the chosen under-
As in the last example, the selection function must choose the lying consequence operation, so the outcome of the contrac-
only member of the remainder set, therefore B −∗ (j → p) = tion by α may still classically imply α.
{p → b, j → b}. It is interesting to note that we could also More recently, there has been a series of papers consider-
use here Cn∗20 (B) to be the set of all Horn consequences of ing Horn Contraction [Delgrande, 2008; Booth et al., 2011;
B. Delgrande and Wassermann, 2013], which again, replace all
The following example was adapted from [Hansson, 1993]. classical reasoning by Horn reasoning. Contraction of belief
sets has also been studied for non-classical logics [Ribeiro et
Example 3 Suppose I believe, for good and independent rea- al., 2013; Ribeiro, 2013] along the same lines of the work on
sons, that Andy is son of the mayor (a) and Bob is son of the belief bases.
mayor (b). Then I hear the mayor say: “I certainly have The approach of [Meyer, 2001] is similar to ours in the fact
nothing against our youth studying abroad. My only son did that it “weakens” the formulas that must be removed from the
it for three years”. I then have to retract a ∧ b from my base base, thus it is also a pseudo-contraction. However, their pur-
B = {a, b}. But it is reasonable to retain a belief that ei- pose is different since they do not take computational costs
ther Andy or Bob is the son of the mayor, i.e., the result of the into account (they define base contraction from theory con-
contraction should be {a ∨ b}. traction, using logical closure), whereas it is one of our main
The remainder set for the operation above is B⊥(a ∧ b) = concerns in this paper.
{{a}, {b}}. So, the resulting partial meet contraction is either The closest proposal to the one described in this paper
{a}, {b} or ∅, the first two being odd since we do not seem to is the idea of disjunctively closed belief bases, proposed by
have reasons to prefer a over b or vice-versa. Hansson [1993], where a single closure is studied, the one we
In the same paper where he presented the example above, used in Example 3.
Hansson has done an extensive study of partial meet contrac- To the best of our knowledge, [Ribeiro and Wassermann,
tion on disjunctively closed bases. If we define Cn∗3 (A) as 2008] was the first proposal where general alternative conse-
the disjunctive closure of A, as defined by Hansson, that is, quence operations are used only to extend the set of formulas
Cn∗3 (A) is the set of sentences that are either elements of A being considered on contraction. The present work follows
or disjunctions of elements of A, we can manage to get the the line of [Ribeiro and Wassermann, 2008] (even borrowing
desired result. the Cn∗ notation), but with a different focus. While the idea
there was to study forms of recovery, here we are interested
Cn∗3 (A) = A ∪ { αi |αi ∈ A}
W
in characterizing partial meet operations where the initial be-
lief state is closed under some subclassical consequence op-
We have Cn∗3 (B) = {a, b, a ∨ b}. Then, the remainder erator.
set is Cn∗3 (B)⊥(a ∧ b) = {{a, a ∨ b}, {b, a ∨ b}}, and so
the selection function may choose both sets, producing the
expected result in the lack of evidence for a or b: B −∗ (a ∧ 7 Conclusion
b) = {a ∨ b}. In this paper, we have proposed an operation of pseudo-
Consider now the case where the language has three propo- contraction, denoted by −∗ . We have provided a character-
sitional letters (a, b, and c). If we take the belief set K = ization of this operation in terms of postulates which were
Cn(B), we have that K contains a ∨ c and b ∨ c. It is adapted from the classical ones to use subclassical operators
not hard to see that there are two remainder sets containing of consequence, which we denote by Cn∗ .
{a, a ∨ b, a ∨ c, b ∨ c}, {b, a ∨ b, a ∨ c, b ∨ c} and hence, these One of the drawbacks of the construction of −∗ is that it
two formulas may survive contraction, even if the original set satisfies enforced closure∗ , i.e., the result of contraction is
did not mention c. always closed under Cn∗ , causing −∗ to violate vacuity.
We have found a way to partially circumvent the problem Part 2: For γ to be a selection function it remains to be
by defining the −0∗ operator. We have also noted that it would proven that if Cn∗ (A)⊥α is not empty, then γ(Cn∗ (A)⊥α)
be worthwhile that the operator could satisfy the postulate is not empty as well. Then, assuming Cn∗ (A)⊥α 6= ∅, we
of core-addition, that avoid needless inclusions. Finally, we know that there is at least one X ∈ Cn∗ (A)⊥α, and we must
conclude that these two flaws would be possibly amended by show that at least one of these X contains A −∗ α. Since
the use of the pseudo-contractions proposed in [Ribeiro and Cn∗ (A)⊥α is not empty, α ∈ / Cn(∅), and by success, α ∈ /
Wassermann, 2008]. Cn(A −∗ α). By inclusion∗ , A −∗ α ⊆ Cn∗ (A), then, by
Despite these problems, we have shown some practical ex- the upper bound property [Alchourrón and Makinson, 1981],
amples of use of this operator in which it does better than the there is an A0 such that A −∗ α ⊆ A0 and A0 ∈ Cn∗ (A)⊥α.
direct application of partial meet contraction for bases. The By the construction of γ, γ(Cn∗ (A)⊥α) is non-empty.
practical usefulness of this operator is limited on isolation, Part 3: Case 1, α ∈ Cn(∅). Then, by logical relevance,
but the importance of the study of its properties can be better since there is no A0 such that α ∈ / Cn(A0 ), no element is in
understood in the context of the pseudo-contraction operators A \ A −∗ α, then, using inclusion∗ , A ⊆TA −∗ α ⊆ Cn∗ (A).
suggested in [Ribeiro and Wassermann, 2008]. We know that Cn∗ (A)⊥α = ∅, then γ(Cn∗ (A)⊥α) =
Future work involves exploring the use of different Cn∗ to Cn∗ (A). We need to show that Cn∗ (A) ⊆ A −∗ α. By
model real problems encountered in reasoning with ontolo- relevance∗ , we know that Cn∗ (A) \ A −∗ α = ∅, then
gies and with Horn theories. Cn∗ (A) ⊆ A −∗ α.
Case 2, α ∈ / Cn(∅). Cn∗ (A)⊥α is non-empty and
Appendix by part 2, γ(Cn∗ (A)⊥α) is non-empty as well. Since
A −∗ α is a Tsubset of all elements of γ(Cn∗ (A)⊥α),
Proof of Theorem 8: γ(Cn∗ (A)⊥α). We need to show that
We know that A −∗ α = T −∗ α∗ ⊆
A
T Construction-to-postulates: γ(Cn (A)⊥α) ⊆ A −∗ α.
γ(Cn∗ (A)⊥α) = Cn∗ (A) −γ α, where −γ is the par- / Cn∗ (A), obviously ε ∈
tial meet contraction. We also know that −γ satisfies success, T Take ∗ε ∈ / A −∗ α. If ε ∈ /
γ(Cn (A)⊥α). If ε ∈ Cn∗ (A) \ A −∗ α, then by
inclusion, relevance and uniformity. So, we have: relevance∗ there is an A0 such that A −∗ α ⊆ A0 ⊆ Cn∗ (A),
• If α ∈ / Cn(Cn∗ (A) −γ α)
/ Cn(∅), then α ∈ α ∈ / Cn(A0 ) but α ∈ Cn(A0 ∪ {ε}). It follows from the
• Cn∗ (A) −γ α ⊆ Cn∗ (A) upper bound property that there is an A00 such that A ⊆ A00
and A00 ∈ Cn∗ (A)⊥α. From A ⊆ A00 , α ∈ Cn(A0 ∪ ε)
• If β ∈ Cn∗ (A)\(Cn∗ (A)−γ α), then there is a B 0 such and ε ∈ A00 we conclude that α ∈ Cn(A00 ), so we must have
that Cn∗ (A) −γ α ⊆ B 0 ⊆ Cn∗ (A), α ∈
/ Cn(B 0 ), but ε∈ / A00 . By our definition of γ, A00T∈ γ(Cn∗ (A)⊥α), and
0
α ∈ Cn(B ∪ {β}). since ε ∈/ A00 , we conclude that ε ∈
/ γ(Cn∗ (A)⊥α).
• If for all B 0 ⊆ Cn∗ (A), α ∈ Cn(B 0 ) if and only if Proof of Proposition 10: We know that A −∗ α =
β ∈ Cn(B 0 ), then Cn∗ (A) −γ α = Cn∗ (A) −γ β. Cn∗ (A) −γ α, where −γ is the partial meet contraction.
Since Cn∗ (A) −γ α = A −∗ α, we are done. Since partial meet satisfies relative closure [Hansson, 1999],
Cn∗ (A)∩Cn(Cn∗ (A)−γ α) ⊆ Cn∗ (A)−γ α is valid. From
Postulates-to-construction: This part is is almost trivially
this we have Cn∗ (A) ∩ Cn(A −∗ α) ⊆ A −∗ α. By the inclu-
obtained from the proof of the representation theorem for par-
sion property of Cn∗ (which is Tarskian) and set theory we
tial meet contraction for bases, which can be found in [Hans-
get A ∩ Cn(A −∗ α) ⊆ Cn∗ (A) ∩ Cn(A −∗ α).
son, 1999].
Let −∗ be an operation for A that satisfies success, Proof of Proposition 11: Since Cn∗ is Tarskian, by in-
inclusion∗ , relevance∗ and uniformity∗ . From the last proof clusion, A − α ⊆ Cn∗ (A − α). We want to show that
and corollary 7 we conclude that −∗ also satisfies logical rel- Cn∗ (A − α) ⊆ A − α. Suppose by contradiction that
evance and uniformity. Let γ be a function such that: β ∈ Cn∗ (A − α) \ (A − α). From inclusion∗ , monotonicity
and idempotence of Cn∗ we obtain β ∈ Cn∗ (A) \ A − α.
• If Cn∗ (A)⊥α = ∅, then γ(Cn∗ (A)⊥α) = {Cn∗ (A)}. Relevance∗ guarantees that there is an A0 such that A − α ⊆
• Otherwise γ(Cn∗ (A)⊥α) = {X ∈ Cn∗ (A)⊥α | A −∗ A0 ⊆ Cn∗ (A), α ∈ / Cn(A0 ) but α ∈ Cn(A0 ∪ {β}).
α ⊆ X} By subclassicality of Cn∗ and β ∈ Cn∗ (A − α) we have
We need to show that (1) γ isTa well-defined function, (2) β ∈ Cn(A−α). By A−α ⊆ A0 and by the inclusion property
γ is a selection function and (3) γ(Cn∗ (A)⊥α) = A −∗ α of Cn, β ∈ Cn(A0 ). So, we have Cn(A0 ) = Cn(A0 ∪ {β}),
for all α. which is a contradiction.
Part 1: For γ to be a well-defined function, for all Proof of Proposition 12: Assume α ∈ / Cn(B).
α
T and β, if Cn∗ (A)⊥α T = Cn
∗
(A)⊥β, we must have By inclusion∗ we already have B −α ⊆ Cn∗ (B). To finish
∗ ∗
γ(Cn (A)⊥α) = γ(Cn (A)⊥β). Suppose that the proof it is sufficient to prove that Cn∗ (B) \ (B − α) = ∅.
Cn∗ (A)⊥α = Cn∗ (A)⊥β. It follows from observation By relevance∗ , if β ∈ Cn∗ (B) \ (B − α), then there is a B 0
1.39 in [Hansson, 1999] that any subset of Cn∗ (A) implies such that B − α ⊆ B 0 ⊆ Cn∗ (B) and α ∈ Cn(B 0 ∪ {β}).
α if and only if it implies β. By uniformity, Cn∗ (A) −∗ From this and subclassicality of Cn∗ we get B 0 ∪ {β} ⊆
α = Cn∗ (A) −∗ β. By the definition of γ we have Cn∗ (B) ⊆ Cn(B) and then by monotony and idempotence
γ(Cn∗ (Cn∗ (A))⊥α) = γ(Cn∗ (Cn∗ (A))⊥β). Since Cn∗ of Cn we have Cn(B 0 ∪ {β}) ⊆ Cn(B). Since α ∈ / Cn(B)
is Tarskian, by idempotence, the result follows. by assumption, we cannot have such α.
References [Nebel, 1989] B. Nebel. A knowledge level analysis of belief
[Alchourrón and Makinson, 1981] Carlos E. Alchourrón and revision. In Proceedings of the 1st International Confer-
ence of Principles of Knowledge Representation and Rea-
D. Makinson. New studies in Deontic Logic, chapter Hier-
soning, 1989.
arquies of regulation and their logic, pages 125–148. Rei-
del Publishing Company, 1981. [Ribeiro and Wassermann, 2008] Márcio Moretto Ribeiro
and Renata Wassermann. Degrees of recovery and inclu-
[Alchourrón et al., 1985] Carlos Alchourrón, Peter sion in belief base dynamics. Non-Monotonic Reasoning,
Gärdenfors, and David Makinson. On the logic of 2008.
theory change. Journal of Symbolic Logic, 50(2):510–
530, 1985. [Ribeiro et al., 2013] Márcio Moretto Ribeiro, Renata
Wassermann, Giorgos Flouris, and Grigoris Antoniou.
[Booth et al., 2011] Richard Booth, Thomas Andreas Meyer, Minimal change: Relevance and recovery revisited.
Ivan José Varzinczak, and Renata Wassermann. On the Journal of Artificial Intelligence, 201:59–80, 2013.
link between partial meet, kernel, and infra contraction and
its application to horn logic. J. Artif. Intell. Res. (JAIR), [Ribeiro, 2013] Márcio Moretto Ribeiro. Belief revision in
42:31–53, 2011. non-classical logics. Springer, 2013.
[Chopra et al., 2001] Samir Chopra, Rohit Parikh, and Re- [Schaerf and Cadoli, 1995] Marco Schaerf and Marco
nata Wassermann. Approximate belief revision. Logic Cadoli. Tractable reasoning via approximation. Artificial
Journal of the IGPL, 9(6):755–768, 2001. Intelligence, 74(2):249–310, 1995.
[Delgrande and Wassermann, 2013] James P. Delgrande and
Renata Wassermann. Horn clause contraction functions. J.
Artif. Intell. Res. (JAIR), 48:475–511, 2013.
[Delgrande, 2008] James P. Delgrande. Horn clause belief
change: Contraction functions. In Gerhard Brewka and
Jérôme Lang, editors, Principles of Knowledge Represen-
tation and Reasoning (KR2008), pages 156–165. AAAI
Press, 2008.
[Hansson and Wassermann, 2002] Sven Ove Hansson and
Renata Wassermann. Local change. Studia Logica,
70(1):49–76, 2002.
[Hansson, 1989] Sven Ove Hansson. New operators for the-
ory change. Theoria, 1989.
[Hansson, 1991] Sven Ove Hansson. Belief contraction
without recovery. Studia Logica, 50(2):251–260, 1991.
[Hansson, 1992a] Sven Ove Hansson. A dyadic represen-
tation of belief. In Peter Gärdenfors, editor, Belief Revi-
sion, volume 29 of Cambridge Tracts in Theoretical Com-
puter Science, pages 89–121. Cambridge University Press,
1992.
[Hansson, 1992b] Sven Ove Hansson. Reversing the Levi
identity. Journal of Philosophical Logic, 22:637–639,
1992.
[Hansson, 1993] Sven Ove Hansson. Changes of disjunc-
tively closed bases. Journal of Logic, Language and In-
formation, 1993.
[Hansson, 1994] Sven Ove Hansson. Kernel contraction.
Journal of Symbolic Logic, 1994.
[Hansson, 1999] Sven Ove Hansson. A Textbook of Belief
Dynamics. Kluwer Academic, 1999.
[Makinson, 1987] David Makinson. On the status of the pos-
tulate of recovery in the logic of theory change. Journal of
Philosophical Logic, 16:383–394, 1987.
[Meyer, 2001] Thomas Meyer. Basic infobase change. Stu-
dia Logica, 2001.