A Logical Study of Local and Global Graded Similarities

Abstract

In this work we study the relationship between global and local similarities in the graded framework of fuzzy class theory (FCT), in which there already exists a graded notion of similarity. In FCT we can express the fact that a fuzzy relation is reflexive, symmetric, or transitive up to a certain degree, and similarity is defined as a first-order sentence, which is the fusion of three sentences corresponding to the graded notions of reflexivity, symmetry, and transitivity. This allows us to speak in a natural way of the degree of similarity of a relation. We consider global similarities defined from local similarities using t-norms as aggregation operators, and we obtain some results in the framework of FCT that, adequately interpreted, allow us to say that when we take a t-norm as an aggregation operator, the properties of reflexivity, symmetry, and transitivity of fuzzy binary relations are inherited from the local to the global level, and that the global similarity is a congruence if some of the local similarities are congruences.

INTRODUCTION

This article is an extended version of Armengol, Dellunde, and García-Cerdaña (in press), in which we began the logical study of the similarity relation between objects represented as attribute-value pairs. Ruspini (1991) suggests that the degree of similarity between two objects A and B may be regarded as the degree of truth of the vague proposition “A is similar to B.” Thus, similarity among objects can be seen as an essentially fuzzy phenomenon.

The notion of similarity in fuzzy sets theory was introduced by Zadeh (1971) as a generalization of the notion of equivalence relation (see Recasens 2011 for a historical overview on the notion of t-norm-based similarity). As Zadeh pointed out, one of the possible semantics of fuzzy sets is in terms of similarity. Indeed, the membership degree of an object to a fuzzy set can be seen as the degree of resemblance between the object and prototypes of the fuzzy set. From a logical point of view, Hájek (1998) studies similarities and congruences in fuzzy predicate logics and proposes axioms for them in the context of the logic BL∀.

It is worth stressing that the common approach to defining similarity between objects is by means of the dual of a distance measure. This implies that objects are described geometrically. At this point, we want to go beyond this idea and integrate more general ideas of similarity as those set by the cognitive and mathematical psychologist Amos Tversky, who argues that often objects are not described geometrically but symbolically. In fact, he shows situations in which similarities do not satisfy the mathematical notions of (dual) metrics (Tversky 1977). In these cases, he proposes to define similarity through the comparison of the features that describe these objects. At this point, following these ideas, to assess the similarity between two objects by comparing their features, we need.

• To assess how both objects are similar in each feature and then to aggregate these similarities.

• To consider weaker notions of similarity in which reflexivity, symmetry, or transitivity does not necessarily hold, or holds only up to some degree.

To illustrate this idea, let us consider Table 1, which describes the mutual feelings among three persons by a degree between 0 and 1.

TABLE 1 Feelings among John, Mary, and Peter

Feelings	John	Mary	Peter
John	1	0.6	0.2
Mary	0.3	0.8	0.7
Peter	0.5	0.9	0.4

Such relation does not satisfy these three properties in degree 1 because (1) feelings is not reflexive because feelings (Mary, Mary) ; (2) feelings is not symmetric because Mary loves John with degree 0.3, whereas John loves Mary with degree 0.6; and (3) feelings is not transitive because feelings (John, Mary) , feelings (Mary, Peter) , but feelings (John, Peter) = 0.2.

In order to deal with a notion of similarity integrating these ideas, we study the relationship between global and local similarities in the graded framework of Fuzzy Class Theory (FCT) in which there already exists a graded notion of similarity. FCT, introduced in Běhounek and Cintula (2005), is a part of mathematical fuzzy logic (Hájek 1998; Běhounek, Cintula, and Hájek 2011) devoted to the axiomatization of the notion of fuzzy sets. This formalism serves as foundation of a large part of fuzzy mathematics. In particular, fuzzy relations such as fuzzy orders and similarities can be studied in this graded framework. For instance, in FCT we can express the fact that a fuzzy relation is reflexive, symmetric, or transitive up to a certain degree. Thus, these properties are expressed by means of first-order sentences. For instance, the degree to which the relation R is reflexive is the truth value of the sentence . Then, similarity is defined as a first-order sentence, which is the fusion of three sentences, corresponding to the graded notions of reflexivity, symmetry, and transitivity. This allows us us to speak in a natural way of the degree of similarity of a relation.

