On Measuring Inconsistency Using Maximal Consistent Sets

Abstract

An important problem in knowledge-based systems is inconsistency handling. This problem has recently been attracting a lot of attention in AI community. In this paper, we tackle the problem of evaluating the amount of conflicts in knowledge bases, and provide a new fine grained inconsistency measure, denoted MCSC, based on maximal consistent sets. In particular, it is suitable in systems where inconsistency results from multiple consistent sources. We show that our measure satisfies several rational postulates proposed in the literature. Moreover, we provide an encoding in integer linear programming for computing MCSC.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

In classical logics, the principle of explosion is a law which states that any formula can be deduced from a contradiction using the inference process. This principle means that the inference process alone in classical logic does not allow to reason under inconsistency. To remedy this problem, several approaches have been proposed in the literature, such as argumentation theory, paraconsistent logics, belief revision, etc. The main goal of these approaches is to deal with inconsistency as an informative concept. In the same vein, inconsistency measures have been introduced in order to be used in analyzing inconsistency. In the literature, an inconsistency measure is defined as a function that associates a value to each knowledge base [1]. Several inconsistency measures have been proposed in the literature (e.g. [1–8]), and it has been shown that they are suitable for various applications such as e-commerce protocols [9], software specifications [10], belief merging [5], news reports [11], requirements engineering [1], integrity constraints [12], databases [13], ontologies [14], semantic web [14], network intrusion detection [15], and multi-agent systems [8].

In [1], Hunter and Konieczny have proposed four axiomatic properties that any inconsistency measure should satisfy. Namely, the properties of consistency, monotony, free-formula independence, and dominance. However, in a recent article [16], Besnard has provided objections to the axiomatic properties of free-formula independence and dominance. Indeed, the author has pointed out in his article undesirable consequences of these properties, such as ignoring certain conflicts, and has provided alternative properties in order to avoid these consequences.

Inconsistency is often measured by quantifying its origin in a monodimensional way, such as the number of minimal inconsistent subsets. However, no value alone can capture the multiple aspects of inconsistency. Indeed, inconsistency in a knowledge base may result from several reasons and has to be measured in a multi-dimensional way. For instance, let us consider the knowledge base $K=\{p, \lnot p\wedge q, \lnot p\wedge r,\lnot p\wedge s\}$. Clearly, the inconsistency of K results from the conflict between the formula p and the subformula $\lnot p$ in the other formulæ. If we use the inconsistency measure $I_{LP_m}$ defined in [4] and based on Priest’s three-valued logic [17], then we can capture the conflict between a and $\lnot a$ ($I_{LP_m}(K)=1$). However, since $I_{LP_m}$ consider K as a single formula, it does not reveal the fact that there are three conflicts between the formulæ of K. To this end, one can use the measure $I_{MI}$ [1] defined as the number of minimal inconsistent subsets of K ($I_{MI}(K)=3$). The measure $I_{MI}$ is not more informative than $I_{LP_m}$ and conversely, but the two measures provide information about incomparable facets of inconsistency. In other words, two measures are not necessarily comparable in the sense that one is better than the other, they can capture incomparable aspects that constitute inconsistency. We think that Besnard’s objections to the properties of free-formula independence and dominance may be used to argue in this sense. For instance, the property of free-formula independence has a sense when we do not consider the internal structure of the formulæ in a knowledge base. Indeed, it simply means that adding a new formula which is not involved in a conflict does not change the amount of inconsistency.

In this work, we introduce an inconsistency measure, denoted MCSC, by following an approach based on the use of maximal consistent subsets. This approach consists in considering that the inconsistency of a knowledge base is a consequence of the fact that its pieces of information are received from ignored multiple consistent sources, where each possible source is identified by a consistent subset of formulæ. In this context, the degree of conflict of a knowledge base can be seen as the smallest number of pieces of information that cannot be shared by possible sources covering all the elements of this base. Clearly, computing this value can be performed by considering only the possible sources identified by the maximal consistent subsets since the objective consists in minimizing the number of non shared pieces of information.

