《《北大離散數(shù)學》PPT課件.ppt》由會員分享，可在線閱讀，更多相關《《北大離散數(shù)學》PPT課件.ppt（63頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、2020/10/17 集合論與圖論第 8講 1 第 8講 等價關系與序關系 內容提要 等價關系 ,等價類 ,商集 劃分 , 第二類 Stirling數(shù) 偏序 ,線序 ,擬序 ,良序 哈斯圖 特殊元素 : 最 ?元 ,極 ?元 ,?界 ,?確界 (反 )鏈 2020/10/17 集合論與圖論第 8講 2 等價 (equivalence)關系 定義 同余關系 等價類 商集 劃分 劃分的加細 Stirling子集數(shù) 2020/10/17 集合論與圖論第 8講 3 等價 (equivalence)關系定義 等價關系 : 設 RAA 且 A, 若 R是 自 反的 , 對

2、稱的 , 傳遞的 ,則稱 R為等價關系 例 9: 判斷是否等價關系 (A是某班學生 ): R1=|x,yAx與 y同年生 R2=|x,yAx與 y同姓 R3=|x,yAx的年齡不比 y小 R4=|x,yAx與 y選修同門課程 R5=|x,yAx的體重比 y重 2020/10/17 集合論與圖論第 8講 4 例 9(續(xù) ) 定義 自反 對稱 傳遞 等價關系 R1 x與 y同年生 R2 x與 y同姓 R3 x的年齡不比 y小 R4 x與 y選修同 門課程 R5 x的體重比 y 重 2020/10/17 集合論與圖論第 8講 5 例 10

3、 例 10: 設 RAA 且 A, 對 R依次求三 種閉包共有 6種不同順序 , 其中哪些順序 一定導致等價關系 ? rst( R ), rts( R ), str( R ), srt( R ), trs( R ), tsr( R )=t(s(r( R ))) 解 : st( R )ts( R ), sr( R )=rs( R ), tsr( R )=trs( R )=rts( R ) str( R )=srt( R )=rst( R ) 2020/10/17 集合論與圖論第 8講 6 例 10(續(xù) ) tsr(R)=trs(R) =rts( R ) str(R)

4、=srt(R) =rst( R ) 自反 對稱 傳遞 等價關系 (等價閉包 ) 2020/10/17 集合論與圖論第 8講 7 等價類 (equivalence class) 等價類 : 設 R是 A上等價關系 ,xA,令 xR= y | yA xRy , 稱 xR為 x關于 R的等價類 , 簡稱 x的等價類 , 簡記為 x. 等價類 性質 : xR ; xRy xR=yR ; xRy xRyR= ; U xR | xA =A. 2020/10/17 集合論與圖論第 8講 8 定理 27 定理 27:設 R是 A上等價關系 ,x,yA, (1) xR (2)

5、xRy xR=yR ; (3) xRy xRyR= ; (4) U xR | xA =A. 證明 : (1) R自反 xRxxxRxR. x 2020/10/17 集合論與圖論第 8講 9 定理 27(證明 (2)) (2) xRy xR=yR ; 證明 : (2) 只需證明 xRyR和 xRyR. () z, zxRxRy zRxxRy zRy zyR . xRyR. () 同理可證 . x y z 2020/10/17 集合論與圖論第 8講 10 定理 27(證明 (3)) (3) xRy xRyR= ; 證明 : (3) (反證 ) 假設 z, zxR

6、yR, 則 zxRyR zRxzRy xRzzRy xRy, 這與 xRy矛盾 ! xRyR=. x y z 2020/10/17 集合論與圖論第 8講 11 定理 27(證明 (4)) (4) U xR | xA = A. 證明 : (4) A=U x | xA U xR | xA U A | xA =A. U xR | xA = A. # x y 2020/10/17 集合論與圖論第 8講 12 同余 關系 : 設 n2,3,4,, x,y Z,則 x與 y模 n同余 (be congruent modulo n) xy(mo

7、d n) n|(x-y) x-y=kn (kZ) 同余關系是等價關系 0 = kn|kZ, 1 = 1+kn|kZ, 2 = 2+kn|kZ,, n-1=(n-1)+kn|kZ. 同余 (congruence)關系 6 3 9 8 7 5 4 2 1 10 11 0 2020/10/17 集合論與圖論第 8講 13 例 11 例 11: 設 A=1,2,3,4,5,8, 求 R3 = | x,yA xy(mod 3) 的等價類 , 畫出 R3的關系圖 . 解 : 1=4=1,4, 2=5=8=2,5,8, 3=3. # 1 4 2