Global similarities between objects can be defined as the aggregation of local similarities (defined between values of the objects’ attributes). As references for the subject of aggregation operations see Detyniecki (2001), Mayor and Mesiar (2002), Dubois and Prade (2004). Important aggregation operators are t-norms and t-conorms (Klement, Mesiar, and Pap 2000). Using these kinds of operations, we can define global similarities in a multiplicative way as “fusion” of local similarities, or in an additive way as residuated sum of such local similarities. In this work we consider global similarities defined from local similarities using t-norms. In addition, we study the relationship between the degree of properties such as reflexivity, symmetry, and transitivity of global similarities and the degree of the same properties in local similarities. We obtain some results in the framework of FCT that, adequately interpreted, allow us to say that when we take a t-norm as aggregation operator:

• the properties of reflexivity, symmetry, and transitivity of fuzzy binary relations at the global level inherit the properties of the fuzzy binary relations at the local level when we fuse them (Proposition 3.2),

• the global similarity is a congruence if some of the local similarities are congruences (Proposition 3.4).

This article is organized as follows. In “Preliminaries,” we introduce some notions concerning similarity and the basics of FCT. In “Local and Global Similarities in Fuzzy Class Theory: Main Results,” we present our main logical results. Finally, there is a section devoted to conclusions and future work.

PRELIMINARIES

A triangular norm (or t-norm; Klement, Mesiar, and Pap 2000) is defined as a binary operation on the real interval [0,1] and satisfying the following properties: associative, commutative, nondecreasing in both arguments, and having 1 as unit element. Given the usual order in [0,1], a left-continuous t-norm * is characterized by the existence of a unique operation satisfying, for all , the condition

This operation is called the residuum of the t-norm and it satisfies

A continuous t-norm is a left-continuous t-norm satisfying the so-called divisibility condition: for all , . A prominent left-continuous t-norm that is not continuous is the Nilpotent Minimum (see Table 2). The three basic continuous t-norms are the Minimum, Product, and Łukasiewicz (see Table 3). These are the basic ones; any continuous t-norm can be expressed as an ordinal sum of copies of them (Mostert and Shields 1957; Ling 1965).

TABLE 2 The Left-Continuous T-Norm Nilpotent Minimum (NM) and Its Residuum

*	NM

TABLE 3 The Three Main Continuous T-Norms and Their Residua

*	Minimum (Gödel)	Product	Łukasiewicz

Given a t-norm *, a similarity relation (Ruspini 1991; Recasens 2011) defined on a universe U is a function

such that, for every x, y, , the following hold:

1. , (Reflexivity)

2. (Symmetry)

3. (Transitivity)

Observe the duality of this notion with the one of normalized distance. The property

being a t-conorm, is a generalization of the triangular inequality. Hájek (1998) studies similarities and congruences in fuzzy predicate logics and proposes the following similarity axioms:¹

• (S1) (Reflexivity)

• (S2) (Symmetry)

• (S3)  (Transitivity)

and a congruence axiom for every n-ary predicate P in the language:

FCT was introduced in Běhounek and Cintula (2005) with the aim to axiomatize the notion of fuzzy set, and it is based on the logic ŁΠ∀. Later, in Běhounek, Bodenhofer, and Cintula (2008), the FCT was based in the more general setting of the logic . In such work, Běhounek, Bodenhofer, and Cintula studied fuzzy relations in the context of FCT, generalizing existing crisp results on fuzzy relations to the graded framework. The algebra of truth values for formulas is the standard -chain over the real unit interval [0, 1].

Let us recall the axiomatization of the logic (for a presentation of this logic see Běhounek, Bodenhofer, and Cintula 2008, Appendix A). The primitive connectives are &, →, Λ, Δ, and . Negation is defined by .

Axioms:

(MTL1)	=
(MTL2)	=
(MTL3)	=
(MTL4)	=
(MTL5)	=
(MTL6)	=
(MTL7a)	=
(MTL7b)	=
(MTL8)	=
(MTL9)	=
(Δ1)	=
(Δ2)	=
(Δ3)	=
(Δ4)	=
(Δ5)	=
(∀1)	=
(∀2)	=
(∀3)	=
(∃1)	=
(∃2)	=

