A Tractable Paraconsistent Fuzzy Description Logic

Abstract

In this paper, we introduce the tractable pf -EL++ logic, a paraconsistent version of the fuzzy logic f -EL++. Within pf -EL++, it is possible to tolerate contradictions under incomplete and vague knowledge. pf -EL++ extends the f -EL++ language with a paraconsistent negation in order to represent contradictions. This paraconsistent negation is defined under Belnap's bilattices. It is important to observe that pf -EL++ is a conservative extension of f -EL++, thus assuring that the polynomial-time reasoning algorithm used in f -EL++ can also be used in pf -EL++.

-

1 Introduction A difficult task in a knowledge base that aims to formalise a real world application is to deal with incomplete, imprecise and contradictory information. Hence, it is unreasonable to expect that a knowledge base which allows realistic reasoning based on partial knowledge must always be kept logically consistent. In this sense, in the last century, the paraconsistent logics were designed to handle inconsistencies without deriving anything from a contradiction. Here, we are particularly interested in the paraconsistent logic introduced by Belnap [ 3 ]. In addition, there are some logical approaches that attempt to formalise reasoning under incomplete and imprecise knowledge as the fuzzy logic introduced by Zadeh [ 10 ].

Although expressive enough to deal with incomplete, imprecise and contradictory information, the satisfiability problem for paraconsistent and fuzzy logics is undecidable. Since real world applications demand efficient inference systems, a family of logics, the Description Logics (DLs) [ 1 ], have been proposed. DLs are decidable fragments of classical first-order logic, and they have been customarily used in the definition of ontologies and applications for the Semantic Web.

In [ 7 ], a fuzzy logic f -E L++ with a polynomial-time subsumption algorithm was specially defined to deal with imprecise and vague knowledge. Unfortunately, this logic cannot express negative information. In fact, it was proved that the introduction of the classical negation in DLs leads to undecidability [ 2 ].

In this paper, we introduce the tractable pf -E L++ logic, a paraconsistent version of f -E L++ that is able to tolerate contradiction under incomplete and vague knowledge. It extends the f -E L++ language with a paraconsistent negation in order to represent contradictions.

Bilattices In [ 3 ] Belnap introduced a logic intended to deal with inconsistent and incomplete information. This logic is capable of representing four truth values: t (true), f (false), > (overdefined) and ? (underdefined). The underdefined value represents the total lack of knowledge, while the overdefined one represents the excess of knowledge (conflicts between information). Belnap’s logic was generalized by Ginsberg [ 4 ], who introduced the notion of bilattices, which are algebraic structures containing an arbitrary number of truth values simultaneously arranged in two partial orders. In the sequel, we will show the definition of bilattices and introduce the particular billatice employed in the representation of fuzzy truth-values in our proposal: Definition 1 (Complete Bilattice) Given two complete lattices1hC; 1i and hD; 2i, the structure B(C; D)=hC D; k; t; :i is a complete bilattice, in which: hc1; d1i k hc2; d2i if c1 1 c2 and d1 2 d2, hc1; d1i t hc2; d2i if c1 1 c2 and d2 2 d1. Furthermore, : : C D ! D C is a negation operation such that: (1) a k b ) :a k :b, (2) a t b ) :b t :a, (3) ::a = a.

B2 = h[0; 1] [0; 1]; t; k; :i is a complete bilattice where : hx1; x2i = hx2; x1i.

In an element x = hx1; x2i in [0; 1] [0; 1], x1 and x2 represent, respectively, the membership and non-membership degrees of x in [0; 1]. This means that x2 can be any value in [0; 1] and not necessarily 1 x1 as one would expect in the classical case. It is a very important distinction because it will allow us to identify contradictory truth-values. A truth-value x = hx1; x2i is contradictory whenever x1 + x2 > 1. 3

