# Incoherency Problems in a Combination of Description Logics and Rules

Authors: Shasha Huang; Jing Hao; Dang Luo
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

A paraconsistent semantics has been presented for hybrid MKNF knowledge bases—a combination method for description logics and rules. However, it is invalid when incoherency occurs in the knowledge base. In this paper, we introduce a semi-S
5 semantics for hybrid MKNF knowledge bases on the basis of nine-valued lattice, such that it is paraconsistent for incoherent knowledge base. It is shown that a semi-S
5 model can be computed via a fixpoint operator and is in fact a paraconsistent MKNF model when the knowledge base is incoherent. Moreover, we apply six-valued lattice to hybrid MKNF knowledge bases and present a suspicious semantics to distinguish different trust level information. At last, we investigate the relationship between suspicious semantics and paraconsistent semantics.


---

## Body

## 1. Introduction and Motivation

The Semantic Web [1] extends the current World Wide Web by standards and techniques that help machines to understand the meaning of data on the web to enable more powerful intelligent system applications. The essence of the Semantic Web is to describe data on the web by metadata that conveys the meaning of the data and that is expressed by means of ontologies.Web Ontology Language (OWL) [1] is based on the Description Logic 𝒮
ℛ
𝒪
ℐ
𝒬
(
𝒟
) [2] and has been recommended by the World Wide Web Consortium for representing ontologies. However, as monotonic logic, description logics (DLs for short) are not as expressive as needed for modeling some real world problems. Consequently, how to improve OWL has become a very important branch of research in the Semantic Web field, and one of the hot topics is how to better combine DL and rules in the sense of logic programming (LP), which is complementary to modeling in DL with respect to expressivity, have become a mature reasoning mechanism in the past thirty years.Several integration methods have been proposed. As a bridge between monotonic reasoning and nonmonotonic reasoning, hybrid MKNF knowledge bases have favourable properties of decidability, flexibility, faithfulness, and tightness. However, due to nonmonotonicity of rules, hybrid MKNF knowledge bases may be incoherent; that is, they do not have an MKNF model due to cyclic dependencies of a modal atom from default negation of the atom in the rule part. Standard reasoning systems will break down in this case. Nevertheless, one might want to derive useful information from incoherent hybrid MKNF knowledge bases. This is similar to paraconsistency, where nontrivial consequences shall be derivable from an inconsistent theory. For distinguishing the former reasoning with the later, we use term paracoherent reasoning to denote reasoning with incoherent knowledge bases. Both types of reasoning for rules have been studied, for example, Sakama and Inoue [3] and Eiter et al. [4]. For hybrid MKNF knowledge bases, Huang et al. [5] presented paraconsistent semantics for it, where only inconsistency can be handled. In this paper, we study the incoherency problem in hybrid MKNF knowledge bases and present a paracoherent reasoning system such that nontrivial conclusions can be drawn from incoherent knowledge bases.The remainder of the paper is organized as follows. In Section2 we have a quick look over hybrid MKNF knowledge bases. In Section 3, we present paracoherent semantics for hybrid MKNF knowledge bases on the basis of nine-valued lattice. In Section 4, we give suspicious MKNF models for such knowledge bases to distinguish different trust level information. In Section 5, we discuss the related work. We conclude and discuss the future work in Section 6.


## 2. Hybrid MKNF Knowledge Bases

