The Modularity of Inconsistent Knowledge Bases with Application to Measuring Inconsistency

Abstract

Inconsistency is one of the important issues in knowledge systems, especially with the advent of the world wide web. Given a context of inconsistency characterization, not all the primitive conflicts in an inconsistent knowledge base are independent of one another in many cases. The primitive conflicts tightly associated with each other should be considered as a whole in handling inconsistency. In this paper, we consider the modularity of inconsistency arising in a knowledge base, which provides a promising starting point for parallel inconsistency handling in very large knowledge bases. Then we propose a modularity-based approach to measuring inconsistency for knowledge bases.

1 Introduction

Inconsistency arises easily in knowledge-based systems when knowledge is gathered from heterogeneous or distributed sources. A growing number of theories and techniques for analyzing and resolving inconsistency have been proposed so far in a variety of application domains. In particular, measuring inconsistency has been considered as a promising starting point for better handling inconsistency in many real-world applications recently [13].

A knowledge base (a finite set of propositional formulas) in a propositional logic is inconsistent if there exists a formula such that both the formula and its negation can be derived from the knowledge base. The occurrence of inconsistency in a knowledge base is disastrous, since any proposition can be derived from that knowledge base. In order to analyze and resolve the inconsistency in a knowledge base, we often need to characterize the inconsistency within some specific context in many cases. For example, the set of minimal inconsistent subsets of an inconsistent knowledge base can be considered as a characterization of inconsistency in the sense that one needs to remove only one formula from each minimal inconsistent subset to resolve inconsistency [20]. Here a minimal inconsistent subset refers to an inconsistent subset without an inconsistent proper subset. Besides this, the set of propositional variables assigned to the designated truth value of both true and false in some paraconsistent models such as the $\mathsf {LP_{m}}$ model in Priest’s Logic of Paradox (LP for short) [18] can be considered as a characterization of inconsistency in a context of atom-based analysis of inconsistency [4, 6, 12]. Here we use the term of primitive conflict introduced in [1] to denote such features of an inconsistent knowledge base used to characterize inconsistency in a given context.

Given a context of inconsistency characterization, if we look inside the set of primitive conflicts, we can find that not all the primitive conflicts are independent of one another for some inconsistent knowledge bases. Some primitive conflicts may be tightly associated with each other for some given knowledge base. For example, in the context of characterizing inconsistency by minimal inconsistent subsets, the association among some minimal inconsistent subsets of a knowledge base due to their overlaps has been considered in some approaches to measuring inconsistency based on minimal inconsistent subsets [7,8,9,10, 15].

Such associations among primitive conflicts bring a natural partition of the set of primitive conflicts such that only primitive conflicts in the same cluster are associated with one another under the given context of inconsistency characterization. To illustrate this, consider knowledge bases $K=\{a\,\wedge \, c,\lnot a, b,\lnot b, c, \lnot c, \lnot a\,\vee \, b, d, \lnot d\}$ under the context of characterizing the inconsistency with minimal inconsistent subsets. Note that K has five minimal inconsistent subsets $\{a\wedge c,\lnot a\}$, $\{b,\lnot b\}$, $\{a\wedge c,\lnot a\vee b,\lnot b\}$, $\{c,\lnot c\}$, and $\{d,\lnot d\}$. The first three minimal inconsistent subsets of K are tightly associated with one other because both $\{a\wedge c,\lnot a\}$ and $\{b,\lnot b\}$ overlap $\{a\wedge c,\lnot a\vee b,\lnot b\}$. Then it is intuitive to consider that K has three separate clusters of primitive conflicts, which arise from the three separate parts $\{a\wedge c,\lnot a, b,\lnot b, \lnot a\vee b\}$, $\{c, \lnot c\}$ and $\{d, \lnot d\}$ of K, respectively. The first cluster consists of the first three minimal inconsistent subsets, while the other two clusters consists of the last two minimal inconsistent subsets, respectively. On the other hand, within the context of atom-based characterization in the framework of LP, it is intuitive to divide $\{a, b, c, d\}$ (atoms assigned to the designated truth value) into two clusters, i.e., $\{a,b,c\}$ and $\{d\}$. Correspondingly, K can be divided into two subsets, i.e., $\{d,\lnot d\}$ and $K\setminus \{d,\lnot d\}$.

In such cases, it is advisable to take into account the separate clusters of primitive conflicts instead of individuals to handle the inconsistency in a knowledge base. Moreover, such a consideration provides a promising starting point for handling the inconsistency in a knowledge base in a parallel way, because any two primitive conflicts from different clusters are independent of each other. This is attractive to inconsistency handling for very large knowledge bases.

In this paper, we focus on taking such a partition of an inconsistent knowledge base into account in characterizing and handling inconsistency for that base. At first, we propose a notion of module to split an inconsistent knowledge base into several parts such that each inconsistent part (module) has only one block of primitive conflicts under a given context of inconsistency characterization. Moreover, we show that there exists a unique module-based partition for a knowledge base under the given context. Then we propose a modularity-based framework for measuring the inconsistency in a knowledge base, which allows us to integrate the inconsistency assessments for modules of the base to assess the inconsistency of the whole knowledge base in a flexible way.

The rest of this paper is organized as follows. In Sect. 2 we introduce some necessary notions about inconsistency characterization. In Sect. 3 we propose the notion of module of a knowledge base, and then we give some instances. In Sect. 4 we propose a modularity-based framework for measuring the inconsistency in a knowledge base. In Sect. 5 we compare our work with some very closely related work. Finally, we conclude this paper in Sect. 6.

2 Preliminaries

We use a finite propositional language in this paper. Let $\mathcal {P}$ be a finite set of propositional atoms (or variables) and $\mathcal {L}$ a propositional language built from $\mathcal {P}$ and two propositional constants $\top$ ($\mathsf{true}$) and $\bot$ ($\mathsf{false}$) under connectives $\{\lnot ,\wedge ,\vee \}$. We use a, b, c, $\cdots$ to denote the propositional atoms, and $\alpha$, $\beta$, $\gamma$, $\cdots$ to denote the propositional formulas.

