关系的闭包性质

考虑一个给定的集合 A，以及 A 上所有关系的集合。设 P 是这些关系的属性，例如对称或传递。具有属性 P 的关系将称为 P 关系。任意关系 R 在 A 上的 P 闭包，表示为 P(R)，是满足以下条件的 P 关系：

(1) 自反闭包和对称闭包： 下一个定理告诉我们如何轻松获得关系的自反闭包和对称闭包。

定理： 设 R 是集合 A 上的关系。然后

• R ∪ ∆_A 是 R 的自反闭包
• R ∪ R^-1 是 R 的对称闭包。

示例 1

求 R 的自反闭包。

解： R ∪ ∆ 是具有自反性质的最小关系，因此，

RF = R ∪ ∆ = {(k, k), (k, l), (l, l), (l, m), (m, m), (m, k)}.

例2： 考虑 A = {4, 5, 6, 7} 上的关系 R，定义为

求 R 的对称闭包。

解： 包含 R 且具有对称性质的最小关系是 R ∪ R^-1，即

RS = R ∪ R-1 = {(4, 5), (5, 4), (5, 5), (5, 6), (6, 5), (6, 7), (7, 6), (7, 4), (4, 7), (7, 7)}.

(2)传递闭包： 考虑集合 A 上的关系 R。关系 R 的传递闭包 R 是包含 R 的最小传递关系。

回想一下 R² = R◦ R 且 Rⁿ = R^n-1 ◦ R。我们定义

以下定理适用

定理1： R^* 是 R 的传递闭包

假设 A 是一个具有 n 个元素的有限集。

R* = R ∪R2  ∪.....∪ Rn

定理 2： 设 R 是具有 n 个元素的集合 A 上的关系。然后

Transitive (R) = R ∪ R2∪.....∪ Rn

例1： 考虑 A = {1, 2, 3} 上的关系 R = {(1, 2), (2, 3), (3, 3)}。那么
R² = R◦ R = {(1, 3), (2, 3), (3, 3)} 且 R³ = R² ◦ R = {(1, 3), (2, 3), (3, 3)} 因此，
传递 (R) = {(1, 2), (2, 3), (3, 3), (1, 3)}

例2： 设 A = {4, 6, 8, 10} 且 R = {(4, 4), (4, 10), (6, 6), (6, 8), (8, 10)} 是集合 A 上的关系。确定 R 的传递闭包。

解： 关系 R 的矩阵如图所示

现在，求 M_R 的幂，如图所示

因此，M_R 的传递闭包是 M_R^*，如图所示（其中 M_R^* 是 M_R 的幂的 OR 运算）。

因此，R^* = {(4, 4), (4, 10), (6, 8), (6, 6), (6, 10), (8, 10)}。

注意：在对矩阵 R 的幂进行 OR 运算时，我们可以消除 M_Rⁿ，因为它等于 M_R^*（如果 n 是偶数）并且等于 M_R³（如果 n 是奇数）。