We show that our inconsistency measure satisfies several desirable properties proposed in the literature, such as Free Formula Independence and Super-additivity. We also provide properties of bounds on MCSC. Then, we study the relationship between our measure and the inconsistency metric proposed in [18]. This study comes from the fact that these two measures satisfy a fundamental property, called Independent MIS-additivity. Finally, we show that our measure can be formulated as an integer linear program by providing an encoding allowing its computation.

2 Formal Setting

In this section, we define the syntax and the semantics of propositional logic. Let ${{\mathsf {Prop}}}$ be a countably set of propositional variables. We use the letters p, q, r, etc. to range over ${{\mathsf {Prop}}}$. The set of propositional formulæ, denoted ${{\mathsf {Form}}}$, is defined inductively started from ${{\mathsf {Prop}}}$, the constant ${{\perp }}$ denoting absurdity, the constant $\top$ denoting true, and using the logical connectives $\lnot$, $\wedge$, $\vee$, $\rightarrow$. Notationally, we use the greek letters $\phi$, $\psi$ to represent formulæ. Given a syntactic object S, we use $\mathcal{P}(S)$ to denote the set of propositional variables appearing in S. For a set S, we denote by |S| its cardinality.

A Boolean interpretation $\mathcal{I}$ of a formula $\phi$ is defined as a function from $\mathcal{P}(\phi )$ to $\{0, 1\}$ (0 corresponds to false and 1 to true). It is inductively extended to propositional formulæ as usual. A formula $\phi$ is consistent if there exists a Boolean interpretation $\mathcal I$ of $\phi$ such that $\mathcal{I}(\phi )=1$. $\phi$ is valid or a theorem, if every Boolean interpretation is a model of $\phi$.

It is worth noticing that we can restrict the language to the connectives $\lnot$ and $\wedge$, since we have the following equivalences: $\phi \vee \psi \equiv \lnot (\lnot \phi \wedge \lnot \psi )$ and $\phi \rightarrow \psi \equiv \lnot \phi \vee \psi$. A knowledge base K is a finite set of propositional formulæ.

Definition 1

Let K be a knowledge base. M is a minimal inconsistent subset (MIS) of K iff (i) $M \subseteq K$, (ii) $M \vdash \bot$ and (iii) $\forall \phi \in M$, $M \setminus \{\phi \} \nvdash \bot$.

We denote by MISes(K) the set of all minimal inconsistent subsets of K.

Definition 2

Let K be a knowledge base and M a subset of K. M is a maximal consistent subset (MCS) of K iff (i) $M \subseteq K$, (ii) $M \nvdash \bot$, (iii) $\forall \phi \in K \setminus M$, $M \cup \{\phi \} \vdash \bot$.

We denote by MCSes(K) the set of all maximal consistent sets of K.

Definition 3

Let K be a knowledge base and $\phi$ a knowledge in K. $\phi$ is a free knowledge in K iff $\phi \notin M$ for every $M\in MISes(K)$.

We use Free(K) to denote the set of free knowledge in K.

In recent years, inconsistent data reasoning has seen a revival in interest because of number of challenges in terms of collecting, modelling, representing, and querying the information. In this context, various logic-based approaches have been proposed in the literature for quantifying the amount of inconsistency. Therefore, several properties have been defined to characterize such measures. More specifically, in [1] the authors propose axiomatic properties that any inconsistency measure should satisfy. An inconsistency measure I is called a basic inconsistency measure if it satisfies the following properties, for all knowledge bases K and $K'$, and for all formulæ $\phi$ and $\psi$:

• Consistency: $I(K) = 0$ iff K is consistent;

