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

1、離散數(shù)學(xué),集合論,2 / 68,主要內(nèi)容,集合代數(shù) 二元關(guān)系 函數(shù),集合的基本概念 集合的運(yùn)算 有窮集合的計(jì)數(shù) 集合恒等式,有序?qū)εc笛卡兒積 二元關(guān)系 關(guān)系的運(yùn)算 關(guān)系的性質(zhì) 關(guān)系的閉包 等價(jià)關(guān)系與劃分 偏序關(guān)系,函數(shù)的定義與性質(zhì) 函數(shù)的復(fù)合與反函數(shù) 雙射函數(shù)與集合的基數(shù),3 / 68,7.5 關(guān)系的閉包,一. 閉包的定義 定義7.14 設(shè)R是非空集合A上的關(guān)系,R的自反閉包(對(duì)稱閉包,傳遞閉包)是 A上的關(guān)系 R ,它滿足: (1) R 是自反的 (對(duì)稱的,傳遞的)； (2) R R ; (3) 對(duì)A上任何包含 R 的自反關(guān)系 (對(duì)稱關(guān)系,傳遞關(guān)系) R 都有R R . 注:R的自反閉包記為

2、 r(R),對(duì)稱閉包記為 s(R),傳遞閉包記 為 t(R).,Reflexive, Symmetric, Transtive: r(R), s(R), t(R).,4 / 68,閉包的計(jì)算,定理 7.10 設(shè)R是A上的關(guān)系,則 (1) r(R)=RR0; (2) s(R)= RR-1; (3) t(R)= RR2R3. 證明：(1) 由IA= R0 RR0 知, RR0 是自反的,且R RR0. 設(shè)R是A上包含R的自反關(guān)系,則 R R , IA R, 因而 RR0 RIA RR = R 即 RR0 R .可見(jiàn)RR0滿足自反閉包的定義,從而 r(R)= RR0. (2) 略.,5 / 68,閉

