# A Max-Term Counting Based Knowledge Inconsistency Checking Strategy and Inconsistency Measure Calculation of Fuzzy Knowledge Based Systems

Authors: Hui-lai Zhi
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

The task of finding all the minimal inconsistent subsets plays a vital role in many theoretical works especially in large knowledge bases and it has been proved to be a NP-complete problem. In this work, at first we propose a max-term counting based knowledge inconsistency checking strategy. And, then, we put forward an algorithm for finding all minimal inconsistent subsets, in which we establish a Boolean lattice to organize the subsets of the given knowledge base and use leaf pruning to optimize the algorithm efficiency. Comparative experiments and analysis also show the algorithm’s improvement over past approaches. Finally, we give an application for inconsistency measure calculation of fuzzy knowledge based systems.


---

## Body

## 1. Introduction

A large knowledge system operating for a long time almost inevitably becomes polluted by wrong data that make the system inconsistent. Despite this fact, a sizeable part of the system remains unpolluted and retains useful information. It is widely adopted that a maximal consistent subset of a system contains a significant portion of unpolluted data [1]. So, simply characterizing a knowledge base as either consistent or inconsistent is of little practical value, and thus ensuring the consistency becomes an important issue [2–4].In practice, there are two types of methods: one method is based on minimal inconsistent subsets, where every strict subset is consistent and the other is directly based on maximal consistent subsets. Actually, the relationship between minimal inconsistent subsets and maximal consistent subsets was discovered separately in [1, 5, 6], which is known as the hitting subset problem [7].As finding minimal inconsistent subsets or maximal consistent subsets is NP-complete, the most efficient algorithm is not known yet, and there are a number of heuristic optimizations that can be used to substantially reduce the size of the search space. In practice, heuristic information [8, 9], optimization [10, 11], and hybrid techniques [12, 13] are recognized to reduce time complexity. In the latest research, McAreavey et al. presented a computational approach to finding and measuring inconsistency in arbitrary knowledge bases [14], while Mu et al. gave a method for measuring the significance of inconsistency in the viewpoints framework [15]. In all the abovementioned works, effectively finding minimal inconsistent subsets is the critical step which has a great impact on the applications especially for large knowledge bases. Apparently, its computational complexity depends on the underlying strategies used for checking the consistency of subsets of the knowledge base, but till now this important issue has not gotten a satisfying solution.In this paper, we first propose an efficient strategy to check the consistency of a given knowledge base. And, then, we put forward an algorithm to find all of the minimal inconsistent subsets of the given knowledge base. Thereafter, to illustrate the algorithm’s improvement, we conduct thorough comparative experiments and analysis with respect to one of the latest proposed algorithm MARCO [16] and give a discussion on the relative algorithms DAA [17] and PDDS [18]. Finally, we give an application for inconsistency measure calculation of fuzzy knowledge based systems.


## 2. Theoretical Basis

