# measuring_strong_inconsistency__23d2d566.pdf

Measuring Strong Inconsistency

Markus Ulbricht Department of Computer Science Leipzig University Germany

Matthias Thimm Institute for Web Science and Technologies University of Koblenz-Landau Germany

Gerhard Brewka Department of Computer Science Leipzig University Germany

We address the issue of quantitatively assessing the severity of inconsistencies in nonmonotonic frameworks. While measuring inconsistency in classical logics has been investigated for some time now, taking the nonmonotonicity into account poses new challenges. In order to tackle them, we focus on the structure of minimal strongly K-inconsistent subsets of a knowledge base K a generalization of minimal inconsistency to arbitrary, possibly nonmonotonic, frameworks. We propose measures based on this notion and investigate their behavior in a nonmonotonic setting by revisiting existing rationality postulates, analyzing the compliance of the proposed measures with these postulates, and by investigating their computational complexity.

1 Introduction In the literature on inconsistency measurement see e. g. (Hunter and Konieczny 2004; Grant and Hunter 2006; Thimm 2016) inconsistency measures are functions that aim at assessing the severity of the inconsistency in knowledge bases formalized in propositional logic. The basic intuition behind an inconsistency measure I is that the larger the inconsistency in K the larger the value I(K). A simple but popular approach to measure inconsistency is to take the number of minimal inconsistent subsets (Hunter and Konieczny 2008), i. e., to define IMI(K) = |Imin(K)|, where Imin(K) is the set of all minimal inconsistent subsets of a knowledge base K. This measure already complies with many basic ideas of inconsistency measurement, in particular IMI(K) = 0 iff K is consistent. By also taking the size and the relationships of minimal inconsistent subsets into account, a wide variety of different inconsistency measures can be defined on top of that idea, see e. g. (Hunter and Konieczny 2008; Jabbour et al. 2016; Jabbour and Sais 2016). Measuring inconsistency in nonmonotonic logics has only recently gained some attention (Ulbricht, Thimm, and Brewka 2016; Brewka, Thimm, and Ulbricht 2017) and a thorough study is still needed. In this setting, a measure such as IMI is not applicable as a consistent nonmonotonic knowledge base K may contain minimal inconsistent subsets. In (Brewka, Thimm, and Ulbricht 2017), a refined notion of

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

inconsistent subsets of a knowledge base K of a possibly nonmonotonic framework has been introduced, called strong K-inconsistency. The notion of strong inconsistency generalizes classical inconsistency in a well-behaved manner as it preserves many structural properties as e. g. the hitting set duality with maximal consistent sets (Reiter 1987). Moreover, this notion allows us to generalize existing inconsistency measures based on minimal inconsistent sets to arbitrary logics, which is the topic of the present paper. Research in inconsistency measurement is driven by rationality postulates, i. e., desirable properties that should hold for concrete approaches. There is a growing number of rationality postulates for inconsistency measurement but not every postulate is generally accepted, see (Besnard 2014) for a discussion on this topic. The issue of measuring inconsistency in nonmonotonic frameworks requires some reconsideration compared to the classical setting. This becomes apparent when considering the monotony postulate which is usually satisfied by classical inconsistency measures and demands I(K) I(K ) whenever K K holds, i. e., the severity of inconsistency cannot be decreased by adding new information. However, in nonmonotonic frameworks, adding information may resolve conflicts. It is thus possible that K is inconsistent, while K is not, so we would expect I(K ) < I(K) for any reasonable measure I. The main contributions of this paper can be summarized as follows. As the basis of our investigation, we consider generalized versions of three measures based on minimal inconsistent sets (Section 2). In order to assess their behaviour, we develop rationality postulates based on previous ones from the literature. Some of the postulates still make sense for a general, possibly nonmonotonic logic, but most of them require refinements (Section 3). We analyze the measures with respect to the postulates in Section 4 and assess their computational complexity by considering natural decision and function problems following (Thimm and Wallner 2016) in Section 5. We apply our ideas to the problem of measuring inconsistency wrt. given contexts, i. e., of relating values of inconsistency of subsets of a knowledge base to inconsistency of the whole knowledge base (Section 6). We discuss related work in Section 7. Section 8 concludes.1

1An extended version of this paper with proofs can be found at http://mthimm.de/misc/utb aaai18 ext.pdf

The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18)

