Let A = {1, 2, 3, 4, 5} and R be the relation defined by a R b if and only if a < b. Compute $R, R^2$ and $R^3$ .Draw digraph of $R, R^2$ and $R^3$.

372views

written 8.0 years ago by

teamques10 ★ 68k

Since Relation R is defined by aRb if and only if a<b.< p="">

So, relation R can be represented as:

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

R in matrix form is as follows:

$R=\begin{bmatrix}0&1&1&1&1 \\ 0&0&1&1&1 \\ 0&0&0&0&0 \\ 0)&0&0&0&1 \\ 0&0&1&1&0 \end{bmatrix}$

The Digraph for the relation R is as shown below:

enter image description here

Now $R^2$ in matrix form is as follows:

$R * R==\begin{bmatrix}0&1&1&1&1 \\ 0&0&1&1&1 \\ 0&0&0&0&0 \\ 0)&0&0&0&1 \\ 0&0&1&1&0 \end{bmatrix} * ==\begin{bmatrix}0&1&1&1&1 \\ 0&0&1&1&1 \\ 0&0&0&0&0 \\ 0)&0&0&0&1 \\ 0&0&1&1&0 \end{bmatrix}==\begin{bmatrix}0&0&1&2&3 \\ 0&0&0&1&2 \\ 0&0&0&0&0 \\ 0&0&0&0&0 \\ 0&0&1&0&0\end{bmatrix} \\ So, R^2= \{(1, 3), (1, 4), (1, 5), (2, 4), (2, 5), (3, 5)\}$

The Digraph for the relation $R^2$ is as shown below:

enter image description here

Now $R^3$ in matrix form is as follows:

$R^2* R==\begin{bmatrix}0&0&1&2&3 \\ 0&0&0&1&2 \\ 0&0&0&0&0 \\ 0&0&0&0&0 \\ 0&0&1&0&0\end{bmatrix} * =\begin{bmatrix}0&1&1&1&1 \\ 0&0&1&1&1 \\ 0&0&0&0&0 \\ 0)&0&0&0&1 \\ 0&0&1&1&0 \end{bmatrix}==\begin{bmatrix}0&0&0&1&3 \\ 0&0&0&0&1 \\ 0&0&0&0&0 \\ 0&0&0&0&0 \\ 0&0&0&0&0 \end{bmatrix} \\ So, R^3= \{(1, 4), (1, 5), (2, 5)\}$

The Digraph for the relation $R^3$ is as shown below:

enter image description here

ADD COMMENT EDIT