# inconsistency_measurement_for_paraconsistent_inference__eb7c95be.pdf

Inconsistency Measurement for Paraconsistent Inference

Yakoub Salhi CRIL, Universit e d Artois & CNRS, France salhi@cril.fr

One of the main aims of the methods developed for reasoning under inconsistency, in particular paraconsistent inference, is to derive informative conclusions from inconsistent bases. In this paper, we introduce an approach based on inconsistency measurement for deﬁning non-monotonic paraconsistent consequence relations. The main idea consists in adapting properties of classical reasoning under consistency to inconsistent propositional bases by involving inconsistency measures (IM). We ﬁrst exhibit interesting properties of our consequence relations. We then study situations where they bring about consequences that are always jointly consistent. In particular, we introduce a property of inconsistency measures that guarantees the consistency of the set of all entailed formulas. We also show that this property leads to several interesting properties of our IM-based consequence relations. Finally, we discuss relationships between our framework and well-known consequence relations that are based on maximal consistent subsets. In this setting, we establish direct connections between the latter and properties of inconsistency measures.

1 Introduction The main problem that we face in inconsistency handling is the principle of explosion. It is a law stating that any formula can be proven from a contradiction. This principle shows that classical inference deals with inconsistent bases as non informative. A logical consequence relation is said to be paraconsistent if it does not validate the principle of explosion (e.g. see [Middelburg, 2011; Arruda, 1980]). Inasmuch as it avoids to treat inconsistency as triviality, paraconsistency is appropriate for contradiction-tolerant reasoning and can be used for deriving useful information from inconsistent bases. Non-monotonic inference deals with the problem of deriving plausible conclusions with the possibility to retract them in conformity with new information (e.g. see [Kraus et al., 1990]). Many problems in artiﬁcial intelligence, such as argumentation, belief revision and planning, involve this type of reasoning. Although paraconsistent consequence relations

are usually monotonic, the deﬁnition of non-monotonic paraconsistent relations has received some attention in the literature according to different approaches. We can ﬁrst mention the relation proposed in [Rescher and Manor, 1970], which is based on the use of maximal consistent subsets to derive plausible conclusions. Other variants of this relation that are both non-monotonic and non-explosive have also been introduced in the literature (e.g. [Benferhat et al., 1993; Benferhat et al., 1997; Konieczny et al., 2019]). Moreover, using a three-valued semantics, the consequence relation of Priest s paraconsistent logic, called minimally inconsistent logic of paradox, is non-monotonic [Priest, 1991]. Inspired by Shoham s idea [Shoham, 1987; Shoham, 1988] of preferential models for making inferences, [Arieli and Avron, 2000] presented an approach that is also based on a multi-valued semantics for deﬁning non-monotonic paraconsistent relations. It is also interesting to mention the approach of adaptive logics that uses dynamic proof theories [Batens, 2013]. While all of these approaches have interesting properties, none of them can be considered as appropriate for reasoning about inconsistency in all situations. This explains the interest in continuing to investigate new approaches to pave the way for more applications of non-monotonic paraconsistent relations. In this work, we use the notion of inconsistency measure (e.g. see [Hunter and Konieczny, 2010]) as a stepping stone for deﬁning non-monotonic paraconsistent consequence relations. We show that our new approach can be seen as a simple and natural way to adapt properties of classical reasoning under consistency to inconsistent propositional bases. These properties concern the consistency of the consequence and the inconsistency of its negation in combination with the considered base. Additionally, our approach can greatly beneﬁt from the variety of inconsistency measures proposed in the literature. Indeed, plenty of proposals for measures and systems to deﬁne them have been made by considering different conﬂict forms (e.g. see [Grant and Hunter, 2013; Besnard, 2014; Thimm, 2016; Bona et al., 2018]). Our contribution is manifold. First, we introduce an IMbased framework for deﬁning three types of consequence relations. Second, because our consequence relations do not always bring about jointly consistent consequences, we propose a property, called DISJUNCT MINIMALITY, that, if satisﬁed by an inconsistency measure, guarantees that any consequence relation based on this measure always generates

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

consistent sets of formulas. Furthermore, we show that this property allows characterizing IM-based consequence relations closed under conjunction introduction, which means that this property is necessary in speciﬁc cases to avoid conﬂicts between the entailed formulas and provide a reasoning framework similar to classical logic. We also show that the measures that satisﬁes DISJUNCT MINIMALITY produce consequence relations that have desired properties of non-monotonic relations mentioned in [Gabbay, 1984; Kraus et al., 1990]. Finally, we discuss relationships between our consequence relations and some well-known relations that are based on the use of maximal consistent subsets (MCS) [Rescher and Manor, 1970; Benferhat et al., 1993]. In this context, we establish direct connections between properties of inconsistency measures and the considered MCSbased relations. In particular, we introduce a new property of inconsistency measures that allows characterizing skeptical reasoning.

