離散數(shù)論-第六章

1、第六章 關(guān)系6.1 關(guān)系及其性質(zhì) 6.2 關(guān)系的運(yùn)算6.3 次序關(guān)系6.4 等價(jià)關(guān)系與劃分16.1 關(guān)系及其性質(zhì)重點(diǎn)：1. 關(guān)系的表示2. 關(guān)系的性質(zhì)2一、關(guān)系的定義定義6.1(關(guān)系):任何有序偶的集合稱為 二元關(guān)系,簡稱為關(guān)系，一般記作 R。X 到Y(jié)的關(guān)系: 若 R 是 X Y的子集 ( 即 R X Y ), 則稱 R 為 X 到 Y 的關(guān)系。當(dāng) X = Y時(shí), 稱 R 為 X 上 的二元關(guān)系。若 R , 則可表示成 x R y , 讀做 “x與y有關(guān)系R”若 R , 則記作 x R y, 讀作 “ x與y不存在關(guān)系R”3例1: A = 1, 2, 3, B = a, b R = , , 是

2、 A 到 B的關(guān)系。例2：實(shí)數(shù)集合上的大于關(guān)系 “ ” 表示如下： = | x , y 是實(shí)數(shù) 且 x y 空關(guān)系：設(shè) X 是集合，X X的子集 ，稱為 X上的空關(guān)系。X上的全域關(guān)系: UX = | xi ，xj X = X XX上的恒等關(guān)系：IX = | x X4例3：設(shè) X = 0, 1, 2 UX = , , , , , , , , IX = , , 定義6.2 設(shè) R X Y,dom (R) = x X | y Y: R , R 的定義域 ran (R) = y Y | x X : R , R 的值域 顯然， dom (R) X， ran (R) Y5二、關(guān)系的表示關(guān)系矩陣：設(shè) X =

3、 x1,xm , Y = y1,yn , R是 X 到 Y 的關(guān)系。 R 的關(guān)系矩陣記作 MR = (rij)mn , 其中 0 若 xi R yj rij = 1 若 xi R yj例 6.3 設(shè) X = x1 , x2 , Y =y1 , y2 , y3 , R是 X 到 Y 的關(guān)系。6R的關(guān)系矩陣是 : 1 0 0 1 1 12. 關(guān)系圖: 設(shè) X 是有窮集合, X 上的二元關(guān)系R 的關(guān)系圖構(gòu)造如下 :R = , , , 7 X 集合中的元素稱為頂點(diǎn) , 并用點(diǎn)或小圈表示 , 對于元素 xi 和 xj , 分別標(biāo)以頂點(diǎn)xi 和 xj . 如果xi R xj ，即R , 就用一條帶箭頭的弧

4、線把xi 和 xj 連接起來，箭頭的方向由xi 指向 xj ；如果 xi R xj 且xj R xi , 則在xi 和 xj 之間畫上兩條方向相反的弧線 ;如果 xi R xi，則畫一條從xi 出發(fā)又返回頂點(diǎn) xi 的弧線，稱這一條弧線為自環(huán) . 當(dāng) R 中所有有序偶處理完畢后 , 便得到關(guān)系 R 的圖 . 81234圖6.4 集合 X 上的關(guān)系圖例6.4 : 設(shè) X =1 , 2 , 3 , 4 , R是集合 X 上的關(guān)系, R = , , , , , , ,則 R的關(guān)系圖如下：9三、關(guān)系的性質(zhì)（包括自反、反自反、對稱、反對稱、傳遞）定義6.3 設(shè)R是非空集合X上的二元關(guān)系R是自反的x(xX

5、 R)關(guān)系圖中每個(gè)頂點(diǎn)有自環(huán).關(guān)系矩陣中主對角線元素均為1.R是反自反的x(xX R)關(guān)系圖中每個(gè)頂點(diǎn)均無自環(huán).關(guān)系矩陣中主對角線元素均為0.10R是對稱的xy (xX y X R R )關(guān)系圖中任兩個(gè)不同頂點(diǎn)間或者無弧或者有兩條方向相反的弧.關(guān)系矩陣是對稱矩陣.R是反對稱的xy (xX yX R R x = y) (或者)xy (xX yX R x y R )關(guān)系圖中任兩點(diǎn)間至多有一條弧.關(guān)系矩陣中 , 若 rij = 1 , 則 rji =011R是傳遞的xyz (xX yX zX R R R )關(guān)系圖中，若任意頂點(diǎn) x到任意頂點(diǎn)y有一條路徑， 則從 x 到 y 必有一條弧。從關(guān)系矩陣中不

