最后更新: 2026-05-24 07:15 查看: 100 次纠错评论(0) 课件开VIP

关系的运算与复合关系

## 关系的运算
**2．3．1 关系的并、交、差、补运算**
关系是特殊的集合，因此可以进行并、交、差、补等运算产生新的关系。若 $R \subseteq A \times B, S \subseteq A \times B$ ，则
$R 、 S$ 的并集：$R \bigcup S=\{(a, b) \mid(a, b) \in R$ 或 $(a, b) \in S\}$

$R 、 S$ 的交集：$R \cap S=\{(a, b) \mid(a, b) \in R \wedge(a, b) \in S\}$
$R 、 S$ 的差集：$R-S=\{(a, b) \mid(a, b) \in R \wedge(a, b) \notin S\}$
$R$ 的补集：$\sim R=A \times B-R$
 `例2.19` 设集合 $A=\{a, b, c\}$ ，集合 $B=\{1,2\}, ~ R$ 和 $S$ 均是从 $A$ 到 $B$ 的二元关系，有 $R=\{(a, 1),(b, 2),(c, 1)\}, S=\{(a, 1),(b, 1),(c, 2)\}$ ，则

$$
\begin{aligned}
& R \bigcup S=\{(a, 1),(b, 2),(c, 1),(b, 1),(c, 2)\} \\
& R \cap S=\{(a, 1)\} \\
& R-S=\{(b, 2),(c, 1)\} \\
& \sim R=\{(a, 2),(b, 1),(c, 2)\}
\end{aligned}
$$

因为关系可以用矩阵的形式表示，所以当用矩阵的形式求关系的并、交、差、补运算时，可以用如下形式表示：

$$
\begin{gathered}
\boldsymbol{M}_{R \cup S}=\boldsymbol{M}_R \vee \boldsymbol{M}_S \text { (矩阵的对应分量做逻辑析取运算) } \\
\boldsymbol{M}_{R \cap S}=\boldsymbol{M}_R \wedge \boldsymbol{M}_S \text { (矩阵的对应分量做逻辑合取运算) } \\
\boldsymbol{M}_{R-S}=\boldsymbol{M}_{R \cap \sim S}=\boldsymbol{M}_R \wedge \boldsymbol{M}_{\sim S} \\
\boldsymbol{M}_{\sim R}=\sim \boldsymbol{M}_R \text { (矩阵的对应分量做逻辑非运算) }
\end{gathered}
$$

`例2.20` 对例 2.19 中的关系运算采用矩阵的形式表示。
解：根据题意，关系 $R$ 和 $S$ 的关系矩阵分别表示为：

$$
\boldsymbol{M}_R=\left[\begin{array}{ll}
1 & 0 \\
0 & 1 \\
1 & 0
\end{array}\right], \boldsymbol{M}_S=\left[\begin{array}{ll}
1 & 0 \\
1 & 0 \\
0 & 1
\end{array}\right]
$$

则

$$
\begin{gathered}
\boldsymbol{M}_{R \cup S}=\left[\begin{array}{ll}
1 & 0 \\
1 & 1 \\
1 & 1
\end{array}\right]=\boldsymbol{M}_R \cup \boldsymbol{M}_S \\
\boldsymbol{M}_{R \cap S}=\left[\begin{array}{ll}
1 & 0 \\
0 & 0 \\
0 & 0
\end{array}\right]=\boldsymbol{M}_R \cap \boldsymbol{M}_S \\
\boldsymbol{M}_{R-S}=\left[\begin{array}{ll}
0 & 0 \\
0 & 1 \\
1 & 0
\end{array}\right]=\boldsymbol{M}_R \cap \boldsymbol{M}_{\sim S} \\
\boldsymbol{M}_{\sim R}=\left[\begin{array}{ll}
0 & 1 \\
1 & 0 \\
0 & 1
\end{array}\right]=\boldsymbol{M}_{A \times B-R}=\sim \boldsymbol{M}_R
\end{gathered}
$$

**2．3．2 关系的复合**
关系的复合运算是区别于传统集合运算的两种运算之一。
**定义2．12** 设有 3 个集合 $A, B, C, R \subseteq A \times B, S \subseteq B \times C$ ，则关系

$$
R \circ S=\{(a, c) \mid a \in A \wedge c \in C \wedge \exists b(b \in B \wedge(a, b) \in R \wedge(b, c) \in S)\}
$$

是 $A$ 到 $C$ 的关系，称为 $R$ 和 $S$ 的复合关系。
注意：在复合关系中，$R$ 的值域所属集合一定是 $S$ 的定义域所属集合，否则 $R$ 和 $S$ 不可以进行复合运算。复合运算的结果 $R \circ S$ 的定义域和 $R$ 的定义域同属于集合 $A$ ，值域就是 $S$ 的值域所属集合。

关系复合是关系最重要的一种运算，下面介绍两种方法来求解关系的复合——关系图方法和关系矩阵方法。

