Posted on Categories:Discrete Mathematics, 数学代写, 离散数学

数学代写|离散数学代写Discrete Mathematics代考|TYPES OF RELATIONS AND RELATION MATRIX

avatest™

avatest™帮您通过考试

avatest™的各个学科专家已帮了学生顺利通过达上千场考试。我们保证您快速准时完成各时长和类型的考试，包括in class、take home、online、proctor。写手整理各样的资源来或按照您学校的资料教您，创造模拟试题，提供所有的问题例子，以保证您在真实考试中取得的通过率是85%以上。如果您有即将到来的每周、季考、期中或期末考试，我们都能帮助您！

•最快12小时交付

•200+ 英语母语导师

•70分以下全额退款

数学代写|离散数学代写Discrete Mathematics代考|TYPES OF RELATIONS AND RELATION MATRIX

Let $\mathrm{A}=\left{a_1, a_2, \ldots, a_i, \ldots, a_j, \ldots \ldots, a_n\right}$ be a non-empty set and $\mathrm{R}$ be a relation defined on the set A. Hence the matrix of the relation $\mathrm{R}$ relative to the ordering $a_1, a_2, \ldots, a_i, \ldots, a_j, \ldots \ldots$, $a_n$ is defined as
\begin{aligned} \mathrm{M}(\mathrm{R}) & =\left[m_{i j}\right]{n \times n} \ m{i j} & = \begin{cases}1 & \text { If } a_i \mathrm{R} a_j \ 0 & \text { If } a_i \mathrm{R} a_j\end{cases} \end{aligned}
3.12.1 Reflexive Relations
The relation $\mathrm{R}$ is said to be reflexive if $m_{i i}=1 \forall 1 \leq i \leq n$ i.e. all elements of the main diagonal in relation matrix $\mathrm{M}(\mathrm{R})$ are 1 .
3.12.2 Symmetric Relations
The relation $\mathrm{R}$ is said to be symmetric if $m_{i j}=m_{j i} \forall 1 \leq i \leq n$ and $1 \leq j \leq n$.
In other words the relation $R$ is said to be symmetric if $M(R)=[M(R)]^T$. where $[M(R)]^{\mathrm{T}}$ represents the transpose of the relation matrix $M(R)$.
3.12.3 Transitive Relation
The relation $\mathrm{R}$ is said to be transitive if $m_{i j}=1$ and $m_{j k}=1$, then $m_{i k}=1$ for $1 \leq i \leq n ; 1 \leq j \leq n$ and $1 \leq k \leq n$.

In other words the relation $\mathrm{R}$ is said to be transitive if and only if $\mathrm{R}^2 \subseteq \mathrm{R}$. i.e. Whenever entry $i, j$ in $[\mathrm{M}(\mathrm{R})]^2$ is non-zero, entry $i, j$ in $\mathrm{M}(\mathrm{R})$ is also non-zero.
Let $R$ be a relation on the set $A$ and $R$ is transitive.
Let
$$(x, z) \in \mathrm{R}^2=\mathrm{R} . \mathrm{R} \text {. }$$
So, there exists $y \in \mathrm{A}$ such that $(x, y) \in \mathrm{R}$ and $(y, z) \in \mathrm{R}$
Thus $(x, z) \in \mathrm{R}[\because \quad \mathrm{R}$ is transitive $]$
i.e.
$$(x, z) \in \mathrm{R}^2 \Rightarrow(x, z) \in \mathrm{R}$$
Therefore
$$\mathrm{R}^2 \subseteq \mathrm{R}$$
Conversely,Suppose that $\mathrm{R}^2 \subseteq R$.
Let $\quad(x, y) \in \mathrm{R}$ and $(y, z) \in \mathrm{R}$
This implies
i.e.
$(x, z) \in \mathrm{R} . \mathrm{R}=\mathrm{R}^2$
i.e.
$(x, z) \in \mathrm{R}^2 \subseteq \mathrm{R}$
$(x, z) \in \mathrm{R}$
Therefore $\mathrm{R}$ is transitive.

数学代写|离散数学代写Discrete Mathematics代考|Anti-Reflexive Relations