At first, the logic of MKNF is a variant of first-order modal logic with two modal operators:K and n
o
t. We present the syntax of MKNF formulae taken from [6]. Let Σ be a signature that consists of constants and function symbols and first-order predicates, including the binary equality predicate ≈. A first-order atom P
(
t
1
,
…
,
t
l
) is an MKNF formula, where P is a first-order predicate and t
i are first-order terms. Other MKNF formulae are built over Σ by using standard connectives in first-order logic and two modal operators as follows: t
r
u
e, ¬
φ, φ
1
∧
φ
2, ∃
x
:
φ, K
φ, n
o
t
φ. Moreover, the symbols ∨, ⊃, ∀, and ≡ represent the usual boolean combination of previously introduced connectors. Formulae of the form K
φ (n
o
t
φ) are calledmodal  K-atoms (n
o
t-atoms). Modal K-atoms and n
o
t-atoms are calledmodal atoms. An MKNF formula φ is calledclosed if it contains no free variables and calledground if it is without any variables. An MKNF formula φ is calledmodally closed if it is closed and all modal operators are applied to closed subformulae. φ
[
t
/
x
] is the formula obtained from φ by substituting the termt for the variablex. Moreover, the equality predicate ≈ in Σ is interpreted as an equivalence relation on Δ, which is called auniverse and contains an infinite supply of constants, besides the constants occurring in the formulae.As shown in [6], hybrid MKNF knowledge bases consist of a finite number of MKNF rules and a decidable description logic knowledge base 𝒪, which satisfies the following conditions: (i) each knowledge base 𝒪
∈
𝒟
ℒ can be translated to a formula π
(
𝒪
) of function-free first-order logic with equality (see [2] for standard translation for description logic axioms), (ii) it supports ABox assertions of the form P
(
t
1
,
…
,
t
l
), where P is a predicate and each t
i a constant of 𝒟
ℒ, and (iii) satisfiability checking and instance checking (i.e., checking entailments of the form 𝒪
⊨
P
(
t
1
,
…
,
t
l
)) are decidable.Definition 1.
Let𝒪 be a DL knowledge base. A first-order function-free atom P
(
t
1
,
…
,
t
n
) over Σ such that P is ≈ or it occurs in 𝒪 is called a DL atom; all other atoms are called non-DL atoms. An MKNF rule r has the following form where H
i, A
i, B
i, are first-order function-free atoms:
(1)
K
H
1
∨
…
∨
K
H
n
⟵
K
A
n
+
1
∧
…
∧
K
A
m
∧
n
o
t
B
m
+
1
∧
…
∧
n
o
t
B
k
.
The sets {
K
H
i
}, {
K
A
i
}, and
{
n
o
t
B
i
} are called the rule head, the positive body, and the negative body, respectively. An MKNF rule r is nondisjunctive if n
=
1; r is positive if m
=
k; r is a fact if m
=
k
=
0. A program 𝒫 is a finite set of MKNF rules. A hybrid MKNF knowledge base 𝒦 is a pair (
𝒪, 𝒫
).To ensure that the MKNF logic is decidable, DL safety is introduced as a restriction to MKNF rules.Definition 2.
An MKNF rule is DL safe if every variable inr occurs in at least one non-DL atom K
B occurring in the body of r. A hybrid MKNF knowledge base 𝒦 is DL safe if all its rules are DL safe.In the rest of this paper, without explicitly stating it, we only consider hybrid MKNF knowledge bases which are DL safe.Definition 3.
Given a hybrid MKNF knowledge base𝒦 = (𝒪, 𝒫), the ground instantiation of 𝒦 is the knowledge base 𝒦
G = (𝒪, 𝒫
G), where 𝒫
G is obtained from 𝒫 by replacing each rule r of 𝒫 with a set of rules substituting each variable in r with constants from 𝒦 in all possible ways.Grounding the knowledge base𝒦 ensures that rules in 𝒫 apply only to objects that occur in 𝒦. And it has been proved by Motik and Rosati [6] that the MKNF models of 𝒦 and 𝒦
G coincide.Hybrid MKNF knowledge bases provide a paradigm for representing data sources on the web by rules and description logics simultaneously. Local closed world reasoning in the knowledge bases bridges the rules and DLs, accordingly overcomes the expressive limitation of rules and DLs, and enhance the expressivity.


## 3. Paracoherent Semantics for Hybrid MKNF Knowledge Base

Huang et al. [5] presented a four-valued paraconsistent semantics for hybrid MKNF knowledge bases, which can handle inconsistent information in the knowledge base. However, there is a kind of knowledge base which has no four-valued paraconsistent MKNF model but still contains useful information, for instance, the following example.Example 4.
Let𝒦
G = (
𝒪, 𝒫
G
) be a ground knowledge base, where 𝒪
=
{
p
} and 𝒫
G = {
K
a
←
n
o
t
a
} (p, a are literals).From [5], we know that 𝒦
G has no paraconsistent MKNF model. Generally, MKNF rule of the form K
a
←
n
o
t
a will lead to incoherency, which is a kind of inconsistency but cannot be handled by four-valued paraconsistent semantics. Therefore, it is desirable to provide a framework for incoherent knowledge bases. In this section, we will present a nine-valued semantics which is paraconsistent for incoherent knowledge bases.Firstly, we introduce the nine-valued lattice𝒩

9. Besides the four basic values t, f, ⊤, and ⊥, which constitute four-valued lattice ℱ
𝒪
𝒰
ℛ and, respectively, representtrue, false, contradictory (bothtrue andfalse), andunknown (neithertrue norfalse), 𝒩

