Belief Change in a Preferential Non-monotonic Framework

1 Introduction

Both belief change and non-monotonic reasoning frameworks provide mechanisms for dealing with conflicting information. For example, suppose I know that vertebrate red blood cells have a nucleus (v � n), that mammalian red blood cells are vertebrate red blood cells (m � v), but that mammalian red blood cells don't have a nucleus (m� n). The existence of mammalian red blood cells (m) then renders my knowledge base inconsistent. Belief change operators modify the existing knowledge base to make it consistent again, while nonmonotonic reasoning typically resolves the issue by introducing a notion of defeasibility-for example, by being able to state that vertebrate red blood cells usually have a nucleus.

In this paper our aim is to integrate the two frameworks by studying belief change in a non-monotonic setting. This approach has not received much attention thus far, mostly for two reasons. Firstly, the standard approaches to belief change usually assume an underlying Tarskian consequence relation which is explicitly monotonic [Alchourr´on et al., 1985]. Secondly, at a first glance belief change seems to be superfluous Thomas Meyer CAIR-CSIR University of Cape Town South Africa tmeyer@cs.uct.ac.za in non-monotonic settings-a revision operator can simply be replaced with expansion, with the non-monotonic machinery then ensuring consistency of some kind. What this simplistic view does not take into account is that non-monotonic frameworks contain a mix of defeasible and classical (nondefeasible) information. In our example above, for instance, the statement that mammalian red blood cells are vertebrate red blood cells should probably not be defeasible, while the statement about vertebrate red blood cells having a nucleus probably should be. The challenge thus becomes one of defining belief change for the monotonic part of the formalism, while simultaneously ensuring that the non-monotonic part remains well-behaved.

In addition to consistency preservation we also consider belief change for the preservation of a restricted version of coherence, as it is intended in the field of logic-based ontologies, that is, that every class that has been introduced in the language can in principle be populated [Qi and Hunter, 2007]. In our example above the (non-defeasible) statements tv � n,m � v,m � nu cause the knowledge base to be incoherent w.r.t. m (there cannot be any mammalian red blood cells), but the knowledge base only becomes inconsistent when m is added. For our purposes here it is sufficient to note that, in a propositional setting, the incoherence of a knowledge base w.r.t. an atom (or any propositional formula A, for that matter), corresponds to the statement A being a consequence of our knowledge base.

We focus on belief change in the preferential approach to non-monotonic reasoning developed by Kraus, Lehmann and Magidor [1990] in which defeasible conditionals of the form C |�D are added to the language of propositional logic (with C and D being classical propositional formulas). In this enriched language the information about vertebrate blood cells usually having a nucleus could be expressed as v |�n.

In Section 2 we briefly summarise the AGM framework and preferential reasoning. Section 3 describes the nonmonotonic framework we consider and introduces the notion of a monotonic core. Section 4 analyses a contraction operator and two revision operators for the monotonic core. Section 5 investigates the connections between contraction of the monotonic core and classical propositional contraction. Section 6 analyses two revision operators for non-monotonic entailment. Section 7 is the concluding section.

2 Background