• Monotony: $I(K) \le I(K \cup K')$;

• Free Formula Independence: if $\phi \in free(K)$, then $I(K) = I(K\setminus \{\phi \})$;

• Dominance: if $\phi \vdash \psi$ and $\phi \nvdash \bot$, then $I(K\cup \{\psi \}) \le I(K \cup \{ \phi \})$.

It is worth noticing that Besnard has provided in [16] objections on the properties of free formula independence and dominance. In particular, the objection to the property of free formula independence comes from the fact that a free formula may be involved in a conflict and in this case it has to increase the amount of inconsistency. Let us consider, for instance, the following knowledge base proposed in [16]: $K=\{p \wedge r,q\wedge \lnot r, \lnot p\vee \lnot q\}$. The knowledge base K has a single minimal inconsistent subset $M=\{p \wedge r, q\wedge \lnot r\}$ and, consequently, $\lnot p \vee \lnot q$ is a free-formula in K. Using the property of free-formula independence, we should have $I(M)=I(K)$. However, p and q are compatible and $p \wedge q$ is contradicted by the free-formula $\lnot p\vee \lnot q$. Consequently, one can consider that K contains more conflicts than M and in this case the free-formula independence property fails. Let us note that to detect whether free-formulæ are involved in a conflict, we have to consider the internal structure of formulæ.

We agree with Besnard’s objections in the sense that it is not suitable to require Hunter and Konieczny’s basic properties for any inconsistency measure. However, we think that inconsistency is a multi-dimensional concept and a single inconsistency measure is insufficient to capture all the information about the amount of inconsistency. In this context, to capture certain aspects that constitute inconsistency, we need inconsistency measures satisfying Hunter and Konieczny’s properties. In particular, aspects which are not related to internal structure of formulæ in knowledge bases.

3 MCS-Cover Based Inconsistency Measure

In this section, we introduce a new inconsistency measure, denoted MCSC, which is based on the use of the MCSes. Intuitively, the main idea behind MCSC is in considering that the inconsistency is due to the fact that the information are often received from ignored multiple consistent information sources. In this context, the degree of conflict corresponds to the smallest number of knowledges that cannot be shared by possible information sources. The possible information sources are characterized by the consistent subsets. Since our aim is to minimize non shared knowledges, we only consider the possible information sources characterized by the MCSes.

Let us first define the following fundamental concepts that will be useful in the sequel.

Definition 4

(MCS-Cover). Let K be a knowledge base. A MCS-cover $\mathcal C$ of K is a subset of MCSes(K) such that $\bigcup _{S\in \mathcal{C}}S = K$.

Let us consider, for instance, the knowledge base $K = \{\lnot p\vee \lnot q, \lnot p\vee \lnot r, \lnot q\vee \lnot r, p,q,r \}$. The following two sets are MCS-covers of K: $\mathcal{C}_1=\{ \{\lnot p\vee \lnot q, \lnot p\vee \lnot r, \lnot q\vee \lnot r, p\}, \{p,q,r \}\}$, $\mathcal{C}_2=\{ \{\lnot p\vee \lnot q, \lnot p\vee \lnot r, \lnot q\vee \lnot r, p\}, \{\lnot p\vee \lnot q, \lnot p\vee \lnot r,q,r \}\}$.

We now define a preorder relation on the MCS-covers of a given knowledge base, denoted $\succeq$. Let K be a knowledge base. For all $\mathcal C$ and $\mathcal C'$ two MCS-covers of K, $\mathcal{C}\succeq \mathcal{C'}$ if and only if $|\bigcap _{S\in \mathcal{C}}S|\mathrel {\geqslant }|\bigcap _{S'\in \mathcal{C'}}S'|$. Let us consider again the previous example. We have $\mathcal{C}_2\succeq \mathcal{C}_1$ since $|\{\lnot p\vee \lnot q, \lnot p\vee \lnot r, \lnot q\vee \lnot r, p\}\cap \{p,q,r \}|=1$ and $|\{\lnot p\vee \lnot q, \lnot p\vee \lnot r, \lnot q\vee \lnot r, p\}\cap \{\lnot p\vee \lnot q, \lnot p\vee \lnot r,q,r \}|=2$.

Definition 5

