Crisp and Fuzzy Relations

A crisp relation represents the presence or absence of association, interaction, or interconnectedness between the elements of two or more sets. This concept can be generalized to allow for various degrees or strengths of relation or interaction between elements. Degrees of association can be represented by membership grades in a fuzzy relation in the same way as degrees of set membership are represented in the fuzzy set. In fact, just as the crisp set can be viewed as a restricted case of the more general fuzzy set concept, the crisp relation can be considered to be a restricted case of the fuzzy relations.

Cartesian product

The Cartesian product of two crisp sets X and Y, denoted by , is the crisp set of all ordered pairs such that the first element in each pair is a member of X and the second element is a member of Y. Formally,

The Cartesian product can be generalized for a family of crisp sets and denoted either by . Elements of the Cartesian product of n crisp sets are n-tuples _Thus,

It is possible for all sets to be equal, that is, to be a single set X. In this case, the Cartesian product of a set X with itself n times is usually denoted by _.

Relation among sets

A relation among crisp sets _{is a subset of the Cartesian product It is denoted either by or by the abbreviated form . Thus,}

,

so for relations among sets , the Cartesian product represents the universal set. Because a relation is itself a set, the basic set concepts such as containment or subset, union, intersection, and complement can be applied without modification to relations.

Each crisp relation R can be defined by a characteristic function that assigns a value 1 to every tuple of the universal set belonging to the relation and a 0 to every tuple that does not belong. Thus,

The membership of a tuple in a relation signifies that the elements of the tuple are related or associated with one another.

A relation can be written as a set of ordered tuples. Another convenient way of representing a relation involves an n-dimensional membership array:

Each element of the first dimension i₁ of this array corresponds to exactly one member of X₁, each element of the first dimension i₂ to exactly one member of X₂, and so on. If the n-tuple ,then

Just as the characteristic function of a crisp set can be generalized to allow for degrees of set membership, the characteristic function of a crisp relation can be generalized to allow tuples to have degrees of membership within the relation.

Thus, a fuzzy relation is a fuzzy set defined on the Cartesian product of crisp sets , may have varying degrees of membership within the relation. The membership grade is usually represented by a real number in the closed interval and indicates the strenght of the relation present between the elements of the tuple.

A fuzzy relation can also conveniently be represented by an n-dimensional membership array whose entries correspond to n-tuples in the universal set. These entries take values representing the membership grades of the corresponding n-tuples.

Examples

Let R be a crisp relation among the two sets X={dollar, pound, franc, mark} and Y={United States, France, Canada, Britain, Germany}, which associates a country with a currency as follows:

R(X,Y) = {(dollar,United States),(franc,France),(dollar,Canada),

(pound,Britain),(mark,Germany)}

This relation can also be represented by the following two dimensional membership array:

                  U.S.      France        Canada        Britain       Germany       
      dollar       1        0             1             0             0             
       pound       0        0             0             1             0             
       franc       0        1             0             0             0             
        mark       0        0             0             0             1             

Let R be a fuzzy relation among the two sets the distance to the target X={far, close, very close} and the speed of the car Y={very slow, slow, normal, quick, very quick}, which represents the relational concept "the break must be pressed very strong".

This relation can be written in list notation as

R(X,Y) = {0/(far, very slow) + .3/(close, very slow) + .8/(very close, very slow)

+ 0/(far, slow) + .4/(close, slow) + .9/(very close, slow)

+ 0/(far, normal) + .5/(close, normal) + 1/(very close, normal)

+ .1/(far, quick) + .6/(close, quick) + 1/(very close, quick)

+ .2/(far,very quick)+ .7/(close,very quick)+ 1/(very close,very quick)}

This relation can also be represented by the following two dimensional membership array:

               very slow    slow          normal        quick         very quick    
         far       0        0             0             .1            .2            
       close       .3       .4            .5            .6            .7            
  very close       .8       .9            1             1             1             

Subsequence

Consider the Cartesian product of all sets in the family . For each sequence (n-tuple)

and each sequence (r-tuple, r < n)

where , let y be called a subsequence of x if and only if .

Let denote that y is a subsequence of x.

Projection

Given a relation , denote the projection of R that disregards all variables in X except those in set

Then, is a fuzzy set (relation) whose membership function is defined on the Cartesian product of sets in Y by the equation

where is the membership function of the given n-ary relation R.

Example

Consider the sets X₁={far, close }, X₂={slow, quick} and X₃={small, tall} and the trenary fuzzy relation

