
| glb[(a, b):R, ǫ1]   | =   | 0.5   |
|---------------------|-----|-------|
| glb[b:C, ǫ2]        | =   | 0.2   |
| glb[b:D, ǫ3]        | =   | 0.3   |
| glb[(a, x):R, ǫ4]   | =   | 0.7   |
| glb[x:D, ǫ5]        | =   | 0.7   |
| glb[x:C, ǫ6]        | =   | 0.4   |

Therefore, we can freely choose ǫ2, ǫ4 and ǫ5, whereas ǫ3 and ǫ6 have to be such **that**
0.3 ≤ 0.5 − ǫ3 and 0.4 ≤ 0.5 − ǫ6. As both h(a, b):R ≥ 0.5i and ha:∀R.C ≥ 0.4i are in S1, while hb:C ≥ 0.4i 6∈ S1, we have the additional restriction on the choice of ǫ1 **(see**
Equation 24) that glb[(a, b):R, ǫ1] ≤ 0.6. But, glb[(a, b):R, ǫ1] = 0.5 ≤ 0.6, for every ǫ1 **and,**
thus, the choice of ǫ1 is also free. A solution to the ǫi is e.g. ǫi = 0.1 and, thus, let I be the following **interpretation:**

$$\begin{array}{r l}{={}}&{{}0.5-\epsilon_{3}}\\ {={}}&{{}1}\\ {={}}&{{}1}\\ {={}}&{{}0.5-\epsilon_{6}.}\end{array}$$

| lub[(a, b):R, ǫ1]   | =   | 1         |
|---------------------|-----|-----------|
| lub[b:C, ǫ2]        | =   | 1         |
| lub[b:D, ǫ3]        | =   | 0.5 − ǫ3  |
| lub[(a, x):R, ǫ4]   | =   | 1         |
| lub[x:D, ǫ5]        | =   | 1         |
| lub[x:C, ǫ6]        | =   | 0.5 − ǫ6. |

1. the domain ∆Iis the set {a, b, x};
2. w I = w, for all w ∈ ∆I;

```
3. ⊤I(w
         I
         ) = 1 and ⊥
                           I
                           (w
                                I
                                ) = 0, for all w ∈ ∆I;
4. C
 I(b) = 0.2, DI(b) = 0.3, DI(x) = 0.7 and C
                                                                I
                                                                (x) = 0.4 (in all other cases, AI(w) =
   0); and

```

5. RI(a, b) = 0.5 and RI(a, x) = 0.7 (in all other **cases,** R′I(w, w
′
) = 0).

Now, it is easily verified that I satisfies S1 and S. ✷
From a computational complexity point of view, the fuzzy entailment problem can be **proven**
to be a PSPACE-complete problem, as is the classical entailment **problem.**
Proposition 4 Let Σ be a fuzzy KB and let ψ be a fuzzy assertion. Determining **whether**
Σ|≈ψ is a PSPACE-complete **problem.** ⊣
Proof: We have seen that termination of the above algorithm is guaranteed. **Additionally,**
for a crisp KB K, define ΣK = {hα ≥ 1i : α ∈ K}. By definition, each ψ ∈ ΣK is KBnormalised and hα ≥ 0.5i is query-normalised. Then from Proposition 2 it follows **that**
K |= α iff ΣK|≈hα ≥ 0.5i. From the PSPACE-completeness of the entailment **problem** in crisp ALC (Schmidt-Schauß & Smolka, 1991), PSPACE-hardness of the fuzzy **entailment**
problem follows. Unfortunately, our algorithm, as it is, requires exponential space due a well know problem inherited from the crisp case. Indeed, it easily verified that a **completion**
of S = {x:C}, where C is the **concept**

## (∃R.A11) ⊓ (∃R.A12) ⊓ ∀R.((∃R.A21) ⊓ (∃R.A22) ⊓ . . . ∀R.((∃R.An1) ⊓ (∃R.An2)). . .)

contains at **least** 2 n + 1 variables. In order to require polynomial space, **Schmidt-Schauß**
and Smolka (1991) introduced the so-called trace rule (T∃) for the ∃ operator. The (T∃)
rule modifies the (∃) rule as shown **below.**

$\square$