離散數(shù)學第4章屈

1、1,第4章 關系,4.1 關系的定義及其表示4.2 關系運算4.3 關系的性質(zhì)4.4 等價關系與偏序關系,2,4.1 關系的定義及其表示,4.1.1 有序?qū)εc笛卡兒積4.1.2 二元關系的定義4.1.3 二元關系的表示,3,定義4.1 由兩個元素，如x和y，按照一定的順序組成的二元組稱為有序?qū)?，記?實例：點的直角坐標 (3,?4) 有序?qū)Φ男再|(zhì) 有序性 ? （當x? y時） 與相等的充分必要條

2、件是 = ? x=u ? y=v例1 =，求 x, y. 解 3y?4=2, x+5=y ? y=2, x= ?3,有序?qū)?4,笛卡兒積,定義4.2 設A, B為集合，A與B 的笛卡兒積記作A?B， A?B = { | x?A ? y?B }.例2 A={0, 1}, B={a, b, c} A?B={,,,,,}

3、B?A ={,,,,,} A = {?}, B = ? P(A)?A = {, } P(A)?B = ?,5,笛卡兒積的性質(zhì),對于并或交運算滿足分配律 A?(B?C)=(A?B)?(A?C) (B?C)?A=(B?A)?(C?A) A?(B?C)=(A?B)?(A?C) (B?C)?A=(B?A)?(C?A),若A或B中

4、有一個為空集，則A?B就是空集. A??=??B=?,不適合交換律 A?B?B?A (A?B, A??, B??),不適合結(jié)合律 (A?B)?C?A?(B?C) (A??, B??, C??),若|A|=m, |B|=n, 則 |A?B|=mn,6,有序 n 元組和 n 階笛卡爾積,定義4.3 (1) 由 n 個元素 x1, x2, …, xn按照一定的順序排列構成

5、 有序 n 元組，記作 (2) 設A1, A2, …, An為集合，稱 A1?A2?…?An={ | xi?Ai, i=1,2, …,n} 為 n 階笛卡兒積. 實例 (1,1,0)為空間直角坐標，(1,1,0)?R ?R ?R,7,二元關系的定義,定義4.4如果一個集合滿足以下條件之一：（1）集合非空, 且它的元素都是有序?qū)Γ?）集合是空集則稱該集合為一個二元關系, 簡稱

6、為關系，記作R.如∈R, 可記作 xRy；如果?R, 則記作x y實例：R={,}, S={,a,b}. R是二元關系, 當a, b不是有序?qū)r，S不是二元關系根據(jù)上面的記法，可以寫1R2, aRb, a c等.,8,實例,例3 (1) R={ | x,y?N, x+y, , , , , } (2) C={ | x,y?R, x2+y2=1}，其中R代表實數(shù)集合，

7、 C是直角坐標平面上點的橫、縱坐標之間的關系， C中的所有的點恰好構成坐標平面上的單位圓. (3) R={ | x,y,z?R, x+2y+z=3}， R代表了空間直角坐標系中的一個平面.,9,5元關系的實例—數(shù)據(jù)庫實體模型,5元組：，,10,從A到B的關系與A上的關系,定義4.5 設A,B為集合, A×B的任何子集所定義的二元關系叫做從 A 到

8、 B 的二元關系, 當 A=B 時則叫做 A上的二元關系.例4 A={0,1}, B={1,2,3}, R1={}, R2=A×B, R3=?, R4={}, 從A到B的關系: R1, R2, R3, R4, A上的關系R3和R4. 計數(shù)：|A|=n, |B|=m, |A×B|=nm, A×B 的子集有 個. 所以從A到B有 個不同的二

9、元關系. |A|=n, A上有 不同的二元關系. 例如 |A|=3, 則 A上有512個不同的二元關系.,11,A上重要關系的實例,設A為任意集合，?是A上的關系，稱為空關系定義 4.6 EA, IA分別稱為全域關系與恒等關系，其中 EA={ | x∈A ?y∈A}=A×A IA={ | x∈A}例如, A={1,2}, 則 EA={,,,} IA={,},12,A上重要關

