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

关系的闭包

从给定关系 $R$ 出发构造一个新关系 $R^{\prime}$ ，使得 $R^{\prime}$ 具有某种性质，并且 $R^{\prime}$ 又是具有该种性质并且包含 $R$ 的所有关系中最小的关系。从关系 $R$ 得到这样的新关系 $R^{\prime}$ 的运算称为闭包运算。现定义如下。

定义2．11 设 $R$ 是 $A$ 上的二元关系，定义 $R$ 的自反（对称，传递）闭包，记为 $R^{\prime}$ ，满足下列 3 个条件：
（1）$R^{\prime}$ 是自反的（对称的，传递的）。

（2）$R \subseteq R^{\prime}$ 。
（3）对任一自反（对称，传递）关系 $R^{\prime \prime}$ ，若 $R \subseteq R^{\prime \prime}$ ，则 $R^{\prime} \subseteq R^{\prime \prime}$ 。
$R$ 的自反闭包，对称闭包和传递闭包分别记为 $r(R), s(R)$ 和 $t(R), t(R)$ 又可记为 $R^{+}$。
由定义 2.11 ，可以看出 $R^{\prime}$ 的自反（对称，传递）闭包是包含 $R^{\prime}$ ，且具有自反（对称，传递）性质的所有关系中的最小关系。

例2．17（1）在例2．2 中，对于 $A$ 上的小于关系 $R, A$ 上的小于等于关系 $R^{\prime}$ 是 $R$ 的自反闭包，$A$ 上的不等关系 $R$＂是 $R$ 的对称闭包，$R$ 的传递闭包还是 $R$ 。
（2）设 $R$ 是 $A=\{1,2,3\}$ 上的二元关系，且 $R=\{(1,2),(1,3)\}$ ，则 $r(R)=\{(1,1),(2,2),(3,3)$ ， $(1,2),(1,3)\} ; s(R)=\{(1,2),(1,3),(2,1),(3,1)\} ; t(R)=R$ 。

由定义 2.11 ，容易得到如下定理。
定理 2.5 设 $R$ 是 $A$ 上的二元关系，则
（1）$R$ 是自反的当且仅当 $r(R)=R$ 。
（2）$R$ 是对称的当且仅当 $s(R)=R$ 。
（3）$R$ 是传递的当且仅当 $t(R)=R$ 。
并且 $r(R), s(R), t(R)$ 具有单调性，如下述定理。
定理 2.6 设 $R_1$ 和 $R_2$ 是 $A$ 上的二元关系，$R_1 \subseteq R_2$ 则
（1）$r\left(R_1\right) \subseteq r\left(R_2\right)$ 。
（2）$s\left(R_1\right) \subseteq s\left(R_2\right)$ 。
（3）$t\left(R_1\right) \subseteq t\left(R_2\right)$ 。
证明留作习题。

下面对自反闭包，对称闭包和传递闭包分别作进一步讨论，根据给出的关系，给出求闭包的一般表达式。

定理 2.7 设 $R$ 是集合 $A$ 上的二元关系，$I_A$ 是集合 $A$ 上的恒等关系，则 $r(R)=R \cup I_A$ 。
证明：令 $R^{\prime}=R \cup I_A$ 。要证明 $R^{\prime}$ 是 $R$ 的自反闭包，就要根据定义 2.11 ，证明 $R^{\prime}$ 满足自反闭包定义中的 3 个条件即可。
（1）因为对任意 $a \in A$ ，有 $(a, a) \in I_A \subseteq R \cup I_A=R^{\prime}$ ，所以 $R^{\prime}$ 自反。
（2）又因为 $R^{\prime}=R \cup I_A$ ，所以 $R \subseteq R^{\prime}$ 。
（3）假设有 $A$ 上的二元关系 $R^{\prime \prime}, ~ R^{\prime \prime}$ 自反且 $R \subseteq R^{\prime \prime}$ ，对任意的 $(a, b) \in R^{\prime}=R \cup I_A$ ，若 $(a, b) \in R$ ，则因为 $R \subseteq R^{\prime \prime}$ ，故 $(a, b) \in R^{\prime \prime}$ ；若 $(a, b) \in I_A$ ，即 $b=a$ ，则因为 $R^{\prime \prime}$ 自反，故 $(a, b) \in R^{\prime \prime}$ ；所以总有 $(a, b) \in R^{\prime \prime}$ ，因此 $R^{\prime} \subseteq R^{\prime \prime}$ 。

即 $R^{\prime}=R \cup I_A$ 是 $R$ 的自反闭包。
定理 2.8 设 $R$ 是集合 $A$ 上的二元关系，则 $s(R)=R \cup R^{-1}$ 。
证明：令 $R^{\prime}=R \cup R^{-1}$ 。同理，要证明 $R^{\prime}$ 是 $R$ 的对称闭包，就要根据定义 2．11，验证 $R^{\prime}$ 满足闭包定义的 3 个条件。

