# on_paraconsistent_belief_revision_in_lp__c3d5e757.pdf

On Paraconsistent Belief Revision in LP

Nicolas Schwind1, S ebastien Konieczny2, Ram on Pino P erez2

1 National Institute of Advanced Industrial Science and Technology, Tokyo, Japan 2 CRIL - CNRS, Universit e d Artois, Lens, France nicolas-schwind@aist.go.jp, {konieczny,pinoperez}@cril.fr

Belief revision aims at incorporating, in a rational way, a new piece of information into the beliefs of an agent. Most works in belief revision suppose a classical logic setting, where the beliefs of the agent are consistent. Moreover, the consistency postulate states that the result of the revision should be consistent if the new piece of information is consistent. But in real applications it may easily happen that (some parts of) the beliefs of the agent are not consistent. In this case then it seems reasonable to use paraconsistent logics to derive sensible conclusions from these inconsistent beliefs. However, in this context, the standard belief revision postulates trivialize the revision process. In this work we discuss how to adapt these postulates when the underlying logic is Priest s LP logic, in order to model a rational change, while being a conservative extension of AGM/KM belief revision. This implies, in particular, to adequately adapt the notion of expansion. We provide a representation theorem and some examples of belief revision operators in this setting.

Introduction Belief revision aims at incorporating, in a rational way, a new piece of information into the beliefs of an agent. The core of belief change theory (Alchourr on, G ardenfors, and Makinson 1985; G ardenfors 1988; Katsuno and Mendelzon 1991; Hansson 1999; Ferm e and Hansson 2011) is well-established now, and the numerous representation theorems, for instance (Alchourr on, G ardenfors, and Makinson 1985; G ardenfors 1988; Katsuno and Mendelzon 1991; Alchourr on and Makinson 1985) as well as the results showing the closeness between belief change and non-monotonic inference (G ardenfors 1990; Kraus, Lehmann, and Magidor 1990; Lehmann and Magidor 1992) and possibilistic logic (Dubois and Prade 1991; Dubois, Lang, and Prade 1994) confirm that the AGM framework (for Alchourr on, G ardenfors and Makinson 1985) correctly models this fundamental process. Nonetheless, some adaptations are required when one leaves the standard classical setting. In particular, one fundamental assumption of the AGM framework is that one works in extensions of classical logic (AGM postulates are stated for any logic satisfying some basic requirements, one

Copyright 2022, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

of which is that the consequence relation must contain all classical consequences). If one does not want this to occur then one quickly enters into unknown territories. To motivate this work, let us recall that the AGM revision postulates aim to formalize three intuitive principles:

primacy of update. The new piece of information must be believed after the change; consistency. The result of the change has to be a consistent belief base whenever the new piece of information is consistent; minimal change. We want the result to be as close as possible to the previous beliefs: we do not want to add unnecessary new beliefs and we want to give up only the beliefs that prevent the first two principles from holding.

Minimal change is really at the heart of belief change, as the revised base should be as pertinent as possible. So it is not a principle that can be relaxed. Primacy of update is a very natural requirement. Nonetheless, in some applications it may be sensible to expect a different behaviour. Sometimes we may want to be given the choice on whether to accept only a part of the new piece of information (Hansson 1998; Makinson 1998; Hansson et al. 2001; Booth et al. 2012; Falappa et al. 2012; Booth et al. 2014; Garapa, Ferm e, and Reis 2020). Or we may not want to give such a high priority on the new piece of information with respect to the current beliefs, which could lead us to promotion (Schwind, Konieczny, and Marquis 2018) or improvement (Konieczny, Medina Grespan, and Pino P erez 2010; Konieczny and Pino P erez 2008), or, when we want to give the same weight to both, to merging operators (Revesz 1993; Konieczny and Pino P erez 2002, 2011; Schwind and Konieczny 2020). So relaxations of this principle have been highly investigated. Contrastingly, the relaxations of the last principle, consistency, have rarely been investigated. We can see several reasons for that. First because, as explained above, the AGM framework requires working with a logic that is an extension of classical logic. So it prevents us from working with paraconsistent logics, that do not contain all classical consequences (in particular when the current belief base is not classically consistent). Another reason could be that adding a new piece of information into the beliefs of the agent when working in a paraconsistent logic could appear simple: as

The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22)

