Didier Dubois
email: dubois@irit.fr

Henri Prade
email: prade@irit.fr

A possibilistic analysis of inconsistency

Central in standard possibilistic logic (where propositional logic formulas are associated with lower bounds of their necessity measures), is the notion of inconsistency level of a possibilistic logic base. Formulas whose level is strictly above this inconsistency level constitute a sub-base free of any inconsistency. Some extensions, based on the notions of paraconsistent completion of a possibilistic logic base, and of safely supported formulas, have been proposed for handling formulas below the level of inconsistency. In this paper we further explore these ideas, and show the interest of considering the minimal inconsistent subsets in this setting. Lines for further research are also outlined.

Introduction

Reasoning under inconsistency [START_REF] Rescher | On inference from inconsistent premises[END_REF][START_REF]Reasoning with Actual and Potential Contradictions[END_REF], or evaluating the inconsistency of a knowledge base [START_REF] Hunter | On the measure of conflicts: Shapley inconsistency values[END_REF][START_REF] Jabbour | Prime implicates based inconsistency characterization[END_REF] have raised a lot of interest in artificial intelligence for a long time. However, the different approaches which have been proposed do not usually take into account the fact that all the formulas a knowledge base are not necessarily equally certain. Possibilistic logic [START_REF] Dubois | Possibilistic logic[END_REF] provides a simple way for a partial handling of inconsistency by taking advantage of a stratification of the knowledge base according to the certainty level associated to the logical formulas. Then we can compute an inconsistency level for a propositional knowledge base, and all the formulas whose certainty is strictly above this inconsistency level form a consistent sub-base. The formulas whose certainty is equal to or smaller than the inconsistency level remain drown in inconsistency, including formulas that are not involved in any minimal inconsistent subsets. This state of fact can be somewhat remedied by defining a paraconsistent completion of the knowledge base, and by using a so-called safely supported entailment relation [START_REF] Benferhat | Reasoning in inconsistent stratified knowledge bases[END_REF][START_REF] Benferhat | An overview of inconsistency-tolerant inferences in prioritized knowledge bases[END_REF]. Strangely enough, this entailment is more productive than the possibilistic logic entailment, but it nevertheless preserves the consistency of the set of consequences. Yet it has remained largely ignored. This short paper revisits the approach and shows its relation with minimal inconsistent subsets.

The paper is structured as follows. Section 2 deals with the flat case [START_REF] Benferhat | Some syntactic approaches to the handling of inconsistent knowledge bases: A comparative study. The flat case[END_REF] where formulas are not associated with certainty levels. We present the idea of paraconsistent completion as a basis for analyzing the conflicts, and then identify the safely supported consequences. In Section 3, we deal with possibilistic logic formulas, and extend the previous definitions. Then a new characterization of safely supported entailment is proposed. Lines for further research are also discussed.

Flat propositional knowledge bases

Let Σ = {p i | i = 1, . . . , n} denote a propositional logic knowledge base. Σ may be inconsistent. Let us first recall two basic notions, needed in the forthcoming discussion: the notions of support for a proposition and of minimal inconsistent subset. A Σ-based support (or reason, or argument) for a proposition p is a subset S p of propositions in Σ such that i) S p is consistent; ii) S p ⊢ p (where ⊢ is the classical logic consequence relation); iii) ∄S ′ ⊂ S p such that S ′ ⊢ p. In other words, S p is a minimal consistent subset of propositions in Σ that together entail p. Likewise, a minimal inconsistent subset of Σ is a minimal subset of propositions that entail ⊥: a non empty subset

S ⊥ of Σ such that i) S ⊥ is inconsistent (S ⊥ ⊢ ⊥); ii) ∄S ′ ⊂ S ⊥ such that S ′ ⊢ ⊥.
For a complete analysis of the inconsistency situation of formulas in Σ, we need to define the "paraconsistent completion" Σ comp of Σ.

Paraconsistent completion