The pf -E L++ Logic Here we propose a new Description Logic, pf -E L++, by extending f -E L++ [ 7 ] with the negation operator :. Motivated by [ 6,5 ], we will employ a bilattice of truth-values to represent the degree of inclusion and non-inclusion of an individual to a concept. The differences between the syntax of pf -E L++ and f -E L++ concepts is that in our proposal we introduce the negation in the alphabet and t and 9 are replaced respectively by k and 9k. Now it is also possible to use negation to concepts and atomic roles: Definition 2 (Concept Semantics) The semantics of pf -E L++ individuals and atomic concepts/roles is given by I = ( I ; :I ), where the domain I is a nonempty set of elements and :I is a mapping function defined by: each individual a 2 NI is mapped to eaaIc2h atoI m;iecacrohleatnoammice cRon2ceNptRniasmmeaApp2edNtoCRisI m:apIped toIA!I :[0; 1I]! [[00;;11]]. [0; 1];

Each atomic concept/role C is mapped to a pair hP; N i, where P; N 2 [0; 1]. Intuitively, P denotes the degree in which an element belongs to C, while N denotes the degree in which it does not belong to C. Note that P +N is not necessarily equal to 1 as in the classical case. We define the functions proj+ hP; N i = P and proj hP; N i = N . Concepts can be interpreted inductively as follows, where for all x 2 I : 1 Let L be a nonempty set and a partial order on L. The pair hL; i is a complete lattice if every subset of L has both a least upper bound and a greatest lower bound according to . Syntax Semantics > >I (x) = h1; 0i ? ?I (x) = h0; 1i :C (:C)I (x) = hN; P i, if CI (x) = hP; N i fag fagI (x) = hh01;; 10ii oifthxer=wiasIe k D (C k D)I (x) = hmin(P1; P2); min(N1; N2)i ;

if CI (x) = hP1; N1i and DI (x) = hP2; N2i 9kR:C (9kR:C)I (x) = h sup (min(proj+(RI (x; y)); proj+(CI (y)))); y2 I sup (min(proj+(RI (x; y)); proj (CI (y)))) i y2 I

The controversial part refers to k and 9k, which were designed in a way that :(C k D)I (x) = (:C k :D)I (x) and :(9kR:C)I (x) = (9kR::C)I (x). Roughly speaking we can understand them as the counterpart in k of conjunction (u) and role restriction (9) respectively. In fact, we can simulate u and 9 presented in f -E L++ respectively as (C u D)I (x) (C k D k >)I (x) and (9R:C)I (x) (9kR:C k >)I (x). The problem is that we cannot introduce them in pf -E L++ language because :(C u D)I (x) = (:C t :D)I (x) and :(9R:C)I (x) = (8R::C)I (x). Then, since our aim is to present a tractable paraconsistent fuzzy extension for E L++, the inclusions of disjunction (t) and universal restriction (8) in E L++ are not allowed. Otherwise, as proved in [ 2 ], the algorithm of decidibility will grow exponentially!

We define the notions of Terminological Box (TBox), Assertional Box (ABox) and ontology in pf -E L++. For now on, consider T1; : : : ; Tk; T refer to atomic roles or the negation of them. The semantics of negation of roles is similar to negation of concepts. Definition 3 (TBox/ABox) A paraconsistent fuzzy TBox in pf -E L++ is a finite set of internal fuzzy inclusion axioms (C @n D), strong fuzzy inclusion axioms (C !n D), internal role inclusion axioms (T1 : : : Tk @ T ) and strong role inclusion axioms (T1 : : : Tk ! T ). A paraconsistent fuzzy ABox in pf -E L++ consists of a finite set of assertion axioms of the form C(a) n and T (a; b) n, where n 2 [0; 1]. Definition 4 (Ontology) An ontology or knowledge base in pf -E L++ is a set composed by a paraconsistent fuzzy TBox and a paraconsistent fuzzy ABox.

The semantics of both paraconsistent fuzzy general concept inclusions, role inclusions, concept assertion and role assertion is given as follows, where for all x; y 2 I : Axiom Name Internal f-GCI Strong f-GCI Internal RIA

Strong RIA Concept assertion

Role assertion

Syntax Semantics C1 @n C2 min(proj+(C1I (x)); n) proj+(C2I (x)) C1 !n C2 min(proj+(C1I (x)); n) proj+(C2I (x)),

