1 Introduction

A general challenge in knowledge representation and reasoning is the handling of uncertain and inconsistent information. The notion of uncertainty here refers to the graded or just unknown assessment of being “true” of some piece of information, from a subjective point of view of a decision-making agent such as a human being. Most of the information any agent possesses is not necessarily strictly true in the actual world and agents have to take into account both uncertainty of factual beliefs—such as “John was supposedly on vacation” and uncertainty on the applicability of rules when deriving new information—such as “When going on vacation, John usually takes his kids with him”. A related notion is inconsistency, which refers (usually) to multiple pieces of information and represents a conflict between those, i. e., they cannot hold at the same time. The two statements “John is on vacation in California” and “John is at home in New York” represent inconsistent information and in order to draw meaningful conclusions from a knowledge base containing these statements, this conflict has to be consolidated somehow. Several fields address the challenge of dealing with inconsistencies by considering different perspectives on the reasons why inconsistencies occur. For example, belief revision [12] considers the scenario where the a priori beliefs of an agent are consistent and a new piece of information—that is potentially contradicting previous beliefs—has to be consistently incorporated in order to obtain the a posteriori beliefs. Similarly, belief merging [25] considers the scenario where multiple belief sets of different agents have to be merged in order to obtain a coherent view on the joint beliefs. While these approaches aim at resolving inconsistencies in the classic-logical sense, other approaches such as paraconsistent logics [3] provide inconsistency-tolerant semantics in order to be able to reason under inconsistency. There are also some works dealing with both inconsistency and (quantitative) uncertainty at the same time such as belief revision and merging for probabilistic knowledge [4, 7, 22, 38].

A quantitative treatment of the challenge of dealing with inconsistencies in knowledge representation is provided by the field of inconsistency measurement, see e. g. [9, 13] for some early surveys. In this field, the main object of research is the inconsistency measure, i. e., a function that assign a non-negative real value to a knowledge base with the informal meaning that larger values indicate a larger inconsistency. These measures are useful for the tasks of analyzing knowledge bases in general [44], identifying the culprits of inconsistency [16], as well as manual and automatic debugging of knowledge bases [10, 38] and inconsistency-tolerant reasoning [39]. The traditional setting for inconsistency measurement is that of classical propositional logic and, beginning with Knight’s inconsistency measure from [23, 24], a lot of proposals of inconsistency measures have been made for this setting [10, 11, 13, 15, 16, 19, 23, 31, 32, 34, 47, 49]. While there are also approaches to inconsistency measurement based on logics incorporating uncertainty [5, 6, 35, 36, 43], we will focus our study here on the classical setting as the variety of different measures in other settings is rather small.

In [14], a first formal proposal was given on what properties a basic inconsistency measure should satisfy. In that work, Hunter and Konieczny proposed the properties consistency (the inconsistency value should be zero iff the knowledge base is consistent), normalization (the inconsistency value should range between zero and one), monotony (adding formulas to the knowledge base should not decrease the inconsistency value), free formula independence (“innocent” formulas can be removed from the knowledge base without changing the inconsistency value), and dominance (semantical weakening of certain formulas should not increase the inconsistency value), to be desirable properties that should be satisfied by a meaningful account to inconsistency measurement. In [16] the property normalization was classified as an additional property and later works such as [11] also did not include dominance in the core set of desirable properties. Following [14] several other works [2, 16, 33, 34, 42, 43] also proposed new rationality postulates, either to replace previously proposed postulates or to extend them. Although these postulates were proposed to evaluate the rationality of concrete approaches to inconsistency measurement, only a few of them have been evaluated wrt. only a subset of the postulates in the references mentioned before.

In this paper, we provide a comprehensive evaluation of 15 inconsistency measures from the recent literature [8, 10, 11, 15, 16, 21, 24, 34, 47, 49] wrt. 18 rationality postulates proposed in [2, 14, 16, 33, 34, 42, 43]. We conduct this evaluation objectively and refrain from discussing the actual rationality of certain postulates and the meaningfulness of certain inconsistency measures in the light of satisfying (or violating) them. In [2], Besnard provides a critical examination of some of the basic postulates mentioned above and we would like to point the interested reader to this work for some excellent discussion on this topic. Similar discussions can also be found in [33, 34]. The present paper shall serve as an overview of the state-of-the-art and as collection of various technical results on the compliance of rationality postulates.

