離散數(shù)學第七章二元關(guān)系ppt課件

1、1,主要內(nèi)容 有序?qū)εc笛卡兒積 二元關(guān)系的定義與表示法 關(guān)系的運算 關(guān)系的性質(zhì) 關(guān)系的閉包 等價關(guān)系與劃分 偏序關(guān)系,第七章 二元關(guān)系,2,7.1 有序?qū)εc笛卡兒積,定義7.1 由兩個元素 x 和 y，按照一定的順序組成的二元組 稱為有序?qū)?，記? 有序?qū)π再|(zhì): (1) 有序性 （當xy時） (2) 與相等的充分必要條件是 = x=uy=v,3,笛卡兒積,定義7.2 設(shè)A,B為集合，A與B的笛卡兒積記作AB，且 AB = | xAyB,例1 A=1,2,3, B=a,b,c AB =, BA =, A=, B= P(A)A = , P(A)B =,4,笛卡兒積的性質(zhì),1) 不適合交換律 AB

2、BA (AB, A, B) (2) 不適合結(jié)合律 (AB)C A(BC) (A, B, C) (3) 對于并或交運算滿足分配律 A(BC) = (AB)(AC) (BC)A = (BA)(CA) A(BC) = (AB)(AC) (BC)A = (BA)(CA) (4) 若 A 或 B 中有一個為空集，則 AB 就是空集. A = B = (5) 若 |A| = m, |B| = n, 則 |AB| = mn,5,性質(zhì)證明,證明 A(BC) = (AB)(AC,證 任取 A(BC) xAyBC xA(yByC) (xAyB)(xAyC) ABAC (AB)(AC) 所以有A(BC) = (AB

3、)(AC,6,實例,例2 (1) 證明A=B,C=D AC=BD (2) AC = BD是否推出 A=B,C=D? 為什么,解 (1) 任取 AC xAyC xByD BD (2) 不一定.反例如下： A=1，B=2, C = D = , 則AC = BD但是A B,7,7.2 二元關(guān)系,定義7.3 如果一個集合滿足以下條件之一： (1) 集合非空, 且它的元素都是有序?qū)?(2) 集合是空集 則稱該集合為一個二元關(guān)系, 簡稱為關(guān)系，記作R. 如果R, 可記作xRy；如果R, 則記作x y 實例：R=, S=,a,b. R是二元關(guān)系, 當a, b不是有序?qū)r，S不是二元關(guān)系 根據(jù)上面的記法，可以

4、寫1R2, aRb, a c等,8,A到B的關(guān)系與A上的關(guān)系,定義7.4 設(shè)A,B為集合, AB的任何子集所定義的二元關(guān)系叫做從A 到B的二元關(guān)系, 當A=B時則叫做A上的二元關(guān)系,例3 A=0,1, B=1,2,3, 那么 R1=, R2=AB, R3=, R4= R1, R2, R3, R4是從 A 到 B 的二元關(guān)系, R3 和 R4 也是A上的二元關(guān)系. 計數(shù): |A|=n, |AA|=n2, AA的子集有個. 所以 A上有 個不同的二元關(guān)系. 例如 |A| = 3, 則 A上有=512個不同的二元關(guān)系,9,A上重要關(guān)系的實例,定義7.5 設(shè) A 為集合, (1) 是A上的關(guān)系，稱為空

5、關(guān)系 (2) 全域關(guān)系 EA = | xAyA = AA 恒等關(guān)系 IA = | xA 小于等于關(guān)系 LA = | x,yAxy, A為實數(shù)子集 整除關(guān)系 DB = | x,yBx整除y, A為非0整數(shù)子集 包含關(guān)系 R = | x,yAxy, A是集合族,10,實例,例如, A=1, 2, 則 EA = , IA = , 例如 A = 1, 2, 3, B=a, b, 則 LA = , DA = , 例如 A = P(B) = ,a,b,a,b, 則 A上的包含關(guān)系是 R = , , 類似的還可以定義： 大于等于關(guān)系, 小于關(guān)系, 大于關(guān)系, 真包含關(guān)系等,11,關(guān)系的表示,1. 關(guān)系矩陣

