離散數(shù)學(xué)-課件-ch11匯編

1、 2 圖2 例例2 判斷下列偏序集是否構(gòu)成格，并說明理由判斷下列偏序集是否構(gòu)成格，并說明理由. (1) ，其中，其中P(B)是集合是集合B的冪集的冪集. (2) ，其中，其中Z是整數(shù)集，是整數(shù)集，為小于或等于關(guān)系為小于或等于關(guān)系. (3) 偏序集的哈斯圖分別在下圖給出偏序集的哈斯圖分別在下圖給出. 實例實例 (1) 冪集格冪集格. x,yP(B)，xy就是就是xy，xy就是就是xy. (2) 是格是格. x,yZ，xy = max(x,y)，xy = min(x,y)， (3) 都不是格都不是格. 可以找到兩個結(jié)點缺少最大下界或最小上界可以找到兩個結(jié)點缺少最大下界或最小上界 3 實例：子群格實

2、例：子群格 例例3 設(shè)設(shè)G是群，是群，L(G)是是G 的所有子群的集合的所有子群的集合. 即即 L(G) = H | HG ， 對任意的對任意的H1, H2L(G)，H1H2是是G 的子群，的子群，是由是由 H1H2生成的子群（即包含著生成的子群（即包含著H1H2的最小子群）的最小子群）. 在在L(G)上定義包含關(guān)系上定義包含關(guān)系 ，則，則L(G)關(guān)于包含關(guān)系構(gòu)成一個關(guān)于包含關(guān)系構(gòu)成一個 格，稱為格，稱為G的子群格的子群格. 在在 L(G)中，中， H1H2 就是就是 H1H2 H1H2 就是就是 4 格的性質(zhì)：對偶原理格的性質(zhì)：對偶原理 定義定義11.2 設(shè)設(shè) f 是含有格中元素以及符號是含

3、有格中元素以及符號 =, , ,和和的命的命 題題. 令令 f*是將是將 f 中的中的 替換成替換成 , 替換成替換成 ,替換成替換成,替換替換 成成 所得到的命題所得到的命題. 稱稱 f* 為為 f 的的對偶命題對偶命題. 例如例如, 在格中令在格中令 f 是是 (ab)c c, f*是是 (ab)c c . 格的格的對偶原理對偶原理 設(shè)設(shè) f 是含有格中元素以及符號是含有格中元素以及符號=, , ,和和等的命題等的命題. 若若 f 對對 一切格為真一切格為真, 則則 f 的對偶命題的對偶命題 f*也對一切格為真也對一切格為真. 例如例如, 如果對一切格如果對一切格L都有都有 a,bL, a

4、b a，那么對一切格那么對一切格 L 都有都有 a,bL, ab a l 注意：對偶是相互的，即注意：對偶是相互的，即 ( f*)*= f 5 格的性質(zhì)：算律格的性質(zhì)：算律 定理定理11.1 設(shè)設(shè)是格是格, 則運算則運算和和適合交換律、結(jié)合律、適合交換律、結(jié)合律、 冪等律和吸收律冪等律和吸收律, 即即 (1) a,bL 有有 ab = ba, ab = ba (2) a,b,cL 有有 (ab)c = a(bc), (ab)c = a(bc) (3) aL 有有 aa = a, aa = a (4) a,bL 有有 a(ab) = a, a(ab) = a 6 證明證明 (1) ab是是 a,

5、 b 的最小上界的最小上界, ba是是 b, a 的最小上界的最小上界. 由于由于 a, b = b, a , 所以所以 ab = ba. 由對偶原理由對偶原理, ab = ba. (2) 由最小上界的定義有由最小上界的定義有 (ab)c ab a (1) (ab)c ab b (2) (ab)c c (3) 由式由式(2)和和(3)有有 (ab)c bc (4) 由式由式(1)和和(4)有有 (ab)c a(bc) 同理可證同理可證 (ab)c a(bc) 根據(jù)反對稱性根據(jù)反對稱性 (ab)c = a(bc) 由對偶原理由對偶原理, (ab)c = a(bc) 7 證明證明 (3) 顯然顯然

