离散数学【关系】习题解析 序偶，直积，关系图，关系矩阵，哈斯图

下面是习题与解析

第一题 序偶与类型

(1) 解：

R={<1,2>,<1,4>,<1,6>,<2,1>,<2,2>,<2,4>,<2,6>,<4,1>,<4,2>,<4,4>,<4,6>,<6,1>,<6,2>,<6,4>,<6,6>}

因为 1+1=2

所以<1,1> $\in /$ R ，<2,2>$\in /$R R既不是自反，也不是反自反

关系矩阵如下
$$R=?\begin{array}{cccc}0& 1& 1& 1\\ 1& 1& 1& 1\\ 1& 1& 1& 1\\ 1& 1& 1& 1\end{array}?$$
可以看出，R为对称矩阵，是对称的

$$MR?R=?\begin{array}{cccc}0& 1& 1& 1\\ 1& 1& 1& 1\\ 1& 1& 1& 1\\ 1& 1& 1& 1\end{array}???\begin{array}{cccc}0& 1& 1& 1\\ 1& 1& 1& 1\\ 1& 1& 1& 1\\ 1& 1& 1& 1\end{array}?=?\begin{array}{cccc}1& 1& 1& 1\\ 1& 1& 1& 1\\ 1& 1& 1& 1\\ 1& 1& 1& 1\end{array}?$$
因为 M _R$?$R $\ge$M_R，所以M_R不是可传递的

(2) R={<1,2>,<1,4>,<1,6>,<2,4>,<2,6>,<4,6>}

因为 <1,1>,<2,2>,<4,4>,<6,6> $\in /$ R，所以是反自反的

关系矩阵
$$R=?\begin{array}{cccc}0& 1& 1& 1\\ 0& 0& 1& 1\\ 0& 0& 0& 1\\ 0& 0& 0& 0\end{array}?$$
显然是不对称的
$$MR?R=?\begin{array}{cccc}0& 1& 1& 1\\ 0& 0& 1& 1\\ 0& 0& 0& 1\\ 0& 0& 0& 0\end{array}???\begin{array}{cccc}0& 1& 1& 1\\ 0& 0& 1& 1\\ 0& 0& 0& 1\\ 0& 0& 0& 0\end{array}?=?\begin{array}{cccc}0& 0& 1& 1\\ 0& 0& 0& 1\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}?$$
因为M _{R $?$ R}$\le$M_R，所以是可传递的

第二题 关系图，矩阵与类型

R的关系矩阵
$$R=?\begin{array}{cccc}1& 0& 0& 1\\ 0& 0& 0& 0\\ 1& 1& 0& 1\\ 0& 0& 1& 0\end{array}?$$
R的关系图

如图，1,2,3节点没有自旋，0有自旋，所以既不是自反，也不是反自反

从关系矩阵中，<2,3><3,2>对称，所以可以看出既不是对称，也不是反对称
$$MR?R=?\begin{array}{cccc}1& 0& 0& 1\\ 0& 0& 0& 0\\ 1& 1& 0& 1\\ 0& 0& 1& 0\end{array}???\begin{array}{cccc}1& 0& 0& 1\\ 0& 0& 0& 0\\ 1& 1& 0& 1\\ 0& 0& 1& 0\end{array}?=?\begin{array}{cccc}1& 0& 1& 1\\ 0& 0& 0& 0\\ 1& 0& 1& 1\\ 1& 1& 0& 1\end{array}?$$
所以M _{R $?$ R}$?$M_R，所以不是可传递的

第三题关系图，矩阵与类型

R的关系图

R的关系矩阵
$$R=?\begin{array}{cccc}0& 0& 1& 1\\ 0& 0& 1& 1\\ 0& 0& 0& 1\\ 0& 0& 0& 0\end{array}?$$
从关系图可知

• 顶点没有自旋，所以是反自反的

• 任意点之间只有单向的边，所以是反对称的

从关系矩阵计算
$$MR?R=?\begin{array}{cccc}0& 0& 1& 1\\ 0& 0& 1& 1\\ 0& 0& 0& 1\\ 0& 0& 0& 0\end{array}???\begin{array}{cccc}0& 0& 1& 1\\ 0& 0& 1& 1\\ 0& 0& 0& 1\\ 0& 0& 0& 0\end{array}?=?\begin{array}{cccc}0& 0& 0& 1\\ 0& 0& 0& 1\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}?$$

因为M _{R $?$ R} $\le$M_R

所以是可传递的

第四题 复合关系

R₁，R₂的关系矩阵
$$R_1=?\begin{array}{cccc}1& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}?R_2=?\begin{array}{cccc}0& 0& 0& 1\\ 0& 0& 1& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 0\end{array}?$$

$$R_1?R_2=?\begin{array}{cccc}1& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}???\begin{array}{cccc}0& 0& 0& 1\\ 0& 0& 1& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 0\end{array}?=?\begin{array}{cccc}0& 0& 1& 1\\ 0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}?$$

$$R_2?R_1=?\begin{array}{cccc}0& 0& 0& 1\\ 0& 0& 1& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 0\end{array}???\begin{array}{cccc}1& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}?=?\begin{array}{cccc}0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 0& 0\end{array}?$$

