Fuzzy Logics have been applied successfully within both Formal Concept Analysis and Description Logics. Especially in the latter field, Fuzzy Logics have been gaining significant momentum during the last two years. Unfortunately, the research on fuzzy logics within the two communities has been conducted independently from each other, leading to different approaches being pursued. We show that if we look at a restricted variant of fuzzy formal concept analysis, then the differences between the two approaches can be reconciled. Moreover, an implicational base can be computed even when the identity hedge is used.
c 2012 by the paper authors. CLA 2012, pp. 163–174. Copying permitted only for
private and academic purposes. Volume published and copyrighted by its editors.
Local Proceedings in ISBN 978–84–695–5252–0,
Universidad de M´alaga (Dept. Matem´atica Aplicada), Spain.
between fuzzy DL and fuzzy FCA are prominent, the situation is not so clear
in the fuzzy variants of the respective theories. In fuzzy FCA one is allowed to
use fuzzy sets of attributes. In fuzzy DL the same concept descriptions as in
crisp DL are used. They are not fuzzy, only their semantics are. In Section 3 we
identify such differences, that hinder the close cooperation that exists between
the crisp variants of the two fields. We propose simple adjustments to avoid
them. Generally speaking, one can say that the FCA community has been more
ambitious and applied Fuzzy Logics to a much larger extent than fuzzy DL.
Unfortunately, for this reason implication bases, which play an important role
in the cooperation between crisp DL and crisp FCA, can no longer effectively be
computed in the general case [
The restriction to the Gödel t-norm is necessary, since fuzzy FCA uses weak
conjunction for the semantics of attribute sets, while DL uses strong conjunction
for its semantics. The two coincide only for the Gödel t-norm. From a current
DL viewpoint, this is not a severe restriction, since up to now the Gödel t-norm
is the only t-norm for which the standard DL reasoning tasks are known to be
decidable [
Fuzzy Logics represent vague data while maintaining a well-defined semantics.
Instead of using only the two values true and false a scale of truth degrees is used.
In this work we consider only the most typical choice where truth degrees are
values from the real unit interval [
Fuzzy Logics provide several operators to define its semantics. A t-norm ⊗
is a binary operator ⊗ : [
Fuzzy sets are a central idea of Fuzzy Logics. Given a set M a fuzzy (sub-)set
T of M is a function T : M → [
S(T1, T2) = inf T1(x) ⇒ T2(x).
x∈M For finite fuzzy sets we use notation such as {0.5/a, 1/b} to denote the set that contains a with degree 0.5 and b with degree 1. 2.2
The crisp setting We introduce crisp FCA in addition to fuzzy FCA, as we
shall need the crisp version of the Duquenne-Guigues Base in the later sections.
In crisp FCA [
A↑ = {m ∈ M | ∀g ∈ A : (g, m) ∈ I}, B↓ = {g ∈ G | ∀m ∈ B : (g, m) ∈ I}. (2) The two derivation operators ·↑ and ·↓ form an antitone Galois-connection. An implication A → B, where A, B ⊆ M , is said to hold in the context K if A↓ ⊆ B↓. A set of attributes U ⊆ M respects A → B iff A 6⊆ U or B ⊆ U . A → B follows from a set of implications L iff every set U that respects all implications from L also respects A → B.
One way to structure the data in a formal context K is the Duquenne-Guigues
base DG(K) [
B↓(g) = inf m∈M
B(m) ⇒ I(g, m) .
(3) Notice, that the hedge ·∗ is used only for the derivation of fuzzy sets of objects. The operators ·↑ and ·↓ form a Galois connection with hedges.
In fuzzy FCA the implications are also allowed to be fuzzy. A fuzzy
implication is a pair written as A → B where A and B are fuzzy subsets of M . Let U
be a fuzzy subset of M . The degree to which A → B holds in U is defined as
kA → BkU = S(A, U )∗ ⇒ S(B, U )
(4)
The degree to which A → B holds in K is defined as kA → BkK = ming∈G kA →
BkIg , where Ig is the fuzzy set to which each m ∈ M belongs with degree I(g, m).
Let L be a fuzzy set of fuzzy implications. A set U ⊆ M is called a model of L if
kA → BkU ≥ L(A → B) holds for every fuzzy implication A → B. We say that
A → B follows from L to degree q if kA → BkU ≥ q for all models U of L. There
have been several works where the existence of bases for fuzzy implications has
been considered [
For DL we only introduce the fuzzy version. The crisp version only occurs in
a high-level description in Section 3.1. For a formal introduction of crisp DL
we refer to [
In fuzzy E L (in contrast to crisp E L) fuzzy sets are used to interpret both concepts and roles. A fuzzy interpretation I = (∆ I , ·I ) satisfies
AI : ∆ I → [
Most existing works at the intersection of FCA and DL have in common that
they associate FCA attributes and DL concept names. The objects are usually
chosen to be domain elements of an interpretation [
To formalize this connection, for every interpretation I = (∆ I , ·I ) one can define its induced context KI whose set of objects is ∆ I , whose attributes are the concept names and where x ∈ ∆ I and A ∈ NC are incident iff x ∈ AI . For example, we can think of the context in Table 1 as being induced by an interpretation I whose domain are the world’s 8 most populous countries, and where the concept names Populous, Large and Asian are interpreted as PopulousI = {China, India}, LargeI = {China, Russia, US}, and AsianI = {China, India, Indonesia, Pakistan, Russia}.
In the induced context it holds for all sets U ⊆ NC that U ↓ = (d U )I , further supporting the intuition that sets of attributes are treated like conjunctions over attributes. Similarly, for two sets of concept names U, V ⊆ NC the GCI d U ⊑ d V holds in the interpretation I iff the implication U → V holds in the induced context of I. Hence, the notions of dependencies also coincide in crisp FCA and crisp DL. One could even go so far to say that standard formal contexts and the very simple DL that only allows for conjunction are syntactic variants of each other. 3.2
In this section, we analyze the differences between fuzzy FCA and fuzzy DL that hinder a close cooperation like it exists in the crisp setting. First, the semantics of fuzzy FCA do not treat sets of attributes like conjunctions over concept names. Remember that in the crisp setting the exact same semantics are used to compute the derivation of a set of attributes or the interpretation of a conjunction of concept names. This is not true in the fuzzy setting because the infimum (or minimum in the case of finite contexts) is used to interpret attribute sets (2) while the t-norm is used to interpret conjunctions (5).3 In the case of the Gödel t-norm this is completely harmless, as the Gödel t-norm coincides with the minimum. For the other t-norms the difference is relevant.
As an example, assume that Table 2 is obtained from a fuzzy interpretation I by using the domain as objects, concept names as attributes and defining I(x, A) = AI (x) (We could call it the induced fuzzy context of I). If we use the Łukasiewicz t-norm, which is defined as x ⊗ y = max{0, x + y − 1}, then (Populous ⊓ Large)I (US) = 0.23 ⊗ 0.58 = 0 However, in fuzzy FCA with the Łukasiewicz t-norm we obtain
{1/Populous, 1/Large}↓(US) = min{1 ⇒ 0.23, 1 ⇒ 0.58} = 0.23.
Thus, unlike in the crisp case, the fuzzy semantics differ even for crisp sets of attributes such as {1/Populous, 1/Large}.
Second, we can observe that in fuzzy DL concept descriptions on their own are not fuzzy. The interpretations are fuzzy, the axioms are fuzzy, but the concept descriptions themselves are not. By contrast, in fuzzy FCA it is possible to use a fuzzy set of attributes to describe a class of objects.
To describe all countries that are (completely) huge and somewhat Asian, one can use a fuzzy set of attributes {1/Large, 0.5/Asian}. Then in Table 2 the membership of Russia in the derivation {1/Large, 0.5/Asian}↓ is 1. By contrast, in DL it is not possible to associate a truth degree with the concepts in a conjunction. The best approximation of the above attribute set in DL is the simple conjunction Large ⊓ Asian, which has, of course, a different semantics. In fact, Russia belongs to (Large ⊓ Asian)I only with degree 0.75.4 In this respect fuzzy FCA is more expressive than fuzzy DL.
Finally, fuzzy FCA typically uses hedges and fuzzy DL does not. In principle, fuzzy FCA is more general here, since one could treat fuzzy DL as the special 3 Some authors use two types of conjunction: a strong conjunction interpreted by the t-norm and a weak conjunction interpreted by the minimum. In this terminology, we could write that fuzzy DL uses strong conjunction while fuzzy FCA uses weak conjunction. 4 The Gödel t-norm is used to emphasize that this is independent of the first problem. case where identity is used as the hedge. In practice, if identity is used as the hedge, one cannot effectively compute a base in fuzzy FCA, at least not in the settings that have previously been considered.
On the other hand, using globalization in combination with crisp sets of attributes has practical limitations. Consider a fuzzy implication A → B. Using the globalization as the hedge means, that all those counterexamples g ∈ G are ignored that do not satisfy S(A, Ig) = 1. This is particularly problematic, if we only consider crisp left-hand sides A, since then
S(A, Ig) = min (1 ⇒ I(g, m)) = min I(g, m).
m∈A m∈A (6) If for just one m ∈ A the value I(g, m) is not 1 then S(A, Ig) < 1 holds and the object g is ignored. For example, in Table 2 if we consider A = {1/Large, 1/Populous} then all objects are ignored, i.e. any implication with A as its left-hand side holds. Presumably, in many applications values that differ from 1 are the rule rather than the exception, meaning that almost all objects will be ignored. 4
In the previous section we have identified the three aspects in which fuzzy DL and fuzzy FCA disagree. We shall now consider a restricted subset of fuzzy FCA for which the semantics agree. Unfortunately, it is not possible to use strong conjunction instead of weak conjunction in fuzzy FCA, since the derivation operators would no longer form a Galois-connection. Instead, we caution that the following theory can only be applied directly in fuzzy DL with Gödel t-norm.
Since truly fuzzy implications have no equivalent in fuzzy DL, we only
consider implications A → B, where both sets A and B are crisp (from now on
called crisp implications). A similar idea has been proposed under the name of
“one-sided fuzzyness” in [
B), and – irredundant, i.e. no fuzzy set U ( T is complete.
Furthermore, we use identity as the hedge, thereby ensuring both compatibility with DL and the use of all objects as potential counterexamples. These three restrictions – Gödel t-norm, identity as the hedge, only crisp implications – guarantee that A → B holds in the fuzzy induced context K of I to degree q iff hd A ⊑ d B, qi holds in I. This is analogous to the crisp case. 4.1
In [
Let L be a fuzzy subset of {A → B | A, B ⊆ M }. Our axiomatic system consists of the following deduction rules, where q1, q2 are positive truth values. In each deduction step a new fuzzy subset Li+1 is obtained from the previous set Li, where L0 = L. For all implications E → F we define Li+1(E → F ) = Li(E → F ) unless mentioned otherwise in the rules. (Refl) From A ⊆ B and Li(A → B) < 1 infer Li+1(A → B) = 1 (Union) From Li(A → B) = q1, Li(A → C) = q2 and Li(A → B ∪ C) < min{q1, q2} infer Li+1(A → B ∪ C) = min{q1, q2} (Trans) From Li(A → B) = q1, Li(B → C) = q2 and Li(A → C) < q1 ⊗ q2 infer Li+1(A → C) = q1 ⊗ q2.
In each of the three rules the inferred implication obtains a membership degree that is smaller or equal to the membership degrees of the rules in the precondition. Since a rule can only be applied if the degree of the inferred implication strictly increases, no implication can ever be used in its own deduction implicitly or explicitly. There are only finitely many crisp implications and therefore the deduction process must terminate. We now want to show that the deduction system is sound, in the sense that if after a finite number k of deduction steps we can deduce Lk(A → B) = q then A → B follows from L with at least degree q, and complete in the sense that if A → B follows from L with degree q then Lk(A → B) = q can be deduced.
Lemma 1. (Refl)–(Trans) is a sound and complete system of deduction rules. Proof. To prove soundness, we prove that each rule application does not change the models, i.e. that every model U of Li is a model of Li+1. The converse that every model of Li+1 is a model of Li is trivial, since Li ⊆ Li+1. Soundness of (Refl) is also trivial. Soundness of (Union): Assume that U is a model of Li. We define α = minm∈A U (m), β = minm∈B U (m) and γ = minm∈C U (m). From (6) and (4) we obtain kA → BkU = α ⇒ β, kA → CkU = α ⇒ γ, kA → B ∪ CkU = α ⇒ min{β, γ}. Monotonicity of the residuum yields kA → B ∪ CkU = min{α ⇒ β, α ⇒ γ} ≥ min{q1, q2}. This proves that U is also a model of Li+1, which suffices to prove soundness of (Union). Soundness of (Trans): Since U is a model of Li we obtain from the preconditions α ⇒ β ≥ q1 and β ⇒ γ ≥ q2. Using (1) we obtain α⊗q1 ≤ β and β ⊗ q2 ≤ γ. From monotonicity of the t-norm we obtain α ⊗ (q1 ⊗ q2) ≤ γ. Using (1) again we get q1 ⊗ q2 ≤ α ⇒ γ = kA → CkU . Hence, U is a model of Li+1, which proves soundness of (Trans).
Completeness: Let X → Y be an implication that follows (semantically) from L to degree q. Let Lk be the fuzzy set of implications obtained after exhaustively applying the deduction rules. To prove completeness it suffices to show that that Lk(X → Y ) ≥ q.
As a preliminary step, let us define the following fuzzy set X+(m) = Lk(X → {m}) and show that it is a model of L. Assume that X+ is not a model of L, i.e. kA → BkX+ < L(A → B) for some implication A → B. We use the notation α = minm∈A X+(m) and β = minm∈B X+(m). Then kA → BkX+ = α ⇒ β < L(A → B), or equivalently by (1) α ⊗ L(A → B) > β. (7) On the other hand X+(a) = Lk(X → {a}) ≥ α holds for all a ∈ A. Because the rules have been applied exhaustively to obtain Lk (Union) is not applicable to Lk and therefore Lk(X → A) ≥ α. Using a similar argument for (Trans) we obtain
Lk(X → B) ≥ Lk(X → A) ⊗ Lk(A → B) ≥ α ⊗ L(A → B), where we have exploited the fact that truth values can only increase when a rule is applied and therefore L(A → B) ≤ Lk(A → B). Finally, using (Refl) and (Trans) it follows that Lk(X → {b}) ≥ α ⊗ L(A → B) for all b ∈ B. This contradicts (7) and thus X+ must be a model of L.
Since X → Y follows from L to degree q it must hold that q ≤ kX → Y kX+ = min X+(x) ⇒ min X+(y) = min X+(y).
x∈X y∈Y y∈Y Therefore Lk(X → {y}) = X+(y) ≥ q for all y ∈ Y . Since (Union) cannot be applied to Lk we obtain Lk(X → Y ) ≥ q which proves completeness. ⊔⊓ 4.2
We now provide a practical approach for computing a finite base for the Gödel
t-norm, the only t-norm for which the semantics of fuzzy FCA and fuzzy DL
coincide. Assume that we are given a finite fuzzy context K = (G, M, I). Let QK
be the set containing 1 and all truth degrees that occur in K. Let q0 ∈ [
B = L = ∅ for all q ∈ QK in decreasing order do
D = DGB(Kq) B = B ∪ D
L = L ∪ {q/A→B | A → B ∈ D} end for return L Lemma 2. A → B holds in K with at least degree q0 iff A → B holds in Kq0 . Proof. Assume that A → B holds in K with degree less than q0. According to (4) and the definition of the Gödel-residuum this is equivalent to min kA → BkIg < q0 g∈G ⇐⇒ ∃g ∈ G : min I(g, a) ⇒ min I(g, b) a∈A b∈B < q0 ⇐⇒ ∃g ∈ G : min I(g, b) < q0 and min I(g, a) > min I(g, b)
b∈B a∈A b∈B ⇐⇒ ∃g ∈ G : ∃b ∈ B : I(g, b) < q0 and ∀a ∈ A : I(g, a) > I(g, b). (8) I(g, b) is a truth degree from QK and gI(g,b) satisfies (gI(g,b), b) ∈/ Iq0 and (gI(g,b), a) ∈ Iq0 for all a ∈ A. Therefore, Kq0 contains a counterexample to A → B, hence A → B does not hold in Kq0 .
On the other hand if A → B does not hold in Kq0 then there must be some gq, q < q0 such that A ⊆ {gq}′ and B 6⊆ {gq}′. By definition of {gq}′ this is equivalent to I(gq, a) > q for all a ∈ A and I(gq, b) ≤ q for some b ∈ B. Since q < q0 it holds that for this value b in particular I(gq, b) < q0 and I(gq, a) > I(gq, b) for all a ∈ A. It then follows from (8) that A → B does not hold in K with at least degree q0. ⊔⊓
Notice, that if q1 < q0 then Gq1 ⊆ Gq0 and Iq1 ⊆ Iq0 . This observation, together with Lemma 2, suggests a levelwise approach as sketched in Algorithm 1. One starts with the largest value qmax in QK and computes the DuquenneGuigues Base for Kqmax . The base serves two purposes. Its implications are added to the fuzzy set of implications L with degree q, and it serves as background knowledge in the next iteration. For the context from Table 3 Algorithm 1 yields the base {1/{Populous,Small}→{HighGDP}, 0.9/{Populous}→{HighGDP}, 0.2/∅→{HighGDP}}. Lemma 3. Upon termination Algorithm 1 returns a fuzzy set of crisp implications L that is sound and complete for Kq and has minimal cardinality among all such sets.
Proof. Soundness follows immediately from Lemma 8. To prove completeness, assume that U → V holds in K with degree q ∈ QK (notice that for the Gödel t-norm it always holds that kU → V kK ∈ QK). Then by Lemma 8 U → V holds in Kq. Consider D, V and L after the iteration for q in Algorithm 1. Since D ∪ B is complete for Kq and U → V holds in Kq the implication U → V follows from D ∪ B = {A → B | L(A → B) ≥ q} in the crisp setting.
We show that then U → V follows to degree q from L in the fuzzy setting. Assume the contrary, i.e. that there exists a context K¯ for which L is sound, but in which U → V does not hold to degree at least q. By Lemma 8 this yields that U → V does not hold in K¯ q while all implications from D ∪ B = {A → B | L(A → B) ≥ q} do hold in K¯ q. Because we have shown that U → V follows from D ∪ B in the crisp setting this is a contradiction. Hence U → V follows to degree q from L, which proves completeness.
Assume that L¯ is another sound and complete fuzzy set of implications for K. Then by Lemma 8 for each q ∈ QK the crisp set
L¯q = {A → B | L(A → B) ≥ q} must be sound and complete for Kq. A simple induction over q ∈ QK can be used to show that |L¯q| ≥ |Lq| for all q ∈ QK. For q maximal in QK the claim follows directly from minimality of the Duquenne-Guigues Base. For the induction step let q ∈ QK where |L¯q¯| ≥ |Lq¯| holds for the next larger value q¯ ∈ QK. Both Lq¯ and L¯q¯ are sound and complete for Kq¯, in particular they have the same models. Thus, L¯q = L¯q \ L¯q¯ ∪ L¯q¯ and L¯q \ L¯q¯ ∪ Lq¯ also have the same models, and are thus both sound and complete for Kq. Minimality of the Lq¯-Duquenne-Guigues base implies |L¯q \ L¯q¯| ≥ |DGLq¯(Kq)|. This proves
|L¯q| = | L¯q \ L¯q¯ | + |L¯q¯| ≥ |DGLq¯(Kq)| + |Lq¯| = |Lq|.
Since this holds for all q ∈ QK we get that L has minimal cardinality among all bases. ⊔⊓
We have restricted fuzzy FCA by allowing only crisp sets of attributes in the implications and using identity as the hedge. We have presented a sound and complete set of deduction rules for this restricted setting. For the Gödel t-norm the restricted setting corresponds semantically to fuzzy DL. Furthermore, we have presented a simple algorithm for computing a minimal base for the restricted setting. In the general setting this is only possible with globalization.
We do not claim, that this restriction of expressivity is the only feasible approach for reconciling the differences between the two fields. In future work it would be interesting to look at a kind of weighted conjunction in DL (imitating the semantics of fuzzy attribute sets). It would also be interesting to consider a version of fuzzy FCA that uses strong conjunction.