7離散數(shù)學(xué)第7章課件ppt_高等教育出版社_屈婉玲_耿素云_張立昂主編

1、1主要內(nèi)容主要內(nèi)容l 有序?qū)εc笛卡兒積有序?qū)εc笛卡兒積l 二元關(guān)系的定義與表示法二元關(guān)系的定義與表示法l 關(guān)系的運(yùn)算關(guān)系的運(yùn)算l 關(guān)系的性質(zhì)關(guān)系的性質(zhì)l 關(guān)系的閉包關(guān)系的閉包l 等價關(guān)系與劃分等價關(guān)系與劃分l 偏序關(guān)系偏序關(guān)系第七章第七章 二元關(guān)系二元關(guān)系27.1 有序?qū)εc笛卡兒積有序?qū)εc笛卡兒積定義定義7.1 由兩個元素由兩個元素 x 和和 y，按照一定的順序組成的二元組，按照一定的順序組成的二元組稱為稱為有序?qū)τ行驅(qū)?，記作，記?有序?qū)π再|(zhì)有序?qū)π再|(zhì): (1) 有序性有序性 （當(dāng)（當(dāng)x y時）時） (2) 與與相等的充分必要條件是相等的充分必要條件是 = x=u y=v. 3笛卡兒積笛卡兒

2、積定義定義7.2 設(shè)設(shè)A,B為集合，為集合，A與與B的的笛卡兒積笛卡兒積記作記作A B，且，且 A B = | x A y B.例例1 A=1,2,3, B=a,b,c A B =, B A =, A=, B= P(A) A = , P(A) B = 4笛卡兒積的性質(zhì)笛卡兒積的性質(zhì)(1) 不適合交換律不適合交換律 A B B A (A B, A, B)(2) 不適合結(jié)合律不適合結(jié)合律 (A B) C A (B C) (A, B, C)(3) 對于并或交運(yùn)算滿足分配律對于并或交運(yùn)算滿足分配律 A (B C) = (A B) (A C) (B C) A = (B A) (C A) A (B C)

3、= (A B) (A C) (B C) A = (B A) (C A) (4) 若若 A 或或 B 中有一個為空集，則中有一個為空集，則 A B 就是空集就是空集. A = B = (5) 若若 |A| = m, |B| = n, 則則 |A B| = mn 5性質(zhì)證明性質(zhì)證明證明證明 A (B C) = (A B) (A C)證證 任取任取 A(BC) xAyBC xA(yByC) (xAyB)(xAyC) ABAC (AB)(AC)所以有所以有A(BC) = (AB)(AC).6實(shí)例實(shí)例例例2 (1) 證明證明A=B,C=D A C=B D (2) A C = B D是否推出是否推出 A=

4、B,C=D? 為什么？為什么？解解 (1) 任取任取 A C x A y C x B y D B D(2) 不一定不一定.反例如下：反例如下： A=1，B=2, C = D = , 則則A C = B D但是但是A B.77.2 二元關(guān)系二元關(guān)系定義定義7.3 如果一個集合滿足以下條件之一：如果一個集合滿足以下條件之一：(1) 集合非空集合非空, 且它的元素都是有序?qū)η宜脑囟际怯行驅(qū)?2) 集合是空集集合是空集則稱該集合為一個則稱該集合為一個二元關(guān)系二元關(guān)系, 簡稱為關(guān)系，記作簡稱為關(guān)系，記作R.如果如果R, 可記作可記作xRy；如果；如果 R, 則記作則記作x y實(shí)例：實(shí)例：R=, S=

5、,a,b. R是二元關(guān)系是二元關(guān)系, 當(dāng)當(dāng)a, b不是有序?qū)r，不是有序?qū)r，S不是二元關(guān)系不是二元關(guān)系根據(jù)上面的記法，可以寫根據(jù)上面的記法，可以寫1R2, aRb, a c等等. 8A到到B的關(guān)系與的關(guān)系與A上的關(guān)系上的關(guān)系定義定義7.4設(shè)設(shè)A,B為集合為集合, AB的任何子集所定義的二元關(guān)系叫做的任何子集所定義的二元關(guān)系叫做從從A到到B的二元關(guān)系的二元關(guān)系, 當(dāng)當(dāng)A=B時則叫做時則叫做A上的二元關(guān)系上的二元關(guān)系.22n例例3 A=0,1, B=1,2,3, 那么那么 R1=, R2=AB, R3=, R4=R1, R2, R3, R4是從是從 A 到到 B 的二元關(guān)系的二元關(guān)系, R3 和

6、和 R4 也是也是A上的二元關(guān)系上的二元關(guān)系. 計數(shù)計數(shù): |A|=n, |AA|=n2, AA的子集有個的子集有個. 所以所以 A上有上有個不同的二元關(guān)系個不同的二元關(guān)系. 例如例如 |A| = 3, 則則 A上有上有=512個不同的二元關(guān)系個不同的二元關(guān)系. 9A上重要關(guān)系的實(shí)例上重要關(guān)系的實(shí)例定義定義7.5 設(shè)設(shè) A 為集合為集合, (1) 是是A上的關(guān)系，稱為上的關(guān)系，稱為空關(guān)系空關(guān)系(2) 全域關(guān)系全域關(guān)系 EA = | xAyA = AA 恒等關(guān)系恒等關(guān)系 IA = | xA 小于等于關(guān)系小于等于關(guān)系 LA = | x,yAxy, A為實(shí)數(shù)子集為實(shí)數(shù)子集 整除關(guān)系整除關(guān)系 DB =

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