3、包的計(jì)算,(3)先證RR2 t(R),為此只需證明對(duì)任意正整數(shù)n都有 Rnt(R). 用歸納法. 當(dāng)n=1時(shí), R1 = R t(R). 假設(shè) Rn t(R), 下證 Rn+1t(R) 事實(shí)上,由于 Rn+1 = Rn R t(Rn R) t(t(R) t(R) t(R) 從而 Rn+1 t(R) . 由歸納法完成證明.,6 / 68,閉包的計(jì)算,下證 RR2 是傳遞的. 事實(shí)上,對(duì)任意 , ( RR2)( RR2) t (Rt) s(Rs) ts( Rt Rs) ts( Rt+s) RR2 從而 RR2 是傳遞的. 因t(R)是傳遞閉包, 故t(R) RR2. 由以上兩方面知, t(R) R

4、R2 .,7 / 68,通過(guò)關(guān)系矩陣求閉包,證:由定理7.6和定理7.10立即得證.,通過(guò)關(guān)系矩陣求閉包 設(shè)關(guān)系R, r(R), s(R), t(R)的關(guān)系矩陣分別為M, Mr, Ms, Mt, 則: Mr = M+E, Ms = M+M, Mt = M+M2+M3+, 其中E是與M同階的單位矩陣.M是M的轉(zhuǎn)置矩陣,矩陣元素相加時(shí)使用邏輯加.,推論 設(shè)R是有限集合A上的關(guān)系，則存在正整數(shù)r使得 t(R)= RR2Rr.,r(R) = RIA r(R) R IA mxy = 1 exy = 1,8 / 68,通過(guò)關(guān)系圖求閉包,設(shè)關(guān)系R, r(R), s(R), t(R)的關(guān)系圖分別記為G, Gr

5、, Gs, Gt, 則Gr, Gs, Gt的頂點(diǎn)集與G的頂點(diǎn)集相同.除了G的邊外,依下述方法添加新邊: (1)對(duì)G的每個(gè)頂點(diǎn),如果無(wú)環(huán),則添加一條環(huán),由此得到Gr; (2)對(duì)G的每條邊,如果它是單向邊,則添加一條反方向的邊.由此得到Gs;,(3) 對(duì)G的每個(gè)頂點(diǎn)xi ,找出從xi 出發(fā)的所有2步, 3步, , n步長(zhǎng)的有向路 (n為G的頂點(diǎn)數(shù)).設(shè)路的終點(diǎn)分別為 ,如果從 xi 到 xj 無(wú)邊,則添上這條邊.如上處理完所有頂點(diǎn)后得到 Gt,9 / 68,Warshall算法,設(shè)A=x1,x2,xn,R為A上的二元關(guān)系,R的關(guān)系矩陣為M: 1. Mt = M+M2+Mn 2. Warshall算

6、法 考慮矩陣序列 M0,M1,Mn= Mt : k=0,1,nMki,j=1 當(dāng)且僅當(dāng) 在GR中存在一條從xi到xj的路徑并且除端點(diǎn)外中間只經(jīng)過(guò)x1,x2,xk中的頂點(diǎn). Mk+1i,j=1 當(dāng)且僅當(dāng) 在GR中存在一條從xi到xj的路徑并且除端點(diǎn)外中間只經(jīng)過(guò)x1,x2,xk,xk+1中的頂點(diǎn) Mki,j=1 或者 Mki,k+1=1 Mkk+1,j=1,10 / 68,Warshall算法示例,設(shè) A=a,b,c,d, R=,求 t( R ). 解,Mk+1i,j=1 Mki,k+1=1 Mkk+1,j=1,11 / 68,閉包的性質(zhì),定理7.11 設(shè)R是非空集合A上的關(guān)系,則 (1) R 是

7、自反的當(dāng)且僅當(dāng)r(R)=R (2) R 是對(duì)稱的當(dāng)且僅當(dāng) s(R)=R (3) R 是傳遞的當(dāng)且僅當(dāng) t(R)=R 證:(1) 充分性顯然.下證必要性. 因 R 是包含了 R 的自反關(guān)系,故r(R)R. 另一方面,顯然 Rr(R). 從而,r(R)=R. (2), (3)略. 定理7.12 設(shè) R1 和 R2 是非空集合A上的關(guān)系,且 R1R2 , 則 (1)r(R1)r(R2); (2)s(R1) s(R2); (3)t(R1) t(R2) 證明略,12 / 68,閉包的性質(zhì),定理7.13 設(shè) R 是非空集合A上的關(guān)系 （1）若R是自反的,則 s(R) 和 t(R) 也是自反的. （2）若R

8、是對(duì)稱的,則 r(R) 和 t(R) 也是自反的. （3）若R是傳遞的,則 r(R) 也是傳遞的. 證明:只證 (2) . 先考慮r(R). 因R是 A上的對(duì)稱關(guān)系。故R=R-1 , 同時(shí) IA = IA-1 ,于是 (RIA)-1=R-1IA-1 (根據(jù)習(xí)題7.20). 從而 r(R)-1 = (RR0)-1 = (RIA)-1 = R-1IA-1 = RIA = r(R) . 這便說(shuō)明 r(R) 是對(duì)稱的. 下面證明t(R)的對(duì)稱性.為此,先用數(shù)學(xué)歸納法證明: 若R是對(duì)稱的, 則對(duì)任何正整數(shù)n, Rn也是對(duì)稱的. 事實(shí)上,當(dāng)n=1時(shí),R=R 顯然是對(duì)稱的.,13 / 68,閉包的性質(zhì),假設(shè)Rn是對(duì)稱的,下證Rn+1 的對(duì)稱性.由于 Rn+1 Rn R t (Rn)R) t (Rn)R) R Rn Rn+1 故 Rn+1 是對(duì)稱的.歸納法定成. 現(xiàn)在來(lái)證 t(R)的對(duì)稱性.由于 t(R) n(Rn) n(Rn) t(R) 因此t(R)是對(duì)稱的. 注:由于對(duì)稱閉包運(yùn)算不保持傳遞性,故在運(yùn)算順序 上它應(yīng)放在傳遞閉包之前,即 t s r(R)=t(s(r(R).,14 / 68,注,二元關(guān)系的閉包仍然是二元關(guān)系,還可以求它的閉包. 例如,R是A上的二元關(guān)系, r(R)是它的自反閉包,還可以求r(R)的對(duì)稱閉包.r(R)的對(duì)稱閉包記為s(r(R)