6、若A=x1, x2, , xm，B=y1, y2, , yn，R是從A到B的 關(guān)系，R的關(guān)系矩陣是布爾矩陣MR = rij mn, 其中 rij = 1 R. 2. 關(guān)系圖 若A= x1, x2, , xm，R是從A上的關(guān)系，R的關(guān)系圖是GR=, 其中A為結(jié)點集，R為邊集. 如果屬于 關(guān)系R，在圖中就有一條從 xi 到 xj 的有向邊. 注意： 關(guān)系矩陣適合表示從A到B的關(guān)系或A上的關(guān)系（A,B為有窮集） 關(guān)系圖適合表示有窮集A上的關(guān)系,12,實例,例4 A=1,2,3,4, R=, R的關(guān)系矩陣MR和關(guān)系圖GR如下,13,7.3 關(guān)系的運算,關(guān)系的基本運算 定義7.6 關(guān)系的定義域、值域與域

7、分別定義為 domR = x | y (R) ranR = y | x (R) fldR = domR ranR,例5 R=, 則 domR=1, 2, 4 ranR=2, 3, 4 fldR=1, 2, 3, 4,14,關(guān)系運算(逆與合成,定義7.7 關(guān)系的逆運算 R1 = | R 定義7.8 關(guān)系的合成運算 RS = | y (R S),例6 R = , , , S = , , , , R1 = , , , RS = , , SR = , , ,15,合成的圖示法,利用圖示（不是關(guān)系圖）方法求合成 RS =, , SR =, , ,16,關(guān)系運算(限制與像,定義7.9 設(shè)R為二元關(guān)系, A

8、是集合 (1) R在A上的限制記作 RA, 其中 RA = | xRyxA (2) A在R下的像記作RA, 其中 RA=ran(RA) 說明： R在A上的限制 RA是 R 的子關(guān)系，即 RA R A在R下的像 RA 是 ranR 的子集，即 RA ranR,17,實例,例7 設(shè)R=, 則 R1 = , R = R2,3 = , R1 = 2,3 R = R3 = 2,18,關(guān)系運算的性質(zhì),定理7.1 設(shè)F是任意的關(guān)系, 則 (1) (F1)1=F (2) domF1= ranF, ranF1= domF,證 (1) 任取, 由逆的定義有 (F1)1 F1 F. 所以有(F1)1=F,2) 任取

9、x, xdomF1 y(F1) y(F) xranF 所以有 domF1=ranF. 同理可證 ranF1=domF,19,定理7.2 設(shè)F, G, H是任意的關(guān)系, 則 (1) (FG)H = F(GH) (2) (FG)1 = G1F1,關(guān)系運算的性質(zhì),證 (1) 任取, (FG)H t (FGH) t ( s (FG)H) t s (FGH) s (Ft (GH) s (FGH) F(GH) 所以 (FG)H = F(GH,20,證明,2) 任取, (FG)1 FG t (FG) t (G1F1) G1 F1所以 (F G)1 = G1 F1,21,關(guān)系運算的性質(zhì),定理7.3 設(shè)R為A上

10、的關(guān)系, 則 RIA= IAR=R,證任取 RIA t (RIA) t (Rt=yyA) R,22,關(guān)系運算的性質(zhì),定理7.4 (1) F(GH) = FGFH (2) (GH)F = GFHF (3) F(GH) FGFH (4) (GH)F GFHF,只證 (3) 任取, F(GH) t (FGH) t (FGH) t (FG)(FH) t (FG)t (FH) FGFH FGFH 所以有 F(GH)=FGFH,23,推廣,定理7.4 的結(jié)論可以推廣到有限多個關(guān)系 R(R1R2Rn) = RR1RR2RRn (R1R2Rn)R = R1RR2RRnR R(R1R2 Rn) RR1RR2 R

11、Rn (R1R2 Rn)R R1RR2R RnR,24,關(guān)系運算的性質(zhì),定理7.5 設(shè)F 為關(guān)系, A, B為集合, 則 (1) F (AB) = F AF B (2) F AB = F AF B (3) F (AB) = F AF B (4) F AB F AF B,25,證明,證 只證 (1) 和 (4). (1) 任取 F (AB) FxAB F(xAxB) (FxA)(FxB) F AF B F AF B 所以有F (AB) = F AF B,26,證明,4) 任取y, yF AB x (FxAB) x (FxAxB) x (FxA)(FxB) x (FxA)x (FxB) yF Ay

12、F B yF AF B 所以有F AB=F AF B,27,關(guān)系的冪運算,定義7.10 設(shè) R 為 A 上的關(guān)系, n為自然數(shù), 則 R 的 n 次冪定義為： (1) R0 = | xA = IA (2) Rn+1 = RnR 注意： 對于A上的任何關(guān)系 R1 和 R2 都有 R10 = R20 = IA 對于A上的任何關(guān)系 R 都有 R1 = R,28,例 8 設(shè)A = a,b,c,d, R = , 求R的各次冪, 分別用矩陣和關(guān)系圖表示,解 R 與 R2的關(guān)系矩陣分別是,冪的求法,29,R3和R4的矩陣是： 因此M4=M2, 即R4=R2. 因此可以得到 R2=R4=R6=， R3=R5=

13、R7= R0的關(guān)系矩陣是,冪的求法,30,關(guān)系圖,R0, R1, R2, R3,的關(guān)系圖如下圖所示,R0,R1,R2=R4,R3=R5,31,冪運算的性質(zhì),定理7.6 設(shè) A 為 n 元集, R 是A上的關(guān)系, 則存在自然數(shù) s 和 t, 使得 Rs = Rt,證 R 為A上的關(guān)系, 由于|A|=n, A上的不同關(guān)系只有 個. 列出 R 的各次冪 R0, R1, R2, , , , 必存在自然數(shù) s 和 t 使得 Rs = Rt,32,定理7.7 設(shè) R 是 A上的關(guān)系, m, nN, 則 (1) RmRn = Rm+n (2) (Rm)n = Rmn,冪運算的性質(zhì),證 用歸納法 (1) 對于

14、任意給定的mN, 施歸納于n. 若n=0, 則有 RmR0 = RmIA = Rm = Rm+0 假設(shè) RmRn = Rm+n, 則有 RmRn+1 = Rm (Rn R) = (Rm Rn)R = Rm+n+1 , 所以對一切m,nN 有 RmRn = Rm+n,33,證明,2) 對于任意給定的mN, 施歸納于n. 若n=0, 則有 (Rm)0 = IA = R0 = Rm0 假設(shè) (Rm)n = Rmn, 則有 (Rm)n+1 = (Rm)nRm = (Rmn)Rn = Rmn+m = Rm(n+1) 所以對一切m,nN 有 (Rm)n = Rmn,34,定理7.8 設(shè)R 是A上的關(guān)系,