2 Preliminary Deﬁnitions and Notations

Given a countable set of propositional variables Prop, a propositional formula φ has the form: φ ::= | p | φ | φ φ, where denotes false, p belongs to Prop, is the negation connective and the conjunction connective. The constant (true) and the connectives , and are deﬁned as usual in classical propositional logic. For the set of propositional formulas we write Form. Notationally, we use, possibly with subscripts and/or superscripts, the letters p, q and r to denote the propositional variables and the greek letters φ, ψ and χ to denote the propositional formulas. Moreover, given a formula φ (resp. a set of formulas S), we use V(φ) (resp. V(S)) to denote the set of propositional variables occurring in φ (resp. S). For the cardinality of a set S we write |S|. An interpretation w is a function from Prop to {0, 1}. It is inductively extended to the propositional formulas as follows: w( ) = 0, w( φ) = 1 w(φ) and w(φ ψ) = min(w(φ), w(ψ)). For the set of interpretations deﬁned over Prop we write WProp. A model of a formula φ is an interpretation w that makes φ true, that is, w(φ) = 1. The set of models of φ is denoted Mod(φ), that is, Mod(φ) := {w WProp : w(φ) = 1}. A formula is said to be consistent if it admits a model. Further, we say that a ﬁnite set of formulas S is consistent if its corresponding formula V φ S φ, written V S, is consistent; otherwise it is inconsistent. We use Inc(S) to refer to the set of inconsistent formulas that belong to S. A formula φ is said to be a logical consequence of a ﬁnite set of formulas S, written S φ, if Mod(V S) Mod(φ). For convenience, if S contains only one formula ψ, we write ψ φ instead of {ψ} φ. We use φ ψ if we have both φ ψ and ψ φ. Moreover, we write Eq(S, φ) for the set of formulas in S equivalent to φ, that is, {ψ S : ψ φ}. Two ﬁnite sets of formulas S and S are said to be bijection equivalent, written S b S , if there is a bijection f : S S such that φ f(φ) holds for each φ S. Clearly, b is an equivalence relation. In addition, given a set X of formulas (resp. of sets of formulas), we use X/ (resp. X/ b) to denote the quotient of X by (resp. b), that is, the set of

all equivalence classes of X w.r.t. (resp. b). A beliefbase is deﬁned as a ﬁnite set of formulas. For the set of beliefbases we write KForm.

Deﬁnition 1 (MIS). A minimal inconsistent subset (MIS) of a beliefbase K is a subset M of K such that M K, M , and for each φ M, M \ {φ} .

Deﬁnition 2 (MCS). A maximal consistent subset (MCS) of a beliefbase K is a subset M of K such that M K, M , and for each φ K \ M, M {φ} .

We use MCS(K) and MIS(K) to denote the set of all maximal consistent subsets and that of all minimal inconsistent subsets of K, respectively.

Deﬁnition 3 (Free Formula). A formula φ in a beliefbase K is said to be free in K if φ / M for every M MIS(K).

For the set of free formulas in K we write Free(K). A formula φ is said to be problematic in a beliefbase K if φ does not belong to Free(K). Among the inconsistency measures considered in this work, the measure IC, introduced in [Konieczny et al., 2003], is based on Priest s three-valued logic [Priest, 1991]. This logic has a semantics with an additional truth-value B representing intuitively both true and false. The three truthvalues are ranked as follows: 0 < B < 1. A three-valued interpretation w of a formula φ is a function from Prop to {0, B, 1}. It is extended to formulas as follows: w( ) = 0; w( φ) = 1 w(φ) if w(φ) {0, 1}, w( φ) = B otherwise; and w(φ ψ) = min(w(φ), w(ψ)). We use both(w) to denote the set {p Prop : w(p) = B}. A three-valued model of a formula φ is an interpretation w such that w(φ) = 0. For the set of three-valued models of φ we write 3VM(φ).

3 Inconsistency Measures

In this paper, we focus on the use of inconsistency measures for deﬁning consequence relations. An inconsistency measure is a function that allows quantifying the intensity of contradiction. Here, we consider a formal deﬁnition that takes into account speciﬁc rationality postulates introduced in the literature [Hunter and Konieczny, 2010; Besnard, 2014]. We write R+ for the set of positive real numbers augmented with a greatest element denoted .

Deﬁnition 4. An inconsistency measure is a function I : KForm R+ that satisﬁes the following properties for every K, K KForm and every φ, ψ Form:

CONSISTENCY: I(K) = 0 iff K ;

MONOTONICITY: if K K then I(K) I(K );