2 Measures for Strong Inconsistency Since we are going to consider arbitrary (nonmonotonic) frameworks, we start by giving an abstract definition of a logic. We do so as in (Brewka, Thimm, and Ulbricht 2017). Definition 2.1. A logic L is a tuple L = (WF, BS, INC, ACC) where WF is a set of well-formed formulas, BS is a set of belief sets (which itself can be defined arbitrarily), INC BS is an upward closed2 set of inconsistent belief sets, and ACC : 2WF 2BS assigns a collection of belief sets to each subset of WF (belief sets are representations of the knowledge which is implicit in a set of formulas; ACC thus defines the semantics of the logic by assigning beliefs sets to sets of formulas). A knowledge base K of L is a finite subset of WF. A knowledge base K is called inconsistent iff ACC(K) INC. Let I (K) and Imin(K) denote the inconsistent and -minimal inconsistent subsets of K, respectively. Note that a knowledge base K can be inconsistent because it has no belief sets, and consistent even if some (but not all) of its belief sets are in INC. Observe that our definition of a logic is general enough to capture established monotonic and nonmonotonic frameworks like propositional logic, logic programming under answer set semantics (Gelfond and Lifschitz 1988), abstract argumentation frameworks (Dung 1995) and so on (Brewka, Thimm, and Ulbricht 2017). We show how to cast logic programs under the answer set semantics (Gelfond and Lifschitz 1991; Gelfond and Leone 2002; Brewka, Eiter, and Truszczynski 2011) into our general definition of a logic. Example 2.2. Let A be a set of propositional atoms and let Lit(A) = A { a | a A} be the set of corresponding literals. A disjunctive rule r is a rule of the form

l0 or ... or lk lk+1, . . . , lm, not lm+1, . . . , not ln. (1)

with l0, . . . , ln Lit(A). Let WFASP A be the set of all such rules. A set P WFASP A is also called a logic program for short. A rule r P of the form a lk+1, . . . , lm, not lm+1, . . . , not ln, not a. where a does not occur elsewhere in P is called constraint and abbreviated by lk+1, . . . , lm, not lm+1, . . . , not ln. . Furthermore, a belief set is any set of literals, i. e., BSASP A = 2Lit(A). For a program P WFASP A without default negation (m = n) an answer set is a minimal set of literals closed under all rules, where a set is closed under a rule of form (1) iff at least one of the head literals l0, . . . , lk is in the set whenever the body literals lk+1, . . . , lm are. For a program P with default negation, a set M of literals is an answer set iff M is an answer set of the reduct P M obtained from P by (i) deleting rules with not lj in the body for some lj M, and (ii) deleting default negated literals from the remaining rules. Now let ACCASP A (P) = {M | M is an answer set of P} for all P WFASP A . Finally, inconsistent belief sets are those sets containing complementary literals. This gives us the logic LASP A = (WFASP A , BSASP A , INCASP A , ACCASP A ).

2S upward closed means B S and B B implies B S.

Let WFASP A WFASP A be the set of all rules of the form (1) with k = 0. Then the logic corresponding to disjunctionfree logic programs under answer set semantics is LASP A = (WFASP A , BSASP A , INCASP A , ACCASP A ). Definition 2.3. (Brewka, Thimm, and Ulbricht 2017) A logic L = (WF, BS, INC, ACC) is weakly monotonic whenever K K implies: if B ACC(K ) then B B for some B ACC(K). We call such L monotonic for short. Note that in a monotonic logic conflicts cannot be resolved, i. e., if K K holds for two knowledge bases K and K where K is inconsistent, then K is inconsistent as well. We can now define strong K-inconsistency (Brewka, Thimm, and Ulbricht 2017) for our general setting, which is the central notion of this paper. Definition 2.4. For H, K WF with H K, H is called strongly K-inconsistent if H H K implies H is inconsistent. The set H is called strongly inconsistent if it is strongly WF-inconsistent. We let SI (K) and SImin(K) denote the set of all strongly K-inconsistent and all -minimal strongly K-inconsistent subsets of K, respectively. In (Brewka, Thimm, and Ulbricht 2017) it has been shown that the notion of strong inconsistency faithfully generalizes classical inconsistency to arbitrary logics. In particular, the notions coincide for monotonic logics and the existence of a strongly K-inconsistent subset of K is a necessary and sufficient condition for inconsistency of K itself. Moreover, removing from K any hitting set3 of SImin(K) yields a maximal consistent subset of K, which is also known as the hitting set duality in classical logics, cf. (Reiter 1987). We refer to (Brewka, Thimm, and Ulbricht 2017) for a more thorough discussion of strong inconsistency. We now introduce the inconsistency measures we are going to consider throughout this paper. Assume an arbitrary but fixed logic L. In classical inconsistency measurement, minimal inconsistent subsets of a knowledge base play an important role as they can be seen as the atomic conflicts within K. A rather simple but still popular approach to measure inconsistency is thus taking the value |Imin(K)|. The notion of strong K-inconsistency facilitates the following generalization of this measure to nonmonotonic logics. Let R 0 be the set of non-negative real values including .

Definition 2.5. Define IMSI : 2WF R 0 via IMSI(K) = |SImin(K)|. It has been noted that larger minimal inconsistent sets should be considered less inconsistent than smaller ones (see e. g. the lottery paradox). Making use of strong Kinconsistency, we obtain the following measure based on one from (Hunter and Konieczny 2008): Definition 2.6. Define IMSIC : 2WF R 0 via IMSIC(K) =

H SImin(K) 1 |H|.

Instead of counting the number of sets in SImin(K), one could also take the amount of formulas into account. Based

3A set H is called a hitting set of a set of sets S = {S1, . . . , Sn} iff H Si = for i = 1, . . . , n.