LetL denote the propositional language built from a finite set of variables P using logical connectives {
∧
,
∨
,
¬
,
→
} and logical constants {
T
,
F
}. Every variable p
∈
P is called an atomic formula or an atom. A literal is an atom or its negation. A clause φ is a formula restricted to a disjunction of literals and let v
a
r
(
φ
) denote the set of variables in a clause φ. A knowledge base K
∈
2
L is a finite set of arbitrary formulae.As every formula can be converted into an equivalent conjunction normal form (CNF) formula, knowledge base can be normalized in such a way that every formula contained in it is a clause. For a given normalized knowledge base, if there are no redundant clauses, we say it is an optimized knowledge base.By the syntactic approach in proof theory, if bothφ and ¬
φ can be derived from a knowledge base K, then we say K is inconsistent. With the semantic approach in model theory, an interpretation or world ω is a function ω
:
P
↦
{
F
,
T
} from P to the set of Boolean values {
F
,
T
}. Let 2
P denote the set of worlds of L. A world ω is a model of K, denoted as ω
⇒
K, iff K is true under ω in the classical truth-functional manner. Let m
o
d
(
K
) denote the set of models of K; that is, m
o
d
(
K
)
=
{
ω
:
ω
∈
2
P
∣
ω
⇒
K
}. We say that K is satisfiable iff there exists a model of K. Conversely, K is unsatisfiable iff there are no models of K. These two approaches coincide in propositional logic; that is, a knowledge base K is consistent iff K is satisfiable.In the following discussion, let the Greek lower case lettersφ
,
ψ
,
… be formulae from L and English lower case letters a
,
b
,
… variables from P.Definition 1.
For a Boolean function ofn variables x
1
,
…
,
x
n, a sum term in which each of the n variables appears once (in either its complemented or uncomplemented form) is called a max-term.Proposition 2.
Letx
1
,
…
,
x
n be n variables and M
0
,
…
,
M
2
n
-
1 the 2
n different max-terms built on these n variables. Then ∏
i
=
0
2
n
-
1
M
i
=
M
0
∧
M
1
∧
⋯
∧
M
2
n
-
1
=
F.For example, letM
0
=
p
∨
q, M
1
=
p
∨
¬
q, M
2
=
¬
p
∨
q, and M
3
=
¬
p
∨
¬
q be formulas built on {
p
,
q
}. Then it is trivial to show that M
0
∧
M
1
∧
M
2
∧
M
3
=
F, which means no assignments to p and q satisfy M
1, M
2, M
3, and M
4 simultaneously.Definition 3.
Letφ be a formula built on a set of variables P. Then we call e
x
t
(
φ
) the extension of φ; that is,(1)
e
x
t
φ
=
φ
∨
a
1
β
1
∨
⋯
∨
a
s
β
s
,
β
1
,
…
,
β
s
∈
0,1
s
,
a
1
,
…
,
a
s
=
P
-
var
⁡
φ
,and, for each i
∈
{
1,2
,
…
s
}, a
i
0
=
a
i, a
i
1
=
¬
a
i.For example, letφ
=
p
∨
¬
q be a formula built on P
=
{
p
,
q
,
r
}. Then we have var
⁡
(
φ
)
=
{
p
,
q
} and e
x
t
(
φ
)
=
{
p
∨
¬
q
∨
r
,
p
∨
¬
q
∨
¬
r
}. Actually, a simple manipulation leads to φ
=
p
∨
¬
q
=
(
p
∨
¬
q
∨
r
)
∧
(
p
∨
¬
q
∨
¬
r
).Remark 4.
It is easy to see that carrying extension ofφ does not change the original meaning of φ.Theorem 5.
Letφ
1
=
a
1
β
1
∨
a
2
β
2
∨
⋯
∨
a
r
β
r
(
β
i
∈
{
0,1
}
(
i
∈
{
1,2
,
…
,
r
}
)
) and φ
2
=
a
1
β
1
′
∨
a
2
β
2
′
∨
⋯  ∨  a
s
β
s
′
(
β
j
′
∈
{
0,1
}
(
j
∈
{
1,2
,
…
,
s
}
)
) be two formulas built on a set of variables P
(
P
=
m
), in which a
i
0
=
a
i, a
i
1
=
¬
a
i. Then the following propositions hold:(i)
If there exists a variablea
i such that one of a
i and ¬
a
i appears in φ
r and the other one appears in φ
s, then e
x
t
φ
1
∩
e
x
t
φ
2
=
0.
(ii)
Otherwise,e
x
t
φ
1
∩
e
x
t
φ
2
=
2
m
-
v
a
r
φ
1
∪
v
a
r
φ
2.Proof.
(i) As there exists a variablea
i such that one of a
i and ¬
a
i appears in φ
1 and the other one appears in φ
2, then one of a
i and ¬
a
i must appear in e
x
t
(
φ
1
) and the other one must appear in e
x
t
(
φ
2
), which makes e
x
t
(
φ
1
) differ from e
x
t
(
φ
2
). Therefore we have e
x
t
φ
1
∩
e
x
t
φ
2
=
0.
(ii) If there does not exist a variablea
i such that one of a
i and ¬
a
i appears in φ
1 and the other one appears in φ
2, then there are two situations that need to be surveyed, respectively.
Situation
1. If v
a
r
(
φ
1
)
∪
v
a
r
(
φ
2
)
=
P, then there exists only one common formula of φ
1 and φ
2, that is, φ
1
∨
φ
2. Hence, we have e
x
t
φ
1
∩
e
x
t
φ
2
=
1, which is equivalent to (2)
e
x
t
φ
1
∩
e
x
t
φ
2
=
2
m
-
v
a
r
φ
1
∪
v
a
r
φ
2
=
2
0
=
1
.
Situation
2. If v
a
r
(
φ
1
)
∪
v
a
r
(
φ
2
)
⊂
P, then the common formula of φ
1 and φ
2 is (3)
φ
1
∨
φ
2
∨
a
1
β
1
∨
⋯
∨
a
s
β
s
β
i
∈
0,1
i
∈
1,2
,
…
,
s
,
a
i
0
=
a
i
,
a
i
1
=
¬
a
i
,where {
a
1
,
…
,
a
s
}
=
P
-
v
a
r
(
φ
1
)
∪
v
a
r
(
φ
2
). Hence, we have(4)
φ
1
∨
φ
2
∨
a
1
β
1
∨
⋯
∨
a
s
β
s
=
2
m
-
v
a
r
φ
1
∪
v
a
r
φ
2
.
Therefore, combining the above two situations, the theorem is proved.Corollary 6.
Let{
φ
1
,
φ
2
,
…
,
φ
k
} be a set of formulas built on a set of variables P
(
P
=
m
). Then the following propositions hold:(1)
If there exist a variablea
i and two formulas φ
r and φ
s such that one of a
i and ¬
a
i appears in φ
r and the other one appears in φ
s, then ⋂
i
=
1
k
e
x
t
φ
i
=
0.
(2)
Otherwise,⋂
i
=
1
k
e
x
t
φ
i
=
2
m
-
⋃
i
=
1
k
v
a
r
φ
i.Theorem 7.
LetΦ
=
{
φ
1
,
φ
2
,
…
,
φ
n
} be a set of formulas built on a set of variables P
(
P
=
m
). Then after carrying extensions for φ
1
,
φ
2
,
…
,
φ
n, respectively, and using σ to denote the number of different formulas obtained, we have (5)
σ
=
⋃
i
=
1
n
e
x
t
φ
i
=
∑
i
=
1
n
e
x
t
φ
i
-
∑
1
≤
i
<
j
≤
n
e
x
t
φ
i
∩
e
x
t
φ
j
+
⋯
+
-
1
n
+
1
⋂
i
=
1
k
e
x
t
φ
i
.Moreover, if σ
=
2
m, then Φ is inconsistent; otherwise Φ is consistent.Proof.
According to inclusion-exclusion principle and in light of Proposition2 the proof is trivial.LetΦ
=
{
p
,
¬
p
∨
q
,
r
} be a set of formulas defined on {
p
,
q
,
r
}. According to Theorem 7, we have σ
=
2
3
-
1
+
2
3
-
2
+
2
3
-
2
-
0
-
2
3
-
2
-
2
3
-
3
+
0
=
5 and thus Φ is consistent.