$$R_1^2=?\begin{array}{cccc}1& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}???\begin{array}{cccc}1& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}?=?\begin{array}{cccc}1& 1& 0& 1\\ 0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}?$$

$$R_2^3=?\begin{array}{cccc}0& 0& 0& 1\\ 0& 0& 1& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 0\end{array}???\begin{array}{cccc}0& 0& 0& 1\\ 0& 0& 1& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 0\end{array}???\begin{array}{cccc}0& 0& 0& 1\\ 0& 0& 1& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 0\end{array}?=?\begin{array}{cccc}0& 0& 0& 0\\ 0& 0& 1& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 0\end{array}?$$

第五题 求t( R)

R={<a,b>,<b,c>,<c,d>,<d,c><b,e>,<e,e>}

R的关系矩阵
$$M=?\begin{array}{ccccc}0& 1& 0& 0& 0\\ 0& 0& 1& 0& 1\\ 0& 0& 0& 1& 0\\ 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 1\end{array}?$$
自反闭包r(R )，将主对角线补齐即可
$$Mr(R)=?\begin{array}{ccccc}1& 1& 0& 0& 0\\ 0& 1& 1& 0& 1\\ 0& 0& 1& 1& 0\\ 0& 0& 1& 1& 0\\ 0& 0& 0& 0& 1\end{array}?$$
对称闭包s(R )，将不成对的1补全
$$Ms(R)=?\begin{array}{ccccc}0& 1& 0& 0& 0\\ 1& 0& 1& 0& 1\\ 0& 1& 0& 1& 0\\ 0& 0& 1& 0& 0\\ 0& 1& 0& 0& 1\end{array}?$$

WarShall求t(R)，从i列计算，j行有为1的，将第i行加到j行
$$M=?\begin{array}{ccccc}0& 1& 0& 0& 0\\ 0& 0& 1& 0& 1\\ 0& 0& 0& 1& 0\\ 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 1\end{array}?M12=?\begin{array}{ccccc}0& 1& 1& 0& 1\\ 0& 0& 1& 0& 1\\ 0& 0& 0& 1& 0\\ 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 1\end{array}?$$

$$M13=?\begin{array}{ccccc}0& 1& 1& 1& 1\\ 0& 0& 1& 0& 1\\ 0& 0& 0& 1& 0\\ 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 1\end{array}?M23=?\begin{array}{ccccc}0& 1& 1& 1& 1\\ 0& 0& 1& 1& 1\\ 0& 0& 0& 1& 0\\ 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 1\end{array}?M43=?\begin{array}{ccccc}0& 1& 1& 1& 1\\ 0& 0& 1& 1& 1\\ 0& 0& 0& 1& 0\\ 0& 0& 1& 1& 0\\ 0& 0& 0& 0& 1\end{array}?$$

$$M14=?\begin{array}{ccccc}0& 1& 1& 1& 1\\ 0& 0& 1& 1& 1\\ 0& 0& 1& 1& 0\\ 0& 0& 1& 1& 0\\ 0& 0& 0& 0& 1\end{array}?M15=?\begin{array}{ccccc}0& 1& 1& 1& 1\\ 0& 0& 1& 1& 1\\ 0& 0& 1& 1& 0\\ 0& 0& 1& 1& 0\\ 0& 0& 0& 0& 1\end{array}?$$

最后的M15就是传递闭包

第六题 求表达式

R的关系矩阵
$$M=?\begin{array}{cccccc}0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 1& 0\\ 1& 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}?M{R}^2=?\begin{array}{cccccc}0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 1& 0& 1& 0& 1& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}?M{R}^3=?\begin{array}{cccccc}0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 1& 0& 1& 0& 1& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}?$$

$$t(R)=?\begin{array}{cccccc}1& 0& 0& 0& 1& 0\\ 0& 1& 0& 0& 1& 0\\ 1& 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 1& 0\\ 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 1\end{array}?s(R)=?\begin{array}{cccccc}0& 0& 1& 0& 1& 0\\ 0& 0& 0& 1& 1& 0\\ 1& 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 1& 0\\ 1& 1& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}?r(R)=?\begin{array}{cccccc}0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 1& 0\\ 1& 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}?$$

r(R)步骤和第5题一致

第七题 求关系图等价类

由关系图可知

A₀={a,b}，A₁={c,d}所组成的所有序偶都在R中

所以R的等价类有A₀,B₀

第八题 写出序偶与哈斯图

(1) R={

<1,1><1,2>,<1,3>,<1,4>,<1,6>,<1,8>,<1,12>,<1,24>

<2,2><2,4>,<2,6>,<2,8>,<2,12>,<2,24>

< 3,3>,< 3,6>,< 3,12>,< 3,24>,<4,4>,<4,8>,<4,12>,<4,24>

<6,6>,<6,12>,<6,24>,<8,8>,<8,24>,<12,12>,<12,24>,<24,24>

}

注：假装没有看到箭头

(2)

R={

<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<1,7>,<1,8>,<1,9>,<1,10>,<1,11>,<1,12>

<2,2><2,4>,<2,6>,<2,8>,<2,12>,< 3,3>,< 3,6>,< 3,9>,< 3,12>

<4,4>,<4,8>,<4,12>,<5,5>,<5,10>,<6,6>,<6,12>

<7,7>,<8,8>,<9,9>,<10,10><11,11>,<12,12>

}