15、若存在自然數(shù) s, t (st) 使得 Rs=Rt, 則 (1) 對任何 kN有 Rs+k = Rt+k (2) 對任何 k, iN有 Rs+kp+i = Rs+i, 其中 p = ts (3) 令S = R0,R1,Rt1, 則對于任意的 qN 有RqS,冪運算的性質(zhì),證 (1) Rs+k = RsRk = Rt Rk = Rt+k (2) 對k歸納. 若k=0, 則有Rs+0p+i = Rs+i 假設(shè) Rs+kp+i = Rs+i, 其中p = ts, 則 Rs+(k+1)p+i = Rs+kp+i+p = Rs+kp+iRp = Rs+iRp = Rs+p+i = Rs+ts+i = R

16、t+i = Rs+i 由歸納法命題得證,35,證明,3) 任取 qN, 若 q t, 顯然有 RqS, 若q t, 則存在自然數(shù) k 和 i 使得 q = s+kp+i, 其中0ip1. 于是 Rq = Rs+kp+i = Rs+i 而 s+i s+p1 = s+ts1 = t1 從而證明了 RqS,36,7.4 關(guān)系的性質(zhì),定義7.11 設(shè) R 為A上的關(guān)系, (1) 若 x(xAR), 則稱 R 在 A 上是自反的. (2) 若 x(xAR), 則稱 R 在 A 上是反自反的,實例： 自反：全域關(guān)系EA, 恒等關(guān)系IA, 小于等于關(guān)系LA, 整除關(guān)系DA 反自反：實數(shù)集上的小于關(guān)系、冪集上