10、系的實例（續(xù)）,小于等于關系LA, 整除關系DA, 包含關系R?定義如下：定義4.7 LA={| x,y∈A∧x≤y}, 這里A?R，R為實數(shù)集合  DB={| x,y∈B∧x整除y}, B?Z*, Z*為非0整數(shù)集  R?={| x,y∈A∧x?y}, 這里A是集合族.例如 A={1,2,3}, B={a,b}, 則 LA={,,,,,} DA={,,,,} A=P(B)={?,{a},{

11、b},{a,b}}, 則A上的包含關系是 R?={,,,,, ,,,}類似的還可以定義大于等于關系, 小于關系, 大于關系, 真包含關系等等.,13,矩陣的定義,定義 由m×n個數(shù)aij(i=1,2,…,m, j=1,2,…,n)排成的一個m行n列的矩形表，稱為m×n矩陣。記為,14,定義,矩陣的乘法,，,其中，,(i=1,2,…,m, j=1,2,…,n),15,矩陣的乘法,1

12、6,關系的表示,表示方式：關系的集合表達式、關系矩陣、關系圖 定義4.8 關系矩陣 若A={x1, x2, …, xm}，B={y1, y2, …, yn}，R是從A到B的關系，R的關系矩陣是布爾矩陣MR = [ rij ] m?n, 其中 rij = 1? ?R. 定義4.9 關系圖 若A= {x1, x2, …, xm}，R是從A上的關系，R的關系圖是GR=, 其中A為結(jié)點集，R為邊集.如果屬于關系R，在圖中就有一條從

13、 xi 到 xj 的有向邊. 注意：設A, B為有窮集關系矩陣適合于表示從A到B 的關系或者A上的關系關系圖適合于表示A上的關系,17,實例,例5 A={a, b, c, d}, R={,,,,},R的關系矩陣 MR 和關系圖 GR 如下：,18,4.2.1 關系的基本運算定義域、值域、域、逆、合成基本運算的性質(zhì)4.2.2 關系的冪運算冪運算的定義冪運算的方法冪運算的性質(zhì),4.2 關系運算,19,關系的基本運算,

14、定義4.10 定義域、值域 和 域 domR = { x | ?y (?R) } ranR = { y | ?x (?R) } fldR = domR ? ranR,例1 R={,,,}, 則 domR = ranR = fldR =,{ a, c, {a}, d, , 66o0nuz},{ a, c, {a}, d },{, d,

15、1q6501f},20,關系的基本運算（續(xù)）,定義4.11 R 的逆 R?1 = { | ?R}定義4.12 R與S的合成 R°S = { | ? y (?R??S) },例2 R={, , , } S={, , , , } R?1 = R°S = S°R =,{, , },{, , ,},

16、{, , , },21,合成運算的圖示方法,利用圖示（不是關系圖）方法求合成 R°S ={, , } S°R ={, , , },22,若X={x1,x2,x3,…xm} Y={y1,y2,y3,…yn} Z={z1,z2,z3,…zp}R是X到Y(jié)的關系，關系矩陣MR是m×n階矩陣,S是Y到Z的關系，關系矩陣MS是n×p階矩陣.設C=R ? S, 關系矩陣MC為m×p階矩陣

17、，其中,用矩陣表示兩個關系的復合,23,R是X到Y(jié)的關系，S是Y到Z的關系，R={(1,2),(3,4),(2,2)}，S={(4,2),(2,5),(3,1),(1,3)}，則,例題,設 X={1,2,3}, Y={1,2,3,4}, Z={1,2,3,4,5},24,基本運算的性質(zhì),定理4.1 設F是任意的關系, 則(1) (F?1)?1=F(2) domF?1=ranF, ranF?1=domF證 (1) 任取