on a measure in (Grant and Hunter 2011), we consider the following, quite simple approach: Definition 2.7. Let Ip : 2WF R 0 be the measure Ip(K) = |

H SImin(K) H|.

Note that there are further variants in the classical setting for taking minimal inconsistent sets into account for the task of measuring inconsistency, see e. g. (Hunter and Konieczny 2008; Jabbour et al. 2016; Jabbour and Sais 2016). An investigation of generalizations of those is left for future work.

3 Rationality Postulates for General Logics We are going to revisit rationality postulates for inconsistency measures from the literature and phrase them within the context of an arbitrary, possibly nonmonotonic, logic. We will start by considering the four postulates which a basic inconsistency measure should have due to (Hunter and Konieczny 2010). We will then continue our investigation with a collection of other postulates that can be lifted to our general setting. If not stated otherwise, we assume an arbitrary but fixed logic L = (WF, BS, INC, ACC) (with being a consistent knowledge base) and an inconsistency measure I : 2WF R 0 for the remainder of this section.

Basic Postulates The most basic (and undisputed) property that an inconsistency measure should have is the ability to distinguish between consistency and inconsistency, i. e., I(K) = 0 if and only if K is consistent. There is no doubt that this makes sense in nonmonotonic frameworks as well. Consistency For any knowledge base K WF, I(K) = 0 if and only if K is consistent. Another fairly accepted postulate is monotony. It formalises the intuition that adding information to a knowledge base should increase the inconsistency value since a knowledge base that contains more information than another one, is also more likely to contain more conflicts. Monotony If K and K are knowledge bases, then I(K) I(K K ). In nonmonotonic frameworks, monotony does not make sense because additional information might restore consistency. A simple special case where this does not happen is when the knowledge base K is itself strongly inconsistent rather than just inconsistent, motivating a postulate like I(K) I(K K ) if K is strongly inconsistent . This would formalize the intuition that adding information cannot resolve strong inconsistency. However, it might still be possible that some conflicts in K are resolved, while others are not. In the most extreme case, all but one conflict in K are resolved, but K contains new ones. In this case, the inconsistency in K K stems more from K rather than K, rendering the comparison between I(K) and I(K K ) quite meaningless. We should thus formalize the concept of monotony more precisely: Definition 3.1. Let K and K be knowledge bases. We say that K preserves conflicts of K if for any H SI (K), it also holds that H SI (K K ).

Proposition 3.2. If K and K are knowledge bases and K preserves conflicts of K, then SImin(K) SImin(K K ). Strong Monotony If K preserves conflicts of K, then I(K) I(K K ). Strong monotony thus formalizes that adding information should not decrease the inconsistency degree of a knowledge base K as long as no conflicts of K are resolved. We turn to free formula independence (Hunter and Konieczny 2010). It states that I(K) = I(K {α}) should hold whenever α K is free, i. e., α does not occur in any minimal inconsistent set. A simple adjustment makes use of the observation that we should take strong K-inconsistency into account: Since a free formula does not introduce inconsistency in the classical case, it makes sense to require that it does not introduce strong inconsistency in nonmonotonic logics. Definition 3.3. Let K be a knowledge base. A formula α K is called free with respect to strong K-inconsistency (SIfree for short) if α / H SImin(K) H. Let Free SI (K) be the set of all SI-free formulas of K. Due to nonmonotonicity, an SI-free formula can still resolve conflicts. Since it cannot introduce them, one might expect the following: SI-free If α Free SI (K), then I(K) I(K \ {α}). Note that this postulate is similar to free formula dilution (Mu, Liu, and Jin 2011). However, even this property turns out to be quite strong. Not even IMSI a measure based on minimal strong K-inconsistent subsets satisfies it in general (cf. Section 4). The reason for this is that removal of formulas in Free SI (K) may affect the structure of SImin(K). Thus, measures based on SImin(K) will not tend to satisfy SI-free even though the intuition is that formulas in Free SI (K) do not participate in conflicts. This motivates consideration of a stronger notion, ensuring that α can neither introduce nor resolve inconsistency: Definition 3.4. (Brewka, Thimm, and Ulbricht 2017) Let K be a knowledge base. A formula α K is called neutral if any subset H K is consistent if and only if H {α} is. We denote the set of all neutral formulas of K by Ntr(K). Independence If α Ntr(K), then I(K) = I(K \ {α}). In the propositional setting, the postulate dominance (Hunter and Konieczny 2010) requires that for two formulas α, β such that α is consistent and α β, then I(K {α}) I(K {β}) should hold. The intuitive meaning is that α carries more information and is thus more likely to be involved in conflicts. Of the postulates we considered so far, it is probably the most disputed one (see e. g. (Besnard 2014)). We are convinced that this postulate is of rather limited use in a nonmonotonic setting. Since adding information to a knowledge base may resolve conflicts, there is simply no reason why α, which carries more information than β, should be considered more problematic in general. Even though there are conceivable adjustments that would make dominance work for nonmontonic frameworks, we are not going to discuss them here. This concludes our discussion on the four postulates for basic inconsistency measures (Hunter and Konieczny 2010).

