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

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

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

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

4、b a，那么對(duì)一切格那么對(duì)一切格 L 都有都有 a,bL, ab a l 注意：對(duì)偶是相互的，即注意：對(duì)偶是相互的，即 ( f*)*= f 5 格的性質(zhì)：算律格的性質(zhì)：算律 定理定理11.1 設(shè)設(shè)是格是格, 則運(yùn)算則運(yùn)算和和適合交換律、結(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. 由對(duì)偶原理由對(duì)偶原理, 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ù)反對(duì)稱性根據(jù)反對(duì)稱性 (ab)c = a(bc) 由對(duì)偶原理由對(duì)偶原理, (ab)c = a(bc) 7 證明證明 (3) 顯然顯然

6、 a aa, 又由又由 a a 可得可得 aa a. 根據(jù)反對(duì)稱性根據(jù)反對(duì)稱性 有有aa = a . 由對(duì)偶原理由對(duì)偶原理, aa = a 得證得證. (4) 顯然顯然 a(ab) a (5) 由由 a a, ab a 可得可得 a(ab) a (6) 由式由式(5)和和(6) 可得可得 a(ab) = a, 根據(jù)對(duì)偶原理根據(jù)對(duì)偶原理, a(ab) = a 8 格的性質(zhì)：序與運(yùn)算的關(guān)系格的性質(zhì)：序與運(yùn)算的關(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. 由反對(duì)稱性得由反對(duì)稱性得 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) 注意：一般說(shuō)來(lái)注意：一般說(shuō)來(lái), 格中的格中的和和運(yùn)算不滿足分配律運(yùn)算不滿足分配律. 10 格作為代數(shù)系統(tǒng)的定義格作為代數(shù)系統(tǒng)的定義 定理定理11.4 設(shè)設(shè)是具有兩個(gè)二元運(yùn)算的代數(shù)系統(tǒng)是具有兩個(gè)二元運(yùn)算的代數(shù)系統(tǒng), 若對(duì)若對(duì) 于于 和和 運(yùn)算適合交換律、結(jié)合律、吸收律運(yùn)算適合交換律、結(jié)合律、吸收律, 則可以適當(dāng)定義則可以適當(dāng)定義S 中中 的偏序的偏序

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

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

11、格五角格. 實(shí)例實(shí)例 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 說(shuō)明圖中的格是否為分配格說(shuō)明圖中的格是否為分配格, 為什么？為什么？ 解解 都不是分配格都不是分配格. 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(zhǎng)的的全下界全下界 (2) 若存在若存在bL使得使得 xL有有 x b, 則稱則稱b為為L(zhǎng)的的全上界全上界 說(shuō)明：說(shuō)明： 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)于運(yùn)算的零元運(yùn)算的零元,運(yùn)算的單位元；運(yùn)算的單位元；1是關(guān)于是關(guān)于運(yùn)算的運(yùn)算的 零元零元,運(yùn)算的單位元運(yùn)算的單位元. l 對(duì)于涉及到有界格的命題對(duì)于涉及到有界格的命題, 如果其中含有全下界如果其中含有全下界0或全上界或全上界 1, 在求該命題的對(duì)偶命題時(shí)在求該命題

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

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

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

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

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