## 3. An Algorithm for Finding All Minimal Inconsistent Subsets

In this section, at first we propose an algorithm for finding all nominal inconsistent subsets via Boolean lattice. And, then, we give an illustrative example and a thorough comparative study with algorithm MARCO by using the number of visited subsets as the benchmark. Besides this, we also give a discussion on relative algorithms DAA and PDDS.


### 3.1. Algorithm

An algorithm to find the minimal inconsistent subsets of a given knowledge system must check each of its subsets for inconsistency. One way to proceed is to construct a Boolean lattice of subsets of the given knowledge system, which is initially used by Bird and Hinze in the process of finding the maximal consistent subsets [19].A latticeL is called a Boolean lattice if(i)
L is distributive,
(ii)
L has 0 and 1,
(iii)
eacha
∈
L has a complement a
∗
∈
L.Figure1 sketches a three-variable Boolean lattice, where all the labels of the nodes consist of the power set of set {
a
,
b
,
c
}.Figure 1
Three-variable Boolean lattice.In Algorithm1, a Boolean lattice is also established and leaf pruning is adopted to optimize the algorithm efficiency. Because the cardinality of the subsets at each level is smaller than those on the level above it, a breadth-first search of the lattice will consider all smaller sets before any larger ones. Apparently, leaf pruning strategy can be used based on the fact that if a node denotes an minimal inconsistent subset, then all of its ancestors are inconsistent; dually, if a node denotes a consistent subset, then all of its descendents are consistent.Algorithm 1:Finding all the minimal inconsistent subsets of a knowledge base.
Input: a knowledge baseK
Output: all the minimal inconsistent subsetsMI
(
K
) of knowledge base K
Begin
(1) normalize the knowledge baseK to ensure that every formula contained in it is a clause,
and denoted it asnorm
⁡
(
K
)
=
φ
1
,
φ
2
,
…
,
φ
m;
initializeMI
(
K
) to be an empty set of sets;
(2) build am variable Boolean lattice BL
m with each node denoting a set of formulas
(if a node denotes an formula set, then we call it a n-degree node), and give each node a unmarked flag;
(3) set up an empty listList, and put all of the 2-degree nodes into List;
fetch the headHead from List;
ifHead is inconsistent, then  //by using Theorem 7
Begin
putHead into MI
(
K
);
mark all the ancestors ofHead;
End
elseHead is consistent, then
Begin
insert all of the un-marked upper neighbors ofHead at the front of List;
mark all the descendants ofHead, and if they exist in List, then remove them from List;
End
(4) returnMI
(
K
).
End.According to Theorem7, directly computing σ is time consuming, so we will store the intermediate calculation results. For example, in Algorithm 1, for each visited node (whose corresponding formula set is {
φ
i
∣
i
∈
T
}), we will store the value of ⋂
i
∈
T
e
x
t
φ
i. Apparently, when computing the σ value of k-degree node, the stored value ⋂
i
∈
T
e
x
t
φ
i of each (
k
-
1
)-degree nodes can be reused to save time cost.In the minimal inconsistent subsets finding algorithm proposed in [14], which is derived indirectly on maximal consistent subset, there exists a disadvantage that while getting maximal consistent subset, pseudo-maximal consistent subset will be generated [11, 15]. As our proposed algorithm always checks the smaller sets before the larger sets, so it can overcome this problem.If the maximal cost for checking inconsistency of isT, the complexity of this algorithm is O
(
2
K
T
) in the worst case. In the following, by using experiment, we will show the relationship between the number of subsets that were checked for inconsistency and the size the of the knowledge base with respect to different probabilities that two formulas are consistent.In the experiment, we use generator GENBAL [20] to generate knowledge bases. The graphs in Figures 2 and 3 show the number of subsets that were checked for inconsistency related to K, the number of clauses contained in the given normalized knowledge base and p, and the probability that two formulas are consistent. All counts are averaged across 100 randomly generated formulae by using GENBAL.Figure 2
Number of subsets visited as a function ofp for K
=
15.Figure 3
Number of subsets visited as a function ofK for p
=
0.3, p
=
0.6, and p
=
0.9.From Figures2 and 3, we can see that larger values for p mean that more subsets will be checked. Moreover, it is easy to show that larger values for p generally also lead to fewer and smaller minimal inconsistent subsets.