因为 $\left(R \cup R^{-1}\right)^{-1}=R \cup R^{-1}$ ，由定理 2．2，可知 $R^{\prime}=R \cup R^{-1}$ 是对称的，且 $R \subseteq R^{\prime}$ 。假设 $R^{\prime \prime}$ 是 $A$ 上的对称关系，并且 $R \subseteq R^{\prime \prime}$ 。对于任意的 $(a, b) \in R^{\prime}$ ，则有 $(a, b) \in R$ 或者 $(a, b) \in R^{-1}$ 。如果 $(a, b) \in R$ ，由于 $R \subseteq R^{\prime \prime}$ ，那么 $(a, b) \in R^{\prime \prime}$ ；如果 $(a, b) \in R^{-1}$ ，则 $(b, a) \in R$ ，所以 $(b, a) \in R^{\prime \prime}$ 。因为 $R^{\prime \prime}$ 是对称的，所以 $(a, b) \in R^{\prime \prime}$ 。因此 $R^{\prime} \subseteq R^{\prime \prime}$ 。所以 $R^{\prime}=s(R)=R \cup R^{-1}$ 。

例 2.18 （1）在例 2.2 中，对于 $A$ 上的小于关系 $R, A$ 上的小于等于关系 $R^{\prime}$ 是 $R$ 的自反闭包，$R^{\prime}=R \cup I_A ; A$ 上的不等关系 $R^{\prime \prime}$ 是 $R$ 的对称闭包，$R^{\prime \prime}=R \cup R^{-1}$ 。
（2）整数集 $I$ 上的恒等关系的自反闭包还是恒等关系；$I$ 上的空关系的自反闭包是恒等关系；$I$ 上的＂$\neq$＂关系的自反闭包则是全关系。
（3）整数集 $I$ 上的＂＜＂关系的对称闭包是＂$\neq "$ 关系；$I$ 上的＂$\leqslant$＂关系的对称闭包则是全关系；$I$ 上的恒等关系的对称闭包还是恒等关系；$I$ 上的＂$\neq$＂关系的对称闭包是还是＂$\neq$＂关系。