8、m，B=y1, y2, , yn，R是從是從A到到B的的 關(guān)系，關(guān)系，R的關(guān)系矩陣是布爾矩陣的關(guān)系矩陣是布爾矩陣MR = rij m n, 其中其中 rij = 1 R. 2. 關(guān)系圖關(guān)系圖 若若A= x1, x2, , xm，R是從是從A上的關(guān)系，上的關(guān)系，R的關(guān)系圖是的關(guān)系圖是GR=, 其中其中A為結(jié)點(diǎn)集，為結(jié)點(diǎn)集，R為邊集為邊集. 如果如果屬于屬于 關(guān)系關(guān)系R，在圖中就有一條從，在圖中就有一條從 xi 到到 xj 的有向邊的有向邊. 注意：注意：l 關(guān)系矩陣適合表示從關(guān)系矩陣適合表示從A到到B的關(guān)系或的關(guān)系或A上的關(guān)系（上的關(guān)系（A,B為有為有窮集）窮集）l 關(guān)系圖適合表示有窮集關(guān)系圖適

9、合表示有窮集A上的關(guān)系上的關(guān)系 12實(shí)例實(shí)例例例4 A=1,2,3,4, R=, R的關(guān)系矩陣的關(guān)系矩陣MR和關(guān)系圖和關(guān)系圖GR如下：如下： 0010000011000011RM137.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算關(guān)系的基本運(yùn)算關(guān)系的基本運(yùn)算定義定義7.6 關(guān)系的關(guān)系的定義域定義域、值域值域與與域域分別定義為分別定義為 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)系運(yùn)算關(guān)系運(yùn)算(逆與合成逆與合成)定義定義7.7 關(guān)系的關(guān)系的逆

10、運(yùn)逆運(yùn)算算 R 1 = | R 定義定義7.8 關(guān)系的關(guān)系的合成合成運(yùn)算運(yùn)算 R S = | y ( R S) 例例6 R = , , , S = , , , , R 1 = , , , R S = , , S R = , , , 15合成的圖示法合成的圖示法利用圖示（不是關(guān)系圖）方法求合成利用圖示（不是關(guān)系圖）方法求合成 R S =, , S R =, , , 16關(guān)系運(yùn)算關(guān)系運(yùn)算(限制與像限制與像)定義定義7.9 設(shè)設(shè)R為二元關(guān)系為二元關(guān)系, A是集合是集合 (1) R在在A上的上的限制限制記作記作 R A, 其中其中 R A = | xRyxA (2) A在在R下的下的像像記作記作RA,

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

