離散數(shù)學(xué)關(guān)系的閉包(1)

1、精選ppt14.4 關(guān)系的閉包關(guān)系的閉包n閉包定義閉包定義n閉包的構(gòu)造方法閉包的構(gòu)造方法 集合表示集合表示 矩陣表示矩陣表示 圖表示圖表示n閉包的性質(zhì)閉包的性質(zhì) 精選ppt2一、閉包定義一、閉包定義 定義定義 設(shè)設(shè)R是非空集合是非空集合A上的關(guān)系上的關(guān)系, R的的自反（對稱自反（對稱或或傳遞）閉包傳遞）閉包是是A上的關(guān)系上的關(guān)系R , 使得使得R 滿足以下條件：滿足以下條件：（1）R 是自反的（對稱的或傳遞的）是自反的（對稱的或傳遞的）（2）R R （3）對）對A上任何包含上任何包含R的自反（對稱或傳遞）關(guān)系的自反（對稱或傳遞）關(guān)系 R 有有 RR . 一般將一般將 R 的自反閉包記作的自反閉

2、包記作 r(R), 對稱閉包記作對稱閉包記作 s(R), 傳遞閉包記作傳遞閉包記作 t(R). 精選ppt3由閉包的定義可知，由閉包的定義可知，R R的自反（對稱，傳遞）閉包是含有的自反（對稱，傳遞）閉包是含有R R并且具有并且具有自反（對稱，傳遞）性質(zhì)的自反（對稱，傳遞）性質(zhì)的“最小最小”的關(guān)系。的關(guān)系。 如果如果R R已是自反的二元關(guān)系，顯然有：已是自反的二元關(guān)系，顯然有：R= r(R)R= r(R)。同樣，當(dāng)同樣，當(dāng)R R是對稱的二元關(guān)系時是對稱的二元關(guān)系時R= s(R)R= s(R)；當(dāng)當(dāng)R R是傳遞的二元關(guān)系時，是傳遞的二元關(guān)系時，R= t(R)R= t(R)，且反之亦然，且反之亦然

3、。 精選ppt4二、關(guān)系的閉包運(yùn)算二、關(guān)系的閉包運(yùn)算 （1 1）已知一個集合中的二元關(guān)系）已知一個集合中的二元關(guān)系R R，則，則 r(R),s(R),t(R)r(R),s(R),t(R)是唯一的，它是包含是唯一的，它是包含R R的的 最小的自反（對稱，傳遞）關(guān)系；最小的自反（對稱，傳遞）關(guān)系；（2 2）若）若R R是自反（對稱，傳遞）的，則是自反（對稱，傳遞）的，則 r(R),s(R),t(R)r(R),s(R),t(R)就是就是R R本身。本身。（3 3）若）若R R不是自反（對稱，傳遞）的，則不是自反（對稱，傳遞）的，則 可以補(bǔ)上最少序偶，使之變?yōu)樽苑础ΨQ、可以補(bǔ)上最少序偶，使之變?yōu)樽苑?/p>

4、、對稱、 傳遞關(guān)系，從而得到傳遞關(guān)系，從而得到r(R),s(R),t(R)r(R),s(R),t(R)；精選ppt5例：設(shè)例：設(shè)=a,b,c,R=,，求，求r(R),s(R),t(R)。解：解：r(R)= ,a bb cc aa ab bc c s(R)= ,a bb ab cc bc aa c t(R)=,例：設(shè)例：設(shè)=a,b,R=a,b,R=，則則r(R)=,r(R)=, s(R)=, s(R)=, t(R)=R t(R)=R精選ppt6 設(shè)設(shè)R是是A上的二元關(guān)系，上的二元關(guān)系，xA，將所有，將所有( (x,x) R的有序?qū)Φ挠行驅(qū)拥郊拥絉上去，使其擴(kuò)充成自反的二元關(guān)系，擴(kuò)充后的自反上去

5、，使其擴(kuò)充成自反的二元關(guān)系，擴(kuò)充后的自反關(guān)系就是關(guān)系就是R的自反閉包的自反閉包r(R)。 例如，例如，A=a,b,c,d,R=(a,a),(b,d),(c,c)。R的自反閉包的自反閉包r(R)= (a,a),(b,d),(c,c),(b,b),(d,d)。 于是可得：于是可得：定理定理: R是是A上的二元關(guān)系，則上的二元關(guān)系，則R的自反閉包的自反閉包r(R)=RIA。1.1.構(gòu)造構(gòu)造R的自反閉包的方法。的自反閉包的方法。 三、閉包的構(gòu)造方法三、閉包的構(gòu)造方法精選ppt72.2.構(gòu)造構(gòu)造R的對稱閉包的方法。的對稱閉包的方法。 每當(dāng)每當(dāng)(a,b)R，而，而(b,a) R時，將有序?qū)r，將有序?qū)?b