18、, 由逆的定義有 ∈(F ? 1)?1 ? ∈F?1 ? ∈F所以有 (F?1)?1=F(2) 任取x, x∈domF?1 ? ?y (∈F?1) ? ?y (∈F) ? x∈ranF 所以有domF?1= ranF. 同理可證 ranF?1 = domF.,25,定理4.2 設F, G, H是任意的關系, 則 (1) (F°G)°H=F°(G°H) (

19、2) (F°G)?1= G?1°F?1 證 (1) 任取,  ?(F°G)°H ? ?t (∈F°G∧∈H) ? ?t (?s (∈F∧∈G)∧∈H) ? ?t ?s (∈F∧∈G∧∈H) ? ?s (∈F∧?t (∈G∧∈H)) ? ?s (∈F∧∈G°H) ? ∈F°(G°H) 所以 (F°G)°H = F°(G°H),基本運算的性質(zhì)（續(xù)）,2

20、6,(2) 任取,  ∈(F°G)?1  ? ∈F°G ? ?t (∈F∧(t, x)∈G) ? ?t (∈G?1∧(t, y)∈F?1) ? ∈G?1°F?1所以 (F°G)?1 = G?1°F?1,基本運算的性質(zhì)（續(xù)）,27,定理4.3 設 R 為 A上的關系, 則  R°IA= IA°R = R 證明任?。牐?∈R°IA ? ?t (∈R∧∈IA)

21、 ? ?t (∈R∧t=y∧y∈A) ? ∈R從而有R°IA=R. 同理可證 IA°R=R.,基本運算的性質(zhì)（續(xù)）,28,A上關系的冪運算定義,定義4.13 設R為A上的關系, n為自然數(shù), 則 R 的 n次冪是 (1) R0 = { | x∈A } = IA (2) Rn+1 = Rn°R 注意： 對于A上的任何關系R1和R2都有

22、 R10 = R20 = IA 對于A上的任何關系 R 都有 R1 = R,29,冪運算的方法,對于集合表示的關系R，計算Rn 就是 n 個 R 合成 . 矩陣表示的關系就是矩陣相乘, 其中相加采用邏輯加. 例3 設A = {a, b, c, d}, R = {,,,}, 求R的各次冪, 分別用矩陣和關系圖表示.解 R與R2的關系矩陣分別為,,30,同理R3和R4的矩陣是：

23、因此M4 = M2, 即R4 = R2. 因此可以得到R2 = R4 = R6 = …, R3 = R5 = R7 = …而R0 = IA的關系矩陣,,冪運算的方法（續(xù)）,31,用關系圖的方法得到R0, R1, R2, R3,…的關系圖如下圖所示,冪運算的方法（續(xù)）,32,冪運算的性質(zhì),定理4.4 設 A 為 n 元集, R是A上的關系, 則存在自然數(shù) s 和 t, 使得 Rs = Rt.證 R 為A上

24、的關系, 由于|A| = n, A上的不同關系只有 個. 當列出 R 的各次冪 R0, R1, R2, …, , …, 必存在自然數(shù) s 和 t 使得 Rs = Rt.,33,定理4.5 設 R 是 A 上的關系, m, n∈N, 則 (1) Rm°Rn = Rm+n (2) (Rm)n = Rmn 證 用歸納法 (1) 對于任意給定的 m∈N, 施歸納于 n.

25、若n=0, 則有 Rm°R0 = Rm°IA= Rm = Rm+0 假設 Rm°Rn = Rm+n, 則有Rm°Rn+1 = Rm°(Rn°R) = (Rm°Rn)°R = Rm+n+1 , 所以對一切 m, n∈N 有 Rm°Rn = Rm+n.,冪運算的性質(zhì)（續(xù)）,34,(2) 對于任意給定的 m∈N, 施歸納于 n. 若 n = 0, 則有 (Rm)0 = IA = R0 = Rm×0

26、 假設 (Rm)n = Rmn, 則有(Rm)n+1 = (Rm)n°Rm = (Rmn)°Rm = Rmn+m = Rm(n+1) 所以對一切 m, n∈N 有 (Rm)n = Rmn.,冪運算的性質(zhì)（續(xù)）,35,定理4.6 設R 是A上的關系, 若存在自然數(shù) s, t (s<t) 使得 Rs = Rt, 則 (1) 對任何 k∈N 有 Rs+k = Rt+k (2) 對任何 k, i∈N 有Rs+k