6、 a aa, 又由又由 a a 可得可得 aa a. 根據(jù)反對稱性根據(jù)反對稱性 有有aa = a . 由對偶原理由對偶原理, aa = a 得證得證. (4) 顯然顯然 a(ab) a (5) 由由 a a, ab a 可得可得 a(ab) a (6) 由式由式(5)和和(6) 可得可得 a(ab) = a, 根據(jù)對偶原理根據(jù)對偶原理, a(ab) = a 8 格的性質(zhì)：序與運算的關(guān)系格的性質(zhì)：序與運算的關(guān)系 定理定理11.2 設(shè)設(shè)L是格是格, 則則 a,bL有有 a b ab = a ab = b 證證 (1) 先證先證 a b ab = a 由由 a a 和和 a b 可知可知 a 是是

7、a,b 的下界的下界, 故故 a ab. 顯然有顯然有ab a. 由反對稱性得由反對稱性得 ab = a. (2) 再證再證 ab = a ab = b 根據(jù)吸收律有根據(jù)吸收律有 b = b(ba) 由由 ab = a 和上面的等式得和上面的等式得 b = ba, 即即 ab = b. (3) 最后證最后證 ab = b a b 由由 a ab 得得 a ab = b 9 格的性質(zhì)：保序格的性質(zhì)：保序 定理定理11.3 設(shè)設(shè)L是格是格, a,b,c,dL，若若a b 且且 c d, 則則 ac bd, ac bd 例例4 設(shè)設(shè)L是格是格, 證明證明 a,b,cL有有 a(bc) (ab)(ac

8、). 證證 ac a b, ac c d 因此因此 ac bd. 同理可證同理可證 ac bd 證證 由由 a a, bc b 得得 a(bc) ab 由由 a a, bc c 得得 a(bc) ac 從而得到從而得到a(bc) (ab)(ac) 注意：一般說來注意：一般說來, 格中的格中的和和運算不滿足分配律運算不滿足分配律. 10 格作為代數(shù)系統(tǒng)的定義格作為代數(shù)系統(tǒng)的定義 定理定理11.4 設(shè)設(shè)是具有兩個二元運算的代數(shù)系統(tǒng)是具有兩個二元運算的代數(shù)系統(tǒng), 若對若對 于于 和和 運算適合交換律、結(jié)合律、吸收律運算適合交換律、結(jié)合律、吸收律, 則可以適當(dāng)定義則可以適當(dāng)定義S 中中 的偏序的偏序

9、,使得使得 構(gòu)成格構(gòu)成格, 且且 a,bS 有有 ab = a b, ab = a b. 證明省略證明省略. 根據(jù)定理根據(jù)定理11.4, 可以給出格的另一個等價定義可以給出格的另一個等價定義. 定義定義11.3 設(shè)設(shè)是代數(shù)系統(tǒng)是代數(shù)系統(tǒng), 和和 是二元運算是二元運算, 如如 果果 和和 滿足交換律、結(jié)合律和吸收律滿足交換律、結(jié)合律和吸收律, 則則構(gòu)成格構(gòu)成格. 11 子格及其判別法子格及其判別法 定義定義11.4 設(shè)設(shè)是格是格, S是是L的非空子集的非空子集, 若若S關(guān)于關(guān)于L中中 的運算的運算和和仍構(gòu)成格仍構(gòu)成格, 則稱則稱S是是L的的子格子格. 例例5 設(shè)格設(shè)格L如圖所示如圖所示. 令令

10、S1=a, e, f, g, S2=a, b, e, g S1不是不是L的子格的子格, 因為因為e, f S1 但但 ef = c S1. S2是是L的子格的子格. 12 11.2 分配格、有補格與布爾代數(shù)分配格、有補格與布爾代數(shù) 定義定義11.5 設(shè)設(shè)是格是格, 若若 a,b,cL,有有 a(bc) = (ab)(ac) a(bc) = (ab)(ac) 則稱則稱L為為分配格分配格. l 注意：可以證明以上兩個條件互為充分必要條件注意：可以證明以上兩個條件互為充分必要條件 L1 和和 L2 是分配格是分配格, L3 和和 L4不是分配格不是分配格. 稱稱 L3為為鉆石格鉆石格, L4為為五角