(Normal MCS-Cover). Let K be a knowledge base and $\mathcal C$ an MCS-cover of K. Then, $\mathcal C$ is a normal MCS-cover if $\mathcal C'$ is not an MCS-cover for every $\mathcal{C}'\subset \mathcal C$.

Definition 6

(Maximum MCS-Cover). Let K be a knowledge base and $\mathcal C$ a MCS-cover of K. Then, $\mathcal C$ is said to be a maximum MCS-cover of K if it is normal and $\forall ~ \mathcal C'$ MCS-cover of K, $\mathcal C \succeq \mathcal C'$. We denote by $\lambda (K)$ the value $|\bigcap _{S\in \mathcal{C}}S|$.

Definition 7

(MCSC). Let K be a knowledge base. The inconsistency measure of K, denoted MCSC(K), is defined as follows: ${MCSC}(K) = {|K|-\lambda (K)}$.

Regarding the previous example of knowledge base, we have $MCSC(K)=4$ since $\mathcal{C}_2$ is a maximum MCS-cover.

We now provide a generalization of the inconsistency measure MCSC. The base idea consists in associating a weight to each formula in a knowledge base representing the degree of its relevance. In this context, the inconsistency value corresponds to the smallest weight of non shared knowledge.

Given a knowledge base K, we define a weight function W of K as a function from K to $\mathbb {N}^*$.

Definition 8

