关闭离散数学关系.pptVIP

4.4 关系的闭包;一、闭包定义;由闭包的定义可知， R的自反（对称，传递）闭包是含有R并且具有 自反（对称，传递）性质的“最小”的关系。 ;二、关系的闭包运算;例：设Ａ={a,b,c},R={a,b,b,c,c,a}，求r(R),s(R),t(R)。; 设R是A上的二元关系，x∈A，将所有(x,x)?R的有序对 加到R上去，使其扩充成自反的二元关系，扩充后的自反 关系就是R的自反闭包r(R)。 ;2.构造R的对称闭包的方法。 ;3.构造R的传递闭包的方法。 ;思考：设A={a,b,c,d}, R={a,b,b,a,b,c,c,d}, 求 r(R), s(R), t(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∪…=