For analyzing the potential conflicts in Σ, it is convenient to proceed with the following construction. The paraconsistent completion Σ comp of Σ is obtained by applying the following procedure: to each formula p i in Σ, one associates i) the set of reasons for p i , and ii) the set of reasons for ¬p i . More formally,

Σ comp = {(p i , {P 1 , • • •, P r }, {C 1 , • • •, C s }) | p i ∈ Σ, P i is a reason for p i , C j is a reason for ¬p i }. Clearly, if p i ∈ Σ, then (p i , {P 1 ,• • •, P r }, {C 1 ,• • •, C s }) ∈ Σ comp , and if ∃j s.t. p j ≡ ¬p i then (¬p i , {P ′ 1 , • • • , P ′ s }, {C ′ 1 , • • • , C ′ r }) ∈ Σ comp with ∀i P ′ i = C i , ∀j C ′ j = P j .
Note that as soon as p i ∈Σ, the set of reasons for p i is not empty: it contains at least {p i }.

The reasons for and against p i can be summarized by triples of the form (p i , π i , γ i ) for i = 1, . . . , n where π i ∈ {0, 1}, γ i ∈ {0, 1}, and: i) p i ∈ Σ; ii) π i = 1 for acknowledging the fact that ∃P k , a reason for p i ; iii) γ i = 1 if ∃C l that is a reason for ¬p i , and γ i = 0 if ∄C l (no reason for ¬p i ). Let Σ para = {(p i , π i , γ i ) : i = 1, . . . , n}. Note that π i = 0 (hence = 1), since each p i ∈ Σ supports itself.

If min(π i , γ i ) = 1, then p i is said to be paraconsistent (in the sense of "conflicting"). Thus in Σ, there are two kinds of propositions, the formulas p i such as γ i = 0 which should be considered as true, and the formulas that are paraconsistent. Note that strictly speaking there is no formula of the form (p j , 0, 1) in Σ para since the information that p j is false appears there only under the form (¬p j , 1, 0), i.e. ¬p j is true. However, note also that one may have

(p i , {{p j }}, {C 1 ,• • •, C s }) ∈ Σ comp ,
where no C k contains ¬p j , which might be understood as suggesting that p j , being only supported by itself, is questionable. Besides, there is no formula of the form (p k , 0, 0) in Σ para (it would express that there is no reason for p k , nor for ¬p k ).

Safely supported propositions

Once Σ comp and Σ para are built from Σ, one can evaluate reasons S in favor of a proposition p by means of the two evaluations, Def (S) and U ns(F ), respectively revealing the potential weakness of its support and its lack of safety:

-Def (S) = min i {π i |(p i ,π i ,γ i )∈Σ para and p i ∈ S}. In fact, one always have Def (S) = 1 since ∀i, p i ∈ S, we have π i = 1, and the case Def (S) = 0 is impossible here since p i is in Σ (p i ∈ Σ is understood as (p i , 1)).

We shall see that when propositional formulas become weighted, we still always have Def (S) > 0, but Def (S) may be "close to 0".

-U ns(S) = max i {γ i |(p i ,π i ,γ i ) ∈ Σ para and p i ∈ S}. Clearly, U ns(S) = 0 if ∀i | p i ∈ S γ i = 0, i.e. if S does not contain any paraconsistent formula, while U ns(S) = 1 if ∃i | p i ∈ S γ i = 1, i.e. there is at least one paraconsistent formula in S. Thus, U ns(S) reflects if there are a reason pro and a reason against an element of S that can be both built from formulas in Σ.

