
```
 Consider a completion S
                        ′ of S. Starting from hα < mi, by applying the rules of inference,
 only
     ∗ marked expressions of type hα
                                  ′ < mi or hα
                                             ′ > 1 − mi can appear in S
                                                                      ′
                                                                      
                                                                        . Furthermore,
 as S is not satisfiable, S
                       ′
                       
                        contains a clash, i.e. the value m is the largest value such that all
 completions S
              ′ of S contain a clash. Let us analyse S
                                                  ′
                                                  
                                                    . As S
                                                         ′
                                                         
                                                           contains a clash, then either
 (i) there is a clash according to Table 1, or (ii) there is a clash according to Table 2. If
 (i) is the case, i.e. there is ψ ∈ S
                                ′ which is a clash, then we have to distinguish between
 two cases: (a) ψ is not marked with
                                   ∗ and (b) ψ is marked with
                                                             ∗
                                                             
                                                               . In the former case, S
                                                                                    ′
                                                                                    
 contains a clash independently of the value m and, thus, the largest possible value m for
 which S
      ′contains a clash is 1. In the latter case, as m > 0, either ψ = hw:⊥ > 1 − mi or
ψ = hw:⊤ < mi which are both clashes for any value of m. As a consequence, the largest
 possible value m for which S
                           ′
                           
                             contains a clash according to Table 1 is 1. Assume (ii) is the
 case, i.e. a conjugated pair of fuzzy constraints ψ and ψ
                                                    ′
                                                    is in S
                                                            ′
                                                            
                                                             . Similarly to the previous
 case, we have to distinguish the cases for which ψ and ψ
                                                    ′ are marked with
                                                                     ∗
                                                                     
                                                                       . There are four
 cases:
     
    (a) ψ = hα ≥ ki and ψ
                           ′ = hα
                                 ′ ≤ k
                                      ′
                                      i are in S
                                                ′
                                                
                                                 , none is marked with
                                                                       ∗ and k > k
                                                                                    ′
                                                                                    
                                                                                    .
                                                                                    
 Therefore, S
            ′
            
              contains a clash for any value of m and, thus, the largest choice is 1;
    (b) ψ = hα ≥ ki and ψ
                          ′ = hα
                                ′ < mi are in S
                                               ′
                                               
                                                , only ψ
                                                       ′
                                                       is marked with
                                                                       ∗ and k ≥ m.
 Therefore, S
            ′
            
              contains a clash for any value of m ≤ k and, thus, the largest choice for m is
 k. It is easily verified by case analysis on the rules that from ψ ∈ S
                                                               ′
                                                               
                                                                , k ∈ NΣ follows;

(c) ψ = hα ≤ ki and ψ
                           ′ = hα
                                  ′ > 1 − mi are in S
                                                          ′
                                                          
                                                            , only ψ
                                                                     ′
                                                                     is marked with
                                                                                         ∗ and k ≤ 1−m.

  Therefore, S
              ′
              
                contains a clash for any value of m ≤ 1 − k and, thus, the largest choice for
m is 1 − k. It is easily verified by case analysis on the rules that from ψ ∈ S
                                                                              ′
                                                                              
                                                                               , 1 − k ∈ NΣ
  follows;

(d) ψ = hα < mi and ψ
                         ′ = hα
                                ′ > 1 − mi are in S
                                                     ′
                                                     
                                                       , both are marked with
                                                                                ∗ and m ≤ 1−m.

```

Therefore, S
′

contains a clash for any value of m ≤ 0.5 and, thus, the largest choice for m is 0.5.

Summing up, we have proved that the largest possible value for m is such **that** m ∈
NΣ. ✷

The algorithms computing glb(Σ, α) and lub(Σ, α) are described in Table 3. For **instance,**
by a binary search on NΣ, the value of glb(Σ, α) can be determined in at most log |NΣ| fuzzy entailment **tests.**

## 6. Conclusions And Future **Work**

In this work, we have presented a quite general fuzzy extension of the DL ALC, a **significant**
and expressive representative of the various DLs. Our fuzzy DL enables us to **reason** in presence of imprecise ALC concepts, i.e. fuzzy ALC concepts. From a semantics **point** of view, fuzzy concepts are interpreted as fuzzy sets i.e. given a concept C and an **individual**
a, C(a) is interpreted as the truth-value of the sentence "a is C". From a syntax **point** of view, we allow to specify lower and upper bounds of the truth-value of C(a). **Complete**
algorithms for reasoning in it have been presented, that is, we have devised algorithms for solving the entailment problem, the subsumption problem as well as the best **truth-value**
bound **problem.**