these logics do not fear logical conflicts, simply performing the conjunction seems to be enough. This is a debatable point, since it forgets the fact that belief revision is about rational change; and the minimal change principle can be interpreted as a requirement to reject the conjunction in this case. This is what this paper is about. A number of AGM postulates are based on consistency conditions. For instance, in line with the previous point, one of the AGM postulates says that if the conjunction of the belief base and the new piece of information is consistent, then the result of the revision must be exactly this conjunction. This is very sensible in classical logic: if there is no logical conflict caused by the new piece of information we have nothing else to do than adding this piece of information. A direct counterpart of this postulate in paraconsistent logics would require to trivialize the change: we would always have to use the conjunction. So this postulate, and other ones, have to be adapted to be able to cope with paraconsistent logics. We want to stress that studying belief revision in a paraconsistent logic setting is more than a technical exercise or a purely theoretical question. The AGM setting assumes that the beliefs of the agent are consistent. If it is not the case, then any revision (by a consistent formula) will restore consistency. This is very sensible theoretically. But we want to stress than in real applications this will certainly be the exception rather than the general case. If an agent gathers its beliefs from a lot of different sources (think for instance of an ontology built from gathering information from internet sources), it may very easily happen that some parts of these beliefs are not consistent. In this case, either we can try to repair the inconsistencies, but this will certainly require arbitrary choices and does not really represent the current beliefs of the agent, or we can live with the inconsistency (Gabbay and Hunter 1991; Priest 2002; B eziau, Carnielli, and Gabbay 2007) until we explicitly obtain information allowing to solve these inconsistencies, while being able to derive sensible conclusions from the beliefs of the agent that are not related to these inconsistencies. As an example, consider that the current beliefs of the agents are p p q r and that the new piece of information is q. If someone uses a classical AGM/KM operator1 then the result will have to be consistent, so learning q will solve the conflict on p. But, without any additional information, it is arguable to consider that these variables can be independent, and that the expected result could be p p q r, i.e., that we take into account the new piece of information, but that it does not change anything about the conflict on p. There is no existing operator that allows that, and this is the kind of operators that we want to introduce in this paper. To do so, we will work in the LP logic setting. LP logic (for Logic of Paradox) (Priest 1979, 1991) is a 3-valued logic, with the third value meaning inconsistent ( both true and false ), that allows to isolate inconsistencies in the concerned propositional variables. For instance in a large base (or ontology), we can have several topics (identified by

1The KM framework is a particular case of AGM in the finite propositional case (Katsuno and Mendelzon 1991).

sets of variables) with inconsistencies on some of these topics, but we want to be able to have non-trivial consequences on topics with no inconsistencies. LP logic allows to do that. We discuss how to adapt the AGM/KM postulates when the underlying logic is Priest s LP logic, in order to model a rational change, while being a conservative extension of AGM/KM belief revision. This requires in particular to adequately adapt the definition of expansion, since its direct translation is not adequate for non classical settings. We provide a representation theorem for this class of revision operators in terms of plausibility preorders (faithful assignements) on interpretations. And we define a whole family of distance-based operators, that generalize Dalal revision in this setting. For space reasons the proofs are omitted, but an extended version containing all the proofs is available from http://www.cril.fr/ konieczny/AAAI22-SKP.pdf.

Formal Preliminaries

Let LP S be a propositional language built up from a finite set of propositional variables PS = {x1, . . . , xn} and the usual connectives. Given X PS, X denotes the set PS \ X. The symbol X denotes the formula V xi X xi xi. Given a formula α, V ar(α) denotes the set of propositional variables appearing in α. An LP world ω is a mapping from PS to {0, 1, B} (the value B intuitively means both true and false ). These three truth values are ordered as 0 <t B <t 1. An LP world ω is said to be a classical world if for each xi PS, ω(xi) {0, 1}. The set Ω denotes the set of all LP worlds, and the set Ωdenotes the set of all classical worlds. The LP semantics of a formula in an LP world ω are defined inductively as follows: ω( α) = B if ω(α) = B, ω( α) = 1 if ω(α) = 0, ω( α) = 0 if ω(α) = 1, ω(α β) = min({ω(α), ω(β)}, t), ω(α β) = max({ω(α), ω(β)}, t). An LP world ω is an LP model of a formula α iff ω(α) {1, B}, and it is said to be a classical model of α when ω is a classical world. A formula is said to be LP-consistent if it has an LP model; it is said to be consistent if it has a classical model. Note that the notion of LP-consistency is a trivial one, since the LP world ω defined as ω (xi) = B for each xi PS is an LP model of every formula. The set of LP models of a formula α is denoted by JαK, and its set of classical models is denoted by [α]. An LP world will be written as a sequence of symbols from {0, 1, B}, assuming an implicit ordering on PS. For instance, for PS = {p, q, r} the LP world ω defined as ω(p) = 0, ω(q) = B and ω(r) = 1 will simply be denoted by ω = 0B1. The LP consequence relation, denoted by |=LP , is defined as α |=LP β iff JαK JβK. Two formulae α, β are said to be equivalent, denoted by α LP β, iff JαK = JβK. Likewise, the classical consequence relation |= is defined as α |= β iff [α] [β], and two formulae are said to be classically equivalent, denoted by α β, iff [α] = [β].

