# «Paraconsistent Reasoning for Expressive and Tractable Description Logics Yue Ma1, Pascal Hitzler2, and Zuoquan Lin1 Department of Information ...»

Paraconsistent Reasoning for Expressive and Tractable

Description Logics

Yue Ma1, Pascal Hitzler2, and Zuoquan Lin1

Department of Information Science, Peking University, China

AIFB, Universit¨ t Karlsruhe, Germany

a

{mayue,lz}@is.pku.edu.cn, hitzler@aifb.uni-karlsruhe.de

Abstract. Four-valued description logic has been proposed to reason with description logic based inconsistent knowledge bases, mainly ALC. This approach

has a distinct advantage that it can be implemented by invoking classical reasoners to keep the same complexity as classical semantics. In this paper, we further study how to extend the four-valued semantics to more expressive description logics, such as SHIQ, and to more tractable description logics including EL++, DL-Lite, and Horn-DLs. The most effort we spend deﬁning the four-valued semantics of expressive four-valued description logics is on keeping the reduction from four-valued semantics to classical semantics as in the case of ALC;

While for tractable description logics, we mainly focus on how to maintain their tractability when adopting four-valued semantics.

1 Introduction Expressive and tractable description logics have been well-studied in the ﬁeld of semantic web applications [12, 13]. However, real knowledge bases and data for Semantic Web applications will rarely be perfect. They will be distributed and multi-authored.

They will be assembled from different sources and reused. It is unreasonable to expect such realistic knowledge bases to be always logically consistent, and it is therefore important to study ways of dealing with inconsistencies in both expressive and tractable description logic based ontologies, as classical description logics break down in the presence of inconsistent knowledge.

About inconsistency handling of ontologies based on description logics, two fundamentally different approaches can be distinguished. The ﬁrst is based on the assumption that inconsistencies indicate erroneous data which is to be repaired in order to obtain a consistent knowledge base, e.g. by selecting consistent subsets for the reasoning process [14, 5, 4]. The other approach yields to the insight that inconsistencies are a natural phenomenon in realistic data which are to be handled by a logic which tolerates it [11, 15, 8]. Such logics are called paraconsistent, and the most prominent of them are based on the use of additional truth values standing for underdeﬁned (i.e. neither true We acknowledge support by the German Federal Ministry of Education and Research (BMBF) under the SmartWeb project (grant 01 IMD01 B), by the EU under the IST project NeOn (ISThttp://www.neon-project.org/), andby the Deutsche Forschungsgemeinschaft (DFG) in the ReaSem project.

nor false) and overdeﬁned (or contradictory, i.e. both true and false). Such logics are appropriately called four-valued logics [2, 1]. We believe that either of the approaches is useful, depending on the application scenario. Besides this, four-valued semantics proves useful for measuring inconsistency of ontologies [9], which can provide context information for facilitating inconsistency handling.

In this paper, based on our study of paraconsistent semantics for ALC in [8], we contribute to the inconsistency handling for DLs in terms of the four-valued semantics

**for expressive and tractable DLs in following aspects:**

– The extension of four-valued semantics to SHIQ is deﬁned. Specially, we show that it still can be reduced to classical semantics regardless its high expressivity.

– The extension of four-valued semantics to tractable description logics EL++, HornDLs, DL-Lite family are studied one by one. We show that the internal inclusion axiom form is a safe way to maintain the tractability when adopting four-valued semantics.

– Compared with our existing work on four-valued semantics of ALC, in this paper, we do not impose four-valued semantics on roles for DLs except DL-Lite. The reasons are: 1) Negative roles are not used as concept constructors in ALC, SHIQ, EL++, or Horn-DLs such that contradiction caused directly by roles can be ignored.

2) We claim that the four-valued semantics should be deﬁned as classically as possible. 3) Four-valued semantics is semantically weaker than classical semantics (the syllogism does not hold under four-valued entailment). So if we adopt four-valued semantics for roles, then we have {R S, R(a, b)} |=4 S(a.b) even though there is no contradiction in the precondition.

The paper is structured as follows. We ﬁrst review brieﬂy the four-valued semantics for ALC in Section 2. Then we study the four-valued semantics for expressive description logics in Section 3 and four-valued semantics for tractable description logics in Section 4, respectively. We conclude and discuss future work in Section 5.

2 Preliminaries

2.1 The Four-valued Semantics for ALC We describe the syntax and semantics of four-valued description logic ALC4 [8]. Syntactically, ALC4 hardly differs from ALC. Complex concepts and assertions are dened in exactly the same way. For class inclusion, however, signiﬁcant effort has been devoted on the intuitions behind these different implications in [8]. We claim that various inclusion axioms provide ﬂexible ways to model inconsistent ontologies. They are