A knowledge base K is a finite set of propositional formulas. For two knowledge bases K and $K'$ such that $K\cap K'=\emptyset$, we use $K+K'$ instead of $K\cup K'$ to denote the union of K and $K'$.

K is inconsistent if there is a formula $\alpha$ such that $K\vdash \alpha$ and $K\vdash \lnot \alpha$, where $\vdash$ is the classical consequence relation. We abbreviate $\alpha \wedge \lnot \alpha$ as $\bot$ when there is no confusion. Then we use $K\vdash \bot$ (resp. $K\not \vdash \bot$) to denote that a knowledge base K is inconsistent (resp. consistent). An inconsistent subset $K'$ of K is called a minimal inconsistent subset of K if no proper subset of $K'$ is inconsistent. We use $\mathsf{MI}(K)$ to denote the set of all the minimal inconsistent subsets of K. A formula in K is called a free formula if this formula does not belong to any minimal inconsistent subset of K [4]. We use $\mathsf{{FREE}}(K)$ to denote the set of free formulas of K. Evidently, $K=(\bigcup \mathsf{MI}(K))\cup \mathsf{FREE}(K)$, where $\bigcup \mathsf{MI}(K)=\cup _{M\in \mathsf{MI}(K)} M$.

Given a knowledge base K, a subset R of K is called a minimal correction subset of K if $K\setminus R\not \vdash \bot$ and for any $R'\subset R$, $K\setminus R'\vdash \bot$. We use $\mathsf{MC}(K)$ to denote the set of all the minimal correction subsets of K.

It is well known that an inconsistent knowledge base K has no classical model. Some paraconsistent models have been established for inconsistent knowledge bases. Without loss of generality, we introduce the $\mathsf{{LP_{m}}}$ model, one of the simple but representative paraconsistent models [4, 6, 12], in this paper.

The $\mathsf {LP_{m}}$ model [18] of knowledge bases is given in the framework of Priest’s Logic of Paradox (LP for short) [19]. Roughly speaking, Priest’s Logic of Paradox provides three-valued models for inconsistent knowledge bases by expanding the classical truth values $\{\mathsf{T},\mathsf{F}\}$ to the set $\{\mathsf{T},\mathsf{F},\{\mathsf{T}, \mathsf{F}\}\}$, in which the third truth value $\{\mathsf{T},\mathsf{F}\}$ (also abbreviated as $\mathsf{B}$ in [6, 12]) is considered intuitively as both true and false [18]. Here we use the following notations and the concepts about the $\mathsf {LP_{m}}$ model used in [6]. An interpretation $\omega$ for $\mathsf {LP_{m}}$ models maps each propositional variable to one of the three truth values $\mathsf {T}$, $\mathsf {F}$, $\mathsf {B}$ such that

• $\omega (\mathsf{true})=\mathsf{{T}}$, $\omega (\mathsf{false})=\mathsf{{F}}$,

• $\omega (\lnot \alpha )=\mathsf{{B}}$ if and only if $\omega (\alpha )=\mathsf{{B}}$, $\omega (\lnot \alpha )=\mathsf{{T}}$ if and only if $\omega (\alpha )=\mathsf{{F}}$,

• $\omega (\alpha \wedge \beta )=\min _{\le t}\{\omega (\alpha ),\omega (\beta )\}$, $\omega (\alpha \vee \beta )=\max _{\le t}\{\omega (\alpha ),\omega (\beta )\}$,

where $\mathsf{{F}}<_{t}\mathsf{{B}}<_{t}\mathsf{{T}}$. Then the set of models of a formula $\alpha$ is defined as $\mathsf{{Mod_{LP}}}(\alpha )=\{\omega |\omega (\alpha )\in \{\mathsf{{T}},\mathsf{{B}}\}\}$. Further, the set of models of a knowledge base K is defined as $\mathsf{{Mod_{LP}}}(K)=\{\omega |\omega \in \mathsf{{Mod_{LP}}}(\alpha )\ \text{ for } \text{ all }\ \alpha \in K\}$.

Let $\omega$ be an interpretation and K a knowledge base, then we use $\omega !(K)$ to denote the set of propositional variables of K assigned to $\mathsf {B}$ by $\omega$. Based on $\omega !(K)$, we can define the minimal models of K w.r.t. $\omega !(K)$ as follows:

$$\begin{aligned} \mathsf{{MinMod_{LP}}}(K)= \{\omega \in \mathsf{{Mod_{LP}}}(K)|\forall \omega '\in \mathsf{{Mod_{LP}}}(K), \omega !(K)\not \subset \omega '!(K)\}. \end{aligned}$$

The probability distribution on the language $\mathcal L$ presented in  [16, 17] is defined as follows: a function $P: {\mathcal {L}}\mapsto [0,1]$ is a probability function on $\mathcal L$ if P satisfies

• if $\models \alpha$, then $P(\alpha )=1$,

• if $\models \lnot (\alpha \wedge \beta )$, then $P(\alpha \vee \beta )=P(\alpha )+P(\beta )$.

Probability distributions over a knowledge base describe how plausible each formula can be true. Note that there is no probability distribution such that the probability of each formula of K is 1 if $K\vdash \bot$.

3 Conflict Modules

In this section, we propose a notion of conflict modules to characterize an inconsistent knowledge base. We start with the notion of partition of a knowledge base.

Let K be a knowledge base, a set ${\mathcal B}=\{B^{(i)}|\emptyset \subset B^{(i)}\subseteq K\}^{m}_{i=0}$ with $B^{(i)}\cap B^{(j)}=\emptyset$ for $i\not =j$ of subsets of K, is called a partition of K if $\sum \limits _{i=0}^{m} B_{i}=K$.

