最后更新: 2025-01-22 08:28 查看: 41 次反馈刷题

关系的运算

从 $A$ 到 $B$ 的二元关系是 $A \times B$ 的子集。因为关系也是一个集合，所以有关集合的并，交，差，补运算以及相应的性质同样适用于关系。定义二元关系的运算如下。

定义2．6 设 $R_1$ 和 $R_2$ 是从 $A$ 到 $B$ 的两个二元关系，对于 $a \in A, b \in B$ ，定义：

$$
\begin{aligned}
& R_1 \cup R_2:(a, b) \in R_1 \cup R_2 \text { 当且仅当 }(a, b) \in R_1 \text { 或 }(a, b) \in R_2 ; \\
& R_1 \cap R_2:(a, b) \in R_1 \cap R_2 \text { 当且仅当 }(a, b) \in R_1 \text { 且 }(a, b) \in R_2 ; \\
& R_1-R_2:(a, b) \in\left(R_1-R_2\right) \text { 当且仅当 }(a, b) \in R_1 \text { 且 }(a, b) \notin R_2^{\prime} ; \\
& \left.\overline{R_1}: a \overline{R_1} b \text { 当且仅当 }(a, b) \notin R_1 \text { (其中 } \overline{R_1}=(A \times B)-R\right)
\end{aligned}
$$

然而，二元关系又是一种特殊的集合，构成关系的元素是有序对。所以下面又定义关系的另一些运算，通过这些运算可以由已知关系产生新的关系。