9 contains five extra truth values b
t, b
f, b
⊤, t
c
b, and
f
c
b, which denotebelieved true,believed false,believed contradictory,true with contradictory belief, andfalse with contradictory belief, respectively. These values constitute a lattice ofnine-valued logic  𝒩

9 [3] (as shown in Figure 1) such that ⊥
≤
b
f
≤
x
≤
x
c
b
≤
⊤ and b
x
≤
b
⊤
≤
x
c
b (x
∈
{
t
,
f
}).Figure 1
Nine-valued Lattice𝒩
9.Letℱ be a first-order theory and ℬ
(
ℱ
) is the Herbrand base of ℱ. Let ℱ
k = ℬ
(
ℱ
)
∪
{
K
A
∣
A is a literal in ℬ
(
ℱ
)
}, and let
I be a subset of ℱ
k. Then anine-valued interpretation  I under the logic 𝒩
9 is defined as a function I: ℬ
(
ℱ
)
→
𝒩
9 such that, for each literal A
∈
ℬ
(
ℱ
),
(2)
(
A
)
I
=
lub
{
x
∣
x
=
t
if
A
∈
I
,
0000000
x
=
f
if
¬
A
∈
I
,
0000000
x
=
b
t
if
K
A
∈
I
,
0000000
x
=
b
f
if
K
¬
A
∈
I
,
000000
x
=
⊥
otherwise
}
,
where the term lub denotesleast upper bound.Every formula inℱ is assigned a value in 𝒩
9. The intuitive meaning of new introduced operator K is “belief.” For instance, K
A
∈
I means we believe that literal A belongs to interpretation I, which coincides with the truth value b
t. By the order structure of nine-valued lattice, (
A
)
I
=
b
⊤ iff both K
A
∈
I and K
¬
A
∈
I; (
A
)
I
=
f
c
b iff both K
A
∈
I and ¬
A
∈
I; (
A
)
I
=
t
c
b iff both A
∈
I and K
¬
A
∈
I. Furthermore, (
A
)
I = t iff (
¬
A
)
I = f, (
A
)
I = ⊤ iff (
¬
A
)
I = ⊤, (
A
)
I = ⊥ iff (
¬
A
)
I = ⊥, (
A
)
I = b
t iff (
¬
A
)
I = b
f, (
A
)
I = t
b
c iff (
¬
A
)
I = f
b
c, and (
A
)
I = b
⊤ iff (
¬
A
)
I = b
⊤.Under this logic, satisfaction of literals and default negation is defined as follows:I
⊨
9
A iff t
≤
(
A
)
I, I
⊨
9
¬
A iff f
≤
(
A
)
I, I
⊨
9
n
o
t
A iff (
A
)
I
≤
f, and I
⊨
9
n
o
t
¬
A iff (
A
)
I
≤
t. Satisfaction of other connectors is defined as usual.Now we come to the nine-valued semantics for hybrid MKNF knowledge bases.For distinguishing the two hybrid MKNF knowledge bases with stable model semantics and nine-valued semantics, we call the latter𝒩

9-MKNF knowledge bases.We use the syntax of para-MKNF knowledge base presented by Huang et al. [5] as the syntax of 𝒩

9-MKNF knowledge bases, which is similar to the classical knowledge base as presented in Section 2. The only difference between them is that MKNF rules are restricted to literals in para-MKNF knowledge bases. In our paper, we use MKNF rules defined as follows:
(3)
K
H
1
∨
…
∨
K
H
n
⟵
K
A
n
+
1
∧
…
∧
K
A
m
∧
n
o
t
B
m
+
1
∧
…
∧
n
o
t
B
k
,
where H
i, A
i, and B
i are first-order function-free literals.Semantically, we first introduce𝒩

9-MKNF structure (
ℐ
,
ℳ
,
𝒩
).Definition 5.
An𝒩

9-MKNF structure (
ℐ
,
ℳ
,
𝒩
) consists of a nine-valued interpretation ℐ and two nonempty sets of nine-valued interpretation interpretations ℳ and 𝒩. A nonempty set of nine-valued interpretations ℳ is called a 𝒩

9-MKNF interpretation.Definition 6.
Let(
ℐ
,
ℳ
,
𝒩
) be a 𝒩

9-MKNF structure. 𝒩

9 satisfaction of closed MKNF formulae is defined inductively as follows:(4)
(
ℐ
,
ℳ
,
𝒩
)
⊨
9
P
(
t
1
,
…
,
t
l
)
iff
P
ℐ