Representative LP Models & LP-DNF Let us now consider the partial ordering2 LP on the set of all LP worlds Ω , defined for all ω, ω Ω as ω LP ω if and only if for each xi PS, ω (xi) {ω(xi), B}. Intuitively, ω <LP ω could be read as ω is less classical than ω. In particular, it can be seen that the minimal elements of Ω with respect to LP form the set of all classical worlds Ω. Now, let us stress that if an LP world ω is an LP model of a formula α, then all of the LP worlds that are less classical than ω are also LP models of α. This is formalized in the following lemma: Lemma 1. If ω JαK and ω LP ω , then ω JαK. Given an LP world ω, let us define the formula ψω as ψω = V xi P S li, where li = xi if ω(xi) = 1, li = xi if ω(xi) = 0, otherwise li = xi xi. One extends the above definition to a set of LP worlds S = , i.e., ψS is defined as ψS = W ω S ψω. The set JψSK is called the LP closure of S. The LP closure of S only contains (i) the LP worlds from S, and (ii) all LP worlds that are less classical than some LP world from S (which is a necessary condition according to Lemma 1). This is formalized in the following lemma: Lemma 2. 1. ω JψωK 2. If ω JψSK, then ω S s.t. ω LP ω 3. If S JαK, then ψS |=LP α The LP closure also satisfies the standard closure properties of extensivity, monotonicity, and idempotence: Lemma 3. 1. S JψSK 2. If S T, then ψS |=LP ψT 3. ψS LP ψJψSK Now, with every formula one can associate a representative subset of its set of LP models that will be of particular importance in the rest of this paper. Definition 1. Given a formula α, the representative set of LP models of α, denoted by JαK , is defined as JαK = min(JαK, LP ). Let us introduce a few remarkable properties on representative LP models: Lemma 4. 1. α LP ψJαK 2. If S JαK , then α |=LP ψS The first point states that the representative set of LP models of α is sufficient to retrieve all LP models of α. And the second point says that each LP model from the representative set of α is necessary to retrieve all LP models of α. These two points together mean that each formula can be characterized (up to equivalence) by its representative set. Given that the LP worlds from any representative set are all pairwise incomparable w.r.t. LP (see Definition 1), this characterization result can be formally expressed as follows: Let (2Ω ) denote the set of all subsets of LP worlds that are pairwise incomparable w.r.t. LP , i.e., (2Ω ) = {S Ω | ω, ω S, ω LP ω = ω = ω }:

2Given a partial ordering , the symbols < and denote respectively the corresponding strict and equivalence relations. When the ordering is denoted by , its strict counterpart is denoted by .

Corollary 1. For any formula α, there is a unique set Sα (2Ω ) such that α LP ψSα. Moreover, Sα = JαK . Corollary 1 says that the representative set of a formula α is the only set from (2Ω ) which can characterize α (up to equivalence). The other way around, one can also see that every set of LP worlds S (2Ω ) is the representative set of some formula: Corollary 2. For each S (2Ω ) , there exists a formula α such that JαK = S. So Corollaries 1 and 2 make clear the one-to-one correspondence between the set of all formulae (up to equivalence) and their representative sets from (2Ω ) . Since any formula α can be represented equivalently in a canonical form characterized by its representative set, in what follows, given any formula α, the formula ψJαK LP α will be called the LP Disjunctive Normal Form (LP-DNF) of α. And lpdnf(α) will denote the set {ψω | ω JαK }. Accordingly, we have that α LP W ψω lpdnf(α) ψω.

Issues with KM Postulates in LP Revision A revision operator associates all formulae ϕ, µ with a formula ϕ µ. A set of standard properties are expected in the classical case. Let us recall the standard KM postulates: Definition 2. (Katsuno and Mendelzon 1991) A revision operator is said to be a KM revision operator if it satisfies the following postulates:

(R1) ϕ µ |= µ (R2) If ϕ µ is consistent, then ϕ µ ϕ µ (R3) If µ is consistent, then ϕ µ is consistent (R4) If ϕ ϕ and µ µ , then ϕ µ ϕ µ

(R5) (ϕ µ) µ |= ϕ (µ µ ) (R6) If (ϕ µ) µ is consistent, then ϕ (µ µ ) |= (ϕ µ) µ

Let us recall that the notion of consistency referred to in these postulates corresponds to the notion of classical consistency, i.e., it refers to formulae which admit at least one classical model. KM revision operators can be characterized in terms of faithful assignments: Definition 3. A faithful assignment (denoted by ϕ 7 ϕ) is a mapping associating every formula ϕ with a preorder ϕ over classical worlds, such that: 1. ω, ω Ω, if ω, ω [ϕ] then ω ϕ ω

2. ω, ω Ω, if ω [ϕ] and ω / [ϕ], then ω ϕ ω

3. If [ϕ] = [ϕ ], then ϕ= ϕ

Proposition 1. (Katsuno and Mendelzon 1991) A revision operator is a KM revision operator if and only if there exists a faithful assignment ϕ 7 ϕ associating every formula ϕ with a total preorder ϕ over classical worlds, such that for all formulae ϕ, µ, [ϕ µ] = min([µ], ϕ). Our goal is to define interesting revision operators in the LP setting, and in order to do so, our first step is to look at the KM postulates with the LP semantics in mind. Yet in the paraconsistent case the notion of LP-consistency is a trivial one, i.e., each formula is LP-consistent since the world ω defined as ω(xi) = B for each xi PS is an LP model

of every formula. So, if one interprets the KM postulates in the LP setting, postulate (R3) becomes trivially true and the remaining KM postulates can be rephrased as follows:

(R1-LP) ϕ µ |=LP µ (R2-LP) ϕ µ LP ϕ µ (R4-LP) If ϕ LP ϕ and µ LP µ , then ϕ µ LP ϕ µ

(R5-LP) (ϕ µ) µ |=LP ϕ (µ µ ) (R6-LP) ϕ (µ µ ) |=LP (ϕ µ) µ

Postulates (R1-LP) and (R4-LP) express requirements that are similar to the classical case and can be seen as natural extensions of (R1) and (R4) to the LP setting. As to the remaining postulates, let us first discuss (R2-LP). This postulate is clearly too strong since it forces the revision to trivialize to the conjunction. So one must consider a weakening of (R2-LP). One of the least demanding weakenings is to ask that the agent s current beliefs should not change when they are revised by a tautology (see, e.g., (Benferhat, Lagrue, and Papini 2005)):

(R2-LP ) ϕ LP ϕ