= { .1/(far, slow, small) + .2/(close, slow, small)

+ .3/(far, quick, small) + .4/(close, quick, small)

+ .5/(far, slow, tall) + .6/(close,slow, tall)

+ .7/(far, quick, tall) + .8/(close, quick, tall) }

defined on .

Let . Then,

R_1,2 = { .5/(far, slow) + .6/(close, slow)

+ .7/(far, quick) + .8/(close, quick) }

R_1,3 = { .3/(far, small) + .4/(close, small)

+ .7/(far, tall) + .8/(close, tall) }

R_2,3 = { .2/(slow, small) + .4/(quick, small)

+ .6/(slow, tall) + .8/(quick, tall) }

R₁ = { .7/(far) + .8/(close) }

R₂ = { .6/(slow) + .8/( quick) }

R₃ = { .4/(small) + .8/(tall) }

Cylindric extension

Another operation on relations which is in some sense an inverse to the projection, is called a cylindric extension. Let X and Y denote the same families of sets as employed in the definition of projection. Let R be a relation defined on the Cartesian product of sets in the family Y, and let denote the cylindric extension of R into sets X_i ( ) that are in X but not in Y. Then,

.

The cylindric extension produces the largest fuzzy relation (in the sense of membership grades of elements of the extended Cartesian product) that is compatible with the given projection. Such a relation is the least specific of all relations compatible with the projection. The cylindric extension thus maximizes the nonspecificity in deriving the n-dimensional relation from one of its r-dimensional projections (r < n). That is, it guarantees that no information that is not included in the projection is employed in determining the extended relation.

Example

Membership functions of cylindric extensions of the first three projections of the previous example with respect to X are shown below. For instance of calculating the membership functions:

R_1,2 = { .5/(far, slow) + .6/(close, slow)

+ .7/(far, quick) + .8/(close, quick) }

= { .5/(far, slow, small) + .6/(close, slow, small)

+ .7/(far, quick, small) + .8/(close, quick, small)

+ .5/(far, slow, tall) + .6/(close,slow, tall)

+ .7/(far, quick, tall) + .8/(close, quick, tall) }

R_1,3 = { .3/(far, small) + .4/(close, small)

+ .7/(far, tall) + .8/(close, tall) }

= { .3/(far, slow, small) + .4/(close, slow, small)

+ .3/(far, quick, small) + .4/(close, quick, small)

+ .7/(far, slow, tall) + .8/(close,slow, tall)

+ .7/(far, quick, tall) + .8/(close, quick, tall) }

R_2,3 = { .2/(slow, small) + .4/(quick, small)

+ .6/(slow, tall) + .8/(quick, tall) }

= { .2/(far, slow, small) + .2/(close, slow, small)

+ .4/(far, quick, small) + .4/(close, quick, small)

+ .6/(far, slow, tall) + .6/(close,slow, tall)

+ .8/(far, quick, tall) + .8/(close, quick, tall) }

Cylindric closure

Relations that can be reconstructed from one of their projections by the cylindric extension exist, but they are rather rare. It is more common that a relation can be exactly reconstructed from several of its projections by taking the set intersection of their cylindric extensions. The resulting relation is usually called a cylindric closure.

When projections are determined by the max operator

,

the min operator is normally used for the set intersection. Hence, given a set of projections of a relation,

where denotes the cylindric closure based on the projections.

Example

The cylindric closure of the first three projections (cylindric extensions) of the previous example is the following fuzzy ternary relation:

cyl{R_1,2, R_1,3, R_2,3} = { .2/(far, slow, small) + .2/(close, slow, small)

+ .3/(far, quick, small) + .4/(close, quick, small)

+ .5/(far, slow, tall) + .6/(close,slow, tall)

+ .7/(far, quick, tall) + .8/(close, quick, tall) }

We can see that the cylindric closure is almost the same as the original relation. The only error in the cylindric closure involvs the triple (far, slow, small), which has a membership grade .1 in R and .2 in the cylindric closure. Hence, the three projections do not capture the original relation fully but approximate it quite well. Another example of the approximation of a relation by its cylindric closures is shown graphically on Fig. 1.3.1.

Fig. 1.3.1. Approximation of the relation R by its cylindric closures

Binary Relations

Any relation between two sets X and Y is known as a binary relation. It is usually denoted by R(X,Y).

In addition to membership matrices, another useful representation of binary relations R(X,Y) are sagittal diagrams. Each of the sets X,Y is represented by a set of nodes in the diagram; nodes corresponding to one set are clearly distinguished from nodes representing the other set. Elements of with nonzero membership grades in R(X,Y) are represented in the diagram by lines connecting the respective nodes. These lines are labeled with the value of the membership grade . An example of the sagittal diagram together with the corresponding membership matrix is shown in Fig. 1.3.2.

