离散数学关系的闭包.pptVIP

4.4 关系的闭包 闭包定义 闭包的构造方法 集合表示 矩阵表示 图表示 闭包的性质 一、闭包定义 定义 设R是非空集合A上的关系, R的自反（对称或传递）闭包是A上的关系R?, 使得R?满足以下条件：（1）R?是自反的（对称的或传递的）（2）R?R?（3）对A上任何包含R的自反（对称或传递）关系 R?? 有 R??R??. 一般将 R 的自反闭包记作 r(R), 对称闭包记作 s(R), 传递闭包记作 t(R). 二、关系的闭包运算 （1）已知一个集合中的二元关系R，则 r(R),s(R),t(R)是唯一的，它是包含R的 最小的自反（对称，传递）关系； 闭包的构造方法（续） 闭包的构造方法（续） 实例 定理 　R是A上关系，则 ⑴R是自反的，当且仅当 r(R)=R. ⑵ R是对称的，当且仅当 s(R)=R. ⑶ R是传递的，当且仅当 t(R)=R. 证明略，因为由闭包定义即可得。 定理　 R是A上关系，则 ⑴R是自反的，则s(R)和t(R)也自反。 ⑵ R是对称的，则r(R)和t(R)也对称。 ⑶ R是传递的，则r(R)也传递。 证明: ⑴因为R自反,得r(R)=R,即 R∪IA=R, r(s(R))=s(R)∪IA=(R∪R-1)∪IA = (R∪IA)∪R-1=r(R)∪R-1 =R∪R-1 =s(R)∴s(R)自反 类似可以证明t(R)也自反。 证明⑵. 证明t(R)对称: (t(R))-1=(R∪R2∪...∪Rn∪...)-1 = R-1∪(R2)-1 ∪...∪(Rn)-1∪... = R-1∪(R-1)2 ∪...∪(R-1)n∪... =R∪R2∪...∪Rn∪... (∵R对称，∴R-1 =R) =t(R) 所以t(R)也对称。 类似可以证明r(R)也对称。 证明⑶. 证明r(R)传递:先用归纳法证明下面结论: (R∪IA)i= IA∪R∪R2∪...∪Ri ①i=1时 R∪IA= IA∪R 结论成立。 ②假设i≤k 时结论成立，即 (R∪IA)k= IA∪R∪R2∪...∪Rk ③当i=k+1时 (R∪IA)k+1=(R∪IA)k (R∪IA) = (IA∪R∪R2∪...∪Rk） (IA∪R) = (IA∪R∪R2∪...∪Rk)∪(R∪R2∪...∪Rk+1) = IA∪R∪R2∪...∪Rk∪Rk+1 所以结论成立. t(r(R))=t(R∪IA) = (R∪IA)∪(R∪IA)2∪(R∪IA)3∪... =(IA∪R)∪(IA∪R∪R2)∪(IA∪R∪R2∪R3)∪... = IA∪R∪R2∪R3∪...= IA∪t(R) = IA∪R (R传递t(R)=R) =r(R) 所以r(R)也传递。 定理　设R1、R2是A上关系，如果R1?R2 ，则 ⑴ r(R1)? r(R2) ⑵ s(R1)? s(R2) ⑶ t(R1)?t(R2) 证明⑴ r(R1)=IA∪R1?IA∪R2= r(R2) ⑵，⑶类似可证。 定理　设R是A上关系，则 ⑴ sr(R)=rs(R) ⑵ tr(R)=rt(R) ⑶ st(R)?ts(R) 证明： ⑴ sr(R)=r(R)∪(r(R)-1=(R∪IA)∪(R∪IA)-1 = (R∪IA)∪(R-1∪IA-1) =R∪IA∪R-1∪IA = (R∪R-1)∪IA= s(R)∪IA=rs(R) ⑵的证明用前边证明的结论： (R∪IA)k= IA∪R∪R2∪...∪Rk 很容易证明，这里从略。 ⑶ 因 R?s(R) ，得 t(R)?ts(R) ； st(R)?sts(R) 因s(R)对称，得ts(R) 也对称，得sts(R)=ts(R) 所以有st(R)?ts(R) 。 证明完毕。 通常将t(R) 记成R+， tr(R)记成R*，即 t(R)= R+=R∪R2∪...∪Rn∪…= tr(R)=rt(R) =R*= R0∪R∪R2∪...∪Rn∪…= * * 由闭包的定义可知， R的自反（对称，传递）闭包是含有R并且具有 自反（对称，传递）性质的“最小”的关系。 如果R已是自反的二元关系，显然有：R= r(R)。 同样，当R是对称的二元关系时R= s(R)； 当R是传递的二元关系时，R= t(R)，且反之亦然。 （2）若R是自反（对称，传递）的，则 r(R),s(R),t(R)就是R本身。 （3）若R不是自反（对称，传