Requiring (R2-LP ) is very natural even in the paraconsistent case: there is no reason for changing some agent s beliefs ϕ when the new information is tautological, whether ϕ is consistent or not. But then, it turns out that the postulates (R5-LP) and (R6-LP) again trivialize the revision to be the conjunction in presence of (R2-LP ):

Proposition 2. If satisfies (R2-LP ), (R5-LP) and (R6LP), then it satisfies (R2-LP).

What is Expansion? The previous results illustrate the trivialization caused by a naive interpretation of KM revision postulates in LP. Most of these problems are caused by the use of LP conjunction. In particular, as LP conjunction is always LP-consistent, then (R2-LP) trivializes the revision to a simple conjunction in LP. As explained in the introduction, we want to go further than that, and we motivated the fact that revision is not just about consistent change, but about rational change. To solve this trivialization issue, one has to come back to the AGM definition of expansion, revision and contraction (Alchourr on, G ardenfors, and Makinson 1985), and to remember that the addition of a formula into a belief set has to be done using expansion, and that revision is defined using expansion. It turns out that AGM showed that, in the classical setting, the only expansion operator is logical conjunction. But this is not necessarily the case in other, nonclassical settings, like ours. Expansion basically aims at acquiring new information when a new evidence does not raise conflicts in the beliefs of the agent. Interpreted in terms of possible worlds, this is done by selecting the possible worlds of the beliefs of the agent that satisfy the new evidence. This makes perfect sense in the AGM coherentist setting, where all the beliefs, so all the possible worlds, have the same status. But in LP, the representative set of models of a formula are more important than the others. For instance, given ϕ = p q, we get that JϕK = {11, 1B, B1, BB} and JϕK = {11}, so the LP model 11 is more informative than the others which are only there because of 11.

So, expansion in this setting should take this dimension into account, and make a selection among the LP worlds from the representative set. Let us put it formally. Recall that the LP-DNF formula which is equivalent to a formula α is ψJαK , and that lpdnf(α) = {ψω | ω JαK }. Then given two formulae α and β, let us denote by lpdnf(α | β) the subset of lpdnf(α) defined as lpdnf(α | β) = {ψω lpdnf(α) | ψω |=LP β}. Let us simply denote by W lpdnf(α | β) the formula W{ψω | ψω lpdnf(α | β)}. From the semantical point of view, the representative set of the formula W lpdnf(α | β) (when defined) precisely corresponds to the LP models in the representative set of α which are LP models of β.

Proposition 3. Assume that lpdnf(α | β) = . Then JW lpdnf(α | β)K = JαK JβK.

And as a direct consequence of the definition of lpdnf(α | β) and Proposition 3, we get:

Corollary 3. lpdnf(α | β) = iff JαK JβK = .

We are now ready to define our expansion operator, which we call LP+expansion:

Definition 4. The LP+expansion of α by β, denoted by α +LP β is defined as

α +LP β = W lpdnf(α | β), if lpdnf(α | β) = , P S, otherwise.

When lpdnf(α | β) = we say that α +LP β is conclusive.

Example 1. Let us illustrate this difference in behaviour between conjunction and LP+expansion with a simple example. Consider a formula α such that JαK = {01BB, 1111}. Now Jα +LP ψ{0111}K = Jψ{01BB}K, whereas Jα ψ{0111}K = Jψ{01BB,B111}K. And Jα +LP ψ{0BBB}K = J P SK, whereas Jα ψ{0BBB}K = Jψ{0BBB}K.

As we will have to deal with representative worlds, we have to define a (strong) inference relation between formulae that takes into account these worlds only.

Definition 5. The strong LP inference relation, denoted by |=LP , is the relation on LP S LP S defined for all formulae α, β as: α |=LP β iff lpdnf(α) lpdnf(β).

Obviously enough, this inference relation |=LP can be semantically characterized in terms of inclusion between representative sets:

Remark 1. α |=LP β iff JαK JβK .

We are now ready to give a translation of the AGM expansion postulates in this setting. In the following postulates we will use strong LP inference to compare the belief bases of the agent, in order to be able to focus on the conservation of representative worlds. Whereas we use (standard) LP inference to look at (all) the consequences of these bases. Definition 6. An operator + : LP S LP S LP S is an LPexpansion operator if is satisfies the following properties:

(K+2) ϕ + α |=LP α (K+3) ϕ + α |=LP ϕ (K+4) If ϕ |=LP α, then ϕ + α LP ϕ

(K+5) If ϕ |=LP ψ, then ϕ + α |=LP ψ + α (K+6) If + satisfies (K+2)-(K+5), then ϕ + α |=LP ϕ + α These postulates are an adaptation of the AGM expansion postulates for this setting where some LP models are more important than others. As in the standard AGM framework there is a unique operator satisfying these postulates: Proposition 4. The LP+expansion +LP is the only LPexpansion operator.

Reasonable LP Revision Based on the notion of LP-expansion, which we denote simply by + in the following (since it is unique), we propose the following new set of postulates for LP revision: Definition 7. A revision operator is an LP revision operator if it satisfies the following postulates:

(LP1) ϕ µ |=LP µ (LP2) If ϕ + µ is conclusive, then ϕ µ LP ϕ + µ (LP4) If ϕ LP ϕ and µ LP µ , then ϕ µ LP ϕ µ

