一、关系矩阵

---

A = { a 1 , a 2 , ⋯   , a n } , R ⊆ A × A A = \{ a_1, a_2 , \cdots , a_n \} , R \subseteq A \times A A={a1​,a2​,⋯,an​},R⊆A×A

$R$ 使用 关系矩阵 表示 : $M(R)=(r_{ij}{)}_{n\times n}$

关系矩阵取值 : $M(R)(i,j)=r_{ij}=\{\begin{array}{ll}1,& a_{i}R{a}_j\\ 0,& 无关系\end{array}$

关系矩阵定义说明 :

$A$ 是个 $n$ 元集 ( 集合中有 $n$ 个元素 ) , $R$ 是$A$ 上的二元关系 , $R$ 的关系矩阵是 $n\times n$ 的方阵 , 第 $i$ 行第 $j$ 列位置的元素 $r_{ij}$ 取值只能是 $0$ 或 $1$ ;

关系矩阵取值说明 :

如果 $r_{ij}=1$ , 则说明 $A$ 集合中 第 $i$ 个元素与第 $j$ 个元素具有关系 $R$ , 记作 : $a_{i}R{a}_j$ ;

如果 $r_{ij}=0$ , 则说明 $A$ 集合中 第 $i$ 个元素与第 $j$ 个元素没有关系 $R$ ;

关系矩阵本质 : 关系矩阵中 , 每一行对应着 $A$ 集合中的元素 , 每一列也对应着 $A$ 集合中的元素 , 行列交叉的位置的值 ( $0$ 或 $1$ ) 表示 $A$ 集合中第 $i$ 个元素与第 $j$ 个元素构成的有序对是否有关系 $R$ ;

二、关系矩阵示例

---

A = { a , b , c } A = \{ a, b, c \} A={a,b,c}

R 1 = { < a , a > , < a , b > , < b , a > , < b , c > } R_1 = \{ <a, a>, <a,b> , <b,a> , <b,c> \} R1​={<a,a>,<a,b>,<b,a>,<b,c>}

R 2 = { < a , b > , < a , c > , < b , c > } R_2 = \{ <a,b> , <a,c> , <b,c> \} R2​={<a,b>,<a,c>,<b,c>}

使用关系矩阵表示上述 $R_1,R_2$ 两个关系 :

R 1 = { < a , a > , < a , b > , < b , a > , < b , c > } R_1 = \{ <a, a>, <a,b> , <b,a> , <b,c> \} R1​={<a,a>,<a,b>,<b,a>,<b,c>} 其中 :

• $<a,a>$ : $a$ 是第 $1$ 个元素 , $a$ 是第 $1$ 个元素 , 第 $1$ 行第 $1$ 列元素是 $1$
• $<a,b>$ : $a$ 是第 $1$ 个元素 , $b$ 是第 $2$ 个元素 , 第 $1$ 行第 $2$ 列元素是 $1$
• $<b,a>$ : $b$ 是第 $2$ 个元素 , $a$ 是第 $1$ 个元素 , 第 $2$ 行第 $1$ 列元素是 $1$
• $<b,c>$ : $b$ 是第 $2$ 个元素 , $c$ 是第 $3$ 个元素 , 第 $2$ 行第 $3$ 列元素是 $1$
• 其余全是 $0$

$M(R_1)=\left[\begin{array}{ccc}1& 1& 0\\ & & \\ 1& 0& 1\\ & & \\ 0& 0& 0\end{array}\right]$

R 2 = { < a , b > , < a , c > , < b , c > } R_2 = \{ <a,b> , <a,c> , <b,c> \} R2​={<a,b>,<a,c>,<b,c>} 其中 :

• $<a,b>$ : $a$ 是第 $1$ 个元素 , $b$ 是第 $2$ 个元素 , 第 $1$ 行第 $2$ 列元素是 $1$
• $<a,c>$ : $a$ 是第 $1$ 个元素 , $c$ 是第 $3$ 个元素 , 第 $1$ 行第 $3$ 列元素是 $1$
• $<b,c>$ : $b$ 是第 $2$ 个元素 , $c$ 是第 $3$ 个元素 , 第 $2$ 行第 $3$ 列元素是 $1$
• 其余全是 $0$

$M(R_2)=\left[\begin{array}{ccc}0& 1& 1\\ & & \\ 0& 0& 1\\ & & \\ 0& 0& 0\end{array}\right]$

三、关系矩阵性质

---

有序对集合表达式 与 关系矩阵 可以唯一相互确定

性质一 : 逆运算相关性质

$M(R^{-1})=(M(R){)}^T$

$M(R^{-1})$ 关系的逆 的 关系矩阵
与
$(M(R){)}^T$ 关系矩阵 的 逆
这两个矩阵是相等的 ;

性质二 : 合成运算相关性质

$M(R_1\circ R_2)=M(R_2)\bullet M(R_1)$

$\bullet$ 是矩阵的 逻辑乘法 , 计算 矩阵 $r_{ij}$ 的值 第 $i$ 行 乘以 第 $j$ 列 , 逐位 逻辑相乘 , 再将逻辑相乘结果再 逻辑相加 ;

上述 逻辑乘法使用 $\wedge$ 运算 , 逻辑加法使用 $\vee$ 运算 ;

四、关系矩阵运算

---

A = { a , b , c } A = \{ a, b, c \} A={a,b,c}

R 1 = { < a , a > , < a , b > , < b , a > , < b , c > } R_1 = \{ <a, a>, <a,b> , <b,a> , <b,c> \} R1​={<a,a>,<a,b>,<b,a>,<b,c>}

R 2 = { < a , b > , < a , c > , < b , c > } R_2 = \{ <a,b> , <a,c> , <b,c> \} R2​={<a,b>,<a,c>,<b,c>}

在上面的示例中 , 已经求出两个关系矩阵 ;

$M(R_1)=\left[\begin{array}{ccc}1& 1& 0\\ & & \\ 1& 0& 1\\ & & \\ 0& 0& 0\end{array}\right]$ , $M(R_2)=\left[\begin{array}{ccc}0& 1& 1\\ & & \\ 0& 0& 1\\ & & \\ 0& 0& 0\end{array}\right]$

1. 求 $M(R^{-1}),M(R_2^{-1})$

直接将矩阵转置 , 即可获取 关系的逆的关系矩阵 ;

$M(R_1^{-1})=(M(R_1){)}^T=\left[\begin{array}{ccc}1& 1& 0\\ & & \\ 1& 0& 0\\ & & \\ 0& 1& 0\end{array}\right]$

$M(R_2^{-1})=(M(R_2){)}^T=\left[\begin{array}{ccc}0& 0& 0\\ & & \\ 1& 0& 0\\ & & \\ 1& 1& 0\end{array}\right]$

R 1 − 1 = { < a , a > , < a , b > , < b , a > , < c , b > } R_1^{-1} = \{ <a, a> , <a, b> , <b,a> , <c,b> \} R1−1​={<a,a>,<a,b>,<b,a>,<c,b>}

R 2 − 1 = { < b , a > , < c , a > , < c , b > } R_2^{-1} = \{ <b, a> , <c,a> , <c,b> \} R2−1​={<b,a>,<c,a>,<c,b>}

2. 求 $M(R_1\circ R_1)$

$M(R_1\circ R_1)=M(R_1)\bullet M(R_1)$

其中的 $\bullet$ 是两个矩阵的逻辑乘法 , 加法使用 $\vee$ , 乘法使用 $\wedge$

$M(R_1)\bullet M(R_1)=\left[\begin{array}{ccc}1& 1& 0\\ & & \\ 1& 0& 1\\ & & \\ 0& 0& 0\end{array}\right]\bullet \left[\begin{array}{ccc}1& 1& 0\\ & & \\ 1& 0& 1\\ & & \\ 0& 0& 0\end{array}\right]=\left[\begin{array}{ccc}1& 1& 1\\ & & \\ 1& 1& 0\\ & & \\ 0& 0& 0\end{array}\right]$

矩阵的逻辑乘法 : 结果矩阵的第 $i$ 行 , 第 $j$ 列元素的值为 , 第 $i$ 行的三个元素 分别与上第 $j$ 列的三个元素 , 然后三个结果进行或运算 , 最终结果就是 矩阵的第 $i$ 行 , 第 $j$ 列元素的值 ;

R 1 ∘ R 1 = { < a , a > , < a , b > , < a , c > , < b , a > , < b , b > } R_1 \circ R_1 = \{ <a,a> , <a,b> , <a,c> , <b,a>, <b,b> \} R1​∘R1​={<a,a>,<a,b>,<a,c>,<b,a>,<b,b>}

3. 求 $M(R_1\circ R_2)$

$M(R_1\circ R_2)=M(R_2)\bullet M(R_1)$

其中的 $\bullet$ 是两个矩阵的逻辑乘法 , 加法使用 $\vee$ , 乘法使用 $\wedge$

特别注意 , 合成的顺序是逆序合成 , 后者关系矩阵在前 , 前者关系矩阵在后

$M(R_1)\bullet M(R_2)=\left[\begin{array}{ccc}0& 1& 1\\ & & \\ 0& 0& 1\\ & & \\ 0& 0& 0\end{array}\right]\bullet \left[\begin{array}{ccc}1& 1& 0\\ & & \\ 1& 0& 1\\ & & \\ 0& 0& 0\end{array}\right]=\left[\begin{array}{ccc}1& 0& 1\\ & & \\ 0& 0& 0\\ & & \\ 0& 0& 0\end{array}\right]$

矩阵的逻辑乘法 : 结果矩阵的第 $i$ 行 , 第 $j$ 列元素的值为 , 第 $i$ 行的三个元素 分别与上第 $j$ 列的三个元素 , 然后三个结果进行或运算 , 最终结果就是 矩阵的第 $i$ 行 , 第 $j$ 列元素的值 ;

R 1 ∘ R 2 = { < a , a > , < a , c > } R_1 \circ R_2 = \{ <a,a>, <a,c> \} R1​∘R2​={<a,a>,<a,c>}

五、关系图

---

A = { a 1 , a 2 , ⋯   , a n } , R ⊆ A × A A = \{ a_1, a_2 , \cdots , a_n \} , R \subseteq A \times A A={a1​,a2​,⋯,an​},R⊆A×A

$R$ 的关系图 :

• 顶点 : $\circ$ 表示 $A$ 集合中的元素 ;
• 有向边 : $\to$ 表示 $R$ 中的元素 ;
• $a_{i}R{a}_j$ 就是从顶点 $a_i$ 到 顶点 $a_j$ 的有向边 $<a_i,a_j>$ ;

六、关系图示例

---

A = { a , b , c } A = \{ a, b, c \} A={a,b,c}

R 1 = { < a , a > , < a , b > , < b , a > , < b , c > } R_1 = \{ <a, a> , <a,b> , <b,a> , <b,c> \} R1​={<a,a>,<a,b>,<b,a>,<b,c>} 关系图表示方式 :

R 2 = { < a , b > , < a , c > , < b , c > } R_2 = \{ <a,b>, <a,c>, <b,c> \} R2​={<a,b>,<a,c>,<b,c>} 使用关系图表示 :

R 1 − 1 = { < a , a > , < a , b > , < b , a > , < c , b > } R_1^{-1} = \{ <a,a>, <a,b>, <b,a> , <c,b> \} R1−1​={<a,a>,<a,b>,<b,a>,<c,b>}

R 2 − 1 = { < b , a > , < c , a > , < c , b > } R_2^{-1} = \{ <b,a> , <c,a> , <c,b> \} R2−1​={<b,a>,<c,a>,<c,b>}

七、关系表示相关性质

---

$A$ 集合中的元素 , 标定次序后 , 即生成了 $A$ 上的关系 , $R\subseteq A\times A$ , 有如下性质 :

• 关系图 $G(R)$ 与 关系的 $R$ 的集合表达式 ( 有序对集合 ) , 可以 唯一确定 ;
• 关系 $R$ 的集合表达式 , 关系矩阵 $M(R)$ , 关系图 $G(R)$ , 都是一一对应的 ;

$R\subseteq A\times B$

• 集合 $A$ 中有 $n$ 个元素 , $|A|=n$
• 集合 $B$ 中有 $m$ 个元素 , $|B|=m$
• 关系矩阵 $M(R)$ 是 $n\times m$ 阶矩阵 ;
• 关系图 $G(R)$ 有向边都是从 $A$ 集合中的元素 指向 $B$ 集合中的元素