27、p+i = Rs+i, 其中p = t?s (3) 令S={R0,R1, …, Rt?1}, 則對于任意的 q∈N有 Rq∈S證明 (1) Rs+k = Rs°Rk = Rt°Rk = Rt+k （2）對 k 歸納. 若k=0, 則有 Rs+0p+i = Rs+i假設 Rs+kp+i = Rs+i, 其中p = t?s, 則Rs+(k+1)p+i = Rs+kp+i+p = Rs+kp+i°Rp

28、 = Rs+i°Rp = Rs+p+i = Rs+t?s+i = Rt+i = Rs+i 由歸納法命題得證.,冪運算的性質(zhì)（續(xù)）,36,(3) 任取 q∈N, 若q<t, 顯然有 Rq∈S. 若 q≥t, 則存在自然數(shù) k 和 i 使得 q = s+kp+i，其中0≤i≤p?1. 于是Rq = Rs+kp+i = Rs+i 而 s+i ≤s+p?1

29、 = s+t?s?1 = t?1 這就證明了 Rq∈S.,冪運算的性質(zhì)（續(xù)）,37,4.3 關系的性質(zhì),4.3.1關系性質(zhì)的定義和判別自反性與反自反性對稱性與反對稱性傳遞性4.3.2 關系的閉包閉包定義閉包計算 Warshall算法,38,自反性與反自反性,定義4.14 設R為A上的關系,  (1) 若?x(x∈A→?R), 則稱R在A上是自反的. (2) 若?x(x∈A→?R), 則稱R在A上是

30、反自反的.自反：A上的全域關系EA, 恒等關系IA, 小于等于關系LA, 整除關系DA反自反：實數(shù)集上的小于關系、冪集上的真包含關系.,R2自反, R3 反自反, R1既不自反也不反自反.,例1 A = {a, b, c}, R1, R2, R3 是 A上的關系, 其中 R1 = {,} R2 = {,,,} R3 = {},39,對稱性與反對稱性,例2 設A＝{a,b,c},

31、 R1, R2, R3和R4都是A上的關系, 其中  R1＝{,}， R2＝{,,} R3＝{,}， R4＝{,,},定義4.15 設R為A上的關系, (1) 若?x?y(x,y∈A∧∈R→∈R), 則稱R為A上 對稱的關系.(2) 若?x?y(x,y∈A∧∈R∧∈R→x=y), 則稱R 為A上的反對稱關系.實例 對稱：A上的全域關系EA, 恒等關系IA和空

32、關系? 反對稱：恒等關系IA，空關系是A上的反對稱關系,R1 對稱、反對稱. R2 對稱. R3 反對稱. R4 不對稱、也不反對稱,40,傳遞性,例3 設A＝{a, b, c}, R1, R2, R3是A上的關系, 其中 R1＝{,} R2＝{,} R3＝{},定義4.16 設R為A上的關系, 若 ?x?y?z(x,y

33、,z∈A∧∈R∧∈R→∈R),則稱R是A上的傳遞關系.實例：A上的全域關系 EA, 恒等關系 IA 和空關系 ?, 小于等于關系, 小于關系, 整除關系, 包含關系, 真包含關系,R1 和 R3 是A上的傳遞關系, R2不是A上的傳遞關系.,41,關系性質(zhì)的充要條件,設 R 為 A 上的關系, 則 (1) R 在 A 上自反當且僅當 IA ?R (2) R 在 A 上反自反當且僅當 R∩IA=? (3) R 在

34、 A 上對稱當且僅當 R=R?1 (4) R 在 A 上反對稱當且僅當 R∩R?1?IA (5) R 在 A 上傳遞當且僅當 R°R?R,42,自反性證明,證明模式 證明 R 在 A 上自反 任取 x, x?A ? ……… ………..…. ……. ? ?R 前提 推理過程 結(jié)論,例

35、4 證明若 IA ?R ，則 R 在 A 上自反. 證 任取x, x?A ? ?IA ? ?R 因此 R 在 A 上是自反的.,43,對稱性證明,,證明模式 證明 R 在 A 上對稱 任取 ?R ?…… ………..…. ……. ? ?R 前提 推理過程 結(jié)論,例5