The relation $\mathrm{R}$ is said to be anti-reflexive if $m_{i i}=0 \forall 1 \leq i \leq n$ i.e. All elements of the main diagonal in relation matrix $\mathrm{M}(\mathrm{R})$ are 0 (zero).
3.12.5 Asymmetric Relations
The relation R is said to be asymmetric if $m_{i j}=1$, then $m_{j i}=0$ and $m_{i i}=0$.
3.12.6 Anti-Symmetric Relations
The relation R is said to be anti-symmetric if $a_i \neq a_j$ then either $m_{i j}=0$ or $m_{j i}=0$ and $m_{i j}=1$ $=m_{j i}$ implies $a_i=a_j$.
Consider the following relations on the set $\mathrm{A}={1,3,5,7}$
\begin{aligned} & \mathrm{R}1={(1,1),(1,3),(1,7),(3,3),(3,7),(5,5),(5,7),(7,7)} \ & \mathrm{R}_2={(1,1),(1,5),(1,7),(3,5),(3,7),(5,1),(5,3),(7,1),(7,3)} \ & \mathrm{R}_3={(1,1),(1,3),(1,5),(1,7),(3,1),(3,3),(3,5),(3,7),(5,7)} \ & \mathrm{R}_4={(1,3),(1,7),(3,7),(5,7),(7,1)} \ & \mathrm{R}_5={(1,3),(3,5),(5,7),(7,1),(7,3)} \ & \mathrm{R}_6={(1,1),(1,7),(7,5),(7,3),(5,3)} \end{aligned} Relative to the ordering $1,3,5,7$ we get $$\begin{array}{ll} M\left(R_1\right)=\left[\begin{array}{llll} 1 & 1 & 0 & 1 \ 0 & 1 & 0 & 1 \ 0 & 0 & 1 & 1 \ 0 & 0 & 0 & 1 \end{array}\right] ; & \mathbf{M}\left(\mathbf{R}_2\right)=\left[\begin{array}{llll} 1 & 0 & 1 & 1 \ 0 & 0 & 1 & 1 \ 1 & 1 & 0 & 0 \ 1 & 1 & 0 & 0 \end{array}\right] ; \ M\left(R_3\right)=\left[\begin{array}{llll} 1 & 1 & 1 & 1 \ 1 & 1 & 1 & 1 \ 0 & 0 & 0 & 1 \ 0 & 0 & 0 & 0 \end{array}\right] ; & \mathbf{M}\left(\mathrm{R}_4\right)=\left[\begin{array}{llll} 0 & 1 & 0 & 1 \ 0 & 0 & 0 & 1 \ 0 & 0 & 0 & 1 \ 1 & 0 & 0 & 0 \end{array}\right] ; \ \mathbf{M}\left(\mathrm{R}_5\right)=\left[\begin{array}{llll} 0 & 1 & 0 & 0 \ 0 & 0 & 1 & 0 \ 0 & 0 & 0 & 1 \ 1 & 1 & 0 & 0 \end{array}\right] ; & \mathbf{M}\left(\mathrm{R}_6\right)=\left[\begin{array}{llll} 1 & 0 & 0 & 1 \ 0 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 1 & 1 & 0 \end{array}\right] ; \end{array}$$ From the above matrices it is clear that $m{i i}=1$ in $\mathbf{M}\left(\mathrm{R}1\right)$ and $m{i i}=0$ in $\mathbf{M}\left(\mathrm{R}_4\right)$ and $\mathbf{M}\left(\mathrm{R}_5\right)$. Thus the relation $R_1$ is reflexive where as the relations $R_4$ and $R_5$ are anti-reflexive. Again
$$\left[M\left(R_2\right)\right]^T=\left[\begin{array}{llll} 1 & 0 & 1 & 1 \ 0 & 0 & 1 & 1 \ 1 & 1 & 0 & 0 \ 1 & 1 & 0 & 0 \end{array}\right]=M\left(R_2\right)$$
So, the relation $R_2$ is symmetric. Also $\left[M\left(R_1\right)\right]^T \neq M\left(R_1\right)$, and hence the relation $R_1$ is not symmetric. Similarly it can be shown that the relations $R_3, R_4, R_5$ and $R_6$ are not symmetric.
Now in $M\left(R_1\right), M\left(R_2\right), M\left(R_3\right)$ and $M\left(R_6\right)$, we see that $m_{i i} \neq 0$, so the relations $R_1, R_2, R_3$ and $R_6$ are not asymmetric. In $\mathrm{M}\left(\mathrm{R}4\right)$ we see that $m{i i}=0$, but $m_{14}=1=m_{41}$. This violate the conditions of asymmetric relation hence not asymmetric. It is also observed that in $\mathbf{M}\left(\mathrm{R}5\right), m{i i}=0 ; m_{12}$ $=1, m_{21}=0 ; m_{23}=1, m_{32}=0 ; m_{34}=1, m_{43}=0 ; m_{41}=1, m_{14}=0$ and $m_{42}=1, m_{24}=0$. Thus the relation $R_5$ is asymmetric. Again
$$\left[M\left(R_3\right)\right]^2=\left[\begin{array}{llll} 1 & 1 & 1 & 1 \ 1 & 1 & 1 & 1 \ 0 & 0 & 0 & 1 \ 0 & 0 & 0 & 0 \end{array}\right]\left[\begin{array}{llll} 1 & 1 & 1 & 1 \ 1 & 1 & 1 & 1 \ 0 & 0 & 0 & 1 \ 0 & 0 & 0 & 0 \end{array}\right]=\left[\begin{array}{llll} 2 & 2 & 2 & 3 \ 2 & 2 & 2 & 3 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \end{array}\right]$$
We see that whenever $i, j$ in $\left[\mathrm{M}\left(\mathrm{R}_3\right)\right]^2$ is non-zero, entry $i, j$ in $\mathrm{M}\left(\mathrm{R}_3\right)$ is also non-zero. So the relation $\mathrm{R}_3$ is transitive. It is also cleared that $\left[\mathrm{M}\left(\mathrm{R}_i\right)\right]^2 \nsubseteq \subset \mathrm{M}\left(\mathrm{R}_i\right)$ for $i=1,2,4,5,6$. Thus the relations $R_1, R_2, R_4, R_5$ and $R_6$ are not transitive. Also it can be shown that the relation $R_6$ is anti-symmetric.

