離散數(shù)學課件ch11

1、1第十一章第十一章 格與布爾代數(shù)格與布爾代數(shù)主要內容主要內容l 格的定義及性質格的定義及性質 l 子格子格l 分配格、有補格分配格、有補格l 布爾代數(shù)布爾代數(shù)211.1 格的定義與性質格的定義與性質 定義定義11.1 設設是偏序集，如果是偏序集，如果 x,y S，x,y都有最小上都有最小上界和最大下界，則稱界和最大下界，則稱S關于偏序關于偏序 作成一個作成一個格格. 求求x,y 最小上界和最大下界看成最小上界和最大下界看成 x 與與 y 的二元運算的二元運算和和，例例1 設設n是正整數(shù)，是正整數(shù)，Sn是是n的正因子的集合的正因子的集合. D為整除關系，則為整除關系，則偏序集偏序集構成格構成格.

2、 x,ySn，xy是是lcm(x,y)，即，即x與與y的的最小公倍數(shù)最小公倍數(shù). xy是是gcd(x,y)，即，即x與與y的最大公約數(shù)的最大公約數(shù). 3圖2例例2 判斷下列偏序集是否構成格，并說明理由判斷下列偏序集是否構成格，并說明理由.(1) ，其中，其中P(B)是集合是集合B的冪集的冪集.(2) ，其中，其中Z是整數(shù)集，是整數(shù)集，為小于或等于關系為小于或等于關系.(3) 偏序集的哈斯圖分別在下圖給出偏序集的哈斯圖分別在下圖給出. 實例實例 (1) 冪集格冪集格. x,yP(B)，xy就是就是xy，xy就是就是xy. (2) 是格是格. x,yZ，xy = max(x,y)，xy = min

3、(x,y)，(3) 都不是格都不是格. 可以找到兩個結點缺少最大下界或最小上界可以找到兩個結點缺少最大下界或最小上界4實例：子群格實例：子群格例例3 設設G是群，是群，L(G)是是G 的所有子群的集合的所有子群的集合. 即即L(G) = H | HG ，對任意的對任意的H1, H2L(G)，H1H2是是G 的子群，的子群，是由是由H1H2生成的子群（即包含著生成的子群（即包含著H1H2的最小子群）的最小子群）.在在L(G)上定義包含關系上定義包含關系 ，則，則L(G)關于包含關系構成一個關于包含關系構成一個格，稱為格，稱為G的子群格的子群格. 在在 L(G)中，中， H1H2 就是就是 H1H

4、2 H1H2 就是就是 5格的性質：對偶原理格的性質：對偶原理定義定義11.2 設設 f 是含有格中元素以及符號是含有格中元素以及符號 =, , ,和和的命的命題題. 令令 f*是將是將 f 中的中的 替換成替換成 , 替換成替換成 ,替換成替換成,替換替換成成所得到的命題所得到的命題. 稱稱 f* 為為 f 的的對偶命題對偶命題. 例如例如, 在格中令在格中令 f 是是 (ab)c c, f*是是 (ab)c c .格的格的對偶原理對偶原理 設設 f 是含有格中元素以及符號是含有格中元素以及符號=, , ,和和等的命題等的命題. 若若 f 對對一切格為真一切格為真, 則則 f 的對偶命題的對

5、偶命題 f*也對一切格為真也對一切格為真. 例如例如, 如果對一切格如果對一切格L都有都有 a,bL, ab a，那么對一切格那么對一切格L都有都有 a,bL, ab a l 注意：對偶是相互的，即注意：對偶是相互的，即 ( f*)*= f6格的性質：算律格的性質：算律定理定理11.1 設設是格是格, 則運算則運算和和適合交換律、結合律、適合交換律、結合律、冪等律和吸收律冪等律和吸收律, 即即(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

6、有有 a(ab) = a, a(ab) = a 7證明證明(1) ab是是 a, 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)由對偶原理

7、由對偶原理, (ab)c = a(bc)8證明證明(3) 顯然顯然 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 9格的性質：序與運算的關系格的性質：序與運算的關系定理定理11.2 設設L是格是格, 則則 a,bL有有a b ab = a ab = b證證 (1) 先證先證 a b ab

8、= a由由 a a 和和 a b 可知可知 a 是是 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 10格的性質：保序格的性質：保序定理定理11.3 設設L是格是格, a,b,c,dL，若若a b 且且 c d, 則則 ac bd, ac bd例例4 設設L是格是格, 證明證明 a,