Rules:

Modus ponens	=	,
Generalization	=
Δ-Necessitation	=

A standard -chain is an algebra , where * is any left-continuous t-norm, is the residuum of *, and δ is the operation defined by , and if .

Let be a first-order signature (predicate symbols and functional symbols). Given that T be a standard -chain, a T-structure for the signature is a tuple

where

1. M is a nonempty set (the universe of the structure);

2. for each k-ary ,

3. for each k-ary ,

Given an assignation v of the variables in M, the value of a term t in M is defined by

Let v be an M assignation such that . The truth value over the chain T of a formula for v is a value in [0,1], inductively defined as follows:

A formula is valid in a T-structure M (denoted as ) if for every assignation v. A T-structure M is an L-model of a theory Γ if for each .

Theorem 2.1

(Completeness Theorem) Let Γ be a theory and be a formula. The following conditions are equivalent:

1. .

2. for each standard MTL_Δ-chain T and each T-model M of Γ.

FCT over MTL_Δ is a theory over the multisorted first-order logic with crisp equality. It has sorts of individuals of order 0 (atomic objects) a, b, c, x, y, z, … ; individuals of the first-order (fuzzy classes) A, B, X, Y, … ; individuals of the second-order (fuzzy classes of fuzzy classes) For every variable x of any order n and for every formula there is a class term of order n + 1. In addition to the logical predicate of identity, the only primitive predicate is the membership predicate between successive sorts. For variables of all orders, the axioms for are:

• , for every formula , (Comprehension Axioms)

• . (Extensionality)

The basic properties of fuzzy relations are defined as sentences as follows:

Definition 2.2

Let R be a binary predicate symbol.

Reflexivity:  

Symmetry:  

Transitivity: 

Example 2.3

Let R₁, R₂, and R₃ be fuzzy relations on the set U = {u, v}, defined as follows:

The elements of these matrices correspond to the following distribution of values:

In such situations, the truth value of Refl(R_i) is obtained in the following way:

Thus, , , and . The truth value of Sym(R_i) is obtained as follows:

To calculate this truth value, we need to take a t-norm. Let us suppose we choose the minimum t-norm. According to Table 3 the residuum of the minimum t-norm is 1 when , and y otherwise. Thus, for instance, . Proceeding similarly with all the terms and for each R_i we obtain:

If we take the t-norm of Łukasiewicz, the symmetry degrees corresponding to Sym(R_i) are the following: , , and . Finally, the truth value of Trans (R_i) is obtained as follows:

For instance, if we take the minimum t-norm, we obtain

By proceeding similarly with all the terms, we obtain

If we take the t-norm of Łukasiewicz, the transitivity degrees corresponding to Trans(R_i) are the following: , , and .

In FCT there are two notions of similarity, the strong one is defined using the strong conjunction , and the weak one is defined using the weak conjunction . They are defined as sentences in the following way:

Definition 2.4