EQUIVALENCE: if φ ψ then I(K {φ}) = I(K {ψ}); and

TAUTOLOGY: if φ then I(K {φ}) = I(K).

CONSISTENCY states that an inconsistency measure must enable distinguishing between consistent and inconsistent beliefbases. MONOTONICITY says that the amount of conﬂicts cannot decrease by adding new formulas. EQUIVALENCE requires that equivalent formulas bring the same intensity of

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

contradiction. TAUTOLOGY decrees that tautologies do not impact inconsistency values. Note that there is a broad consensus in the literature on CONSISTENCY and MONOTONICITY, which is not the case of the two other properties. In our work, the beneﬁt of including EQUIVALENCE in the deﬁnition of inconsistency measure is to avoid deriving a formula and rejecting one of its equivalent formulas from the same beliefbase. Regarding TAUTOLOGY, it is used to prevent any change in the obtained consequences by adding tautologies. Let us mention that the literature is rich in more or less disputed postulates (e.g. see [Besnard, 2014; Ammoura et al., 2017; Thimm, 2018]). Among them, we are particularly interested in the following properties:

DOMINANCE: if φ and φ ψ then I(K {φ}) I(K {ψ});

FREE FORMULA: if φ Free(K) then I(K \ {φ}) = I(K);

EPENALTY: if φ K and φ / Free(K) then I(K \ Eq(K, φ)) < I(K).

The deﬁnition of EPENALTY is an adaptation of the property named PENALTY in the literature to take into account the presence of EQUIVALENCE in the deﬁnition of inconsistency measure. The three foregoing properties are particularly considered to point out their impact on the introduced IM-based consequence relations. Let us now recall speciﬁc inconsistency measures from the literature:

ID(K) = 1 if K , and ID(K) = 0 if K [Hunter and Konieczny, 2008];

IM(K) = |MIS(K)/ b| [Hunter and Konieczny, 2008];

IA(K) = |MCS(K)/ b|+α(K) 1, where α(K) = 1 if Inc(K) = , and α(K) = 0 if Inc(K) = [Grant and Hunter, 2011];

IP (K) = |(K \Free(K))/ | [Grant and Hunter, 2011];

IHS(K) = min{|H| : H S

φ K Mod(φ) and φ K,

w H, w(φ) = 1} 1 with min{} = [Thimm, 2016];

IC(K) = min{both(w) : w 3VM(K)} if Inc(K) = , and IC(K) = if Inc(K) = [Konieczny et al., 2003];

Imax Dalal(K) = min{max φ K d(Mod(φ), w) : w WProp}

[Grant and Hunter, 2017].

where d corresponds to the Dalal distance between interpretations deﬁned as follows: for all w, w WProp, d(w, w ) = |{p Prop : w(p) = w (p)}|. It is extended to sets of interpretations as follows: d(S, w) := min{d(w , w) : w S} if S = , d(S, w) := otherwise. Note that some of the measures above are adapted to satisfy EQUIVALENCE. For instance, the original versions of IM and IP count the number of minimal inconsistent subsets and the number of problematic formulas, respectively.

4 IM-based Consequence Relations

In the following, we present three types of consequence relations that involve inconsistency measurement. They are inspired by speciﬁc properties satisﬁed by the classical consequence relation under consistency.

Deﬁnition 5 (IM-based Consequence Relations). Let I be an inconsistency measure. The consequence relations 1 I, 2 I and 3 I are deﬁned as follows: for each K KForm and each φ Form,

K 1 I φ iff I(K { φ}) > I(K);

K 2 I φ iff I(K {φ}) = I(K) and I(K { φ}) > I(K);

K 3 I φ iff I(K { φ}) > I(K {φ}).

In order to motivate our approach, consider a consistent beliefbase K. For every formula φ, we have K φ if and only if K { φ} , which means that the negation of the consequence brings contradiction in a conﬂict-free beliefbase. Using the notion of inconsistency measure, this is extended to inconsistent beliefbases in a natural way by the relation 1 I, which says that a formula is a consequence if its negation brings new conﬂicts in the beliefbase. However, note that 1 I does not take into account the conﬂicts that may arise from the entailed formula. This explains the proposal of 2 I and 3 I. The consequence relation 2 I considers the additional property that the entailed formula must not bring any new conﬂict in the beliefbase. To some extent, it is similar to the fact that K {φ} results from K φ whenever K is consistent (the consequence keeps the beliefbase conﬂictfree). As regards the consequence relation 3 I, it is deﬁned by requiring that each entailed formula must bring less conﬂicts than its negation. Clearly, it is weaker than the relation 2 I. That is, for every beliefbase K and every formula φ, if K 2 I φ then K 3 I φ; the converse is not necessarily true. Moreover, the relation 1 I is weaker than both 2 I and 3 I. Notationally, for the set {φ Form : K i I φ} we write Cn(K, I, i).