The main contribution of this paper is summarized in Table 1 where the compliance of each of the considered 15 inconsistency measures wrt. 18 rationality postulates is stated. The necessary preliminaries about the logical context are given in Sect. 2, the definitions of the considered inconsistency measures can be found in Sect. 3, and the considered rationality postulates are presented in Sect. 4. An overview on the results is given in Sect. 5 and a final discussion concludes this paper in Sect. 6.

2 Preliminaries

Let \(\mathsf {At}\) be some fixed propositional signature, i. e., a (possibly infinite) set of propositions, and let \(\mathcal {L}(\mathsf {At})\) be the corresponding propositional language constructed using the usual connectives \(\wedge\) (and), \(\vee\) (or), and \(\lnot\) (negation).

Definition 1

A knowledge base \(\mathcal {K}\) is a finite set of formulas \(\mathcal {K}\subseteq \mathcal {L}(\mathsf {At})\). Let \(\mathbb {K}\) be the set of all knowledge bases.

If X is a formula or a set of formulas we write \(\mathsf {At}(X)\) to denote the set of propositions appearing in X. Semantics to a propositional language is given by interpretations and an interpretation \(\omega\) on \(\mathsf {At}\) is a function \(\omega :\mathsf {At}\rightarrow \{\mathsf {true},\mathsf {false}\}\). Let \(\Omega (\mathsf {At})\) denote the set of all interpretations for \(\mathsf {At}\). An interpretation \(\omega\) satisfies (or is a model of) an atom \(a\in \mathsf {At}\), denoted by \(\omega \models a\), if and only if \(\omega (a)=\mathsf {true}\). The satisfaction relation \(\models\) is extended to formulas in the usual way.

For \(\Phi \subseteq \mathcal {L}(\mathsf {At})\) we also define \(\omega \models \Phi\) if and only if \(\omega \models \phi\) for every \(\phi \in \Phi\). Define furthermore the set of models \(\mathsf {Mod}(X)=\{\omega \in \Omega (\mathsf {At})\mid \omega \models X\}\) for every formula or set of formulas X. By abusing notation, a formula or set of formulas \(X_{1}\) entails another formula or set of formulas \(X_{2}\), denoted by \(X_{1}\models X_{2}\), if \(\mathsf {Mod}(X_{1})\subseteq \mathsf {Mod}(X_{2})\). Two formulas or sets of formulas \(X_{1},X_{2}\) are equivalent, denoted by \(X_{1}\equiv X_{2}\), if \(\mathsf {Mod}(X_{1})=\mathsf {Mod}(X_{2})\). Furthermore, two sets of formulas \(X_{1}\), \(X_{2}\) are semi-extensionally equivalent if there is a bijection \(s:X_{1}\rightarrow X_{2}\) such that for all \(\alpha \in X_{1}\) we have \(\alpha \equiv s(\alpha )\) [43]. We denote this by \(X_{1}\equiv ^{s}X_{2}\). If \(\mathsf {Mod}(X)=\emptyset\) we also write \(X\models \perp\) and say that X is inconsistent.

3 Inconsistency Measures

Let \(\mathbb {R}^{\infty }_{\ge 0}\) be the set of non-negative real values including \(\infty\). Inconsistency measures are functions \(\mathcal {I}:\mathbb {K}\rightarrow \mathbb {R}^{\infty }_{\ge 0}\) that aim at assessing the severity of the inconsistency in a knowledge base \(\mathcal {K}\). The basic idea is that the larger the inconsistency in \(\mathcal {K}\) the larger the value \(\mathcal {I}(\mathcal {K})\). For the remainder of the paper, we also denote \(\mathcal {I}(\mathcal {K})\) as the inconsistency value of \(\mathcal {K}\) (wrt. \(\mathcal {I}\)). Inconsistency is a concept that is not easily quantified and there have been a couple of proposals for inconsistency measures so far, in particular for classical propositional logic, see e. g. [2, 17, 19, 32] for some recent works. Here, we select a representative selection of 15 inconsistency measures from the literature in order to conduct our evaluation, taken from [8, 10, 11, 15, 16, 21, 24, 34, 47, 49]. We briefly introduce these measures in this section for the sake of completeness, but we refer for a detailed explanation to the corresponding original papers.

The formal definitions of the considered inconsistency measures can be found in Fig. 1 while the necessary notation for understanding these measures follows below.

Fig. 1
figure 1

Definitions of the considered inconsistency measures