6、,a)加到加到R上去，上去，使其擴(kuò)充成對稱的二元關(guān)系，擴(kuò)充后的對稱關(guān)系就是使其擴(kuò)充成對稱的二元關(guān)系，擴(kuò)充后的對稱關(guān)系就是R的對稱閉包的對稱閉包s(R)。 例如，例如，A=a,b,c,d,e,R= (a,a), (a,b), (b,a), (b,c), (d,e)。R的對稱閉包的對稱閉包s(R) = (a,a), (a,b), (b,a), (b,c), (c,b), (d,e), (e,d)。定理定理: : R是是A上二元關(guān)系，上二元關(guān)系， 是其逆關(guān)系，是其逆關(guān)系，則則R的對稱閉包的對稱閉包s(R)=R 。 RR由逆關(guān)系的定義可知：由逆關(guān)系的定義可知：精選ppt83.3.構(gòu)造構(gòu)造R的傳遞閉包的

7、方法。的傳遞閉包的方法。 設(shè)設(shè)R 是是A A上的二元關(guān)系，每當(dāng)上的二元關(guān)系，每當(dāng)(a,b)R和和(b,c)R而而(a,c) R時，將時，將有序?qū)τ行驅(qū)?a,c)加到加到R上使其擴(kuò)充成上使其擴(kuò)充成R1，并稱，并稱R1 為為R的傳遞擴(kuò)張，的傳遞擴(kuò)張， R1 如果是傳遞關(guān)系如果是傳遞關(guān)系，則，則R1是是R的傳遞閉包；如果的傳遞閉包；如果R1不是傳遞關(guān)系，不是傳遞關(guān)系，繼續(xù)求繼續(xù)求R1的的傳遞擴(kuò)張的的傳遞擴(kuò)張R2， 如果如果R2是傳遞關(guān)系時，則是傳遞關(guān)系時，則R2是是R的傳的傳遞閉包；遞閉包； 如果如果R2不是傳遞關(guān)系時，繼續(xù)求不是傳遞關(guān)系時，繼續(xù)求R2的的傳遞擴(kuò)張的的傳遞擴(kuò)張R3，如果，如果A是有限

8、集，是有限集，R經(jīng)過有限次擴(kuò)張后，定能得到經(jīng)過有限次擴(kuò)張后，定能得到R的傳遞閉包的傳遞閉包。擴(kuò)張后的傳遞關(guān)系就是擴(kuò)張后的傳遞關(guān)系就是R的傳遞閉包的傳遞閉包t(R)。 定理定理: 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, 則有則有t(R) = RR2R3說明：說明： 對于有窮集合對于有窮集合A (|A|=n) 上的關(guān)系上的關(guān)系, 上式中的并最多不超過上式中的并最多不超過 Rn. 精選ppt9思考：設(shè)思考：設(shè)A=a,b,c,d, R=, 求求 r(R), s(R), t(R). 解解: r(R) = RR0=, , , , , , s(R) = RR 1=, , t(R) = RR2R3 R4 R2=, ,

9、 , R3= , , , R4= , , , = R2于是于是 t(R) = RR2R3= , , , , , , , , .精選ppt10閉包的構(gòu)造方法（續(xù)）閉包的構(gòu)造方法（續(xù)）設(shè)關(guān)系設(shè)關(guān)系R, r(R), s(R), t(R)的關(guān)系矩陣分別為的關(guān)系矩陣分別為M, Mr, Ms 和和 Mt , 則則 Mr = M + E Ms = M + M Mt = M + M2 + M3 + E 是和是和 M 同階的單位矩陣同階的單位矩陣, M是是 M 的轉(zhuǎn)置矩陣的轉(zhuǎn)置矩陣. 注意在上述等式中矩陣的元素相加時使用邏輯加注意在上述等式中矩陣的元素相加時使用邏輯加.精選ppt11閉包的構(gòu)造方法（續(xù)）閉包的構(gòu)

10、造方法（續(xù)）設(shè)關(guān)系設(shè)關(guān)系R, r(R), s(R), t(R)的關(guān)系圖分別記為的關(guān)系圖分別記為G, Gr, Gs, Gt , 則則Gr, Gs, Gt 的頂點(diǎn)集與的頂點(diǎn)集與G 的頂點(diǎn)集相等的頂點(diǎn)集相等. 除了除了G 的的邊以外邊以外, 以下述方法添加新邊：以下述方法添加新邊： 考察考察G的每個頂點(diǎn)的每個頂點(diǎn), 如果沒有環(huán)就加上一個環(huán)，最如果沒有環(huán)就加上一個環(huán)，最終得到終得到Gr . 考察考察G的每條邊的每條邊, 如果有一條如果有一條 xi 到到 xj 的單的單向邊向邊, ij, 則在則在G中加一條中加一條 xj 到到 xi 的反方向邊，最終得的反方向邊，最終得到到Gs. 考察考察G的每個頂點(diǎn)的

