《离散数学-3-8关系的闭包运算revised.ppt》由会员分享，可在线阅读，更多相关《离散数学-3-8关系的闭包运算revised.ppt（15页珍藏版）》请在三一办公上搜索。
1、1,第三章 集合与关系,3-8 关系的闭包运算授课人：李朔Email:,2,一闭包的概念,对集合X上的二元关系R，有时候希望R具有一些有用的性质，这就需要在R中增加一些序偶，但又希望R不要变得太大。闭包运算就能解决这一问题。闭包运算:对给定的关系用扩充一些序偶的办法得到具有某些特殊性质的新关系。,3,一、闭包的概念,P129 定义3-8.1 设R为X上的二元关系，若有另一个关系R满足：1）R是自反的（对称，可传递的）；(闭包具有相应性质）2）RR；（闭包在R的基础上得到）3）对任何自反的(对称的，传递的)关系R，若RR，就有R R（最小），则称关系R为R的自反（对称，传递）闭包，记作：r(R)
2、,(S(R),t(R)*自反（对称，传递）闭包应是包含R的具有相应性质的最小关系,4,一、闭包的概念,定理3-8.1 设R为X上的二元关系，则1）R是自反的，当且仅当r(R)=R；2）R是对称的，当且仅当S(R)=R；3）R是传递的，当且仅当t(R)=R。证明：1）若R自反的，因RR，且任何包含R的自反关系R，有RR，故R为自反闭包，即 r(R)=R。反之，若r(R)=R，则必自反。其余证明略。,5,二、闭包的求法,具体如何求X上关系R的闭包呢？下面给出方法。P120 定理3-8.2 设R为非空集X上的二元关系，则 r(R)=RRIX证：设RRIX，则称任xX,R故R在X上自反。又R RIX，
3、故R R。若有自反关系R且RR，则IX R 故 R IX RR所以 r(R)=R IX关系图求法？无环结点加环,6,二、闭包的求法,P120 定理3-8.3 设R为非空集X上的二元关系，则S(R)=RR C证：令R=RRC，因R RRC即RR，又设 R，则R或 RC即 RC或R故RRC，故R是对称的。设R是对称的且RR，则对任R则R或 RC 当R则R当RC则R,R因R对称，故R，故RR即S(R)=RRC关系图求法？各单向边加相反方向的一条边,7,二、闭包的求法,定理3-8.4 设R为非空集X上的二元关系，则t(R)=RR2R3 证明：证明分两部分：(1)(基础)从传递闭包的定义,立即得到Rt(
4、R)(2)(归纳)假设Rnt(R),n1.设a,bRn+1.因为Rn+1=RnR,存在cA,使a,cRn和c,bR.根据归纳前提和基础步骤,a,ct(R)和c,bt(R).因为t(R)是传递的,得a,bt(R).这证明了 Rn+1t(R).所以有 设a,b,c,b，则必存在整数s和t,使得a,b RS，c,b Rt，这样RSRt，即a,c,所以 是传递的。由于包含R的可传递关系都包含t(R)，故t(R)由a)和b)可得t(R)=，通常，将 记作R+。关系图求法？为不直通但有通路的两结点间加上一条有向弧,8,二、闭包的求法,P121 例1：A=a,b,c,R=,求r(R),S(R),t(R).解
5、：r(R)=R IA=,s(R)=RR C=,为求t(R)先求R2，R3，R4即R2,R3=,R4=,可见R=R4=R3n+1R2=R5=R3n+2R3=R6=R3n+3故t(R)=RR 2R 3=,，,9,二、闭包的求法,例：设A=1,2,3,4,5,R是A上的二元关系，R=,分别求r(R),S(R),T(R).（可用关系图求解）,10,二、闭包的求法,定理3-8.5 设X是含有n个元素的集合，R是X上的二元关系，则存在一个正整数kn，使得：t(R)=RR 2R 3Rk证明：设有xi,xjX,记t(R)=R+,如果xiR+xj则存在整数p0，使xiRpxj成立，即存在e1,e2,ep-1有x
6、iRe1,e1Re2,ep-1Rxj。设满足上述条件的最小p大于n，则在上述序列中必有0tn不成立。*从本定理可以知道，在n个元素的有限集上关系R的传递闭包不妨写为t(R)=RR 2R 3Rn。例2：P123,11,二、闭包的求法,定理3-8.6设X是集合，R是X上的二元关系，则：a)rs(R)=sr(R)b)rt(R)=tr(R)c)ts(R)st R)证明：令Ix表示X上的恒等关系。a)sr(R)=s(IxR)=(IxR)(IxR)c=(IxR)(IxcRc)=IxRRc=Ixs(R)=rs(R)*求R+的Warshall算法 P124,12,求R+的Warshall算法,R=,i=1,2,3n,各行i列元素为1？与I行逻辑加,13,若R是自反的，则s(R)和t(R)也是自反的若R是对称的，则r(R)和t(R)也是对称的若R是传递的，那么r(R)是传递的。*注意，此时S(R)却不一定是传递的例如：S(R)不具有传递性。为什么？,14,本课小结,自反闭包对称闭包传递闭包,15,作业,P127（7）,