Let K be a knowledge base and ${\mathcal A}(K)$ the set of atoms of formulas in K. A set $\{A^{(i)}|\emptyset \subset A^{(i)}\subseteq {\mathcal A}(K)\}^{m}_{i=0}$ with $A^{(i)}\cap A^{(j)}=\emptyset$ for $i\not =j$ of subsets of ${\mathcal A}(K)$, is called a partition of ${\mathcal A}(K)$ if $\sum \limits _{i=0}^{m} A_{i}={\mathcal A}(K)$. Such a partition may be considered as a kind of language split used in belief change in some sense. Let $\emptyset \subset A\subseteq {\mathcal A}(K)$, we use ${\mathcal F}(A)$ to denote the set of formulas containing at least one variable of A in K.

We can also split a knowledge base into several parts according to the separation of their atoms. Let K be a knowledge base, a partition ${\mathcal B}=\{B^{(i)}|\emptyset \subset B^{(i)}\subseteq K\}^{m}_{i=0}$ of K, is called an A-partition of K if ${\mathcal F}({\mathcal A}(B_{i}))=B_{i}$ for all $0\le i\le m$. Evidently, if $\{B^{(i)}\}^{m}_{i=0}$ is an A-partition of K, then $\{{\mathcal A}(B^{(i)})\}^{m}_{i=0}$ is a partition of ${\mathcal A}(K)$.

Further, if a partition ${\mathcal B}$ of K satisfies a given constraint such as ${\mathcal F}({\mathcal A}(B_{i}))=B_{i}$, then we call ${\mathcal B}$ a constrained partition. Essentially, an A-partition of K is a constrained partition of K. A partition ${\mathcal B}_{1}$ of K is a refinement of a partition ${\mathcal B}_{2}$ of K if every element of ${\mathcal B}_{1}$ is a subset of some element of ${\mathcal B}_{2}$.

Here we use ${\mathcal C}_{\mu }(K)$ to denote the set of primitive conflicts of K under the context $\mu$ of inconsistency characterization. For example, if we use minimal inconsistent subsets to characterize the inconsistency of K, then the set of primitive conflicts of K is exactly $\mathsf{MI}(K)$. Now we are ready to define the conflict modules of a knowledge base.

Definition 1

Let K be an inconsistent knowledge base and $\mu$ a context of inconsistency characterization. Then a set $\{K^{(i)}|K^{(i)}\subseteq K\}^{m}_{i=1}$ of subsets of K with $K^{(i)}\cap K^{(j)}=\emptyset$ for $i\not =j$, is called the set of conflict modules of K w.r.t. $\mu$, if

• (1) $K^{(i)}\vdash \bot$, $i=1,2,\ldots , m$,

• (2) ${\mathcal C}_{\mu }(\sum \limits _{l=1}^{k}K^{(i_{l})})=\sum \limits _{l=1}^{k}{\mathcal C}_{\mu }(K^{(i_{l})})$ for all $1\le i_{1}<\cdots <i_{k}\le m$,

• (3) ${\mathcal C}_{\mu }(\sum \limits _{i=1}^{m}K^{(i)})={\mathcal C}_{\mu }(K)$,

• (4) for each $K^{(i)}$, there is no constrained partition of $K^{(i)}$ w.r.t. $\mu$, or for each partition $\{K^{(i)}_{1},K^{(i)}_{2}\}$ of $K^{(i)}$, ${\mathcal C}_{\mu }(K^{(i)}_{1})+{\mathcal C}_{\mu }(K^{(i)}_{2})\subset {\mathcal C}_{\mu }(K^{(i)})$.

Here (1) states that each conflict module of K is inconsistent. (2) states that any union of conflict modules cannot bring any new primitive conflict under the context $\mu$. This essentially ensures that the primitive conflicts in different conflicts modules exactly belong to different blocks of primitive conflicts under the context $\mu$. (3) states that all the primitive conflicts in K are distributed over the conflicts modules of K. (4) states that each conflict module is a unity in characterizing inconsistency under the context $\mu$.

Just for simplicity, the set of conflict modules of a consistent knowledge base is considered as $\emptyset$. If the set of conflict modules of an inconsistent knowledge base K is $\{K\}$, then we call K a modular knowledge base. We call $K\setminus \sum \limits _{i=1}^{m}K^{(i)}$ the conflict-free module of K. We use $K^{(0)}$ to denote the conflict-free module of K. Evidently, if K is consistent, its conflict-free module is itself. From now on, we call the partition $\{K^{(i)}\}^{m}_{i=0}$ the set of modules of K.

Proposition 1

Let K be an inconsistent knowledge base and $\mu$ a context of inconsistency characterization. Then there is a unique set of conflict modules of K w.r.t. $\mu$.

Proof. Let $\{K_{1}^{(i)}\}_{i=1}^{m}$ and $\{K_{2}^{(j)}\}_{j=1}^{n}$ be two different sets of conflict modules of K. Without loss of generality, suppose that $K_{1}^{(1)}$ is covered by $K_{2}^{(1)}$ and $K_{2}^{(2)}$, i.e., $K_{1}^{(1)}\subseteq K_{2}^{(1)}\cup K_{2}^{(2)}$ and $K_{1}^{(1)}\cap K_{2}^{(1)}\not =\emptyset , K_{1}^{(1)}\cap K_{2}^{(2)}\not =\emptyset$.

If there is no constrained partition of $K_{1}^{(1)}$ w.r.t. $\mu$, then consider $\alpha _{1}\in K_{1}^{(1)}\cap K_{2}^{(1)}$ and $\alpha _{2}\in K_{1}^{(1)}\cap \, K_{2}^{(2)}$, then $\alpha _{1}\in K_{2}^{(1)}$ and $\alpha _{2}\in K_{2}^{(2)}$. This contradicts that $\alpha _{1}$ and $\alpha _{2}$ must be in the same part when we partition K in the context $\mu$.