11、格五角格. 實例實例 13 分配格的判別及性質(zhì)分配格的判別及性質(zhì) 定理定理11.5 設(shè)設(shè)L是格是格, 則則L是分配格當(dāng)且僅當(dāng)是分配格當(dāng)且僅當(dāng)L不含有與鉆石格不含有與鉆石格 或五角格同構(gòu)的子格或五角格同構(gòu)的子格. 證明省略證明省略. 推論推論 (1) 小于五元的格都是分配格小于五元的格都是分配格. (2) 任何一條鏈都是分配格任何一條鏈都是分配格. 例例6 說明圖中的格是否為分配格說明圖中的格是否為分配格, 為什么？為什么？ 解解 都不是分配格都不是分配格. a,b,c,d,e 是是L1的子格的子格, 同構(gòu)于鉆石格同構(gòu)于鉆石格 a,b,c,e,f 是是L2的子格的子格, 同構(gòu)于五角格；同構(gòu)于五角

12、格； a,c,b,e,f 是是L3的子格的子格 同構(gòu)于鉆石格同構(gòu)于鉆石格. 14 有界格的定義有界格的定義 定義定義11.6 設(shè)設(shè)L是格是格, (1) 若存在若存在aL使得使得 xL有有 a x, 則稱則稱a為為L的的全下界全下界 (2) 若存在若存在bL使得使得 xL有有 x b, 則稱則稱b為為L的的全上界全上界 說明：說明： l 格格L若存在全下界或全上界若存在全下界或全上界, 一定是惟一的一定是惟一的. l 一般將格一般將格L的全下界記為的全下界記為0, 全上界記為全上界記為1. 定義定義11.7 設(shè)設(shè)L是格是格,若若L存在全下界和全上界存在全下界和全上界, 則稱則稱L 為為有界有界

13、格格, 一般將有界格一般將有界格L記為記為. 15 定理定理11.6 設(shè)設(shè)是有界格是有界格, 則則 aL有有 a0 = 0, a0 = a, a1 = a, a1 = 1 注意：注意： l 有限格有限格L=a1,a2,an是有界格是有界格, a1a2an是是L的全下的全下 界界, a1a2an是是L的全上界的全上界. l 0是關(guān)于是關(guān)于運算的零元運算的零元,運算的單位元；運算的單位元；1是關(guān)于是關(guān)于運算的運算的 零元零元,運算的單位元運算的單位元. l 對于涉及到有界格的命題對于涉及到有界格的命題, 如果其中含有全下界如果其中含有全下界0或全上界或全上界 1, 在求該命題的對偶命題時在求該命題

14、的對偶命題時, 必須將必須將0替換成替換成1, 而將而將1替換替換 成成0. 有界格的性質(zhì)有界格的性質(zhì) 16 有界格中的補元及實例有界格中的補元及實例 定義定義11.8 設(shè)設(shè)是有界格是有界格, aL, 若存在若存在bL 使得使得 ab = 0 和和 ab = 1 成立成立, 則稱則稱b是是a的的補元補元. l 注意：若注意：若b是是a的補元的補元, 那么那么a也是也是b的補元的補元. a和和b互為補元互為補元. 例例7 考慮下圖中的格考慮下圖中的格. 針對不同的元素，求出所有的補元針對不同的元素，求出所有的補元. 17 解答解答 (1) L1中中 a 與與 c 互為補元互為補元, 其中其中 a