(LP5) (ϕ µ) + µ |=LP ϕ (µ µ ) (LP6) If (ϕ µ) + µ is conclusive, then ϕ (µ µ ) |=LP (ϕ µ) + µ

These postulates are similar to the original KM ones, except that we use the correct notion of expansion in this setting. We did not add a translation to (R3) since as we previously explained, its direct translation is trivially true in LP. But we will discuss an adaptation of (R3) in the next section. Let us now give a representation theorem for these operators. Definition 8. An LP faithful assignment is a mapping ϕ 7 ϕ which associates every formula ϕ with a preorder over LP worlds and which satisfies the following conditions:

(L1) If ω, ω JϕK , then ω ϕ ω

(L2) If ω JϕK and ω / JϕK , then ω ϕ ω

(L3) If ϕ LP ϕ then ϕ= ϕ

Proposition 5. An operator is an LP revision operator if and only if there is an LP faithful assignment ϕ 7 ϕ associating every formula with a total preorder over LP worlds such that for all formulae ϕ, µ, ϕ µ LP ψmin(JµK, ϕ). So, as in the classical case, there is a whole family of sensible revision operators, which can be defined as a selection of the most plausible (LP) possible worlds.

Adaptation of (R3) (R3) requires that the result of the revision has to be consistent whenever the new piece of information is consistent. As all formulae are LP-consistent, a direct translation of (R3) into our LP setting would always be trivially satisfied. Nonetheless, one could expect the fact that if the new piece of information is consistent, then the result should be consistent. In fact, such a property would be both too strong and too weak. So we will look for a more adequate version of it. To see that it is too strong, one has to realize that two formulae that are equivalent in classical logic are not always so in LP. In the following example, we show that revising a consistent base by a consistent new information does not lead to a consistent result.

Example 2. Let α1 = p q and α2 = p ( p q). Remark that in classical logic these two formulae are equivalent. This is no longer the case in LP, since Jα1K = {11}, whereas Jα2K = {11, B0}. Indeed, in LP logic there is a possible LP world in α2 where the variable p is inconsistent and q is false (i.e., the LP world B0), which is not an LP model of α1. Then it can be perfectly sensible to expect the revision by q to give different results in these two cases, for instance obtaining Jα1 q K = {10} and Jα2 q K = {B0}. Remark that α2 q is not consistent, whereas both α2 and q are. On the other hand, (R3) focuses on (fully) consistent cases (i.e., where the models are classical ones). But consider for instance a (almost consistent) case with ten propositional variables, with only one variable having a B value in all (representative) models of the base and the new information, all the other ones having classical truth values. Then we could expect an (R3)-like postulate to force those other variables to remain classical. It is this property that we intend to formalize now. Given an LP world ω Ω , we denote by ω! the set of inconsistent variables in ω, i.e., ω! = {xi PS | ω(xi) = B}. Given X PS, a formula α is said to be strongly Xconsistent whenever ω! X for all ω such that ω JαK . Obviously enough, strong PS-consistency implies (classical) consistency. The converse statement does not hold, e.g., the formula α = p ( p q) is consistent, but JαK = {11, B0}, thus α is not strongly PS-consistent. Definition 9. An LP revision operator is said to be strong if it satisfies the following additional postulate: (LP3) If ϕ is strongly X-consistent and µ is strongly Xconsistent, then ϕ µ is strongly X-consistent

This postulate ensures that if some propositional variables have consistent truth values in the (representative set of the) beliefs and in the (representative set of the) new information, then they will have consistent truth values in the (representative set of the) revised beliefs. Definition 10. An LP faithful assignment ϕ 7 ϕ is said to be strong if it satisfies the following additional condition: (S) If ϕ is strongly X-consistent, ω! X, ω ! X = and ω <LP ω , then there exists ω s.t. ω ! X, ω LP ω , ω ϕ ω , and (ω LP ω = ω ϕ ω )

This condition states that if the beliefs are strongly Xconsistent, then any possible world that does not comply with X (i.e., x X s.t. ω(x) = B) is worse than some more classical possible world that complies with X. We can now state the representation theorem for strong LP revision operators: Proposition 6. An operator is a strong LP revision operator if and only if there is a strong LP faithful assignment ϕ 7 ϕ associating every formula with a total preorder over LP worlds such that for all formulae ϕ, µ, ϕ µ LP ψmin(JµK, ϕ). Condition (S) of a strong LP faithful assignment characterizes (LP3) for LP revision operators. But as it may be difficult to check, it can be useful to consider a simpler (stronger) version of this condition:

(C) If ϕ is strongly X-consistent, ω! X and ω ! X = , then ω ϕ ω

This condition states that if the beliefs are strongly Xconsistent, then all possible worlds that do not comply with X are worse than all worlds that comply with X.

Proposition 7. If ϕ 7 ϕ is an LP faithful assignment which satisfies (C), then it satisfies (S).

Let us show that strong LP revision operators can be seen as an extension of classical AGM/KM revision operators. First, let us recall that strong PS-consistency implies (classical) consistency, but not conversely. However, the DNF of every consistent formula α is a formula which is classically equivalent to α and is strongly PS-consistent3:

Proposition 8. If α is consistent, then dnf(α) is strongly PS-consistent.

Notice that for classical revision operators we have that ϕ α dnf(ϕ) α. This is a consequence of (R4). Now we can show that:

Proposition 9. For every KM revision operator , there exists a strong LP revision operator such that for every consistent formula ϕ and every formula µ, we have that ϕ µ dnf(ϕ) µ.

So, the class of strong LP revision operators can be seen as a safe extension of classical AGM/KM revision operators. Some strong LP revision operators behave exactly as classical AGM/KM revision on consistent formulae, while giving non-trivial results on inconsistent formulae.

Distance-Based LP Revision Operators Let us now investigate how to generalize Dalal revision (Dalal 1988), and more generally, distance-based revision operators into this LP logic setting.

Definition 11. Let d be a mapping Ω Ω 7 R+ such that d(ω, ω ) = 0 if and only if ω = ω . The distance-based LP revision operator db is defined for all formulae ϕ, µ by ϕ db µ = ψmin(JµK, d ϕ), where d ϕ is a total preorder over LP worlds induced by ϕ and defined by:

ω d ϕ ω if and only if d(ω, ϕ) d(ω , ϕ) d(ω, ϕ) = minω JϕK d(ω, ω ),

Note that the distance is computed from the representative models of the base. Moreover, d is not required to satisfy the properties of symmetry and triangular inequality of standard metrics. For convenience, such a mapping d will be called a distance in the following, since it generalizes well-known distance-based operators.

Proposition 10. Every distance-based LP revision operator is an LP revision operator, i.e., it satisfies (LP1), (LP2), (LP4), (LP5), and (LP6).

One of the most natural ways to define a distance d is to take advantage of existing distances in the classical case, like the Hamming distance d H, defined as

3Note that for a consistent formula α, dnf(α) = ψ[α].

d H(ω, ω ) = P x P S d H b (ω(x), ω (x)), where d H b is defined by d H b (ω(x), ω (x)) = 0 if ω(x) = ω (x), otherwise d H b (ω(x), ω (x)) = 1. In the classical case, this distance induces a revision operator which corresponds to the Dalal revision operator (Dalal 1988)4. We will study similar distance definitions in our LP setting, so let us put it formally: Definition 12. A decomposable distance between LP worlds is a mapping Ω Ω 7 R+ defined for all LP worlds ω, ω as d(ω, ω ) = P x P S db(ω(x), ω (x)), where db is a mapping {0, 1, B}2 7 R+ satisfying db(ω(x), ω (x)) = 0 if and only if ω(x) = ω (x). Since a decomposable distance d is fully characterized by db, one denotes by db the induced LP distance-based revision operator. It can be easily seen that every operator db is indeed a distance-based LP operator according to Definition 11. Let us see what kind of properties could make sense for the db mapping. First, let us remark that symmetry is not a natural requirement in our setting. For instance, one may want in some cases to favor classical truth values (true and false) over the inconsistent one, e.g., to ask that db(0, B) = db(B, 0). But a sensible requirement is to be neutral with respect to the classical values true and false, i.e., to decomposable distances that are 0-1 symmetric , i.e., such that db(0, B) = db(1, B), db(B, 0) = db(B, 1), and db(0, 1) = db(1, 0). Now, since in the classical case 2-valued worlds are considered, to define an operator based on a 0-1 symmetric decomposable distance the only reasonable choice for db is to define db(0, 1) = db(1, 0) = 1, which defines the Dalal operator (taking any positive value other than 1 defines the same operator). But in our setting, with 3-valued interpretations, there is more room for non-trivial choices. Still, by setting the distance between the classical values to the reference value 1 (i.e., db(0, 1) = db(1, 0) = 1) and since db(ω(x), ω(x)) = 0 by definition, we already require that: db(0, 0) = db(1, 1) = db(B, B) = 0 db(0, 1) = db(1, 0) = 1 So one is left with a choice on the remaining values: db(0, B) = db(1, B) = d01 B db(B, 0) = db(B, 1) = d B 01 But it turns out that the choice for d01 B does not matter: Proposition 11. Let db, d b be such that d B 01 = d B 01. Then db = d b. So an operator db based on a 0-1 symmetric decomposable distance is in fact characterized by a single value: the value d B 01. We know from Proposition 10 that whatever the choice of this value, the obtained operator will satisfy all required postulates. But the exact value will determine the exact behaviour of the operator. In particular the choice of d B 01 < 1, so d B 01 < db(0, 1) = db(1, 0), will give rise to operators that always

4In his paper (Dalal 1988), Dalal defines his operator by means of formula dilation (Bloch and Lang 2002), but it can also be defined using the Hamming distance between worlds.

prefer to change the valuation of a propositional variable to B instead of the classical truth values 0 and 1. Conversely the choice of d B 01 > |PS| will force the best possible worlds to be the most classical ones (since the price to pay for a B value will be too high). And choosing an intermediate value (1 d B 01 |PS|) gives rise to operators that more or less favor classical truth values with respect to the B value, so one can choose the cost of not being consistent. Now let us show that there is only one operator with d B 01 < 1, and similarly there is a unique operator with d B 01 > |PS|: Proposition 12. 1. Let db, d b be such that d B 01 < 1 and d B 01 < 1. Then db = d b. 2. Let db, d b be such that d B 01 > |PS| and d B 01 > |PS|. Then db = d b.