6、易看出傳遞關(guān)系的特征。例 (1) X上的恒等關(guān)系是自反、對稱、反對稱、 傳遞的 (2) X上的“ ”是反自反、反對稱、傳遞的12圖6.5給出了一些關(guān)系圖.指出由這些圖給定的關(guān)系所具有的性質(zhì),并寫出對應(yīng)的關(guān)系矩陣.x5x1x2x3x1x2x3x4(a)(b)x1x2x3x4(c)圖6.5 關(guān)系圖(d)x2x1x3x413解 圖6.5(a)的關(guān)系是反對稱的 , 反自反的. 圖6.5(b)的關(guān)系是自反的、對稱的、反對稱的、 和可傳遞的。 圖6.5(c)的關(guān)系是自反的，對稱的。 圖6.5(d)的關(guān)系是反自反的、反對稱的、傳遞的。146.2關(guān)系的運(yùn)算重點(diǎn)掌握關(guān)系的復(fù)合、逆、自反閉包、對稱閉包、傳遞閉包等

7、定義及運(yùn)算定義6.4 設(shè)R和S是從集合A到集合B的關(guān)系，取全集為AB，則RS，RS，RS，R仍然是A到B的關(guān)系，并且對于任意xA,yB,x(RS)y xRyxSyx(RS)y xRyxSyx(RS)y xRyx S yx(R)y xRy15例4.12 設(shè)R和S是集合A1,2,3,4上的關(guān)系，Rx,yxy是2的非零整倍數(shù)Sx,yxy是3的非零整倍數(shù)求：RS，RS，RS和R。解 R1,3,3,1,2,4 4,2S1,4,4,1RSRS1,3,3,1,2,4,4,2,1,4,4,1RS1,3,3,1,2,4,4,2R1,1,1,2,1,4,2,1,2,2,2,3,3,2,3,3,3,4,4,1,4,

8、3,4,416定義6.5 關(guān)系R和S的復(fù)合關(guān)系RS定義為： RSx,zy(xRyySz)。若R是X到Y(jié)的關(guān)系,S是Y到Z的關(guān)系,則R和S的復(fù)合關(guān)系RS是X到Z的關(guān)系,即RSx,zxXz Z y(y Y xRyySz)。RSRS17例4.13 設(shè)R1,2,2,2,3,4, S1,3,2,5,3,1,4,2求:R S , S R , (R S) R，R (S R)，R R。解:R S =, , S R=, R R=,顯然，dom(RS)dom(R)，ran(RS) ran(S)。 R SS R，所以關(guān)系的復(fù)合運(yùn)算不滿足交換律。 (R S) R= R (S R)=可證關(guān)系的復(fù)合運(yùn)算滿足結(jié)合律。18定

