Fuzzy Description Logics (DLs) are a formalism for the representation of structured knowledge a ected by imprecision or vagueness. In the setting of fuzzy DLs, restricting to a nite set of degrees of truth has proved to be useful. In this paper, we propose nite fuzzy DLs as a generalization of existing approaches. We assume a nite totally ordered set of linguistic terms or labels, which is very useful in practice since expert knowledge is usually expressed using linguistic terms. Then, we consider any smooth t-norm de ned over this set of degrees of truth. In particular, we focus on the nite fuzzy DL ALCH, studying some logical properties, and showing the decidability of the logic by presenting a reasoning preserving reduction to the non-fuzzy case.
It has been widely pointed out that classical ontologies are not appropriate
to deal with imprecise and vague knowledge, which is inherent to several
realworld domains. Since fuzzy logic is a suitable formalism to handle these types
of knowledge, there has been an important interest in generalize the formalism
of Description Logics (DLs) [
It is well known that di erent families of fuzzy operators (or fuzzy logics)
lead to fuzzy DLs with di erent properties [
In fuzzy DLs, some fuzzy operators imply logical properties which are usually
undesired. For instance, in Zadeh fuzzy logic concepts and roles do not fully
subsume themselves [
Assuming a nite set of degrees of truth is useful in the setting of fuzzy
DLs, [
There is a recent promising line of research that tries to ll the gap between
mathematical fuzzy logic and fuzzy DLs [
Instead of dealing with degrees of truth in [0; 1], as usual in fuzzy DLs, we will assume a nite (totally ordered) set of linguistic terms or labels. For instance, N = ffalse; closeToFalse; neutral; closeToTrue; trueg. This makes possible to abstract from the numerical interpretations of these labels.
The use of linguistic labels as degrees in fuzzy DLs has already been
proposed. U. Straccia proposed to take the degrees from an uncertainty lattice [
The bene ts of this paper are two-fold: rstly, since experts' knowledge is
usually expressed using a set of linguistic terms [
The remainder is organized as follows. Section 2 includes some preliminaries on nite fuzzy logics. Then, Section 3 de nes a fuzzy extension of the DL ALCH based on nite fuzzy logics and discusses some logical properties. Section 4 shows the decidability of the logic by providing a reduction of fuzzy ALCH into crisp ALCH. Finally, Section 5 sets out some conclusions and ideas for future research. 2
Fuzzy set theory and fuzzy logic were proposed by L. Zadeh [
Let X be a set of elements called the reference set, and let S be a totally ordered scale with e as minimum element and u as maximum. A fuzzy subset A of X is de ned by a membership function A(x) : X ! S which assigns any x 2 X to a value in S. Similarly as in the classical case, e means no-membership and u full membership, but now a value between them represents to which extent x can be considered as an element of X.
All crisp set operations are extended to fuzzy sets. The intersection, union, complement and implication are performed by a t-norm function, a t-conorm function, a negation function, and an implication function, respectively.
In the following, we consider nite chains of degrees of truth [
In the rest of the paper, we will use the following notion: N + = N n f 0g, + i = i+1, i = i 1. Let us also denote by [ i; j ] the nite chain given by the subinterval of all k 2 N such that i k j.
T-norms, t-conorms, negations and implications can be restricted to nite chains. Table 1 shows some popular examples: Zadeh, Godel, and Lukasiewicz.
The smoothness condition is a discrete counterpart of continuity on [0; 1]. A function f : N ! N is smooth i it satis es the following condition for all i 2 N + f ( i) = j implies that f ( i 1) = k with j 1 k j + 1. A binary operator is smooth when it is smooth in each place.
A t-norm on N is a function : N 2 ! N satisfying commutativity, associativity, monotonicity, and some boundary conditions. Smoothness for t-norms is equivalent to the divisibility condition in [0; 1], i.e., i j if and only if there exists k 2 N such that j k = i. A t-norm is Archimedean i 8 1; 2 2 N n f 0; pg there is n 2 N such that 1 1 1 (n times) < 2. Proposition 1. There is one and only one Archimedean smooth t-norm on N given by i j = maxf0;i+j pg. Moreover, given any subset J of N containing 0; p, there is one and only one smooth t-norm J on N that has J as the set of idempotent elements. In fact, if J is the set J = f0 = i0 < i1 < < im 1 < im = 1g such a t-norm is given by: i
J j = maxfik;i+j ik+1g if i; j 2 [ik; ik+1] for some 0 minfi;jg otherwise k m 1
Note that the Archimedean smooth t-norm happens with J = f 0; pg, and that the minimum happens with J = N . It is worth to note that, as a consequence of Proposition 1, a nite smooth product t-norm is not possible. Example 1. Given the nite chain N = f 0; 1; 2; 3; 4; 5g and the set J = f 0; 3; 5g, J is de ned as:
A negation function on N is strong if it veri es ( is only one strong negation on N and it is given by
Given a smooth t-norm and the strong negation t-conorm , as the function satisfying i j = (( ) = ; 8 2 N . There i = p i , we can de ne the dual i) ( j )).
Proposition 2. There is one and only one Archimedean smooth t-conorm on N given by i j = minfp;i+jg. Moreover, given any subset J of N containing 0; p, there is one and only one smooth t-conorm J on N that has J as the set of idempotent elements. In fact, if J is the set J = f0 = i0 < i1 < < im 1 < im = 1g such a t-conorm is given by: i
J j = minfik+1;i+j ikg if i; j 2 [ik; ik+1] for some 0 maxfi;jg otherwise k m 1
Note that the Archimedean smooth t-conorm happens with J = f 0; pg, and that the maximum happens with J = N .
A binary operator ): N 2 ! N is said to be an implication, if it is nonincreasing in the rst place, non-decreasing in the second place, and satis es some boundary conditions.
Given a smooth t-norm and the strong negation , an S-implication )s is the function satisfying i )s j = ( i ( j)) = ( i) j. Proposition 3. Let J : N 2 ! N be a smooth t-norm with J = f0 = i0 < i1 < < im 1 < im = 1g. Then, the implication )s is given by: i )s j = minfp ik;ik+1+j ig if 9 ik 2 J such that ik maxfp i;jg otherwise i; p j ik+1
The Kleene-Dienes implication happens with the minimum t-norm, and the Lukasiewicz implication happens with the Archimedean t-norm.
Given a smooth t-norm , an R-implication )r can be de ned as i )r j = maxf k 2 N j( i k) jg, for all i; j 2 N .
Proposition 4. Let J : N 2 ! N be a smooth t-norm with J = f0 = i0 < i1 < < im 1 < im = 1g. Then, the implication )r is given by: i )r j = 8< p if i j
ik+1+j i if 9 ik 2 J such that ik : j otherwise j < i ik+1 Example 2. Given the t-norm in Example 1, )r is de ned as follows, where the rst column is the antecedent and the rst row is the consequent:
Godel implication happens with the minimum t-norm, and the Lukasiewicz implication happens with the Archimedean t-norm.
A QL-implication is an implication verifying i ) j = ( i) ( i j). Proposition 5. Let : N 2 ! N be a smooth t-norm. The operator i ) j = ( i) ( i j ) is a QL-implication i is the Archimedean smooth t-conorm. Moreover, in this case, i )ql j = p i+z for all i; j 2 N , where z = i j .
Proposition 6. Let J : N J N ! N be a smooth t-norm with J = f0 = i0 < i1 < < im 1 < im = 1g. Then, the implication )ql is given by: i )ql j = 8< pmaix+fpj i+ik;p+j ik+1g iiff ij; j i2k [ik; iikf+o1r] sfoomresoimke20J : p otherwise k m 1
The Lukasiewicz implication happens with the minimum t-norm, and the KleeneDienes implication happens with the Archimedean t-norm (note the difference with respect to S-implications).
Interestingly, )s and )ql are smooth if and only if so is , but the smoothness condition is not preserved in general for R-implications.
Finally, we can also de ne D-implications. The name is due to the equivalence to the Dishkant arrow in orthomodular lattices. Note that D-implication are sometimes called NQL-implication. A D-implication is an implication satisfying i ) j = (( i) ( j )) j for all i; j 2 N . However, QL-implications and D-implications on N actually coincide. Given a set J and J = f p xj x 2 J g, then )ql J is equivalent to )d J .
The notions of fuzzy relation, inverse relation, composition of relations, reexivity, symmetry and transitivity can trivially be restricted to N . 3
In this section we de ne fuzzy ALCH, a fuzzy extension of ALCH where:
{ Concepts denote fuzzy sets of individuals.
{ Roles denote fuzzy binary relations.
{ Degrees of truth are taking from a nite chain N .
{ Axioms have a degree of truth associated.
{ The fuzzy connectives used are a smooth t-norm on N , the strong negation
on N , the dual t-conorm , and the implications )s ; )r ; )ql .
In this paper, we will assume the reader to be familiar with classical DLs (for
details, we refer to [
De nition Notation. In the rest of this paper, C; D are (possibly complex) concepts, A is an atomic concept, R is a role, a; b are individuals, ./ 2 f ; <; ; >g, C 2 f ; >g, B 2 f ; <g. We will also use to denote semantical equivalence, and we will not write in the subscripts of the implications.
Syntax. Finite fuzzy ALCH assumes three alphabets of symbols, for concepts, roles and individuals. A Fuzzy Knowledge Base (KB) contains a nite set of axioms organized in a fuzzy ABox A (axioms about individuals), a fuzzy TBox T (axioms about concepts), and a fuzzy RBox T (axioms about roles).
The syntax of fuzzy concept, roles, and axioms are shown in Table 2. Note that in fuzzy ALCH, all fuzzy roles are atomic.
Remark 1. As opposed to the crisp case, there are three types of universal restrictions, fuzzy GCIs, and fuzzy RIAs. In fact, the di erent subscripts s, r, and ql denote an S-implication, R-implication, and QL-implication, respectively. Semantics. A fuzzy interpretation I is a pair ( I ; I ) where I is a non empty set (the interpretation domain) and I is a fuzzy interpretation function mapping (i) every individual a onto an element aI of I , (ii) every concept C onto a function CI : I ! N , and (iii) every role R onto a function RI : I I ! N . The fuzzy interpretation function is extended to fuzzy complex concepts and axioms as shown in Table 2.
CI denotes the membership function of the fuzzy concept C with respect to the fuzzy interpretation I. CI (x) gives us the degree of being x an element of the fuzzy concept C under I. Similarly, RI denotes the membership function of the fuzzy role R with respect to I. RI (x; y) gives us the degree of being (x; y) an element of the fuzzy role R.
Remark 2. Note an important di erence with previous work in fuzzy DLs.
Usually, I maps every concept C onto a function CI : I ! [0; 1], and every
role R onto RI : I I ! [0; 1]. Consequently, a fuzzy KB fha : C >
0:5i; ha : C < 0:75g is satis able, by taking CI (a) 2 (0:5; 0:75). But now,
given N = ffalse; closeToFalse; neutral; closeToTrue; trueg, a fuzzy KB
fha : C > closeToFalsei; ha : C < neutralg is not satis able, since CI (a) 2 N .
Witnessed models. In order to correctly manage in ma and suprema in the
reasoning, we need to de ne the notion of witnessed interpretations [
{ Fuzzy KB satis ability. A fuzzy interpretation I satis es (is a model of) a
fuzzy KB K = hA; T ; Ri i it satis es each element in A, T and R.
{ Concept satis ability. C is -satis able w.r.t. a fuzzy KB K i K [ fha : C
ig is satis able, where a is a new individual, which does not appear in K.
{ Entailment. A fuzzy concept assertion ha : C ./ i is entailed by a fuzzy
KB K (denoted K j= ha : C ./ i) i K [ fha : C : ./ ig is unsatis able.
Furthermore, K j= h(a; b) : R i i K [ fhb : B pig j= ha : 9R:B i,
where B is a new concept.
{ Greatest lower bound. The greatest lower bound of a concept or role assertion
is de ned as the supf : K j= h ig. It can be computed performing at
most log jN j entailment tests [
Proposition 7. Finite fuzzy ALCH interpretations coincide with crisp interpretations if we restrict the membership degrees to f 0 = 0; p = 1g.
The following properties are extensions to a nite chain N of properties for
Zadeh fuzzy DLs [
In this section we show how to reduce a fuzzy KB into a crisp KB. The procedure is satis ability-preserving, so existing DL reasoners could be applied to the resulting KB. The basic idea is to create some new crisp concepts and roles, representing the -cuts of the fuzzy concepts and relations, and to rely on them. Next, some new axioms are added to preserve their semantics and nally every axiom in the ABox, the TBox and the RBox is represented, independently from other axioms, using these new crisp elements.
Before proceeding formally, we will illustrate this idea with an example. Example 3. Consider the smooth t-norm on N used in Example 1, and let us compute some -cuts of the fuzzy concept A1 u A2 (denoted (A1 u A2; )).
To begin with, let us consider = 2. By de nition, this set includes the elements of the domain x satisfying A1I (x) A2I (x) 2. There are two possibilities: (i) A1I (x) 2 and A2I (x) 3, or (ii) A1I (x) 3 and A2I (x) 2. Hence, (A1 u A2; 2) = (A1; 2) u (A2; 3) t (A1; 3) u (A2;
Now, let us consider = 3. Now, there is only one possibility: A1I (aI ) and A2I (aI ) 3. Hence, (A1 u A2; 3) = (A1; 3) u (A2; 3). Let A be the set of atomic fuzzy concepts and R the set of atomic fuzzy roles in a fuzzy KB K = hA; T ; Ri, respectively. For each 2 N +, for each A 2 A, a new atomic concepts A is introduced. A represents the crisp set of individuals which are instance of A with degree higher or equal than i.e the -cut of A. Similarly, for each R 2 R, a new atomic role R is created.
Remark 4. The atomic elements A 0 and R 0 are not considered because they
are always equivalent to the > concept. Also, as opposite to previous works [
The semantics of these newly introduced atomic concepts and roles is preserved by some terminological and role axioms. For each 1 i p 1 and for each A 2 A, T (N ) is the smallest terminology containing these axioms: A i+1 v A i . Similarly, for each RA 2 R, R(N ) is the smallest terminology containing these axioms: R i+1 v R i .
Remark 5. Again, note that the number of new axioms needed here is less than
the number needed in similar works [
Mapping Fuzzy Concepts, Roles and Axioms Fuzzy concept and role expressions are reduced using mapping , as shown in the top part of Table 3. Given a fuzzy concept C, (C; ) is a crisp set containing all the elements which belong to C with a degree greater or equal than . The other cases (C; ./ ) are similar. is de ned in a similar way for fuzzy roles. Furthermore, axioms are reduced as in the bottom part of Table 3, where ( ) maps a fuzzy axiom in nite fuzzy ALCH into a set of crisp axioms in ALCH.
The reduction of the conjunction considers every pair x; y 2 ( ik ; ik+1 ] such that 2 ( ik ; ik+1 ], and x + y = ik+1 + z, with = z. Note that the reduction does not consider a closed internal of the form [ ik ; ik+1 ]. The reason is that, if is idempotent and we set ik+1 = , the result is correct ( x = y = ). However, setting ik = would yield an incorrect result. Similarly, the reduction of the disjunction also considers a closed interval.
When dealing with R-implications and QL-implications, we consider optimal pairs of elements, to get e cient representation that avoids super uous elements. De nition 1. Let ) be an implication in N , and let x; y 2 N +. ( x; y) is a () )-optimal pair i (i) x ) y , (ii) there are no x0; y0 2 N + such that x0 ) y0 , and such that either x0 < x or y0 < y.
De nition 2. Let ) be an implication in N , and let x 2 N +; y 2 N . ( x; y) is a () )-optimal pair i (i) x ) y , (ii) there are no x0; y0 2 N + such that x0 ) y0 , and such that either x0 < x or y0 > y.
Example 4. Given the R-implication in Example 2, the () 3 )-optimal pairs are ( 3; 3), ( 2; 2), and ( 1; 1); and the () 3 )-optimal pairs are ( 5; 3), ( 3; 2), ( 2; 1), and ( 1; 0).
Note that R-implications are, in general, non smooth (see Example 2). Hence, a pair of elements 1; y such that x )r y = might not exist, and thus we have to consider an inequality of the form x )r y . In QL-implications, due to the optimality condition, = and yield the same result. (>; ) (>; ) (?; ) (?; ) (A; ) (A; ) (:C; ./ ) (C u D; (C u D; (C t D; (C t D; (9R:C; (9R:C; (8sR:C; (8sR:C; (8rR:C; (8rR:C; (8qlR:C; (8qlR:C; ) ) ) ) ) ) ) ) ) ) ) ) (R; ) (R; ) (ha : C ./ i) (h(a; b) : R ./ i) (hC vs D i) (hC vr D (hC vql D (hR1 vs R2 (hR1 vr R2 (hR1 vql R2 i) i) i) i) i) (A) (resp. (T ), (R)) denotes the union of the reductions of every axiom in A (resp. T , R). crisp(K) denotes the reduction of a fuzzy KB K. A fuzzy KB K = hA; T ; Ri is reduced into a KB crisp(K) = h (A); T (N ) [ (T ); R(N ) [ (R)i. Correctness. The following theorem, showing the logic is decidable and that the reductions preserves reasoning, can be shown.
Theorem 1. The satis ability problem in nite fuzzy ALCH is decidable.
Furthermore, a nite fuzzy ALCH fuzzy KB K is satis able i crisp(K) is.
Complexity. In general, the size of crisp(K) is O(jKj jN jk), being k the maximal
depth of the concepts appearing in K. In the particular case of nite Zadeh fuzzy
logic, the size of crisp(K) is O(jKj jN j) [
This paper has set a general framework for fuzzy DLs with a nite chain of degrees of truth N . N can be seen as a nite totally ordered set of linguistic terms or labels. This is very useful in practice, since expert knowledge is usually expressed using linguistic terms and avoiding their numerical interpretations.
Starting from a smooth nite t-norm on N , we de ne the syntax and semantics of fuzzy ALCH. The negation function and the t-conorm are imposed by the choice of the t-norm, but there are di erent options for the implication function. For this reason, whenever this is possible (i.e., in universal restriction concepts and in inclusion axioms), the language allows to use three di erent implications. We have studies some of the logical properties of the logic. This will help the ontology developers to use the implication that better suit their needs.
The decidability of the logic has been shown by presenting a reasoning
preserving reduction to the crisp case. Providing a crisp representation for a fuzzy
ontology allows reusing current crisp ontology languages and reasoners, among
other related resources. The complexity of the crisp representation is higher than
in nite Zadeh fuzzy DLs, because it is necessary to build disjunctions or
conjunctions over all possible degrees of truth. However, Zadeh fuzzy DLs have some
logical problems [
As future work we will study more expressive logics than ALCH, applying the
ideas in the previous work DLs [
F. Bobillo acknowledges support from the Spanish Ministry of Science and Technology (project TIN2009-14538-C02-01) and Ministry of Education (program Jose Castillejo, grant JC2009-00337).