交大數(shù)理邏輯課件10-3關(guān)系.ppt

1、第10章 關(guān) 系,10.1 二元關(guān)系 10.2 關(guān)系矩陣和關(guān)系圖 10.3 關(guān)系的逆、合成、限制和象 10.4 關(guān)系的性質(zhì) 10.5 關(guān)系的閉包 10.6 等價(jià)關(guān)系和劃分 10.7 相容關(guān)系和覆蓋 10.8 偏序關(guān)系,關(guān)系性質(zhì)的充要條件,設(shè)R為A上的二元關(guān)系, 則 R在A上自反當(dāng)且僅當(dāng) IA R R在A上反自反當(dāng)且僅當(dāng) RIA= R在A上對(duì)稱當(dāng)且僅當(dāng) R=R1 R在A上反對(duì)稱當(dāng)且僅當(dāng) RR1IA R在A上傳遞當(dāng)且僅當(dāng) RRR,證：必要性： R是傳遞 RRR RR (z)(x,zRz,yR) R RRR 充分性： RRR R是傳遞 x,zRz,yR RR R R是傳遞的,R 是傳遞的,RRR,1

2、0.5.2 關(guān)系閉包的定義,閉包的定義 包含R的最小自反關(guān)系是R的自反閉包 包含R的最小對(duì)稱關(guān)系是R的對(duì)稱閉包 包含R的最小傳遞關(guān)系是R的傳遞閉包 一般地，將 R 的 自反閉包記作 r(R), 對(duì)稱閉包記作 s(R), 傳遞閉包記作 t(R,10.5.3 閉包的性質(zhì),定理10.5.4 對(duì)非空集合A上的關(guān)系R，有 若R是自反的 r(R)=R; 若R是對(duì)稱的 s(R)=R; 若R是傳遞的 t(R)=R. 定理10.5.5 對(duì)非空集合A上的關(guān)系R1、R2, 若R1R2 則 r(R1) r(R2) s(R1) s(R2) t(R1) t(R2) 定理10.5.5 對(duì)非空集合A上的關(guān)系R1、R2，則 r

3、(R1) r(R1) = r(R1R2) s(R1) r(R1) = s(R1R2) t(R1) r(R1) = t(R1R2,10.5.4 閉包的構(gòu)造方法,設(shè)R為A上的關(guān)系, 則有 定理10.5.7: r(R) = RR0 = RIA 定理10.5.8: s(R) = RR-1 定理10.5.9: t(R) = RR2R3 定理10.5.10: 設(shè)A為非空集合，|A|=n，則存在一個(gè)正整數(shù)kn，使得 t(R) = RR2R3 Rk (kn) t(R) = RR2R3 Rn 以上分別是自反閉包r(R) 、對(duì)稱閉包s(R)和傳遞閉包t(R)的構(gòu)造方法,證明: t(R) = RR2R3,先證RR2

4、R3 t(R) 當(dāng)n =1時(shí)，R1= R t(R)。 設(shè)n =k時(shí)，Rkt(R)。 下證 Rk+1t(R) x,yRk+1 x,y Rk R (z)(x,zRz,yRk) (z)(x,zt(R)z,yt(R) x,yt(R) 即 Rk+1 t(R) (k0) 故RR2R3 t (R,證明: t(R) = RR2R3,再證t(R)RR2R3 顯然 RRR2R3 下證明RR2R3是傳遞的。 x,zRR2R3z,yRR2R3 (t)(x,zRt )(s)(z,yRs) (s,t0的自然數(shù)) x,yRtRs =Rt+sRR2R3 x,yRR2R3 根據(jù)傳遞關(guān)系的定義，有 RR2R3是傳遞的,閉包的構(gòu)造

5、方法舉例,設(shè)A=a,b,c，定義A上的二元關(guān)系R為： R=a,b,b,c,c,a 試用關(guān)系合成運(yùn)算方法求：r(R)，s(R)，t(R) 解: r(R)= RIA =a,b,b,c,c,a,a,a,b,b,c,c s(R)=RR-1 =a,b,b,c,c,a,b,a,c,b,a,c t(R) = RR2R3 ： R2= RR =a,c,b,a,c,b R3= R2R =a,a,b,b,c,c=IA t(R) =a,a, a,b, a,c, b,a, b,b, b,c, c,a,c,b,c,c= EA,閉包的構(gòu)造方法（矩陣法,設(shè)關(guān)系R, r(R), s(R), t(R)的關(guān)系矩陣分別為M, Mr,

6、 Ms 和 Mt , 則 Mr = M + I Ms = M + M Mt = M + M2 + M3 + 說(shuō)明:I 是和 M 同階的單位矩陣, M是 M 的轉(zhuǎn)置矩陣. 注意:在上述等式中矩陣的元素相加時(shí)使用邏輯加,閉包的矩陣構(gòu)造方法舉例,設(shè)A=a,b,c，定義A上的二元關(guān)系R為： R=a,b,b,c,c,a 試求：t(R) 解：用關(guān)系矩陣求t(R)的方法如下,閉包的矩陣構(gòu)造方法舉例,其中，表示矩陣的對(duì)應(yīng)元素進(jìn)行邏輯加運(yùn)算,閉包同時(shí)具有的多種性質(zhì),定理10.5.11 對(duì)非空集合A上的關(guān)系R，有 若R是自反的 s(R)、t(R)是自反的; 若R是對(duì)稱的 r(R)、t(R)是對(duì)稱的; 若R是傳遞的

7、 r(R)是傳遞的. 證： R是傳遞 RRR， 而r(R)=RIA r(R) r(R) =(RIA) (R IA) =R (R IA) IA (R IA) =R R R IA IA (R IA) =R R (R IA) =R IA = r(R,注意：若R是傳遞的 ，s(R)是不一定是傳遞的. 如：A=1, 2, 3, R= 是傳遞的 r(R) =RIA =, , 是傳遞的 但s(R) =RR -1 =, 不是傳遞,閉包同時(shí)具有的多種性質(zhì),定理10.5.12 對(duì)非空集合A上的關(guān)系R, 有 rs(R) = sr(R) rt(R) = tr(R) st(R) ts(R) 設(shè) A=1, 2, R= s

8、t(R)= s(t(R) =s()= , ts(R)= t(s(R) =t(, ) = , , ,10.6 等價(jià)關(guān)系和劃分,等價(jià)關(guān)系 是最重要、最常見的二元關(guān)系之一。它有良好的性質(zhì)。在計(jì)算機(jī)科學(xué)和計(jì)算機(jī)技術(shù)、信息科學(xué)和信息工程中都有廣泛的應(yīng)用。 定義 設(shè) R 為非空集合上的關(guān)系. 如果 R 是自反的、對(duì)稱的和傳遞的, 則稱 R 為 A 上的等價(jià)關(guān)系. 等價(jià)關(guān)系的關(guān)系矩陣和關(guān)系圖的特點(diǎn) 關(guān)系矩陣的主對(duì)角線全為1且是對(duì)稱陣； 關(guān)系圖每一個(gè)結(jié)點(diǎn)上都有自回路且每?jī)蓚€(gè)結(jié)點(diǎn)間如果有邊，一定有方向相反的兩條邊,等價(jià)關(guān)系的實(shí)例,設(shè)A=1,2,3,4,5，R是A上的等價(jià)關(guān)系， R=1,1,1,2,2,1,2,2

9、,3,3,3,4,4,3,4,4,5,5 則R的關(guān)系矩陣M(R)如下： A上的等價(jià)矩陣可用正方形的一條對(duì)角線和線上的若干正方形表示。 M(R)的主對(duì)角線全為1且是對(duì)稱陣，所以R是自反的和對(duì)稱的；還可以用二元關(guān)系傳遞性的定義證明R是傳遞的。故R是A上的等價(jià)關(guān)系,等價(jià)關(guān)系的實(shí)例,設(shè) A=1,2,3,4,5,6,7,8, A上的關(guān)系 R如下定義： R = | x,yAxy(mod 3) 其中 xy(mod 3) 叫做 x 與 y 模3相等, 即 x 除以3的余數(shù)與 y 除以3的余數(shù)相等. 驗(yàn)證模 3 相等關(guān)系 R 為 A上的等價(jià)關(guān)系 xA, x-x=30，所以 x x(mod 3) (R是自反的)

10、x, yA, 若 x y(mod 3), x-y = 3t，(tZ) y-x =3(t)，(tZ) y x(mod 3) (R是對(duì)稱的） x, y, zA, 若x y(mod 3), y z(mod 3), x-y = 3t1，t1Z，y-z = 3t2， t2 Z x-z=(x-y)+(y-z)=3t1+3t2=3(t1+t2)，t1+t2Z， xz(mod 3) (R是傳遞的,A上模3等價(jià)關(guān)系的關(guān)系圖,設(shè) A=1,2,3,4,5,6,7,8, R= | x, y A x y (mod 3) 1(mod 3)=4(mod 3)=7(mod 3)=1 2(mod 3)=5(mod 3)=8(m

11、od 3)=2 3(mod 3)=6(mod 3)=0,等價(jià)類,定義 設(shè)R為非空集合A上的等價(jià)關(guān)系, xA，令xR = y | yAxRy 稱 xR 為 x 關(guān)于R 的等價(jià)類, 簡(jiǎn)記為x. 實(shí)例 A=1,2,3,4,5,6,7,8 上模 3 等價(jià)關(guān)系的等價(jià)類： 1R=4R=7R=1,4,7 2R=5R=8R=2,5,8 3R=6R=3,6,等價(jià)類的性質(zhì),定理10.6.1 設(shè)R是非空集合A上的等價(jià)關(guān)系，對(duì)x, y A ，下面的結(jié)論成立。 (1) xR ，且xRA ； (2) 若 R，則xR=yR； (3) 若 R，則xRyR= ； (4,任何等價(jià)類都是A的非空子集,A中任取兩個(gè)元素，它們的等價(jià)類

12、或相等、或是不相交,所有等價(jià)類的并集就是A,A中任取兩個(gè)元素，它們的等價(jià)類或相等、或是不相交,等價(jià)類的性質(zhì)舉例,實(shí)例: A=1,2,8 上模 3 等價(jià)關(guān)系的等價(jià)類： 1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,6 12= 13= 23= 1,4,7 2,5,8 3,6=A,商集,定義 設(shè)R為非空集合A上的等價(jià)關(guān)系, 以R的所有不交的等價(jià)類作為元素的集合，稱為A在R下的商集, 記做A/R, A/R = xR | xA 實(shí)例 A=1,2,3,4,5,6,7,8， A關(guān)于模3等價(jià)關(guān)系R的商集為 A/R = 1,4,7, 2,5,8, 3,6 =0, 1, 2 A關(guān)于恒等關(guān)系IA商集為

13、： A/IA = 1,2, ,8= x | xA A關(guān)于全域關(guān)系EA的商集為： A/EA = 1, 2, ,8 =A,10.6.2 集合的劃分,定義 設(shè)A為非空集合, 若存在集合 滿足下面條件： (1) (x)(xx A) (即 P(A) (2) (3) =A (4) xy (x,yxyxy=) 滿足條件(1)(2)(3)，稱是A 的覆蓋. 滿足全部條件稱為A 的一個(gè)劃分， 稱中的元素為A的劃分塊. 如： A關(guān)于模3等價(jià)關(guān)系R的商集是A的一個(gè)劃分 A/R = 1,4,7, 2,5,8, 3,6 1,4,7, 1,2,5,8, 3,5,6 為A的一個(gè)覆蓋,商集和劃分的關(guān)系,定理10.6.2 對(duì)非

14、空集合A上的一個(gè)等價(jià)關(guān)系R，A商集A/R就是A的一個(gè)劃分。它稱為由等價(jià)關(guān)系R誘導(dǎo)出來(lái)的A的劃分，記作R 即由A上的等價(jià)關(guān)系R可以誘導(dǎo)出A的一個(gè)劃分。 定理10.6.3 對(duì)非空集合A上的一個(gè)劃分，令A(yù)上的關(guān)系R為 R=|(z)(z xz yz 則R是A上的等價(jià)關(guān)系，它稱為劃分誘導(dǎo)出來(lái)的A上的等價(jià)關(guān)系。 定理10.6.4 對(duì)非空集合A上的一個(gè)劃分和A上的等價(jià)關(guān)系R，誘導(dǎo)R當(dāng)且僅當(dāng)R誘導(dǎo)。 所以，集合A上的等價(jià)關(guān)系與集合A的劃分是一一對(duì)應(yīng)的,由劃分導(dǎo)出等價(jià)關(guān)系的方法,定理 設(shè)S=S1，S2，Sm是A的一個(gè)劃分， R=x,y| x和y在同一個(gè)劃分塊中 則R是A上的等價(jià)關(guān)系。 劃分S導(dǎo)出的等價(jià)關(guān)系R可以

15、表示為： R =(S1S1)(S2S2)(SmSm) 例：設(shè)A=1,2,3,4，A的劃分S=1, 2,3, 4， 則從S導(dǎo)出的等價(jià)關(guān)系R為： R=1,1,2,2,2,3,3,2,3,3,4,4 =112,32,344 可以驗(yàn)證R是A上的等價(jià)關(guān)系,設(shè) A=1,2,3，求出A上所有的等價(jià)關(guān)系,解：先寫出集合X上的所有劃分，它們是： 1=2,3,1, 2=1,3,2 3=1,2,3， 4=1,2,3， 5=1,2,3,設(shè) A=1,2,3，求出A上所有的等價(jià)關(guān)系,對(duì)應(yīng)的等價(jià)關(guān)系為： R1=2,32,311 =2,2,2,3,3,2,3,3,1,1 R2=1,31,322 =1,1,1,3,3,1,3,

16、3,2,2 R3=1,21,233 =1,1,1,2,2,1,2,2, 3,3 R4=1,2,31,2,3=AA=EA R5=112233 =1,1,2,2,3,3=IA,1=2,3,1, 2=1,3,2, 3=1,2,3， 4=1,2,3， 5=1,2,3,由等價(jià)關(guān)系求劃分的實(shí)例,例 設(shè) A=1, 2, 3, 4，在 A上定義二元關(guān)系R： ,R x+y = u+v， 求 R 導(dǎo)出的劃分. 解：根據(jù) 的 x + y = 2,3,4,5,6,7,8 將AA劃分成7個(gè)等價(jià)類： (AA)/R= , , , , , , , , , , , , , ,10.7 相容關(guān)系和覆蓋,定義 對(duì)非空集合A上的關(guān)系

17、R，如果R是自反的和對(duì)稱的，則稱R為A上的相容關(guān)系。 相容關(guān)系的性質(zhì) 所有等價(jià)關(guān)系都是相容關(guān)系。 相容關(guān)系的關(guān)系矩陣主對(duì)角線全為1且是對(duì)稱陣。 相容關(guān)系的關(guān)系圖每一個(gè)結(jié)點(diǎn)上都有自回路且每?jī)蓚€(gè)結(jié)點(diǎn)間如果有邊，一定有方向相反的兩條邊,相容關(guān)系舉例,設(shè)A=316,347,204,678,770, A上的二元關(guān)系R定義為 R=x,y| xAyAx和y有相同數(shù)碼， xA， 有R， R是自反的； R， 有R， R是對(duì)稱的。 于是，R是相容關(guān)系。 令a=316，b=347，c=204，d=678，e=770 R=a,a,a,b,a,d,b,a,b,b,b,c,b,d, b,e,c,b,c,c,c,e,d,a

18、,d,b,d,d, d,e,e,b,e,c,e,d,e,e,相容類,定義 對(duì)非空集合A上的相容關(guān)系，若CA，對(duì)a,bC, 有a,bR，則稱C是由相容關(guān)系R產(chǎn)生的相容類。 相容類的性質(zhì) 相容類C A xA，x是由相容關(guān)系R產(chǎn)生的一個(gè)相容類。 上例中， a,a,b,b,c都是R產(chǎn)生的相容類。 a,b,d、b,c,e和b,d,e也是R 產(chǎn)生的相容類,最大相容類,定義 對(duì)非空集合A 是上的相容關(guān)系R，一個(gè)相容類若不是任何相容類的真子集，就稱為最大相容類。記為CR。 最大相容類CR的性質(zhì)： (x)(y)(xCR yCR ) xRy) CR中任意元素x與y都有相容關(guān)系R (x)(xA-CR (y)(yCR xRy) A-CR中沒(méi)有一個(gè)元素與CR中 的所有元素都有相容的關(guān)系R,最大相容類,最大相容類簡(jiǎn)化關(guān)系圖的特點(diǎn)： 最大完全多邊形的頂點(diǎn)構(gòu)成的集合是最大相容類。 孤立點(diǎn)構(gòu)成的集合是最大相容類。 如果一條邊不是任何完全多邊形的邊，則它的兩個(gè)端點(diǎn)構(gòu)成的集合是最大相容類 例如右圖： 最大完全3邊形的頂點(diǎn)構(gòu)成的集合： 2,3,5和2,3