If there is at least one constrained partition of $K_{1}^{(1)}$ w.r.t. $\mu$, then there exists at least one primitive conflict $C\in {\mathcal C}_{\mu }(K_{1}^{(1)})$ such that $F(C)\cap K_{2}^{(1)}\not =\emptyset$ and $F(C)\cap K_{2}^{(2)}\not =\emptyset$, where F(C) is the set of formulas involved in C. So, $C\not \in {\mathcal C}_{\mu }(K^{(1)}_{2})$ and $C\not \in {\mathcal C}_{\mu }(K^{(2)}_{2})$, but $C\in {\mathcal C}_{\mu }(K^{(1)}_{2}+K^{(2)}_{2})$. Therefore, ${\mathcal C}_{\mu }(K^{(1)}_{2})+{\mathcal C}_{\mu }(K^{(2)}_{2})\subset {\mathcal C}_{\mu }(K^{(1)}_{2}+K^{(2)}_{2})$. This contradicts that $\{K_{2}^{(j)}\}_{j=1}^{n}$ is also a set of modules of K w.r.t. $\mu$. Therefore, $\{K_{1}^{(i)}\}_{i=1}^{m}=\{K_{2}^{(j)}\}_{j=1}^{n}$.    $\Box$

Here we give some instances of conflicts modules. Consider the case $\mu _{M}$ where the inconsistency of a knowledge base is characterized by minimal inconsistent subsets of K. We define a relation $R_{\mu _{M}}$ over $\bigcup \mathsf{MI}(K)$ as follows: $(\alpha ,\beta )\in R_{\mu _{M}}$ if and only if there exists a sequence $\alpha _{0},\cdots ,\alpha _{n}$ of formulas in $\bigcup \mathsf{MI}(K)$ with $\alpha _{0}=\alpha$ and $\alpha _{n}=\beta$ such that $\alpha _{i-1}$ and $\alpha _{i}$ belong to the same minimal inconsistent subset for all $1\le i\le n$. Evidently, $R_{\mu _{M}}$ is an equivalence relation. We use $[\alpha ]_{\mu _{M}}$ to denote the equivalence class $\alpha$ belongs to, i.e., $[\alpha ]_{\mu _{M}}=\{\beta \in \bigcup \mathsf{MI}(K)|(\alpha ,\beta )\in R_{\mu _{M}}\}$. Then the set of conflict modules of K w.r.t. $\mu _{M}$ is given as the quotient set of $\bigcup \mathsf{MI}(K)$ by $R_{\mu _{M}}$.

Proposition 2

Let K be an inconsistent knowledge base. Then

• the set of conflict modules of K w.r.t. $\mu _{M}$ is given as $\left\{ [\alpha ]_{\mu _{M}}|\alpha \in \bigcup \mathsf{MI}(K)\right\}$;

• the conflict-free module $K^{(0)}=\mathsf{FREE}(K)$.

Proof. Given $K\vdash \bot$, suppose that $\{[\alpha _{1}]_{\mu _{M}},\ldots , [\alpha _{m}]_{\mu _{M}}\}$ is the quotient set of $\bigcup \mathsf{MI}(K)$ by $R_{\mu _{M}}$. It can be easily shown that the quotient set satisfies conditions (1)-(3) of definition of conflict modules. For the condition (4), any split of $[\alpha _{i}]_{\mu _{M}}$ can break at least one minimal inconsistent subset, then $\mathsf{MI}(S_{1})+\mathsf{MI}(S_{2})\subset \mathsf{MI}([\alpha _{i}]_{\mu _{M}})$ for any partition $\{S_{1},S_{2}\}$ of $[\alpha _{1}]_{\mu _{M}}$. Therefore, $\left\{ [\alpha ]_{\mu _{M}}|\alpha \in \bigcup \mathsf{MI}(K)\right\}$ is the set of conflict modules of K w.r.t. $\mu _{M}$, and $K^{(0)}= \mathsf{FREE}(K)$.    $\Box$

Example 1

Consider $K_{1}=\{a,\lnot a, \lnot a\vee b, \lnot b\wedge d, \lnot d\wedge e, c,\lnot c, e\vee f, g\}$. Then $\mathsf{MI}(K_{1})=\{M_{1},M_{2}, M_{3}, M_{4}\}$, where $M_{1}=\{a,\lnot a\}$, $M_{2}=\{a,\lnot a\vee b, \lnot b\wedge d\}$, $M_{3}=\{\lnot b\wedge d, \lnot d\wedge e\}$, and $M_{4}=\{c,\lnot c\}$. The set of conflict modules of $K_{1}$ with regard to $\mu _{M}$ is $\{\{a,\lnot a, \lnot a\vee b, \lnot b\wedge d, \lnot d\wedge e\}, \{c, \lnot c\}\}$, and the corresponding conflict-free module of $K_{1}$ is $\{e\vee f, g\}$. The set of minimal inconsistent subsets of $K_{1}$ can be divided into two blocks, i.e., $\{M_{1},M_{2}, M_{3}\}$ and $\{M_{4}\}$.

Now we give an A-partition of K based on the dependence of formulas on atoms. We define a relation $R_{A}$ over K as follows: $(\alpha ,\beta )\in R_{A}$ if and only if there exists a sequence $\alpha _{0},\cdots ,\alpha _{n}$ of formulas in K with $\alpha _{0}=\alpha$ and $\alpha _{n}=\beta$ such that $\alpha _{i-1}$ and $\alpha _{i}$ have at least one common atom for all $1\le i\le n$. Evidently, $R_{A}$ is an equivalence relation. We use $[\alpha ]_{A}$ to denote the equivalence class $\alpha$ belongs to, i.e., $[\alpha ]_{A}=\{\beta \in K|(\alpha ,\beta )\in R_{A}\}$. Evidently, ${\mathcal F}({\mathcal A}([\alpha ]_{A}))=[\alpha ]_{A}$. Then $\{[\alpha ]_{A}|\alpha \in K\}$ is exactly an A-partition of K.