36、 證明若 R=R?1 , 則 R 在A上對稱. 證 任取 ?R ? ?R ?1 ? ?R 因此 R 在 A 上是對稱的.,44,反對稱性證明,,證明模式 證明 R 在 A 上反對稱 任取 ?R??R ? ………..………. ? x=y 前提 推理過程 結(jié)論,例6 證明若 R∩R?1?I

37、A , 則 R 在 A 上反對稱. 證 任取 ?R ??R ? ?R ??R ?1 ? ?R∩R ?1 ? ?IA ? x=y 因此 R 在 A 上是反對稱的.,45,傳遞性證明,,證明模式 證明 R 在 A上傳遞 任取， ?R??R ?…..………. ? ?R 前提 推理過程

38、 結(jié)論,例7 證明若 R°R?R , 則 R 在 A 上傳遞. 證 任取， ?R ??R ? ?R°R ? ?R 因此 R 在 A 上是傳遞的.,46,關系性質(zhì)判別,47,實例,例8 判斷下圖中關系的性質(zhì), 并說明理由,(3) 自反，不是反自反；反對稱，不是對稱；不傳遞.,(1) 不是自反也不是反自反；對稱, 不是反對稱；不傳遞.,(2) 反自反, 不是自反；反對稱, 不是對稱；傳

39、遞.,48,運算與性質(zhì)的關系,49,閉包定義,定義4.17 設R是非空集合A上的關系, R 的自反 (對稱或傳遞) 閉包 是A上的關系R?, 使得 R ?滿足以下條件： (1) R ?是自反的（對稱的或傳遞的） (2) R ?R ? (3) 對A上任何包含R 的自反（對稱或傳遞）關系R ?? 有 R ??R ??. 一般將 R 的自反閉包記作 r(R), 對稱閉包記作 s(R), 傳遞閉包記作 t(R)

40、.,50,閉包的構造方法,,集合表示定理4.7 設R為A上的關系, 則有 (1) r(R)=R∪R0 (2) s(R)=R∪R?1 (3) t(R)=R∪R2∪R3∪…說明：對于有窮集合A (|A|=n) 上的關系, (3)中的并最多不超過Rn. 若R 是自反的，則 r(R)=R; 若 R 是對稱的，則 s(R)=R;若R 是傳遞的，則 t(R)=R.,51,定理4.7的證明,只證 (1) 和 (

41、3) 證 r(R)=R∪R0 只需證明R∪R0 滿足閉包定義. R∪R0包含了R 由IA?R∪R0可知 R∪R0 在 A上是自反的. 下面證明R∪R0是包含R 的最小的自反關系. 假設R ?是包含R 的自反關系，那么IA?R ?, R?R ?，因此有 R∪R0=IA?R ?R ?,52,任取和 ?R∪R2∪R3∪…. ? ?R∪R2∪R3∪…. ? ?R∪R2∪R3∪….于是，由R∪R2∪R

42、3∪….的傳遞性得 t(R) ?R∪R2∪R3∪… 對n 進行歸納證明 Rn ?t(R).n=1時顯然為真. 假設n=k時為真，那么對于任意?Rk+1? ?Rk°R ??t (?Rk ??R) ??t (?t(R)??t(R)) ??t(R) （t(R)傳遞） 于是， R∪R2∪R3∪… ? t(R),定理4.7的證明（續(xù)）,53,矩陣表示設關系R, r(R), s(R), t(R)的

43、關系矩陣分別為M, Mr, Ms 和 Mt , 則  Mr =M + E Ms =M + M ’ Mt =M + M2 + M3 + …其中E 是和 M 同階的單位矩陣, M ’是 M 的轉(zhuǎn)置矩陣. 注意：在上述等式中矩陣的元素相加時使用邏輯加. ,閉包的構造方法（續(xù)）,54,圖表示設關系R, r(R), s(R), t(R)的關系圖分別記為G, Gr