15、 為全下界為全下界, c為全上界為全上界, b 沒有沒有 補元補元. (2) L2中中 a 與與 d 互為補元互為補元, 其中其中 a 為全下界為全下界, d 為全上界為全上界, b與與 c 也互為補元也互為補元. (3) L3中中a 與與 e 互為補元互為補元, 其中其中 a 為全下界為全下界, e 為全上界為全上界, b 的補的補 元是元是 c 和和 d ; c 的補元是的補元是 b 和和 d ; d 的補元是的補元是 b 和和 c ; b, c, d 每個元素都有兩個補元每個元素都有兩個補元. (4) L4中中 a 與與 e 互為補元互為補元, 其中其中 a 為全下界為全下界, e 為全

16、上界為全上界, b 的補的補 元是元是 c 和和 d ; c 的補元是的補元是 b ; d 的補元是的補元是 b . 18 有界分配格的補元惟一性有界分配格的補元惟一性 定理定理11.7 設(shè)設(shè)是有界分配格是有界分配格. 若若L中元素中元素 a 存在存在 補元補元, 則存在惟一的補元則存在惟一的補元. 證證 假設(shè)假設(shè) c 是是 a 的補元的補元, 則有則有 ac = 1, ac = 0, 又知又知 b 是是 a 的補元的補元, 故故 ab = 1, ab = 0 從而得到從而得到 ac = ab, ac = ab, 由于由于L是分配格是分配格, b = c. 注意：注意： l 在任何有界格中在任

17、何有界格中, 全下界全下界0與全上界與全上界1互補互補. l 對于一般元素對于一般元素, 可能存在補元可能存在補元, 也可能不存在補元也可能不存在補元. 如果如果 存在補元存在補元, 可能是惟一的可能是惟一的, 也可能是多個補元也可能是多個補元. 對于有界對于有界 分配格分配格, 如果元素存在補元如果元素存在補元, 一定是惟一的一定是惟一的. 19 圖9 有補格的定義有補格的定義 定義定義11.9 設(shè)設(shè)是有界格是有界格, 若若L中所有元素都有補中所有元素都有補 元存在元存在, 則稱則稱L為為有補格有補格. 例如例如, 圖中的圖中的L2, L3和和L4是有補格是有補格, L1不是有補格不是有補格

18、. 20 布爾代數(shù)的定義與實例布爾代數(shù)的定義與實例 定義定義11.10 如果一個格是有補分配格如果一個格是有補分配格, 則稱它為布爾格或布則稱它為布爾格或布 爾代數(shù)爾代數(shù). 布爾代數(shù)標(biāo)記為布爾代數(shù)標(biāo)記為, 為求補運算為求補運算. 例例8 設(shè)設(shè) S110 = 1, 2, 5, 10, 11, 22, 55, 110是是110的正因子集合，的正因子集合， gcd表示求最大公約數(shù)的運算，表示求最大公約數(shù)的運算，lcm表示求最小公倍數(shù)的運表示求最小公倍數(shù)的運 算，問算，問是否構(gòu)成布爾代數(shù)？為什么？是否構(gòu)成布爾代數(shù)？為什么？ 解解 (1) 不難驗證不難驗證S110關(guān)于關(guān)于gcd 和和 lcm 運算構(gòu)成格