Consider an atom-based case $\mu _{L}$ where the inconsistency of a knowledge base is characterized by the set of propositional variables assigned to $\mathsf{B}$ by minimal $\mathsf {LP_{m}}$ models, that is, ${\mathcal C}_{\mu _{L}}(K)=\{a\in {\mathcal A}(K)|\exists \omega \in \mathsf{{MinMod_{LP}}}(K)s.t. \omega (a)=\mathsf{B}\}$. Then the set of conflict modules of K w.r.t. $\mu _{L}$ can be given by the following proposition.

Proposition 3

Let K be an inconsistent knowledge base. Then

• the set of conflict modules of K w.r.t. $\mu _{L}$ is given as

  $$\left\{ [\alpha ]_{A}|\alpha \in K\ s.t.\ [\alpha ]_{A}\vdash \bot \right\} ;$$

• the conflict-free module $K^{(0)}=\sum \limits _{[\alpha ]_{A}\not \vdash \bot }[\alpha ]_{A}$.

Proof. Let K be an inconsistent knowledge base and $\alpha \in K$ such that $[\alpha ]_{A}\vdash \bot$. Then for any $\beta \in K$ such that $\beta \not \in [\alpha ]_{A}$, then it holds that $b\not \in {\mathcal C}_{\mu _{L}}([\alpha ]_{A})$ for all $b\in {\mathcal A}(\{\beta \})$. Then it is easy to check that the conditions (1), (2), and (3) of the definition of conflict modules are satisfied. Note that for any proper subset $S\not =\emptyset$ of $[\alpha ]_{A}$, ${\mathcal F}({\mathcal {A}}(S))\not =S$. So, the condition (4) is also satisfied.    $\Box$

Example 2

Consider $K_{1}$ again. The set of conflict modules of $K_{1}$ with regard to either $\mu _{L}$ is $\{\{a,\lnot a, \lnot a\vee b, \lnot b\wedge d, \lnot d\wedge e, e\vee f\}, \{c, \lnot c\}\}$, and the corresponding conflict-free module of $K_{1}$ is $\{g\}$.

The corresponding partition of atoms is $\{\{a,b,d,e,f\},\{c\},\{g\}\}$. The set of atoms assigned to $\mathsf{B}$ by minimal $\mathsf {LP_{m}}$ models can be split into two blocks, i.e., $\{a, d\}$ and $\{c\}$.

Consider a case $\mu _{P}$ of probability-based inconsistency characterization where the primitive conflicts are represented by minimal P-inconsistent subsets. Here a subset S of K is called a P-inconsistent subset of K if ${\mathcal F}({\mathcal A}(S))=S$, and there is no probability distribution P on S such that $P(\alpha )=1$ for all $\alpha \in S$. A P-inconsistent subset S is called a minimal P-inconsistent of K if no proper subset of S is P-inconsistent. Then the set of conflict modules of K w.r.t. $\mu _{P}$ can be given by the following proposition.

Proposition 4

Let K be an inconsistent knowledge base. Then

• the set of conflict modules of K w.r.t. $\mu _{P}$ is given as

  $$\left\{ [\alpha ]_{A}|\alpha \in K\ s.t.\ [\alpha ]_{A}\vdash \bot \right\} ;$$

• the conflict-free module $K^{(0)}=\sum \limits _{[\alpha ]_{A}\not \vdash \bot }[\alpha ]_{A}$.

Proof. Let K be an inconsistent knowledge base and $\alpha \in K$. Note that $[\alpha ]_{A}$ is a minimal P-inconsistent subset iff $[\alpha ]_{A}\vdash \bot$.    $\Box$

However, for any context $\mu _{A}$ of atom-based or valuation-based or paraconsistent models-based inconsistency characterization, the set of conflict modules of K w.r.t. $\mu _{A}$ is exactly $\left\{ [\alpha ]_{A}|\alpha \in K\ s.t.\ [\alpha ]_{A}\vdash \bot \right\}$.

4 Module-Based Inconsistency Assessment

The modularity of inconsistent knowledge bases provides a good starting point to measure inconsistency in a parallel way. Given a context of inconsistency characterization, the primitive conflicts of an inconsistent knowledge base are distributed over the conflict modules of that base. Moreover, the primitive conflicts in each conflict module exactly comprise a separate block. Then a desirable inconsistency measure should take into account the inconsistency assessment of each module as well as the way to integrate the assessments of these modules in order to assess the inconsistency of the whole knowledge base. To this end, we first give a general framework to define an inconsistency measure based on modules of a knowledge base.

Definition 2

Let K be a knowledge base. Then the inconsistency measure for K with regard to $\mu$, denoted $I_{\mu }(K)$, is a module-based measure if

$$\begin{aligned} I_{\mu }(K)=\delta (I_{\mu }(K^{(0)}),I_{\mu }(K^{(1)}),\cdots ,I_{\mu }(K^{(m)})), \end{aligned}$$

(1)

where $\{K^{(i)}\}_{i=1}^{m}$ (possibly empty) is the set of conflict modules of K with regard to $\mu$, and $\delta$ is an operation for integrating the measures of modules with $\delta (x)=x$.

Now we give some existing instances of module-based measures.

• The measure $I_{MI}(K)$ presented in [6] is defined as the number of minimal inconsistent subsets of K. Then by Proposition 2, $I_{MI}(K)=\sum \limits _{i=0}^{m}I_{MI}(K^{(i)})$.

• The measure $I_{dr}(K)$ presented in [14] is defined as the smallest size of minimal correction subsets of K. Then by Proposition 2, $I_{dr}(K)=\sum \limits _{i=0}^{m}I_{dr}(K^{(i)})$.

• The measure $I_{LP_{m}}(K)$ presented in [4, 6] is defined as the normalized minimum number of variables assigned inconsistent truth values in $\mathsf{{LP_{m}}}$ models (with regard to $|{\mathcal {P}}|$). Then by Proposition 3, $I_{LP_{m}}(K)=\sum \limits _{i=0}^{m}I_{LP_{m}}(K^{(i)})$.

