《北大離散數學》PPT課件.ppt
《《北大離散數學》PPT課件.ppt》由會員分享,可在線閱讀,更多相關《《北大離散數學》PPT課件.ppt(63頁珍藏版)》請在裝配圖網上搜索。
1、2020/10/17 集合論與圖論第 8講 1 第 8講 等價關系與序關系 內容提要 等價關系 ,等價類 ,商集 劃分 , 第二類 Stirling數 偏序 ,線序 ,擬序 ,良序 哈斯圖 特殊元素 : 最 ?元 ,極 ?元 ,?界 ,?確界 (反 )鏈 2020/10/17 集合論與圖論第 8講 2 等價 (equivalence)關系 定義 同余關系 等價類 商集 劃分 劃分的加細 Stirling子集數 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數 (Bell number) 問題 : 給 n個對象分類 , 共有多少種分法 ? 答案 : Bell數 Bn= (Eric Temple Bell
12、, 18831960) Stirling子集數 (Stirling subset number) : 把 n個對象分成 k個非空子集的分法個數 . 遞推公式 : .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子集數 遞推公式 : .111 k n k nk k n 剔除一個 其余分 k類 加入一類 其余分 k-1類 自成一類
13、 2020/10/17 集合論與圖論第 8講 23 第一、二類 Stirling數 第一類 Stirling數 (Stirling number of the first kind): s(n,k) 第二類 Stirling數 (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數表 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數表 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均有最小元 , 則稱 為良序 關系 , 為良序集 例 :
- 溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 裝配圖網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 數學人教版六上《圓的周長》課件
- 【魯科版】微項目-科學使用含氯消毒劑課件
- 七年級美術上冊第四單元我們的“動漫天地”第8課幽默智慧的漫畫ppt課件5嶺南版
- 三年級上冊古詩三首贈劉景文部編版課件
- 七年級英語上冊Unit7Reading牛津深圳版ppt課件新版
- 建立以勝任力模型為核心的戰(zhàn)略性人力資源管理課件
- 《窗邊的小豆豆》讀書分享課件
- 急性缺血性卒中靜脈溶栓治療課件
- 《我一生中的重要抉擇》PPt課件
- 七年級下冊英語(人教新目標版)Unit7-Section-A(GrammarFocus-3b)公開課課件
- 【人教版】(新起點)英語五上:Unit-5《TV-Shows》(Lesson-1)ppt課件
- 人教版選修八-unit1-A-land-of-diversity-句型講解和練習課件
- 高中英語Unit3TheworldonlineSectionLanguagePointsppt課件牛津譯林版選修
- 二年級上冊語文復習資料PPT教案課件
- 日歷中的數學規(guī)律課件