9、理6.1 設(shè)R，S，P是三個(gè)關(guān)系，則(R S)PR(SP)。證明 對任意x,w，x,w(RS)P z(x,zRSz,wP) z( y(x,yRy,zS)z,wP) y(x,yR z(y,zSz,wP) y(x,yRy,wSP)x,wR(SP)故(RS)PR(SP)。19例6.8 設(shè)R和S是整數(shù)集合Z上的兩個(gè)關(guān)系，Rx,2xxZ，Sx,7xxZ求：RS，R R，R R R和R S R。解R Sx,14xxZR Rx,4xxZR R Rx,8xxZR S Rx,28xxZ定義4.16 設(shè)R是集合A上的關(guān)系，n是自然數(shù)，R的n次冪Rn定義如下：(1) R0 是集合A上的恒等關(guān)系IA，即R0IA；(2

10、) Rn1Rn R。顯然，R1R0 RIA RR 20對n歸納易證，對于任意m,nN，(1) Rm RnRmn(2) (Rm)nRmn兩個(gè)關(guān)系的復(fù)合，也可以用矩陣運(yùn)算來表示。用矩陣運(yùn)算求兩個(gè)關(guān)系的復(fù)合多用于一個(gè)集合上的關(guān)系的復(fù)合。為了不失一般性，下面介紹A到B的關(guān)系和B到C的關(guān)系的復(fù)合。關(guān)系復(fù)合的矩陣表示：21設(shè)集合Aa1,a2,am, Bb1,b2,bp, Cc1,c2,cn,R是A到B的關(guān)系，S是B到C的關(guān)系，關(guān)系矩陣MR(rij)mp ，MS(sij)pn , 則RS的關(guān)系矩陣 MRS (tij)mn ，其中 tij (ri1s1j ) (ri2s2j ) (ripspj) (riksk

11、j ) 因?yàn)橛蓮?fù)合關(guān)系的定義，ai,cjRS當(dāng)且僅當(dāng)，存在bk使得ai,bkR且bk,cjS。即rikskj1。故rikskj1。也就是說，ri1s1j，ri2s2j，ripspj中至少有一個(gè)是1，即(ri1s1j ) (ri2s2j ) (ripspj)1 。 pK=122例：設(shè)集合Aa,b,c,d上的關(guān)系Ra,b,b,a,b,c,c,d,求R2的關(guān)系矩陣。解： MR MR2 * 23顯然，dom(R 1 )ran(R)，ran(R 1 )dom(R)， R1 的逆關(guān)系是R，即(R 1 ) 1 R 。若R和S都是關(guān)系，則(RS) 1 R 1 S 1 。R 1 的關(guān)系矩陣是R的關(guān)系矩陣MR的轉(zhuǎn)

12、置矩陣。將R的關(guān)系圖中的每條有向邊的方向反向，就得到R 1 的關(guān)系圖。定義6.7 將關(guān)系R中每個(gè)有序偶的第一元和第二元對換所得到的關(guān)系稱為R的逆關(guān)系，記作R1， R1x,yy,xR。例如：Ra,1,a,3,b,1,b,2,c,1 R11,a,3,a,1,b,2,b,1,c24定理6.2 設(shè)R和S是關(guān)系，則(RS)1S 1 R 1 。證明 對于任意z,x， z, x (R S) 1 x,zRS y(x,yRy,zS) y(y,xR1z,yS1) z,xS1R1因此，(RS) 1S1R1 。25定義6. 8 設(shè)R是集合A上的關(guān)系。關(guān)系R 稱為R的自反閉包（對稱閉包、傳遞閉包），當(dāng)且僅當(dāng)R滿足以下三

13、個(gè)條件：(1) R 是自反的（對稱的、傳遞的）；(2) R R ；(3) 對于A上的任何自反（對稱、傳遞）關(guān)系R，如果 R R ，則R R。將R的自反閉包、對稱閉包、傳遞閉包分別記作r(R),s(R),t(R)。由定義知道，R是自反的當(dāng)且僅當(dāng)r(R)R，R是對稱的當(dāng)且僅當(dāng)s(R)R，R是傳遞的當(dāng)且僅當(dāng)t(R)R 。26定理6.3 設(shè)R是集合A上的關(guān)系，則r(R)R IA 。證明 顯然RIA是自反的且R RIA 。設(shè)R是A上自反關(guān)系且RR ，則IA R ，因此RIAR 。由自反閉包的定義知道，r(R)RIA 。引理6.1 設(shè)R是A上的關(guān)系，R對稱當(dāng)且僅當(dāng)R=R1 。證明 ：若R對稱，則對任意,