Extended Postulates

We continue our investigation with a generalization of monotony, namely supper-additivity (Thimm 2009). It states that I(K) + I(K ) I(K K ) should hold whenever K K = . As above, we need to take into account that adding information might resolve conflicts in nonmonotonic frameworks. Therefore, we add the additional condition of conflict preservation to our version of super-additivity.

Strong Super-Additivity If K and K preserve each other s conflicts and K K = , then I(K)+I(K ) I(K K ).

Many concrete approaches to inconsistency measurement depend on the syntax of a knowledge base. The most common example is the difference between the conjunction {a b} and two formulas {a, b}. The postulate adjunction invariance (Besnard 2014) formalizes the idea that there should be no difference, i. e., I(K {a b}) = I(K {a, b}). In the classical setting, there are a couple of more postulates considering situations where (parts of) semantically equivalent knowledge bases are compared, cf. (Thimm 2017). In nonmonotonic frameworks, a notion of equivalence of the form K has the same models as K is too weak as conclusions can be withdrawn due to nonmonotonicity. In the context of logic programming, for example, this observation has led to the consideration of so called strong equivalence (Lifschitz, Pearce, and Valverde 2001). It is straightforward to generalize this notion to arbitrary nonmonotonic frameworks (Brewka, Thimm, and Ulbricht 2017).

Definition 3.5. Let L = (WF, BS, INC, ACC) be a logic. The knowledge bases K and K are strongly equivalent, denoted by K s K , iff ACC(K H) = ACC(K H) for each H WF.

Proposition 3.6. (Brewka, Thimm, and Ulbricht 2017) Let K, K and H be knowledge bases. If K and K are strongly equivalent, then K is strongly K H-inconsistent iff K is strongly K H-inconsistent.

Strong equivalence plays a similar role in nonmonotonic frameworks as (normal) equivalence in monotonic frameworks. In particular, it allows for modularisation of knowledge bases. If a subset H of a knowledge base K is strongly equivalent to a set H then H can be replaced in K by H without changing the inferences one can draw from K. This also means that H and H should be interchangeably when it comes to the inconsistency they contribute to K. By generalising this idea to the whole knowledge base, we obtain the desirable property that strongly equivalent knowledge bases should have the same degree of inconsistency.

Strong Equivalence If K s K then I(K) = I(K ).

Example 3.7. Consider the logic programs P and P given as follows.

P : a. b. c a, b, not c.

P : a. b a. c a, b, not c.

Both programs are inconsistent due to not having an answer set. However, the observation P s P is still meaningful as both programs can be rendered consistent by adding rules

which facilitate derivation of c. Moreover, in both cases inconsistency stems from the derivation of a and b (in both cases without making use of defaults) combined with the rule c a, b, not c. . It is thus reasonable to expect I(P) = I(P ). However, whether or not this is meaningful depends on the framework under consideration. Sometimes, it might not be helpful to distinguish between inconsistent knowledge bases. For example, in classical logics we have K s K for any two inconsistent knowledge bases K and K , thus rendering the above postulates too strong. In order to obtain a more fine grained notion of equivalence, we utilize a technique from (Thimm 2013a) for the postulate irrelevance of syntax . For our setting we define: Definition 3.8. Let K and K be two knowledge bases. We call K and K formula-wise strongly equivalent, denoted by K α K , if there is a bijection ρ : K K such that {α} s {ρ(α)} holds for all α K. We obtain the following generalization of irrelevance of syntax (Thimm 2013a) (FW=formula-wise): FW-Strong Equivalence If K α K then I(K) = I(K ). The final postulate we consider in this subsection is separability (Hunter and Konieczny 2010) which has a straightforward representation in our general context. Separability If SImin(K K )=SImin(K) SImin(K ) and SImin(K) SImin(K )= then I(K K )=I(K)+I(K ). In other words, if the conflicts of two knowledge bases K and K are completely independent, the inconsistency value of their union should be decomposed as the sum of the individual values.

4 Analysis Now we investigate the compliance of the considered measures with the rationality postulates above. For postulates that are not satisfied by a particular measure in general, we give counterexamples within the logic LASP A . Regarding consistency, note that SImin(K) = if and only if K is consistent. Hence, the postulate is satisfied by all measures. In general, we obtain the following result on the compliance of our measures with the rationality postulates, see also Table 1. Proposition 4.1. IMSI, IMSIC and Ip satisfy consistency, strong monotony, independence and strong super-additivity, and FW-strong equivalence. IMSI and IMSIC also satisfy separability. As already mentioned in Section 3, the postulate SI-free is not satisfied by any of the measures. Example 4.2. Consider the program P given as follows:

P : a not a, b. a not c, not d. b. c. d.

The rule r = a not c, not d. is in Free SI (P): the rule a not a, b. combined with the fact b. is responsible for P being inconsistent and r cannot restore consistency as long as c. or d. are present. Hence, SImin(P) consists of {a not a, b., b., c.} and {a not a, b., b., d.}, i. e.,