(
t
1
,
…
,
t
l
)
≥
t
,
(
ℐ
,
ℳ
,
𝒩
)
⊨
9
¬
φ
iff

(
ℐ
,
ℳ
,
𝒩
)
(
φ
)
≥
f
,
(
ℐ
,
ℳ
,
𝒩
)
⊨
9
φ
1
∧
φ
2
iff
(
ℐ
,
ℳ
,
𝒩
)
⊨
9
φ
i
,
i
=
1,2
,
(
ℐ
,
ℳ
,
𝒩
)
⊨
9
∃
x
:
φ
iff
(
ℐ
,
ℳ
,
𝒩
)
⊨
9
φ
[
a
x
]
for
some
α
∈
Δ
,
(
ℐ
,
ℳ
,
𝒩
)
⊨
9
φ
1
⊃
φ
2
iff
(
ℐ
,
ℳ
,
𝒩
)
⊭
9
φ
1
or
(
ℐ
,
ℳ
,
𝒩
)
⊨
9
φ
2
,
(
ℐ
,
ℳ
,
𝒩
)
⊨
9
K
φ
iff
(
𝒥
,
ℳ
,
𝒩
)
⊨
9
φ
∀
𝒥
∈
ℳ
,
(
ℐ
,
ℳ
,
𝒩
)
⊨
9
n
o
t
φ
iff
(
𝒥
,
ℳ
,
𝒩
)
(
φ
)
≤
f
for
some
𝒥
∈
𝒩
.A𝒩

9-MKNF interpretation ℳ is asemi-
S
5
model of a given closed MKNF formula φ, written as
ℳ
⊨
9
φ if and only if (
ℐ
,
ℳ
,
ℳ
)
⊨
9
φ for each ℐ
∈
ℳ.How to obtain models of a knowledge base is a basic problem in the reasoning process. The next work is around this topic.Let𝒦
G = (
𝒪, 𝒫
G
) be a ground 𝒩

9-MKNF knowledge base. The set of K-atoms of 𝒦
G, written as K
A
(
𝒦
G
), is the smallest set that contains (1) all ground K-atoms occurring in 𝒫
G and (3) a modal atom K
ξ for each ground modal atom n
o
t
ξ occurring in 𝒫
G. Let K
A
k
(
𝒦
G
) = K
A
(
𝒦
G
)
∪
{
K
K
A
∣
K
A is an element in K
A
(
𝒦
G
)
}. Furthermore, H
A
(
𝒦
G
) is the subset of K
A
(
𝒦
G
) that contains all K-atoms occurring in the head of some rule in 𝒫
G. H
A
k
(
𝒦
G
) is a subset of K
A
k
(
𝒦
G
).We now recall the fixpoint operator of positive paraconsistent MKNF knowledge base, which will be used to search for the semi-S
5 models of 𝒩