17、的真包含關(guān)系. A=1,2,3, R1, R2, R3是A上的關(guān)系, 其中 R1, R2, R3 R2 自反 ，R3 反自反，R1既不是自反的也不是反自反的,37,對稱性與反對稱性,定義7.12 設(shè) R 為 A上的關(guān)系, (1) 若xy( x,yARR), 則稱 R 為 A上對 稱的關(guān)系. (2) 若xy( x,yARRx=y), 則稱 R 為 A上的反對稱關(guān)系,實例：對稱關(guān)系：A上的全域關(guān)系EA, 恒等關(guān)系IA和空關(guān)系 反對稱關(guān)系：恒等關(guān)系IA和空關(guān)系也是A上的反對稱關(guān)系. 設(shè)A1,2,3, R1, R2, R3和R4都是A上的關(guān)系, 其中 R1,，R2, R3,，R4, R1：對稱和反對稱

18、； R2：只有對稱；R3：只有反對稱； R4：不對稱、不反對稱,38,傳遞性,定義7.13 設(shè)R為A上的關(guān)系, 若 xyz(x,y,zARRR), 則稱 R 是A上的傳遞關(guān)系,實例： A上的全域關(guān)系 EA,恒等關(guān)系 IA和空關(guān)系 ，小于等 于和小于關(guān)系，整除關(guān)系，包含與真包含關(guān)系 設(shè) A1,2,3, R1, R2, R3是A上的關(guān)系, 其中 R1, R2, R3 R1和R3是A上的傳遞關(guān)系, R2不是A上的傳遞關(guān)系,39,關(guān)系性質(zhì)成立的充要條件,定理7.9 設(shè)R為A上的關(guān)系, 則 (1) R 在A上自反當且僅當 IA R (2) R 在A上反自反當且僅當 RIA = (3) R 在A上對稱當且

19、僅當 R=R1 (4) R 在A上反對稱當且僅當 RR1 IA (5) R 在A上傳遞當且僅當 RR R,40,證明,證明 只證(1)、(3)、(4)、(5) (1) 必要性 任取, 由于R 在A上自反必有 IA x,yAx=y R 從而證明了IAR 充分性. 任取x, 有 xA IA R 因此 R 在A上是自反的,41,證明,3) 必要性. 任取, R R R1 所以 R = R1 充分性. 任取, 由R = R1得R R1 R 所以R在A上是對稱的,42,證明,4) 必要性. 任取, 有 RR1 RR1 RR x=y x,yA IA 這就證明了RR1IA 充分性. 任取, RR RR1 R