We consider a finitely generated propositional language L with lower case letters denoting atoms, and capital letters denoting elements of L. We adopt the standard semantics for propositional logic. The set V of valuations v are functions from the set of atoms in L to t0, 1u denoting truth and falsity. Satisfaction is denoted by ,, and entailment by (.

AGM Belief Change. AGM belief change assumes an underlying logic with a propositional language and a Tarskian entailment relation Cn that is compact and satisfies disjunction in the premises ([Alchourr´on et al., 1985], p.511-512). A knowledge base K is assumed to be a set of formulas closed under entailment. AGM is concerned with three types of operators: expansion, contraction, and revision. Expansion is simply defined as adding a formula and closing under entailment: K � A � CnpK Y tAuq. The intuition associated with the contraction of K by A is that it should result in a knowledge base K � A in which A is not entailed. Dually, a revision of K by A should result in a consistent knowledge base K � A in which A is entailed. Formally, AGM contraction is required to satisfy the following basic postulates:

• p�5q If A � B then K�A �K� B (� extensionality)

AGM contraction operators can be constructed using socalled partial meet functions ([Alchourr´on et al., 1985], Observation 2.5). Let K�A be the remainder set, containing the maximal subsets K1 of K s.t. A R K1 . That is, K1 P K�A iff (i) K1 � K, (ii) A R K1 , and (iii) there is no set K2 s.t. K1 � K2 � K and A R K2 . Let pm be a partial meet function defined over K�A s.t. pmpK�Aq � K�A and if K�A � H, then pmpK�Aq � H. A partial meet contraction operator � is defined as: K�A � � pmpK�Aq.

Theorem 1 [Alchourr´on et al., 1985] A contraction operator is an AGM contraction operator (satisfying p�1q-p�6q) iff it is a partial meet operator.

Similarly, AGM revision is required to satisfy the following postulates:

• p�4q A P K�A (� success)
• p�5q If A � B then K�A �K�B (� extensionality)
• p�6q If A � K then K�A * K (� consistency)

It is well-known that revision can be defined in terms of contraction and expansion via the Levi Identity [Levi, 1977] : K�A � pK� Aq�A .

Theorem 2 [Alchourr´on et al., 1985] Revision defined in terms of a contraction operator � via the Levi Identity is an AGM revision operator iff � is an AGM contraction operator.

Intuitively the Levi Identity states that, to revise a knowledge base with A, we first contract with its negation, thereby "making room" for A, and then simply expand with A.

Preferential Entailment. To introduce defeasibility we consider the language L|� consisting of defeasible conditionals of the form A |� B (for A,B P L), that are read as 'Typically, if A then B'. The semantics of L|� is based on the notion of a preferential interpretation: triples of the form xW, l,�y where W is a set of objects (states), l is a function from W to V (mapping states into valuations), and � is a strict partial ordering on W [Kraus et al., 1990]. w � v is interpreted as indicating that the state w represents a more typical situation than the state v. For A P L, we let rAsW � tw P W | lpwq , Au. A defeasible conditional A |�B is satisfied in a preferential interpretation P, denoted as P , A |� B, iff min�rAsW � rBsW . Observe that a propositional formula A is satisfied in all the elements of W (i.e., lpwq , A for every w P W) iff P , A |� K. This means that any classical propositional formula A can be represented as the defeasible conditional A |� K. Indeed every conditional of the form A |� K is not defeasible, and actually represents classical propositional information. E.g., the statement that vertebrate red blood cells have a nucleus (v � n) will be represented as pv � nq |�K. Because of this we sometimes abuse notation by referring to A |�K as the propositional formula A.

Let B indicate a finite set of defeasible conditionals. The set of preferential models of B, preferential interpretations satisfying B, is denoted by rrBss. The obvious notion of Tarskian entailment associated with this semantics is known as preferential entailment [Lehmann and Magidor, 1992], represented as (pr, where B (pr A |�B iff rrBss � rrtA |� Buss. The closure operator associated with preferential entailment is known as preferential closure: PpBq � tA |�B | B (pr A |�Bu. We use the notation K, K1 etc. to refer to conditional knowledge bases closed under preferential entailment. B is preferentially inconsistent iff B (pr J |�K, and B is preferentially incoherent w.r.t. a propositional formula A iff B (pr A |�K. Two bases are preferentially equivalent iff they have the same preferential models.

In what follows below, the notion of exceptionality and the rank of a formula (and a defeasible conditional) is important ([Lehmann and Magidor, 1992], Section 2.6). A P L is said to be exceptional w.r.t. B iff B (pr J |� A (that is, in every model of B A is falsified in all the most typical states), and A |� B P L|� is said to be exceptional w.r.t. B iff A is exceptional w.r.t. B. We make use of exceptionality to provide a notion of rank for defeasible conditionals. E B 0 � B and for i ¥ 0, E B i � tA |� B P E B i�1 | A |� B is exceptional w.r.t. E B i�1 u. There is a smallest integer, say n, such that E B n � E B n�1 (it may be the case that E B n � H). The rank of A P L w.r.t. B, denoted as rBpAq, is the smallest integer k for which A is not exceptional w.r.t. E B k . If A is exceptional w.r.t. E B i for all i, then rBpAq � 8. The rank of a defeasible conditional A |� B w.r.t. B, denoted as rBpA |� Bq, is equal to rBpAq. Intuitively, the rank of a defeasible conditional provides an indication of the extent to which we would be willing to override it: the lower the rank, the more likely we are to discard it. Conditionals with rank 8 will never be overridden and can thus be viewed as classical assertions w.r.t. B. For i P t0, . . . , n � 1,8u we let Bi � tA |� B P B | rBpA |� Bq � iu, and we let B�8 � BzB8. From a computational perspective, it is useful to note that exceptionality checking can be reduced to classical propositional reasoning. The materialisation ��B of B is defined as follows: ��B � tA � B | A |� B P Bu. It is known that exceptionality w.r.t. B (B (pr J |� A) can be reduced to checking whether ��B ( A ([Lehmann and Magidor, 1992], Section 5.8). In particular, B8 is the biggest subset of B s.t. B8 � tA |�B P B | �� B8 ( Au, and, for every A P L, A |� K P PpBq iff �� B8 ( A. All the notions defined above for conditional bases B also apply to every knowledge base with the property of having a wellfounded model. Base-generated knowledge bases have such a property ([Lehmann and Magidor, 1992], Lemma 2.24); it can be proved that the operators defined here preserve it as well.

3 The Monotonic Core

It is widely recognised that preferential entailment is too weak to be an appropriate form of entailment for a nonmonotonic framework ([Kraus et al., 1990], pp. 4,34). This is primarily because the preferential entailment relation itself is monotonic (non-monotonicity occurs on the object-level, within defeasible conditionals). At the same time there is sufficient consensus that any acceptable form of non-monotonic entailment will be an extension of preferential entailment [Kraus et al., 1990; Lehmann and Magidor, 1992]. Our final focus in this paper is on such an extended set of nonmonotonic entailment relations. Below we make this idea more precise by defining the class of supra-preferential cumulative entailment relations.

Consider a closure operator C, which is defined as follows: A |� B P CpBq iff P , A |� B for every preferential model P P cpBq, where c is a choice function s.t. (i) cpBq � rrBss, (ii) if rrBss � H then cpBq � H, and (iii) cpBq � cpcpBqq. The closure operators definable using such choice functions are the ones that extend preferential closure and respect consistency preservation (if J |� K R PpBq, then J |� K R CpBq), and we will indicate them as supraclassical. We also require cumulativity: for every B, B1 , if B � B1 � CpBq, then CpB1 q � CpBq. This is captured by a choice function c as follows: if cpBq � rrB1 ss � rrBss, then cpB1 q � cpBq. We refer to the closure operators satisfying these properties as spc-operators (as supra-preferential cumulative). Most of the prominent non-monotonic closure operators proposed in the preferential framework (e.g. [Kraus et al., 1990; Lehmann and Magidor, 1992; Lehmann, 1995; Casini and Straccia, 2013]) are spc-operators. Our goal is to analyse belief change for the class of spc-operators.

As mentioned in Section 1, belief change in a nonmonotonic framework seems superfluous at a first glance, since the non-monotonic machinery usually takes care of 'readjusting' the inferences in order to preserve consistency and coherence facing new unexpected evidence. But that's not always the case. Let's look at some examples.

• Example 1 Consider the example about the red blood cells, but adding the information that avian red blood cells are vertebrate red blood cells (a � v). Let our base contain the conditional counterpart of the classical formalisation. I.e., B � t pv � nq |� K, pm � vq |� K, pm � nq |� K, pa � vq |�Ku. Consider the following situations:
• m |�K is in CpBq. But mammalian red blood cells exist, and we want to enforce such information. In propositional belief change we would remove some piece of information, presumably either m � v, v � n, or m � n. In the framework we propose we can resolve the situation by introducing defeasibility. Contracting m |� K from B we would like to end up, for example, with B1 � tv |�n, pm� vq |� K, pm � nq |�K, pa � vq |�Ku in which, instead of eliminating pv �nq |�K, we have just made it defeasible.
• If C is a well-behaved non-monotonic closure operator, we should have a |�n P CpB1 q, since, with the information we have, we can treat avian cells as typical vertebrate cells. Now assume we are informed that a |� n: B2 � tv |�n, pm� vq |�K, pm� nq |�K, pa � vq |�K, a |� nu. In this case, since a |� n is a presumptive conclusion made by the non-monotony machinery, the entailment relation itself will take care of eliminating such a conclusion once faced with conflicting evidence. In such a case we want the introduction of a |� n to correspond to a simple expansion.
• We are then informed that a |�n actually holds, information that directly conflicts with a |� n in our base. This kind of conflict cannot be managed by the non-monotonic machinery, since a |� n is a (trivial) necessary conclusion from B2 . So, we would be forced to conclude that avian red blood cell do not exist (a |�K). We have two choices: either we are interested just in general consistency (not deriving J |�K), and in such a case the addition of a |�n is just an expansion and we conclude that birds do not have red blood cells. Or we perform a revision in order to 'make room' for a |�n without being forced to conclude a |�K.

As shown in the examples, in order to preserve consistency and coherence we need to distinguish between what follows necessarily from the information at our disposal and what the inference operator concludes 'presumptively'. That is, we need to identify the monotonic part of our reasoning and operate only on it, while for the non-monotonic part the entailment relation should automatically take care of the appropriate adjustments. A closure operator Cl is called the monotonic core of a non-monotonic operator C if, for every B, B1 , (i) B � B1 implies ClpBq � ClpB1 q; (ii) ClpBq � CpBq; (iii) for every closure operator Cl1 satisfying (i) and (ii), Cl1 pBq � ClpBq. Given a non-monotonic entailment relation, the existence of a monotonic core needs to be proved.

Proposition 1 The monotonic core of a supra-preferential closure operator is the preferential closure P.

Proof: (Sketch). Assume that for some A |� B P CpBqzPpBq there is a monotonic C 1 contained in C s.t. A |� B P C 1 pBq, and obtain a contradiction. l

Hence, the monotonic core of the class of spc-operators is the preferential closure.

4 Preferential Belief Change

In this section we start our investigation with a study of belief change for the monotonic core of spc-operators-that is, belief change for preferential entailment. We apply an AGM-like approach to the preferential closure K of defeasible knowledge bases B. Expansion is then defined as: K� A|�B � PpK Y tA |�Buq. The postulates for contraction are as follows (where �P refers to preferential equivalence):

Partial meet functions for preferential entailment are defined as expected. K1 P pK�A |� Bq iff (i) K1 � K, (ii) A |� B R K1 , and (iii) there is no K2 s.t. K1 � K2 � K and A |� B R K2 . Let pm be a partial meet function defined over pK�A |�Bq s.t. pmpK�A |�Bq � pK�A |�Bq and if pK�A |�Bq � H, then pmpK�A |�Bq � H. A partial meet contraction operator � is defined as: K� A|�B � � pmpK�A |� Bq. And as expected, we have a representation result, linking the postulates and partial meet functions.

Theorem 3 A contraction operator � for preferential entailment satisfies p�1q to p�6q iff it is a partial meet contraction operator.

The proof of this result is postponed to the end of Section 5. Turning now to coherence preservation, observe firstly that this can be attained using preferential contraction. More precisely, to ensure coherence of K w.r.t. a formula A, we perform a contraction of K by A |�K (see Example 1.1).

Moving to revision, in the present framework we can define two kinds of revision: one to preserve consistency (adding A |�B while avoiding to conclude J |�K) and one to preserve coherence (adding A |�B while avoiding to conclude A |� K, see Example 1.3). Regarding the former, we will make use of the following result.

Proof: From left to right, assume that K *pr J |�A^ B. Then there is a model P s.t. P . J |� A ^ B. That is, there is a valuation v that is minimal in P s.t. v , A � B. Let P 1 be a model consisting of v only. P 1 is a model of K Y tA |� Bu. The other direction comes from A |�B (pr J |�A � B ([Kraus et al., 1990], Lemma 19) and the monotonicity of (pr. l

The postulates for this type of revision are the following:

Observe that for revision we require, in addition to the translation of the standard postulates, the extra postulate p��q. The reason for the need of this postulate relates to the result in Proposition 2, plus the fact that A |� B (pr J |�A � B. Proposition 2 implies that to "make room" for A |� B and preserve consistency we need to "make room" only for the weaker conditional J |�A � B.

A direct translation of the Levi Identity into the preferential framework is not possible, since the negation of a conditional A |�B cannot be expressed directly. But recall that in classical AGM, contraction with the negation of A should result in a knowledge base that is compatible with A. Proposition 2 gives us the right contraction to apply to preserve consistency, and we rephrase the Levi Identity as follows:

From this we get the following representation result.

Theorem 4 A revision operator � satisfies the postulates p�1q � p�6q and p��q iff it can be defined, via (1), from a contraction operator satisfying the postulates p�1q � p�6q.

Proof: (Sketch). From right to left, it is easy to check that if � satisfies p�1q � p�6q, � satisfies p�1q � p�6q, p��q. From left to right, define K� A|�B as follows: if |ø A � J, then K� A|�B :� pK�J|� B XKq (a reformulation of the Harper Identity [Harper, 1976]); if |� A � J, then K� A|�B :� � pmpK�A |� Bq for some choice function pm. We prove that � generates �: pK� J|�A^ B q�A|�B � pK�J|�A�B XKq�A|�B ; pK�J|�A�B X Kq�A|�B � ppK�J|�A�B q�A|�B X K� A|�B q, that by p��q is equivalent to pK�A|�B X K� A|�B q, that by p�2q is equivalent to K�A|�B . Now we have to check that � satisfies p�1q � p�6q. For |� A � J, use Theorem 3. If |ø A � J, the only difficulty is to prove p�6q: K � pK� J|�B q�J|�B iff K � pK�J|� B XKq�J|�B iff K � ppK�J|� B q�J|�B XpKq�J|�B q iff K � pK�J|� B q�J|�B , that holds since J |�K P pK�J|� B q�J|�B .

If we want to add a conditional A |�B preserving not only consistency but also coherence w.r.t. A, we can model a revision operator � as

We characterise such a class of operators with a set of postulates p�1q � p�6q where p�1q, p�2q, p�4q, p�5q are the reformulation for � of the corresponding �-postulates, while p�3q and p�6q are:

If we use a partial meet contraction � in the definition of �, it is easy to show that we obtain a revision operator that satisfies p�1q � p�6q, but in order to characterise such a class of revision operators, we refer to a more general class of contraction operations: those satisfying p�1q � p�5q.

Proof: (Sketch). If � satisfies p�1q � p�5q, it is easy to check that p�1q � p�6q are satisfied. For p�6q we need p�4q and Lemma (1) (see below). Now let � be a revision operator satisfying p�1q � p�6q, and define � as K� A|�B :� pK�A|� B X Kq. First, we have to check that � generates �. Start with K�A|�B � pK�A|�B X Kq�A|�B , that is equivalent to K�A|�B � ppK�A|�B q�A|�B XK� A|�B q. By p�2q that's equivalent to K�A|�B � pK�A|�B q�A|�B , that by p�6q, p�4q, and p�3q is equivalent to K�A|�B � K�A|�B . Proving that � satisfies p�1q � p�5q is immediate. l

Contraction operations satisfying p�1q � p�5q can be easily characterised using a choice function that, for the contraction of A |�B from K, just pick a subtheory of K that does not imply A|�B.

5 AReduction to Classical Contraction

In this section we investigate the option of defining contraction for preferential entailment in terms of classical propositional contraction. As we shall see, it turns out that piq there is an intuitive way for doing so and piiq perhaps surprisingly, there is a precise correspondence between classical AGM contraction and preferential AGM contraction. To do so, we'll make use of the following result.

Recall from Section 2 that a knowledge base K is partitioned into ranks Ki for i P t0, . . . , n � 1,8u. It is not hard to prove that the entailment of formulas of the form A |� K is determined solely by the conditionals of infinite rank.

For brevity, we use K1 to denote K Y tA |� Bu, K8 A|� B to denote K18 XK (that is, the set of conditionals in K that have infinite rank in K1 ), while K�8 A|� B :� KzK8 A|� B (the conditionals in K that do not have infinite rank in K1 ). Then we get from Lemmas 1 and 2 that K (pr A |�B iff K18 (pr A |�K. Also, if K1 (pr A |�K it must hold that A |� B P K18. Therefore K18 � K8 A|� B Y tA|� Bu and

So, to obtain a preferential partial meet contraction operator w.r.t. the contraction of A |� B we only consider K8 A|� B , leaving K�8 A|� B untouched, as Propositions 4 and 5 imply.

We can conclude the following.

K� (pr { A |�B iff �������� K� zK�8 A|� B |� A � B. Together with the definition of a remainder set and Proposition 4 this proves the proposition. l

Given a classical propositional contractor operator �, we can now justify the following definition of preferential contraction in terms of �:

The following is the main result of this section.

Theorem 5 � is a partial meet preferential contraction iff it can be defined, in terms of Definition 1, using a partial meet propositional contraction �.

Proof: (Sketch). It is easily derivable from Proposition 5. For one direction let � be defined as � pmpK�A |� Bq for some pm, and then introduce a propositional choice function pm1 as pm1 p����� K8 A|� B �A � Bq :� t�������� K� zK�8 A|� B | K� P pmpK�A |� Bqu to define �. For the other direction let � be defined using a function pm1 and use pmpK�A |�Bq :� tK�8 A|� B Y tC |� D P K8 A|� B | C � D P Au | A P pm1 p����� K8 A|� B �A�Bqu to define �. l

Theorem 5 shows that there is a precise correspondence between classical AGM contraction and preferential AGM contraction: the latter can be determined using the former, preceded by the ranking process described in Section 2.

We conclude this section with a proof of Theorem 3 in Section 5, made easy by the availability of Theorem 5.

Proof of Theorem 3: (Sketch). From left to right it is sufficient to check that every postulate is satisfied. p�1q � p�5q are easy. p�6q comes easily from Theorem 5 and p�6q. From right to left, fromK� A|�B define a partial meet function pm as K� P pmpK�A |�Bq iff K� P pK�A |�Bq and K� A|�B � K� . We need to prove that K� A|�B � � pmpK�A|�Bq. It is provable defining a propositional partial meet function pm1 over p����� K8 A|� B �A � Bq as in the proof of Theorem 5, then defining from it a partial meet propositional contraction �, and then showing that � can be defined using � in Definition 1. By Theorem 5, � is a partial meet preferential contraction. l

Note that, applying any partial meet operator in Example 1.1 to contract m |� K, we preserve the conditional v |� n, since it does not have an infinite rank.

6 Revision w.r.t. Non-monotonic Closure

In the previous sections we investigated belief change for the monotonic core of the (non-monotonic) spc-operators. Here we build on those results to venture into the area of belief change for the spc-operators. So consider an spc-operator C. As in the previous sections, our focus will be on operators for closed knowledge bases-closed under C in this case. We use K to refer to knowledge bases closed under C. Since revision for C will be defined in terms of its monotonic core, we need to distinguish between K and its monotonic core. We refer to the latter as KP . Here are the postulates for revision w.r.t. C:

• p�4q A|�B P K�A|�B (� success)

The only postulate that needs some explanation is p�2q. Given that C is non-monotonic , standard inclusion (K�A|�B � CppKP q�A|�B q) is not applicable. What p�2q conveys is that it should be possible to generate the non-monotonic closure K�A|�B from the C-closure of a set of conditionals K1 that is a subset of pKP q�A|�B : our revision on the non-monotonic level should be generated by a revision in the monotonic core.

As Theorem 6 shows, the revision for C can be defined in terms of the revision of the monotonic core.

Theorem 6 � is a revision operator satisfying p�1q � p�6q iff there is a preferential revision � satisfying p�1q � p�6q s.t. K�A|�B � CppKP q�A|�B q.

Proof: From right to left it is easily provable. In the other direction, define � as pKP q�A|�B :� pK�A|�B X pKP q�A|�B q. We need to prove that K�A|�B � CppKP q�A|�B q. CppKP q�A|�B q � CpK�A|�B XpKP q�A|�B q and, by p�2q, there is a K1 s.t. K�A|�B � CpCpK1 q X pKP q�A|�B q and K1 � pKP q�A|�B . Hence we have that K1 � pCpK1 q X pKP q�A|�B q � CpK1 q, and, C being cumulative, we obtain that CppCpK1 q X pKP q�A|�B qq � CpK1 q that in turn equals K�A|�B . Check that � satisfies p�1q � p�6q. l At the moment we do not have a representation result that also incorporates the postulate p��q.

We can define revision for coherence preservation in a similar way, except that we have to add a constraint to C. That is, the monotonic part of our information is determined by the preferential closure: for every A and every K, A |� K P K iff A |� K P KP . This property was initially proposed by Lehmann and Magidor ([1992], Sections 5.4-5.5). It is satisfied by most of the prominent non-monotonic entailment relations proposed in the preferential framework [Kraus et al., 1990; Lehmann and Magidor, 1992; Lehmann, 1995; Casini and Straccia, 2013]. The revision postulates for coherence preservation are pb1q, pb2q, pb4q, and pb5q, that are direct reformulations of b of p�1q, p�2q, p�4q, and p�5q, and:

We obtain the analogous of Th. 6 for coherence preservation. Theorem 7 b is a revision operator satisfying pb1q � pb6q iff there is a preferential revision � satisfying p�1q � p�6q s.t. Kb A|�B � CppKP q�A|�B q.

Proof: The proof is similar to that of Theorem 6. In the first half, to prove that pb6q hold we have to refer to the property that A |�K P K iff A |�K P KP . l

As p�3q indicates, the operator is such that if the conflicts do not arise at the level of preferential entailment, the revision resolves in a simple expansion, as indicated in Example 1.2.

7 Conclusion

In this paper we have laid the foundations for defining belief change in (preferential) non-monotonic framework. Following the well-known AGM approach, we defined and characterised AGM expansion, contraction and revision (for both consistency and coherence preservation) on the monotonic core of a class of non-monotonic closure operators-the spcoperators. We also showed that preferential AGM contraction can be reduced to classical AGM contraction. Then we showed how to define revision for the class of spc-operators.

As far as we know, just a few works deal with belief change in a nonmonotonic framework. Booth and Paris [1998] deal with conditional bases, but also containing negative conditionals, which can be thought of as related to the contraction of conditionals. Casini and Meyer [2016] are concerned with the contraction of strict conditionals A |�K from finite conditional bases in order to restore coherence. Hunter [2016] deals with the revision of highly implausible conditionals, while Delgrande and others [2013] analyse belief change in Answer Set Programming. Conditional belief change was previously addressed by Kern-Isberner [1999], who proposes a set of rationality postulates; the relations between her approach and ours will be object of further analysis.

For future work, an obvious next step is to define a form of base change for defeasible bases, but in such a way that it adheres to the type of change defined for the closed knowledge bases. For example, for a base contraction operator � of this kind, we would require that PpB� A|�B q � PpBq�A|�B . We have started to work along these lines where the base contraction operator � is built on top of similar propositional base contraction operators [Nebel, 1989; Meyer, 2001]. We also intend to extend our work to belief change for Description Logics. Recently, there has been a lot of interest in developing non-monotonic formalisms for this family of logics, especially in the preferential framework [Britz et al., 2008; 2011; Casini and Straccia, 2010; 2013; Giordano et al., 2013; 2015; Lukasiewicz, 2008]. Given the importance of coherence in the field, we expect such an extension to be very useful.

Acknowledgments

The work of Giovanni Casini has been supported by the Fonds National de la Recherche, Luxembourg, and cofunded by the Marie Curie Actions of the European Commission (FP7COFUND) (AFR/9181001). Thomas Meyer has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie SkłodowskaCurie grant agr. No. 690974.