8、 5 8 3 2020/10/17 集合論與圖論第 8講 14 商集 (quotient set) 商集 : 設 R是 A上等價關系 , A/R = xR | xA 稱為 A關于 R的商集 , 簡稱 A的商集 . 顯然 U A/R = A. 例 11(續(xù) ): A/R3 = 1,4, 2,5,8, 3 . 2020/10/17 集合論與圖論第 8講 15 例 12(1) 例 12(1): 設 A=a1,a2,,a n, IA, EA, Rij=IA, 都是 A上等價關系 , 求對應的商集 , 其中 ai,ajA, ij. 是 A上等價關系嗎 ? 解 : A/IA= a1, a2,, a

9、 n A/EA= a1,a2,,a n A/Rij= A/IAai,aj - ai,aj. 不是 A上等價關系 (非自反 ). # 2020/10/17 集合論與圖論第 8講 16 劃分 (partition) 劃分 : 設 A, AP(A),若 A滿足 (1) A ; (2) x,y( x,yA xy xy= ) (3) UA = A 則稱 A為 A的一個劃分 , A中元素稱為 劃分 塊 (block). 2020/10/17 集合論與圖論第 8講 17 劃分 (舉例 ) 設 A1,A2,,A nE, 則以下都是劃分 : Ai = Ai,Ai,

10、 ( i=1,2,,n ) Aij = AiAj,AiAj, AiAj, AiAj- ( i,j =1,2,,n ij ) A12n = A1A2 An,, A1A2 An-1An, A1A2 An-. # 2020/10/17 集合論與圖論第 8講 18 劃分 (舉例 ,續(xù) ) Ai Ai 2020/10/17 集合論與圖論第 8講 19 等價關系與劃分是一一對應的 定理 28: 設 A, 則 (1) R是 A上等價關系 A/R是 A的劃分 (2) A是 A的劃分 RA是 A上等價關系 ,其中 xRAy z(zA xz

11、yz) RA稱為由劃分 A 所定義的等價關系 (同塊關系 ). # 2020/10/17 集合論與圖論第 8講 20 例 12(2) 例 12(2): A=a,b,c, 求 A上全體等價關系 . 解 : A上不同劃分共有 5種 : a b c a b c a b c a b c a b c R1= EA, R2=IA, R3=IA, R4=IA, R5=IA. # 2020/10/17 集合論與圖論第 8講 21 Bell數(shù) (Bell number) 問題 : 給 n個對象分類 , 共有多少種分法 ? 答案 : Bell數(shù) Bn= (Eric Temple Bell

12、, 18831960) Stirling子集數(shù) (Stirling subset number) : 把 n個對象分成 k個非空子集的分法個數(shù) . 遞推公式 : .21 1 n nnn k nn k k n .1,1,122,11,00 21 n nC n nnnn n n .111 knknkkn 2020/10/17 集合論與圖論第 8講 22 Stirling子集數(shù) 遞推公式 : .111 k n k nk k n 剔除一個 其余分 k類 加入一類 其余分 k-1類 自成一類