Full size image

The measure \(\mathcal {I}_{d}(\mathcal {K})\) [15] is usually referred to as a baseline for inconsistency measures as it only distinguishes between consistent and inconsistent knowledge bases.

The measures \(\mathcal {I}_{\mathsf {MI}}(\mathcal {K})\) [15], \(\mathcal {I}_{\mathsf {MI^{C}}}(\mathcal {K})\) [15], \(\mathcal {I}_{p}\) [10], and \(\mathcal {I}_{mv}\) [49] are defined using minimal inconsistent subsets. A set \(M\subseteq \mathcal {K}\) is called minimal inconsistent subset (MI) of \(\mathcal {K}\) if \(M\models \perp\) and there is no \(M'\subset M\) with \(M'\models \perp\). Let \(\mathsf {MI}(\mathcal {K})\) be the set of all MIs of \(\mathcal {K}\).

For \(\mathcal {I}_{mc}\) [10], let furthermore \(\mathsf {MC}(\mathcal {K})\) be the set of maximal consistent subsets of \(\mathcal {K}\), i. e., \(\mathsf {MC}(\mathcal {K})=\{\mathcal {K}'\subseteq \mathcal {K}\mid \mathcal {K}'\not \models \perp \wedge \forall \mathcal {K}''\supsetneq \mathcal {K}':\mathcal {K}''\models \perp \}\), and let \(\mathsf {SC}(\mathcal {K})\) be the set of self-contradictory formulas of \(\mathcal {K}\), i. e., \(\mathsf {SC}(\mathcal {K})=\{\phi \in \mathcal {K}\mid \phi \models \perp \}\). Note also that \(\mathcal {I}_{nc}\) [8] uses the concept of maximal consistency in its formal definition, but in a slightly different manner.

The measure \(\mathcal {I}_{\eta }\) [24] considers probability functions P of the form \(P:\Omega (\mathsf {At})\rightarrow [0,1]\) with \(\sum _{\omega \in \Omega (\mathsf {At})}P(\omega )=1\). Let \(\mathcal {P}(\mathsf {At})\) be the set of all those probability functions and for a given probability function \(P\in \mathcal {P}(\mathsf {At})\) define the probability of an arbitrary formula \(\phi\) via \(P(\phi )=\sum _{\omega \models \phi }P(\omega )\).

The measure \(\mathcal {I}_{c}\) [10] utilizes a paraconsistent semantics using three-valued interpretations for propositional logic [40].Footnote 1 A three-valued interpretation \(\upsilon\) on \(\mathsf {At}\) is a function \(\upsilon :\mathsf {At}\rightarrow \{T,F,B\}\) where the values T and F correspond to the classical \(\mathsf {true}\) and \(\mathsf {false}\), respectively. The additional truth value B stands for both and is meant to represent a conflicting truth value for a proposition. Taking into account the truth order \(\prec\) defined via \(T\prec B \prec F\), an interpretation \(\upsilon\) is extended to arbitrary formulas via \(\upsilon (\phi _{1}\wedge \phi _{2})=\min _{\prec }(\upsilon (\phi _{1}),\upsilon (\phi _{2}))\), \(\upsilon (\phi _{1}\vee \phi _{2})=\max _{\prec }(\upsilon (\phi _{1}),\upsilon (\phi _{2}))\), and \(\upsilon (\lnot T)=F\), \(\upsilon (\lnot F)=T\), \(\upsilon (\lnot B)=B\). An interpretation \(\upsilon\) satisfies a formula \(\alpha\), denoted by \(\upsilon \models ^{3}\alpha\) if either \(\upsilon (\alpha )=T\) or \(\upsilon (\alpha )=B\).

For \(\mathcal {I}_{hs}\) [47], a subset \(H\subseteq \Omega (\mathsf {At})\) is called a hitting set of \(\mathcal {K}\) if for every \(\phi \in \mathcal {K}\) there is \(\omega \in H\) with \(\omega \models \phi\).

The Dalal distance \(d_{\text {d}}\) is a distance function for interpretations in \(\Omega (\mathsf {At})\) and is defined as \(d(\omega ,\omega ')=|\{a \in \mathsf {At}\mid \omega (a)\ne \omega '(a)\}|\) for all \(\omega ,\omega '\in \Omega (\mathsf {At})\). If \(X\subseteq \Omega (\mathsf {At})\) is a set of interpretations we define \(d_{\text {d}}(X,\omega )=\min _{\omega '\in X}d_{\text {d}}(\omega ',\omega )\) (if \(X=\emptyset\) we define \(d_{\text {d}}(X,\omega )=\infty\)). We consider the inconsistency measures \(\mathcal {I}^{\Sigma }_{\text {dalal}}\), \(\mathcal {I}^{\max }_{\text {dalal}}\), and \(\mathcal {I}^{\text {hit}}_{\text {dalal}}\) from [11] but only for the Dalal distance. Note that in [11] these measures were considered for arbitrary distances and that we use a slightly different but equivalent definition of these measures.

For every knowledge base \(\mathcal {K}\), \(i=1,\ldots ,|\mathcal {K}|\) define \(\mathsf {MI}^{(i)}(\mathcal {K})=\{M\in \mathsf {MI}(\mathcal {K})\mid |M|=i\}\) and \(\mathsf {CN}^{(i)}(\mathcal {K})=\{C\subseteq \mathcal {K}\mid |C|=i \wedge C\not \models \perp \}\). Furthermore define \(R_i(\mathcal {K})=0\) if \(|\mathsf {MI}^{(i)}(\mathcal {K})|+|\mathsf {CN}^{(i)}(\mathcal {K})|=0\) and otherwise \(R_i(\mathcal {K})=|\mathsf {MI}^{(i)}(\mathcal {K})|/(|\mathsf {MI}^{(i)}(\mathcal {K})|+|\mathsf {CN}^{(i)}(\mathcal {K})|)\). Note that the definition of \(\mathcal {I}_{D_{f}}\) in Table 1 is only one instance of the family studied in [34], other variants can be obtained by different ways of aggregating the values \(R_i(\mathcal {K})\).

Considering \(\mathcal {I}_{P_{m}}\) [21], for an atom \(x\in \mathsf {At}\) or a negated atom \(x=\lnot y\) (\(y\in \mathsf {At}\)) a minimal proof in \(\mathcal {K}\) is a set \(\pi \subseteq \mathcal {K}\) such that (1) x appears as a subformula in some \(\alpha \in \pi\), (2) \(\pi \models x\), and (3) \(\pi\) is minimal wrt. set inclusion (note that \(\pi\) is not necessarily consistent). Let \(P^{\mathcal {K}}_m(x)\) be the set of all minimal proofs of x in \(\mathcal {K}\). Note that the definition of \(\mathcal {I}_{P_{m}}\) in Fig. 1 is not the original definition but a characterization also provided in [21].

We conclude this section with a small example illustrating the behavior of the considered inconsistency measures.

Example 1

Let \(\mathcal {K}_{1}\) and \(\mathcal {K}_{2}\) be given as

$$\begin{aligned} \mathcal {K}_{1}&= \{a,b\vee c, \lnot a \wedge \lnot b,d\} \\ \mathcal {K}_{2}&= \{a, \lnot a, b, \lnot b\} \end{aligned}$$

Then

$$\begin{array}{ll} \mathcal {I}_{d}(\mathcal {K}_{1})=1&\mathcal {I}_{d}(\mathcal {K}_{2})= 1 \\ \mathcal {I}_{\mathsf {MI}}(\mathcal {K}_{1})= 1&\mathcal {I}_{\mathsf {MI}}(\mathcal {K}_{2})= 2 \\ \mathcal {I}_{\mathsf {MI^{C}}}(\mathcal {K}_{1})= 1/2&\mathcal {I}_{\mathsf {MI^{C}}}(\mathcal {K}_{2})= 1\\ \mathcal {I}_{\eta }(\mathcal {K}_{1})= 1/2&\mathcal {I}_{\eta }(\mathcal {K}_{2})= 1/2\\ \mathcal {I}_{c}(\mathcal {K}_{1})= 1&\mathcal {I}_{c}(\mathcal {K}_{2})= 2 \\ \mathcal {I}_{mc}(\mathcal {K}_{1})= 1&\mathcal {I}_{mc}(\mathcal {K}_{2})= 3 \\ \mathcal {I}_{p}(\mathcal {K}_{1})= 2&\mathcal {I}_{p}(\mathcal {K}_{2})= 4 \\ \mathcal {I}_{hs}(\mathcal {K}_{1})= 1&\mathcal {I}_{hs}(\mathcal {K}_{2})= 1 \\ \mathcal {I}^{\Sigma }_{\text {dalal}}(\mathcal {K}_{1})= 1&\mathcal {I}^{\Sigma }_{\text {dalal}}(\mathcal {K}_{2})= 2 \\ \mathcal {I}^{\max }_{\text {dalal}}(\mathcal {K}_{1})= 1&\mathcal {I}^{\max }_{\text {dalal}}(\mathcal {K}_{2})= 1 \\ \mathcal {I}^{\text {hit}}_{\text {dalal}}(\mathcal {K}_{1})= 1&\mathcal {I}^{\text {hit}}_{\text {dalal}}(\mathcal {K}_{2})= 2 \\ \mathcal {I}_{D_{f}}(\mathcal {K}_{1})= 1/12&\mathcal {I}_{D_{f}}(\mathcal {K}_{2})= 1/6 \\ \mathcal {I}_{P_{m}}(\mathcal {K}_{1})= 1&\mathcal {I}_{P_{m}}(\mathcal {K}_{2})= 2 \\ \mathcal {I}_{mv}(\mathcal {K}_{1})= 1/2&\mathcal {I}_{mv}(\mathcal {K}_{2})= 1 \\ \mathcal {I}_{nc}(\mathcal {K}_{1})= 3&\mathcal {I}_{nc}(\mathcal {K}_{2})= 3 \end{array}$$

A web application for trying out all the discussed inconsistency measures can be found on the website of the Tweety projectFootnote 2, cf. [45].

4 Rationality Postulates

In the previous section, we recalled concrete approaches to inconsistency measurement from the literature. However, the question is still open what these functions should actually measure. In the classic-logical sense, inconsistency is a binary concept. Either a knowledge base is inconsistent or it is consistent. Inconsistency measures address the challenge to further distinguish inconsistent knowledge bases in a similar manner as information measures [28, 41] address the issue of further distinguishing consistent knowledge bases, in particular through measuring the information content. While information content can be formalized in a way that is (mostly) agreed upon in the community, the concept of inconsistency has no such generally accepted formalization. Instead, rationality postulates have been proposed to give general guidelines on how inconsistency measures should behave in certain scenarios. In the following, we recall 18 rationality postulates that have been proposed in the literature [2, 14, 16, 33, 34, 42, 43]. We will refrain from discussing the actual rationality of these postulates and only recall the original motivation for stating these postulates as desirable properties.

The first set of rationality postulates has been proposed in [14] in order to provide a definition of a basic inconsistency measure. In order to state these postulates we need one further definition.

Definition 2

A formula \(\alpha \in \mathcal {K}\) is called free formula if \(\alpha \notin \bigcup \mathsf {MI}(\mathcal {K})\). Let \(\mathsf {Free}(\mathcal {K})\) be the set of all free formulas of \(\mathcal {K}\).

In other words, a free formula is basically a formula that is not directly participating in any derivation of a contradiction. Using this definition and the concepts already introduced before, the first five rationality postulates of [14] can be stated as follows. For the remainder of this section, let \(\mathcal {I}\) be any function \(\mathcal {I}:\mathbb {K}\rightarrow \mathbb {R}^{\infty }_{\ge 0}\), \(\mathcal {K},\mathcal {K}'\in \mathbb {K}\), and \(\alpha ,\beta \in \mathcal {L}(\mathsf {At})\).

  • Consistency (CO) \(\mathcal {I}(\mathcal {K})=0\) if and only if \(\mathcal {K}\) is consistent

  • Normalization (NO) \(0\le \mathcal {I}(\mathcal {K})\le 1\)

  • Monotony (MO) If \(\mathcal {K}\subseteq \mathcal {K}'\) then \(\mathcal {I}(\mathcal {K})\le \mathcal {I}(\mathcal {K}')\)

  • Free-formula independence (IN) If \(\alpha \in \mathsf {Free}(\mathcal {K})\) then \(\mathcal {I}(\mathcal {K})=\mathcal {I}(\mathcal {K}\setminus \{\alpha \})\)

  • Dominance (DO) If \(\alpha \not \models \perp\) and \(\alpha \models \beta\) then \(\mathcal {I}(\mathcal {K}\cup \{\alpha \})\ge \mathcal {I}(\mathcal {K}\cup \{\beta \})\)

The first postulate, CO, requires that consistent knowledge bases receive the minimal inconsistency value zero and every inconsistent knowledge base has a strictly positive inconsistency value. This postulate is actually the only generally accepted postulate and describes the minimal requirement for an inconsistency measure. An inconsistency measure \(\mathcal {I}\) that satisfies CO does not distinguish between consistent knowledge bases and can, at least, distinguish inconsistent knowledge bases from consistent ones.

The postulate NO states that the inconsistency value is always in the unit interval, thus allowing inconsistency values to be comparable even if knowledge bases are of different sizes. In later works, this postulate is usually regarded as an optional feature.

MO requires that adding formulas to the knowledge base cannot decrease the inconsistency value. Besides CO this is the least disputed postulate and most inconsistency measures do satisfy it (Sect. 5).

IN states that removing free formulas from the knowledge base should not change the inconsistency value. The motivation here is that free formulas do not participate in inconsistencies and should not contribute to having a certain inconsistency value.

DO says that substituting a consistent formula \(\alpha\) by a weaker formula \(\beta\) should not increase the inconsistency value. Here, as \(\beta\) carries less information than \(\alpha\) there should be less opportunities for inconsistencies to occur.

The set of postulates was extended in [42] for the case of inconsistency measurement in probabilistic logics. However, we can state these postulates also for propositional logic.

Definition 3

A formula \(\alpha \in \mathcal {K}\) is called safe formula if it is consistent and \(\mathsf {At}(\alpha )\cap \mathsf {At}(\mathcal {K}\setminus \{\alpha \})=\emptyset\). Let \(\mathsf {Safe}(\mathcal {K})\) be the set of all safe formulas of \(\mathcal {K}\).

A formula is safe, if its signature is disjoint from the signature of the rest of the knowledge base, cf. the concept of language splitting in belief revision [26, 37]. Every safe formula is also a free formula [42].

  • Safe-formula independence (SI) If \(\alpha \in \mathsf {Safe}(\mathcal {K})\) then \(\mathcal {I}(\mathcal {K})=\mathcal {I}(\mathcal {K}\setminus \{\alpha \})\)

  • Super-Additivity (SA) If \(\mathcal {K}\cap \mathcal {K}'=\emptyset\) then \(\mathcal {I}(\mathcal {K}\cup \mathcal {K}')\ge \mathcal {I}(\mathcal {K})+\mathcal {I}(\mathcal {K}')\)

  • Penalty (PY) If \(\alpha \notin \mathsf {Free}(\mathcal {K})\) then \(\mathcal {I}(\mathcal {K})>\mathcal {I}(\mathcal {K}\setminus \{\alpha \})\)

The postulate SI requires that removing isolated formulas from a knowledge base cannot change the inconsistency value. This postulate is a weakening of IN, i. e., if a measure \(\mathcal {I}\) satisfies IN it also satisfies SI, cf. [42] and Theorem 1.

SA is a strengthening of MO [42] and requires that the sum of the inconsistency values of two disjoint knowledge bases is not larger than the inconsistency value of the joint knowledge base.

PY is the complementary postulate to IN and states that adding a formula participating in inconsistency must have a positive impact on the inconsistency value.

The following two postulates have been first used in [16]:

  • MI -separability (MI) If \(\mathsf {MI}(\mathcal {K}_{1}\cup \mathcal {K}_{2})=\mathsf {MI}(\mathcal {K}_{1})\cup \mathsf {MI}(\mathcal {K}_{2})\) and \(\mathsf {MI}(\mathcal {K}_{1})\cap \mathsf {MI}(\mathcal {K}_{2})=\emptyset\) then \(\mathcal {I}(\mathcal {K}_{1}\cup \mathcal {K}_{2})=\mathcal {I}(\mathcal {K}_{1})+\mathcal {I}(\mathcal {K}_{2})\)

  • MI -normalization (MN) If \(M\in \mathsf {MI}(\mathcal {K})\) then \(\mathcal {I}(M)=1\)

MI focuses particularly on the role of minimal inconsistent subsets in the determination of the inconsistency value. It states that the sum of the inconsistency values of two knowledge bases that have “non-interfering” sets of minimal inconsistent subsets should be the same as the inconsistency value of their union.

MN demands that a minimal inconsistent subset is the atomic unit for measuring inconsistency by requiring that the inconsistency value of any minimal inconsistent subset is one.

The following postulates have been proposed in [33] to further define the role of minimal inconsistent subsets in measuring inconsistency:

  • Attenuation (AT) \(M,M'\in \mathsf {MI}(\mathcal {K})\) and \(\mathcal {I}(M)<\mathcal {I}(M')\) implies \(|M|>|M'|\)

  • Equal Conflict (EC) \(M,M'\in \mathsf {MI}(\mathcal {K})\) and \(\mathcal {I}(M)=\mathcal {I}(M')\) implies \(|M|=|M'|\)

  • Almost Consistency (AC) Let \(M_{1},M_{2},\ldots\) be a sequence of minimal inconsistent sets \(M_{i}\) with \(\lim _{i\rightarrow \infty }|M_{i}| = \infty\), then \(\lim _{i\rightarrow \infty }\mathcal {I}(M_{i}) = 0\)

The postulate AT states that minimal inconsistent sets of smaller size should have a larger inconsistency value. The motivation of this postulate stems from the lottery paradoxFootnote 3 [27].

The postulate EC is the counterpart of AT and requires minimal inconsistent subsets having the same inconsistency value also to have the same size.

AC considers the inconsistency values on arbitrarily large minimal inconsistent subsets in the limit and requires this to be zero.

The following postulates are from [34].

  • Contradiction (CD) \(\mathcal {I}(\mathcal {K})=1\) if and only if for all \(\emptyset \ne \mathcal {K}'\subseteq \mathcal {K}\), \(\mathcal {K}'\models \perp\)

  • Free Formula Dilution (FD) If \(\alpha \in \mathsf {Free}(\mathcal {K})\) then \(\mathcal {I}(\mathcal {K})\ge \mathcal {I}(\mathcal {K}\setminus \{\alpha \})\)

CD is meant as an extension of NO and states that a knowledge base is maximally inconsistent if all non-empty subsets are inconsistent. Note that CD only makes sense if NO is satisfied as well. We do not consider here the property Monotony w.r.t. Conflict Ratio from [34] as it is too specifically tailored for the measure \(\mathcal {I}_{D_{f}}\).

The following property has been first mentioned in [43]:

  • Irrelevance of Syntax (SY) If \(\mathcal {K}_{1}\equiv ^{s}\mathcal {K}_{2}\) then \(\mathcal {I}(\mathcal {K}_{1})=\mathcal {I}(\mathcal {K}_{2})\)

SY states that knowledge bases with pairwise equivalent formulas should receive the same inconsistency value.

In [2] a series of further postulates have been discussed. For our current study, we only consider the following two:

  • Exchange (EX) If \(\mathcal {K}'\not \models \perp\) and \(\mathcal {K}'\equiv \mathcal {K}''\) then \(\mathcal {I}(\mathcal {K}\cup \mathcal {K}')=\mathcal {I}(\mathcal {K}\cup \mathcal {K}'')\)

  • Adjunction Invariance (AI) \(\mathcal {I}(\mathcal {K}\cup \{\alpha ,\beta \})=\mathcal {I}(\mathcal {K}\cup \{\alpha \wedge \beta \})\)

EX is similar in spirit to SY and demands that exchanging consistent parts of the knowledge base with equivalent ones should not change the inconsistency value.

AI demands that the set notation of knowledge bases should be equivalent to the conjunction of its formulas in terms of inconsistency values. In difference to EX note that AI has no precondition on the consistency of the considered formulas.

The rationality postulates presented so far are not independent. The following theorem shows some general relationships (a statement “A implies B” is meant to be read as “if a measure satisfies A then it satisfies B”; a statement “A\(_{1}\),..., A\(_{n}\) are incompatible” means “there is no measure satisfying A\(_{1}\),..., A\(_{n}\) at the same time”).

Theorem 1

 

  1. 1.

    IN implies SI

  2. 2.

    IN implies FD

  3. 3.

    SA implies MO

  4. 4.

    MN and AC are incompatible

  5. 5.

    MN and CD are incompatible

  6. 6.

    MO implies FD

  7. 7.

    MN, MI, and NO are incompatible

  8. 8.

    MN, SA, and NO are incompatible

The proof of the above theorem is given in the online appendixFootnote 4, see also [2] for some more detailed discussions.

5 Compliance of Inconsistency Measures

Table 1 Compliance of inconsistency measures with rationality postulates; previous results are indicated by a super-scripted reference of the original work (some of the results have been shown in multiple publications, only the first occurrence is cited)
Full size table

Table 1 gives the complete picture on which inconsistency measure satisfies (\(\checkmark\)) and violates (\(\times\)) the previously discussed rationality postulates. Some of these results have been shown before in [10, 11, 15, 16, 18, 21, 24, 34, 43, 47, 49]Footnote 5, marked correspondingly in Table 1. The proofs and counterexamples of the remaining statements are all given in the online appendix\(^4\). Note that in [49] it has been shown that \(\mathcal {I}_{mv}\) satisfies restricted versions of MO and IN where only formulas are considered that do not use fresh propositions.

The only rationality postulate where all considered measures agree upon is CO, which is not surprising as it captures the minimal requirement for any inconsistency measure. Most measures also satisfy MO, which is also the least disputed in the literature. The only cases where MO fails is usually when NO is satisfied, cf. \(\mathcal {I}_{D_{f}}\) and \(\mathcal {I}_{mv}\). However, note that MO and NO are not generally incompatible as e. g. \(\mathcal {I}_{\eta }\) satisfies both. Some other postulates are violated by most of the considered inconsistency measures, in particular if they address a very specific feature. For example, CD is motivated by the measure \(\mathcal {I}_{D_{f}}\)—which is also the only one satisfying it—and can be seen as the counterpart to CO as it describes a concept of maximal inconsistency. Of course, requiring that a maximally inconsistent knowledge base receives the maximal possible inconsistency value is a desirable property. The specific instance of this requirement in CD, i. e., that maximal inconsistency is defined by not having non-empty consistent subsets and that the maximal value is 1, is very specific to \(\mathcal {I}_{D_{f}}\). The value 1 only makes sense when the measure is normalized, so that 1 is indeed the maximal possible value. Moreover, also the definition of maximal inconsistency requires some more investigation.

One important thing to note from the results shown in Table 1, is that there are no two inconsistency measures that are equivalent in terms of these postulates. More precisely, for every pair of inconsistency measures \(\mathcal {I}, \mathcal {I}'\) discussed in this paper there is always at least one postulate which is satisfied by \(\mathcal {I}\) and violated by \(\mathcal {I}'\) (or vice versa). A simple corollary of this is, that all considered inconsistency measures are different from each other. That is, for every pair of measures \(\mathcal {I}, \mathcal {I}'\) we can find knowledge bases \(\mathcal {K}_{1},\mathcal {K}_{2}\) such that \(\mathcal {I}(\mathcal {K}_{1})<\mathcal {I}(\mathcal {K}_{2})\) and \(\mathcal {I}'(\mathcal {K}_{1})\ge \mathcal {I}'(\mathcal {K}_{2})\) (or vice versa).

It can also be seen that satisfaction of many rationality postulates is not a sufficient criterion for evaluating an inconsistency measure, as the drastic inconsistency measure already satisfies 12 of the 18 considered postulates—which is also the maximal number of postulates satisfied by any measure—but should not be seen as a meaningful inconsistency measure. Moreover, the drastic inconsistency measure is also the only measure besides \(\mathcal {I}_{c}\) satisfying EX and AI, which have been proposed in [2] as a more meaningful alternative to the existing postulates. These observations call for more investigations in rationality postulates for inconsistency measurement, as the existing ones are obviously not able to sufficiently assess the quality of a measure. One particular approach to complement rationality postulates in this regard is to analyze the expressivity of inconsistency measures, i. e., the number of different inconsistency values that can be attained on some class of knowledge bases. See [46] for a recent discussion on this topic.

6 Conclusion

In this paper, we provided a comprehensive evaluation of recent approaches to inconsistency measures wrt. several rationality postulates from the literature. It therefore extends previous partial investigations, serves as an overview of the state-of-the-art, and as collection of various technical results on the compliance of rationality postulates (which, due to space limitations, can be found in the online appendix\(^{4}\)).

Our investigation on compliance is comprehensive but, of course, not complete. In particular, we did not yet consider the measures of [1, 18–20] and, for example, the property weak dominance from [19]. There are variants of the inconsistency measure \(\mathcal {I}_{c}\) which are also based on multi-valued interpretations, see e. g. [16, 29, 30].

Our investigation shows that, besides the postulate CO, there is no common agreement on the variety of rationality postulates. This calls for both, a deeper investigation of rationality postulates and the development of new measures satisfying them. Furthermore, besides the satisfaction of rationality postulates, other dimensions for evaluating inconsistency measures should also be taken into account such as the aforementioned expressivity [46] as well as computational complexity [48].