14、R R R1 ,因此R=R1 若R=R1 ,則對任意， R R1 R, 因此R對稱.所以R對稱當(dāng)且僅當(dāng)R=R127定理6.4 設(shè)R是集合A上的關(guān)系，則s(R)RR1 。證明 (RR1 ) 1 R1 (R1 ) 1 R1 RRR1，由引理6.1知道，RR 1 是對稱的。顯然RRR1 。設(shè)R是A上任意對稱關(guān)系且RR ，則R1 (R) 1 。因?yàn)镽是對稱的，由引理6.1，(R) 1 R ，R1 R ，所以RR 1 R 。由對稱閉包的定義知道，s(R)RR1 。，定理6.5 設(shè)R是集合A上的關(guān)系，則t(R)RR2R3 =證明： 只要證明t(R)與 互包含即可。首先用歸納法證：對于任意n1， Rn t(

15、R)。由傳遞閉包的定義可知， R t(R)。設(shè)對于任意n1,28Rnt(R),證明Rn+1t(R)。設(shè) Rn+1 ，由于Rn+1 = Rn R，則存在z A ，使得 Rn， R。根據(jù)歸納假設(shè)和歸納基礎(chǔ)，有 t(R)和 t(R)，由此可得 t(R)，則Rn+1t(R)。由于對于所有的n1， Rnt(R)，因此 t(R) 再 證 t(R) 顯然 R 。只要再證 是傳遞的即可。設(shè)任意 ， ，則存在正整數(shù)s和k，使得 Rs , Rk ,這樣 Rs+k ，因此有 ，所以 是傳遞的。由t(R)的最小性，得t(R) 29定理 6. 6 設(shè)R是集合A上的關(guān)系， A有n個(gè)元素，則t(R)例：設(shè)集合Aa,b,c上

16、的關(guān)系Ra,b,b,c,c,c， 求：r(R), s(R), t(R)。解 r(R)RIAa,b,b,c,c,c,a,a,b,bS(R)RR1a,b,b,c,c,c,b,a,c,bR2a,c,b,c,c,c R3 = a,c,b,c,c,c= R2t(R)RR2a,b,b,c,c,c , a,c30例6.10 設(shè)集合Aa,b,c,d, A上的關(guān)系Ra,b,b,a,b,c,c,d，試畫出t(R)關(guān)系圖。R關(guān)系圖t(R)關(guān)系圖abcdbacd31例6.10 設(shè)集合Aa,b,c,d, A上的關(guān)系Ra,b,b,a,b,c,c,d，試畫出t(R)關(guān)系圖。R關(guān)系圖abcdt(R)關(guān)系圖bacd326.3

17、次序關(guān)系重點(diǎn): 偏序關(guān)系 畫哈斯圖 求偏序集合中的特殊元素次序關(guān)系包括：偏序關(guān)系，全序關(guān)系，嚴(yán)格偏序關(guān)系，良序關(guān)系。33定義6.9（偏序關(guān)系）集合P上的關(guān)系R稱為P上的偏序關(guān)系，當(dāng)且僅當(dāng)R是自反的、反對稱的和傳遞的。例：N , ,N , ,P(A) , 都是偏序集合。定義6.10（全序關(guān)系）設(shè)P , 是一個(gè)偏序集合，如果對于每一個(gè)x ，yP，或者有xy ，或者yx，則稱為P上的全序或線序，并稱P , 為全序集合或鏈。即 (x) (y)(xPyPxyyx) 用“”表示偏序關(guān)系，并用P , 表示偏序集合。 如果x , yP 且xy，則稱“ x 小于或等于y ”或“ x 在 y 之前 ”。34對于偏

18、序集合P , ，如果兩元素 x , y P，或者有xy 或者有yx，就說P的元素 x 和 y 是可比的。例：N , ,N , 都是全序集合。它們中的任意元素 x 和 y 都是可比的定義6.11（嚴(yán)格偏序關(guān)系） R是集合P上的嚴(yán)格偏序關(guān)系，當(dāng)且僅當(dāng)R是反自反的和傳遞的。 用“”表示嚴(yán)格偏序關(guān)系，并稱“ x 小于y ”，稱P , 為嚴(yán)格偏序集合。35例： N , ,N , ,P(A) , 都是嚴(yán)格偏序集合。例：證明 若R是P上嚴(yán)格偏序關(guān)系，則R是反對稱的。證明：假設(shè)R不是反對稱的，則存在x , yP且xy，使得 x , yR 且 y , x R因?yàn)镽是傳遞的，所以 x , x R ，這與R是反自反

19、的矛 盾。由上述證明可知， P上的嚴(yán)格偏序關(guān)系和偏序關(guān)系有如下關(guān)系： I P 36 xy x yxy y遮蓋x xy z (zPxzzy)遮蓋：例：P1，2，3，4，是P上的小于或等于關(guān)系，則稱4遮蓋了3 ，3遮蓋了2 ，2遮蓋了1 .若是P上的大于或等于關(guān)系，則上述遮蓋關(guān)系恰好相反。哈斯圖： 在偏序集合P , 中，對于任何兩個(gè)元素 x , yP，如果 xy 并且不存在任何其它的元素 zP，使得 xz 和 zy，則稱 y 遮蓋x . 偏序集合通常用簡化的關(guān)系圖來表示，這種關(guān)系圖稱為偏序集合圖或哈斯圖.37哈斯圖具體畫法如下：集合的每一個(gè)元素用一個(gè)點(diǎn)表示，對于 x , yP ，如果 xy ，則點(diǎn)