IMSI IMSIC Ip Consistency Strong Monotony SI-free Independence Strong Super-Additivity Strong Equivalence FW-Strong Equivalence Separability

Table 1: Compliance of measures with rationality postulates

IMSI(P) = 2, IMSIC(P) = 2 3 and Ip(P) = 4. However SImin(P \ {r}) = {a not a, b., b.}, i. e., IMSI(P \ {r}) = 1, IMSIC(P \ {r}) = 1

2 and Ip(P \ {r}) = 2. Example 4.3. Consider the programs P and P given via

P : a. a. P : a. a. a a. a a.

It is easy to see that P s P as the inconsistency in both programs cannot be repaired in any extension of them. However, we have that I(P1) = I(P2) for all I {IMSI, IMSIC, Ip} thus showing that strong equivalence is violated by all three measures. For a counterexample of separability wrt. Ip see (Thimm 2017) (already in the classical case). Observe that for those postulates that are generalizations of classical ones i. e., consistency, strong monotony, independence, strong superadditivity, and separability the compliance of our three measures generalizes their compliance with the corresponding postulates in the classical case, cf. (Thimm 2017).

5 Computational Complexity We now address the computational complexity of the measures we considered so far. Following (Thimm and Wallner 2016), we consider the three decision problems EXACTI, UPPERI, LOWERI, and the natural function problem VALUEI. Let L = (WF, ACC, BS, INC) be a logic. EXACTL I Input: K WF, x [0, ] Output: TRUE iff I(K) = x UPPERL I Input: K WF, x [0, ] Output: TRUE iff I(K) x LOWERL I Input: K WF, x (0, ] Output: TRUE iff I(K) x VALUEL I Input: K WF Output: The value of I(K) We assume the reader to be familiar with the polynomial hierarchy, i. e., the classes Σp m and Πp m for m 0. We also consider Dp m = {L1 L1 | L1 Σp m, L2 Πp m}. Moreover, FPΣp m[log n] is the class containing function problems whose solution can be computed in P with access to a logarithmically bounded number of calls to an Σp m oracle. Finally, we make use of the counting polynomial hierarchy (Wagner 1986), which provides classes for decision problems involving subproblems such as counting strongly minimal inconsistent sets (represented by a prefixing C before the standard complexity class names).

First, we consider an arbitrary, possibly nonmonotonic logic L = (WF, ACC, BS, INC). Since hardness results cannot be expected in general (these depend on the concrete logic), we will only give membership statements here. Our results will depend on the complexity of the satisfiability check of L. SATL Input: K WF Output: TRUE iff K is consistent Depending on SATL, we obtain the following membership results for IMSI and Ip: Theorem 5.1. Let m 1. If the problem SATL is in 1. Σp m, then UPPERL IMSI and LOWERL IMSI are in CΣp m, 2. Πp m, then UPPERL IMSI and LOWERL IMSI are in CΣp m+1, 3. Πp m and L is monotonic, then UPPERL IMSI and LOWERL IMSI are in CΣp m. Note that no counting class occurs in the following theorem as the decision problems for Ip are much easier. Theorem 5.2. Let m 1. If the problem SATL is in 1. Σp m, then LOWERL Ip is in Σp m+1,

2. Πp m, then LOWERL Ip is in Σp m+2,

3. Πp m and L is monotonic, then LOWERL Ip is in Σp m+1. Using the latter theorem and techniques from (Thimm and Wallner 2016), Lemmas 2 and 3, we infer: Corollary 5.3. Let m 1. If the problem SATL is in 1. Σp m, then UPPERL Ip is in Πp m+1, EXACTL Ip is in Dp m+1 and

VALUEL Ip is in FPΣp m+1[log n],

2. Πp m, then UPPERL Ip is in Πp m+2, EXACTL Ip is in Dp m+2 and

VALUEL Ip is in FPΣp m+2[log n],

3. Πp m and L is monotonic, then UPPERL Ip is in Πp m+1,

EXACTL Ip is in Dp m+1 and VALUEL Ip is in FPΣp m+1[log n]. Furthermore, Table 2 summarises some additional results pertaining to hardness wrt. the concrete logics LASP A and LASP A (disjunction-free and disjunctive logic programs under the answer set semantics, respectively). As with the other results, proofs can be found in the online appendix. Recall that deciding whether a program P within the framework LASP A is consistent is NP-complete in general, while the decision problem for programs P in LASP A is Σp 2-complete (Eiter and Gottlob 1995). The results show that, for LASP A , the computational complexity of the problems we consider is similar to the results for the propositional case given in (Thimm and Wallner 2016). This seems natural as the satisfiability check for propositional logic is NP-complete as well. As expected, considering LASP A involves going up one level within the corresponding hierarchy. Finally, we have the following results pertaining to VALUEIMSI, cf. (Valiant 1979) for the definition of the used counting complexity classes.