• The maximal $\eta$ -consistency presented in [11] is one of the most representative of probability-based measures. For $0\le \eta \le 1$, a knowledge base K is $\eta$-consistent if there exists a probability function P such that $P(\alpha )\ge \eta$ for all $\alpha \in K$. Furthermore, K is maximally $\eta$-consistent if K is $\eta$-consistent, and for all $\gamma >\eta$, K is not $\gamma$-consistent. If we define $I_{pr}(K)=\eta$ if K is maximally $\eta$-consistent, then by Proposition 4, $I_{pr}(K)=\min \limits _{0\le i\le m}I_{pr}(K^{(i)})$.

The behavior of the module-based inconsistency measure depends on properties of assessments for modules as well as characteristics of the integration operation $\delta$. Just for simplicity, we assume that any inconsistency measure discussed from now on is a non-negative inconsistency measure such that the higher the inconsistency value, the more inconsistent a knowledge base is.

In order to characterize a module-based inconsistency measure, we consider the following postulates about the integration operation $\delta$ firstly. Let $x_{i}\ge 0$ for $i\ge 0$,

• 0-Invariance: $\delta (x_{0},x_{1},\cdots ,x_{m})=\delta (x_{1},\cdots ,x_{m})$ if $x_{0}=0$.

• M-Monotony: $\delta (x_{0},\cdots ,x_{m})\le \delta (x_{0},\cdots ,x_{m},x_{m+1})$ for $0\le m$.

• R-Monotony: $\ \delta (x_{0},\cdots ,x_{i}, x_{i+1}, \cdots , x_{m})\le \delta (y,x_{i+1},\cdots ,x_{m})$ if $\delta (x_{0},\cdots ,x_{i})$ $\le y$.

Essentially, the property of 0-Invariance says that the variables with the value 0 play no role in the integration of nonnegative variables under $\delta$. The property of M-monotony says that the result of integration under $\delta$ cannot decrease as we extend the set of variables to be integrated. The property of R-monotony says that replacing a set of variables with some variable greater than the integration of these variables cannot make the result of integration under $\delta$ decrease.

Evidently, both $\delta (x_{0},x_{1},\cdots ,x_{m})=\sum \limits _{i=0}^{m}x_{i}$ and $\delta (x_{0},x_{1},\cdots ,x_{m})=\max \limits _{0\le i\le m}x_{i}$ satisfy all the three postulates.

Then we consider the properties of inconsistency assessment for modules and modular knowledge bases.

• Consistency: $I_{\mu }(K^{(i)})=0$ if and only if $i=0$.