传递闭包是一个重要的概念，在计算机科学领域中有广泛的应用。
定理 2.9 设 $R$ 是集合 $A$ 上的二元关系，则 $t(R)=\cup_{i=1}^{\infty} R^i=R \cup R^2 \cup R^3 \cup \ldots$ 。
证明：令 $R^{\prime}=R \cup R^2 \cup R^3 \cup \ldots$ ，由定义 2．11，要验证 $R^{\prime}$ 满足传递闭包定义的 3 个条件。
（1）首先证明 $R^{\prime}$ 是传递的，即如果 $(a, b) \in R^{\prime},(b, c) \in R^{\prime}$ ，则 $(a, c) \in R^{\prime}$ 。因为 $(a, b) \in R^{\prime},(b, c) \in R^{\prime}$ ，则必存在正整数 $n$ 和 $k$ ，使得 $(a, b) \in R^n,(b, c) \in R^k$ ；又因为 $R^n \circ R^k=R^{n+k}$ ，所以 $(a, c) \in R^{n+k}$ ，则 $(a$ ， c）$\in R^{\prime}$ 。即 $R^{\prime}$ 是传递的。
（2）因为 $R \subseteq R \cup R^2 \cup R^3 \cup \ldots$ ，所以 $R \subseteq R^{\prime}$ 。
（3）假设有 $A$ 上的二元关系 $R^{\prime \prime}, ~ R^{\prime \prime}$ 传递且 $R \subseteq R^{\prime \prime}$ ，如果 $(a, b) \in R^{\prime}$ ，则存在 $k$ ，使得 $(a, b) \in R^k$ ，
所以存在 $k-1$ 个元素 $c_l, c_2, \cdots, c_{k-1}$ ，使得 $\left(a, c_1\right) \in R,\left(c_1, c_2\right) \in R, \ldots,\left(c_{k-1}, b\right) \in R$ ；因为 $R \subseteq R^{\prime \prime}$ ，所以 $\left(a, c_l\right) \in R^{\prime \prime},\left(c_l, c_2\right) \in R^{\prime \prime}, \ldots,\left(c_{k-1}, b\right) \in R^{\prime \prime}$ 。又因为 $R^{\prime \prime}$ 是传递的，所以 $(a, b) \in R^{\prime \prime}$ ，因此 $R^{\prime} \subseteq R^{\prime \prime}$ 。所以 $R^{\prime}=t(R)=R \cup R^2 \cup R^3 \cup \ldots$ 。
在实际计算时，对于有限集 $A$ ，其上的关系的传递闭包只要进行有限次计算即可。

定理 2.10 设 $R$ 是有限集 $A$ 上的二元关系，且 $|A|=n$ ，则 $t(R)=\cup_{i=1}^n R^i$ 。
证明：由定理 2．9，$\cup_{i=1}^n R^i \subseteq t(R)$ ；现在证明 $t(R) \subseteq \cup_{i=1}^n R^i$ 。
当 $k \leqslant n$ 时，必有 $R^k \subseteq R \cup R^2 \cup R^3 \cup \ldots \cup R^n$ 。
当 $k>n$ 时，若 $(a, b) \in R^k$ ，则存在元素个数为 $k+1$ 的元素序列 $c_0, c_1, \cdots, c_k, c_0=a, c_k=b$ ，并且对 $1 \leqslant i \leqslant k,\left(c_{i-1}, c_i\right) \in R$ 。由于 $k>n$ ，所以在元素序列中必有元素 $c_i$ 不止出现一次，即 $\left(a, c_1\right),\left(c_1\right.$ ， $\left.c_2\right), \cdots,\left(c_{i-1}, c_i\right),\left(c_i, c_p\right), \cdots,\left(c_q, c_i\right),\left(c_i, c_{i+1}\right), \cdots,\left(c_{k-1}, b\right) \in R$ ，在删去 $\left(c_i, c_p\right), \cdots,\left(c_q, c_i\right)$ 这一段后，如果序列中元素个数仍大于 $n$ ，则继续上述过程，直到序列中元素个数 $k^{\prime} \leqslant n$ 为止。此时有 $(a$ ， $b) \in R^{k^{\prime}}$ ，所以 $(a, b) \in R \cup R^2 \cup R^3 \cup \ldots \cup R^n$ 。

例 $2.19 A=\{a, b, c, d\}, R=\{(a, b),(b, a),(b, c),(c, d)$ ，求 $t(R)$ 。
解：$R=\{(a, b),(b, a),(b, c),(c, d)\}$ ，则 $R^2=R \circ R=\{(a, a),(a, c),(b, b),(b, d)\}, R^3=R^2 \cdot R=\{(a, b)$ ， $(a, d),(b, a),(b, c)\}, R^4=R^3 R=\{(a, a),(a, c),(b, b),(b, d)\}=R^2$ ，因此 $t(R)=R \cup R^2 \cup R^3=\{(a, b),(b$, $a),(b, c),(c, d),(a, a),(a, c),(b, b),(b, d),(a, d)\}$ 。

闭包还有一些其他的性质。
定理 2.11 设 $R$ 是 $A$ 上的二元关系。
（1）若 $R$ 是自反的，则 $s(R)$ 和 $t(R)$ 都是自反的。
（2）若 $R$ 是对称的，则 $r(R)$ 和 $t(R)$ 都是对称的。
（3）若 $R$ 是传递的，则 $r(R)$ 是传递的。
可以分别根据自反，对称和传递的定义进行证明定理 2.11 ，具体证明留作习题。
定理 2.12 设 $R$ 是 $A$ 上的二元关系，则
（1）$r s(R)=s r(R)$（这里 $r s(R)$ 读作 $R$ 的对称自反闭包）。

（2）$r t(R)=\operatorname{tr}(R)$ 。
（3）$s t(R) \subseteq t s(R)$ 。
证明：设 $I_A$ 是 $A$ 上的恒等关系。
（1） $\operatorname{sr}(R)=s\left(R \cup I_A\right)=\left(R \cup I_A\right) \cup\left(R \cup I_A\right)^{-1}=\left(R \cup I_A\right) \cup\left(R^{-1} \cup I_A\right)=\left(R \cup I_A\right) \cup R^{-1}=\left(R \cup R^{-1}\right) \cup I_A=$ $r\left(R \cup R^{-1}\right)=r(s(R))=r s(R)$
（2）利用复合运算性质以及定理 2.4 ，对 $n$ 进行归纳证明，得到

$$
\begin{aligned}
& \left(R \cup I_A\right)^n=I_A \cup\left(\cup_{i=1}^n R^i\right) \\
& \operatorname{tr}(R)=t\left(R \cup I_A\right)=\cup_{i=1}^{\infty}\left(R \cup I_A\right)^i=\left(R \cup I_A\right) \cup\left(R \cup I_A\right)^2 \cup\left(R \cup I_A\right)^3 \cup \ldots \\
& =I_A \cup R \cup R^2 \cup R^3 \cup \ldots=I_A \cup t(R)=r t(R)
\end{aligned}
$$

（3）因为 $R \subseteq s(R)$ ，基于定理 2．6（3），$t(R) \subseteq t s(R), ~ s t(R) \subseteq s t s(R)$ ；由定理2．11（2），$t s(R)$ 是对称的；由定理 $2.5(2)$ ，所以 $s t s(R)=t s(R)$ 。因此 $s t(R) \subseteq t s(R)$ 。
$t s(R)$ 是否与 $s t(R)$ 不相等，请看反例。
例2．20 设 $R=\{(1,2)\}$ ，则 $t(R)=\{(1,2)\}, ~ s t(R)=\{(1,2),(2,1)\}$ ；而 $s(R)=\{(1,2),(2,1)\}$ ， $t(s(R))=\{(1,1),(1,2),(2,1),(2,2)\}$ ；因此 $t(s(R)) \neq s(t(R))$ 。

刷题

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

上一篇：自然连接

下一篇：等价关系与划分

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