下面是习题与解析

第一题 序偶与类型

(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> $\notin$∈/​ R ，<2,2>$\notin$∈/​R R既不是自反，也不是反自反

关系矩阵如下
$R=\begin{bmatrix} 0&1&1&1\\ 1&1&1&1\\ 1&1&1&1\\ 1&1&1&1 \end{bmatrix}$R=⎣⎢⎢⎡​0111​1111​1111​1111​⎦⎥⎥⎤​
可以看出，R为对称矩阵，是对称的

$M R\circ R=\begin{bmatrix} 0&1&1&1\\ 1&1&1&1\\ 1&1&1&1\\ 1&1&1&1 \end{bmatrix} \circ \begin{bmatrix} 0&1&1&1\\ 1&1&1&1\\ 1&1&1&1\\ 1&1&1&1 \end{bmatrix} =\begin{bmatrix} 1&1&1&1\\ 1&1&1&1\\ 1&1&1&1\\ 1&1&1&1 \end{bmatrix}$MR∘R=⎣⎢⎢⎡​0111​1111​1111​1111​⎦⎥⎥⎤​∘⎣⎢⎢⎡​0111​1111​1111​1111​⎦⎥⎥⎤​=⎣⎢⎢⎡​1111​1111​1111​1111​⎦⎥⎥⎤​
因为 M ~R$\circ$∘ R~ $\geq$≥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> $\notin$∈/​ R,所以是反自反的

关系矩阵
$R=\begin{bmatrix} 0&1&1&1\\ 0&0&1&1\\ 0&0&0&1\\ 0&0&0&0 \end{bmatrix}$R=⎣⎢⎢⎡​0000​1000​1100​1110​⎦⎥⎥⎤​
显然是不对称的
$MR\circ R=\begin{bmatrix} 0&1&1&1\\ 0&0&1&1\\ 0&0&0&1\\ 0&0&0&0 \end{bmatrix} \circ \begin{bmatrix} 0&1&1&1\\ 0&0&1&1\\ 0&0&0&1\\ 0&0&0&0 \end{bmatrix} =\begin{bmatrix} 0&0&1&1\\ 0&0&0&1\\ 0&0&0&0\\ 0&0&0&0 \end{bmatrix}$MR∘R=⎣⎢⎢⎡​0000​1000​1100​1110​⎦⎥⎥⎤​∘⎣⎢⎢⎡​0000​1000​1100​1110​⎦⎥⎥⎤​=⎣⎢⎢⎡​0000​0000​1000​1100​⎦⎥⎥⎤​
因为M _{R $\circ$∘ R}$\leq$≤M_R，所以是可传递的

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

R的关系矩阵
$R=\begin{bmatrix} 1&0&0&1\\ 0&0&0&0\\ 1&1&0&1\\ 0&0&1&0 \end{bmatrix}$R=⎣⎢⎢⎡​1010​0010​0001​1010​⎦⎥⎥⎤​
R的关系图

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

从关系矩阵中，<2,3><3,2>对称，所以可以看出既不是对称，也不是反对称
$MR\circ R=\begin{bmatrix} 1&0&0&1\\ 0&0&0&0\\ 1&1&0&1\\ 0&0&1&0 \end{bmatrix} \circ \begin{bmatrix} 1&0&0&1\\ 0&0&0&0\\ 1&1&0&1\\ 0&0&1&0 \end{bmatrix} =\begin{bmatrix} 1&0&1&1\\ 0&0&0&0\\ 1&0&1&1\\ 1&1&0&1 \end{bmatrix}$MR∘R=⎣⎢⎢⎡​1010​0010​0001​1010​⎦⎥⎥⎤​∘⎣⎢⎢⎡​1010​0010​0001​1010​⎦⎥⎥⎤​=⎣⎢⎢⎡​1011​0001​1010​1011​⎦⎥⎥⎤​
所以M _{R $\circ$∘ R}$\nleq$≰M_R，所以不是可传递的

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

R的关系图

R的关系矩阵
$R=\begin{bmatrix} 0&0&1&1\\ 0&0&1&1\\ 0&0&0&1\\ 0&0&0&0 \end{bmatrix}$R=⎣⎢⎢⎡​0000​0000​1100​1110​⎦⎥⎥⎤​
从关系图可知

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

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

从关系矩阵计算
$MR \circ R=\begin{bmatrix} 0&0&1&1\\ 0&0&1&1\\ 0&0&0&1\\ 0&0&0&0 \end{bmatrix} \circ \begin{bmatrix} 0&0&1&1\\ 0&0&1&1\\ 0&0&0&1\\ 0&0&0&0 \end{bmatrix} =\begin{bmatrix} 0&0&0&1\\ 0&0&0&1\\ 0&0&0&0\\ 0&0&0&0 \end{bmatrix}$MR∘R=⎣⎢⎢⎡​0000​0000​1100​1110​⎦⎥⎥⎤​∘⎣⎢⎢⎡​0000​0000​1100​1110​⎦⎥⎥⎤​=⎣⎢⎢⎡​0000​0000​0000​1100​⎦⎥⎥⎤​

因为M _{R $\circ$∘ R}$\leq$≤M_R

所以是可传递的

第四题 复合关系

R₁，R₂的关系矩阵
$R1=\begin{bmatrix} 1&1&0&0\\ 0&0&0&1\\ 0&0&0&0\\ 0&0&0&0 \end{bmatrix} R2=\begin{bmatrix} 0&0&0&1\\ 0&0&1&1\\ 0&1&0&0\\ 0&0&0&0 \end{bmatrix}$R1=⎣⎢⎢⎡​1000​1000​0000​0100​⎦⎥⎥⎤​R2=⎣⎢⎢⎡​0000​0010​0100​1100​⎦⎥⎥⎤​

$R1\circ R2=\begin{bmatrix} 1&1&0&0\\ 0&0&0&1\\ 0&0&0&0\\ 0&0&0&0 \end{bmatrix} \circ \begin{bmatrix} 0&0&0&1\\ 0&0&1&1\\ 0&1&0&0\\ 0&0&0&0 \end{bmatrix} =\begin{bmatrix} 0&0&1&1\\ 0&0&0&0\\ 0&0&0&0\\ 0&0&0&0 \end{bmatrix}$R1∘R2=⎣⎢⎢⎡​1000​1000​0000​0100​⎦⎥⎥⎤​∘⎣⎢⎢⎡​0000​0010​0100​1100​⎦⎥⎥⎤​=⎣⎢⎢⎡​0000​0000​1000​1000​⎦⎥⎥⎤​

$R2\circ R1= \begin{bmatrix} 0&0&0&1\\ 0&0&1&1\\ 0&1&0&0\\ 0&0&0&0 \end{bmatrix} \circ \begin{bmatrix} 1&1&0&0\\ 0&0&0&1\\ 0&0&0&0\\ 0&0&0&0 \end{bmatrix}= \begin{bmatrix} 0&0&0&0\\ 0&0&0&0\\ 0&0&0&1\\ 0&0&0&0 \end{bmatrix}$R2∘R1=⎣⎢⎢⎡​0000​0010​0100​1100​⎦⎥⎥⎤​∘⎣⎢⎢⎡​1000​1000​0000​0100​⎦⎥⎥⎤​=⎣⎢⎢⎡​0000​0000​0000​0010​⎦⎥⎥⎤​

$R1^2= \begin{bmatrix} 1&1&0&0\\ 0&0&0&1\\ 0&0&0&0\\ 0&0&0&0 \end{bmatrix} * \begin{bmatrix} 1&1&0&0\\ 0&0&0&1\\ 0&0&0&0\\ 0&0&0&0 \end{bmatrix} =\begin{bmatrix} 1&1&0&1\\ 0&0&0&0\\ 0&0&0&0\\ 0&0&0&0 \end{bmatrix}$R12=⎣⎢⎢⎡​1000​1000​0000​0100​⎦⎥⎥⎤​∗⎣⎢⎢⎡​1000​1000​0000​0100​⎦⎥⎥⎤​=⎣⎢⎢⎡​1000​1000​0000​1000​⎦⎥⎥⎤​

$R2^3= \begin{bmatrix} 0&0&0&1\\ 0&0&1&1\\ 0&1&0&0\\ 0&0&0&0 \end{bmatrix} * \begin{bmatrix} 0&0&0&1\\ 0&0&1&1\\ 0&1&0&0\\ 0&0&0&0 \end{bmatrix} * \begin{bmatrix} 0&0&0&1\\ 0&0&1&1\\ 0&1&0&0\\ 0&0&0&0 \end{bmatrix} =\begin{bmatrix} 0&0&0&0\\ 0&0&1&1\\ 0&1&0&0\\ 0&0&0&0 \end{bmatrix}$R23=⎣⎢⎢⎡​0000​0010​0100​1100​⎦⎥⎥⎤​∗⎣⎢⎢⎡​0000​0010​0100​1100​⎦⎥⎥⎤​∗⎣⎢⎢⎡​0000​0010​0100​1100​⎦⎥⎥⎤​=⎣⎢⎢⎡​0000​0010​0100​0100​⎦⎥⎥⎤​

第五题 求t(R)

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

R的关系矩阵
$M=\begin{bmatrix} 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{bmatrix}$M=⎣⎢⎢⎢⎢⎡​00000​10000​01010​00100​01001​⎦⎥⎥⎥⎥⎤​
自反闭包r(R )，将主对角线补齐即可
$M~r(R)~=\begin{bmatrix} 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{bmatrix}$M r(R) =⎣⎢⎢⎢⎢⎡​10000​11000​01110​00110​01001​⎦⎥⎥⎥⎥⎤​
对称闭包s(R )，将不成对的1补全
$M~s(R)~=\begin{bmatrix} 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{bmatrix}$M s(R) =⎣⎢⎢⎢⎢⎡​01000​10101​01010​00100​01001​⎦⎥⎥⎥⎥⎤​

WarShall求t(R)，从i列计算，j行有为1的，将第i行加到j行
$M=\begin{bmatrix} 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{bmatrix} M12=\begin{bmatrix} 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{bmatrix}$M=⎣⎢⎢⎢⎢⎡​00000​10000​01010​00100​01001​⎦⎥⎥⎥⎥⎤​M12=⎣⎢⎢⎢⎢⎡​00000​10000​11010​00100​11001​⎦⎥⎥⎥⎥⎤​

$M13=\begin{bmatrix} 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{bmatrix} M23=\begin{bmatrix} 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{bmatrix} M43=\begin{bmatrix} 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{bmatrix}$M13=⎣⎢⎢⎢⎢⎡​00000​10000​11010​10100​11001​⎦⎥⎥⎥⎥⎤​M23=⎣⎢⎢⎢⎢⎡​00000​10000​11010​11100​11001​⎦⎥⎥⎥⎥⎤​M43=⎣⎢⎢⎢⎢⎡​00000​10000​11010​11110​11001​⎦⎥⎥⎥⎥⎤​

$M14=\begin{bmatrix} 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{bmatrix} M15=\begin{bmatrix} 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{bmatrix}$M14=⎣⎢⎢⎢⎢⎡​00000​10000​11110​11110​11001​⎦⎥⎥⎥⎥⎤​M15=⎣⎢⎢⎢⎢⎡​00000​10000​11110​11110​11001​⎦⎥⎥⎥⎥⎤​

最后的M15就是传递闭包

第六题 求表达式

R的关系矩阵
$M=\begin{bmatrix} 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{bmatrix} MR^2=\begin{bmatrix} 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{bmatrix} MR^3=\begin{bmatrix} 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{bmatrix}$M=⎣⎢⎢⎢⎢⎢⎢⎡​001000​000000​001000​000000​110100​000000​⎦⎥⎥⎥⎥⎥⎥⎤​MR2=⎣⎢⎢⎢⎢⎢⎢⎡​001000​000000​001000​000000​001000​000000​⎦⎥⎥⎥⎥⎥⎥⎤​MR3=⎣⎢⎢⎢⎢⎢⎢⎡​001000​000000​001000​000000​001000​000000​⎦⎥⎥⎥⎥⎥⎥⎤​

$t(R)=\begin{bmatrix} 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{bmatrix} s(R)=\begin{bmatrix} 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{bmatrix} r(R)=\begin{bmatrix} 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{bmatrix}$t(R)=⎣⎢⎢⎢⎢⎢⎢⎡​101000​010000​001000​000100​110110​000001​⎦⎥⎥⎥⎥⎥⎥⎤​s(R)=⎣⎢⎢⎢⎢⎢⎢⎡​001010​000110​101000​010010​110100​000000​⎦⎥⎥⎥⎥⎥⎥⎤​r(R)=⎣⎢⎢⎢⎢⎢⎢⎡​001000​000000​001000​000000​110100​000000​⎦⎥⎥⎥⎥⎥⎥⎤​

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>,❤️,6>,❤️,9>,❤️,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>

}