第4章 二元关系和函数（4）.pptVIP

4.3.2 关 系 的 闭 包 闭包运算是关系运算中一种比较重要的特殊运算， 是对原关系的一种扩充。 在实际应用中， 有时会遇到这样的问题， 给定了的某一关系并不具有某种性质， 要使其具有这一性质， 就需要对原关系进行扩充， 而所进行的扩充又是最小的。 这种关系的扩充就是对原关系的这一性质的闭包运算。 定义4.4.1 设R是非空集合A 上的关系， 如果 A上有另一个关系R′满足： ? （1） R′是自反的（对称的或传递的）； （2） RR′； （3） 对A上任何自反的（对称的或传递的）关系R″, 若RR″， 均有R′R″， 则称R′为R的自反（对称或传递）闭包。 一般将R的自反闭包记作r(R)， R的对称闭包记作s(R) ， R的传递闭包记作t(R)。 称r、 s、 t为闭包运算， 它们作用于关系R后， 分别产生包含R的, 最小的具有自反性、 对称性、 传递性的二元关系。 这三个闭包运算也可由下述定理来构造。 定理4.4.1 设R是集合A上的二元关系， 那么 （1） r(R)=IA∪R （2） s(R)=R∪R -1 （3） 证明 （1） IA∪R自反且RIA∪R是显然的。 为证IA∪R为自反闭包， 还需证它的“最小性”。 为此， 令R′自反， 且RR′， 欲证IA∪RR′ 由于R′自反，可得 IAR′， 又RR′， 即得IA∪RR′ 所以 r(R)=IA∪R （2） 证明。 （3） 例1 设A＝{1, 2, 3}, R1={〈1,2〉,〈2,1〉,〈1, 3〉, 〈1, 1〉}, R2={〈1, 2〉,〈2, 1〉}, R3={〈1, 2〉}, 求它们的闭包。 解 r(R1)=IA∪R ={〈1, 1〉, 〈2, 2〉, 〈3, 3〉, 〈1, 2〉, 〈2, 1〉, 〈1, 3〉} s(R1)=R∪R -1 ={〈1, 2〉,〈2, 1〉,〈1, 3〉,〈3, 1〉, 〈1, 1〉} t(R1)={〈1, 2〉, 〈2, 1〉,〈1, 1〉, 〈2, 2〉,〈1, 3〉, 〈2, 3〉} r(R2)=IA∪R={〈1, 1〉, 〈2, 2〉, 〈3, 3〉, 〈1, 2〉, 〈2, 1〉} s(R2)=R∪R -1={〈1, 2〉, 〈2, 1〉}=R2 t(R2)={〈1, 2〉, 〈2, 1〉, 〈1, 1〉, 〈2, 2〉} r(R3)=IA∪R={〈1, 2〉, 〈1, 1〉, 〈2, 2〉, 〈3, 3〉} s(R3)=R∪R -1={〈1, 2〉, 〈2, 1〉} t(R3)={〈1, 2〉}=R3 例2 设R是集合A={a， b， c， d}上的二元关系， R={〈a, b〉， 〈b,a〉， 〈b, c〉， 〈c, d〉}。 求R的闭包：r（R）、 s（R）、 t（R）， 并画出对 应的关系图。 解 r(R)={〈a, b〉,〈b, a〉,〈b, c〉,〈c, d〉, 〈a, a〉, 〈b, b〉, 〈c, c〉, 〈d, d〉} s(R)={〈a, b〉, 〈b, a〉, 〈b, c〉, 〈c, d〉, 〈c, b〉, 〈d, c〉} t(R)={〈a,b〉, 〈b,a〉, 〈b,c〉, 〈c,d〉, 〈a,a〉, 〈a,c〉, 〈b,b〉, 〈b,d〉, 〈a,d〉} 从以上讨论可以看出， 传递闭包的求取是很复杂的。 但是， 当集合A为有限集时， A上二元关系的传递闭包的求取便可大大简化。 推论 A为非空有限集合， |A|=n。 R是A上的关系， 则存在正整数k≤n， 使得 t(R)=R +=R∪R 2∪…∪R k 例3 设A={1, 2, 3, 4, }， R={〈1, 1〉,〈1,