### 3.2. An Illustrative Example and Comparative Study

Apart from our proposed method, there are many other solvers for computing minimal inconsistent subsets. One of the latest published algorithm is MARCO [16], which adopts the most recent advances. At first we give an illustrative example and then we compare our method with MARCO.Example 8.
Considering a set of formulas,1
:
(
a
), 2
:
(
¬
a
), 3
:
(
¬
a
∨
b
), and 4
:
(
¬
b
), which is used in [16], we use Algorithm 1 to find all the minimal inconsistent subsets.
At first we also establish a Boolean lattice, which is shown in Figure4.
Then we establish a listL
i
s
t, and initialize L
i
s
t as (6)
L
i
s
t
:
1,2
,
1,3
,
1,4
,
2,3
,
2,4
,
3,4
.Figure 4
Four-variable Boolean lattice.Fetch the headH
e
a
d from L
i
s
t; that is, H
e
a
d
=
{
1,2
}. According to Theorem 7, H
e
a
d
=
{
1,2
} is inconsistent, and then mark its ancestors {
1,2
,
3
},  {
1,2
,
4
}, and {
1,2
,
3,4
}.Fetch the headH
e
a
d from L
i
s
t; that is, H
e
a
d
=
{
1,3
}. According to Theorem 7, H
e
a
d
=
{
1,3
} is consistent; insert its unmarked upper neighbor {
1,3
,
4
} at the front of L
i
s
t, and mark its descendants {
1
} and {
3
}.Fetch the headH
e
a
d from L
i
s
t; that is, H
e
a
d
=
{
1,3
,
4
}. According to Theorem 7, H
e
a
d
=
{
1,3
,
4
} is inconsistent.Fetch the headH
e
a
d from L
i
s
t; that is, H
e
a
d
=
{
1,4
}. According to Theorem 7, H
e
a
d
=
{
1,4
} is consistent, and mark its unmarked descendant {
4
}.Fetch the headH
e
a
d from L
i
s
t; that is, H
e
a
d
=
{
2,3
}. According to Theorem 7, H
e
a
d
=
{
1,3
} is consistent; insert its unmarked upper neighbor {
2,3
,
4
} at the front of L
i
s
t, and mark its unmarked descendant {
2
}.Fetch the headH
e
a
d from L
i
s
t; that is, H
e
a
d
=
{
2,3
,
4
}. According to Theorem 7, H
e
a
d
=
{
1,3
} is consistent, and mark its unmarked descendant {
2,4
} and {
3,4
} and remove {
2,4
} and {
3,4
} from L
i
s
t.At this point,L
i
s
t is empty; algorithm terminates with results {
1,2
} and {
1,3
,
4
}.It is apparent that in order to get all the minimal inconsistent subsets we have to judge the consistency of 6 sets, which are(7)
1,2
,
1,3
,
1,3
,
4
,
1,4
,
2,3
,
2,3
,
4
.Fundamentally, the MARCO algorithm operates repeatedly:(i)
Selecting an unexplored point in the power set lattice, a subset ofC that we call a seed.
(ii)
Checking the satisfiability of the seed.
(iii)
Growing or shrinking it to an MSS or an MUS as appropriate.
(iv)
Marking a corresponding region of the lattice as explored.When we use algorithm MARCO, the consistency of 10 sets needs to be considered one by one, which are(8)
1,2
,
4
,
1,2
,
3
,
1,3
,
2
,
2,3
,
2,4
,
2,3
,
4
,
1,4
,
1,3
,
4
.So, our algorithm performs better than MARCO with respect to the number of the visited sets.The difference between our algorithm and MARCO is that our algorithm traverses the Boolean lattice incremental according to the cardinalities of the sets while MARCO traverses the Boolean lattice randomly, as the functionGetUnexplored() used in MARCO randomly returns any unexplored sets. As the objectives of both algorithms are to find all of the minimal sets which are inconsistent, the incremental feature of our algorithm brings a higher efficiency.In the comparative study, we also use generator GENBAL [20] to generate knowledge base. Number of visited subsets is used as the benchmarks, as it is more objective than the other benchmarks. For example, we do not choose CPU times as the benchmark as it is strongly affected by the running environment, including the status of both hardware and software.The graphs in Figures5, 6, and 7 show the number of subsets that were checked for inconsistency related to K, the number of clauses contained in the given normalized knowledge base and p, and the probability that two formulas are consistent. All counts are averaged across 100 randomly generated formulae by using GENBAL. All of Figures 5, 6, and 7 show that our algorithm performs better than MARCO with respect to the number of the visited sets.Figure 5
Number of subsets visited as a function ofK for p
=
0.3.Figure 6
Number of subsets visited as a function ofK for p
=
0.6.Figure 7
Number of subsets visited as a function ofK for p
=
0.9.DAA is another algorithm that exploits the hitting set duality between minimal correction sets (MCSes) and minimal unsatisfiable subsets [17]. DAA uses the Grow subroutine on known-satisfiable subsets to produce maximal satisfiable subsets (MSSes) and their complementary MCSes and then computes minimal hitting sets of the MCSes found thus far. PDDS, an approach closely related to DAA, was later proposed [18]. The main differences are that PDDS takes an initial set of either maximal satisfiable subsets (MUSes) or MCSes as input, and PDDS does not necessarily compute all hitting sets of the MCSes at each iteration, avoiding the memory scaling issues of DAA.The DAA and PDDS algorithms have the benefit that they are decoupled from the choice of hitting set algorithm. It is pointed out that the choice of the incremental algorithm presented by Fredman and Khachiyan [21] for computing hitting sets results in a version of the DAA algorithm with worst case runtime that is subexponential in the size of the output [22]. And studies have shown that MARCO performs better than DAA and PDDS [16].