Example 1. Consider the beliefbase K = {p q, p q, q q, r, r r, r q} and the inconsistency measure IM. We have IM(K) = 4. The formula q is free in K {q}, and it follows IM(K) = IM(K {q}) = 4. However, the MISes of K { q} are {p q, p q}, {q q}, {p q, q}, {r q, q}, { p q, q}, { r, r} and { r, r q}; hence, IM(K { q}) = 7 holds. Therefore, we obtain K 1 IM q, K 2 IM q and K 3 IM q. Additionally, I(K {p}) = 5 and I(K { p}) = 5 yield K 1 IM p, K 2 IM p and K 3 IM p. Moreover, K 1 IM r, K 2 IM r and K 3 IM r ensue from I(K {r}) = 5 and I(K { r}) = 6.

Note that the three consequence relations coincide in the case of the inconsistency measure ID. In fact, a formula φ is a logical consequence of a beliefbase K w.r.t. any consequence relation based on ID if and only if K and K φ. In other words, the consequence relation in this case is the most restrictive paraconsistent relation that preserve classical reasoning under consistency. (The relation that decrees that nothing is entailed from inconsistent beliefbases.)

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

We show below that our IM-based consequence relations preserve classical reasoning under consistency. This explains why our approach can be seen as an extension of the properties related to entailment under consistency mentioned previously. Note that we only need the postulate CONSISTENCY to show the following proposition. Proposition 1. Let I be an inconsistency measure. Then, for every K KForm such that K and every φ Form, we have K i I φ iff K φ for each i {1, 2, 3}.

Proof. We only consider the case of 1 I, the others being similar. Using CONSISTENCY and K , I(K) = 0 holds. Then, K 1 I φ iff I(K { φ}) > 0. Hence, in view of, again, CONSISTENCY, we obtain K 1 I φ iff K { φ} . We ﬁnally have K { φ} iff K φ.

The following proposition provides some common properties of the IM-based consequence relations. Proposition 2. The following properties are satisﬁed for every inconsistency measure I, every i {1, 2, 3} and every beliefbase K KForm: 1. there exists a formula φ s.t. K i I φ;

2. i I is non-monotonic;

3. for every φ K, K i I φ;

4. for every φ, ψ Form with φ ψ, K i I φ iff K i I ψ;

5. for every φ, ψ, χ Form with φ ψ, K {φ} i I χ iff K {ψ} i I χ. Property 1 says that there is no beliefbase where the IMbased consequence relations explodes into triviality; it ensues that these relations are paraconsistent for any inconsistency measure. Property 2 shows that all IM-based relations are non-monotonic (a consequence relation is monotonic if K ψ implies K {φ} ψ, for any formula φ). Property 3 states that it is not possible to entail the negation of a formula that belongs to the beliefbase. Properties 4 and 5 say that no difference is made between equivalent formulas. Note that non-monotonicity can be easily seen from the fact that we have {p} i I p (see Proposition 1) without having {p, p} i I p (Property 3). Now, we show that 2 I and 3 I prevent contradiction between consequences. Proposition 3. Let I be an inconsistency measure. Then, for every K KForm and every φ Form, K i I φ or K i I φ for i {2, 3}. The foregoing proposition is not satisﬁed by 1 I. Consider, for instance, the beliefbase K = {p q, p q}. Then, we obtain IM(K) = 1, IM(K {p}) = 2 and IM(K { p}) = 2. Consequently, IM(K {p}) > IM(K) and IM(K { p}) > IM(K) yield K 1 IM p and K 1 IM p. To illustrate the presence of relationships between IM properties and IM-based consequence relations, we point out in the proposition below the impact of Dominance. Proposition 4. Let I be an inconsistency measure that satisﬁes Dominance. Then, the following properties are satisﬁed for every i {1, 2, 3}, every K KForm, and every φ, ψ Form s.t. φ and φ ψ:

1. if K i I φ then K i I ψ, and

2. K {φ} i I ψ.

5 Consistent Consequence Relation

In the general case, our consequence relations do not bring about jointly consistent formulas. We discuss in this section an IM property, called DISJUNCT MINIMALITY, that guarantees the consistency of the associated consequence relations. It deals with disjunction and is satisﬁed by several inconsistency measures. We also show that this property allows characterizing IM-based consequence relations closed under conjunction introduction. This shows that DISJUNCT MINIMALITY is necessary in speciﬁc cases to avoid conﬂicts between entailed formulas and provide a reasoning framework similar to classical logic. Let us recall the compactness theorem that states that a set of formulas is satisﬁable if and only if all of its ﬁnite subsets are satisﬁable. This mainly allows us to deal with the satisﬁability of a set that corresponds to all consequences of a beliefbase. We deﬁne the property DISJUNCT MINIMALITY as follows: for every K KForm and every φ, ψ Form,