`例2.21`设集合 $A=\{1,2,3,4\}, B=\{2,3,4\}, C=\{1,2,3\}, ~ R=\{(2,4)$ ， $(3,3),(4,2)\}, S=\{(2,1),(3,2),(4,3)\}$ ，求 $R \circ S$ 。

解：（1）关系图方法
对于关系 $R$ 和 $S$ 的复合关系，可以用图2．3直观表示。

![图片](/uploads/2026-05/4c284c.jpg)
 
 根据复合关系的定义，得到

$$
R \cdot S=\{(2,3),(3,2),(4,1)\}
$$

（2）关系矩阵方法
根据题意，关系 $R$ 和 $S$ 的关系矩阵分别表示为：

$$
\boldsymbol{M}_R=\left[\begin{array}{lll}
0 & 0 & 0 \\
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0
\end{array}\right], \boldsymbol{M}_S=\left[\begin{array}{lll}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{array}\right]
$$

故

![图片](/uploads/2026-05/3f2a83.jpg)
 
 注意：上式中的 ⊗ 是布尔矩阵乘法。
**定理2．6** 设 $R$ 为定义在集合 $A$ 上的关系，则

$$
R \circ I_A=I_A \circ R=R
$$

该定理很容易由定义证明。关系的复合运算满足结合律，下面的定理证明了这一点。

**定理 2.7** 设 $R, S, T$ 分别表示从 $A$ 到 $B, B$ 到 $C, C$ 到 $D$ 的关系，则有

$$
(R \circ S) \circ T=R \circ(S \circ T)
$$

证明：先证明 $(R \circ S) \circ T \subseteq R \circ(S \circ T)$ 。
设有任意 $(a, d) \in(R \circ S) \circ T$ ，则必存在 $c \in C$ ，使 $(a, c) \in R \circ S,(c, d) \in T$ 。
同时，必存在 $b \in B$ ，使 $(a, b) \in R,(b, c) \in S$ 。
因为 $(b, c) \in S,(c, d) \in T$ ，故必有 $(b, d) \in S \circ T$ 。
同时，因为 $(a, b) \in R,(b, d) \in S \circ T$ ，故必有 $(a, d) \in R \circ(S \circ T)$ 。
由此证明了 $(R \circ S) \circ T \subseteq R \circ(S \circ T)$ 。
可类似证得 $R \circ(S \circ T) \subseteq(R \circ S) \circ T$ 。由此定理得证。
由于关系的复合运算满足结合律，故可以将复合运算中的括号去除，即

$$
(R \circ S) \circ T=R \circ(S \circ T)=R \circ S \circ T
$$

对于某个关系 $R$ ，自己与自己的复合运算是 $R \circ R$ ，可以用 $R^2$ 表示；同理， $R \circ R \circ R$ 可用 $R^3$ 表示。因此，可以用下面的方式来定义关系的幂。

**定义2．13** 设有一个集合 $A$ 上的关系 $R$ ，则 $R^n$ 可定义如下：
（1）$R^0=I_A$ ；
（2）$R^1=R$ ；
（3）$R^{n+1}=R^n \circ R$ 。
由定义，很容易知道

$$
\begin{aligned}
R^m \circ R^n & =R^{m+n} \\
\left(R^m\right)^n & =R^{m \times n}
\end{aligned}
$$

**2．3．3 关系 $\boldsymbol{R}$ 的逆运算**
关系的第二种区别于传统集合的运算为关系的逆运算。以程序调用为例，设某程序 $a$ 可以调用另一程序 $b$ ，因此 $a$ 与 $b$ 有调用关系；反之，程序 $b$ 可以被程序 $a$所调用，因此 $b$ 与 $a$ 有被调用关系。这样就说被调用关系是调用关系的＂逆关系＂。
 
**定义2．14** 若 $R \subseteq A \times B$ ，则关系

$$
\bar{R}=\{(y, x) \mid(x, y) \in R\}
$$

是集合 $B$ 到集合 $A$ 的关系，称为关系 $R$ 的逆关系。

`例2.22`设集合 $A=\{1,2,3\}, B=\{2,3,4\}, R=\{(1,2),(2,2),(3,4)\}$ ，则其逆关系为 $\bar{R}=\{(2,1),(2,2),(4,3)\}$ 。

一个关系的逆关系可以用图形及矩阵来表示，将关系 $R$ 的关系图中有向边的方向改变后即得逆关系的关系图。

关系的逆运算满足下面的定理。
**定理 2.8** 设 $R$ 和 $S$ 分别是从 $A$ 到 $B 、 B$ 到 $C$ 的关系，则有
（1） $\bar{R}=R$ ；
（2）$\overline{(R \circ S)}=\bar{S} \circ \bar{R}$ 。

## 二元关系
从 $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)

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：关系的矩阵表示与图表示

下一篇：关系的重要性质

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