## 3.1. Algorithm

An algorithm to find the minimal inconsistent subsets of a given knowledge system must check each of its subsets for inconsistency. One way to proceed is to construct a Boolean lattice of subsets of the given knowledge system, which is initially used by Bird and Hinze in the process of finding the maximal consistent subsets [19].A latticeL is called a Boolean lattice if(i)
L is distributive,
(ii)
L has 0 and 1,
(iii)
eacha
∈
L has a complement a
∗
∈
L.Figure1 sketches a three-variable Boolean lattice, where all the labels of the nodes consist of the power set of set {
a
,
b
,
c
}.Figure 1
Three-variable Boolean lattice.In Algorithm1, a Boolean lattice is also established and leaf pruning is adopted to optimize the algorithm efficiency. Because the cardinality of the subsets at each level is smaller than those on the level above it, a breadth-first search of the lattice will consider all smaller sets before any larger ones. Apparently, leaf pruning strategy can be used based on the fact that if a node denotes an minimal inconsistent subset, then all of its ancestors are inconsistent; dually, if a node denotes a consistent subset, then all of its descendents are consistent.Algorithm 1:Finding all the minimal inconsistent subsets of a knowledge base.
Input: a knowledge baseK
Output: all the minimal inconsistent subsetsMI
(
K
) of knowledge base K
Begin
(1) normalize the knowledge baseK to ensure that every formula contained in it is a clause,
and denoted it asnorm
⁡
(
K
)
=
φ
1
,
φ
2
,
…
,
φ
m;
initializeMI
(
K
) to be an empty set of sets;
(2) build am variable Boolean lattice BL
m with each node denoting a set of formulas
(if a node denotes an formula set, then we call it a n-degree node), and give each node a unmarked flag;
(3) set up an empty listList, and put all of the 2-degree nodes into List;
fetch the headHead from List;
ifHead is inconsistent, then  //by using Theorem 7
Begin
putHead into MI
(
K
);
mark all the ancestors ofHead;
End
elseHead is consistent, then
Begin
insert all of the un-marked upper neighbors ofHead at the front of List;
mark all the descendants ofHead, and if they exist in List, then remove them from List;
End
(4) returnMI
(
K
).
End.According to Theorem7, directly computing σ is time consuming, so we will store the intermediate calculation results. For example, in Algorithm 1, for each visited node (whose corresponding formula set is {
φ
i
∣
i
∈
T
}), we will store the value of ⋂
i
∈
T
e
x
t
φ
i. Apparently, when computing the σ value of k-degree node, the stored value ⋂
i
∈
T
e
x
t
φ
i of each (
k
-
1
)-degree nodes can be reused to save time cost.In the minimal inconsistent subsets finding algorithm proposed in [14], which is derived indirectly on maximal consistent subset, there exists a disadvantage that while getting maximal consistent subset, pseudo-maximal consistent subset will be generated [11, 15]. As our proposed algorithm always checks the smaller sets before the larger sets, so it can overcome this problem.If the maximal cost for checking inconsistency of isT, the complexity of this algorithm is O
(
2
K
T
) in the worst case. In the following, by using experiment, we will show the relationship between the number of subsets that were checked for inconsistency and the size the of the knowledge base with respect to different probabilities that two formulas are consistent.In the experiment, we use generator GENBAL [20] to generate knowledge bases. The graphs in Figures 2 and 3 show the number of subsets that were checked for inconsistency related to K, the number of clauses contained in the given normalized knowledge base and p, and the probability that two formulas are consistent. All counts are averaged across 100 randomly generated formulae by using GENBAL.Figure 2
Number of subsets visited as a function ofp for K
=
15.Figure 3
Number of subsets visited as a function ofK for p
=
0.3, p
=
0.6, and p
=
0.9.From Figures2 and 3, we can see that larger values for p mean that more subsets will be checked. Moreover, it is easy to show that larger values for p generally also lead to fewer and smaller minimal inconsistent subsets.