(Weighted Maximum MCS-Cover). Let K be a knowledge base, W a weight function of K and $\mathcal C$ a MCS-cover of K. Then, $\mathcal C$ is said to be a weighted maximum MCS-cover of K w.r.t. W if it is normal and $\sum _{\phi \in \bigcap _{M\in \mathcal C} M} W(\phi )\mathrel {\geqslant }\sum _{\phi \in \bigcap _{M\in \mathcal C'} M} W(\phi )$ for every MCS-cover $\mathcal C'$. We denote by $\lambda (K,W)$ the value $\sum _{\phi \in \bigcap _{M\in \mathcal C} M} W(\phi )$.

Definition 9

(WMCSC). Let K be a knowledge base and W a weight function of K. The inconsistency measure of K, denoted WMCSC(K, W), is defined as follows: ${MCSC}(K) = {|K|-\lambda (K,W)}$.

Clearly, WMCSC can be seen as a generalization of MCSC. Indeed, by using a weight function W giving the weight 1 to every formula in the knowledge base K, we get $WMCSC(K,W)=MCSC(K)$. Let us note that there are several ways to define a weight function of a knowledge base from the structure of its formulæ. For instance, the weight of a formula may be defined as the number of propositional variables occurring in it. Intuitively, this means that the importance of a knowledge depends on the number of pieces of information which are binded by it.

4 Properties of MCSC Measure

In the section, we describe some important properties of the inconsistency measure MCSC. We first show that it satisfies the properties of consistency, monotony, free formula independence, and a weak form of the property of dominance. Then, we show that our measure satisfies also the property of super-additivity.

Proposition 1

MCSC measure satisfies Consistency, Monotony and Free Formula Independence.

Proof

Consistency. Let K be a consistent knowledge base. Then, $\{K\}$ is the unique maximum MCS-cover of K ($\lambda (K)=|K|$). Hence, $MCSC(K)=0$.

Monotony. Proposition 3 can be seen as a generalization of Monotony.

Free Formula Independence. Let K be a knowledge base and $\phi$ a free formula in K. Let $\mathcal{C}=\{S_1,\ldots {}, S_n\}$ be a maximum MCS-cover of $K\setminus \{\phi \}$. Since $\phi \in Free(K)$, $S_i\cup \{\phi \}\nvdash {{\perp }}$ holds for every $1\mathrel {\leqslant }i\mathrel {\leqslant }n$. Thus, $\{S_1\cup \{\phi \},\ldots {}, S_n\cup \{\phi \}\}$ is a maximum MCS-cover of K and we obtain $\lambda (K) = \lambda (K\setminus \{\phi \})+ 1$. As a consequence, $MCSC(K) = |K|-\lambda (K)= |K\setminus \{\phi \}|+1- \lambda (K\setminus \{\phi \})-1= MCSC(K\setminus \{\phi \})$.

Proposition 2

Let K be a knowledge base and $\phi$ and $\psi$ two formulæ such that $\phi \nvdash {{\perp }}$ and $\phi \mathbin {\vdash }\psi$. If $\phi \notin K$ or $\psi \in K$, then $MCSC(K\cup \{\psi \}) \le MCSC(K \cup \{ \phi \})$.

Proof

Let $\mathcal{C}$ be a maximum MCS-cover of $K\cup \{\phi \}$. We consider w.l.o.g. that $\psi \notin K$ since MCSC satisfies the property of monotony. Clearly, by replacing in $\mathcal C$ the formula $\phi$ with $\psi$ we obtain a set of satisfiable subsets of $K\cup \{\psi \}$. As a consequence, we have $\lambda (K\cup \{ \psi \})\mathrel {\geqslant }\lambda (K\cup \{\phi \})$. Thus, we obtain $MCSC(K\cup \{\psi \})= |K\cup \{\psi \}|-\lambda (K\cup \{ \psi \})\mathrel {\leqslant }|K\cup \{\phi \}|-\lambda (K\cup \{\phi \})= MCSC(K\cup \{\phi \})$.

Let us note that MCSC does not satisfy Dominance. Consider for instance the knowledge base $K=\{p \wedge (p\rightarrow q), \lnot q\}$. We have $p \wedge (p \rightarrow q)\nvdash {{\perp }}$, $p \wedge (p \rightarrow q)\mathbin {\vdash }q$ and $\lambda (K)=0$. Moreover, $\lambda (K\cup \{q\})=0$ holds. Then, we have $MCSC(K\cup \{q\})=3>MCSC(K\cup \{p \wedge (p \rightarrow q)\})=2$.

Other rational postulates than those of the basic system have been proposed in the literature. In particular, we consider the following additivity properties introduced in [1, 19]:

• Super-additivity: if $K\cap K'=\emptyset$, then $I(K\cup K')\mathrel {\geqslant }I(K)+I(K')$.

• MIS-additivity: if $MISes(K)= MISes(K')\uplus MISes(K'')$, then $I(K)= I(K')+I(K'')$.

One can easily see that Super-additivity is a generalization of Monotony.

Proposition 3

MCSC measure satisfies Super-additivity.

Proof

Let K and $K'$ be two knowledge bases such that $K\cap K'=\emptyset$ and $\mathcal C$ a maximum MCS-cover of $K\cup K'$. Clearly, for all $S\in MCSes(K\cup K')$, there exist $S'\in MCSes(K)$ and $S''\in MCSes(K')$ such that $S\subseteq S'\cup S''$. Then, there exist MCS-covers $\mathcal C'$ and $\mathcal C''$ of K and $K'$ respectively such that $\bigcap _{S\in \mathcal C} S\subseteq (\bigcap _{S'\in \mathcal C'} S')\cup (\bigcap _{S\in \mathcal C''} S'')$. As a consequence, we have $\lambda (K\cup K')\mathrel {\leqslant }\lambda (K)+\lambda (K')$. Therefore, $MCSC(K\cup K')\mathrel {\geqslant }MCSC(K)+MCSC(K')$ holds.

In the following proposition, we show that MCSC measure satisfies a property generalizing Super-additivity.

Proposition 4

Given two knowledge bases K and $K'$, we have:

$MCSC(K\cup K')\mathrel {\geqslant }MCSC(K)+MCSC(K')-|K\cap K'|$.

Proof