Theorem 5.4. The problem VALUELASP A IMSI is # co NPcomplete under subtractive reductions. The problem VALUELASP A IMSI is # Πp 2-complete under subtractive reductions.

IMSI IMSIC Ip

UPPER LASP A I CNP-c CNP-h Σp 2-c

LOWER LASP A I CNP-c CNP-h Πp 2-c

EXACT LASP A I C=NP-h C=NP-h Dp 2-c

UPPER LASP A I CΣp 2-c CΣp 2-h Σp 3-c

LOWER LASP A I CΣp 2-c CΣp 2-h Πp 3-c

EXACT LASP A I C=Σp 2-h C=Σp 2-h Dp 3-c

Table 2: Hardness results for LASP A and LASP A

6 Strong Inconsistency and Context As already taken into account by Definition 2.4, the central issue regarding inconsistency in nonmonotonic logics is that conflicts may be resolved by adding information. This raises the question how, given an inconsistent knowledge base K, the degree of inconsistency of a subset H K should be assessed. We give a motivating example within the logic LASP A . Example 6.1. Consider the program P given as follows:

P : a or b. not a. not b.

Inconsistency of P stems from the two constraints not a. and not b. . As answer sets are required to be minimal models, an answer set can only contain either a or b, but not both. Yet, the subset H = { not a., not b.} obviously consists of two conflicts and this intuition is confirmed by the observation that IMSI(H) = 2 holds. The preceding example makes use of the observation that a set H SImin(K) may itself contain more than one inconsistent subset. In fact, as the hitting set duality utilizing strong K-inconsistency (Brewka, Thimm, and Ulbricht 2017) suggests, inconsistency of a subset H K is only meaningful within the context of the knowledge base K. Postulates describing the behaviour of subsets of knowledge bases as well as single formulas should respect this observation. This motivates the following notion. Definition 6.2. Let I : 2WF R 0 be an inconsistency measure, K a knowledge base and H K. We call

Co K,I(H) := min H H K I(H ) (2)

the value of I(H) with respect to the context K. Taking the minimum in (2) has the same motivation as considering all supersets of H in Definition 2.4: We are only interested in (the severity of) conflicts that cannot be resolved within K. For example, if we are given H K and a measure I satisfying consistency, then Co K,I(H) = 0 iff H is not strongly K-inconsistent. Moreover, as most classical inconsistency measures for propositional knowledge bases satisfy monotony (cf. (Thimm 2017)), Co K,I(H) = I(H) oftentimes holds in the classical case, anyway. Hence, when assessing the severity of inconsistency of subsets of a knowledge base K, utilizing Co K,I(H) appears to be appropriate. Moreover, many of the postulates given above are preserved by Co K,I(H):

Proposition 6.3. Let K be a knowledge base and H, H K. It holds that 1. Co K,I(H) Co K,I(H H ), 2. if I satisfies consistency, then Co K,I(H) = 0 if and only if H / SI (K), 3. if I satisfies independence and α Ntr(K), then Co K,I(H) = Co K,I(H \ {α}), 4. if I satisfies strong equivalence and H s H for H, H K, then Co K,I(H) = Co K,I(H ). Note that Co K,I(H) Co K,I(H H ) holds without the notion of preserving conflicts. Since we calculate the minimum in (2), nonmonotonicity is already taken into account. Now consider the following postulate adapted from (Hunter and Konieczny 2010): MSI-Normalization If H SImin(K), then I(H) = 1. MSI-Normalization reflects the intuition that a subset H SImin(K) should correspond to an atomic conflict within K. However, this is not done by Co K,I(H), even for the special case I = IMSI. Example 6.4. Let K = {α1, . . . , α4} be a knowledge base such that only {α1, α3} and {α2, α4} are consistent subsets. Let H = {α1, α2}. One can verify that Co K,IMSI(H) = 2. The reason is, roughly speaking, that a set H SImin(K) does not represent one conflict , but rather one conflict that cannot be resolved . Thus, to capture atomic conflicts in a nonmonotonic logic, we need to utilize a notion of resolvable conflicts . This induces the following novel measure. Definition 6.5. Let K be a knowledge base. Let H K and consider {H1, . . . , Hn} = SImin(H), i. e., the minimal conflicts of H. Let H = H \ SImin(H). Define IRes(K)(H) as the number of conflicts within H that cannot be resolved within K, i. e.,

IRes(K)(H) = min I {1,...,n}{n |I| |

i I Hi H / SI (K)}.

Example 6.6. Consider P from above again: P : a or b. not a. not b. Again, let H = P \ {a or b.}. We have SImin(H) = {{ not a.}, { not b.}} and H = . Let H1 = { not a.} and H2 = { not b.}. Then, Hi / SI (P), i = 1, 2, H1 H2 SI (P). So, a or b. can resolve one conflict . As desired, IRes(P)(H) = 1. The next example shall illustrate why we need H in the definition of IRes(P)(H). Consider

