定理10.5.10
A为非空有限集合, R是A上的关系,则存在正整数 ,使得
。
证明
设有 ,则存在整数 ,使得 ,即存在序列
,有
。设满足上述条件的最小的p,有 ,则 个元素都是A中的n个元素,
个元素中必有两个相等,即有 使 ,因此序列可以去掉中间一段成为 和两段。第一段有t各有序对,第二段有 个有序对。因此, ,其中
。这与p为最小的假设矛盾。故 不成立。
由此定理可知,这时的 不妨写成
。
例5
集合 上的关系R为
。
则 

而


由 
则


当有限集合A的元素较多时,用矩阵运算求A是的关系R的传递闭包仍很复杂。1962年Warshall提出了一种有效的算法。
Warshall算法:(令 表示矩阵B第j行第i列的元素)
(1) 令矩阵 ,
(2) 令 ,
(3) 对 ,如果 =1,则对
,令
,
(4) i加1,
(5) 若
,则转到(3),否则停止,且
。
例6
A上的关系R的关系矩阵为
令 。
时,第1列只有 ,将第1行与第1行各对应元素作逻辑加,仍记于第1行。
时,第2列中 ,将第1行与第2行各对应元素作逻辑加,记于第1行。
第2列还有
,将第4行与第2行对应加,记于第4行。
时,第3列全是0,B不变。
时,第4列中 ,将第1,2,4这3行分别与第4行对应元素逻辑加,分别记于1,2,4这3行。

这就是
。
有时希望所求的闭包具有两种或三种性质。应该先作哪种闭包运算呢?下面分析这个问题。
定理10.5.11
对非空集合A上的关系R,有
(1) 若R是自反的,则 和 是自反的,
(2) 若R是对称的,则 和 是对称的,
(3) 若R是传递的,则 是传递的。
证明
只证(2),其他留作思考题。
(2)先证 是对称的。对任意的 ,如果 ,则
,
如果 ,则

(因 )
(R是对称的)
。
总之, 是对称的。
再证 是对称的。为此先证,若R对称,则对非零自然数n,有 是对称的。施归纳于n。
当 时, 是对称的。
假设 时 是对称的。令 ,对任意的 ,可得




则 是对称的。对非零自然数n,有 是对称的。
对任意的 ,可得


所以, 是对称的。
定理10.5.12讨论了关系性质和闭包运算之间的联系。
如果关系R是自反的或对称的,那么经过求闭包的运算以后所得到关系仍旧是自反的或对称的。但是对于传递的关系则不然。它的自反闭包仍旧保持传递性,而对称闭包就有可能失去传递性。例如:A=|1,2,3|,R={<1,3>}是A上的传递关系,R的对称闭包

显然 不再是A上的传递关系。从这里可以看出,如果计算关系R的自反,对称,传递的闭包,为了不失去传递性,传递闭包运算应该放在对称闭包运算的后边,若令

定理10.5.13
对非空集合A上的关系R,有
(1)
,
(2)
,
(3)
。
其中 ,其它类似。
证明
(1)


。
(2)先证 。施归纳于n。
当 时,
。
假设时有
。令
,则有




。
利用这个结论




。
(3)因为 ,所以 和 。因为 是对称的,所以 。因此 。
由定理可知,若要求出R的自反、对称且传递的闭包,则应先求 ,再求 ,最后求
。若先求 ,再求 ,则 不一定是传递的。
|