44、, Gs, Gt , 則Gr, Gs, Gt 的頂點集與G 的頂點集相等. 除了G 的邊以外, 以下述方法添加新的邊： 考察G 的每個頂點, 如果沒有環(huán)就加上一個環(huán). 最終得到的是Gr. 考察G 的每一條邊, 如果有一條 xi 到 xj 的單向邊, i≠j, 則在G中加一條 xj 到 xi 的反方向邊. 最終得到Gs. 考察G 的每個頂點 xi, 找從 xi 出發(fā)的每一條路徑，如果從 xi 到路徑中的任何結(jié)點 xj 沒有邊，就加

45、上這條邊. 當檢查完所有的頂點后就得到圖Gt .,閉包的構造方法（續(xù)）,55,實例,例1 設A={a,b,c,d}, R={,,,,},R和 r(R), s(R), t(R)的關系圖如下圖所示.,R,r(R),s(R),t(R),56,傳遞閉包的計算——Warshall算法,算法思路：考慮 n+1個矩陣的序列M0, M1, …, Mn , 將矩陣 Mk 的 i 行 j 列的元素記作Mk[i,j]. 對于k=0,1,…,n, Mk[

46、i,j]=1當且僅當在R 的關系圖中存在一條從 xi 到 xj 的路徑，并且這條路徑除端點外中間只經(jīng)過{x1, x2, …, xk}中的頂點. 不難證明M0就是R 的關系矩陣，而 Mn 就對應了R 的傳遞閉包. Warshall算法：從M0開始，順序計算 M1, M2, …, 直到 Mn 為止.,,57,Warshall算法的依據(jù),從 Mk [i, j] 計算 Mk+1[i, j]: i, j?V. 頂點集 V1={1,

47、2, …, k}, V2={k+2, …,n},V=V1?{k+1}?V2，Mk+1[i,j]=1? 存在從i 到 j 中間只經(jīng)過V1?{k+1}中點的路徑這些路徑分為兩類：第1類：只經(jīng)過 V1中點第2類：經(jīng)過 k+1點存在第1類路徑：Mk[i,j]=1存在第2類路徑： Mk[i,k+1]=1?Mk[k+1,j]=1,58,Warshall算法及其效率,算法4.1 Warshall算法 輸入：M （R 的關系矩陣）

48、輸出：Mt （t(R)的關系矩陣） 1. Mt?M2. for k?1 to n do3. for i?1 to n do4. for j?1 to n do5. Mt[i, j] ?Mt[i, j] + Mt[i, k]?Mt[k, j],時間復雜度 T(n)=O(n3),59,4.4 等價關系與偏序關系,4.4.1 等價關系4.4.2 等價類和商集4.4.3 集

49、合的劃分4.4.4 偏序關系4.4.5 偏序集與哈斯圖,60,等價關系的定義與實例,定義4.18 設R為非空集合上的關系. 如果R是自反的、對稱的和傳遞的, 則稱R為A上的等價關系. 設 R 是一個等價關系, 若∈R, 稱 x等價于y, 記做x～y. 例1 設 A={1, 2, …, 8}, 如下定義 A上的關系R： R={| x,y∈A ∧ x≡y (mod 3)}其中 x≡y (mod 3) 叫做

50、 x與y 模3相等, 即 x 除以3的余數(shù)與 y 除以3的余數(shù)相等. 不難驗證R為A上的等價關系, 因為 ?x∈A, 有x≡x(mod 3) ?x,y∈A, 若x≡y(mod 3), 則有y≡x(mod 3) ?x,y,z∈A, 若x≡y(mod 3), y≡z(mod 3), 則有 x≡z(mod 3),61,模3等價關系的關系圖,,,設 A=

51、{1, 2, …, 8}, R={ | x,y∈A ∧ x≡y (mod 3) }R 的關系圖如下：,62,等價類,定義4.19 設R為非空集合A上的等價關系, ?x∈A，令 [x]R = { y | y∈A ∧ xRy }稱 [x]R 為x關于R 的等價類, 簡稱為 x 的等價類, 簡記為[x]. 實例 A={ 1, 2, … , 8 }上模 3 等價關系的等價類： [1]=[4]=[7]

52、={1,4,7} [2]=[5]=[8]={2,5,8} [3]=[6]={3,6},63,等價類的性質(zhì),,定理4.8 設R是非空集合A上的等價關系, 則 (1) ?x∈A, [x] 是A的非空子集. (2) ?x, y∈A, 如果 xRy, 則 [x]=[y]. (3) ?x, y∈A, 如果 x y, 則 [x]與[y]不交. (4) ，即所有等價類