9-MKNF knowledge bases.Definition 7 (see [5]).
Let𝒦
G = (𝒪, 𝒫) be a ground positive para-MKNF knowledge base and 𝕊
∈
2
2
H
A
(
𝒦
G
). A mapping 𝔗
𝒦
G: 2
2
H
A
(
𝒦
G
)
→
2
2
H
A
(
𝒦
G
) is defined as
(5)
𝔗
𝒦
G
(
𝕊
)
=
⋃
S
∈
𝕊
‍
T
𝒦
G
(
S
)
,
where the mapping T
𝒦
G: 2
H
A
(
𝒦
G
)
→
2
2
H
A
(
𝒦
G
) is defined as follows. (i)
IfO
B
𝒪
,
S
⊨
4
A
i,  n
+
1
≤
i
≤
m for some ground integrity constraint ←
K
A
n
+
1
∧
…
∧
K
A
m in 𝒫
G, then T
𝒦
G
(
S
)
=
∅.
(ii)
Otherwise,T
𝒦
G
(
S
)
=
{
Q
t
⊆
H
A
(
𝒦
G
)
∣
Q
t
=
S
∪
R
t
∪
H
}, where R
t
=
{
K
H
t
∣
for
each
ground
MKNF
rule
C
j
∈
𝒫
G
:
O
B
𝒪
,
S
⊨
4
A
i,  n
+
1
≤
i
≤
m
} and H
=
{
K
ξ
∈
H
A
(
𝒦
G
)
∣
O
B
𝒪
,
S
⊨
4
ξ
}.Then we can use the following fixpoint procedure to compute paraconsistent MKNF models of positive para-MKNF knowledge bases:(6)
𝔗
𝒦
G
↑
0
=
∅
,
𝔗
𝒦
G
↑
n
+
1
=
𝔗
𝒦
G
(
𝔗
𝒦
G
↑
n
)
,
𝔗
𝒦
G
↑
ω
=
⋃
α
<
ω
‍
⋂
α
≤
n
<
ω
‍
𝔗
𝒦
G
↑
n
,
where n is a successor ordinal and ω is a limit ordinal.For general para-MKNF knowledge bases, a transformation was presented.Definition 8.
Let𝒦
G = (
𝒪, 𝒫
G
) be a ground para-MKNF knowledge base. Then its transformation is defined as 𝒦
G
* obtained by replacing each general rule in 𝒫
G with the following positive MKNF rule
(7)
K
μ
1
∨
…
∨
K
μ
n
∨
K
K
B
m
+
1
∨
…
∨
K
K
B
k
⟵
K
A
n
+
1
∧
…
∧
K
A
m
,
(8)
K
H
i
⟵
K
μ
i
for
1
≤
i
≤
n
,
(9)
⟵
K
μ
i
∧
K
B
j
for
1
≤
i
≤
n
,
m
+
1
≤
j
≤
k
,
(10)
K
μ
i
⟵
K
H
i
∧
K
μ
j
for
1
≤
i
,
j
≤
n
.Letγ
(
𝔗
𝒦
G
↑
ω
)
=
{
S
∣
S
∈
𝔗
𝒦
G
↑
ω
,
and
S
∈
𝔗
𝒦
G
(
{
S
}
)
} and min
⁡
⁡
(
𝕊
)
=
{
S
∣
there
exists
no
Q
∈
𝕊
such
that
Q
⊂
S
}. Given a set 𝕊
* that is a subset of 2
H
A
(
𝒦
G
*
), 𝕊
* iscanonical if K
K
a
∈
𝕊
* implies K
a
∈
𝕊
*. Φ
(
𝕊
*
)
=
{
S
*
∩
K
A
(
𝒦
G
)
∣
S
*
∈
𝕊
*
and
𝕊
*
is
c
a
n
o
n
i
c
a
l
}.Theorem 9.
Let𝒦
G = (
𝒪, 𝒫
G
) be a ground para-MKNF knowledge base, and then each paraconsistent MKNF model of 𝒦
G equals ℳ = {
ℐ
∣
ℐ
⊨
4
O
B
𝒪
,
P
h
}, where P
h is an element of the set ℚ
=
Φ
(
min
⁡
⁡
(
γ
(
𝔗
𝒦
G
*
↑
ω
)
)
).Note that the transformation of general MKNF rules is a little different from the one in [5]. However, this does not affect the result of Theorem 9. In fact, both two transformations have the same essence, transforming default negation in the rule body to a literal in rule head, and the unique difference is between “K
K
B
k” and “K
B
k” in the transformed MKNF rules. But from the canonical condition, K
K
B
k implies K
B
k, which does not change the original proof of [5, Theorem 4]. Therefore, Theorem 9 still holds if replacing K
a in (3) with K
K
a. In a previous work, we have mentioned that K
a is interpreted by “belief true,” corresponding to the truth value “b
t
.” As we have defined, a nine-valued interpretation can be represented by special Herbrand interpretation equipped with new elements of form K
ɛ based on classical Herbrand interpretation, in which ɛ is a literal.Given a set𝕊
* that is a subset of 2
H
A
(
𝒦
G
*
), 𝕊
* ismaximally canonical if there is no subset 𝕊
1
* of 2
H
A
(
𝒦
G
*
), such that {
K
K
a
∣
K
K
a
∈
𝕊
1
* and K
a
∉
𝕊
1
*
}
⊂
{
K
K
a
∣
K
K
a
∈
𝕊
* and K
a
∉
𝕊
*
}:
(11)
Φ
mc
(
𝕊
*
)
=
{
S
*
∩
K
A
(
𝒦
G
)
∣
S
*
∈
𝕊
*
0000
and
𝕊
*
is
canonical
}
.With maximally canonical condition, semi-S
5 models of a hybrid MKNF knowledge base can be computed by the fixpoint operator presented in Definition 7.Theorem 10.
Let𝒦
G
=
(
𝒪, 𝒫
G
) be a 𝒩
9-MKNF knowledge base, if P
h is an element of the set ℚ
=
Φ
m
c
(
min
⁡
⁡
(
γ
(
𝔗
𝒦
G
*
↑
ω
)
)
) and ℳ = {
ℐ
∣
ℐ
⊨
9
O
B
𝒪
,
P
h
}, then ℳ is a semi-S
5 model of 𝒦
G.Proof.
Given a maximally canonical elementP
h
*
∈
min
⁡
⁡
(
γ
(
𝔗
𝒦
G
*
↑
ω
)
) and ℳ
* = {
ℐ
∣
ℐ
⊨
9
O
B
𝒪
,
P
h
*
}. ℳ
* is a paraconsistent S
5 model of 𝒦
G
* by [5, Lemma 4]. For each transformed MKNF rules (3) and (7), if ℳ
*
⊨
9
K
A
i, for each n
+
1
≤
i
≤
m, then either ℳ
*
⊨
9
K
H
j, for some 1
≤
k
≤
n, or ℳ
*
⊨
9
K
K
B
t, for some m
+
1
≤
t
≤
k. Case 1: ℳ
*
⊨
9
K
H
j, for some 1
≤
k
≤
n, then the corresponding MKNF rule of form (1) is satisfied. Case 2: ℳ
*
⊨
9
K
K
B
t, for some m
+
1
≤
t
≤
k. Then for each nine-valued interpretation I
∈
ℳ
*, I
⊨
9
K
B
t, which means B
t
ℐ
≥
b
t and then ℳ
⊭
9
n
o
t
B
t. In either case, corresponding MKNF rule of form (1) is satisfied. Let P
h = P
h
*
∩
K
A
(
𝒦
G
) and ℳ = {
ℐ
∣
ℐ
⊨
9
O
B
𝒪
,
P
h
}, and then ℳ is a semi-S
5 model of 𝒦
G.Corollary 11.
If𝒦
G is a coherent knowledge base, then its semi-S
5 model coincides with paraconsistent MKNF model.Proof.
Whenmin
⁡
⁡
(
γ
(
𝔗
𝒦
G
*
↑
ω
)
) contains canonical element, it is also maximally canonical. Therefore, the result holds.Theorem 12.
Let𝒦
G
=
(
𝒪, 𝒫
G
) be a ground hybrid MKNF knowledge base, if 𝒦
G has an S
5 model, it has a semi-S
5 model.Proof.
If𝒦
G has an S
5 model, then it is easy to construct a MKNF interpretation that satisfies 𝒦
G
*. Then min
⁡
⁡
(
γ
(
𝔗
𝒦
G
*
↑
ω
)
) contains maximally canonical elements. Thus Φ
mc
(
min
⁡
⁡
(
γ
(
𝔗
𝒦
G
*
↑
ω
)
)
) is not empty. Theorem holds.Example 13.
Consider the incoherent knowledge base𝒦
G from Example 4. By Definition 8, 𝒫
G is transformed to 𝒫
G
*:
(12)
K
μ
∨
K
K
a
⟵
K
a
⟵
K
μ
⟵
K
μ
∧
K
a
.
We compute the fixpoint by applying the procedure presented in Section 3 to the knowledge base 𝒦
G
* = (
𝒪,𝒫
G
*
). By evaluating 𝔗
𝒦
G
↑
n
+
1
=
𝔗
𝒦
G
𝔗
𝒦
G
↑
n recursively, min
⁡
⁡
(
𝔗
𝒦
G
*
↑
n
) = {
{
K
K
a
,
K
p
}
}. Also, it can be easily verified that ℳ
=
{
ℐ
∣
ℐ
⊨
9
{
K
a
,
p
}
}.