## 3.2. An Illustrative Example and Comparative Study

Apart from our proposed method, there are many other solvers for computing minimal inconsistent subsets. One of the latest published algorithm is MARCO [16], which adopts the most recent advances. At first we give an illustrative example and then we compare our method with MARCO.Example 8.
Considering a set of formulas,1
:
(
a
), 2
:
(
¬
a
), 3
:
(
¬
a
∨
b
), and 4
:
(
¬
b
), which is used in [16], we use Algorithm 1 to find all the minimal inconsistent subsets.
At first we also establish a Boolean lattice, which is shown in Figure4.
Then we establish a listL
i
s
t, and initialize L
i
s
t as (6)
L
i
s
t
:
1,2
,
1,3
,
1,4
,
2,3
,
2,4
,
3,4
.Figure 4
Four-variable Boolean lattice.Fetch the headH
e
a
d from L
i
s
t; that is, H
e
a
d
=
{
1,2
}. According to Theorem 7, H
e
a
d
=
{
1,2
} is inconsistent, and then mark its ancestors {
1,2
,
3
},  {
1,2
,
4
}, and {
1,2
,
3,4
}.Fetch the headH
e
a
d from L
i
s
t; that is, H
e
a
d
=
{
1,3
}. According to Theorem 7, H
e
a
d
=
{
1,3
} is consistent; insert its unmarked upper neighbor {
1,3
,
4
} at the front of L
i
s
t, and mark its descendants {
1
} and {
3
}.Fetch the headH
e
a
d from L
i
s
t; that is, H
e
a
d
=
{
1,3
,
4
}. According to Theorem 7, H
e
a
d
=
{
1,3
,
4
} is inconsistent.Fetch the headH
e
a
d from L
i
s
t; that is, H
e
a
d
=
{
1,4
}. According to Theorem 7, H
e
a
d
=
{
1,4
} is consistent, and mark its unmarked descendant {
4
}.Fetch the headH
e
a
d from L
i
s
t; that is, H
e
a
d
=
{
2,3
}. According to Theorem 7, H
e
a
d
=
{
1,3
} is consistent; insert its unmarked upper neighbor {
2,3
,
4
} at the front of L
i
s
t, and mark its unmarked descendant {
2
}.Fetch the headH
e
a
d from L
i
s
t; that is, H
e
a
d
=
{
2,3
,
4
}. According to Theorem 7, H
e
a
d
=
{
1,3
} is consistent, and mark its unmarked descendant {
2,4
} and {
3,4
} and remove {
2,4
} and {
3,4
} from L
i
s
t.At this point,L
i
s
t is empty; algorithm terminates with results {
1,2
} and {
1,3
,
4
}.It is apparent that in order to get all the minimal inconsistent subsets we have to judge the consistency of 6 sets, which are(7)
1,2
,
1,3
,
1,3
,
4
,
1,4
,
2,3
,
2,3
,
4
.Fundamentally, the MARCO algorithm operates repeatedly:(i)
Selecting an unexplored point in the power set lattice, a subset ofC that we call a seed.
(ii)
Checking the satisfiability of the seed.
(iii)
Growing or shrinking it to an MSS or an MUS as appropriate.
(iv)
Marking a corresponding region of the lattice as explored.When we use algorithm MARCO, the consistency of 10 sets needs to be considered one by one, which are(8)
1,2
,
4
,
1,2
,
3
,
1,3
,
2
,
2,3
,
2,4
,
2,3
,
4
,
1,4
,
1,3
,
4
.So, our algorithm performs better than MARCO with respect to the number of the visited sets.The difference between our algorithm and MARCO is that our algorithm traverses the Boolean lattice incremental according to the cardinalities of the sets while MARCO traverses the Boolean lattice randomly, as the functionGetUnexplored() used in MARCO randomly returns any unexplored sets. As the objectives of both algorithms are to find all of the minimal sets which are inconsistent, the incremental feature of our algorithm brings a higher efficiency.In the comparative study, we also use generator GENBAL [20] to generate knowledge base. Number of visited subsets is used as the benchmarks, as it is more objective than the other benchmarks. For example, we do not choose CPU times as the benchmark as it is strongly affected by the running environment, including the status of both hardware and software.The graphs in Figures5, 6, and 7 show the number of subsets that were checked for inconsistency related to K, the number of clauses contained in the given normalized knowledge base and p, and the probability that two formulas are consistent. All counts are averaged across 100 randomly generated formulae by using GENBAL. All of Figures 5, 6, and 7 show that our algorithm performs better than MARCO with respect to the number of the visited sets.Figure 5
Number of subsets visited as a function ofK for p
=
0.3.Figure 6
Number of subsets visited as a function ofK for p
=
0.6.Figure 7
Number of subsets visited as a function ofK for p
=
0.9.DAA is another algorithm that exploits the hitting set duality between minimal correction sets (MCSes) and minimal unsatisfiable subsets [17]. DAA uses the Grow subroutine on known-satisfiable subsets to produce maximal satisfiable subsets (MSSes) and their complementary MCSes and then computes minimal hitting sets of the MCSes found thus far. PDDS, an approach closely related to DAA, was later proposed [18]. The main differences are that PDDS takes an initial set of either maximal satisfiable subsets (MUSes) or MCSes as input, and PDDS does not necessarily compute all hitting sets of the MCSes at each iteration, avoiding the memory scaling issues of DAA.The DAA and PDDS algorithms have the benefit that they are decoupled from the choice of hitting set algorithm. It is pointed out that the choice of the incremental algorithm presented by Fredman and Khachiyan [21] for computing hitting sets results in a version of the DAA algorithm with worst case runtime that is subexponential in the size of the output [22]. And studies have shown that MARCO performs better than DAA and PDDS [16].