19、運(yùn)算構(gòu)成格. (略略) (2) 驗(yàn)證分配律驗(yàn)證分配律 x, y, zS110 有有 gcd(x, lcm(y, z) = lcm(gcd(x, y), gcd(x, z) (3) 驗(yàn)證它是有補(bǔ)格驗(yàn)證它是有補(bǔ)格, 1作為作為S110中的全下界中的全下界, 110為全上界為全上界, 1和和110互為補(bǔ)元互為補(bǔ)元, 2和和55互為補(bǔ)元互為補(bǔ)元, 5和和22互為補(bǔ)元互為補(bǔ)元, 10和和 11互為補(bǔ)元互為補(bǔ)元, 從而證明了從而證明了為布爾代數(shù)為布爾代數(shù). 21 實(shí)例實(shí)例 例例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)成格, 因?yàn)橐驗(yàn)楹秃瓦\(yùn)算滿足交換律運(yùn)算滿足交換律, 結(jié)合律和吸收律結(jié)合律和吸收律. (2) 由于由于和和互相可分配互相可分配, 因此因此P(B)是分配格是分配格. (3) 全下界是空集全下界是空集, 全上界是全上界是B. (4) 根據(jù)絕對(duì)補(bǔ)的定義根據(jù)絕對(duì)補(bǔ)的定義, 取全集為取全集為B, xP(B), x是是x的補(bǔ)元的補(bǔ)元. 從而證明從而證明P(B)是有補(bǔ)分配格是有補(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 的補(bǔ)元的補(bǔ)元, a也是也是a 的補(bǔ)元的補(bǔ)元. 由補(bǔ)元惟一性得由補(bǔ)元惟一性得(a ) =a. (2) 對(duì)任意對(duì)任意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的補(bǔ)元的補(bǔ)元, 根據(jù)補(bǔ)元惟一性有根據(jù)補(bǔ)元惟一性有(ab) = a b , 同理同理 可證可證 (ab) = a b . l 注意：德摩根律對(duì)有限個(gè)元素也是正確的注意：德摩根律對(duì)有

22、限個(gè)元素也是正確的. 23 布爾代數(shù)作為代數(shù)系統(tǒng)的定義布爾代數(shù)作為代數(shù)系統(tǒng)的定義 定義定義11.11 設(shè)設(shè)是代數(shù)系統(tǒng)是代數(shù)系統(tǒng), 和和 是二元運(yùn)算是二元運(yùn)算. 若若 和和 運(yùn)運(yùn) 算滿足：算滿足： (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) 補(bǔ)元律補(bǔ)元律, 即即 aB, 存在存在 a B 使得使得 a a = 0,

23、 a a = 1 則稱則稱 是一個(gè)布爾代數(shù)是一個(gè)布爾代數(shù). 可以證明，布爾代數(shù)的兩種定義是等價(jià)的可以證明，布爾代數(shù)的兩種定義是等價(jià)的. 24 有限布爾代數(shù)的結(jié)構(gòu)有限布爾代數(shù)的結(jié)構(gòu) 定義定義11.12 設(shè)設(shè) L 是格是格, 0L, 若若 bL有有 0 b a b = a, 則則 稱稱 a 是是 L 中的中的原子原子. 實(shí)例：實(shí)例：(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). 實(shí)例實(shí)例: (1) S110關(guān)于關(guān)于gcd, lcm運(yùn)算構(gòu)成的布爾代數(shù)運(yùn)算構(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ì)的有限布爾代數(shù)都是同構(gòu)的任何等勢(shì)的有限布爾代數(shù)都是同構(gòu)的. (證明省略證明省略) 結(jié)論結(jié)論 ： l 有限布爾代數(shù)的基數(shù)都是有限布爾代數(shù)的基數(shù)都是2的冪的冪, l 對(duì)于任何自然數(shù)對(duì)于任何自然數(shù)n, 僅存在一個(gè)僅存在一個(gè)2n元的布爾代數(shù)元的布爾代數(shù). 27 圖11 實(shí)例實(shí)例 下圖給出了下圖給出了 1 元元, 2 元元, 4 元和元和 8 元的布爾代數(shù)元的布爾代數(shù). 28 第十一章第十一章 習(xí)題課習(xí)題課 主要內(nèi)容主要內(nèi)容 l 格的兩個(gè)等價(jià)定義格的兩個(gè)等價(jià)定義 l 格的性質(zhì)格的性質(zhì) l 子格子格

27、 l 特殊格：分配格、有界格、有補(bǔ)格、布爾代數(shù)特殊格：分配格、有界格、有補(bǔ)格、布爾代數(shù) 基本要求基本要求 l 能夠判別給定偏序集或者代數(shù)系統(tǒng)是否構(gòu)成格能夠判別給定偏序集或者代數(shù)系統(tǒng)是否構(gòu)成格 l 能夠確定一個(gè)命題的對(duì)偶命題能夠確定一個(gè)命題的對(duì)偶命題 l 能夠證明格中的等式和不等式能夠證明格中的等式和不等式 l 能判別格能判別格L的子集的子集S是否構(gòu)成子格是否構(gòu)成子格 l 能夠判別給定的格是否為分配格、有補(bǔ)格能夠判別給定的格是否為分配格、有補(bǔ)格 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. 由由 于于 偏序的反對(duì)稱性偏序的反對(duì)稱性, 等式得證等式得證. (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,