Since values d B 01 < 1 define the same operator, let us denote it by dinf. Likewise, the values d B 01 > |PS| define the operator denoted by dsup. So, intuitively, when defining an operator, one would rather choose a lower value for d B 01 when one is more reluctant to change, or stated equivalently, more tolerant to inconsistencies. In the most change-reluctant cases, in particular for dinf, one would expect the underlying operators not to be inclined to any change at all, giving as output a revised formula ϕ µ which always entails ϕ. Note that whereas this is not a desired behaviour in the classical setting where consistency must be preserved in all cases (cf. (R3)), this property is perfectly acceptable (although not necessary) in our LP setting. Let us call this property persistence : (Per) ϕ µ |=LP ϕ It turns out that, among the class of all operators based on a 0-1 symmetric decomposable distance, the operator dinf is the only operator satisfying (Per): Proposition 13. An operator db based on a 0-1 symmetric decomposable distance satisfies (Per) if and only if db = dinf. But, as our work shows, this is the simplest of all possibilities. And in fact all the remaining operators db, i.e., when d B 01 1 are strong LP revision operators: Proposition 14. An operator db based on a 0-1 symmetric decomposable distance satisfies (LP3) if and only if d B 01 1. Actually, the operator dsup can be characterized by an additional interesting property: (LP3 ) If ϕ is strongly PS-consistent and µ is consistent, then ϕ µ is strongly PS-consistent Proposition 15. An operator db based on a 0-1 symmetric decomposable distance satisfies (LP3 ) if and only if db = dsup. So the operator dsup forces the result of the revision to be consistent whenever it is possible. The postulates (LP3 ) and (LP3) are two adaptations of (R3) in our framework. Note that there can be other interesting ones.

Let us illustrate the (differences in) behaviour of these operators on the following example:

Example 3. Consider first the following worlds: ωϕ = 000000000000 ω1 = 0000000BBBBB ω2 = 1000000BBBB0 ω3 = 1110000BB000 ω4 = 111111100000 ω5 = B000000BBBB0 ω6 = BBB0000BB000 Now, let ϕ and µ be two formulae such that JϕK = {ωϕ} and JµK = {ω1, ω2, ω3, ω4}. Let d1 B 01 = 1 and d2 B 01 = 2. We get that ϕ dinf µ = {ω1, ω5, ω6}, ϕ d1 B 01 µ = {ω1, ω2, ω3}, ϕ d2 B 01 µ = {ω3, ω4}, and ϕ dsup µ = {ω4}.

Accordingly, the higher the value of d B 01, the more classical the result of the revision of ϕ by µ.

Related Work

There is a few related work on revision on paraconsistent logics. The first approach we are aware of is (da Costa and Bueno 1998), which contains an extensive discussion on why belief revision in paraconsistent logics makes perfect sense. It uses da Costa Cn logics, but does not go further than discussing the standard AGM postulates in this setting. In (Mares 2002) the author works with a dedicated logic R, where an additional structure is required to guide the revision process, and no link is made with the standard approach. In (Priest 2001) the proposed operator used a complex process using different criteria to rank all bases considered as potential solutions. This paper also discussed which are the AGM postulates satisfied by this operator. In (Girard and Tanaka 2016) the authors use LP logic, like us, but they defined two particular operators, corresponding to Segerberg s irrevocable revision (Segerberg 1998) and to Nayak s lexicographic revision (Nayak 1994) on 3-valued interpretations. Their operators are defined using dynamic epistemic logic, and they do not study the links with AGM postulates. Note that none of these works provide a representation theorem, and none of them safely extend the classical AGM/KM framework. The only two works that we are aware of where the authors provide representation theorems are (Testa, Coniglio, and Ribeiro 2017) and (Testa et al. 2018). But in both cases they use a logic with an explicit consistency connector, and the theorems are set for the basic postulates only, not for the full set of AGM postulates.

In this work we discussed how to adapt the AGM/KM postulates when the underlying logic is Priest s LP logic, in order to model a rational change, as a conservative extension of AGM/KM belief revision. This implied in particular to adequately adapt the notion of expansion. We provided a representation theorem and some examples of belief revision operators in this setting. We hope that this work will allow to rethink the definition of revision as rational change instead of as consistent change, and will be applied to frameworks where some beliefs are more important/fundamental than others.

Acknowledgements This work has benefited from the support of the AI Chair BE4mus IA of the French National Research Agency (ANR20-CHIA-0028) and of the JSPS KAKENHI Grant Number JP20K11947. The third author has also been partially funded by the program PAUSE of Coll ege de France.