A reason S in favor of proposition p is free iff Def (S) > U ns(S), i.e. iff all the formulas in S are believed to be true and none is inconsistent with other formulas in Σ. By extension, in this case, we shall say all the formulas in S are free as well. Moreover, any formula in a minimal inconsistent subset S ⊥ = {r 1 , r 2 , • • • , r k } of Σ is not free, since S ⊥ \{r j } is consistent and ∀j, S ⊥ \{r j } ⊢ ¬r j . Thus, if ∃S ⊥ , r j ∈ S ⊥ ⊆ Σ then (r j , 1, 1) ∈ Σ para , i.e., r j is a paraconsistent formula in Σ. If a formula is involved in several minimal inconsistent subsets, one might think that this formula could be considered as more "paraconsistent" since there exists several distinct reasons against it. However, this looks debatable since a "basic" piece of information often used in inferences may have some chance to be, on the contrary, strongly established.

In the classical case, Def (S) > U ns(S) ⇔ U ns(S) = 0, since then Def (S) = 1. Thus, a proposition p is safely supported if it exists a reason S for it which is free. The safely supported propositions are just the consequences of the set of free ones. It follows that the set of safely supported formulas in Σ is always consistent. So in particular, p and ¬p cannot be both safely supported.

This departs from the so-called argumentative inference [START_REF] Benferhat | Argumentative inference in uncertain and inconsistent knowledge base[END_REF], which is more adventurous than the safely supported inference, since it may lead to an inconsistent set of conclusions, but not to direct contradictions such as p and ¬p. The argumentative inference amounts to conclude p if there is a reason for p and no reason for ¬p in Σ.

For instance, consider the base Σ = {r, ¬r ∨ p, ¬r, r ∨ q}. Then, we can infer both p and q argumentatively from Σ. In contrast, the reader can check that Σ para = {(r, 1, 1), (¬r, 1, 1), (¬r ∨p, 1, 0), (r ∨q, 1, 0)}, from which one can infer neither that p nor q is safely supported (in fact, no formula is free). Still, as recalled in the discussion section, one can also infer (p, 1, 1) and (q, 1, 1) from Σ para , thus acknowledging that p and q are indeed paraconsistent conclusions.

We now examine how the notions of reason, of paraconsistent completion, and of safely supported proposition can become graded.

Possibilistic logic bases

We now assume that the propositions that are elements of a reason supporting a proposition may be pervaded with uncertainty. More precisely, the propositions p i are now replaced by possibilistic logic formulas [START_REF] Dubois | Possibilistic logic[END_REF] of the form (p i , a i ), i.e., p i is believed with certainty at least a i , a i 's belonging to a linearly ordered, bounded scale

S = {s 1 = 1 > s 2 > • • • > s n+1 = 0}
, with top and bottom elements denoted by 1 and 0 respectively.

Let Σ = {(p i , a i ) | i = 1, • • • , m}
, where a i is the strength with which p i is believed to be true in Σ. The higher a i , the higher the strength. Thus, (p, a) is subsumed by (p, b) as soon as b > a. So, it is assumed that Σ does not contain both (p i , a i ) and (p j , a j ) with p i ≡ p j and a i = a j . Let Σ * = {p i | (p i , a i ) ∈ Σ}. Similarly, if S ⊆ Σ, S * denotes the set of propositions appearing in the possibilistic formulas in S without their weight. The set of propositions Σ * is not assumed to be consistent. In possibilistic logic, this amounts to say that the inconsistency level of Σ is strictly positive [START_REF] Dubois | Possibilistic logic[END_REF].

A subset S of Σ is said to be a reason for p iff i) S * is consistent; ii) ∃a > 0, S ⊢ π (p, a) where ⊢ π is the possibilistic logic entailment 1

; iii) ∄S ′ ⊂ S such that S ′ ⊢ π (p, b) with b > 0.
In other words, S is such that S * is a minimal consistent subset of propositions that entail p and a is the minimum of the weights of the formulas in S. a is the weight of the reason. Clearly there may exist distinct reasons S and S ′ (with S * = S ′ * ) for p in Σ. Thus the pair (S, (p, a)) is a (possibilistic) argument for p with strength a, with a = min{a i | (p i , a i ) ∈ S}.

Graded paraconsistent completions