The symbol R representing a binary relation is often used in the following alternative way: we write xRy when ; for fuzzy relations, we write when .

Example

The domain of a relation

The domain of a crisp binary relation is written as domR(X,Y) and is defined as the crisp subset of X whose members participate in the relation. Formally,

If R(X,Y) is a fuzzy relation, its domain is the fuzzy set domR(X,Y) whose membership function is defined by

for each . Thus, each element of set X belongs in the domain of R to the degree equal to the strenght of its strongest relation to any member of set Y.

The range of a relation

The range of a crisp binary relation R(X,Y) is denoted by ranR(X,Y) and is defined as the crisp subset of Y whose members participate in the relation. Thus,

When R(X,Y) is a fuzzy relation, its range is the fuzzy set ranR(X,Y) whose membership function is defined by

for each . Therefore, the strength of the strongest relation that each element of Y has to an element of X is equal to the degree of that element's membership in the range of R.

The range of a relation

The height of a fuzzy relation R is a number h(R) defined by

that is, the largest membership grade attained by any pair , then the relation is called normal; otherwise it is called subnormal.

The inverse of a relation

The inverse of a crisp relation R(X,Y) is written as R^-1(X,Y) and is a subset of such that

where .

Clearly, .

For a fuzzy relation R(X,Y), the inverse fuzzy relation R^-1(X,Y) is defined by

.

A membership matrix _{representing R^-1(X,Y) is the transpose of the matrix for R(X,Y), that is, the rows of equal the columns of and the columns of equal the rows of . Clearly,}

for any binary fuzzy relation.

Example

Let R(X,Y) be a fuzzy relation on and such that

The inverse of R(X,Y) is then specified by the membership matrix

where denotes the transponse of .

The Composition of Binary Relations, the Fuzzy Max-Min Composition

Consider two crisp binary relations P(X,Y) and Q(Y,Z) defined with a common set Y. The composition of these two crisp relations is denoted by

and is defined as a subset R(X,Z) of , such that if and only if there exists at least one . It follows from this definition of composition that the following three properties are satisfied for binary relations P, Q, R:

Just as the classical set operations such as union and intersection have a variety of generalizations for fuzzy sets, the composition operation for fuzzy relations can take several forms. The most common of these is the max-min composition. Denoted again by , this operation is defined by

for all . This operation satisfies the same three properties just listed for the composition of crisp relations.

If the composition for crisp relations P(X,Y) and Q(Y,Z) is thought of as representing the existence of a relational chain between elements of X and Z, then the max-min composition for fuzzy relations can be interpreted as indicating the strength of such a relational chain. This strength is represented by the membership grade of the pair in the composition. The strength of each chain equals the strength of its weakest link; and the strength of the relation between elements x and z is then the strength of the strongest chain between them.

Example

Consider two binary relations P(X,Y) and Q(Y,Z) specified by their sagittal diagrams in Fig. 1.3.3. Let . is represented by the membership function specified in Fig. 1.3.3. For example,

Note that the pairs of that have nonzero membership grades in the composition are those joined by lines intersecting at a common element of Y in Fig. 1.3.3.

Composition of binary relations are conveniently performed in terms of membership matrices of the relations. Let be membership matrices of binary relations such that . We can then write, using this matrix notation,

Observe that the same elements of M_P and M_Q are used in the calculation of M_R as would be used in the regular multiplication of matrices, but the product and sum operations are here replaced with the min and max operations, respectively.

Example

The following matrix equations illustrate the max-min composition:

The Relational Join of Binary Relations

A similar operation on two binary relations, which differs from the composition in that it yields triples instead of pairs, is known as the relational join. Let us denote it by .

For crisp relations P(X,Y) and Q(Y,Z), it is defined as

_.

For fuzzy relations P(X,Y) and Q(Y,Z), the relational join corresponding to the max-min composition is defined by

.

We can see that the join operation forms a ternary relation from two binary relations. This is a major difference from the operation of composition, which produces another binary relation. In fact, the max-min composition is obtained by aggregating appropriate elements of the corresponding join by the max operator. Formally,

.

Observe that although a composition can be determined from the corresponding join, the reverse determination cannot be made, that is, the join cannot be determined from the composition.

Example

The join of relations P and Q given in Fig. 1.3.3. is represented by the membership function specified in the same figure. To convert this join into the corresponding composition by using the equation , the two indicated pairs of values of in Fig. 1.3.3. are aggregated by the max operator. For instance,