**as follows:**

C → D (material inclusion axiom), C D (internal inclusion axiom), C → D (strong inclusion axiom).

Semantically, interpretations map individuals to elements of the domain of the interpretation, as usual. For concepts, however, modiﬁcations are made to the notion of interpretation in order to allow for reasoning with inconsistencies.

Table 1. Semantics of ALC4 Concepts

Intuitively, in four-valued logic we need to consider four situations which can occur in terms of containment of an individual in a concept: (1) we know it is contained, (2) we know it is not contained, (3) we have no knowledge whether or not the individual is contained, (4) we have contradictory information, namely that the individual is both contained in the concept and not contained in the concept. There are several equivalent ways how this intuition can be formalised, one of which is described in the following.

For a given domain ∆I and a concept C, an interpretation over ∆I assigns to C a pair P, N of (not necessarily disjoint) subsets of ∆I. Intuitively, P is the set of elements known to belong to the extension of C, while N is the set of elements known to be not contained in the extension of C. For simplicity of notation, we deﬁne functions proj+ (·) and proj− (·) by proj+ P, N = P and proj− P, N = N.

Formally, a four-valued interpretation is a pair I = (∆I, ·I ) with ∆I as domain, where ·I is a function assigning elements of ∆I to individuals, and subsets of (∆I )2 to concepts, such that the conditions in Table 1 are satisﬁed. Note that the semantics of roles here remains unchanged from the classical two-valued case. Intuitively, inconsistencies always rise on concepts, and not on roles, at least in the absence of role negation, which is often assumed when studying DLs. We will see in this paper that this approach can be used to tolerate inconsistency, not only for ALC but also for more expressive description logics. This is an improvement over [8] in the sense that we would like to make as few changes as possible when extending the classical semantics to a four-valued semantics for handling inconsistency.

The semantics of the three different types of inclusion axioms is formally deﬁned in Table 2 (together with the semantics of concept assertions). we refer to [8] for details.

We say that a four-valued interpretation I satisﬁes a four-valued knowledge base O (i.e. is a model of it) iff it satisﬁes each assertion and each inclusion axiom in O. A knowledge base O is satisﬁable (unsatisﬁable) iff there exists (does not exist) such a model.

Table 2. Semantics of inclusion axioms in ALC4

2.2 Reduction from Four-valued Semantics of ALC to Classical Semantics It is a pleasing property of ALC4 that it can be translated easily into classical ALC, such that paraconsistent reasoning can be simulated by using standard ALC reasoning algorithms.

Deﬁnition 1 (Concept transformation) For any given concept C, its transformation π(C) is the concept obtained from C by the following inductively deﬁned transformation.

= A for A an atomic concept, then π(C) = A+, where A+ is a new concept;

– If C – If C = ¬A for A an atomic concept, then π(C) = A, where A is a new concept;

– If C =, then π(C) = ;

– If C = ⊥, then π(C) = ⊥;

– If C = E D for concepts D, E, then π(C) = π(E) π(D);

– If C = E D for concepts D, E, then π(C) = π(E) π(D);

– If C = ∃R.D for D a concept and R is a role, then π(C) = ∃R.π(D);

– If C = ∀R.D for D a concept and R is a role, then π(C) = ∀R.π(D);

– If C = ¬¬D for a concept D, then π(C) = π(D);

– If C = ¬(E D) for concepts D, E, then π(C) = π(¬E) π(¬D);

– If C = ¬(E D) for concepts D, E, then π(C) = π(¬E) π(¬D);

– If C = ¬(∃R.D) for D a concept and R is a role, then π(C) = ∀R.π(¬D);

– If C = ¬(∀R.D) for D a concept and R is a role, then π(C) = ∃R.π(¬D);

Based on this, axioms are transformed as follows.

Deﬁnition 2 (Axiom Transformations) For any ontology O, π(O) is deﬁned as the set {π(α) | α is an axiom of O}, where π(α) is the transformation performed on each

**axiom deﬁned as follows:**

– π(α) = ¬π(¬C1 ) π(C2 ), if α = C1 → C2 ;

– π(α) = π(C1 ) π(C2 ), if α = C1 C2 ;

– π(α) = {π(C1 ) π(C2 ), π(¬C2 ) π(¬C1 )}, if α = C1 → C2 ;.

– π(C(a)) = π(C)(a), π(R)(a, b) = R(a, b), where a, b are individuals, C1, C2, C are concepts, R a role.

We note two issues. First of all, the transformation algorithm is linear in the size of the ontology. Secondly, for any ALC ontology O, π(O) is still an ALC ontology.