I(K {φ ψ}) min(I(K {φ}), I(K {ψ}))

It can be seen as the complement of the following property introduced in [Besnard, 2014]: I(K {φ ψ}) max(I(K {φ}), I(K {ψ})). The proposition below is a consequence of the fact that each (three-valued) interpretation satisﬁes φ ψ if and only if it satisﬁes φ or ψ.

Proposition 5. The inconsistency measures IC, IHS and Imax Dalal satisfy DISJUNCT MINIMALITY.

For the sake of illustration, let us show that IM does not satisfy DISJUNCT MINIMALITY. Consider the belief base K = {p p, p q, p q}. Then, IM(K) = 1 holds. However, we have I({p, p q, p q}) = 2 and I({ p, p q, p q}) = 2.

Theorem 1. Let I be an inconsistency measure that satisﬁes DISJUNCT MINIMALITY. Then, the consequence relations 1 I, 2 I and 3 I coincide.

Proof. We only need to show that 1 I 2 I, since we already have 2 I 3 I 1 I. Let K be a beliefbase and φ a formula s.t. K 1 I φ. Thus, I(K) < I(K { φ}) holds. Using TAUTOLOGY, we have I(K) = I(K {φ φ}). Then, using DISJUNCT MINIMALITY, we obtain I(K {φ φ}) min(I(K {φ}), I(K { φ})). Consequently, I(K) I(K {φ}) holds, which yields I(K) = I(K {φ}) (MONOTONICITY). Therefore, we have K 2 I φ.

For convenience, since 1 I, 2 I and 3 I coincide whenever I satisﬁes DISJUNCT MINIMALITY, we write I in this case to refer to the three relations.

Proposition 6. Let I be an inconsistency measure that satisﬁes DISJUNCT MINIMALITY. Then, for every beliefbase K, and every formulas φ and ψ, if K I φ and K I ψ then K I φ ψ.

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

Proof. Assume that K I φ and K I ψ. Then, I(K) < I(K { φ}) and I(K) < I(K { ψ}) ensue. We also have I(K { φ ψ}) min(I(K { φ}), I(K { ψ})). As a result, I(K) < I(K { φ ψ}) holds. Thus, we obtain K I φ ψ.

The following theorem states that requiring DISJUNCT MINIMALITY on the inconsistency measures used for deﬁning consequence relations always leads to jointly consistent consequences.

Theorem 2. Let I be an inconsistency measure that satisﬁes DISJUNCT MINIMALITY. Then, Cn(K, I, i) is consistent for every i {1, 2, 3} and every K KForm.

Proof. We need to show that every ﬁnite subset of Cn(K, I, i) is consistent. We proceed by contradiction. Assume that there exists an inconsistent ﬁnite subset S of Cn(K, I, i). Using Proposition 6, K I V S holds. Then, we have I(K) < I(K { V S}). Furthermore, TAUTOLOGY yields I(K) = I(K { V S}), and we obtain a contradiction.

A set of formulas S is said to be closed under conjunction introduction if for every φ, ψ S, φ ψ S.

Theorem 3. Let I be an inconsistency measure. If Cn(K, I, 1) is closed under conjunction introduction for every K KForm, then I satisﬁes DISJUNCT MINIMALITY.

Proof. Let K be a beliefbase, and φ and ψ two formulas. Suppose for the sake of contradiction that I(K {φ ψ}) < min(I(K {φ}), I(K {ψ})). Then, we have I(K {φ ψ}) < I(K {φ}) and I(K {φ ψ}) < I(K {ψ}). Using MONOTONICITY, I(K {φ ψ}) < I(K {φ ψ, φ}) and I(K {φ ψ}) < I(K {φ ψ, ψ}) ensue. Hence, we obtain K {φ ψ} 1 I φ and K {φ ψ} 1 I ψ. This leads to K {φ ψ} 1 I φ ψ since Cn(K, I, 1) is closed under conjunction introduction. It results that I(K {φ ψ}) < I(K {φ ψ}), and we obtain a contradiction. Therefore, I(K {φ ψ}) min(I(K {φ}), I(K {ψ})) holds.

The theorem below shows that the measures that satisfy DISJUNCT MINIMALITY result in consequence relations that have desired properties of non-monotonic relations mentioned in [Gabbay, 1984; Kraus et al., 1990].

Theorem 4. Let I be an inconsistency measure that satisﬁes DISJUNCT MINIMALITY. Then, the following properties are satisﬁed for every K KForm and every φ, ψ Form:

1. if K I φ and K {φ} I ψ then K I ψ (Cut);