9、b,cL有有 a(bc) (ab)(ac).證證 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)注意：一般說來注意：一般說來, 格中的格中的和和運算不滿足分配律運算不滿足分配律. 11格作為代數(shù)系統(tǒng)的定義格作為代數(shù)系統(tǒng)的定義定理定理11.4 設設是具有兩個二元運算的代數(shù)系統(tǒng)是具有兩個二元運算的代數(shù)系統(tǒng), 若對若對于于 和和 運算適合交換律、結合律、吸收律運算適合交換律、結合律、吸收律, 則可以適當定義則可以適當定

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

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

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

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

14、L記為記為.16 定理定理11.6 設設是有界格是有界格, 則則 aL有有a0 = 0, a0 = a, a1 = a, a1 = 1注意：注意：l 有限格有限格L=a1,a2,an是有界格是有界格, a1a2an是是L的全下的全下界界, a1a2an是是L的全上界的全上界. l 0是關于是關于運算的零元運算的零元,運算的單位元；運算的單位元；1是關于是關于運算的運算的零元零元,運算的單位元運算的單位元. l 對于涉及到有界格的命題對于涉及到有界格的命題, 如果其中含有全下界如果其中含有全下界0或全上界或全上界1, 在求該命題的對偶命題時在求該命題的對偶命題時, 必須將必須將0替換成替換成1,

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