逆运算
对于表 2．1，\｛（李洋，程序设计），（苏展，数学），（王净晶，程序设计），（李洋，政治）， （徐智婷，物理）$\}$ 反映了学生选课情况，而 \｛（程序设计，李洋），（数学，苏展），（程序设计，王净晶），（政治，李洋），（物理，徐智婷）\} 则反映了课程被学生选修的情况。这样通过关系的逆运算，由给定关系产生其逆关系。
定义2．7 设 $R$ 是从 $A$ 到 $B$ 的二元关系，则从 $B$ 到 $A$ 的二元关系记为 $R^{-1}$ ，定义为：$R^{-1}=\{(b, a)(a$ ， b）$\in R$ \} 称为 $R$ 的逆关系。

例如，$R=\{(1,2),(2,3),(1,3)\}$ ，则 $R^{-1}=\{(2,1),(3,2),(3,1)\}$ 。
定理 2.1 设 $R, R_1, R_2$ 是从 $A$ 到 $B$ 的二元关系，则
（1）$\left(R^{-1}\right)^{-1}=R_{\circ}$
（2）$\left(R_1 \cup R_2\right)^{-1}=R_1^{-1} \cup R_2{ }^{-1}$ 。
（3）$\left(R_1 \cap R_2\right)^{-1}=R_1^{-1} \cap R_2{ }^{-1}$ 。
（4）$(A \times B)^{-1}=B \times A$ 。
（5）$\varnothing^{-1}=\varnothing$ 。
（6） $\bar{R}^{-1}=\overline{R^{-1}}$ 。
（7）$\left(R_1-R_2\right)^{-1}=R_1^{-1}-R_2^{-1}$ 。
（8）若 $R_1 \subseteq R_2$ 则 $R_1^{-1} \subseteq R_2^{-1}$ 。
证明：（1）$(a, b) \in R \Leftrightarrow(b, a) \in R^{-1} \Leftrightarrow(a, b) \in\left(R^{-1}\right)^{-1}$ ，则 $\left(R^{-1}\right)^{-1}=R$ 。
（2）$(a, b) \in\left(R_1 \cup R_2\right)^{-1} \Leftrightarrow(b, a) \in R_1 \cup R_2 \Leftrightarrow(b, a) \in R_1$ 或者 $(b, a) \in R_2 \Leftrightarrow(a, b) \in R_1^{-1}$ 或者 $(a$ ， b）$\in R_2^{-1} \Leftrightarrow(a, b) \in R_1^{-1} \cup R_2^{-1}$ ；因此 $\left(R_1 \cup R_2\right)^{-1}=R_1^{-1} \cup R_2^{-1}$ 。
（7）因为 $R_1-R_2=R_1 \cap \overline{R_2}$ ，所以 $\left(R_1-R_2\right)^{-1}=\left(R_1 \cap \overline{R_2}\right)^{-1}=R_1^{-1} \cap \overline{R_2}=R_1^{-1} \cap \overline{R_2^{-1}}=R_1^{-1}-$ $R_2{ }^{-1}$ 。

其他留给读者自行证明。
由定理 2.1 的证明可知，因为关系是集合，所以证明关系运算表达式相等可以采用证明集合运算表达式的方法。通过证明左式 $\subseteq$ 右式以及右式 $\subseteq$ 左式，则可以推导出左式 $=$ 右式；或者通过等式的推导来进行证明。

定理 2.2 设 $R$ 是 $A$ 上的二元关系，则 $R$ 是对称的当且仅当 $R=R^{-1}$ 。
要证明 $R$ 是对称的，就要根据对称的定义，对于任意的 $(a, b) \in R$ ，证明 $(b, a) \in R$ 成立。证明留作习题。

复合运算
先举一个例子，兄妹关系为 $R_1$ ，母子关系为 $R_2$ ，如果 $(a, b) \in R_1,(b, c) \in R_2$ ，也就是说 $a$ 与 $b$ 是兄妹关系，而 $b$ 与 $c$ 有母子关系，则在 $a$ 与 $c$ 之间通过 $b$ 可以建立一种新的关系：舅舅和外甥的关系，这样在 $R_1$ 和 $R_2$ 的基础上建立新的关系称为复合关系，记为 $R_1 \circ R_2$ 。 $a$ 与 $c$ 之间有舅甥关系，记为 $(a, c) \in R_1 \circ R_2$ 。从 $R_1$ 和 $R_2$ 得到 $R_1 \circ R_2$ 的运算称为复合运算。

定义 2.8 设 $R_1$ 是从 $A$ 到 $B$ 的二元关系，$R_2$ 是从 $B$ 到 $C$ 的二元关系，则从 $A$ 到 $C$ 的二元关系记为 $R_1 \circ R_2$ ，定义为：$R_1 \circ R_2=\left\{(a, c) \mid a \in A, c \in C\right.$ ，并且存在 $b \in B$ ，使得 $\left.(a, b) \in R_1,(b, c) \in R_2\right\}$ ，称为 $R_1$ 和 $R_2$ 的复合关系。

例2．9 设 $A=\{p, q, r, s\}, B=\{a, b\}, C=\{1,2,3,4\}$ ，且从 $A$ 到 $B$ 的关系 $R_1=\{(p, a),(p, b),(q, b)$ ， $(r, a),(s, a)\}$ ，从 $B$ 到 $C$ 的关系 $R_2=\{(a, 1),(a, 2),(b, 4)\}$ ，则从 $A$ 到 $C$ 的复合关系 $R_1 \circ R_2=\{(p, 1),(p, 2)$ ， $(p, 4),(q, 4),(r, 1),(r, 2),(s, 1),(s, 2)\}$ 。

显然，$R_1$ 和 $R_2$ 复合的前提是 $R_1$ 是从 $A$ 到 $B$ 的二元关系，$R_2$ 是从 $B$ 到 $C$ 的二元关系。如果Ran $R_1 \cap \operatorname{Dom} R_2=\varnothing$ ，则 $R_1 \circ R_2$ 是空关系。

定理 2.3 设 $R_1$ 是从 $A$ 到 $B$ 的二元关系，$R_2$ 是从 $B$ 到 $C$ 的二元关系，$R_3$ 是从 $C$ 到 $D$ 的二元关系，则有 $R_1 \circ\left(R_2 \circ R_3\right)=\left(R_1 \circ R_2\right) \circ R_3$（结合律）。

证明：设 $(a, d) \in\left(R_1 \circ R_2\right) \circ R_3$ ，则存在 $c$ 使 $(a, c) \in R_1 \circ R_2,(c, d) \in R_3$ ；因为 $(a, c) \in R_1 \circ R_2$ ，则存在 $b$ 使 $(a, b) \in R_1$ ，且 $(b, c) \in R_2$ ；又由 $(b, c) \in R_2,(c, d) \in R_3$ ，则 $(b, d) \in R_2 \circ R_3$ ；所以 $(a, d) \in$ $R_1 \circ\left(R_2 \circ R_3\right)$ ，由此得到 $\left(R_1 \circ R_2\right) \circ R_3 \subseteq R_1 \circ\left(R_2 \circ R_3\right)$ 。同理可证 $R_1 \circ\left(R_2 \circ R_3\right) \subseteq\left(R_1 \circ R_2\right)$ 。

复合运算不满足交换律，即，在一般情况下，$R_1 \circ R_2 \neq R_2 \circ R_1$ 。
幂运算
设 $R$ 是 $A$ 上的一个二元关系，$R \circ R$ 记为 $R^2, ~ R \circ R \circ R$ 记为 $R^3$ 等，于是我们可以定义 $R$ 的幂运算。
定义2．9 设 $R$ 是 $A$ 上的二元关系，$n \in N, R$ 的 $n$ 次幂记为 $R^n$ ，定义如下：
（1）$R^0$ 是 $A$ 上的恒等关系，即 $R^0=\{(a, a) \mid a \in A\}$ ，记为 $I_A ; R^1=R$ 。
（2）$R^{n+1}=R^n \circ R$ 。
定理 2.4 设 $R$ 是 $A$ 上的二元关系，$m, n \in N$ ，则
（1）$R^m \circ R^n=R^{m+n}$
（2）$\left(R^m\right)^n=R^{m n}$
证明留作习题，用归纳法证明。
以上所述由关系的并，交，逆和复合运算得到新的关系都可以用关系矩阵来表示。
设 $A=\left\{a_1, a_2, \ldots, a_n\right\}, B=\left\{b_1, b_2, \ldots, b_m\right\}, ~ R_1$ 和 $R_2$ 都是 $A$ 到 $B$ 的二元关系，$n \times m$ 阶矩阵 $M_{R_1}=\left(x_{i j}\right)$ 和 $M_{R_2}=\left(y_{i j}\right)$ 分别是 $R_1$ 和 $R_2$ 的关系矩阵（关于 $A$ 和 $B$ 中元素次序），那么 $M_{R_1 \cup R_2}=\left(z_{i j}\right)$ ， $M_{R_1 \cap R_2}=\left(w_{i j}\right)$ ，其中 $z_{i j}=x_{i j} \vee y_{i j}, w_{i j}=x_{i j} \wedge y_{i j}$ ，运算规则如下所示。
 ![图片](/uploads/2025-01/6fb9ab.jpg)
 
 
 例 2.10 设 $A=\{2,3,4\}, B=\{1,3,5,7\}, R_1=\{(2,3),(2,5),(2,7),(3,5),(3,7),(4,5),(4,7)\}$ ， $R_2=\{(2,5),(3,3),(4,1),(4,7)\}$ 。则 $R_1$ 和 $R_2$ 的关系矩阵以及 $R_1$ 和 $R_2$ 的并和交的关系矩阵如下。
 
  ![图片](/uploads/2025-01/667d70.jpg)
   ![图片](/uploads/2025-01/82877a.jpg)
   
   设 $M_R$ 是从 $A$ 到 $B$ 的二元关系 $R$ 的关系矩阵，那么逆关系 $R^{-1}$ 的关系矩阵 $M_{R^{-1}}=M_R^T$ ，其中 $M_R^T$ 是 $M_R$ 的转置矩阵。例 2.10 中 $R_1$ 的逆关系 $R_1^{-1}$ 的关系矩阵为
    ![图片](/uploads/2025-01/4b80e2.jpg)
    
    设 $A=\left\{a_1, a_2, \ldots, a_n\right\}, ~ B=\left\{b_1, b_2, \cdots, b_m\right\}, C=\left\{c_1, c_2, \cdots, c_r\right\}, R_1$ 是 $A$ 到 $B$ 的二元关系，其关系矩阵 $M_{R_1}=\left(x_{i j}\right)$ 是 $n \times m$ 阶矩阵，$R_2$ 是 $B$ 到 $C$ 的二元关系，其关系矩阵 $M_{R_2}=\left(y_{i j}\right)$ 是 $m \times r$ 阶矩阵，则 $R_1$ 和 $R_2$ 的复合关系 $R_1 \circ R_2$ 的关系矩阵 $M_{R_1 \circ R_2}=\left(z_{i j}\right)$ 是 $n \times r$ 阶矩阵。其中

$$
z_{i j}=\sum_{k=1}^m\left(x_{i k} \wedge y_{k j}\right) \quad i=1,2, \cdots, n, j=1,2, \cdots, r 。
$$

下面介绍一种很有实际用途的关系运算——投影运算。

投影运算
在关系数据库中，用关系来描述数据时还常常应用投影运算进行数据操作。
定义2．10 设 $R$ 是 $A_1, A_2, \cdots, A_n$ 的 $n$ 元关系，定义 $R$ 在 $A_{i_1}, A_{i_2}, \cdots, A_{i_m}$ 上的投影是一个 $m$ 元关系，它是通过选取 $R$ 中的每个有序 $n$ 元组的第 $i_1$ ，第 $i_2, \cdots$ ，第 $i_m$ 个分量组成有序 $m$ 元组作为 $m$元关系中的元素，这个投影记为 $\Pi_{A_{i_1}, A_{i_2}, \ldots, A_{i_m}}(R)$ 。

例 2.11 设 $R$ 定义如下。
 ![图片](/uploads/2025-01/c8a111.jpg)
 则投影 $\Pi_{A C}(R)$ 如下。
  ![图片](/uploads/2025-01/72b982.jpg)

刷题

做题，是检验是否掌握数学的唯一真理

上一篇：关系的性质

下一篇：关系数据库的一个实例

本文对您是否有用？有用 (0) 无用 (0)