13、 2020/10/17 集合論與圖論第 8講 23 第一、二類 Stirling數(shù) 第一類 Stirling數(shù) (Stirling number of the first kind): s(n,k) 第二類 Stirling數(shù) (Stirling number of the second kind): S(n,k)= k n .)1()2)(1(),( 0 kk n k xkxxxxxkns .),()1()2)(1(),( 00 k n k n k n xknSkxxxxknSx 2020/10/17 集合論與圖論第 8講 24 Bell數(shù)表 n Bn

14、n Bn 1 1 8 4,140 2 2 9 21,147 3 5 10 115,975 4 15 11 678,570 5 52 12 4,213,597 6 203 13 27,644,437 7 877 14 190,899,322 2020/10/17 集合論與圖論第 8講 25 第二類 Stirling數(shù)表 nk 0 1 2 3 4 5 6 7 8 9 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966

15、 1,170 1,050 266 28 1 9 0 1 255 3,035 7,770 6,951 2,646 462 36 1 10 0 1 511 9,330 34,501 42,525 22,827 5,880 750 45 2020/10/17 集合論與圖論第 8講 26 例 13 例 13: 問 A=a,b,c,d上有多少種等價關系 ? 解 : # .1516711)12(14 4 3 4 2 4 1 4 2 4 3 4 CB 2020/10/17 集合論與圖論第 8講

16、 27 劃分的加細 (refinement) 劃分的 加細 : 設 A和 B都是集合 A的劃分 , 若 A的每個劃分塊都包含于 B的某個劃分 塊中 , 則稱 A為 B的加細 . A為 B的加細 RARB 2020/10/17 集合論與圖論第 8講 28 例 14 例 14: 考慮 A=a,b,c上的劃分之間的加細 . 解 : a b c a b c a b c a b c a b c 加細 加細 加細 加細 加細 加細 # 2020/10/17 集合論與圖論第 8講 29 序關系 偏序 ,線序 ,擬序 ,良序 哈斯圖 特殊元素 : 最 ?元 , 極 ?元 , ?界 ,

17、?確界 (反 )鏈 2020/10/17 集合論與圖論第 8講 30 偏序 (partial order)關系 偏序關系 : 設 RAA 且 A, 若 R是 自 反的 , 反對稱的 , 傳遞的 , 則稱 R為偏序關 系 通常用 表示偏序關系 ,讀作“ 小于等于 ” R xRy xy “嚴格小于 ”: xy xy xy 偏序集 (poset): , 是 A上偏序關系 例子 : , , , 2020/10/17 集合論與圖論第 8講 31 偏序集 , , AR = | x,yA xy , = | x,yA xy , AZ+= x | xZ x0 | =

18、 | x,yA x|y 2020/10/17 集合論與圖論第 8講 32 偏序集 AP(A), = | x,yA xy 設 A=a,b, A1=,a,b, A2=a,a,b, A3=P(A)=,a,b,a,b,則 1 = IA1 , 2 = IA2 3 = IA3 ,, , , 2020/10/17 集合論與圖論第 8講 33 偏序集 A, 是由 A的一些劃分組成的集合 加細 = | x,y x是 y的 加細 設 A=a,b,c, A1=a,b,c,A2=a,b,c, A3=b,a,c,A4=c,a,b,A5=a,b,c 取 1=A1,A2,2

19、=A2,A3,3=A1,A2,A3,A4,A5 1 = I1 , 2 = I2, 3 = I3 ,, , ,,,. # 2020/10/17 集合論與圖論第 8講 34 哈斯圖 (Hasse diagram) 設 是偏序集 , x,yA 可比 (comparable): x與 y可比 xy yx 覆蓋 (cover): y覆蓋 x xy z( zA xzy ) 哈斯圖 : 當且僅當 y覆蓋 x時 ,在 x與 y之間 畫 無向邊 , 并且 x畫在 y下方 2020/10/17 集合論與圖論第 8講 35 例 16(1)(2) 例 16: 畫出下列偏序關系的哈斯圖 . (1)

20、 , A=1,2,3,4,5,6,9,10,15 (2) , A=a,b,c, AP(A), A=,a,b,c,a,b,b,c,a,c 解 : 1 2 4 3 6 9 15 5 10 a b c a,b a,c b,c 2020/10/17 集合論與圖論第 8講 36 例 16(3) 例 16: 畫出下列偏序關系的哈斯圖 . (3) , =A1,A2,A3,A4,A5,A6, A=a,b,c,d A1 = a, b, c, d , A2 = a,b, c,d , A3 = a,c, b,d , A4 = a, b,c,d , A5 = a, b, c,d ,

21、A6 = a,b,c,d 解 : A1 A2 A5 A3 A4 A6 # 2020/10/17 集合論與圖論第 8講 37 偏序關系中的特殊元素 最大元 , 最小元 極大元 , 極小元 上界 , 下界 最小上界 (上確界 ), 最大下界 (下確界 ) 2020/10/17 集合論與圖論第 8講 38 最大元 , 最小元 設 為偏序集 , BA, yB 最大元 (maximum/greatest element): y是 B的最大元 x( xB xy ) 最小元 (minimum/least element): y是 B的最小元 x( xB yx ) 2020/1

22、0/17 集合論與圖論第 8講 39 最大元 , 最小元舉例 (例 16(1)) 例 16(1): , A=1,2,3,4,5,6,9,10,15 B1=1,2,3, B2=3,5,15, B3=A. B1的最大元是 , B1的最小元是 1 B2的最大元是 15, B2的最小元是 B3的最大元是 , B3的最小元是 1 1 2 4 3 6 9 15 5 10 1 2 4 3 6 9 15 5 10 2020/10/17 集合論與圖論第 8講 40 極大元 ,極小元 設 為偏序集 , BA, yB 極大元 (maximal element): y是 B的

23、極大元 x( xB yx x=y ) 極小元 (minimal element): y是 B的極小元 x( xB xy x=y ) 2020/10/17 集合論與圖論第 8講 41 極大元 ,極小元舉例 (例 16(1)) 例 16(1): , A=1,2,3,4,5,6,9,10,15 B1=1,2,3, B2=3,5,15, B3=A. B1的極大元是 2,3, B1的極小元是 1 B2的極大元是 15, B2的極小元是 3,5 B3的極大元是 4,6,9,15,10, B3的極小元是 1 1 2 4 3 6 9 15 5 10 1

24、2 4 3 6 9 15 5 10 2020/10/17 集合論與圖論第 8講 42 上界 , 下界 設 為偏序集 , BA, yA 上界 (upper bound): y是 B的上界 x( xB xy ) 下界 (lower bound): y是 B的下界 x( xB yx ) 2020/10/17 集合論與圖論第 8講 43 上界 , 下界舉例 (例 16(1)) 例 16(1): , A=1,2,3,4,5,6,9,10,15 B1=1,2,3, B2=3,5,15, B3=A. B1的上界是 6, B1的下界是 1 B2的上界是 15, B

25、2的下界是 1 B3的上界是 , B3的下界是 1 1 2 4 3 6 9 15 5 10 1 2 4 3 6 9 15 5 10 2020/10/17 集合論與圖論第 8講 44 最小上界 , 最大下界 設 為偏序集 , BA 最小上界 (least upper bound): 設 C = y | y是 B的 上 界 , C的最 小 元稱 為 B的 最小上界 , 或 上確界 . 最大下界 (greatest lower bound): 設 C = y | y是 B的 下 界 , C的最 大 元稱 為 B的 最大下界 , 或 下確界 . 2020/10/17 集合論

26、與圖論第 8講 45 最小上界 ,最大下界舉例 (例 16(1)) 例 16(1): , A=1,2,3,4,5,6,9,10,15 B1=1,2,3, B2=3,5,15, B3=A. B1的最小上界是 6, B1的最大下界是 1 B2的最小上界是 15, B2的最大下界是 1 B3的最小上界是 , B3的最大下界是 1 1 2 4 3 6 9 15 5 10 1 2 4 3 6 9 15 5 10 2020/10/17 集合論與圖論第 8講 46 特殊元素比較 存在 (B非空有窮 ) 存在 (B無窮 ) 唯一 B 最大元 (表示 不一定 ) 最小元

27、 極大元 (表示 一定 ) ,B=Z 極小元 上界 下界 上確界 下確界 2020/10/17 集合論與圖論第 8講 47 鏈 (chain), 反鏈 (antichain) 設 為偏序集 , BA, 鏈 (chain): B是 A中的鏈 xy( xByB x與 y可比 ) |B|稱為鏈的 長度 反鏈 (antichain): B是 A中的反鏈 xy( xByBxy x與 y不可比 ) |B|稱為反鏈的 長度 2020/10/17 集合論與圖論第 8講 48 鏈 , 反鏈 (舉例 ) 設 偏序集 如圖所示 , A=a,b,,k.

28、 a b c d e f g h i j k B1=a,c,d,e是長為 4的 鏈 上界 e,f,g,h, 上確界 e 下界 a, 下確界 a B2=a,e,h是長為 3的鏈 B3=b,g是長為 2的鏈 B4=g,h,k是長為 3的 反鏈 上界 ,下界 ,上確界 ,下確界 : 無 B5=a是長為 1的鏈和反鏈 B6=a,b,g,h既非鏈 ,亦非反鏈 2020/10/17 集合論與圖論第 8講 49 定理 31 定理 31: 設 為 偏序集 , A中最長鏈的 長度為 n, 則 (1) A中存在極大元 (2) A存在 n個劃分塊的劃分 , 每個劃分

29、塊 都是反鏈 (即 A劃分成 n個互不相交的反鏈 ) 推論 : 設 為 偏序集 , 若 |A|=mn+1,則 A中要么存在長度為 m+1的反鏈 , 要么存 在長度為 n+1的鏈 . 2020/10/17 集合論與圖論第 8講 50 定理 31(舉例 ) a b c d e f g h i j k 最長鏈長度為 6, 如 B1=a,c,d,e,f,h, B2=a,c,d,e,f,g, A=a,b,,k可以劃分為 A 1= a,b,i, c,j, d, e, f, g,h,k , A 2= a,b, c,i, d,j, e,k, f, g,h |A|=11=25+1, A中既有長度為

30、 2+1=3的反鏈 , 也有長度為 5+1=6的鏈 2020/10/17 集合論與圖論第 8講 51 定理 31(證明 (1)) 定理 31: 設 為 偏序集 , A中最長鏈的 長度為 n, 則 (1) A中存在極大元 證明 : (1) 設 B是 A中長度為 n的最長鏈 , B 有極大元 (也是最大元 )y, 則 y也是 A的極 大元 , 否則 A中還有比 y“大 ”的元素 z, B就 不是最長鏈 . 2020/10/17 集合論與圖論第 8講 52 定理 31(證明 (2)) 定理 31: 設 為 偏序集 , A中最長鏈的 長度為 n, 則 (2) A存在 n個劃分塊的劃分 , 每個

31、劃分塊都是反鏈 (即 A劃分成 n個互不 相交的反鏈 ) 證明 : (2) A1 = x | x是 A中的極大元 , A2 = x | x是 (A-A1)中的極大元 , An = x | x是 (A-A1- -An-1)中的極大元 , 則 A = A1, A2,, A n 是滿足要求的劃分 . 2020/10/17 集合論與圖論第 8講 53 定理 31(證明 (2):舉例 ) a b c d e f g h i j k 最長鏈長度為 6, A1 = g, h, k , A2 = f, j , A3 = e, i , A4 = d , A5 = c ,

32、 A6 = a, b , A = a,b, c, d, e,i, f,j, g,h,k 2020/10/17 集合論與圖論第 8講 54 定理 31(證明 (2)續(xù) ) 證明 (續(xù) ): 1 A1 = x | x是 A中的極大元 , 極大 元互相之間不可比 , 所以 A1是反鏈 , 同理 A2,,A n都是反鏈 . 2 顯然 A1,A2,,A n互不相交 . 3 最長鏈上的元素分屬 A1,A2,,A n, 所以 A1,A2,,A n都非空 . 4 假設 zA-A1- -An,則最長鏈上的元素加上 z 就是長度為 n+1的鏈 , 矛盾 ! 所以 A=A1A2 An. 綜

33、上所述 , A= A1,A2,,A n 確是所求劃分 . # 2020/10/17 集合論與圖論第 8講 55 定理 31推論 (證明 ) 推論 : 設 為 偏序集 , 若 |A|=mn+1,則 A中要么存在長度為 m+1的反鏈 , 要么存 在長度為 n+1的鏈 . 證明 : (反證 )假設 A中既沒有長度為 m+1 的反鏈 , 也沒有長度為 n+1的鏈 , 則按照定 理 31(2)中要求來劃分 A, A至多劃分成 n塊 , 每塊至多 m個元素 , 于是 A中至多有 mn個 元素 , 這與 |A|=mn+1矛盾 ! # 2020/10/17 集合論與圖論第 8講 56 全序 (total o

34、rder)關系 全序關系 : 若 偏序集 滿足 xy( xAyA x與 y可比 ) 則稱 為全序關系 , 稱 為 全序集 全序關系亦稱 線序 (linear order)關系 例 : , 2020/10/17 集合論與圖論第 8講 57 擬序 (quasi-order)關系 擬序關系 : 設 RAA 且 A, 若 R是 反 自反的 , 傳遞的 , 則稱 R為擬序關系 通常用 表示擬序關系 (對比 :“嚴格小 于” ) 反自反性 與 傳遞性 蘊涵 反對稱性 擬序集 : , 是 A上擬序關系 例子 : 設 AR, BZ+

35、 2020/10/17 集合論與圖論第 8講 58 定理 29 定理 29:設 是非空集合 A上偏序關系 ,是 A上擬序關系 ,則 (1) 是反對稱的 ; (2) -IA是 A上擬序關系 ; (3) IA是 A上偏序關系 . 證明 : (1) xy yx xx , 矛盾 ! (2)(3) 顯然 . 2020/10/17 集合論與圖論第 8講 59 定理 30 定理 30:設 是非空集合 A上擬序關系 ,則 (1) xy,x=y,yx中至多有一式成立 ; (2) (xy x=y) (yx x=y) x=y. 證明 : (1) 兩式以上成立導致 xx

36、, 矛盾 ! (2) xy (xy ) (yx ), (由已知條件 ) 與 (1)矛盾 ! # 2020/10/17 集合論與圖論第 8講 60 三歧性 (trichotomy) 三歧性 : 設 是非空集合 A上擬序關系 , 若 xy,x=y,yx中有且僅有一式成立 ,則稱 具有 三歧性 . 擬全序關系 :設 是非空集合 A上擬序關系 , 若 具有 三歧性 , 則 稱 為擬全序關系 , 或 擬線序關系 ,稱 為 擬線序集 . 2020/10/17 集合論與圖論第 8講 61 良序 (well-order) 良序關系 : 設 為擬全序集 , 若 A的 任 何非空子集 B均有最小元 , 則稱 為良序 關系 , 為良序集 例 :