16、元.(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 為全上界為全上界, b 的補的補 元是元是 c 和和 d ; c 的補元

17、是的補元是 b ; d 的補元是的補元是 b . 19有界分配格的補元惟一性有界分配格的補元惟一性定理定理11.7 設設是有界分配格是有界分配格. 若若L中元素中元素 a 存在存在補元補元, 則存在惟一的補元則存在惟一的補元.證證 假設假設 c 是是 a 的補元的補元, 則有則有 ac = 1, ac = 0, 又知又知 b 是是 a 的補元的補元, 故故 ab = 1, ab = 0 從而得到從而得到 ac = ab, ac = ab, 由于由于L是分配格是分配格, b = c. 注意：注意：l 在任何有界格中在任何有界格中, 全下界全下界0與全上界與全上界1互補互補.l 對于一般元素對于一

18、般元素, 可能存在補元可能存在補元, 也可能不存在補元也可能不存在補元. 如果如果存在補元存在補元, 可能是惟一的可能是惟一的, 也可能是多個補元也可能是多個補元. 對于有界對于有界分配格分配格, 如果元素存在補元如果元素存在補元, 一定是惟一的一定是惟一的.20圖9有補格的定義有補格的定義定義定義11.9 設設是有界格是有界格, 若若L中所有元素都有補中所有元素都有補元存在元存在, 則稱則稱L為為有補格有補格. 例如例如, 圖中的圖中的L2, L3和和L4是有補格是有補格, L1不是有補格不是有補格. 21布爾代數(shù)的定義與實例布爾代數(shù)的定義與實例定義定義11.10 如果一個格是有補分配格如果

19、一個格是有補分配格, 則稱它為布爾格或布則稱它為布爾格或布爾代數(shù)爾代數(shù). 布爾代數(shù)標記為布爾代數(shù)標記為, 為求補運算為求補運算. 例例8 設設 S110 = 1, 2, 5, 10, 11, 22, 55, 110是是110的正因子集合，的正因子集合，gcd表示求最大公約數(shù)的運算，表示求最大公約數(shù)的運算，lcm表示求最小公倍數(shù)的運表示求最小公倍數(shù)的運算，問算，問是否構成布爾代數(shù)？為什么？是否構成布爾代數(shù)？為什么？解解 (1) 不難驗證不難驗證S110關于關于gcd 和和 lcm 運算構成格運算構成格. (略略)(2) 驗證分配律驗證分配律 x, y, zS110 有有 gcd(x, lcm(y

20、, z) = lcm(gcd(x, y), gcd(x, z) (3) 驗證它是有補格驗證它是有補格, 1作為作為S110中的全下界中的全下界, 110為全上界為全上界, 1和和110互為補元互為補元, 2和和55互為補元互為補元, 5和和22互為補元互為補元, 10和和 11互為補元互為補元, 從而證明了從而證明了為布爾代數(shù)為布爾代數(shù). 22實例實例例例9 設設B為任意集合為任意集合, 證明證明B的冪集格的冪集格構成布爾代數(shù)構成布爾代數(shù), 稱為集合代數(shù)稱為集合代數(shù).證證 (1) P(B)關于關于和和構成格構成格, 因為因為和和運算滿足交換律運算滿足交換律, 結合律和吸收律結合律和吸收律. (

21、2) 由于由于和和互相可分配互相可分配, 因此因此P(B)是分配格是分配格.(3) 全下界是空集全下界是空集, 全上界是全上界是B. (4) 根據(jù)絕對補的定義根據(jù)絕對補的定義, 取全集為取全集為B, xP(B), x是是x的補元的補元. 從而證明從而證明P(B)是有補分配格是有補分配格, 即布爾代數(shù)即布爾代數(shù). 23布爾代數(shù)的性質布爾代數(shù)的性質定理定理11.8 設設是布爾代數(shù)是布爾代數(shù), 則則(1) aB, (a ) = a .(2) a,bB, (ab) = a b , (ab) = a b （德摩根律）（德摩根律）證證 (1) (a ) 是是a 的補元的補元, a也是也是a 的補元的補元.

22、 由補元惟一性得由補元惟一性得(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 = 0a b 是是ab的補元的補元, 根據(jù)補元惟一性有根據(jù)補元惟一性有(ab) = a b , 同理同理可證可證 (ab) = a b . l 注意：德摩根律對有限個元素也是正確的注意：德摩根律對有限個元素也是正確的. 24布爾代數(shù)作為代數(shù)系統(tǒng)的定義布爾代數(shù)作為代數(shù)系統(tǒng)的定義定義定義11.11 設設是代數(shù)系統(tǒng)是代數(shù)系統(tǒng), 和和

23、是二元運算是二元運算. 若若 和和 運運算滿足：算滿足： (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, a a = 1 則稱則稱 是一個布爾代數(shù)是一個布爾代數(shù).可以證明，布爾代數(shù)的兩種定義是等價的可以證明，布爾代數(shù)的兩種定義是等價的. 25

24、有限布爾代數(shù)的結構有限布爾代數(shù)的結構定義定義11.12 設設 L 是格是格, 0L, 若若 bL有有 0 b a b = a, 則則稱稱 a 是是 L 中的中的原子原子. 實例：實例：(1) L是正整數(shù)是正整數(shù) n 的全體正因子關于整除關系構成的的全體正因子關于整除關系構成的格格, 則則L的原子恰為的原子恰為n的全體素因子的全體素因子.(2) 若若L是是B的冪集的冪集, 則則L的原子就是的原子就是B中元素構成的單元集中元素構成的單元集 (3) 圖中圖中L1的原子是的原子是a, L2的原子是的原子是a, b, c, L3的原子是的原子是a 和和 b26有限布爾代數(shù)的表示定理有限布爾代數(shù)的表示定理

25、定理定理11.9 (有限布爾代數(shù)的表示定理有限布爾代數(shù)的表示定理) 設設B是有限布爾代數(shù)是有限布爾代數(shù), A是是B的全體原子構成的集合的全體原子構成的集合, 則則B同構同構于于A的冪集代數(shù)的冪集代數(shù)P(A).實例實例: (1) S110關于關于gcd, lcm運算構成的布爾代數(shù)運算構成的布爾代數(shù). 它的原子是它的原子是2, 5和和11, 因此原子的集合因此原子的集合A = 2,5,11. 冪集冪集 P(A) = ,2,5,11,2,5,2,11,5,11,2,5,11. 冪集代數(shù)是冪集代數(shù)是. 只要令只要令 f: S110P(A), f(1) = , f(2) = 2, f(5) = 5, f

26、(11) = 11, f(10) = 2,5, f(22) = 2, 11, f(55) = 5, 11, f(110) = A, 那么那么 f 就是從就是從S110到冪集到冪集P(A)的同構映射的同構映射. 27推論推論推論推論1 任何有限布爾代數(shù)的基數(shù)為任何有限布爾代數(shù)的基數(shù)為2n, nN.證證 設設B是有限布爾代數(shù)是有限布爾代數(shù), A是是B的所有原子構成的集合的所有原子構成的集合, 且且 |A| = n, nN. 由定理得由定理得 B P(A), 而而 |P(A)| = 2n, 所以所以 |B| = 2n. 推論推論2 任何等勢的有限布爾代數(shù)都是同構的任何等勢的有限布爾代數(shù)都是同構的.

27、(證明省略證明省略)結論結論 ：l 有限布爾代數(shù)的基數(shù)都是有限布爾代數(shù)的基數(shù)都是2的冪的冪, l 對于任何自然數(shù)對于任何自然數(shù)n, 僅存在一個僅存在一個2n元的布爾代數(shù)元的布爾代數(shù). 28圖11實例實例下圖給出了下圖給出了 1 元元, 2 元元, 4 元和元和 8 元的布爾代數(shù)元的布爾代數(shù). 29第十一章第十一章 習題課習題課主要內容主要內容l 格的兩個等價定義格的兩個等價定義l 格的性質格的性質l 子格子格l 特殊格：分配格、有界格、有補格、布爾代數(shù)特殊格：分配格、有界格、有補格、布爾代數(shù)基本要求基本要求l 能夠判別給定偏序集或者代數(shù)系統(tǒng)是否構成格能夠判別給定偏序集或者代數(shù)系統(tǒng)是否構成格l

28、能夠確定一個命題的對偶命題能夠確定一個命題的對偶命題l 能夠證明格中的等式和不等式能夠證明格中的等式和不等式l 能判別格能判別格L的子集的子集S是否構成子格是否構成子格l 能夠判別給定的格是否為分配格、有補格能夠判別給定的格是否為分配格、有補格l 能夠判別布爾代數(shù)并證明布爾代數(shù)中的等式能夠判別布爾代數(shù)并證明布爾代數(shù)中的等式 30練習練習11(1) 證明格中的命題證明格中的命題, 即即 (ab)b = b(2) 證明證明 (ab)(cd) (ac)(bd)(1) (ab)b是是ab與與b的最小上界的最小上界, 根據(jù)最小上界的定義根據(jù)最小上界的定義有有(ab)b b . b是是ab與與b的上界的上

29、界, 故有故有(ab)b b. 由由于于偏序的反對稱性偏序的反對稱性, 等式得證等式得證. (2) ab a ac, ab b bd, 所以所以 (ab) (ac)(bd), 同理同理 (cd) (ac)(bd). 從而得到從而得到 (ab)(cd) (ac)(bd)31解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,

30、 c, e , a, d, e , b, c, e , b, d, e ；4元子格：元子格： a, b, c, e , a, b, d, e , b, c, d, e ；5元子格：元子格： a, b, c, d, e 練習練習2eabcd32圖133判別下述格判別下述格L是否為分配格是否為分配格. L1不是分配格不是分配格, 因為它含有與鉆石格同構的子格因為它含有與鉆石格同構的子格. L2和和L3不是分配格不是分配格, 因為它們含有與五角格同構的子格因為它們含有與五角格同構的子格.L1 L2 L3練習練習333L1 L2 L3圖124針對下圖，求出每個格的補元并說明它們是否為有補格針對下圖，求

31、出每個格的補元并說明它們是否為有補格L1中中, a與與h互為補元互為補元, 其他元素沒補元其他元素沒補元. L2中中, a與與g互為補元互為補元. b的補元為的補元為c, d, f；c的補元為的補元為b, d, e, f；d的補元為的補元為b, c, e；e的補元為的補元為c, d, f；f的補元為的補元為b, c, e. L3中中, a與與h互為補元互為補元, b的補元為的補元為d；c的補元為的補元為d；d的補元為的補元為b, c, g；g的補元為的補元為d. L2與與L3是有補格是有補格.練習練習4345對于以下各題給定的集合和運算判斷它們是哪一類代數(shù)對于以下各題給定的集合和運算判斷它們是

32、哪一類代數(shù)系統(tǒng)（半群、獨異點、群、環(huán)、域、格、布爾代數(shù)）系統(tǒng)（半群、獨異點、群、環(huán)、域、格、布爾代數(shù)）, 并說并說明理由明理由.(1) S1 = 1, 1/2, 2, 1/3, 3, 1/4, 4, 為普通乘法為普通乘法.(2) S2 = a1, a2, ., an, ai, ajS2, ai aj = ai, 這里的這里的 n 為給定為給定 正整數(shù)正整數(shù), n1.(3) S3 = 0, 1, 為普通乘法為普通乘法.(4) S4 = 1, 2, 3, 6, x,yS4, x y與與x y分別表示分別表示 x 與與 y 的的最小公倍數(shù)和最大公約數(shù)最小公倍數(shù)和最大公約數(shù).(5) S5 = 0, 1, 為模為模2加法加法, 為模為模2乘法乘法. 練習練習535解： 解答解答(1) 不是代數(shù)系統(tǒng)