2. if K I φ and K I ψ then K {φ} I ψ (Cautious Monotonicity);

3. if K I φ and K I ψ then K {φ} I ψ (Rational Monotonicity).

Consider now the property DISJUNCTION DOMINANCE that we deﬁne as follows: for every K KForm and every φ, ψ Form, I(K {φ ψ}) min(I(K {φ}), I(K {ψ})).

Proposition 7. An inconsistency measure I satisﬁes DISJUNCTION DOMINANCE iff it satisﬁes DOMINANCE.

Proof. Let us ﬁrst consider the if part. In the case of φ and ψ , this property is a direct consequence of the fact that φ φ ψ and ψ φ ψ for every φ, ψ Form. In the remaining case, it is a direct consequence of Equivalence. Consider now the only if part. Let K KForm and φ, ψ Form s.t. φ and φ ψ. Using Equivalence, we have I(K {ψ}) = I(K {φ ψ}). It follows from DISJUNCTION DOMINANCE that I(K {ψ}) min(I(K {φ}), I(K {ψ})). Thus, I(K {φ}) I(K {ψ}) holds.

In the following theorem, we show that DOMINANCE allows charactering IM-based consequence relations closed under conjunction elimination. A set of formula S is said to be closed under conjunction elimination if for every φ ψ S, φ S and ψ S. Theorem 5. Let I be an inconsistency measure. If Cn(K, I, 1) is closed under conjunction elimination for every K KForm, then I satisﬁes DOMINANCE. The proof is obtained by showing that the considered measure satisﬁes DISJUNCTION DOMINANCE and using Proposition 7. One might think that interesting properties can be captured by considering the dual property of DISJUNCT MINIMALITY deﬁned as follows: for every K KForm and every φ, ψ Form, I(K {φ ψ}) max(I(K {φ}), I(K {ψ})). However, there is no inconsistency measure that satisﬁes this property. Indeed, using CONSISTENCY, I({p p}) > 0 holds for every inconsistency measure I. Then, using the same property, we obtain I({p}) = 0 and I({ p}) = 0; hence, it results that I({p p}) > max(I({p}), I({ p})).

6 MCS-based Consequence Relations In this section, we focus on relationships between our consequence relations and three well-known relations that are based on the use of maximal consistent subsets (MCS) [Rescher and Manor, 1970; Benferhat et al., 1993]. We ﬁrst show that two of the considered MCS-based relations (namely credulous and argumentative relations) can be characterized using the inconsistency measure IM. Then, we establish direct connections between properties of inconsistency measures and these two relations. We ﬁnally introduce a new IM property that allows characterizing the remaining MCS-based relation (skeptical relation). Let us ﬁrst deﬁne the considered MCS-based consequence relations: Credulous Inference: K cr φ iff there exists K in MCS(K) s.t. K φ. Argumentative Inference: K arg φ iff K cr φ and for every K in MCS(K), K φ. Skeptical Inference: K sk φ iff for every K in MCS(K), K φ. Clearly, for every beliefbase K, we have {φ Form : K sk φ} {φ Form : K arg φ} {φ Form : K cr φ}. Moreover, sk is the unique relation that always generates jointly consistent consequences. The proposition below shows that the inconsistency measure IM allows us to capture the credulous and argumentative consequence relations.

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

Proposition 8. Let K be a beliefbase and φ a formula. Then, the following properties are satisﬁed:

if Eq(K, φ) = , K 1 IM φ iff K cr φ;

if Eq(K, φ) = and Eq(K, φ) = , K 2 IM φ iff K arg φ.

The condition Eq( φ, K) = is required because our relations cannot entail the negation of a formula equivalent to an element of the beliefbase. Regarding the condition Eq(φ, K) = , it comes from the fact that adding a formula that already belongs to the beliefbase does not change the amount of contradiction, even if the added formula is rejected by one of the consistent subsets of the beliefbase. To illustrate this point, consider the beliefbase K = {p q, p, q}. We have K 2 IM p q since IM(K) = 1 and IM(K { p q}) = 2. However, we have K arg p q because of { p, q} (p q). Note that the same properties can be obtained if we use the inconsistency measure IA instead of IM. A natural question to ask is whether there are relationships between common properties of IA and IM, and the credulous and argumentative inferences. Certain relationships are stated in the theorem below.

Theorem 6. Let I be an inconsistency measure, K a belief base and φ a formula. The following properties hold:

1. if I satisﬁes FREE FORMULA and K 1 I φ, then K cr φ;

2. if I satisﬁes EPENALTY, Eq( φ, K) = and K cr φ, then K 1 I φ;

3. if I satisﬁes FREE FORMULA and EPENALTY, Eq(φ, K) = , and K 2 I φ, then K arg φ;