11、每個頂點(diǎn) xi, 找從找從 xi 出發(fā)的每一條路徑出發(fā)的每一條路徑，如果從，如果從 xi 到路徑中任何結(jié)點(diǎn)到路徑中任何結(jié)點(diǎn) xj 沒有邊，就加上這沒有邊，就加上這條邊條邊. 當(dāng)檢查完所有的頂點(diǎn)后就得到圖當(dāng)檢查完所有的頂點(diǎn)后就得到圖Gt . 精選ppt12實(shí)例實(shí)例例例1 設(shè)設(shè)A=a,b,c,d, R=, R和和 r(R), s(R), t(R)的關(guān)系圖如下圖所示的關(guān)系圖如下圖所示. Rr(R)s(R)t(R)精選ppt南寧空調(diào)回收 南寧空調(diào)出租 仧莒彾 Microsoft Office PowerPoint，是微軟公司的演示文稿軟件。用戶可以在投影儀或者計(jì)算機(jī)上進(jìn)行演示，也可以將演示文稿打印出來

12、，制作成膠片，以便應(yīng)用到更廣泛的領(lǐng)域中。利用Microsoft Office PowerPoint不僅可以創(chuàng)建演示文稿，還可以在互聯(lián)網(wǎng)上召開面對面會議、遠(yuǎn)程會議或在網(wǎng)上給觀眾展示演示文稿。 Microsoft Office PowerPoint做出來的東西叫演示文稿，其格式后綴名為：ppt、pptx；或者也可以保存為：pdf、圖片格式等精選ppt14定理定理 R是是A上關(guān)系，則上關(guān)系，則R是自反的，當(dāng)且僅當(dāng)是自反的，當(dāng)且僅當(dāng) r(R)=R. R是對稱的，當(dāng)且僅當(dāng)是對稱的，當(dāng)且僅當(dāng) s(R)=R. R是傳遞的，當(dāng)且僅當(dāng)是傳遞的，當(dāng)且僅當(dāng) t(R)=R.證明略，因?yàn)橛砷]包定義即可得。證明略，因?yàn)橛?/p>

13、閉包定義即可得。定理定理 R是是A上關(guān)系，則上關(guān)系，則R是自反的，則是自反的，則s(R)和和t(R)也自反。也自反。 R是對稱的，則是對稱的，則r(R)和和t(R)也對稱。也對稱。 R是傳遞的，則是傳遞的，則r(R)也傳遞。也傳遞。證明證明: 因?yàn)橐驗(yàn)镽自反自反,得得r(R)=R,即即RIA=R, r(s(R)=s(R)IA=(RR-1)IA= (RIA)R-1=r(R)R-1 =RR-1 =s(R)s(R)自反自反 精選ppt15類似可以證明類似可以證明t(R)也自反。也自反。證明證明. 證明證明t(R)對稱對稱:(t(R)-1=(RR2.Rn.)-1 = R-1(R2)-1 .(Rn)-1

14、. = R-1(R-1)2 .(R-1)n. =RR2.Rn. (R對稱，對稱，R-1 =R) =t(R) 所以所以t(R)也對稱。也對稱。類似可以證明類似可以證明r(R)也對稱。也對稱。證明證明. 證明證明r(R)傳遞傳遞:先用歸納法證明下面結(jié)論先用歸納法證明下面結(jié)論: (RIA)i= IARR2.Ri i=1時時 RIA= IAR 結(jié)論成立。結(jié)論成立。 假設(shè)假設(shè)ik 時結(jié)論成立，即時結(jié)論成立，即 (RIA)k= IARR2.Rk(R2)-1=(R R)-1=R-1 R-1=(R-1)2精選ppt16當(dāng)當(dāng)i=k+1時時(RIA)k+1=(RIA)k (RIA) = (IARR2.Rk） (I

15、AR) = (IARR2.Rk)(RR2.Rk+1) = IARR2.RkRk+1所以結(jié)論成立所以結(jié)論成立.t(r(R)=t(RIA)= (RIA)(RIA)2(RIA)3.=(IAR)(IARR2)(IARR2R3).= IARR2R3.= IAt(R)= IAR (R傳遞傳遞t(R)=R) =r(R) 所以所以r(R)也傳遞。也傳遞。 。精選ppt17定理定理設(shè)設(shè)R1、R2是是A上關(guān)系，如果上關(guān)系，如果R1 R2 ，則，則 r(R1) r(R2) s(R1) s(R2) t(R1) t(R2) 證明證明 r(R1)=IAR1 IAR2= r(R2) ，類似可證。，類似可證。定理定理設(shè)設(shè)R是是A上關(guān)系，則上關(guān)系，則 sr(R)=rs(R) tr(R)=rt(R) st(R) ts(R)證明：證明： sr(R)=r(R)(r(R)-1=(RIA)(RIA)-1 = (RIA)(R-1IA-1) =RIAR-1IA = (RR-1)IA= s(R)IA=rs(R) 的證明用前邊證明的結(jié)論：的證明用前邊證明的結(jié)論：(RIA)k= IARR2.Rk很容易證明，這里從略。很容易證明，這里從略。