20、 x 畫在點(diǎn) y 之下，如果 y 遮蓋 x ，就在 x 和 y 之間畫一條直線，在哈斯圖中省略了自環(huán)，并約定弧的指向向上，不畫箭頭 .例：畫出滿足下列條件的哈斯圖 . Pa1，2，3，4，并設(shè)是Pa上的小于或等于關(guān)系 . 1234a , b , ca , ba Pb ,a,a , b,a , b , c,并設(shè) 是Pb上的包含關(guān)系。解：見右圖解：見右圖38例：設(shè) X=2，3，6，12，24，36，為整除關(guān)系，如果 x 整除 y ，便有 xy . 畫出X , 的哈斯圖 .336261224解：見右圖解：見右圖例：設(shè)A=a，b，c， 是冪集（A）上的包含關(guān)系，畫出 （A） ， 的哈斯圖 a,b,ca

21、,ba, cb,cabc39 b是B的最大元 bB x (xB xb) b是B的最大下界 b是B的下界且對每一個(gè)B的下界x都有xb 偏序集合中的特殊元素：定義6.12 設(shè)A , 是偏序集合，并且B A，則 b是B的最大元 bB x (xB xb) b是B的最小元 bB x (xB bx) b是B的極大元 bB x (xB bx) b是B的極小元 bB x (xB xb) 定義6.13 設(shè)A , 是偏序集合，并且B A，則 b是B的上界 bA x (xB xb) b是B的下界 bA x (xB bx) b是B的最小上界 b是B的上界且對每一個(gè)B的上界x都有bx40 若B是有窮集，則B的極大元、極

22、小元必存在，但B的最大元、最小元不一定存在 .例：設(shè)集合A1, 2, 3, 4, 5, 6, 關(guān)系是整除關(guān)系，畫出哈斯圖，并指出A的極大元、極小元、最大元、最小元、上界、下界、最小上界、最大下界. 由上述定義可知： B的最大元、最小元若存在，則唯一； B的極大元、極小元若存在，不一定唯一；A的極大元：4, 5, 6 極小元：1 最大元： 無 最小元：1 上界： 無 下界： 1 最小上界：無 最大下界：1 12364541定義6.14（良序集合）：一個(gè)偏序集合P , ，如果它的每一個(gè)非空子集都有一個(gè)最小元，則稱關(guān)系為良序關(guān)系， P , 為良序集合 . 由定義可知，每一個(gè)良序集合都是一個(gè)全序集合

23、. 即每一個(gè)全序集合不一定是良序的，但有窮的全序集合一定是良序的 例： N , 是全序集合，也是良序集合； N , 是全序集合，但不是良序集合，因?yàn)樗鼪]有最小元。 R , 是全序集合，但不是良序集合，例如它的子區(qū)間（1，2）就沒有最小元。426.4 等價(jià)關(guān)系與劃分例6.18 設(shè)R是集合A1,2,3,4,5,6,7上的關(guān)系，Rx,yxAyA(xy)能被3整除（模3同余關(guān)系），說明R是一個(gè)等價(jià)關(guān)系，并畫出其關(guān)系圖。 解：畫出其關(guān)系圖由關(guān)系圖可見，R是A上自反的、對稱的、傳遞的關(guān)系，因此，R是A上的等價(jià)關(guān)系。定義（等價(jià)關(guān)系） 如果R是集合A上自反的、對稱的、傳遞的關(guān)系，則稱R為A上的等價(jià)關(guān)系。43例