## 4. Suspicious MKNF Models

As the beginning of this section, we give a motivation example as follows.Example 14.
Let𝒦
G = (
𝒪, 𝒫
G
) be a ground knowledge base, where 𝒪
=  {
p
},  𝒫
G = {
K
a
←
K
¬
p, K
¬
p
←, K
c
←
} (p, a, c are literals).In the above paraconsistent hybrid MKNF knowledge base𝒦
G, both c and a are the consequence of it. However, it is not difficult to find that a is derived by inconsistent information, while c is not. Apparently a is less credible than c. Therefore, it is necessary to distinguish information derived by inconsistencies from others.In order to distinguish two kinds of information, we introduce six-valued lattice, which is used by Sakama and Inoue [3] to present suspicious stable models for a program. As shown in Figure 2, there are two new introduced values s
f and s
f in six-valued lattice V
I, which, respectively, stand forsuspiciously false andsuspiciously true. These newly introduced values together with ℱ
𝒪
𝒰
ℛ constitute six-valued lattice such that ⊥
≤
s
x
≤
x
≤
⊤ (x
∈
{
t
,
f
}).Figure 2
Six-valued LatticeV
I.Letℱ be a first-order theory, ℱ
s = ℬ
(
ℱ
)
∪
{
A
s
∣
A is a literal in ℬ
(
ℱ
)
}, and I be a subset of ℱ
s. Then a six-valued interpretation I under the logic V
I is defined as a function I: ℬ
(
ℱ
)
→
V
I such that, for each literal A
∈
ℬ
(
ℱ
),
(13)
(
A
)
I
=
lub
{
x
∣
x
=
t
if
A
∈
I
,
0000000
x
=
f
if
¬
A
∈
I
,
0000000
x
=
s
t
if
A
s
∈
I
,
0000000
x
=
s
f
if
¬
A
s
∈
I
,
000000
x
=
⊥
otherwise
}
.
Note that (
A
)
I = s
t if and only if (
¬
A
)
I = s
f. Under the logic V
I, satisfaction of literals and default negation is defined as follows: I
⊨
6
A if and only if s
t
≤
(
A
)
I, I
⊨
6
¬
A if and only if s
f
≤
(
A
)
I, I
⊨
6   n
o
t
A if and only if (
A
)
I
≤
f, and I
⊨
6   n
o
t
¬
A if and only if (
A
)
I
≤
t. Satisfaction of other connectors is defined as usual.Given a hybrid MKNF knowledge base, its suspiciousS
5 models are defined by suspicious MKNF structure (
ℐ
,
ℳ
,
𝒩
), which is defined as usual.Definition 15.
A suspicious MKNF structure(
ℐ
,
ℳ
,
𝒩
) consists of a six-valued interpretation ℐ and two nonempty sets of six-valued interpretation interpretations ℳ and 𝒩. A nonempty set of six-valued interpretations ℳ is called a suspicious MKNF interpretation.Definition 16.
Let(
ℐ
,
ℳ
,
𝒩
) be a suspicious MKNF structure. Six-valued satisfaction of closed MKNF formulae is defined inductively as follows:(14)
(
ℐ
,
ℳ
,
𝒩
)
⊨
6
P
(
t
1
,
…
,
t
l
)
iff
P
ℐ
(
t
1
,
…
,
t
l
)
≥
s
t
,
(
ℐ
,
ℳ
,
𝒩
)
⊨
6
¬
φ
iff
(
ℐ
,
ℳ
,
𝒩
)
(
φ
)
≥
s
f
,
(
ℐ
,
ℳ
,
𝒩
)
⊨
6
φ
1
∧
φ
2
iff
(
ℐ
,
ℳ
,
𝒩
)
⊨
6
φ
i
,
i
=
1,2
,
(
ℐ
,
ℳ
,
𝒩
)
⊨
6
∃
x
:
φ
iff
(
ℐ
,
ℳ
,
𝒩
)
⊨
6
φ
[
a
x
]
for
some
α
∈
Δ
,
(
ℐ
,
ℳ
,
𝒩
)
⊨
6
φ
1
⊃
φ
2
iff
(
ℐ
,
ℳ
,
𝒩
)
⊭
6
φ
1
or
(
ℐ
,
ℳ
,
𝒩
)
⊨
6
φ
2
,
(
ℐ
,
ℳ
,
𝒩
)
⊨
6
K
φ
iff
(
𝒥
,
ℳ
,
𝒩
)
⊨
6
φ
∀
𝒥
∈
ℳ
,
(
ℐ
,
ℳ
,
𝒩
)
⊨
6
n
o
t
φ
iff
(
𝒥
,
ℳ
,
𝒩
)
(
φ
)
≤
f
for
some
𝒥
∈
𝒩
.A suspicious MKNF interpretationℳ is a s
u
s
p
i
c
i
o
u
s  S
5  m
o
d
e
l of a given closed MKNF formula φ, written as
ℳ
⊨
6
φ if and only if (
ℐ
,
ℳ
,
ℳ
)
⊨
6
φ for each ℐ
∈
ℳ.To compute the suspiciousS
5 models, we introduce a new fixpoint operator 𝔗
𝒦
G
s, which is little different from the operator 𝔗
𝒦
G on the definition of T
𝒦
G
(
S
). We replace T
𝒦
G
(
S
) with T
𝒦
G
s
(
S
), which is defined as follows.(i)
IfO
B
𝒪
,
S
⊨
6
A
i, n
+
1
≤
i
≤
m for some ground integrity constraint ←
K
A
1
∧
…
∧
K
A
m in 𝒫
G, then T
𝒦
G
s
(
S
)
=
∅.
(ii)
Otherwise,T
𝒦
G
s
(
S
)
=
{
S
∪
R
t
∪
H
∣ for each ground MKNF rule C
j
∈
𝒫
G: O
B
𝒪
,
S
⊨
6
A
i
,
n
+
1
≤
i
≤
m, R
t
=
∪
C
j
{
K
H
t
′
} (1
≤
t
≤
n), where H
t
′
=
H
t, if O
B
𝒪
,
S
⊨
6
A
i, and O
B
𝒪
,
S
⊭
6
¬
A
i for each n
+
1
≤
i
≤
m; H
t
′
=
H
t
s, otherwise. H
=
{
K
ξ
∈
H
A
(
𝒦
G
)
∣
O
B
𝒪
,
S
⊨
6
ξ
}
}.Note that the only difference between operatorsT
𝒦
G and T
𝒦
G
s is replacing K
H
i with K
H
i
s when K
H
i is derived by inconsistent information. However, this will not affect the final results, since ℳ
⊨
6
K
H
i
s implies ℳ
⊨
6
K
H
i for any suspicious MKNF interpretation ℳ. The superscript “s” in K
H
i
s is just like a label of suspicious information.Given a hybrid MKNF knowledge base𝒦
G and its transformation 𝒦
G
* as shown in Definition 8, let P
h be an element of the set ℚ
=
Φ
(
min
⁡
⁡
(
γ
(
𝔗
𝒦
G
*
s
↑
ω
)
)
) and ℳ = {
ℐ
∣
ℐ
⊨
6
O
B
𝒪
,
P
h
}. We call ℳ thesuspicious MKNF model of 𝒦
G.Theorem 17.
Let𝒦
G be a hybrid MKNF knowledge base. If ℳ is a suspicious MKNF model of 𝒦
G, then it is a suspicious S
5 model of 𝒦
G.Proof.
Letℳ
′ be the corresponding MKNF interpretation, in which each literal H
i
s is replaced by H
i. It is easy to see that ℳ
′ is a paraconsistent MKNF model of 𝒦
G. Moreover, for each literal A, ℳ
′
⊨
4
K
A if and only if ℳ
⊨
6
K
A, and ℳ
′
⊨
4
n
o
t
A if and only if ℳ
⊨
6
n
o
t
A. Thus ℳ satisfies each MKNF rule in 𝒦
G. Hence the result follows.


