离散数学-3-8关系的闭包运算revised

《离散数学-3-8关系的闭包运算revised》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章集合与关系3-8关系的闭包运算授课人：李朔Email:chn.nj.ls@gmail.com1一．闭包的概念对集合X上的二元关系R，有时候希望R具有一些有用的性质，这就需要在R中增加一些序偶，但又希望R不要变得太大。闭包运算就能解决这一问题。闭包运算:对给定的关系用扩充一些序偶的办法得到具有某些特殊性质的新关系。2一、闭包的概念P129定义3-8.1设R为X上的二元关系，若有另一个关系R′满足：1）R′是自反的（对称，可传递的）；(闭包具有相应性质）2）R′R；（闭包在R的基础上得到）3）对任何自反的(对称的，传递的)

2、关系R″，若R″R，就有R″R′（最小），则称关系R′为R的自反（对称，传递）闭包，记作：r(R),(S(R),t(R))*自反（对称，传递）闭包应是包含R的具有相应性质的最小关系3一、闭包的概念定理3-8.1设R为X上的二元关系，则1）R是自反的，当且仅当r(R)=R；2）R是对称的，当且仅当S(R)=R；3）R是传递的，当且仅当t(R)=R。证明：1）若R自反的，因RR，且任何包含R的自反关系R″，有R″R，故R为自反闭包，即r(R)=R。反之，若r(R)=R，则必自反。其余证明略。4二、闭包的求法具体如何求X上关

3、系R的闭包呢？下面给出方法。P120定理3-8.2设R为非空集X上的二元关系，则r(R)=R＝RIX证：设R′＝RIX，则称任xX,R′故R′在X上自反。又RRIX，故RR′。若有自反关系R″且RR″，则IXR″故R″IXR＝R′所以r(R)=RIX关系图求法？无环结点加环5二、闭包的求法P120定理3-8.3设R为非空集X上的二元关系，则S(R)=RRC证：令R′=RRC，因RRRC即R′R，又设R′，则R或RC即RC或R

4、故RRC，故R′是对称的。设R″是对称的且R″R，则对任R′则R或RC当R则R″当RC则R,R″因R″对称，故R″，故R′R″即S(R)=RRC关系图求法？各单向边加相反方向的一条边6二、闭包的求法定理3-8.4设R为非空集X上的二元关系，则t(R)=RR2R3……证明：证明分两部分：(1)(基础)从传递闭包的定义,立即得到Rt(R)(2)(归纳)假设Rnt(R),n≥1.设〈a,b〉∈Rn

5、+1.因为Rn+1=Rn·R,存在c∈A,使〈a,c〉∈Rn和〈c,b〉∈R.根据归纳前提和基础步骤,〈a,c〉∈t(R)和〈c,b〉∈t(R).因为t(R)是传递的,得〈a,b〉∈t(R).这证明了Rn+1t(R).所以有设〈a,b〉,〈c,b〉，则必存在整数s和t,使得〈a,b〉RS，〈c,b〉Rt，这样RSоRt，即〈a,c〉,所以是传递的。由于包含R的可传递关系都包含t(R)，故t(R)由a)和b)可得t(R)=，通常，将记作R+。关系图求法？为不直通但有通路的两结点间加上一条有向弧7二、闭包的求法P1

6、21例1：A={a,b,c},R={,,},求r(R),S(R),t(R).解：r(R)=RIA={,,,,,}s(R)=RRC={,,,,,}为求t(R)先求R2，R3，R4即R2＝{,,}R3={,,}R4={,,}可见R=R4=R3n+1R2=R5=R3n+2R3=R6=R3n+3

7、故t(R)=RR2R3={,,,,,，,,}8二、闭包的求法例：设A={1,2,3,4,5},R是A上的二元关系，R={<1,1>,<2,2>,<2,3>,<3,4>,<5,4>,<4,5>}分别求r(R),S(R),T(R).（可用关系图求解）9二、闭包的求法定理3-8.5设X是含有n个元素的集合，R是X上的二元关系，则存在一个正整数k≤n，使得：t(R)=RR2R3…Rk证明：设有xi,xjX,记t(R)=R+,如果xiR

8、+xj则存在整数p>0，使xiRpxj成立，即存在e1,e2,…,ep-1有xiRe1,e1Re2,…,ep-1Rxj。设满足上述条件的最小p大于n，则在上述序列中必有0≤t