P : a. not a. a. with H being the subset H = { a., not a.}. We have SImin(H ) = {{ not a.}} and hence, within H the fact a. is not yet identified as potential conflict. However, as satisfaction of the constraint not a. requires a. , the negated fact a. should be taken into account. Thus, even though the constraint being the only rule in SImin(H ) can be resolved, IRes(P )(H ) = 1. This is as desired, because H carries two problems of which only one can be resolved; not both simultaneously. Moreover, H SI (P ) suggests that a measure should not assign 0 to it.

Since conflicts cannot be resolved by adding information in monotonic logics, IRes(K)(H) and IMI(H) should coincide to capture our intuition of minimal inconsistent sets as atomic conflicts . Indeed: Proposition 6.7. If L is a monotonic logic and K a knowledge base with H K, then IRes(K)(H) = IMI(H). Moreover, it complies with some of the ideas above, e. g.: Proposition 6.8. Let K be a knowledge base and H, H K. It holds that 1. IRes(K)(H) = 0 if and only if H / SI (K), 2. IRes(K)(H) IRes(K)(H H ), 3. IRes(K)(H) = IRes(K)(H \ {α}) if α Ntr(K).

In particular, IRes(K)(H) captures the intuition that a set H SImin(K) represents exactly one conflict. Proposition 6.9. Let K be a knowledge base and H SImin(K). Then IRes(K)(H) = 1.

7 Related Work Inconsistency measurement in non-classical frameworks has been addressed in some limited fashion before (Thimm 2013b; Potyka 2014; De Bona and Finger 2015; Condotta, Raddaoui, and Salhi 2016; Ulbricht, Thimm, and Brewka 2016; Amgoud and Ben-Naim 2017). The latter paper studies disagreement in argumentation graphs, a notion slightly different from inconsistency. It will nevertheless be interesting to see whether postulates for disagreement are applicable to inconsistency as well. However, the closest work to this one is (Ulbricht, Thimm, and Brewka 2016) where the special case of LASP A is considered rather than a general, nonmonotonic logic. We briefly discuss some of the postulates mentioned. Many of them are concerned about situations where some kind of monotony should hold. However, all of them do have in common that conflicts are preserved as in strong monotony from above. In fact, they turn out to be special cases. Before we state them, we need the notion of a splitting set of a program P. Definition 7.1. Let P be a logic program, i. e., a set of rules of the form (1). A set U of literals is called a splitting set for P, if {l0, . . . , lk} U = implies {l0, . . . , ln} U for any rule r P. For a splitting set U, let bot U(P) be the set of all rules r P with {l0, . . . , ln} U. Now we consider the following postulates from (Ulbricht, Thimm, and Brewka 2016). CLP-Monotonicity If P does not contain default negation not , then I(P) I(P P ) for any program P . Split-Monotonicity If U is a splitting set for P, then I(bot U(P)) I(P).

Con-Monotonicity If P WFASP A and r P is a constraint, then I(P) I(P {r}). All of them describe situations where the additional rules preserves conflicts of the program on the left hand side. Proposition 7.2. If a measure I satisfies strong monotony, it satisfies CLP-Monotony, Split-Monotony and Con Monotony as well.

Some postulates in the literature explicitly make use of the language resp. atoms occurring in a formula or knowledge base. It is thus hard to phrase them for a general logic L. However, it is done for answer set programming. Recall SIfree and independence from above. Both are generalizations of free formula independence. A weaker version is safe rule independence (Hunter and Konieczny 2010). It states that a consistent formula α should not change the inconsistency value of a knowledge base K if no atom in K occurs in α. Within answer set programming, we can define the notion of a safe rule more liberally as only the head atoms of a rule are to be taken into account (Ulbricht, Thimm, and Brewka 2016).

Definition 7.3. Let P be a disjunctive logic program. A rule r such that {r} is consistent is called safe with respect to P if the atoms occurring in the head of r do not occur in P \ {r}.

This induces the following postulate:

Safe-rule independence If P is a logic program and r safe with respect to P, then I(P) = I(P {r }).

More generally, the inconsistency values of two independent programs should add up.

Language Separability If P and P are programs that do not share any atoms, then I(P P ) = I(P) + I(P ).

Note that this postulate is similar to separability from above, without explicitly making use of SImin(P) and SImin(P ).

8 Conclusions

We made first steps towards measuring inconsistency in a general, possibly nonmonotonic, framework by revisiting rationality postulates for propositional logic and adjusting them for our setting. Utilizing those postulates, we examined the behaviour of measures based on minimal strong Kinconsistent subsets, a generalization of minimal inconsistent subsets to nonmonotonic frameworks. We also analyzed their computational complexity. Finally, we re-examined the notion of strong inconsistency in order to define an inconsistency measure on subsets of a context. This measure can therefore be used to analyse the distribution of inconsistency within a knowledge base, similar as the Shapley measure (Hunter and Konieczny 2010) in the classical case. In the literature, additional measures based on minimal inconsistent sets of a knowledge base K have been proposed, e. g., (Jabbour et al. 2016; Jabbour and Sais 2016). It is a natural idea to investigate their behavior in nonmonotonic frameworks, making use of strong K-inconsistency. Moreover, focusing on particular frameworks similar in spirit to (Ulbricht, Thimm, and Brewka 2016) may lead to the development of more significant rationality postulates, as they can be tailored for the framework.