References Alchourr on, C. E.; G ardenfors, P.; and Makinson, D. 1985. On the logic of theory change: partial meet contraction and revision functions. Journal of Symbolic Logic, 50: 510 530. Alchourr on, C. E.; and Makinson, D. 1985. On the logic of theory change: safe contraction. Studia Logica, 44(4): 405 422. Benferhat, S.; Lagrue, S.; and Papini, O. 2005. Revision of partially ordered information: axiomatization, semantics and iteration. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI 05), 376 381. Bloch, I.; and Lang, J. 2002. Towards mathematical morpho-logics, 367 380. Heidelberg: Physica-Verlag HD. Booth, R.; Ferm e, E.; Konieczny, S.; and Pino P erez, R. 2012. Credibility limited revision operators in propositional logic. In Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR 12), 116 125. Booth, R.; Ferm e, E.; Konieczny, S.; and Pino P erez, R. 2014. Credibility-limited improvement operators. In Proceedings of the 21st European Conference on Artifical Intelligence (ECAI 14), 123 128. B eziau, J.-Y.; Carnielli, W. A.; and Gabbay, D. M. 2007. Handbook of paraconsistency. Studies in logic. College publications. da Costa, N. C.; and Bueno, O. 1998. Belief change and inconsistency. Logique et Analyse, 41(161/163): 31 56. Dalal, M. 1988. Investigations into a theory of knowledge base revision: preliminary report. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI 88), 475 479. Dubois, D.; Lang, J.; and Prade, H. 1994. Handbook of Logic in Artificial Intelligence and Logic Programming, volume 3 : Nonmonotonic Reasoning and Uncertain Reasoning, chapter Possibilistic Logic. Oxford Science Publications. Dubois, D.; and Prade, H. 1991. Epistemic entrenchment and possibilistic logic. Artificial Intelligence, 50: 223 239. Falappa, M. A.; Kern-Isberner, G.; Reis, M. D. L.; and Simari, G. R. 2012. Prioritized and non-prioritized multiple change on belief bases. Journal of Philosophical Logic, 41(1): 77 113. Ferm e, E.; and Hansson, S. O. 2011. AGM 25 years: twentyfive years of research in belief change. Journal of Philosophical Logic, 40(2): 295 331. Gabbay, D. M.; and Hunter, A. 1991. Making inconsistency respectable: a logical framework for inconsistency in reasoning. In International Workshop on Fundamentals of Artificial Intelligence Research (FAIR 91), 19 32.

Garapa, M.; Ferm e, E.; and Reis, M. D. L. 2020. Credibilitylimited base revision: new classes and their characterizations. Journal of Artificial Intelligence Research, 69: 1023 1075. G ardenfors, P. 1988. Knowledge in flux. MIT Press. G ardenfors, P. 1990. Belief revision and nonmonotonic logic: two sides of the same coin? In Proceedings of the 9th European Conference on Artificial Intelligence (ECAI 90), 768 773. Girard, P.; and Tanaka, K. 2016. Paraconsistent dynamics. Synthese, 193(1): 1 14. Hansson, S.; Ferme, E.; Cantwell, J.; and Falappa, M. 2001. Credibility limited revision. Journal of Symbolic Logic, 66(4): 1581 1596. Hansson, S. O. 1998. What s new isn t always best. Theoria, 1 13. Special issue on non-prioritized belief revision. Hansson, S. O. 1999. A textbook of belief dynamics. Theory change and database updating. Kluwer. Katsuno, H.; and Mendelzon, A. O. 1991. Propositional knowledge base revision and minimal change. Artificial Intelligence, 52: 263 294. Konieczny, S.; Medina Grespan, M.; and Pino P erez, R. 2010. Taxonomy of improvement operators and the problem of minimal change. In Proceedings of the 12th International Conference on Principles of Knowledge Representation and Reasoning (KR 10), 161 170. Konieczny, S.; and Pino P erez, R. 2002. Merging information under constraints: a logical framework. Journal of Logic and Computation, 12(5): 773 808. Konieczny, S.; and Pino P erez, R. 2008. Improvement operators. In Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR 08), 177 187. Konieczny, S.; and Pino P erez, R. 2011. Logic based merging. Journal of Philosophical Logic, 40(2): 239 270. Kraus, S.; Lehmann, D.; and Magidor, M. 1990. Nonmonotonic reasoning, preferential models and cumulative logics. Artificial Intelligence, 44: 167 207. Lehmann, D.; and Magidor, M. 1992. What does a conditional knowledge base entail? Artificial Intelligence, 55(1): 1 60. Makinson, D. 1998. Screened revision. Theoria, 14 23. Special issue on non-prioritized belief revision. Mares, E. D. 2002. A paraconsistent theory of belief revision. Erkenntnis, 56(2): 229 246. Nayak, A. C. 1994. Iterated belief change based on epistemic entrenchment. Erkenntnis, 41(3): 353 390. Priest, G. 1979. The logic of paradox. Journal of Philosophical Logic, 8(1): 219 241. Priest, G. 1991. Minimally inconsistent LP. Studia Logica, 50: 321 331. Priest, G. 2001. Paraconsistent belief revision. Theoria, 67(3): 214 228. Priest, G. 2002. Paraconsistent logic, 287 393. Springer Netherlands.

Revesz, P. Z. 1993. On the semantics of theory change: arbitration between old and new information. In Proceedings of the 12th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Databases, 71 92. Schwind, N.; and Konieczny, S. 2020. Non-prioritized iterated revision: improvement via incremental belief merging. In Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning (KR 20), 738 747. Schwind, N.; Konieczny, S.; and Marquis, P. 2018. On belief promotion. In Proceedings of the 16th International Conference on the Principles of Knowledge Representation and Reasoning (KR 18), 297 307. Segerberg, K. 1998. Irrevocable belief revision in dynamic doxastic logic. Notre Dame Journal of Formal Logic, 39(3): 287 306. Testa, R.; Ferm e, E.; Garapa, M.; and Reis, M. 2018. How to construct remainder sets for paraconsistent revisions: preliminary report. In 17th International Workshop on Non Monotonic Reasoning (NMR 18). Testa, R. R.; Coniglio, M. E.; and Ribeiro, M. M. 2017. AGM-like paraconsistent belief change. Logic Journal of the IGPL, 25(4): 632 672.