24、：設(shè)集合X是整數(shù)集合I 的任意子集，證明X上的模m同余關(guān)系是等價(jià)關(guān)系。證明：自反性，對于任意x X，因?yàn)椋▁-x）/ m=0 I，所以xx（mod m）。對稱性，對于任意x，y X ，若xy（mod m），則存在n I，使得（x-y）/ m=n I，于是有 （ y - x ）/ m=-n I，因此， y x （mod m）傳遞性，對于任意x，y ，z X ，若xy（mod m）， y z（mod m）則存在n ，kI，使得模3同余關(guān)系是模同余關(guān)系的特例。下面證明對于任意正整數(shù)m，模m同余關(guān)系是等價(jià)關(guān)系。 若x和y有模m同余關(guān)系，一般記作xy（mod m）44（x-y）/ m=n I，（y-z）

25、/ m=k I，于是有 （ x - z）/ m=n +kI，因此， x z（mod m）綜上所述，模m同余關(guān)系是等價(jià)關(guān)系。45定義（等價(jià)類）設(shè)R是集合A上的等價(jià)關(guān)系。對于每個(gè)xA，A中與x有關(guān)系R的元素的集合稱為x關(guān)于R的等價(jià)類，簡稱為x的等價(jià)類，記作xR， 即 xRyyAxRy。對于上例中給出的集合A1,2,3,4,5,6,7上的關(guān)系R，A中各元素的等價(jià)類如下：1R4 R 7 R 1,4,72 R 5 R 2,53 R 6 R 3,6定理 （等價(jià)類的性質(zhì)）設(shè)R是非空集合A上的關(guān)系，則以下結(jié)論成立：46(1) 對于每個(gè)xA，xx R , 且x R是A的非空子集。(2) x R y R當(dāng)且僅當(dāng)x

26、 R y 。(3) 若x,yA且x y，則x R y R 。(4) x R A, 其中 x R表示所有等價(jià)類的并集。證明：（1）因?yàn)镽是自反的，對于 x A，都有x R x，因此 x x R ， x R 。對于 y x R ，由等價(jià)類的定義，可得y A，因此x R A， x R是A的非空子集。（2）設(shè)x R y R ， y y R，則y x R ，由x R的定義，可得x R y。設(shè)x R y,對于 z y R ,當(dāng)且僅當(dāng) y R z,因R是傳遞的，47所以 xRz，zx R ，故y R x R 。因R是對稱的，所以有yRx，同理可證， x R y R ， 因此， x R =y R（3）設(shè)x R

27、 y R 。則 z x R ， z y R ，即xRz， yRz，因R是對稱的，所以有zRy，由于R是傳遞的，所以有xRy，這與x y矛盾。（4）由（1）的證明可知，對于 x A，x R A，因此 x R A。 對于z A，有z z R ， z R x R ，故有z x R ，因此， A x R ，所以 x R A。48定義 設(shè)S是非空集合,是由S的子集組成的集合,即 (S),若滿足下三個(gè)條件,則稱為S上的一個(gè)劃分。(1) 對于每個(gè)A，A；(2) 對于任意A,B，若AB，則A B；(3) S。定義 設(shè)R是集合A上的等價(jià)關(guān)系，所有等價(jià)類組成的集合稱為A關(guān)于R的商集，記作A/R，即A/RxR x

28、A例：上例中集合A1,2,3,4,5,6,7關(guān)于其等價(jià)關(guān)系R的商集A/R1,4,7,2,5,3,649例： 設(shè)Sa,b,c，給定下列S的子集的集合：Aa,b,cBa,b,cCa,b,cDa,b,b,cEa,c問：這些集合中哪些是S上的劃分？把中的元素稱為劃分塊，劃分中劃分塊個(gè)數(shù)稱為秩有有窮個(gè)劃分塊的劃分稱為有窮劃分，否則稱為無窮劃分50定理 非空集合A上的等價(jià)關(guān)系R決定了A上的一個(gè)劃分，這個(gè)劃分就是商集A/R 。證明：根據(jù)商集的定義A/RxRA、等價(jià)類的性質(zhì)定理和劃分的定義，即得商集A/R是A上的一個(gè)劃分。定理 設(shè)是非空集合A上的一個(gè)劃分，若 xRy當(dāng)且僅當(dāng) x和y在的同一個(gè)劃分塊中，則R必是 A上的等價(jià)關(guān)系。 稱R為由確定的等價(jià)關(guān)系。證明：只要證明R有自反性、對稱性、傳遞性。（1）自反性，由劃分的定義可知，對于任意xA，51