关系的闭合性质关系的闭合性质|离散数学

考虑给定集合A以及A上所有关系的集合。令P为此类关系的属性, 例如对称或可传递。具有属性P的关系将称为P关系。在A上表示为P（R）的任意关系R的P闭包是一个P关系, 使得

R ? P (R) ? S

（1）自反和对称闭包：下一个定理告诉我们如何轻松获得关系的自反和对称闭包。
定理：设R是集合A上的一个关系。

R∪?A是R的自反闭合
R∪R-1是R的对称闭环。

范例1：

Let A = {k, l, m}. Let R is a relation on A defined byR = {(k, k), (k, l), (l, m), (m, k)}.

找到R的反身闭合。
解：R∪?是具有反射性的最小关系, 因此,

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

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

R = {(4, 5), (5, 5), (5, 6), (6, 7), (7, 4), (7, 7)}

查找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的最小传递关系。
回忆一下R2 =R?R和Rn =Rn-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）}。那么R2 =R?R = {（1, 3）, （2, 3）, （3, 3）}且R3 =R2?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的矩阵如图所示：

现在, 找到MR的功能, 如图所示：

因此, 如图1所示, MR的传递闭包为MR *（其中MR *是MR幂的ORing）。

因此, R * ＝ {（4, 4）, （4, 10）, （6, 8）, （6, 6）, （6, 10）, （8, 10）}。
注意：在对矩阵R的幂进行或运算时, 我们可以消除MRn, 因为如果n为偶数, 则MRn等于MR *；如果n为奇数, 则等于MR3。