53、的并集就是A. ,64,性質(zhì)的證明,(1)由等價類定義可知, ?x∈A有[x]?A. 由自反性有xRx，因此x∈[x], 即[x]非空. (2)任取z, 則有z∈[x] ? ∈R ? ∈R∈R ∧ ∈R ? ∈R ? ∈R 從而證明了z∈[y]. 綜上所述必有[x]?[y]. 同理可證[y] ? [x]. 這就得到了[x]=[y].(3) 假設[x]∩[y]≠?, 則存在z

54、∈[x]∩[y], 從而有 z∈[x] ∧ z∈[y], 即∈R ∧ ∈R 成立. 根據(jù)R 的對稱性和傳遞性必有∈R, 與x y矛盾,65,性質(zhì)的證明（續(xù)）,,,,,,,,(4) 先證 . 任取y,  y∈ ? ?x (x∈A ∧ y∈[x]) ? y∈[x] ∧ [x]?A ? y∈A 從而有

55、 .再證A? . 任取y, y∈A ? y∈[y] ∧ y∈A ?y∈從而有A? 成立. 綜上所述得,66,商集,定義4.20 設R 為非空集合A 上的等價關系, 以R 的所有等價類作為元素的集合稱為A關于R 的商集, 記做 A/R, A/R = { [x]R | x∈A }例2令A={1, 2, …, 8}，A關于模 3 等價關

56、系R 的商集為 A/R = { {1, 4,7}, {2, 5, 8}, {3, 6} } A關于恒等關系和全域關系的商集為： A/IA = { {1},{2}, … ,{8}} A/EA = { {1, 2, … ,8} },67,集合的劃分,定義4.21 設A為非空集合, 若A的子集族? (? ?P(A)) 滿足下面條件： (1) ??? (2) ?x?y (x,y∈?∧x≠y

57、→x∩y=?) (3) ∪? =A 則稱?是A的一個劃分, 稱? 中的元素為A的劃分塊.例3 設A＝{a, b, c, d}, 給定? 1, ? 2, ? 3, ? 4, ? 5, ? 6如下： ? 1={{a, b, c},r6160xu}， ? 2={{a, b},{c},r150ga0} ? 3={{a},{a, b, c, d}}， ? 4={{a, b},{c}} ? 5={?,{a, b},{c, d}}

58、， ? 6={{a,{a}},{b, c, d}} 則? 1和? 2是A的劃分, 其他都不是A的劃分.,68,等價關系與劃分的一一對應,,商集 A/R 就是A 的一個劃分 不同的商集對應于不同的劃分 任給A 的一個劃分? , 如下定義A 上的關系 R：R ={ | x, y∈A ∧ x 與 y 在?的同一劃分塊中 }則R 為A上的等價關系, 且該等價關系確定的商集就是?.,例4 給出A＝{1,2,3}上所有的等價關系求

59、解思路：先做出A的所有劃分, 然后根據(jù)劃分寫出 對應的等價關系.,69,例 4,? 1, ? 2和? 3分別對應于等價關系 R1, R2和R3. 其中 R1={,}∪IA  R2={,}∪IA R3={,}∪IA,A上的等價關系與劃分之間的對應：? 4對應于全域關系EA? 5對應于恒等關系IA,70,實例,根據(jù)有序?qū)Φ?x+y=2,3,4,5,6,7,8 將A?A劃分.

60、 (A?A)/R={{}, {,}, {, , }, {, , , }, {, , }, {, }, {}},例5 設A={1,2,3,4}，在A?A上定義二元關系 R： ,>?R ? x+y = u+v，求R 導出的劃分.,解 A?A={, , , , , , , ,, , , , , , , },71,偏序關系,定義4.22 非空集