数学代写|离散数学代写Discrete Mathematics代考|TYPES OF RELATIONS AND RELATION MATRIX

\begin{aligned} \mathrm{M}(\mathrm{R}) & =\left[m_{i j}\right]{n \times n} \ m{i j} & = \begin{cases}1 & \text { If } a_i \mathrm{R} a_j \ 0 & \text { If } a_i \mathrm{R} a_j\end{cases} \end{aligned}
3.12.1自反关系

3.12.2对称关系

3.12.3传递关系

$$(x, z) \in \mathrm{R}^2=\mathrm{R} . \mathrm{R} \text {. }$$

$$(x, z) \in \mathrm{R}^2 \Rightarrow(x, z) \in \mathrm{R}$$

$$\mathrm{R}^2 \subseteq \mathrm{R}$$

$(x, z) \in \mathrm{R} . \mathrm{R}=\mathrm{R}^2$

$(x, z) \in \mathrm{R}^2 \subseteq \mathrm{R}$
$(x, z) \in \mathrm{R}$

数学代写|离散数学代写Discrete Mathematics代考|Anti-Reflexive Relations

3.12.5非对称关系

3.12.6反对称关系

$$\left[M\left(R_3\right)\right]^2=\left[\begin{array}{llll} 1 & 1 & 1 & 1 \ 1 & 1 & 1 & 1 \ 0 & 0 & 0 & 1 \ 0 & 0 & 0 & 0 \end{array}\right]\left[\begin{array}{llll} 1 & 1 & 1 & 1 \ 1 & 1 & 1 & 1 \ 0 & 0 & 0 & 1 \ 0 & 0 & 0 & 0 \end{array}\right]=\left[\begin{array}{llll} 2 & 2 & 2 & 3 \ 2 & 2 & 2 & 3 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \end{array}\right]$$