(Cf. Běhounek, Bodenhofer, and Cintula (2008) Let R be a binary predicate symbol,

Strong similarity: 

Weak similarity: 

As in Example 2.3, taking the Łukasiewicz t-norm, the degree of weak similarity for each is the following:

and the degree of strong similarity for each is

Notice that, in general, when we take the minimum t-norm, both similarities coincide. In this article we focus mainly on the strong similarity, and the analysis of the weak similarity remains as future work.

LOCAL AND GLOBAL SIMILARITIES IN FUZZY CLASS THEORY: MAIN RESULTS

Now we will proceed to prove the logical main results of this article concerning the relationship between local and global similarities. We show that basic properties of local similarities are preserved when we define a global similarity between objects, using these local similarities.

Let U be a set of objects represented by attribute-value pairs. Let be the attributes used to describe the objects in U. Suppose that every attribute takes values in a set . For every , let be a binary fuzzy relation defined on . Each relation induces a relation on U as follows. For every u, , , and , we define

We call each a local relation. From these local relations, and using a t-norm *, we define a new relation R as follows:

We say that R is a global relation.

Example 3.1

Table 4 shows the description of three persons according to the degree to which they like three hobbies: trekking, reading, and cinema. In order to compare them, we have to define a measure of how similar are two of these values. Let us suppose that we use the following formula to establish the similarity between two values:

TABLE 4 Descriptions of the Degree to Which Three Persons Like Three Hobbies: Trekking, Reading, and Cinema

Name	Trekking	Reading	Cinema
John	0.5	0.3	0.9
Mary	0.6	0.8	0.7
Peter	0.9	0.5	0.4

Now we use this expression to calculate the similarity between all the hobbies. For instance, concerning “trekking”. John, Mary, and Peter have the following degrees of similarity:

• –

• –

• –

The relations trekking , reading , and cinema are expressed as matrices:

The global relation is , and its matrix is computed in the following way:

where , , and , stand for the element of the matrices , , and , respectively. If we consider that is the minimum t-norm, we have

and, considering that is the Łukasiewicz t-norm, we have

Intuitively, the following proposition shows that the properties of reflexivity, symmetry, and transitivity of fuzzy binary relations at the global level inherit the properties of the fuzzy binary relations at the local level when we fuse them.

Proposition 3.2

For a fixed natural number , let be binary predicate symbols from the language of FCT, be atomic formulas, and . Then, the following theorems are provable in FCT:

Proof

For the proof of this Proposition, we apply repeatedly the following theorem of FCT (see, for instance, Běhounek, Bodenhofer, and Cintula 2008, Lemma B.8 (L15)):

(1)

and we also apply the following theorem of FCT (see, for instance, Běhounek and Cintula 2006, Lemma 3.2.2(3)):

(2)

(TS1): By Definition 2.2, . By applying FCT Theorem (1), we have:

and since , we have

(TS2): By Definition 2.2,

Now, by applying FCT Theorem (1) two times, we obtain:

By applying FCT Theorem (2) we obtain:

Finally, by transitivity, we obtain:

Consequently, .

(TS3): By Definition 2.2,

Now, by applying FCT Theorem (1) three times, we obtain:

By applying FCT Theorem (2) we obtain:

By repeatedly applying the commutativity and associativity axioms for & we obtain:

That is, by definition of the atomic formula Rxy,

The consequent formula of the previous sentence is precisely Trans(R). Thus, by transitivity, we obtain .□

Following with Example 3.1, we see that the relations R_t, R_r, and R_c are reflexive and symmetric to a degree 1 because all the elements in the diagonal of the matrices are 1 and all the matrices are symmetric. Also, the matrices representing the global similarity taking both the minimum t-norm (R_min) and the Łukasiewicz t-norm (R_Ł) have 1 in the diagonal and are symmetric. The relations R_t, R_r, and R_c are not transitive if we take the minimum t-norm. To see this, we must see that there are some elements x, y, z such that for , the inequalities are not satisfied. Indeed,

• R_t(John, Mary) * R_t(Mary, Peter) R_t(John, Peter), since min{0.9, 0.7} = 0.7 and R_t(John, Peter) = 0.6

• R_r(John, Peter) * R_r(Peter, Mary) R_r(John, Mary), since min{0.8, 0.7} = 0.7 and R_r(John, Mary) = 0.5

• R_c(John, Mary) * R_c(Mary, Peter) R_c(John, Peter), since min{0.8,0.7} = 0.7 but R_c(John, Peter) = 0.5

Therefore, the local relations have a degree of transitivity strictly lower than 1 when taking the minimum t-norm. An easy computation shows that, in this case, the transitivity degree of each of the local relations is the following: , , and . According to Proposition 3.2, the degree of transitivity of the global relation has to be greater than or equal to 0.5, which is the minimum of the values of local transitivities. Indeed, by computing directly from the global matrix R_min, we see that . Therefore, as was expected,

Taking the Łukasiewicz t-norm, it is not difficult to see that R_t, R_r, and R_c are all transitive. According to Proposition 3.2, the global relation also has transitivity of degree 1.

Now, as it is proved in the following corollary of the previous proposition, a lower bound of the degree of similarity of a global relation can be calculated by using the degrees of similarity of the local relations.

Corollary 3.3

For a fixed natural number , let be binary predicate symbols from the language of FCT, atomic formulas, and . Then, the following theorems are provable in FCT:

Proof

(TS4): By Definition 2.4, we have

Observe that, using the axioms of commutativity and associativity for &, we get:

Now, we use the fact that if are theorems of FCT, then is also a theorem of FCT. From (TS1), (TS2), and (TS3) of Proposition 3.2, using FCT Theorem (2), we obtain that the following formula is a theorem of FCT:

The consequent formula of the previous sentence is precisely Sim(R). Finally, by transitivity we get .

(TS5): It is analogously proved by using the following theorem (3) (see, for instance, Běhounek and Cintula 2006, Lemma 3.2.2(4)) instead of (2):

(3)

To illustrate the consequences of the previous corollary, we use again Example 3.1. We calculate here the degree of similarity of the global relation from the degree of similarity of each of the local similarities. First let us focus on R_t. According to Definition 2.4, its degree of strong similarity is computed as the truth value of the sentence . We know that using the minimum t-norm, and . Therefore, we have . Proceeding analogously with R_r and R_c, using the minimum t-norm, we have the following values: , and .

According to Corollary 3.3, the degree of similarity of the global relation has to be greater than or equal to 0.5, which is the minimum of the degrees of local similarities. If we compute directly, using the minimum t-norm, we have that and . Therefore, as is expected,

Because the definition of weak similarity (wSim), interprets the conjunction as the minimum, the values for Refl(R_t), Sym(R_t), and Trans(R_t) are the same as the strong similarity.

The following proposition shows that the global similarity is a congruence if some of the local similarities are also congruences.

Proposition 3.4

For a fixed natural number , let be binary predicate symbols from the language of FCT, be atomic formulas, and . Assume that T is a theory such that, for some , and for each n-ary predicate P,

Then, the following property holds for R: For each n-ary predicate P,

Proof

For the sake of clarity, we prove the proposition for every binary predicate P, but the same proof holds for predicates of arbitrary arity. Let i, , be such that for each n-ary predicate P,

Let us consider the following instance of the axiom (MTL1):

(⋆)   

On the one hand, since , using the theorem

(4)

we obtain that and are theorems of FCT. Therefore, by applying FCT theorem (1), we have:

(5)

On the other hand, by assumption we have:

(6)

Now, taking as premises (⋆), (5), and (6), by applying Modus Ponens two times, we obtain:

(7)

Finally, by applying the Generalization rule to (7) four times, we obtain:

(8)

q.e.d.

In Hájek (1998, Lemma 5.6.8) it is proved, in the context of the logic BL∀, that similar objects have similar properties, being that these properties are expressed by first-order formulas evaluated in these objects. In the forthcoming article (Armengol, Dellunde, and García-Cerdaña in press, Theorem 1) we generalized this result to the logic MTL∀. To present here this result, we extend the notion of syntactic degree of a formula (Hájek 1998, Definition 5.6.7) to the language of in the following way:

Notation

Let abbreviate (k times).

Theorem 3.5

(Armengol Dellunde, and García-Cerdaña in press, Theorem 1) Let T be a theory in MTL∀ containing the axioms:

• (S1) (Reflexivity)

• (S2) (Symmetry)

• (S3)  (Transitivity)

and, for every n-ary predicate P of the language, the congruence axiom:

Let be a first-order formula of MTL∀ with , and let be variables including all free variables of in such a way that, for every , y_i is substituable for x_i in . Then,

In our context we can use the result only for the fragment without Δ, as the following example shows. Suppose that . Let M be a T-structure for the minimum, as defined in “Preliminaries,” in a signature with only a monadic predicate symbol P and a binary relation symbol ≈. Assume that this structure is a model of the axioms (S1), (S2), (S3) and of the axiom of congruence for ≈ corresponding to P. This structure is not a model of the formula : Indeed, take a, b to be elements of M suchthat , and .

For formulas containing the connective Δ we have the following result:

Theorem 3.6

Let T be a theory in MTL_Δ containing axioms (S1), (S2), (S3), and the congruence axioms or ≈. Let be a first-order formula of MTL∀_Δ with , and let be variables including all free variables of in such a way that, for every , y_i is substituable for x_i in . Then,

Proof

By induction on the complexity of formulas. By axioms (S1), (S2), (S3), and congruence axioms, the assertion is true for atomic formulas (and is vacuous for truth constants). For the proof of all the inductive steps except for the Δ step, we refer to the proof of Armengol Dellunde, and García-Cerdaña (in press, Theorem 1). For the sake of simplicity, we prove the Δ step for only 2 variables, that is, for instead for . The generalization to the n case is trivial.

Inductive step . By definition of the syntactic degree, . By inductive hypothesis, we have . Thus, by the Δ rule,

and then, by Axiom (Δ5) of MTL_Δ, . Finally, by using the fact that is a theorem of MTL_Δ (Cf. Běhounek and Cintula 2006, Lemma 3.2.1(TΔ3)), and using again Axiom (Δ5), it is easy to see that

CONCLUSIONS AND FUTURE WORK

In the present work we study similarities in the framework of Fuzzy Class Theory (FCT) and prove some logical properties. FCT allows us to deal with relations having different degrees of reflexivity, symmetry, and transitivity. We obtain some results that, adequately interpreted, allow us to say that, taking a t-norm as aggregation operator, the properties of reflexivity, symmetry, and transitivity of fuzzy binary relations at the global level inherit the properties of the fuzzy binary relations at the local level when we fuse them. Moreover, we have shown that the global similarity is a congruence if some of the local similarities are congruences.

Fuzzy description logics (FDLs) are natural extensions of description logics (Baader et al. 2003) expressing vague concepts commonly present in real applications (see Lukasiewicz and Straccia 2008 for a survey). In García-Cerdaña, Armengol, and Dellunde (2010), we studied the notion of similarity between objects represented as attribute-value pairs in the context of FDL. In that study we proposed to add an SBox (Similarity Box) to the knowledge bases of an -like fuzzy description language. The SBox allows the expression of properties such as reflexivity, symmetry, transitivityn and congruence of a relation. The results presented in “Local and Global Similarities in Fuzzy Class Theory: Main Results” of the current article will be used in a forthcoming study in order to introduce graded axioms for reflexivity, symmetry, and transitivity in the SBox of FDL in a systematic way.

An aggregation operator has the property of compensation (also known as Pareto property) when the result of the aggregation is lower than the maximum element aggregated and higher than the minimum one (Detyniecki 2001). Some authors stress that t-norms (and also t-conorms) lack a compensation behavior, which is considered crucial in the aggregation process. In practice, when the property of compensation does not hold, this can produce undesirable effects when two object are similar in all the attributes except one. The operators known as uninorms (Fodor, Yager, and Rybalov 1997) are a generalization of t-norms in which the neutral element of the operation does not coincide with the maximum. This characteristic implies that these kinds of operations admit, in general, a good compensating behavior. As future work, we plan to study the FCT based in UL, the logic of uninorms (Metcalfe and Montagna 2007), in order to deal with similarities in this context. We want to explore the plausibility of the results obtained in the present study in the more general context of uninorms. We also plan to study other aggregation operators from a logical point of view.

Finally, we want to experiment with the approach introduced in this paper on a real domain. In particular, we are interested on assessing the life quality of people with intellectual disabilities. Schalock and Verdugo (2002) proposed a model in which the life quality of a person is a relation of eight dimensions. In fact, the relation between these dimensions is unknown, i.e., we do not know how low or high values of one dimension affect the values of the others. We think thats with our approachs we can model both the similarity between two persons and also the relations between the dimensions.

FUNDING

The authors acknowledge support by the Spanish projects EdeTRI (TIN2012-39348-C02-01), COGNITIO (TIN2012-38450-C03-03), MILESS (TIN2013-45039-P), and MTM 2011-25747; and the grants 2014SGR-118 and 2014SGR-788 from the Genera-litat de Catalunya.

Additional information

Funding

The authors acknowledge support by the Spanish projects EdeTRI (TIN2012-39348-C02-01), COGNITIO (TIN2012-38450-C03-03), MILESS (TIN2013-45039-P), and MTM 2011-25747; and the grants 2014SGR-118 and 2014SGR-788 from the Genera-litat de Catalunya.

Notes

¹ In order to economize within parenthese we will consider → the least binding connective.