4. if I satisﬁes FREE FORMULA and EPENALTY, Eq( φ, K) = , and K arg φ, then K 2 I φ.

Proof. Property 1. We proceed by contradiction. Assume that K cr φ. Then, for every K MCS(K), K φ holds (K { φ} ). Thus, we have φ Free(K { φ}). The property FREE FORMULA yields I(K { φ}) = I(K), which means that K 1 I φ. Hence, we have a contradiction. Property 2. For the sake of contradiction, suppose that K 1 I φ, so I(K { φ}) = I(K) holds. Using Eq( φ, K) = and EPENALTY, we obtain φ Free(K { φ}). Consequently, for every K MCS(K), K φ holds. Therefore, K cr φ, and we have a contradiction. Property 3. Suppose by way of contradiction that K arg φ. Then, (i) for every K MCS(K), K φ holds; or (ii) there exists K MCS(K) s.t. K φ (K {φ} ). We only consider the case of (ii), the proof in the case of (i) being similar to that of Property 1. Using the property (ii), φ is not free in K {φ}. As a result, we have I(K {φ}) > I(K) because of EPENALTY and Eq(φ, K) = . Thus, we obtain a contradiction. Property 4. Assume that K arg φ. Then φ is a problematic formula in K { φ} and φ is free in K {φ}. Using FREE FORMULA, EPENALTY and Eq( φ, K) = , I(K) = I(K {φ}) and I(K) < I(K { φ}) hold. Consequently, we have K 2 I φ.

Now, we aim at ﬁnding a property on inconsistency measures that allows us to capture skeptical inference. Before that, we describe a simple characterization of this MCS-based inference.

Proposition 9. For every belief base K and every formula φ, K sk φ iff MCS(K) MCS(K { φ}).

We call MCS DEPENDANCE the following property on inconsistency measures that allows us to characterize skeptical relation: for every K KForm and every φ Form, we have I(K) < I(K {φ}) iff MCS(K) MCS(K {φ}), or MCS(K) = MCS(K {φ}) and Inc(K) = . In the following proposition, we show that this property is stronger than FREE FORMULA.

Proposition 10. If an inconsistency measure satisﬁes MCS DEPENDANCE, then it satisﬁes FREE FORMULA.

Proof. Let K be a beliefbase and φ a free formula in K. Clearly, for every K MCS(K), we have φ K . Thus, MCS(K \ {φ}) MCS(K). Consequently, using MCS DEPENDANCE, we have I(K) = I(K \ {φ}).

Let us now establish a direct relationship between MCS DEPENDANCE and skeptical inference.

Proposition 11. Let I be an inconsistency, K a belief base and φ a formula s.t. Eq( φ, K) = . Then, we have the property K sk φ iff K 1 I φ, if and only if I satisﬁes MCS DEPENDANCE.

Proposition 12. Let I be an inconsistency measure that satisﬁes MCS DEPENDANCE. Then, the consequence relations 1 I, 2 I and 3 I coincide.

Since sk is a relation that leads to jointly consistent consequences, the property MCS DEPENDANCE is an additional property with DISJUNCT MINIMALITY that allows obtaining consistent consequence relations. Note that none of the measures described in this work satisfy MCS DEPENDANCE.

7 Conclusion and Perspectives

We have introduced an IM-based framework for deﬁning different types of non-monotonic paraconsistent consequence relations. We have also proposed properties of inconsistency measures that allow deﬁning consistent consequence relations. Finally, we have described direct relationships between properties of inconsistency measures and well-known MCSbased consequence relations. There are several perspectives for future work. Among them, we ﬁrst mention the study of the impact on the proposed consequence relations of other properties of inconsistency measures from the literature. It is also interesting to examine the possible connections between our framework and that based on MCS selection [Konieczny et al., 2019]. More generally, it is worthwhile to investigate other approaches for deﬁning consequence relations through inconsistency measurement

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