• $\subseteq$ -Monotony: $I_{\mu }(K)\le I_{\mu }(K')$ for two modular knowledge bases K and $K'$ such that $K\subseteq K'$.

• Reinforcement: Suppose that $K_{1},\ldots , K_{n-1}$, and $K_{n}$ are modular knowledge bases with regard to $\mu$ such that $\sum \limits _{i=1}^{n-1}K_{i}\subseteq K_{n}$, then

  $$\delta (I_{\mu }(K_{1}),\cdots ,I_{\mu }(K_{n-1}))\le I_{\mu }(K_{n}).$$

• M-Dominance: Let ${\mathcal B}_{\beta }$ and ${\mathcal B}_{\alpha }$ be the sets of modules of $K\cup \{\beta \}$ and $K\cup \{\alpha \}$ for two formulas $\alpha$ and $\beta$ not in K, respectively, then $\delta (I_{\mu }(K')|K'\in {\mathcal B}_{\alpha }\setminus {\mathcal B}_{\beta })\ge \delta (I_{\mu }(K'')|K''\in {\mathcal B}_{\beta }\setminus {\mathcal B}_{\alpha })$ if $\alpha \vdash \beta$ and $\alpha \not \vdash \bot$.

The property of Consistency says that only the conflict-free module has null inconsistency assessment. However, it is exactly the property of consistency presented in [6]. The property of $\subseteq$-monotony says that the inconsistency measure for modular knowledge bases is monotonic w.r.t. set inclusion. The property of Reinforcement says that the inconsistency assessment of a modular knowledge base obtained by connecting a number of smaller disjoint modular knowledge bases is not less than the result of integration of assessments of these smaller modular knowledge bases. The property of M-Dominance states the result of integration of new modules cannot be less than that of the modules disappeared by replacing a formula with another logically stronger formula.

Besides the property of Consistency presented in [6], the properties of Monotony, Free Formula Independence, and Dominance presented in  [4,5,6], and the property of Safe Formula Independence (also termed as Weak Independence in [21]) presented in  [6] are considered as representative ones for characterizing inconsistency measures. In detail, let I be an inconsistency measure, then

• Consistency : $I(K)=0$ if and only if K is consistent.

• Monotony: $I(K\cup K')\ge I(K)$.

• Free Formula Independence: If $\alpha \in \mathsf{{FREE}}(K\cup \{\alpha \})$, then $I(K\cup \{\alpha \})=I(K)$.

• Dominance: If $\alpha \not \in K$ and $\alpha \vdash \beta$ and $\alpha \not \vdash \bot$, then $I(K\cup \{\alpha \})\ge I(K\cup \{\beta \})$.

• Safe Formula Independence: If ${\mathcal A}(\{\alpha \})\cap {\mathcal A}(K)=\emptyset$ and $\alpha \not \vdash \bot$, then $I(K\cup \{\alpha \})=I(K)$.

Here we adopt the revised form of Dominance presented by [2].

However, the following propositions show that the postulates of the integration operation and the properties of inconsistency measures for modules and modular knowledge bases guarantee the satisfaction of these representative properties by the module-based inconsistency measure.

Proposition 5

  If $I_{\mu }$ satisfies $I_{\mu }(K^{(0)})=0$, and $\delta$ satisfies 0-Invariance, then $I_{\mu }(K\setminus K^{(0)})=I_{\mu }(K)$.

Proof. Let $\{K^{(i)}\}_{i=1}^{m}$ be the set of conflict modules of K, then if $I_{\mu }(K^{(0)})=0$, $I_{\mu }(K)=\delta (0,I_{\mu }(K^{(1)}),\cdots ,I_{\mu }(K^{(m)}))$. Further, by 0-Invariance, $I_{\mu }(K)=\delta (I_{\mu }(K^{(1)}),\cdots ,I_{\mu }(K^{(m)}))=I_{\mu }(K\setminus K^{(0)})$.    $\Box$

Corollary 1

If $I_{\mu _{M}}$ satisfies $I_{\mu _{M}}(K^{(0)})=0$, and $\delta$ satisfies 0-Invariance, then $I_{\mu _{M}}$ satisfies the property of Free Formula Independence.

Proof. If $\alpha$ is a free formula of $K\cup \{\alpha \}$, then $(K\cup \{\alpha \})^{(0)}=K^{(0)}\cup \{\alpha \}$. Then by Proposition 5, $I_{\mu _{M}}(K\cup \{\alpha \})$= $I_{\mu _{M}}(K\cup \{\alpha \}\setminus K\cup \{\alpha \})^{(0)})=I_{\mu _{M}}(K\setminus K^{(0)})=I_{\mu _{M}}(K)$.    $\Box$

Corollary 2

If $I_{\mu _{L}}$ satisfies $I_{\mu _{L}}(K^{(0)})=0$, and $\delta$ satisfies 0-Invariance, then $I_{\mu _{L}}$ satisfies the property of Safe Formula Independence.

Proof. Note that $\alpha$ is a safe formula of K, then $\alpha$ is also a free formula of K.    $\Box$

Proposition 6

If $I_{\mu }$ satisfies $\subseteq$-Monotony and Reinforcement, and $\delta$ satisfies M-monotony and R-monotony, then $I_{\mu }$ satisfies the property of Monotony.

Proof. Let $\{(K)^{(i)}\}_{i=0}^{m}$ and $\{(K\cup K')^{(j)}\}_{j=0}^{n}$ be sets of modules of K and $K\cup K'$, respectively. Moreover, suppose that for $j>k$, $(K\cup K')^{(j)}\cap (K)^{(i)}=\emptyset$ for all $i=1,2,\cdots , m$. Suppose that $x_{i}=I_{\mu }((K)^{(i)})$ and $y_{j}=I_{\mu }((K\cup K')^{(j)})$. Then if $(K)^{(i)}$ is not a module of $K\cup K'$, then there exists some $(K\cup K')^{(j)}$ such that $(K)^{(i)}\subset (K\cup K')^{(j)}$. Suppose that $(K)^{(j_{1})}, \cdots , (K)^{(j_{l})}\subset (K\cup K')^{(j)}$. Then by Reinforcement, it holds that $\delta (x_{j_{1}},\cdots , x_{j_{l}})\le y_{j}$. Further, by R-monotony, it holds that $\delta (x_{1},\cdots , x_{j_{1}},\cdots , x_{j_{l}},\cdots , x_{m})\le \delta (x_{1},\cdots , y_{j}, \cdots ,x_{m})$. Then by M-monotony, $\delta (x_{1},\cdots , x_{m})\le \delta (x_{1},\cdots , x_{m}, y_{k},y_{k+1},\cdots , y_{n})$. Further, by $\subseteq$-Monotony and the two inequalities above, it holds that $\delta (x_{1},\cdots , x_{m})\le \delta (y_{1},\cdots , y_{k-1}, y_{k},y_{k+1},\cdots , y_{n})$.    $\Box$

Proposition 7

If $I_{\mu }$ satisfies $\subseteq$-Monotony, M-Dominance and Reinforcement, and $\delta$ satisfies M-monotony and R-monotony, then $I_{\mu }$ satisfies the property of Dominance.

Proof. Let ${\mathcal B}_{\beta }$ and ${\mathcal B}_{\alpha }$ be the sets of modules of $K\cup \{\beta \}$ and $K\cup \{\alpha \}$ for two formulas $\alpha$ and $\beta$ not in K, respectively, then $I_{\mu }(K\cup \{\alpha \})=\delta (I_{\mu }(K')|K'\in {\mathcal B}_{\alpha })$ and $I_{\mu }(K\cup \{\beta \})=\delta (I_{\mu }(K')|K'\in {\mathcal B}_{\beta })$.

Let $K_{\alpha }$ be the module of $K\cup \{\alpha \}$ such that $\alpha \in K_{\alpha }$. Then $I_{\mu }(K\cup \{\alpha \})=\delta (I_{\mu }(K_{\alpha }), I_{\mu }(K')|K'\in {\mathcal B}_{\alpha }\setminus \{K_{\alpha }\})$. Note that $I_{\mu }(K_{\beta })\le \delta (I_{\mu }(K'')|K''\in {\mathcal B}_{\beta }\setminus {\mathcal B}_{\alpha })$ and $I_{\mu }(K_{\alpha })=\delta (I_{\mu }(K'')|K''\in {\mathcal B}_{\alpha }\setminus {\mathcal B}_{\beta })\ge \delta (I_{\mu }(K'')|K''\in {\mathcal B}_{\beta }\setminus {\mathcal B}_{\alpha })$. Therefore, $I_{\mu }(K\cup \{\alpha \})\ge \delta (I_{\mu }(K'')|K''\in ({\mathcal B}_{\beta }\setminus {\mathcal B}_{\alpha })+{\mathcal B}_{\alpha }\setminus \{K_{\alpha }\})$. So, $I_{\mu }(K\cup \{\alpha \})\ge I_{\mu }(K\cup \{\beta \})$.    $\Box$

Lastly we give two new instances of module-based inconsistency measure guided by these postulates.

Definition 3

Let K be a knowledge base and $\{K^{(i)}\}_{i=0}^{m}$ the set of modules of K with regard to $\mu _{M}$. Then the inconsistency measure $I_{\max }(K)$ for K is defined as $I_{\max }(K) = \max \limits _{0\le i\le m} I_{dr}(K^{(i)})$.

Essentially, $I_{\max }(K)$ use the maximum value of modules of K as the inconsistency value of the whole knowledge.

Proposition 8

$I_{\max }$ satisfies the properties of Consistency, Free Formula Independence, Safe Formula Independence, Monotony, and Dominance.

Proof. Note that proofs for Consistency, Free Formula Independence, Safe Formula Independence and Monotony are trivial. Here we just focus on Dominance. Let $\alpha \not \in K$ and $\alpha \vdash \beta$ and $\alpha \not \vdash \bot$. Let $K_{\alpha }$ (resp. $K_{\beta }$) be a module of $K\cup \{\alpha \}$ (resp. $K\cup \{\beta \}$ ) such that $\alpha \in K_{\alpha }$ (resp.$\beta \in K_{\beta }$ ). Let $K_{1},K_{2},\ldots , K_{m}$ be the modules of $K\cup \{\beta \}$ such that $K_{i}\cap K_{\alpha }\not =\emptyset$ and $K_{i}\not =K_{\beta }$ for all $i=1,2,\cdots , m$.

Let R be the smallest correction subset of $K_{\alpha }$. If $\alpha \not \in R$, then R is also a (not necessarily minimal) correction subset of $K_{\beta }\cup K_{1}\cup \cdots \cup K_{m}$. If $\alpha \in R$, then $R\cup \{\beta \}\setminus \{\alpha \}$ is a correction subset of $K_{\beta }\cup K_{1}\cup \cdots \cup K_{m}$. So, $I_{dr}(K_{\alpha })\ge I_{dr}(K_{\beta }\cup K_{1}\cup \cdots \cup K_{m})$. Therefore, $I_{\max }(K\cup \{\alpha \})\ge I_{\max }(K\cup \{\beta \})$.    $\Box$

Definition 4

Let K be a knowledge base and $\{K^{(i)}\}_{i=0}^{m}$ the set of modules of K with regard to $\mu _{M}$. Then the inconsistency measure $I_{e}(K)$ for K is defined as

$$\begin{aligned} I_{e}(K)= & {} \delta _{e}(I_{e}(K^{(0)}),\cdots ,I_{e}(K^{(m)}))= \left\{ \begin{array}{ll}\prod \limits _{i=1}^{m} I_{e}(K^{(i)}), &{} \text{ if }\ m\ge 1\\ 0, &{} \text{ otherwise. }\end{array}\right. \end{aligned}$$

where $I_{e}(K^{(0)})=0$ and $I_{e}(K^{(i)})=e^{ I_{dr}(K^{(i)})}$ for $1\le i\le m$.

Note that $I_{e}(K^{(i)})>1$, then we have the following result.

Proposition 9

$I_{e}$ satisfies the properties of Consistency, Free Formula Independence, Safe Formula Independence, Monotony, and Dominance.

The proof is similar to the proof above. So we omit it.

5 Comparison and Discussion

Splitting an inconsistent knowledge into their modules provides a promising starting point for handling inconsistency for big knowledge bases in a parallel way. Note that the notion of conflict module is based on the association among primitive conflicts under a given context of inconsistency characterization.

Within the context $\mu _{M}$ where the inconsistency is characterized by minimal inconsistent subsets, the notion of strong-partition presented in [7] and the notion of MIS partition presented in [9] are similar to that of the set of conflict modules. All the three notions take into account the association among minimal inconsistent subsets of an inconsistent knowledge base. But they are different from one another in essence. The MIS-partition is a partition of the set of minimal inconsistent subsets. Instead, both the set of modules and the strong partition are partitions of the whole knowledge base. Note that the set of conflict modules must cover all the minimal inconsistent subsets as well as their associations. So, all the blocks of minimal inconsistent subsets remain unchanged in conflict modules. However, this does not hold for strong partition. To illustrate this, consider $K=\{a, \lnot a, b, \lnot b,\lnot a\vee b\}$, then the conflict module of K is itself, while the strong partition of K is $\{\{a,\lnot a\}, \{b,\lnot b\}, \{\lnot a\vee b\}\}$. On the other hand, the MIS-partition also tends to break the associations among minimal inconsistent subsets. Consider K again. The MIS-partition of $\mathsf{MI}(K)$ is $\{\{\{a,\lnot a\},\{b, \lnot b\}\}, \{\{a,\lnot a\vee b, \lnot b\}\}\}$. Such a partition breaks the block consists of all the three minimal inconsistent subsets.

In addition, the language splitting-based belief revision [3] seems similar to the modularity of inconsistent knowledge base. However, the language splitting-based belief revision aims to isolate local relevant information to new information when the new information brings conflicts to the old belief base, whilst we split an inconsistent knowledge base into several separate parts according to the distribution of all primitive conflicts given a context of inconsistency characterization.

The modularity-based framework for measuring the inconsistency in a knowledge base consists of two parts, i.e., inconsistency assessments for conflict modules and the integration operation over them. The sum operation is an usual one for integrating a set of variables. In this case, it is advisable to adapt the properties about additivity such as MinInc Separation presented in [6], Ind-decomposability presented in [7], and Sub-Additivity presented in [9] to ones in terms of modules.

6 Conclusion

We have proposed the notion of conflict modules to capture the association among primitive conflicts as well as all the primitive conflicts of a knowledge base under a given context of inconsistency characterization. The association among primitive conflicts makes primitive conflicts comprise separate blocks, each of which should be considered as a whole in inconsistency handling. Given a knowledge base, each of conflict modules exactly contains one block of primitive conflicts of that base, moreover, all the primitive conflicts are distributed over the conflict modules.

Then we have proposed a flexible framework for measuring inconsistency of a knowledge based on modularization of that knowledge base, which consists of two parts, i.e., inconsistency assessments for conflict modules and the integration operation over them. Some intuitive postulates about integration operation and properties for inconsistency assessment for modules have been proposed to characterize the framework.