19、運算構(gòu)成格. (略略) (2) 驗證分配律驗證分配律 x, y, zS110 有有 gcd(x, lcm(y, z) = lcm(gcd(x, y), gcd(x, z) (3) 驗證它是有補格驗證它是有補格, 1作為作為S110中的全下界中的全下界, 110為全上界為全上界, 1和和110互為補元互為補元, 2和和55互為補元互為補元, 5和和22互為補元互為補元, 10和和 11互為補元互為補元, 從而證明了從而證明了為布爾代數(shù)為布爾代數(shù). 21 實例實例 例例9 設(shè)設(shè)B為任意集合為任意集合, 證明證明B的冪集格的冪集格 構(gòu)成布爾代數(shù)構(gòu)成布爾代數(shù), 稱為集合代數(shù)稱為集合代數(shù). 證證 (1)

20、 P(B)關(guān)于關(guān)于和和構(gòu)成格構(gòu)成格, 因為因為和和運算滿足交換律運算滿足交換律, 結(jié)合律和吸收律結(jié)合律和吸收律. (2) 由于由于和和互相可分配互相可分配, 因此因此P(B)是分配格是分配格. (3) 全下界是空集全下界是空集, 全上界是全上界是B. (4) 根據(jù)絕對補的定義根據(jù)絕對補的定義, 取全集為取全集為B, xP(B), x是是x的補元的補元. 從而證明從而證明P(B)是有補分配格是有補分配格, 即布爾代數(shù)即布爾代數(shù). 22 布爾代數(shù)的性質(zhì)布爾代數(shù)的性質(zhì) 定理定理11.8 設(shè)設(shè)是布爾代數(shù)是布爾代數(shù), 則則 (1) aB, (a ) = a . (2) a,bB, (ab) = a b

21、, (ab) = a b （德摩根律）（德摩根律） 證證 (1) (a ) 是是a 的補元的補元, a也是也是a 的補元的補元. 由補元惟一性得由補元惟一性得(a ) =a. (2) 對任意對任意a, bB有有 (ab)(a b ) = (aa b )(ba b ) = (1b )(a 1) = 11 = 1, (ab)(a b ) = (aba )(abb ) = (0b)(a0) = 00 = 0 a b 是是ab的補元的補元, 根據(jù)補元惟一性有根據(jù)補元惟一性有(ab) = a b , 同理同理 可證可證 (ab) = a b . l 注意：德摩根律對有限個元素也是正確的注意：德摩根律對有

22、限個元素也是正確的. 23 布爾代數(shù)作為代數(shù)系統(tǒng)的定義布爾代數(shù)作為代數(shù)系統(tǒng)的定義 定義定義11.11 設(shè)設(shè)是代數(shù)系統(tǒng)是代數(shù)系統(tǒng), 和和 是二元運算是二元運算. 若若 和和 運運 算滿足：算滿足： (1) 交換律交換律, 即即 a,bB有有a b = b a, a b = b a (2) 分配律分配律, 即即 a,b,cB有有 a (b c) = (a b) (a c), a (b c) = (a b) (a c) (3) 同一律同一律, 即存在即存在0,1B, 使得使得 aB有有a 1 = a, a 0 = a (4) 補元律補元律, 即即 aB, 存在存在 a B 使得使得 a a = 0,

23、 a a = 1 則稱則稱 是一個布爾代數(shù)是一個布爾代數(shù). 可以證明，布爾代數(shù)的兩種定義是等價的可以證明，布爾代數(shù)的兩種定義是等價的. 24 有限布爾代數(shù)的結(jié)構(gòu)有限布爾代數(shù)的結(jié)構(gòu) 定義定義11.12 設(shè)設(shè) L 是格是格, 0L, 若若 bL有有 0 b a b = a, 則則 稱稱 a 是是 L 中的中的原子原子. 實例：實例：(1) L是正整數(shù)是正整數(shù) n 的全體正因子關(guān)于整除關(guān)系構(gòu)成的的全體正因子關(guān)于整除關(guān)系構(gòu)成的 格格, 則則L的原子恰為的原子恰為n的全體素因子的全體素因子. (2) 若若L是是B的冪集的冪集, 則則L的原子就是的原子就是B中元素構(gòu)成的單元集中元素構(gòu)成的單元集 (3) 圖

24、中圖中L1的原子是的原子是a, L2的原子是的原子是a, b, c, L3的原子是的原子是a 和和 b 25 有限布爾代數(shù)的表示定理有限布爾代數(shù)的表示定理 定理定理11.9 (有限布爾代數(shù)的表示定理有限布爾代數(shù)的表示定理) 設(shè)設(shè)B是有限布爾代數(shù)是有限布爾代數(shù), A是是B的全體原子構(gòu)成的集合的全體原子構(gòu)成的集合, 則則B同構(gòu)同構(gòu) 于于A的冪集代數(shù)的冪集代數(shù)P(A). 實例實例: (1) S110關(guān)于關(guān)于gcd, lcm運算構(gòu)成的布爾代數(shù)運算構(gòu)成的布爾代數(shù). 它的原子是它的原子是 2, 5和和11, 因此原子的集合因此原子的集合A = 2,5,11. 冪集冪集 P(A) = ,2,5,11,2,5

25、,2,11,5,11,2,5,11. 冪集代數(shù)是冪集代數(shù)是. 只要令只要令 f: S110P(A), f(1) = , f(2) = 2, f(5) = 5, f(11) = 11, f(10) = 2,5, f(22) = 2, 11, f(55) = 5, 11, f(110) = A, 那么那么 f 就是從就是從S110到冪集到冪集P(A)的同構(gòu)映射的同構(gòu)映射. 26 推論推論 推論推論1 任何有限布爾代數(shù)的基數(shù)為任何有限布爾代數(shù)的基數(shù)為2n, nN. 證證 設(shè)設(shè)B是有限布爾代數(shù)是有限布爾代數(shù), A是是B的所有原子構(gòu)成的集合的所有原子構(gòu)成的集合, 且且 |A| = n, nN. 由定理得

26、由定理得 B P(A), 而而 |P(A)| = 2n, 所以所以 |B| = 2n. 推論推論2 任何等勢的有限布爾代數(shù)都是同構(gòu)的任何等勢的有限布爾代數(shù)都是同構(gòu)的. (證明省略證明省略) 結(jié)論結(jié)論 ： l 有限布爾代數(shù)的基數(shù)都是有限布爾代數(shù)的基數(shù)都是2的冪的冪, l 對于任何自然數(shù)對于任何自然數(shù)n, 僅存在一個僅存在一個2n元的布爾代數(shù)元的布爾代數(shù). 27 圖11 實例實例 下圖給出了下圖給出了 1 元元, 2 元元, 4 元和元和 8 元的布爾代數(shù)元的布爾代數(shù). 28 第十一章第十一章 習(xí)題課習(xí)題課 主要內(nèi)容主要內(nèi)容 l 格的兩個等價定義格的兩個等價定義 l 格的性質(zhì)格的性質(zhì) l 子格子格

27、 l 特殊格：分配格、有界格、有補格、布爾代數(shù)特殊格：分配格、有界格、有補格、布爾代數(shù) 基本要求基本要求 l 能夠判別給定偏序集或者代數(shù)系統(tǒng)是否構(gòu)成格能夠判別給定偏序集或者代數(shù)系統(tǒng)是否構(gòu)成格 l 能夠確定一個命題的對偶命題能夠確定一個命題的對偶命題 l 能夠證明格中的等式和不等式能夠證明格中的等式和不等式 l 能判別格能判別格L的子集的子集S是否構(gòu)成子格是否構(gòu)成子格 l 能夠判別給定的格是否為分配格、有補格能夠判別給定的格是否為分配格、有補格 l 能夠判別布爾代數(shù)并證明布爾代數(shù)中的等式能夠判別布爾代數(shù)并證明布爾代數(shù)中的等式 29 練習(xí)練習(xí)1 1(1) 證明格中的命題證明格中的命題, 即即 (a

28、b)b = b (2) 證明證明 (ab)(cd) (ac)(bd) (1) (ab)b是是ab與與b的最小上界的最小上界, 根據(jù)最小上界的定義根據(jù)最小上界的定義 有有(ab)b b . b是是ab與與b的上界的上界, 故有故有(ab)b b. 由由 于于 偏序的反對稱性偏序的反對稱性, 等式得證等式得證. (2) ab a ac, ab b bd, 所以所以 (ab) (ac)(bd), 同理同理 (cd) (ac)(bd). 從而得到從而得到 (ab)(cd) (ac)(bd) 30 解 2求圖中格的所有子格求圖中格的所有子格. 1元子格：元子格： a , b , c , d , e ； 2元子格：元子格： a, b , a, c , a, d , a, e , b, c , b, d , b, e , c, e , d, e ； 3元子格：元子格： a, b, c , a, b, d , a, b, e , a, c, e , a, d, e , b,