References [Ammoura et al., 2017] Meriem Ammoura, Yakoub Salhi, Brahim Oukacha, and Badran Raddaoui. On an MCSbased Inconsistency Measure. International Journal of Approximate Reasoning, 80:443 459, 2017. [Arieli and Avron, 2000] Ofer Arieli and Arnon Avron. General Patterns for Nonmonotonic Reasoning: From Basic Entailments to Plausible Relations. Logic Journal of the IGPL, 8(2):119 148, 2000. [Arruda, 1980] Ayda Ignez Arruda. A survey of Paraconsistent Logic. In Mathematical Logic in Latin America, volume 99 of Studies in Logic and the Foundations of Mathematics, pages 1 41. Elsevier, 1980. [Batens, 2013] Diderik Batens. New Arguments for Adaptive Logics as Unifying frame for the Defeasible Handling of Inconsistency. In Paraconsistency: Logic and Applications, volume 26 of Logic, Epistemology, and the Unity of Science, pages 101 122. Springer, 2013. [Benferhat et al., 1993] Salem Benferhat, Didier Dubois, and Henri Prade. Argumentative inference in uncertain and inconsistent knowledge bases. In UAI 93: Proceedings of the Ninth Annual Conference on Uncertainty in Artiﬁcial Intelligence, USA, pages 411 419, 1993. [Benferhat et al., 1997] Salem Benferhat, Didier Dubois, and Henri Prade. Some Syntactic Approaches to the Handling of Inconsistent Knowledge Bases: A Comparative Study Part 1: The Flat Case. Studia Logica, 58(1):17 45, 1997. [Besnard, 2014] Philippe Besnard. Revisiting Postulates for Inconsistency Measures. In Logics in Artiﬁcial Intelligence - 14th European Conference, JELIA 14, Portugal, pages 383 396. Springer, 2014. [Bona et al., 2018] Glauber De Bona, John Grant, Anthony Hunter, and S ebastien Konieczny. Towards a Uniﬁed Framework for Syntactic Inconsistency Measures. In Proceedings of the Thirty-Second AAAI Conference on Artiﬁcial Intelligence, USA, 2018. [Gabbay, 1984] Dov M. Gabbay. Theoretical Foundations for Non-Monotonic Reasoning in Expert Systems. In Logics and Models of Concurrent Systems, volume 13 of NATO ASI Series, pages 439 457. Springer, 1984. [Grant and Hunter, 2011] John Grant and Anthony Hunter. Measuring the Good and the Bad in Inconsistent Information. In IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artiﬁcial Intelligence, Spain, pages 2632 2637. IJCAI/AAAI, 2011. [Grant and Hunter, 2013] John Grant and Anthony Hunter. Distance-Based Measures of Inconsistency. In Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 12th European Conference, ECSQARU, The Netherlands, pages 230 241. Springer, 2013. [Grant and Hunter, 2017] John Grant and Anthony Hunter. Analysing inconsistent information using distance-based measures. International Journal of Approximate Reasoning, 89:3 26, 2017.

[Hunter and Konieczny, 2008] Anthony Hunter and S ebastien Konieczny. Measuring Inconsistency through Minimal Inconsistent Sets. In Principles of Knowledge Representation and Reasoning: Proceedings of the Eleventh International Conference, KR 08, Australia, pages 358 366. AAAI Press, 2008. [Hunter and Konieczny, 2010] Anthony Hunter and S ebastien Konieczny. On the measure of conﬂicts: Shapley Inconsistency Values. Artiﬁcial Intelligence, 174(14):1007 1026, 2010. [Konieczny et al., 2003] S ebastien Konieczny, J erˆome Lang, and Pierre Marquis. Quantifying information and contradiction in propositional logic through test actions. In IJCAI-03, Proceedings of the Eighteenth International Joint Conference on Artiﬁcial Intelligence, Mexico, pages 106 111. Morgan Kaufmann, 2003. [Konieczny et al., 2019] S ebastien Konieczny, Pierre Marquis, and Srdjan Vesic. Rational Inference Relations from Maximal Consistent Subsets Selection. In Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence, IJCAI 2019, Macao, China, pages 1749 1755. ijcai.org, 2019. [Kraus et al., 1990] Sarit Kraus, Daniel Lehmann, and Menachem Magidor. Nonmonotonic Reasoning, Preferential Models and Cumulative Logics. Artiﬁcial Intelligence, 44(1-2):167 207, 1990. [Middelburg, 2011] Cornelis Adam Middelburg. A Survey of Paraconsistent Logics. Co RR, abs/1103.4324, 2011. [Priest, 1991] Graham Priest. Minimally inconsistent LP. Studia Logica, 50:321 331, 1991. [Rescher and Manor, 1970] Nicholas Rescher and Ruth Manor. On inference from inconsistent premisses. Theory and Decision, 1(2):179 217, 1970. [Shoham, 1987] Yoav Shoham. A Semantical Approach to Nonmonotic Logics. In Proceedings of the Symposium on Logic in Computer Science (LICS, USA, pages 275 279. IEEE Computer Society, 1987. [Shoham, 1988] Yoav Shoham. Reasoning about change : time and causation from the standpoint of artiﬁcial intelligence. MIT Press Cambridge, 1988. [Thimm, 2016] Matthias Thimm. On the expressivity of inconsistency measures. Artiﬁcial Intelligence, 234:120 151, 2016. [Thimm, 2018] Matthias Thimm. On the Evaluation of Inconsistency Measures. In Measuring Inconsistency in Information, volume 73 of Studies in Logic. College Publications, February 2018.

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)