On this basis, one can extend the completions Σ comp and Σ para to a possibilistic logic base Σ. Namely to each formula p i in Σ * , one may associate i) the set of reasons for p i , and the set of reasons for ¬p i , or ii) or only the weights of the best reason for p i and of the best reason for ¬p i .

More formally, the first one is defined by

Σ comp = {(p i , {P 1 , • • • , P r }, {C 1 , • • • , C s }) | (p i , a i ) ∈ Σ, P i is a (graded) reason for p i , C j is a (graded) reason for ¬p i }. The second completion is defined by Σ para = {(p i , π i , γ i ) | (p i , a i ) ∈ Σ, π i
is the greatest weight of a reason for p i in Σ, γ i is the greatest weight of a reason for ¬p i in Σ}.

Note that π i ≥ a i . Example. Σ = {(p, s 1 ), (¬p∨q, s 2 ), (¬p, s 3 ), (¬r, s 4 ), (r, s 5 ), (¬r∨q, s 6 )} (with s 6 > 0)

Then Σ para = {(p, s 1 , s 3 ), (¬p ∨ q, s 2 , 0), (¬p, s 3 , s 1 ), (¬r, s 4 , s 5 ), (r, s 5 , s 4 ), (¬r ∨ q, s 2 , 0)}.

Σ comp = {(p, {(p, s 1 )}, {(¬p, s 3 )}), (¬ p ∨ q, {(¬p ∨ q, s 2 )}, ∅), (¬p, {(¬p, s 3 ), {(p, s 1 )}), (¬r, {(¬r, s 4 )}, {(r, s 5 )}), (r, {(r, s 5 )}, {(¬r, s 4 )}), (¬r ∨ p, {{(p, s 1 ), (¬p ∨ q, s 2 )}, {(¬r, s 4 )}}, ∅)}.

Graded safely supported propositions

The notion of safely supported proposition then extends to possibilistic propositional formulas with weights. Once Σ para is built from Σ, one can evaluate reasons S in favor of p i in the following way, by means of the two measures [START_REF] Benferhat | Reasoning in inconsistent stratified knowledge bases[END_REF][START_REF] Benferhat | An overview of inconsistency-tolerant inferences in prioritized knowledge bases[END_REF]:

-

Def (S) = min{π i | ((p i , π i , γ i ) ∈ Σ para and p i ∈ S * }. -U ns(S) = max{γ i | ((p i , π i , γ i ) ∈ Σ para and p i ∈ S * } Def (S)
reflects the less certain belief in S, U ns(S) the most strongly attacked belief in S. Note that we always have Def (S) > 0, but Def (S) may be equal to s n , and thus now "close to 0".

A reason is free iff Def (S) > U ns(S), i.e. iff its certainty is above the strength of the strongest attack. Then a proposition p is safely supported if it exists a reason S that is free for it. It can be shown [START_REF] Benferhat | An overview of inconsistency-tolerant inferences in prioritized knowledge bases[END_REF] that the set of safely supported consequences of a base Σ is always consistent. So in particular, p and ¬p cannot be both safely supported.

It clearly generalizes the case of a binary scale, i.e. a scale S with only two levels 1 and 0 , (where the condition Def (S) > U ns(S) can only hold under the form U ns(S) = 0), which means that all the formulas in S are fully believed and none is attacked. In the graded case, the formulas involved in S are only more believed than they are attacked.

Let us come back to minimal inconsistent subsets. Let S be a minimal inconsistent subset in Σ * , and let inc(S) = min{a j | (p j , a j ) ∈ Σ, p j ∈ S} be the level of inconsistency of S. Then, inc(Σ) = max{inc(S) : S minimal inconsistent subset of Σ}, where inc(Σ) = max{a | Σ π (⊥, a)} and π is the standard possibilistic entailment defined by possibilistic resolution [START_REF] Dubois | Possibilistic logic[END_REF]. Moreover, it appears that if (p i , π i , γ i ) ∈ Σ para , we have

γ i = max{inc(C k ) : (p i , a i ) ∈ Σ, p i ∈ C k , C k minimal inconsistent subset of Σ} with inc(C k ) = min{a j | (p j , a j ) ∈ Σ, p j ∈ C k }.
In fact we have the following result: the safely supported entailment from Σ coincides with the possibilistic entailment from the consistent possibilistic logic base Σ cons obtained from Σ by deleting, in all minimal inconsistent subsets S of Σ, the formulas with a certainty level equal to inc(S). Namely Σ cons = Σ\{(p i , a i ) | (p i , a i ) ∈ S, S minimal inconsistent subset of Σ, a i = inc(S)}.

Lines for further research

The construction of Σ comp and of Σ para is reminiscent of the motivations of Belnap for introducing his well-known four-valued logic [START_REF] Belnap | A useful four-valued logic[END_REF]. Belnap was considering several sources of information for which an atomic formula p may be known to be true, known to be false, or unknown. This may be naturally encoded by one of the four triples (p, 1, 0) (p is held for true according to sources), (p, 0, 1) (p is held for false according to sources), (p, 1, 1) (this is the paraconsistent case p is true according to some sources and false according to others), and (p, 0, 0) stands for the case where the truth status of p is unknown for sources. In Belnap's calculus (p, 1, 1) and (q, 0, 0) yields (p ∧ q, 0, 1), which may appear strange at first glance. As pointed out in [START_REF] Dubois | On ignorance and contradiction considered as truth-values[END_REF], this may be understood in the following way. On the one hand, we have both an argument in favor of p true and an argument in favor of p false. On the other hand we have no argument either in favor of q true or in favor of q false. This is enough to build an argument in favor of p ∧ q false (from the argument in favor of p false) and we cannot build any argument in favor of p ∧ q true (since one has no argument in favor of q true).

Yet, there already exists an extension of possibilistic logic inference that can be defined from Σ para (and then extended toΣ comp ). It is based on the following generalized resolution rule [START_REF] Dubois | Handling uncertainty, context, vague predicates, and partial inconsistency in possibilistic logic[END_REF] where the paraconsistency of formulas can be propagated

(¬p ∨ q, π 1 ,γ 1 ), (p ∨ r, π 2 ,γ 2 ) ⊢ (q ∨ r, min(π 1 ,π 2 ), max(γ 1 ,γ 2 )).
There is also another inference rule that holds in the logic of supporters [START_REF] Lafage | A logic of supporters[END_REF], a logic closely related to possibilistic logic, which corresponds to the case where there are no reasons against in Σ comp , and where the scale S is binary:

(¬p ∨ q, P 1 ), (¬p ∨ r, P 2 ) ⊢ (¬p ∨ r, P 1 ∪ P 2 ). This rule was proposed moreover in an ATMS-like perspective, where two kinds of literals are distinguished, as in the following example:

Example. Given Assumptions = {A, B, C}, and the knowledge base Σ = {(p, A), (q, B), (¬q ∨ p, C)}, p in Σ comp is then supported by two reasons, i.e., we have (p, {{A}, {B, C, }}, ∅).

Such inference rules may provide the starting point for reasoning directly in terms of arguments, and not only about arguments.

Concluding remarks

This short paper is intended to show that the benefit of taking into account the certainty levels of formulas when reasoning under inconsistency may be still much higher than the one already obtained by applying standard possibilistic logic where only formulas strictly above the inconsistency level of the knowledge base are salvaged. Indeed when inconsistency takes place, it is often due to the presence of formulas in which we are not fully confident. Considering minimal inconsistent subsets provides a local view of where the conflicts take place, and then the deletion of the less certain formulas inside these subsets enables us to restore consistency while keeping more information than with the standard possibilistic logic view.

Possibilistic inference is governed by the resolution rule (¬p ∨ q, a), (p ∨ r, b) ⊢π (q ∨ r, min(a, b))[START_REF] Dubois | Possibilistic logic[END_REF].