61、合A上的自反、反對稱和傳遞的關系，稱為A上的偏序關系，記作?. 設?為偏序關系, 如果∈?, 則記作 x?y, 讀作 x“小于或等于”y. 實例 集合A上的恒等關系 IA 是A上的偏序關系. 小于或等于關系, 整除關系和包含關系也是相應集合上的偏序關系.,72,相關概念,定義4.23 x與y可比 設R為非空集合A上的偏序關系,  x, y?A, x與y 可比 ? x?y ∨ y?x.

62、結(jié)論：?x, y?A，下述幾種情況發(fā)生其一且僅發(fā)生其一. x?y, y?x, x＝y(tǒng), x與y不可比定義4.24 擬序 R為非空集合A上的關系,如果R是反自反和傳遞的，則稱R是A上的擬序關系，簡稱為擬序，記作?. 定義4.25 全序 R為非空集合A上的偏序, ?x, y?A, x與y 都可比，則稱R為全序. 定義4.26 覆蓋 x,y∈A, 如果x?y且不存在 z?A使得 x?z?y, 則稱 y覆蓋x.

63、實例：數(shù)集上的小于或等于關系是全序關系 整除關系不是正整數(shù)集合上的全序關系 {1, 2, 4, 6}集合上的整除關系, 2覆蓋1, 4 和 6 覆蓋2. 但4不覆蓋1.,73,偏序集與哈斯圖,定義4.27 集合A和A上的偏序關系?一起叫做偏序集, 記作.實例：整數(shù)集和數(shù)的小于等于關系構成偏序集 冪集P(A)和包含關系構成偏序集. 哈斯圖：利用偏序自反、反對稱、傳遞性簡化的關系圖特點：

64、 每個結(jié)點沒有環(huán) 兩個連通的結(jié)點之間的序關系通過結(jié)點位置的高低 表示，位置低的元素的順序在前 具有覆蓋關系的兩個結(jié)點之間連邊,74,哈斯圖實例,例6 ,75,例7 已知偏序集的哈斯圖如下圖所示, 試求出集合A和關系R的表達式.,哈斯圖實例（續(xù)）,A={a, b, c, d, e, f, g, h} R={,,,,,,,, }

65、∪IA,76,偏序集的特定元素,定義4.28 設為偏序集, B?A, y∈B. (1) 若?x(x∈B→y?x)成立, 則稱 y 為 B 的最小元. (2) 若?x(x∈B→x?y)成立, 則稱 y 為 B 的最大元. (3) 若?x(x∈B∧x?y→x=y)成立, 則稱 y 為B的極小元. (4) 若?x(x∈B∧y?x→x=y)成立, 則稱 y 為B的極大元. 性質(zhì)：對于有窮集，極小元和極大元必存在，可能存在

66、多個. 最小元和最大元不一定存在，如果存在一定惟一.最小元一定是極小元；最大元一定是極大元. 孤立結(jié)點既是極小元，也是極大元.,77,定義4.29 設為偏序集, B?A, y?A. （1） 若?x (x∈B→x?y) 成立, 則稱 y 為B 的上界. （2） 若?x (x∈B→y?x) 成立, 則稱 y 為B 的下界. （3） 令C＝{y | y為B的上界}, 則稱C的最小元為B 的最小上界 或上確界.

67、（4） 令D＝{y | y為B的下界}, 則稱D的最大元為B 的最大下界 或下確界.性質(zhì)： 下界、上界、下確界、上確界不一定存在 下界、上界存在不一定惟一 下確界、上確界如果存在，則惟一 集合B的最小元就是它的下確界，最大元就是它的上確界；反之不對.,偏序集的特定元素(續(xù)),78,實例,例8 設偏序集如下圖所示，求A 的極小元、最小元、極大元、最大元. 設B＝{ b, c, d }, 求B 的下界

68、、上界、下確界、上確界.,解：極小元：a, b, c, g；極大元：a, f, h；沒有最小元與最大元.B的下界和最大下界都不存在, 上界有d 和 f, 最小上界為 d.,79,偏序集的特殊子集,定義4.30 設為偏序集, B?A. (1) 如果?x,y?B，x與y都是可比的，則稱B是A中的一條鏈，B中的元素個數(shù)稱為鏈的長度； (2) 如果?x,y?B，x?y，x與y都是不可比的，則稱B是A中的一條反鏈，B中的元