min(proj (C2I (x)); n) proj (C1I (x)) T1 : : : Tk @ T proj+([T1I t : : : t TkI ](x; y)) proj+(T I (x; y)) T1 : : : Tk ! T proj+([T1I t : : : t TkI ](x; y)) proj+(T I (x; y)),

proj (T I (x; y)) proj ([T1I t : : : t TkI ](x; y)) C(a) n proj+(CI (aI )) n

T (a; b) n proj+(T I (aI ; bI )) n

Finally, we show the notions of satisfiability and logical consequence in pf -E L++: Definition 5 (Satisfiability) The satisfiability of an axiom by a fuzzy interpretation I , denoted I j= , is defined as I j= C1 vn C2 iff 8x 2 I , min(proj+(C1I (x)); n) proj+(C2I (x)). The notion is similarly applied to the other axioms shown in the table above. I is a model of an ontology O iff I satisfies each axiom of O.

Definition 6 (Logical Consequence) An axiom is a logical consequence of an ontology O, denoted by O j= , iff every model of O satisfies .

Paraconsistency comes to deal with the principle that ; : 6` ?, where is an axiom. Note that in pf -E L++, ? is not logical consequence of and : . For example, consider the axioms (C(a) 0), (:C(a) 0) and (?(a) 1). We have that (C(a) 0); (:C(a) 0) 6` (?(a) 1), because there is an interpretation I (say CI (aI ) = h0; 0i) such that (C(a) 0)I and (:C(a) 0)I are true and (?(a) 1)I is false. 4

Conclusions and Future Works In this paper, we introduced pf -E L++, a paraconsistent extension of the fuzzy description logic f -E L++, that deals with negation on concepts and roles. Inspired in [ 6 ], we can show how to translate pf -E L++ into f -E L++, preserving logical consequence, and under linear time and space in the size of the ontology. Since there is an algorithm for deciding fuzzy concept subsumptions operating in polynomial time [ 8 ], we know that paraconsistency can be simulated by f -E L++ without the loss of tractability.

Regarding future works, we plan to investigate and extend another approach to fuzzy E L, presented by Vojta´s [ 9 ], where conjunction is interpreted as a fuzzy aggregation function rather than fuzzy intersection. Another line of research is to extend tractable DLs to deal with probabilistic and possibilistic knowledge.

References

1. F. Baader . The Description Logic Handbook: theory, implementation, and applications . Cambridge University Press, 2003 .

2. F. Baader , S. Brand , and C. Lutz . Pushing the el envelope . In Proc. of IJCAI 2005 , pages 364 - 369 . Morgan-Kaufmann Publishers, 2005 .

3. N. D. Belnap . A useful four-valued logic . In J. Michael Dunn and G . Epstein, editors, Modern Uses of Multiple-Valued Logic , pages 8 - 37 . D. Reidel , 1977 .

4. M. Ginsberg . Multivalued logics: A uniform approach to reasoning in artificial intelligence . Computational Intelligence , 4 : 265 - 316 , 1988 .

5. Y. Ma , P. Hitzler, and Z. Lin . Algorithms for paraconsistent reasoning with owl . In The Semantic Web: Research and Applications. Proceedings of the 4th European Semantic Web Conference, ESWC2007 , pages 399 - 413 . Springer, 2007 .

6. Y. Ma , P. Hitzler, and Z. Lin . Paraconsistent reasoning for expressive and tractable description logics . Proceedings of the 21st International Workshop on Description Logics , 2008 .

7. T. Mailis , G. Stoilos, N. Simou , and G. Stamou . Tractable reasoning based on the fuzzy el ++ algorithm , 2008 .

8. G. Stoilos , G. Stamou, and J. Z. Pan . Classifying fuzzy subsumption in fuzzy-el+ . 21st International Workshop on Description Logics , 2008 .

9. P. Vojta ´s. A fuzzy el description logic with crisp roles and fuzzy aggregation for web consulting . Proc. of the 2nd int. workshop on uncertainty reasoning for the semantic web , 2007 .

10. L.A. Zadeh . Fuzzy sets . Information Control , 8 : 338 - 353 , 1965 .