## 4. Inconsistency Measure Calculation for Fuzzy Knowledge Based Systems

In this section, we show an application of Algorithm1 for inconsistency measure calculation of fuzzy knowledge based systems.Fuzzy knowledge based systems are a typical rule-based inference system for providing expertise over a domain, which is capable of drawing conclusions from given uncertain evidence [23]. In fuzzy knowledge based systems, knowledge is represented by using possibilistic logic.LetΔ
=
{
(
φ
1
,
α
1
)
,
(
φ
2
,
α
2
)
,
…
,
(
φ
n
,
α
n
)
} denote a fuzzy knowledge based system, in which φ
1
,
φ
2
,
…
,
φ
n are classical propositional logic formulas and α
1
,
α
2
,
…
,
α
n are their possibility measures.Definition 9.
LetΔ be a fuzzy knowledge based system. If Δ contains two formulas (
φ
,
α
1
), (
φ
,
α
2
) with α
1
>
α
2, then we call Δ
′
=
Δ
-
(
φ
,
α
2
) the possibility based deduction result of Δ and denote by d
(
Δ
)
=
Δ
′.Definition 10.
Let(
φ
,
α
) be a possibility formula built on a set of variables P. Then we call e
x
t
(
φ
,
α
) the extension of (
φ
,
α
); that is,(9)
e
x
t
φ
,
α
=
φ
∨
γ
1
β
1
∨
⋯
∨
γ
s
β
s
,
α
,
β
1
,
…
,
β
s
∈
0,1
s
,
γ
1
,
…
,
γ
s
=
P
-
var
⁡
φ
,and for each i
∈
{
1,2
,
…
,
s
}, γ
i
0
=
γ
i, γ
i
1
=
¬
γ
i.Definition 11.
LetΔ
=
{
(
φ
1
,
α
1
)
,
(
φ
2
,
α
2
)
,
…
,
(
φ
n
,
α
n
)
} be a fuzzy knowledge based system. Then we call π
(
Δ
)
=
{
φ
1
,
φ
2
,
…
,
φ
n
} the projection of Δ onto the classical knowledge base.Definition 12 (see [24]).
LetΔ be a fuzzy knowledge based system. If Δ is inconsistent, then its inconsistency measure is defined as(10)
I
N
C
O
N
Δ
=
m
a
x
Δ
′
⊆
Δ
,
I
N
C
O
N
Δ
′
>
0
min
⁡
α
∣
φ
,
α
∈
Δ
′
.Theorem 13.
LetΔ be a fuzzy knowledge based system built on a set of variables P
(
P
=
m
). After extensions and possibility based deduction of Δ are performed, Δ
′ is derived. If π
Δ
′
=
2
m, then Δ is inconsistent, and its inconsistency measure is(11)
I
N
C
O
N
Δ
=
M
i
n
α
i
∣
φ
i
,
α
i
∈
Δ
′
.Proof.
AsI
N
C
O
N
(
Δ
)
=
m
a
x
Δ
∗
⊆
Δ
′
,
I
N
C
O
N
Δ
∗
>
0
min
⁡
α
∣
φ
,
α
∈
Δ
∗ and Δ
′ is result of extensions and possibility based deduction of Δ, then I
N
C
O
N
(
Δ
)
=
I
N
C
O
N
(
Δ
′
). Since π
Δ
′
=
2
m, we know that Δ
′ is inconsistent, and its inconsistency measure is M
i
n
α
i
∣
φ
i
,
α
i
∈
Δ
′. Hence, the theorem is proved.Example 14.
LetΔ
=
{
(
¬
p
∨
q
,
0.6
)
,
(
p
∨
¬
q
,
0.8
)
,
(
q
∨
r
,
1
)
,
(
r
,
0.3
)
,
(
¬
r
,
0.5
)
} be a fuzzy knowledge based system built on {
p
,
q
,
r
}.
After carrying extensions and possibility based deduction ofΔ, we get(12)
Δ
′
=
¬
p
∨
q
∨
¬
r
,
0.6
,
p
∨
¬
q
∨
r
,
0.8
,
p
∨
¬
q
∨
¬
r
,
0.8
,
p
∨
q
∨
r
,
1
,
¬
p
∨
q
∨
r
,
1
,
¬
p
∨
¬
q
∨
r
,
0.3
,
p
∨
q
∨
¬
r
,
0.5
,
¬
p
∨
¬
q
∨
¬
r
,
0.5
.
According to Theorem13, we know that Δ is inconsistent and its inconsistency measure is 0.3.


## 5. Conclusions

The purpose of this paper is to find all the minimal inconsistent subsets of a given knowledge system. Initially we propose a max-term counting based knowledge inconsistency checking strategy. And, then, we put forward an algorithm for finding all minimal inconsistent subsets, in which we establish a Boolean lattice to organize the subsets of the given knowledge base and use leaf pruning to optimize the algorithm efficiency. Finally, we give a method for inconsistency measure calculation of fuzzy knowledge based system.As in a fuzzy knowledge based system, there may be several statements in contradiction to each other; how to measure the significance of the inconsistency is a valuable problem for further study.



---

*Source: 134950-2015-08-13.xml*