Acknowledgements

This work was partially funded by Deutsche Forschungsgemeinschaft DFG (Research Training Group 1763; project BR 1817/7-2).

References Amgoud, L., and Ben-Naim, J. 2017. Measuring disagreements in argumentation graphs. In Proceedings of the 11th International Conference on Scalable Uncertainty Management (SUM 17). Besnard, P. 2014. Revisiting postulates for inconsistency measures. In Proceedings of the 14th European Conference on Logics in Artificial Intelligence (JELIA 14), 383 396. Brewka, G.; Eiter, T.; and Truszczynski, M. 2011. Answer set programming at a glance. Commun. ACM 54(12):92 103. Brewka, G.; Thimm, M.; and Ulbricht, M. 2017. Strong inconsistency in nonmonotonic reasoning. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, 901 907. Condotta, J.-F.; Raddaoui, B.; and Salhi, Y. 2016. Quantifying conflicts for spatial and temporal information. In Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning (KR 16). De Bona, G., and Finger, M. 2015. Measuring inconsistency in probabilistic logic: Rationality postulates and dutch book interpretation. Artificial Intelligence 227:140 164. Dung, P. M. 1995. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artif. Intell. 77(2):321 358. Eiter, T., and Gottlob, G. 1995. On the computational cost of disjunctive logic programming: Propositional case. Annals of Mathematics and Artificial Intelligence 15(3-4):289 323. Gelfond, M., and Leone, N. 2002. Logic programming and knowledge representation the A-Prolog perspective. Artificial Intelligence 138(1 2):3 38. Gelfond, M., and Lifschitz, V. 1988. The stable model semantics for logic programming. In ICLP/SLP, volume 88, 1070 1080. Gelfond, M., and Lifschitz, V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Comput. 9(3/4):365 386. Grant, J., and Hunter, A. 2006. Measuring Inconsistency in Knowledgebases. Journal of Intelligent Information Systems 27:159 184. Grant, J., and Hunter, A. 2011. Measuring consistency gain and information loss in stepwise inconsistency resolution. Symbolic and Quantitative Approaches to Reasoning with Uncertainty 362 373. Hunter, A., and Konieczny, S. 2004. Approaches to Measuring Inconsistent Information. In Inconsistency Tolerance, volume 3300 of Lecture Notes in Computer Science. Springer International Publishing. 189 234. Hunter, A., and Konieczny, S. 2008. Measuring inconsistency through minimal inconsistent sets. In Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning (KR 2008), 358 366. AAAI Press. Hunter, A., and Konieczny, S. 2010. On the measure of conflicts: Shapley inconsistency values. Artificial Intelligence 174(14):1007 1026.

Jabbour, S., and Sais, L. 2016. Exploiting MUS Structure to Measure Inconsistency of Knowledge Bases. In Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI 16). Jabbour, S.; Ma, Y.; Raddaoui, B.; Sais, L.; and Salhi, Y. 2016. A MIS Partition Based Framework for Measuring Inconsistency. In Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning (KR 16). Lifschitz, V.; Pearce, D.; and Valverde, A. 2001. Strongly equivalent logic programs. ACM Transactions on Computational Logic 2(4):526 541. Mu, K.; Liu, W.; and Jin, Z. 2011. A general framework for measuring inconsistency through minimal inconsistent sets. Knowledge and Information Systems 27(1):85 114. Potyka, N. 2014. Linear Programs for Measuring Inconsistency in Probabilistic Logics. In Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR 14), 568 577. Reiter, R. 1987. A theory of diagnosis from first principles. Artif. Intell. 32(1):57 95. Thimm, M., and Wallner, J. P. 2016. Some complexity results on inconsistency measurement. In Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning (KR 16), 114 124. Thimm, M. 2009. Measuring inconsistency in probabilistic knowledge bases. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, 530 537. AUAI Press. Thimm, M. 2013a. Inconsistency measures for probabilistic logics. Artificial Intelligence 197:1 24. Thimm, M. 2013b. Inconsistency Measures for Probabilistic Logics. Artificial Intelligence 197:1 24. Thimm, M. 2016. On the expressivity of inconsistency measures. Artificial Intelligence 234:120 151. Thimm, M. 2017. On the compliance of rationality postulates for inconsistency measures: A more or less complete picture. KI-K unstliche Intelligenz 31(1):31 39. Ulbricht, M.; Thimm, M.; and Brewka, G. 2016. Measuring Inconsistency in Answer Set Programs. In Proceedings of the 15th European Conference on Logics in Artificial Intelligence (JELIA 16). Valiant, L. G. 1979. The complexity of computing the permanent. Theoretical computer science 8(2):189 201. Wagner, K. W. 1986. The complexity of combinatorial problems with succinct input representation. Acta informatica 23(3):325 356.