## 5. Related Works

Huang et al. [5] presented a four-valued paraconsistent semantics for hybrid MKNF knowledge bases, which resolved the inconsistency problem but was invalid to incoherency.Michael Fink [7] proposed paraconsistent hybrid theory for handling paraconsistent and paracoherent information in a combination of DL and rules, which is based on here-and-there logic.Sakama and Inoue [3] proposed a paraconsistent stable semantics for extended disjunctive programs. Moreover, they introduced suspicious stable models to distinguish facts affected by inconsistent information from others in a program. At last, in order to handle incoherency occurring in a program, they employed nine-valued lattice and presented semistable models, which is also used in [8] to cope with instability and also is the inspiration of our work on incoherency handling in hybrid MKNF knowledge bases.


## 6. Conclusion

In this paper we presented a semi-S
5 semantics for hybrid MKNF knowledge bases which is paraconsistent for incoherent knowledge bases. We showed that a semi-S
5 model can be computed via a fixpoint operator and is in fact a paraconsistent MKNF model when the knowledge base is incoherent. Furthermore, we applied six-valued lattice to hybrid MKNF knowledge bases and present a suspicious semantics to distinguish different trust level information.Our future work can be directed towards several paths. First of all, a well-founded semantics of hybrid MKNF knowledge bases has better complexity properties than paraconsistent semantics, and paraconsistent approach could be carried over to this paradigm. Moreover, in the real world, there are some other problems, such as probabilistic uncertainty, that cannot be coped with by classical reasoners. Then it is necessary to extend probabilistic semantics to hybrid MKNF knowledge bases.



---

*Source: 604753-2014-03-06.xml*