定理10.5.7
对非空集合A上的关系R,有

证明
对任意的 ,于是 ,所以 是A上自反的。显然 ,所以 是包含R的自反关系。对A上任意的自反关系 ,如果 ,则对任意的 ,若 ,则或者 ,或者 。当 ,由 有 。若 ,则 ,由 的自反性有 。两种情况都有 。因此, 。总之 ,
满足 的定义, 。
由定理可知,很容易构造R的自反闭包,只要把所有的 构成的 加入R中。若通过关系矩阵构造R的自反闭包。设关系 的关系矩阵分别为 ,那么

其中E是与M同阶的单位矩阵。另外在上述等式中矩阵的元素相加时使用逻辑加。
若通过关系图构造R的自反闭包。设关系 的关系图分别为 ,则 的顶点集与G的顶点集相等。除了G的边以外,依下述方法添加新的边。
考察G的每个顶点,如果没有环就加上一个环,最终得到的是 。
定理10.5.8
对非空集合A上的关系R,有
。
证明
对任意的 ,可得

所以, 是A上对称的关系。
显然有
。
对A上任意的包含R的对称关系
,对任意的 ,若 ,则 或 ,当 ,由
。当 ,则 , ,因 是对称的,故 。两种情况都有 ,则 。
总之, 满足 的定义,所以
。
由定理可知,很容易构造R的对称闭包,只要对任何 且 把
加入R中。
若通过关系矩阵构造R的自反闭包。设关系 的关系矩阵分别为 ,那么
其中 是M的转置矩阵。另外在上述等式中矩阵的元素相加时使用逻辑加。
若通过关系图构造R的自反闭包。设关系 的关系图分别为 则 的顶点集与G的顶点集相等。除了G的边以外,依下述方法添加新的边。
考察G的每一条边,如果有一条 到 的单向边, ,则在G中加一条 到 的反方向边,最终得到的是 。
定理10.5.9
对非空集合A上的关系R,有
。
证明
先证
。为此只要证明对任意的 ,有 。施归纳于n。
当 时,
。
假设 时有
。令 ,对任意的 有




所以,
。由归纳法,对 ,有 。于是
。
再证
。对任意的 和 ,可得


其中s和t是非零自然数



所以, 是传递的,此外它包含R。所以
总之,
。
通常简写为
,
而且
。
定理10.5.3指出,在 中只有有限个不同的合成关系。所以在计算 时,可以只用有限个合成关系。
若通过关系矩阵构造R的自反闭包。设关系 的关系矩阵分别为 ,那么

在上述等式中矩阵的元素相加时使用逻辑加。
若通过关系图构造R的自反闭包。设关系 的关系图分别为 ,则 的顶点集与G的顶点集相等。除了G的边以外,依下述方法添加新的边。
考察G的每个顶点 ,找出从 出发的所有2步,3步,…,n步长的路径(n为G中的顶点数)。设路径的终点为 。如果没有从 到 (l=1,2,…,k)的边,就加上这条边,当检查完所有的顶点后最终得到的是 。
|