Crisp relation – Definition, types and operations

Crisp relation is defined over the cartesian product of two crisp sets. Suppose, A and B are two crisp sets. Then Cartesian product denoted as A×B is a collection of order pairs, such that

A × B = { (a, b)  |  a ∈ A and b ∈ B }

Note:

A × B ≠ B × A

|A × B| = |A| × |B|

A × B provides a mapping from  a ∈ A to b ∈ B

The relation is a very useful concept in many fields. It is useful in logic, pattern recognition, control system, classification etc.

Crisp relation is a set of order pairs (a, b) from Cartesian product A × B such that a ∈ A and b ∈ B. Relations basically represent the mapping of the sets. It defines the interaction or association of variables. The strength of the relationship between ordered pairs of elements in each universe is measured by the characteristic function denoted by χ.

where a value of unity is associated with a complete relationship and a value of zero is associated with no relationship, i.e.,

\[ \chi_{R}(a,b) = \begin{cases} 1 , & if (a,b) \in (A \times B) \\ 0, & if (a,b) \notin (A \times B) \end{cases} \]

Example: Crisp relation

Consider two crisp sets: C = {1, 2, 3} and D = {4, 5, 6}.

  • Find Cartesian product of C×D
  • Also find relation R over this Cartesian products such that R={(c, d) |  d = c + 2, (c, d) ∈ C × D }

Solution:

C × D = { (1, 4), (1, 5), (1, 6),(2, 4), (2, 5), (2, 6),(3, 4), (3, 5), (3, 6) }

crisp set relation
The pair highlighted in bold satisfy the condition

From the above table, it is easy to infer that, relation R={(2, 4), (3, 5)}

Representation of crisp relation:

We can represent crisp relations in various ways. One way is to represent it using the functional form, which we already have described earlier.

Two other popular representations are shown below:

Let us represent both the relation for the relation R defined over set A and B as

A = {1, 2, 3}, B = {4, 5, 6}, R = {(2, 4), (3, 5)}

Sagittal / Pictorial Representation:

sagittal representation of relation

Matrix Representation:

matrix representation of relation

Some special relations:

Let us discuss some special types of relations.

Null Relation: There is no mapping of elements from universe X to universe Y

null relation
Null relation

Complete Relation: All the elements of universe X is mapped to universe Y

identity relation
Identity relation

Universal Relations: The universal relation on A is defined as UA = A x A = A2

Let A = {0, 1, 2}, then UA = A x A = {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)}

Identity Relations: The identity relation on A is defined as IA = { (a, a), ∀a ∈ A }

Let A = {0, 1, 2}, then IA = {(0, 0), (1, 1), (2, 2)}

Watch on YouTube: Crisp relation

crisp relation on youtube

Operations on crisp relation:

Like operations on crisp sets, we can also perform operations on crisp relations. Suppose, R(x, y) and S(x, y) are the two relations defined over two crisp sets, where x ∈ A and y ∈ B

We will discuss various operations on crisp set for the following two crisp relations R and S:

relation r
Relation R
relation S
Relation S

Union of crisp relation:

R ∪ S = χR ∪ S (x, y) = max( χR(x, y), χS(x, y) )

The Union of the given relation R and S would be,

Union of crisp relations

Intersection of crisp relation:

R ∩ S = χR ∩ S (x, y) = min( χR(x, y), χS(x, y) )

The intersection of the given relation R and S would be,

intersection of crisp relation
The intersection of crisp relations

Complement of crisp relation:

Rc = χRc (x, y)= 1 – χR(x, y)

The intersection of the given relation R would be,

Complement of crisp relation
Complement of crisp relation

Containment:

R ⊂ S = χR ⊂ S (x, y) = χR(x, y) ≤ χS(x, y)

Relation R is not contained within relation S. Consider the relation T as given below:

Relation T
Relation T

Here, χR(x, y) ≤ χT(x, y), so R is contained within T.

Cardinality of crisp set:

Cardinality defines the number of elements in the given set. Let A and B be the crisp sets with cardinality n and m, respectively. The cardinality of crisp relation defined over Cartesian product A×B will be n × m

Example:

Let A = (1, 2) and B = {3, 4, 5}

Here, n = |A| = 2 and m = |B| =3, So, n×m=6

The cartesian product of both the set,

A × B={ (1, 3), (1, 4), (1, 5),(2, 3), (2, 4), (2, 5) }

Cardinality of cartesian product is, | A × B | = 6 = n × m

Composition of crisp relation:

The composition of relation R and S is denoted as R ∘ S

R ∘ S = {(x, z) | (x, y) ∈ R, and (y, z) ∈ S, ∀y ∈ Y}

The composition of the relation is computed in two different ways:

Although, for crisp relation, both methods yield identical results. For fuzzy relations, it gives different results.


Test your knowledge:

For the given relations,

Find the union, intersection, complement and containment of relation A in B.

Please post your answer / query / feedback in comment section below !

10 Responses

  1. mohammadc says:

    Excellent article

  2. Rajvi Upadhyay says:

    Wonderfully explained with example. Thank you very much for providing better understanding.

  3. Smita Mahajani says:

    Union is Row wise {{1,0,1} , {1,1,1} ,{0,1,1} }

  4. Smita Mahajani says:

    Intersection is {{1,0,0} , {0,0,1} , {0,0,1}} (row wise )

  5. İzzet Türkalp says:

    Composition of crisp realtion: must be relation

Leave a Reply

Your email address will not be published. Required fields are marked *