12、所以有(F 1) 1=F.(2) 任取任取x, xdomF 1 y(F 1) y(F) xranF 所以有所以有 domF 1=ranF. 同理可證同理可證 ranF 1=domF.19定理定理7.2 設(shè)設(shè)F, G, H是任意的關(guān)系是任意的關(guān)系, 則則(1) (F G) H = F (G H)(2) (F G) 1 = G 1 F 1關(guān)系運(yùn)算的性質(zhì)關(guān)系運(yùn)算的性質(zhì)證證 (1) 任取任取, (F G) H t (F GH) t ( s (FG)H) t s (FGH) s (F t (GH) s (FG H) F (G H) 所以所以 (F G) H = F (G H)20證明證明(2) 任取任取

13、, (F G) 1 F G t (FG) t (G 1F 1) G 1 F 1所以所以 (F G) 1 = G 1 F 1 21關(guān)系運(yùn)算的性質(zhì)關(guān)系運(yùn)算的性質(zhì)定理定理7.3 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, 則則 R IA= IA R=R證證任取任取 R IA t (RIA) t (Rt=yyA) R22關(guān)系運(yùn)算的性質(zhì)關(guān)系運(yùn)算的性質(zhì)定理定理7.4 (1) F (G H) = F GF H (2) (GH) F = G FH F (3) F (GH) F GF H (4) (GH) F G FH F只證只證 (3) 任取任取, F (GH) t (FGH) t (FGH) t (FG)(FH) t

14、(FG) t (FH) F GF H F GF H所以有所以有 F (GH)=F GF H23推廣推廣定理定理7.4 的結(jié)論可以推廣到有限多個關(guān)系的結(jié)論可以推廣到有限多個關(guān)系 R (R1R2Rn) = R R1R R2R Rn (R1R2Rn) R = R1 RR2 RRn R R (R1R2 Rn) R R1R R2 R Rn (R1R2 Rn) R R1 RR2 R Rn R 24關(guān)系運(yùn)算的性質(zhì)關(guān)系運(yùn)算的性質(zhì)定理定理7.5 設(shè)設(shè)F 為關(guān)系為關(guān)系, A, B為集合為集合, 則則(1) F (AB) = F AF B(2) F AB = F AF B(3) F (AB) = F AF B(4)

15、 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 AyF B yF AF B所以有所以有F AB=F AF B. 27關(guān)系的冪運(yùn)算關(guān)系的冪運(yùn)算定義定義7.10設(shè)設(shè) R 為為 A 上的關(guān)系上的關(guān)系, n為自然數(shù)為自然數(shù), 則則 R 的的 n 次冪次冪定義為：定義為：(1)

16、 R0 = | xA = IA(2) Rn+1 = Rn R注意：注意：l對于對于A上的任何關(guān)系上的任何關(guān)系 R1 和和 R2 都有都有 R10 = R20 = IA l對于對于A上的任何關(guān)系上的任何關(guān)系 R 都有都有 R1 = R28例例 8 設(shè)設(shè)A = a,b,c,d, R = , 求求R的各次冪的各次冪, 分別用矩陣和關(guān)系圖表示分別用矩陣和關(guān)系圖表示. 0000100001010010M解解 R 與與 R2的關(guān)系矩陣分別是：的關(guān)系矩陣分別是： 0000000010100101000010000101001000001000010100102M冪的求法冪的求法29R3和和R4的矩陣是：的矩

17、陣是：因此因此M4=M2, 即即R4=R2. 因此可以得到因此可以得到 R2=R4=R6=， R3=R5=R7=R0的關(guān)系矩陣是的關(guān)系矩陣是 0000000010100101,000000000101101043MM 10000100001000010M冪的求法冪的求法30關(guān)系圖關(guān)系圖R0, R1, R2, R3,的關(guān)系圖如下圖所示的關(guān)系圖如下圖所示. R0R1R2=R4=R3=R5=31冪運(yùn)算的性質(zhì)冪運(yùn)算的性質(zhì)定理定理7.6 設(shè)設(shè) A 為為 n 元集元集, R 是是A上的關(guān)系上的關(guān)系, 則存在自然數(shù)則存在自然數(shù) s 和和 t, 使得使得 Rs = Rt.證證 R 為為A上的關(guān)系上的關(guān)系, 由

18、于由于|A|=n, A上的不同關(guān)系只有上的不同關(guān)系只有 個個. 列出列出 R 的各次冪的各次冪 R0, R1, R2, , , , 必存在自然數(shù)必存在自然數(shù) s 和和 t 使得使得 Rs = Rt 22nR22n32定理定理7.7 設(shè)設(shè) R 是是 A上的關(guān)系上的關(guān)系, m, nN, 則則 (1) Rm Rn = Rm+n(2) (Rm)n = Rmn 冪運(yùn)算的性質(zhì)冪運(yùn)算的性質(zhì)證證 用歸納法用歸納法(1) 對于任意給定的對于任意給定的mN, 施歸納于施歸納于n.若若n=0, 則有則有 Rm R0 = Rm IA = Rm = Rm+0 假設(shè)假設(shè) Rm Rn = Rm+n, 則有則有 Rm Rn+

19、1 = Rm (Rn R) = (Rm Rn) R = Rm+n+1 , 所以對一切所以對一切m,nN 有有 Rm Rn = Rm+n. 33證明證明(2) 對于任意給定的對于任意給定的mN, 施歸納于施歸納于n.若若n=0, 則有則有 (Rm)0 = IA = R0 = Rm0 假設(shè)假設(shè) (Rm)n = Rmn, 則有則有 (Rm)n+1 = (Rm)n Rm = (Rmn) Rn = Rmn+m = Rm(n+1)所以對一切所以對一切m,nN 有有 (Rm)n = Rmn. 34定理定理7.8 設(shè)設(shè)R 是是A上的關(guān)系上的關(guān)系, 若存在自然數(shù)若存在自然數(shù) s, t (st) 使得使得 Rs=

20、Rt, 則則 (1) 對任何對任何 kN有有 Rs+k = Rt+k (2) 對任何對任何 k, iN有有 Rs+kp+i = Rs+i, 其中其中 p = t s (3) 令令S = R0,R1,Rt 1, 則對于任意的則對于任意的 qN 有有RqS冪運(yùn)算的性質(zhì)冪運(yùn)算的性質(zhì)證證 (1) Rs+k = Rs Rk = Rt Rk = Rt+k (2) 對對k歸納歸納. 若若k=0, 則有則有Rs+0p+i = Rs+i假設(shè)假設(shè) Rs+kp+i = Rs+i, 其中其中p = t s, 則則 Rs+(k+1)p+i = Rs+kp+i+p = Rs+kp+i Rp = Rs+i Rp = Rs+

21、p+i = Rs+t s+i = Rt+i = Rs+i 由歸納法命題得證由歸納法命題得證.35證明證明(3) 任取任取 qN, 若若 q t, 顯然有顯然有 RqS, 若若q t, 則存在自然數(shù)則存在自然數(shù) k 和和 i 使得使得 q = s+kp+i, 其中其中0ip 1.于是于是 Rq = Rs+kp+i = Rs+i 而而 s+i s+p 1 = s+t s 1 = t 1從而從而證明了證明了 RqS.367.4 關(guān)系的性質(zhì)關(guān)系的性質(zhì)定義定義7.11 設(shè)設(shè) R 為為A上的關(guān)系上的關(guān)系, (1) 若若 x(xA R), 則稱則稱 R 在在 A 上是上是自反自反的的.(2) 若若 x(xA

22、 R), 則稱則稱 R 在在 A 上是上是反自反反自反的的. 實(shí)例：實(shí)例：自反：全域關(guān)系自反：全域關(guān)系EA, 恒等關(guān)系恒等關(guān)系IA, 小于等于關(guān)系小于等于關(guān)系LA, 整除關(guān)系整除關(guān)系DA反自反：實(shí)數(shù)集上的小于關(guān)系、冪集上的真包含關(guān)系反自反：實(shí)數(shù)集上的小于關(guān)系、冪集上的真包含關(guān)系. A=1,2,3, R1, R2, R3是是A上的關(guān)系上的關(guān)系, 其中其中 R1, R2, R3R2 自反自反 ，R3 反自反，反自反，R1既不是自反的也不是反自反的既不是自反的也不是反自反的.37對稱性與反對稱性對稱性與反對稱性定義定義7.12 設(shè)設(shè) R 為為 A上的關(guān)系上的關(guān)系, (1) 若若 x y( x,yAR

23、R), 則稱則稱 R 為為 A上上對對稱稱的關(guān)系的關(guān)系.(2) 若若 x y( x,yARRx=y), 則稱則稱 R 為為A上的上的反對稱反對稱關(guān)系關(guān)系.實(shí)例：對稱關(guān)系：實(shí)例：對稱關(guān)系：A上的全域關(guān)系上的全域關(guān)系EA, 恒等關(guān)系恒等關(guān)系IA和空關(guān)系和空關(guān)系反對稱關(guān)系：恒等關(guān)系反對稱關(guān)系：恒等關(guān)系IA和空關(guān)系也是和空關(guān)系也是A上的反對稱關(guān)系上的反對稱關(guān)系. 設(shè)設(shè)A1,2,3, R1, R2, R3和和R4都是都是A上的關(guān)系上的關(guān)系, 其中其中 R1,，R2, R3,，R4, R1：對稱和反對稱；：對稱和反對稱； R2：只有對稱；：只有對稱；R3：只有反對稱；：只有反對稱； R4：不對稱、不反對稱

24、：不對稱、不反對稱38傳遞性傳遞性定義定義7.13 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, 若若 x y z(x,y,zARRR),則稱則稱 R 是是A上的上的傳遞傳遞關(guān)系關(guān)系.實(shí)例：實(shí)例： A上的全域關(guān)系上的全域關(guān)系 EA,恒等關(guān)系恒等關(guān)系 IA和空關(guān)系和空關(guān)系 ，小于等小于等于和小于關(guān)系，整除關(guān)系，包含與真包含關(guān)系于和小于關(guān)系，整除關(guān)系，包含與真包含關(guān)系設(shè)設(shè) A1,2,3, R1, R2, R3是是A上的關(guān)系上的關(guān)系, 其中其中 R1, R2, R3R1和和R3是是A上的傳遞關(guān)系上的傳遞關(guān)系, R2不是不是A上的傳遞關(guān)系上的傳遞關(guān)系. 39關(guān)系性質(zhì)成立的充要條件關(guān)系性質(zhì)成立的充要條件定理定理7.9

25、 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, 則則(1) R 在在A上自反當(dāng)且僅當(dāng)上自反當(dāng)且僅當(dāng) IA R(2) R 在在A上反自反當(dāng)且僅當(dāng)上反自反當(dāng)且僅當(dāng) RIA = (3) R 在在A上對稱當(dāng)且僅當(dāng)上對稱當(dāng)且僅當(dāng) R=R 1(4) R 在在A上反對稱當(dāng)且僅當(dāng)上反對稱當(dāng)且僅當(dāng) RR 1 IA(5) R 在在A上傳遞當(dāng)且僅當(dāng)上傳遞當(dāng)且僅當(dāng) R R R 40證明證明證明證明 只證只證(1)、(3)、(4)、(5)(1) 必要性必要性任取任取, 由于由于R 在在A上自反必有上自反必有 IA x,yAx=y R從而證明了從而證明了IA R充分性充分性.任取任取x, 有有 xA IA R因此因此 R 在在A上是自

26、反的上是自反的. 41證明證明(3) 必要性必要性. 任取任取, R R R 1所以所以 R = R 1充分性充分性.任取任取, 由由R = R 1得得R R 1 R所以所以R在在A上是對稱的上是對稱的42證明證明(4) 必要性必要性. 任取任取, 有有 RR 1 RR 1 RR x=y x,y A IA這就證明了這就證明了RR 1 IA充分性充分性. 任取任取, RR RR 1 RR 1 IA x=y從而證明了從而證明了R在在A上是反對稱的上是反對稱的.43證明證明(5) 必要性必要性. 任取任取有有 R R t (RR) R所以所以 R R R充分性充分性. 任取任取,R, 則則 RR R

27、 R R 所以所以 R 在在 A上是傳遞的上是傳遞的44自反性自反性反自反性反自反性對稱性對稱性反對稱性反對稱性傳遞性傳遞性集合集合IA RRIA=R=R 1RR 1 IAR R R關(guān)系關(guān)系矩陣矩陣主對角主對角線元素線元素全是全是1主對角線主對角線元素全是元素全是0矩陣是矩陣是對稱矩陣對稱矩陣若若rij1, 且且ij, 則則rji0M2中中1位置位置, M中相應(yīng)位中相應(yīng)位置都是置都是1關(guān)系關(guān)系圖圖每個頂每個頂點(diǎn)都有點(diǎn)都有環(huán)環(huán)每個頂點(diǎn)每個頂點(diǎn)都沒有環(huán)都沒有環(huán)兩點(diǎn)之間兩點(diǎn)之間有邊有邊, 是是一對方向一對方向相反的邊相反的邊兩點(diǎn)之間有兩點(diǎn)之間有邊邊,是一條有是一條有向邊向邊點(diǎn)點(diǎn)xi到到xj有有邊邊,

28、 xj 到到xk有邊有邊, 則則xi到到xk也有邊也有邊 關(guān)系性質(zhì)的三種等價條件關(guān)系性質(zhì)的三種等價條件45自反性自反性反自反性反自反性對稱性對稱性反對稱性反對稱性傳遞性傳遞性R1 1 R1R2 R1R2 R1 R2 R1 R2 關(guān)系的性質(zhì)和運(yùn)算之間的聯(lián)系關(guān)系的性質(zhì)和運(yùn)算之間的聯(lián)系467.5 關(guān)系的閉包關(guān)系的閉包 主要內(nèi)容主要內(nèi)容l 閉包定義閉包定義l 閉包的構(gòu)造方法閉包的構(gòu)造方法 集合表示集合表示 矩陣表示矩陣表示 圖表示圖表示l 閉包的性質(zhì)閉包的性質(zhì) 47閉包定義閉包定義定義定義7.14 設(shè)設(shè)R是非空集合是非空集合A上的關(guān)系上的關(guān)系, R的的自反自反(對稱對稱或或傳遞傳遞)閉閉包包是是A上的

29、關(guān)系上的關(guān)系R , 使得使得R 滿足以下條件：滿足以下條件：(1) R 是自反的是自反的(對稱的或傳遞的對稱的或傳遞的) (2) R R (3) 對對A上任何包含上任何包含R的自反的自反(對稱或傳遞對稱或傳遞)關(guān)系關(guān)系R 有有RR R的自反閉包記作的自反閉包記作r(R), 對稱閉包記作對稱閉包記作s(R), 傳遞閉包記作傳遞閉包記作t(R). 定理定理7.10 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, 則有則有(1) r(R)=RR0(2) s(R)=RR 1(3) t(R)=RR2R3說明：對有窮集說明：對有窮集A(|A|=n)上的關(guān)系上的關(guān)系, (3)中的并最多不超過中的并最多不超過Rn48證明證明

30、證證 只證只證(1)和和(3). (1) 由由IA=R0 RR0 知知 RR0是自反的是自反的, 且滿足且滿足R RR0設(shè)設(shè)R 是是A上包含上包含R的自反關(guān)系的自反關(guān)系, 則有則有R R 和和IA R . 從而有從而有RR0 R . RR0滿足閉包定義滿足閉包定義, 所以所以r(R)=RR0.(1) 先證先證 RR2 t(R)成立成立. 用歸納法證明對任意正整數(shù)用歸納法證明對任意正整數(shù)n 有有Rn t(R). n=1時有時有R1=R t(R). 假設(shè)假設(shè)Rn t(R)成立成立, 那么對任意的那么對任意的 Rn+1=Rn R t ( RnR) t (t(R)t(R) t(R) 這就證明了這就證明

31、了Rn+1 t(R). 由歸納法命題得證由歸納法命題得證. 49證明證明再證再證 t(R) RR2成立成立, 為此只須證明為此只須證明RR2傳遞傳遞. 任取任取, 則則 RR2RR2 t (Rt) s(Rs) t s (Rt Rs ) t s (Rt+s ) RR2從而證明了從而證明了RR2是傳遞的是傳遞的.50閉包的矩陣表示和圖表示閉包的矩陣表示和圖表示設(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 是是 轉(zhuǎn)置矩陣，相加時使用轉(zhuǎn)置矩陣，相

32、加時使用邏輯加邏輯加.設(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 的邊以外的邊以外, 以下述以下述方法添加新的邊：方法添加新的邊： (1) 考察考察G 的每個頂點(diǎn)的每個頂點(diǎn), 若沒環(huán)就加一個環(huán)，得到若沒環(huán)就加一個環(huán)，得到Gr (2) 考察考察G 的每條邊的每條邊, 若有一條若有一條 xi 到到 xj 的單向邊的單向邊, ij, 則在則在G 中加一條中加一條 xj 到到 xi 的反向邊的反向邊, 得到得到Gs(3) 考察考察G 的每個頂

33、點(diǎn)的每個頂點(diǎn) xi, 找找 xi 可達(dá)的所有頂點(diǎn)可達(dá)的所有頂點(diǎn) xj (允許允許i=j )， 如果沒有從如果沒有從 xi 到到 xj 的邊的邊, 就加上這條邊就加上這條邊, 得到圖得到圖Gt51實(shí)例實(shí)例例例9 設(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)52閉包的性質(zhì)閉包的性質(zhì)定理定理7.11 設(shè)設(shè)R是非空集合是非空集合A上的關(guān)系上的關(guān)系, 則則(1) R是自反的當(dāng)且僅當(dāng)是自反的當(dāng)且僅當(dāng) r(R)=R. (2) R是對稱的當(dāng)且僅當(dāng)是對稱的當(dāng)且僅當(dāng) s(R)=R. (3) R是傳遞的當(dāng)且僅當(dāng)是傳遞的當(dāng)且

34、僅當(dāng) t(R)=R.定理定理7.12 設(shè)設(shè)R1和和R2是非空集合是非空集合A上的關(guān)系上的關(guān)系, 且且 R1 R2, 則則(1) r(R1) r(R2) (2) s(R1) s(R2) (3) t(R1) t(R2)證明證明 略略53定理定理7.13 設(shè)設(shè)R是非空集合是非空集合A上的關(guān)系上的關(guān)系,(1) 若若R是自反的是自反的, 則則 s(R) 與與 t(R) 也是自反的也是自反的(2) 若若R是對稱的是對稱的, 則則 r(R) 與與 t(R) 也是對稱的也是對稱的(3) 若若R是傳遞的是傳遞的, 則則 r(R) 是傳遞的是傳遞的. 說明：如果需要進(jìn)行多個閉包運(yùn)算，比如求說明：如果需要進(jìn)行多個閉

35、包運(yùn)算，比如求R的自反、對的自反、對稱、傳遞的閉包稱、傳遞的閉包 tsr(R)，運(yùn)算順序如下：，運(yùn)算順序如下： tsr(R) = rts(R) = trs(R)閉包的性質(zhì)閉包的性質(zhì)證明證明 略略547.6 等價關(guān)系與劃分等價關(guān)系與劃分 主要內(nèi)容主要內(nèi)容l 等價關(guān)系的定義與實(shí)例等價關(guān)系的定義與實(shí)例l 等價類及其性質(zhì)等價類及其性質(zhì)l 商集與集合的劃分商集與集合的劃分l 等價關(guān)系與劃分的一一對應(yīng)等價關(guān)系與劃分的一一對應(yīng) 55等價關(guān)系的定義與實(shí)例等價關(guān)系的定義與實(shí)例定義定義7.15 設(shè)設(shè)R為非空集合上的關(guān)系為非空集合上的關(guān)系. 如果如果R是自反的、對稱的和是自反的、對稱的和傳遞的傳遞的, 則稱則稱R為

36、為A上的上的等價關(guān)系等價關(guān)系. 設(shè)設(shè) R 是一個等價關(guān)系是一個等價關(guān)系, 若若R, 稱稱 x等價于等價于y, 記做記做xy. 實(shí)例實(shí)例 設(shè)設(shè) A=1,2,8, 如下定義如下定義A上的關(guān)系上的關(guān)系R： R=| x,yAx y(mod 3)其中其中x y(mod 3)叫做叫做 x與與 y 模模3相等相等, 即即x除以除以3的余數(shù)與的余數(shù)與y除以除以3的余數(shù)相等的余數(shù)相等. 不難驗(yàn)證不難驗(yàn)證 R 為為A上的等價關(guān)系上的等價關(guān)系, 因?yàn)橐驗(yà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

37、 3), y z(mod 3), 則有則有x z(mod 3)56模模 3 等價關(guān)系的關(guān)系圖等價關(guān)系的關(guān)系圖等價關(guān)系的實(shí)例等價關(guān)系的實(shí)例57等價類定義等價類定義 定義定義7.16 設(shè)設(shè)R為非空集合為非空集合A上的等價關(guān)系上的等價關(guān)系, xA，令，令 xR = y | yAxRy稱稱xR 為為x關(guān)于關(guān)于R的等價類的等價類, 簡稱為簡稱為x的的等價類等價類, 簡記為簡記為x或或 實(shí)例實(shí)例 A=1, 2, , 8上模上模3等價關(guān)系的等價類：等價關(guān)系的等價類： 1 = 4 = 7 = 1, 4, 7 2 = 5 = 8 = 2, 5, 8 3 = 6 = 3, 6x58等價類的性質(zhì)等價類的性質(zhì)定理定理

38、7.14 設(shè)設(shè)R是非空集合是非空集合A上的等價關(guān)系上的等價關(guān)系, 則則(1) x A, x是是A的非空子集的非空子集(2) x,y A, 如果如果 xRy, 則則 x = y(3) x,y A, 如果如果 x y, 則則 x與與y不交不交(4) x | x A=A證證 (1) 由定義由定義, x A有有x A. 又又x x, 即即x非空非空. (2) 任取任取 z, 則有則有 zx R R R R R R從而證明了從而證明了zy. 綜上所述必有綜上所述必有 x y. 同理可證同理可證 y x. 這就得到了這就得到了x = y.59證明證明(3) 假設(shè)假設(shè) xy, 則存在則存在 z xy, 從而

39、有從而有z xz y, 即即 R R成立成立. 根據(jù)根據(jù)R的對稱性和傳遞性必有的對稱性和傳遞性必有 R, 與與 x y矛盾矛盾(4) 先證先證x | x A A. 任取任取y, y x | x A x(x Ay x) y xx A y A 從而有從而有x | xA A 再證再證A x | xA. 任取任取y, y A y yy A yx | x A 從而有從而有x | xA A成立成立.綜上所述得綜上所述得x | x A = A. 60商集與劃分商集與劃分定義定義7.17 設(shè)設(shè) R 為非空集合為非空集合A上的等價關(guān)系上的等價關(guān)系, 以以 R 的所有等價的所有等價類作為元素的集合稱為類作為元素的

40、集合稱為A關(guān)于關(guān)于R的的商集商集, 記做記做A/R, A/R = xR | xA實(shí)例實(shí)例 設(shè)設(shè) A=1,2,8，A關(guān)于模關(guān)于模3等價關(guān)系等價關(guān)系R的商集為的商集為 A/R = 1,4,7, 2,5,8, 3,6A關(guān)于恒等關(guān)系和全域關(guān)系的商集為：關(guān)于恒等關(guān)系和全域關(guān)系的商集為： A/IA = 1, 2, , 8， A/EA = 1,2,8定義定義7.18 設(shè)設(shè)A為非空集合為非空集合, 若若A的子集族的子集族( P(A)滿足滿足:(1) (2) x y(x,y xyxy=)(3) = A則稱則稱是是A的一個的一個劃分劃分, 稱稱中的元素為中的元素為A的的劃分塊劃分塊.61劃分實(shí)例劃分實(shí)例 例例10

41、 設(shè)設(shè) A a, b, c, d , 給定給定 1, 2, 3, 4, 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)系上所有的等價關(guān)系實(shí)例實(shí)例1 123 31 1 123 351 123 321 123 341 123 331對應(yīng)對應(yīng) EA, 5 對應(yīng)對應(yīng) IA, 2, 3 和和 4分別對應(yīng)分別對應(yīng) R2,

42、R3和和 R4. R2=,IA R3=,IA R4=,IA解解 先做出先做出A的劃分的劃分, 從左到右分別記作從左到右分別記作 1, 2, 3, 4, 5.637.7 偏序關(guān)系偏序關(guān)系 主要內(nèi)容主要內(nèi)容l 偏序關(guān)系偏序關(guān)系 偏序關(guān)系的定義偏序關(guān)系的定義 偏序關(guān)系的實(shí)例偏序關(guān)系的實(shí)例l 偏序集與哈斯圖偏序集與哈斯圖l 偏序集中的特殊元素及其性質(zhì)偏序集中的特殊元素及其性質(zhì) 極大元、極小元、最大元、最小元極大元、極小元、最大元、最小元 上界、下界、最小上界、最大下界上界、下界、最小上界、最大下界64定義與實(shí)例定義與實(shí)例定義定義7.19 偏序關(guān)系偏序關(guān)系：非空集合：非空集合A上的自反、反對稱和傳遞的關(guān)

43、系，上的自反、反對稱和傳遞的關(guān)系，記作記作 . 設(shè)設(shè) 為偏序關(guān)系為偏序關(guān)系, 如果如果 , 則記作則記作 x y, 讀讀作作x“小于或等于小于或等于”y. 實(shí)例實(shí)例集合集合A上的恒等關(guān)系上的恒等關(guān)系 IA是是 A上的偏序關(guān)系上的偏序關(guān)系. 小于或等于關(guān)系小于或等于關(guān)系, 整除關(guān)系和包含關(guān)系也是相應(yīng)集合上的偏整除關(guān)系和包含關(guān)系也是相應(yīng)集合上的偏序關(guān)系序關(guān)系. 65相關(guān)概念相關(guān)概念定義定義7.20 設(shè)設(shè) R 為非空集合為非空集合A上的偏序關(guān)系上的偏序關(guān)系, (1) x, yA, x與與y可比可比 x yy x (2) 任取元素任取元素 x 和和 y, 可能有下述幾種情況發(fā)生：可能有下述幾種情況發(fā)生

44、： x y (或或 y x), xy, x與與y不是可比的不是可比的定義定義7.21 R 為非空集合為非空集合A上的偏序關(guān)系上的偏序關(guān)系, (1) x,yA, x與與y都是可比的，則稱都是可比的，則稱R為為全序全序（或線序）（或線序）實(shí)例：數(shù)集上的小于或等于關(guān)系是全序關(guān)系實(shí)例：數(shù)集上的小于或等于關(guān)系是全序關(guān)系,整除關(guān)系不是正整除關(guān)系不是正整數(shù)集合上的全序關(guān)系整數(shù)集合上的全序關(guān)系定義定義7.22 x,yA, 如果如果 x y 且不存在且不存在 zA 使得使得 x z y, 則稱則稱 y覆蓋覆蓋x.例如例如1,2,4,6集合上整除關(guān)系集合上整除關(guān)系, 2覆蓋覆蓋1, 4和和6覆蓋覆蓋2, 4不覆蓋

45、不覆蓋1. 66偏序集與哈斯圖偏序集與哈斯圖定義定義7.23 集合集合A和和A上的偏序關(guān)系上的偏序關(guān)系 一起叫做一起叫做偏序集偏序集, 記作記作. 實(shí)例實(shí)例: , 哈斯圖哈斯圖: 利用偏序關(guān)系的自反、反對稱、傳遞性進(jìn)行簡化的利用偏序關(guān)系的自反、反對稱、傳遞性進(jìn)行簡化的關(guān)系圖關(guān)系圖特點(diǎn)：特點(diǎn)：(1) 每個結(jié)點(diǎn)沒有環(huán)每個結(jié)點(diǎn)沒有環(huán)(2) 兩個連通的結(jié)點(diǎn)之間的序關(guān)系通過結(jié)點(diǎn)位置的高低表兩個連通的結(jié)點(diǎn)之間的序關(guān)系通過結(jié)點(diǎn)位置的高低表 示，位置低的元素的順序在前示，位置低的元素的順序在前(3) 具有覆蓋關(guān)系的兩個結(jié)點(diǎn)之間連邊具有覆蓋關(guān)系的兩個結(jié)點(diǎn)之間連邊67實(shí)例實(shí)例例例12 偏序集偏序集和和的的哈斯圖哈

46、斯圖.68例例13 已知偏序集已知偏序集的哈斯圖如下圖所示的哈斯圖如下圖所示, 試求出集合試求出集合A和關(guān)系和關(guān)系R的表達(dá)式的表達(dá)式. 解解 A= a, b, c, d, e, f, g, h R=,IA實(shí)例實(shí)例69偏序集中的特殊元素偏序集中的特殊元素 定義定義7.24 設(shè)設(shè)為偏序集為偏序集, B A, yB(1) 若若 x(xBy x)成立成立, 則稱則稱 y 為為B的的最小元最小元(2) 若若 x(xBx y)成立成立, 則稱則稱 y 為為B的的最大元最大元(3) 若若 x(xBx yx=y)成立成立, 則稱則稱 y 為為B的的極小元極小元(4) 若若 x(xBy xx=y)成立成立, 則

47、稱則稱 y 為為B的的極大元極大元性質(zhì)：性質(zhì)：(1) 對于有窮集，極小元和極大元一定存在，可能存在多個對于有窮集，極小元和極大元一定存在，可能存在多個. (2) 最小元和最大元不一定存在，如果存在一定惟一最小元和最大元不一定存在，如果存在一定惟一.(3) 最小元一定是極小元；最大元一定是極大元最小元一定是極小元；最大元一定是極大元. (4) 孤立結(jié)點(diǎn)既是極小元，也是極大元孤立結(jié)點(diǎn)既是極小元，也是極大元.70定義定義7.25 設(shè)設(shè)為偏序集為偏序集, B A, yA(1) 若若 x(xBx y)成立成立, 則稱則稱y為為B的的上界上界 (2) 若若 x(xBy x)成立成立, 則稱則稱y為為B的的

48、下界下界 (3) 令令Cy| y為為B的上界的上界, C的最小元為的最小元為B的的最小上界最小上界或或上確界上確界 (4) 令令Dy| y為為B的下界的下界, D的最大元為的最大元為B的的最大下界最大下界或或下確界下確界偏序集中的特殊元素偏序集中的特殊元素 性質(zhì)：性質(zhì)：(1) 下界、上界、下確界、上確界不一定存在下界、上界、下確界、上確界不一定存在(2) 下界、上界存在不一定惟一下界、上界存在不一定惟一(3) 下確界、上確界如果存在，則惟一下確界、上確界如果存在，則惟一(4) 集合的最小元是其下確界，最大元是其上確界；反之不對集合的最小元是其下確界，最大元是其上確界；反之不對. 71實(shí)例實(shí)例例

49、例14 設(shè)偏序集設(shè)偏序集，求，求A的極小元、最小元、極大元、的極小元、最小元、極大元、最最大元，設(shè)大元，設(shè)B b,c,d , 求求B的下界、上界、下確界、上確界的下界、上界、下確界、上確界. 解解極小元：極小元：a, b, c, g； 極大元：極大元：a, f, h；沒有最小元與最大元沒有最小元與最大元.B的下界和最大下界都不存在；的下界和最大下界都不存在；上界有上界有 d 和和 f, 最小上界為最小上界為 d. 72實(shí)例實(shí)例例例15 設(shè)設(shè)X為集合為集合, AP(X)X, 且且A. 若若|X|=n, n2. 問：問： (1) 偏序集偏序集 是否存在最大元？是否存在最大元？ (2) 偏序集偏序集

50、 是否存在最小元？是否存在最小元？ (3) 偏序集偏序集 中極大元和極小元的一般形式是什么？中極大元和極小元的一般形式是什么？ 并說明理由并說明理由. 解解 (1) 不存在最小元和最大元不存在最小元和最大元, 因?yàn)橐驗(yàn)閚2.(2) 的極小元就是的極小元就是 X 的所有單元集的所有單元集, 即即x, xX.(3) 的極大元恰好比的極大元恰好比 X 少一個元素少一個元素, 即即X x, xX.73第七章第七章 習(xí)題課習(xí)題課 主要內(nèi)容主要內(nèi)容l 有序?qū)εc笛卡兒積的定義與性質(zhì)有序?qū)εc笛卡兒積的定義與性質(zhì)l 二元關(guān)系、從二元關(guān)系、從A到到B的關(guān)系、的關(guān)系、A上的關(guān)系上的關(guān)系l 關(guān)系的表示法：關(guān)系表達(dá)式、

51、關(guān)系矩陣、關(guān)系圖關(guān)系的表示法：關(guān)系表達(dá)式、關(guān)系矩陣、關(guān)系圖l 關(guān)系的運(yùn)算：定義域、值域、域、逆、合成、限制、像、關(guān)系的運(yùn)算：定義域、值域、域、逆、合成、限制、像、冪冪l 關(guān)系運(yùn)算的性質(zhì)關(guān)系運(yùn)算的性質(zhì): A上關(guān)系的自反、反自反、對稱、反對上關(guān)系的自反、反自反、對稱、反對稱、傳遞的性質(zhì)稱、傳遞的性質(zhì)l A上關(guān)系的自反、對稱、傳遞閉包上關(guān)系的自反、對稱、傳遞閉包l A上的等價關(guān)系、等價類、商集與上的等價關(guān)系、等價類、商集與A的劃分的劃分l A上的偏序關(guān)系與偏序集上的偏序關(guān)系與偏序集74基本要求基本要求l 熟練掌握關(guān)系的三種表示法熟練掌握關(guān)系的三種表示法 l 能夠判定關(guān)系的性質(zhì)（等價關(guān)系或偏序關(guān)系）能

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