Based on these two observations as well as the following theorem, we can see that paraconsistent reasoning of ALC can indeed be simulated on standard reasoners by means of the transformation just given.

Theorem 1 For any ontology O in ALC, O is 4-valued unsatisﬁable if and only if π(O) is unsatisﬁable under the classical semantics of ALC.

Deﬁnition 3 Given a knowledge base O, the satisﬁable form of O, written SF(O), is a knowledge base obtained by replacing each occurrence of ⊥ in O with Anew ¬Anew, and replacing each occurrence of in (O) with with Anew ¬Anew, where Anew is a new atomic concept.

3 Paraconsistent Semantics for Expressive DLs In this section, we study how to extend four-valued semantics to SHIQ.

For the conﬂicting assertion set {≥ (n + 1)R.C(a), ≤ nR.C(a)}, intuitively, it is caused by the contradiction that there should be less than n different individuals related to a via the R relation, and also there should be more than n + 1 different individuals related to a via R. That is, the contradiction is from the set of individuals of concept C which relate a via R. By this idea, we extend the four-valued semantics to the constructors for number restrictions in Table 3. We remark that the semantics of roles is just the classical semantics. So the semantics for role inclusion and transitive role axiom are still classical.

Table 3. Four-valued Semantics Extension to Number Restrictions and Nominals

Example 1 Consider {≥ 2hasStu.P hD(Green), ≤ 1hasStu.P hD(Green)} which says the conﬂicting facts that Green has at least two and at most one PhD student. Consider a 4-interpretation: I = (∆I, ·I ) where ∆I = {a1, a2, b1, b2, Green}, P hDI = {a1, b1 }, {b1, b2, a2 }, and hasStuI = {(Green, a1 ), (Green, a2 ), (Green, b1 ), (Green, b2 )}.

According to Table 3, we can see that I is a 4-model because (≥ 2hasStu.P hD(Green))I = (≤ 1hasStu.P hD(Green))I = B by checking Green ∈ {x | #(y.(x, y) ∈ hasStuI ∧ y ∈ proj+ (P hDI )) ≥ 2}, Green ∈ {x | #(y.(x, y) ∈ hasStuI ∧ y ∈ proj− (P hDI )) 2}.

That is, the conﬂicting assertions are assigned the contradictory truth value B under their 4-model I.

For the extended four-valued semantics deﬁned in Table 3, we have following properties hold as under classical semantics.

Proposition 2 Let C be a concept and R be an object role name. For any fourvalued interpretation I deﬁned satisfying Table 3, we have

Proposition 2 and Proposition 3 show that many intuitive relations between different concept constructors still hold under the four-valued semantics, which is one of nice properties of our four-valued semantics for handling inconsistency.

Next proposition shows that our deﬁnition of four-valued semantics for SHIQ is enough to handle inconsistencies in an SHIQ knowledge base.

Proposition 4 For any SHIQ knowledge base O, SF(O) always has at least one 4-valued model, where SF(·) operator is deﬁned in Deﬁnition 3.

Note that unqualiﬁed number restrictions, ≥ n.R and ≤ n.R are special forms of number restrictions because of the equations ≤ n.R =2 ≤ nR. and ≥ n.R =2 ≥ nR.. However, if we deﬁned the four-valued semantics of ≤ n.R(≥ n.R) by the fourvalued semantics of ≤ nR. (≥ nR. ) deﬁned in Table 3 and Table 1, we would ﬁnd that {≤ n.R(a), ≥ n+1.R(a)} is still an unsatisﬁable set. This is because #(y.(a, y) ∈ proj(RI ) ∧ y ∈ proj+ ( I )) ≥ n + 1 and #(y.(a, y) ∈ proj(RI ) ∧ y ∈ proj− ( I )) ≤ n cannot hold simultaneously since I = ∆I, ∅.

To address this problem, we also adopt the substitution deﬁned by Deﬁnition 3. By substituting by Anew ¬Anew in ≥ (n + 1)R. and ≤ nR., we can see that {≤ n.R(a), ≥ n + 1.R(a)} has a four-valued model with ∆I = {a, b1,..., bn+1 }, (a, bi ) ∈ RI for 1 ≤ i ≤ n + 1, and AI = ∆I, ∆I. By doing this, we get a four-valued new model I which pushes the contraction onto the new atomic concept Anew.

Next we study how to extend the reduction algorithm to the case of four-valued semantics of SHIQ.

Deﬁnition 4 (Deﬁnition 1 extended) For any given concept C, its transformation π(C) is the concept obtained from C by the following inductively deﬁned transformation.