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*_{1} of this array
corresponds to exactly one member of *X*_{1}, each element of the
first dimension *i*_{2} to exactly one member of
*X*_{2}, 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*_{1}={far, close },
*X*_{2}={slow, quick} and* X*_{3}={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*_{1 } = { .7/(far) + .8/(close) }

*R*_{2} = { .6/(slow) + .8/( quick) }

*R*_{3} = { .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}* (

_{
}.

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

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*

Fig. 1.3.2. Sagittal diagram together with the corresponding membership matrix

__The domain of a relation__

The *domain* of a crisp binary relation is written as
dom*R*(*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 dom*R*(*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 ran*R*(*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 ran*R*(*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.

Fig. 1.3.3. Composition and join of binary relations

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,

_{
}