20、R1 IA x=y 從而證明了R在A上是反對稱的,43,證明,5) 必要性. 任取有 RR t (RR) R 所以 RR R 充分性. 任取,R, 則 RR RR R 所以 R 在 A上是傳遞的,44,關(guān)系性質(zhì)的三種等價條件,45,關(guān)系的性質(zhì)和運算之間的聯(lián)系,46,7.5 關(guān)系的閉包,主要內(nèi)容 閉包定義 閉包的構(gòu)造方法 集合表示 矩陣表示 圖表示 閉包的性質(zhì),47,閉包定義,定義7.14 設(shè)R是非空集合A上的關(guān)系, R的自反(對稱或傳遞)閉 包是A上的關(guān)系R, 使得R滿足以下條件： (1) R是自反的(對稱的或傳遞的) (2) RR (3) 對A上任何包含R的自反(對稱或傳遞)關(guān)系R 有RR

21、R的自反閉包記作r(R), 對稱閉包記作s(R), 傳遞閉包記作t(R,定理7.10 設(shè)R為A上的關(guān)系, 則有 (1) r(R)=RR0 (2) s(R)=RR1 (3) t(R)=RR2R3 說明：對有窮集A(|A|=n)上的關(guān)系, (3)中的并最多不超過Rn,48,證明,證 只證(1)和(3). (1) 由IA=R0RR0 知 RR0是自反的, 且滿足RRR0 設(shè)R 是A上包含R的自反關(guān)系, 則有RR 和IA R . 從而有 RR0R. RR0滿足閉包定義, 所以r(R)=RR0,1) 先證 RR2 t(R)成立. 用歸納法證明對任意正整數(shù)n 有Rn t(R). n=1時有R1=R t(R

22、). 假設(shè)Rnt(R)成立, 那么對任意的 Rn+1=RnR t ( RnR) t (t(R)t(R) t(R) 這就證明了Rn+1t(R). 由歸納法命題得證.,49,證明,再證 t(R) RR2成立, 為此只須證明RR2傳遞. 任取, 則 RR2RR2 t (Rt)s(Rs) t s (RtRs ) t s (Rt+s ) RR2 從而證明了RR2是傳遞的,50,閉包的矩陣表示和圖表示,設(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 是 轉(zhuǎn)置矩陣，相加時使用邏輯加,設(shè)關(guān)

23、系R, r(R), s(R), t(R)的關(guān)系圖分別記為G, Gr, Gs, Gt, 則Gr , Gs , Gt 的頂點集與G 的頂點集相等. 除了G 的邊以外, 以下述 方法添加新的邊： (1) 考察G 的每個頂點, 若沒環(huán)就加一個環(huán)，得到Gr (2) 考察G 的每條邊, 若有一條 xi 到 xj 的單向邊, ij, 則在G 中加一條 xj 到 xi 的反向邊, 得到Gs (3) 考察G 的每個頂點 xi, 找 xi 可達的所有頂點 xj (允許i=j )， 如果沒有從 xi 到 xj 的邊, 就加上這條邊, 得到圖Gt,51,實例,例9 設(shè)A=a,b,c,d, R=, R和r(R), s(

24、R), t(R)的關(guān)系圖如下圖所示,52,閉包的性質(zhì),定理7.11 設(shè)R是非空集合A上的關(guān)系, 則 (1) R是自反的當且僅當 r(R)=R. (2) R是對稱的當且僅當 s(R)=R. (3) R是傳遞的當且僅當 t(R)=R,定理7.12 設(shè)R1和R2是非空集合A上的關(guān)系, 且 R1R2, 則 (1) r(R1) r(R2) (2) s(R1) s(R2) (3) t(R1) t(R2,證明 略,53,定理7.13 設(shè)R是非空集合A上的關(guān)系, (1) 若R是自反的, 則 s(R) 與 t(R) 也是自反的 (2) 若R是對稱的, 則 r(R) 與 t(R) 也是對稱的 (3) 若R是傳遞的

25、, 則 r(R) 是傳遞的. 說明：如果需要進行多個閉包運算，比如求R的自反、對 稱、傳遞的閉包 tsr(R)，運算順序如下： tsr(R) = rts(R) = trs(R,閉包的性質(zhì),證明 略,54,7.6 等價關(guān)系與劃分,主要內(nèi)容 等價關(guān)系的定義與實例 等價類及其性質(zhì) 商集與集合的劃分 等價關(guān)系與劃分的一一對應,55,等價關(guān)系的定義與實例,定義7.15 設(shè)R為非空集合上的關(guān)系. 如果R是自反的、對稱的和 傳遞的, 則稱R為A上的等價關(guān)系. 設(shè) R 是一個等價關(guān)系, 若 R, 稱 x等價于y, 記做xy,實例 設(shè) A=1,2,8, 如下定義A上的關(guān)系R： R=| x,yAx y(mod 3

26、) 其中x y(mod 3)叫做 x與 y 模3相等, 即x除以3的余數(shù)與y除以 3的余數(shù)相等. 不難驗證 R 為A上的等價關(guān)系, 因為 (1) xA, 有 x x (mod 3) (2) x,yA, 若x y(mod 3), 則有y x(mod 3) (3) x,y,zA, 若x y(mod 3), y z(mod 3), 則有x z(mod 3,56,模 3 等價關(guān)系的關(guān)系圖,等價關(guān)系的實例,57,等價類定義,定義7.16 設(shè)R為非空集合A上的等價關(guān)系, xA，令 xR = y | yAxRy 稱xR 為x關(guān)于R的等價類, 簡稱為x的等價類, 簡記為x或 實例 A=1, 2, , 8上模3

27、等價關(guān)系的等價類： 1 = 4 = 7 = 1, 4, 7 2 = 5 = 8 = 2, 5, 8 3 = 6 = 3, 6,58,等價類的性質(zhì),定理7.14 設(shè)R是非空集合A上的等價關(guān)系, 則 (1) xA, x是A的非空子集 (2) x,yA, 如果 xRy, 則 x = y (3) x,yA, 如果 x y, 則 x與y不交 (4) x | xA=A,證 (1) 由定義, xA有xA. 又xx, 即x非空. (2) 任取 z, 則有 zx R R RR R R 從而證明了zy. 綜上所述必有 xy. 同理可證 yx. 這就得到了x = y,59,證明,3) 假設(shè) xy, 則存在 zxy,

28、 從而有zxzy, 即RR成立. 根據(jù)R的對稱性和傳遞性必有 R, 與 x y矛盾,4) 先證x | xA A. 任取y, yx | xA x(xAyx) yxx A yA 從而有x | xA A 再證A x | xA. 任取y, yA yyyA yx | xA 從而有x | xA A成立. 綜上所述得x | xA = A,60,商集與劃分,定義7.18 設(shè)A為非空集合, 若A的子集族( P(A)滿足: (1) (2) xy(x,yxyxy=) (3) = A 則稱是A的一個劃分, 稱中的元素為A的劃分塊,61,劃分實例,例10 設(shè) A a, b, c, d , 給定 1, 2, 3, 4,

29、5, 6如下： 1= a, b, c , d 2= a, b, c , d 3= a , a, b, c, d 4= a, b, c 5=, a, b , c, d 6= a, a , b, c, d 則 1和 2是A的劃分, 其他都不是A的劃分,62,例11 給出 A1,2,3上所有的等價關(guān)系,實例,1對應 EA, 5 對應 IA, 2, 3 和 4分別對應 R2, R3和 R4. R2=,IA R3=,IA R4=,IA,解 先做出A的劃分, 從左到右分別記作 1, 2, 3, 4, 5,63,例12 給出 A1,2,3,4上所有的等價關(guān)系,實例,1對應 EA, 5 對應 IA, 2, 3

30、 和 4分別對應 R2, R3和 R4. R2=,IA R3=,IA R4=,IA,解 先做出A的劃分, 從左到右分別記作 1, 2, 3, 4, 5,64,例12 給出 A1,2,3,4上所有的等價關(guān)系,實例,1對應 EA ,2, 3 , 4和5分別對應 R2, R3，R4和R5 R2=,IAR3=, ,IA R4=, ,IA R5=, ,IA,解 先做出A的劃分, 可分別記作 1 15,1,65,例12 給出 A1,2,3,4上所有的等價關(guān)系,實例(續(xù),6, 7 , 8和9分別對應 R6, R7,R8和R9 R6=,IAR7=, ,IA R8=, ,IA R9=IA,解 先做出A的劃分,

31、可分別記作 1 9,8,66,7.7 偏序關(guān)系,主要內(nèi)容 偏序關(guān)系 偏序關(guān)系的定義 偏序關(guān)系的實例 偏序集與哈斯圖 偏序集中的特殊元素及其性質(zhì) 極大元、極小元、最大元、最小元 上界、下界、最小上界、最大下界,67,定義與實例,定義7.19 偏序關(guān)系：非空集合A上的自反、反對稱和傳遞的關(guān)系， 記作. 設(shè)為偏序關(guān)系, 如果 , 則記作 x y, 讀作 x“小于或等于”y. 實例 集合A上的恒等關(guān)系 IA是 A上的偏序關(guān)系. 小于或等于關(guān)系, 整除關(guān)系和包含關(guān)系也是相應集合上的偏 序關(guān)系,68,相關(guān)概念,定義7.20 設(shè) R 為非空集合A上的偏序關(guān)系, (1) x, yA, x與y可比 x yy x

32、 (2) 任取元素 x 和 y, 可能有下述幾種情況發(fā)生： x y (或 y x), xy, x與y不是可比的,定義7.21 R 為非空集合A上的偏序關(guān)系, (1) x,yA, x與y都是可比的，則稱R為全序（或線序） 實例：數(shù)集上的小于或等于關(guān)系是全序關(guān)系,整除關(guān)系不是正 整數(shù)集合上的全序關(guān)系,定義7.22 x,yA, 如果 xy 且不存在 zA 使得 xzy, 則稱 y 覆蓋x. 例如1,2,4,6集合上整除關(guān)系, 2覆蓋1, 4和6覆蓋2, 4不覆蓋1,69,相關(guān)概念,定義7.22 x,yA, 如果 xy 且不存在 zA 使得 xzy, 則稱 y 覆蓋x,蓋住關(guān)系: CovA=| xA

33、yA y 覆蓋x,例如1,2,4,6集合上整除關(guān)系, 2覆蓋1, 4和6覆蓋2, 4不覆蓋1,上例的蓋住關(guān)系為: CovA,70,例1 求關(guān)系圖和哈斯圖,設(shè)A=2,3,6,12,24,36，“”是A上的整除關(guān)系R，寫出蓋住關(guān)系，并畫出其一般的關(guān)系圖和哈斯圖。 解:由題意可得整除關(guān)系R如下： R=, , ,。 從而得出該偏序集的一般關(guān)系圖如下,71,例1 求關(guān)系圖和哈斯圖(續(xù),72,偏序集與哈斯圖,定義7.23 集合A和A上的偏序關(guān)系一起叫做偏序集, 記作 . 實例: ,哈斯圖: 利用偏序關(guān)系的自反、反對稱、傳遞性進行簡化的 關(guān)系圖 特點： (1) 每個結(jié)點沒有環(huán) (2) 兩個連通的結(jié)點之間的序

34、關(guān)系通過結(jié)點位置的高低表 示，位置低的元素的順序在前 (3) 具有覆蓋關(guān)系的兩個結(jié)點之間連邊,73,實例,例12 偏序集和的 哈斯圖,74,例13 已知偏序集的哈斯圖如下圖所示, 試求出集合A 和關(guān)系R的表達式,解 A= a, b, c, d, e, f, g, h R=,IA,實例,75,偏序集中的特殊元素,定義7.24 設(shè)為偏序集, BA, yB (1) 若x(xByx)成立, 則稱 y 為B的最小元 (2) 若x(xBxy)成立, 則稱 y 為B的最大元 (3) 若x(xBxyx=y)成立, 則稱 y 為B的極小元 (4) 若x(xByxx=y)成立, 則稱 y 為B的極大元,性質(zhì)： (

35、1) 對于有窮集，極小元和極大元一定存在，可能存在多個. (2) 最小元和最大元不一定存在，如果存在一定惟一. (3) 最小元一定是極小元；最大元一定是極大元. (4) 孤立結(jié)點既是極小元，也是極大元,76,定義7.25 設(shè)為偏序集, BA, yA (1) 若x(xBxy)成立, 則稱y為B的上界 (2) 若x(xByx)成立, 則稱y為B的下界 (3) 令Cy| y為B的上界, C的最小元為B的最小上界或上確界 (4) 令Dy| y為B的下界, D的最大元為B的最大下界或下確界,偏序集中的特殊元素,性質(zhì)： (1) 下界、上界、下確界、上確界不一定存在 (2) 下界、上界存在不一定惟一 (3)

36、 下確界、上確界如果存在，則惟一 (4) 集合的最小元是其下確界，最大元是其上確界；反之不對,77,實例,例14 設(shè)偏序集，求A的極小元、最小元、極大元、最 大元，設(shè)B b,c,d , 求B的下界、上界、下確界、上確界,解 極小元：a, b, c, g； 極大元：a, f, h； 沒有最小元與最大元. B的下界和最大下界都不存在； 上界有 d 和 f, 最小上界為 d,78,實例,例15 設(shè)X為集合, AP(X)X, 且A. 若|X|=n, n2. 問： (1) 偏序集 是否存在最大元？ (2) 偏序集 是否存在最小元？ (3) 偏序集 中極大元和極小元的一般形式是什么？ 并說明理由,解 (1

37、) 不存在最小元和最大元, 因為n2. (2) 的極小元就是 X 的所有單元集, 即x, xX. (3) 的極大元恰好比 X 少一個元素, 即Xx, xX,79,第七章 習題課,主要內(nèi)容 有序?qū)εc笛卡兒積的定義與性質(zhì) 二元關(guān)系、從A到B的關(guān)系、A上的關(guān)系 關(guān)系的表示法：關(guān)系表達式、關(guān)系矩陣、關(guān)系圖 關(guān)系的運算：定義域、值域、域、逆、合成、限制、像、冪 關(guān)系運算的性質(zhì): A上關(guān)系的自反、反自反、對稱、反對稱、傳遞的性質(zhì) A上關(guān)系的自反、對稱、傳遞閉包 A上的等價關(guān)系、等價類、商集與A的劃分 A上的偏序關(guān)系與偏序集,80,基本要求,熟練掌握關(guān)系的三種表示法 能夠判定關(guān)系的性質(zhì)（等價關(guān)系或偏序關(guān)系）

38、 掌握含有關(guān)系運算的集合等式 掌握等價關(guān)系、等價類、商集、劃分、哈斯圖、偏序集等概念 計算AB, dom R, ranR, fldR, R1, RS , Rn , r(R), s(R), t(R) 求等價類和商集A/R 給定A的劃分，求出 所對應的等價關(guān)系 求偏序集中的極大元、極小元、最大元、最小元、上界、下界、上確界、下確界 掌握基本的證明方法 證明涉及關(guān)系運算的集合等式 證明關(guān)系的性質(zhì)、證明關(guān)系是等價關(guān)系或偏序關(guān)系,81,練習1,1設(shè)A = 1, 2, 3, R = | x, yA且x+2y 6 ， S = , , 求: (1) R的集合表達式 (2) R1 (3) dom R, ran R, fld R (4) RS, R3 (5) r(R), s(R), t(R,82,解答,1) R = , , , , (2) R1 = , , , , (3) domR = 1, 2, 3, ranR = 1,2, fldR = 1, 2, 3 (4) RS = , , , , , R3 = , ,