We have, for all $S\in MCSes(K\cup K')$, $S'=S\cap K$ and $S''=S\cap K'$ are both consistent. Let $\mathcal{C}=\{S_1,\ldots {},S_n\}$ be a maximum MCS-cover of $K\cup K'$. Then, $\mathcal{C'}=\{S_1\cap K, \ldots {}, S_n\cap K\}$ and $\mathcal{C''}=\{S_1\cap K', \ldots {}, S_n\cap K'\}$ are sets of consistent subsets. Moreover, $\bigcap _{S\in \mathcal C} S = (\bigcap _{S'\in \mathcal C'} S') \cup (\bigcap _{S''\in \mathcal C''} S'')$. Thus, $\lambda (K\cup K')\mathrel {\leqslant }\lambda (K)+\lambda (K')$ holds and, consequently, $MCSC(K\cup K')\mathrel {\geqslant }|K\cup K'|-\lambda (K)-\lambda (K')$ holds. Since $|K\cup K'|=|K|+|K'|-|K\cap K'|$, we deduce that $MCSC(K\cup K')\mathrel {\geqslant }MCSC(K)+MCSC(K')-|K\cap K'|$.

It is worth noticing that MCSC does not satisfy MIS-additivity. Consider, for instance, $K=\{a,b,\lnot a\wedge \lnot b\}$, $K_1=\{a,\lnot a\wedge \lnot b\}$ and $K_2=\{b,\lnot a\wedge \lnot b\}$. It is easy to see that $MCSC(K)=3$, $MCSC(K_1)=2$ and $MCSC(K_2)=2$. We have $MISes(K)=MISes(K_1)\uplus MISes(K_2)$, but $MCSC(K)\ne MCS(K_1) +MCS(K_2)$.

Proposition 5

Given a knowledge base K, $MCSC(K)\mathrel {\leqslant }|K|-|Free(K)|$.

Proof

This property is a direct consequence of the fact that, for all $S\in MCSes(K)$, $Free(K)\subseteq S$.

Proposition 6

Given a minimal inconsistent set of formulæK such that $|K|>1$, we have $MCSC(K)= 2$.

Proof

Let $K=\{\phi _1,\ldots {}, \phi _n\}$ be a minimal inconsistent set such that $n>1$. Then, $S=\{\phi _1,\ldots {}, \phi _{n-1}\}$ and $S'=\{\phi _2,\ldots {}, \phi _n\}$ are MCSes of K, and $\{S,S'\}$ are an MCS-cover of K. Then, $MCSC(K)\mathrel {\leqslant }n-(n-2)=2$ holds. Let us assume that $MCSC(K)=1$. Then, there exist S and $S'$ in MCSes(K) such that $S\ne S'$ and $|S\cap S'|\mathrel {\geqslant }n-1$. Thus, $|S|=|S'|=n$ holds and we get a contradiction. Therefore, we obtain $MCSC(K)=2$.

5 Relationship Between MCSC and $I_{CC}$ Measures

In this section, we study the relationship between our inconsistency measure and an existing one, denoted $I_{CC}$, introduced recently by Jabbour et al. in [18]. This study comes from the fact that the two metrics MCSC and $I_{CC}$ satisfy both a fundamental property, called Independent MIS-additivity. Firstly, we introduce the measure $I_{CC}$ as follows. Given a knowledge base K, a MIS-decomposition of K is a pair $\langle \{K_1,\ldots {},K_n\}, K'\rangle$ satisfying the following properties: (i)$(\bigcup _{i=1}^n K_i)\cap K'=\emptyset$; (ii) $K_i\vdash {{\perp }}$ for every $1\mathrel {\leqslant }i\mathrel {\leqslant }n$; (iii) $K_i\cap K_j=\emptyset$ for every $1\mathrel {\leqslant }i\ne j\mathrel {\leqslant }n$; (iv) $MISes(\bigcup _{i=1}^n K_i)= \biguplus _{i=1}^n MISes(K_i)$.

Given a knowledge base K, $I_{CC}(K)=n$ if there is a MIS-decomposition $\langle D,K'\rangle$ where $|D|=n$, and there is no MIS-decomposition $\langle D',K'' \rangle$ such that $|D'|>n$. In this case, $\langle D,K'\rangle$ is called maximum MIS-decomposition. Intuitively, this measure can be seen as the maximum number of MISes that can be isolated by removing formulæ  from the knowledge base.

Definition 10

(Independent MIS-Additivity). Let I be an inconsistency measure. Then, I satisfies the property of independent MIS-additivity¹ iff, for all knowledge bases K and $K'$, if $MISes(K\cup K')=MISes(K)\uplus MISes(K')$ and $(\bigcup _{M\in MISes(K)} M)\cap (\bigcup _{M\in MISes(K')} M)=\emptyset$, then $I(K\cup K')=I(K)+I(K')$.

Proposition 7

MCSC measure satisfies the property of independent MIS-additivity.

Proof

Let K, $K_1$ and $K_2$ be knowledge bases such that $MISes(K)=MISes(K_1)\uplus MISes(K_2)$ and, for all $M\in MISes(K_1)$ and $M'\in MISes(K_2)$, $M\cap M'=\emptyset$. We denote $K'$, $K_1'$ and $K_2'$ the sets $\bigcup _{M\in MISes(K)} M$, $\bigcup _{M\in MISes(K_1)} M$ and $\bigcup _{M\in MISes(K_2)} M$ respectively. Let us note that $K'=K_1'\uplus K_2'$. Using the property of free formula independence, we have $MCS(K)=MCS(K')$, $MCS(K_1)=MCS(K'_1)$ and $MCS(K_2)=MCS(K_2')$. Then, using the properties of super-additivity, we have $MCSC(K)\mathrel {\geqslant }MCS(K_1)+MCS(K_2)$. Let $S\in MCSes(K_1')$ and $S'\in MCSes(K_2')$. Since $(\bigcup _{M\in MISes(K_1)} M)\cap (\bigcup _{M\in MISes(K_2)} M)=\emptyset$, $S\cup S'$ is a consistent set in $K'$. Then, using the fact that $K'=K_1'\uplus K_2'$, we have $\lambda (K')\mathrel {\geqslant }\lambda (K_1')+\lambda (K_2')$ and, consequently, $MCSC(K')\mathrel {\leqslant }MCSC(K_1')+MCSC(K_2')$. Thus, $MCSC(K)\mathrel {\leqslant }MCSC(K_1)+MCSC(K_2)$ holds. Therefore, we get $MCSC(K)= MCSC(K_1)+MCSC(K_2)$.

Proposition 8

Given a knowledge base K, we have $MCSC(K)\mathrel {\geqslant }2\times I_{CC}(K)$.

Proof

The property is a consequence of Super-additivity and Proposition 6.

We now show that MCSC allows to distinguish knowledge bases which are not distinguishable by $I_{CC}$. Consider, for instance, the two knowledge bases $K_1=\{p\wedge q, p\wedge r, \lnot p\}$ and $K_2=\{p\wedge q, \lnot p\}$. Then, $MISes(K_1)= \{\{p\wedge q,\lnot p\}, \{p\wedge r, \lnot p\}\}$ and $MISes(K_2)= \{\{p\wedge q,\lnot p\}\}$. Hence, we have clearly $I_{CC}(K_1)= I_{CC}(K_2)=1$. Furthermore, $\mathcal{C}_1=\{\{p\wedge q, p\wedge r\},\{\lnot p\}\}$ and $\mathcal{C}_2=\{\{p\wedge q\},\{\lnot p\}\}$ are maximum MCS-covers of $K_1$ and $K_2$ respectively. As a consequence, $\lambda (K_1)=\lambda (K_2)=0$. Thus, $MCSC(K_1)=3$ and $MCSC(K_2)=2$ hold.

Conversely, consider the knowledge bases $K_3=\{p\wedge q_1, p\wedge q_2, \lnot p, r,\lnot r\}$ and $K_4=\{p\wedge q_1, p\wedge q_2, p\wedge q_3, p\wedge q_4, \lnot p\}$. Then, $\langle \{\{p\wedge q_1, p\wedge q_2, \lnot p \},\{r,\lnot r\}\},\emptyset \rangle$ and . $\langle \{\{p\wedge q_1, p\wedge q_2, p\wedge q_3, p\wedge q_4, \lnot p\}\},\emptyset \rangle$ are maximum MIS-decompositions of $K_3$ and $K_4$ respectively and, consequently, $I_{CC}(K_3)=2$ and. $I_{CC}(K_3)=1$ hold. Moreover, $\{\{p\wedge q_1, p\wedge q_2,r\},\{\lnot p,\lnot r\}\}$ and $\{\{p\wedge q_1, p\wedge q_2, p\wedge q_3, p\wedge q_4\},\{\lnot p\} \}$ are maximum MCS-covers of $K_3$ and $K_4$ respectively. Thus, we obtain $MCSC(K_3)=MCSC(K_4)=5$.

The previous examples show that MCSC allows to distinguish knowledge bases which are not distinguishable by $I_{CC}$ and vice versa. As a consequence, these measures do not capture the same facets in measuring inconsistency.

6 Integer Linear Programming Formulation

In this section, we show that our measure can be formulated as an integer linear program (ILP) by providing an encoding defined mainly from the set of the MCSes of a knowledge base. To do this, each variable used in our encoding is binary (a 0-1 variable) and corresponds to either a formula or an MCS. The constraints are defined so that the objective consists in maximizing the function corresponding to the sum of the variables associated to formulæ.

Variables. We associate a binary variable $X_\phi$ having as domain $\{0,1\}$ to each formula $\phi$ in K. We also associate a binary variable $Y_M$ having as domain $\{0,1\}$ to each MCS M of K.

The integer linear program ILP-MCSC(K) is as follows:

$$\begin{aligned} minimize ~~\mathop {|K|}\limits _{\mathrm{subject\, to:}}-\sum \nolimits _{\phi \in K} X_{\phi } \end{aligned}$$

$$\begin{aligned} \sum _{M:\phi \in M} Y_M\mathrel {\geqslant }1~for~all~\phi \in K \end{aligned}$$

(1)

$$\begin{aligned} X_\phi + Y_M\mathrel {\leqslant }1~for~all~ \phi \in K~and~M\in MCSes(K)~with~\phi \notin M \end{aligned}$$

(2)

Proposition 9

(Soundness). Given a knowledge base K and a solution S of ILP-MCSC(K), then $MCSC(K)= |K|-|\{\phi \in K\mid S(X_\phi )=1\}|$.

Proof

Each solution $S_1$ of the linear inequality (1) means that the set $\mathcal{C}=\{M\in MCSes(K)\mid S_1(Y_M)=1\}$ is an MCS-cover of K. Moreover, each solution $S_2$ of the linear inequality (2) means that $\{\phi \in K\mid S_2(X_\phi )=1\}\subseteq \bigcap _{L} M$ where $L=\{M\in MCSes(K) \mid S_2(Y_M)=1\}$. Thus, since minimizing $|K|-\sum _{\phi \in K} X_\phi$ corresponds to maximizing $\sum _{\phi \in K} X_\phi$, we have $\lambda (K)= |\{\phi \in K\mid S(X_\phi )=1\}|$. As a consequence, $MCSC(K)= |K|-|\{\phi \in K\mid S(X_\phi )=1\}|$ holds.

7 Conclusion and Perspectives

Several approaches for measuring inconsistency have been proposed in the literature. In this paper, we proposed an original approach based on the use of maximal consistent sets. The basic idea consists in considering the conflict of a knowledge base as a consequence of the use of multiple consistent information sources. We showed that our inconsistency measure satisfies several desired rational properties. We also proposed an encoding in integer linear programming for its computation.

As a future work, we intend to investigate complexity issues related to our framework. We also plan to define algorithms for the problem of MCSC computation and conduct experimental evaluations.