第八章格與布爾代數(shù)

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

2、格. x,ySn，xy是是lcm(x,y)，即，即x與與y的的最小公倍數(shù)最小公倍數(shù). xy是是gcd(x,y)，即，即x與與y的最大公約數(shù)的最大公約數(shù). 第八章格與布爾代數(shù)3圖2例例2 判斷下列偏序集是否構(gòu)成格，并說明理由判斷下列偏序集是否構(gòu)成格，并說明理由.(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,

3、y)，xy = min(x,y)，(3) 都不是格都不是格. 可以找到兩個(gè)結(jié)點(diǎn)缺少最大下界或最小上界可以找到兩個(gè)結(jié)點(diǎn)缺少最大下界或最小上界第八章格與布爾代數(shù)4實(shí)例：子群格實(shí)例：子群格例例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

4、(G)中，中， H1H2 就是就是 H1H2 H1H2 就是就是 第八章格與布爾代數(shù)5格的性質(zhì)：對(duì)偶原理格的性質(zhì)：對(duì)偶原理定義定義 設(shè)設(shè) f 是含有格中元素以及符號(hào)是含有格中元素以及符號(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

5、對(duì)對(duì)一切格為真一切格為真, 則則 f 的對(duì)偶命題的對(duì)偶命題 f*也對(duì)一切格為真也對(duì)一切格為真. 例如例如, 如果對(duì)一切格如果對(duì)一切格L都有都有 a,bL, ab a，那么對(duì)一切格那么對(duì)一切格L都有都有 a,bL, ab a l 注意：對(duì)偶是相互的，即注意：對(duì)偶是相互的，即 ( f*)*= f第八章格與布爾代數(shù)6格的性質(zhì)：算律格的性質(zhì)：算律定理定理 設(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)(

6、3) aL 有有 aa = a, aa = a(4) a,bL 有有 a(ab) = a, a(ab) = a 第八章格與布爾代數(shù)7證明證明(1) ab是是 a, 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)同理可證同理可證 (a

7、b)c a(bc) 根據(jù)反對(duì)稱性根據(jù)反對(duì)稱性 (ab)c = a(bc)由對(duì)偶原理由對(duì)偶原理, (ab)c = a(bc)第八章格與布爾代數(shù)8證明證明(3) 顯然顯然 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 第八章格與布爾代數(shù)9格的性質(zhì)：序與運(yùn)算的關(guān)系格的性質(zhì)：序與運(yùn)算的關(guān)系定理定理

8、 設(shè)設(shè)L是格是格, 則則 a,bL有有 a b ab = a ab = b證證 (1) 先證先證 a b ab = a由由 a a 和和 a b 可知可知 a 是是 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 第八章格與布爾代數(shù)10格的性質(zhì)：保序格的性質(zhì)：保序定理定理 設(shè)設(shè)L是格是

9、格, a,b,c,dL，若若a b 且且 c d, 則則 ac bd, ac bd例例4 設(shè)設(shè)L是格是格, 證明證明 a,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)注意：一般說來注意：一般說來, 格中的格中的和和運(yùn)算不滿足分配律運(yùn)算不滿足分配律. 第八章格與布爾代數(shù)11格作為代數(shù)系統(tǒng)的定義格作為代數(shù)系統(tǒng)的定義定理定理 設(shè)設(shè)是具有兩個(gè)二元運(yùn)算的代數(shù)系統(tǒng)是具有兩

10、個(gè)二元運(yùn)算的代數(shù)系統(tǒng), 若對(duì)于若對(duì)于 和和 運(yùn)算適合交換律、結(jié)合律、吸收律運(yùn)算適合交換律、結(jié)合律、吸收律, 則可以適當(dāng)定義則可以適當(dāng)定義S中中的偏序的偏序 ,使得使得 構(gòu)成格構(gòu)成格, 且且 a,bS 有有 ab = a b, ab = a b.證明省略證明省略. 根據(jù)定理根據(jù)定理8.4, 可以給出格的另一個(gè)等價(jià)定義可以給出格的另一個(gè)等價(jià)定義. 定義定義 設(shè)設(shè)是代數(shù)系統(tǒng)是代數(shù)系統(tǒng), 和和 是二元運(yùn)算是二元運(yùn)算, 如果如果 和和 滿足交換律、結(jié)合律和吸收律滿足交換律、結(jié)合律和吸收律, 則則構(gòu)成格構(gòu)成格.第八章格與布爾代數(shù)12子格及其判別法子格及其判別法定義定義 設(shè)設(shè)是格是格, S是是L的非空子集的

11、非空子集, 若若S關(guān)于關(guān)于L中的運(yùn)中的運(yùn)算算和和仍構(gòu)成格仍構(gòu)成格, 則稱則稱S是是L的子格的子格. 例例5 設(shè)格設(shè)格L如圖所示如圖所示. 令令 S1=a, e, f, g, S2=a, b, e, gS1不是不是L的子格的子格, 因?yàn)橐驗(yàn)閑, f S1 但但 ef = c S1.S2是是L的子格的子格. 第八章格與布爾代數(shù)138.2 分配格、有補(bǔ)格與布爾代數(shù)分配格、有補(bǔ)格與布爾代數(shù) 定義定義 設(shè)設(shè)是格是格, 若若 a,b,cL,有有 a(bc) = (ab)(ac) a(bc) = (ab)(ac) 則稱則稱L為分配格為分配格.l 注意：可以證明以上兩個(gè)條件互為充分必要條件注意：可以證明以上兩

12、個(gè)條件互為充分必要條件L1 和和 L2 是分配格是分配格, L3 和和 L4不是分配格不是分配格. 稱稱 L3為鉆石格為鉆石格, L4為五角格為五角格.實(shí)例實(shí)例第八章格與布爾代數(shù)14分配格的判別及性質(zhì)分配格的判別及性質(zhì)定理定理 設(shè)設(shè)L是格是格, 則則L是分配格當(dāng)且僅當(dāng)是分配格當(dāng)且僅當(dāng)L不含有與鉆石格不含有與鉆石格或五角格同構(gòu)的子格或五角格同構(gòu)的子格.證明省略證明省略.推論推論 (1) 小于五元的格都是分配格小于五元的格都是分配格.(2) 任何一條鏈都是分配格任何一條鏈都是分配格. 例例6 說明圖中的格是否為分配格說明圖中的格是否為分配格, 為什么？為什么？解解 都不是分配格都不是分配格. a,

13、b,c,d,e 是是L1的子格的子格, 同構(gòu)于鉆石格同構(gòu)于鉆石格 a,b,c,e,f 是是L2的子格的子格, 同構(gòu)于五角格；同構(gòu)于五角格； a,c,b,e,f 是是L3的子格的子格 同構(gòu)于鉆石格同構(gòu)于鉆石格. 第八章格與布爾代數(shù)15有界格的定義有界格的定義定義定義 設(shè)設(shè)L是格是格,(1) 若存在若存在aL使得使得 xL有有 a x, 則稱則稱a為為L的全下界的全下界(2) 若存在若存在bL使得使得 xL有有 x b, 則稱則稱b為為L的全上界的全上界 說明：說明：l 格格L若存在全下界或全上界若存在全下界或全上界, 一定是惟一的一定是惟一的. l 一般將格一般將格L的全下界記為的全下界記為0,

14、 全上界記為全上界記為1.定義定義 設(shè)設(shè)L是格是格,若若L的每個(gè)非空子集均有上下確界，則稱其為的每個(gè)非空子集均有上下確界，則稱其為完全格；若完全格；若L存在全下界和全上界存在全下界和全上界, 則稱其為有界則稱其為有界格格, 一般將有界格一般將有界格L記為記為.第八章格與布爾代數(shù)16 定理定理 設(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)算的單

15、位元；1是關(guān)于是關(guān)于運(yùn)算的運(yùn)算的零元零元,運(yùn)算的單位元運(yùn)算的單位元. l 對(duì)于涉及到有界格的命題對(duì)于涉及到有界格的命題, 如果其中含有全下界如果其中含有全下界0或全上界或全上界1, 在求該命題的對(duì)偶命題時(shí)在求該命題的對(duì)偶命題時(shí), 必須將必須將0替換成替換成1, 而將而將1替換替換成成0.有界格的性質(zhì)有界格的性質(zhì)第八章格與布爾代數(shù)17有界格中的補(bǔ)元及實(shí)例有界格中的補(bǔ)元及實(shí)例定義定義 設(shè)設(shè)是有界格是有界格, aL, 若存在若存在bL 使得使得 ab = 0 和和 ab = 1 成立成立, 則稱則稱b是是a的補(bǔ)元的補(bǔ)元.l 注意：若注意：若b是是a的補(bǔ)元的補(bǔ)元, 那么那么a也是也是b的補(bǔ)元的補(bǔ)元.

16、a和和b互為補(bǔ)元互為補(bǔ)元. 例例7 考慮下圖中的格考慮下圖中的格. 針對(duì)不同的元素，求出所有的補(bǔ)元針對(duì)不同的元素，求出所有的補(bǔ)元.第八章格與布爾代數(shù)18解答解答(1) L1中中 a 與與 c 互為補(bǔ)元互為補(bǔ)元, 其中其中 a 為全下界為全下界, c為全上界為全上界, b 沒有沒有 補(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ǔ)元是的

17、補(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 為全上界為全上界, b 的補(bǔ)的補(bǔ) 元是元是 c 和和 d ; c 的補(bǔ)元是的補(bǔ)元是 b ; d 的補(bǔ)元是的補(bǔ)元是 b . 第八章格與布爾代數(shù)19有界分配格的補(bǔ)元惟一性有界分配格的補(bǔ)元惟一性定理定理 設(shè)設(shè)是有界分配格是有界分配格. 若若L中元素中元素 a 存在存在補(bǔ)元補(bǔ)元, 則存在惟一的補(bǔ)元?jiǎng)t存在惟一的補(bǔ)元.證證 假設(shè)假設(shè) c 是是 a 的補(bǔ)元的補(bǔ)元, 則有則有 ac = 1, ac

18、 = 0, 又知又知 b 是是 a 的補(bǔ)元的補(bǔ)元, 故故 ab = 1, ab = 0 從而得到從而得到 ac = ab, ac = ab, 由于由于L是分配格是分配格, b = c. 注意：注意：l 在任何有界格中在任何有界格中, 全下界全下界0與全上界與全上界1互補(bǔ)互補(bǔ).l 對(duì)于一般元素對(duì)于一般元素, 可能存在補(bǔ)元可能存在補(bǔ)元, 也可能不存在補(bǔ)元也可能不存在補(bǔ)元. 如果如果存在補(bǔ)元存在補(bǔ)元, 可能是惟一的可能是惟一的, 也可能是多個(gè)補(bǔ)元也可能是多個(gè)補(bǔ)元. 對(duì)于有界對(duì)于有界分配格分配格, 如果元素存在補(bǔ)元如果元素存在補(bǔ)元, 一定是惟一的一定是惟一的.第八章格與布爾代數(shù)20圖9有補(bǔ)格的定義有補(bǔ)

19、格的定義定義定義 設(shè)設(shè)是有界格是有界格, 若若L中所有元素都有補(bǔ)中所有元素都有補(bǔ)元存在元存在, 則稱則稱L為有補(bǔ)格為有補(bǔ)格. 例如例如, 圖中的圖中的L2, L3和和L4是有補(bǔ)格是有補(bǔ)格, L1不是有補(bǔ)格不是有補(bǔ)格. 第八章格與布爾代數(shù)21布爾代數(shù)的定義與實(shí)例布爾代數(shù)的定義與實(shí)例定義定義 如果一個(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)算，表

20、示求最大公約數(shù)的運(yùn)算，lcm表示求最小公倍數(shù)的運(yùn)表示求最小公倍數(shù)的運(yùn)算，問算，問是否構(gòu)成布爾代數(shù)？為什么？是否構(gòu)成布爾代數(shù)？為什么？解解 (1) 不難驗(yàn)證不難驗(yàn)證S110關(guān)于關(guān)于gcd 和和 lcm 運(yùn)算構(gòu)成格運(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ǔ)

21、元互為補(bǔ)元, 從而證明了從而證明了為布爾代數(shù)為布爾代數(shù). 第八章格與布爾代數(shù)22實(shí)例實(shí)例例例9 設(shè)設(shè)B為任意集合為任意集合, 證明證明B的冪集格的冪集格構(gòu)成布爾代數(shù)構(gòu)成布爾代數(shù), 稱為集合代數(shù)稱為集合代數(shù).證證 (1) 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)是有

22、補(bǔ)分配格是有補(bǔ)分配格, 即布爾代數(shù)即布爾代數(shù). 第八章格與布爾代數(shù)23布爾代數(shù)的性質(zhì)布爾代數(shù)的性質(zhì)定理定理 設(shè)設(shè)是布爾代數(shù)是布爾代數(shù), 則則(1) aB, (a ) = a .(2) a,bB, (ab) = a b , (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

23、) = 00 = 0a b 是是ab的補(bǔ)元的補(bǔ)元, 根據(jù)補(bǔ)元惟一性有根據(jù)補(bǔ)元惟一性有(ab) = a b , 同理同理可證可證 (ab) = a b . l 注意：德摩根律對(duì)有限個(gè)元素也是正確的注意：德摩根律對(duì)有限個(gè)元素也是正確的. 第八章格與布爾代數(shù)24布爾代數(shù)作為代數(shù)系統(tǒng)的定義布爾代數(shù)作為代數(shù)系統(tǒng)的定義定義定義 設(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

24、c) = (a b) (a c) (3) 同一律同一律, 即存在即存在0,1B, 使得使得 aB有有a 1 = a, a 0 = a (4) 補(bǔ)元律補(bǔ)元律, 即即 aB, 存在存在 a B 使得使得 a a = 0, a a = 1 則稱則稱 是一個(gè)布爾代數(shù)是一個(gè)布爾代數(shù).可以證明，布爾代數(shù)的兩種定義是等價(jià)的可以證明，布爾代數(shù)的兩種定義是等價(jià)的. 第八章格與布爾代數(shù)25有限布爾代數(shù)的結(jié)構(gòu)有限布爾代數(shù)的結(jié)構(gòu)定義定義 設(shè)設(shè) L 是格是格, 0L, 若若 bL有有 0 b a b = a, 則則稱稱 a 是是 L 中的原子中的原子. 實(shí)例：實(shí)例：(1) L是正整數(shù)是正整數(shù) n 的全體正因子關(guān)于整除關(guān)

25、系構(gòu)成的的全體正因子關(guān)于整除關(guān)系構(gòu)成的格格, 則則L的原子恰為的原子恰為n的全體素因子的全體素因子.(2) 若若L是是B的冪集的冪集, 則則L的原子就是的原子就是B中元素構(gòu)成的單元集中元素構(gòu)成的單元集 (3) 圖中圖中L1的原子是的原子是b,c,d, L2的原子是的原子是 b, c, L3的原子是的原子是c,b,e第八章格與布爾代數(shù)26有限布爾代數(shù)的表示定理有限布爾代數(shù)的表示定理定理定理 (有限布爾代數(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)

26、 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,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)映射. 第八章格與布爾代

27、數(shù)27推論推論推論推論1 任何有限布爾代數(shù)的基數(shù)為任何有限布爾代數(shù)的基數(shù)為2n, nN.證證 設(shè)設(shè)B是有限布爾代數(shù)是有限布爾代數(shù), A是是B的所有原子構(gòu)成的集合的所有原子構(gòu)成的集合, 且且 |A| = n, nN. 由定理得由定理得 B P(A), 而而 |P(A)| = 2n, 所以所以 |B| = 2n. 推論推論2 任何等勢的有限布爾代數(shù)都是同構(gòu)的任何等勢的有限布爾代數(shù)都是同構(gòu)的. (證明省略證明省略)結(jié)論結(jié)論 ：l 有限布爾代數(shù)的基數(shù)都是有限布爾代數(shù)的基數(shù)都是2的冪的冪, l 對(duì)于任何自然數(shù)對(duì)于任何自然數(shù)n, 僅存在一個(gè)僅存在一個(gè)2n元的布爾代數(shù)元的布爾代數(shù). 第八章格與布爾代數(shù)28圖

28、11實(shí)例實(shí)例下圖給出了下圖給出了 1 元元, 2 元元, 4 元和元和 8 元的布爾代數(shù)元的布爾代數(shù). 第八章格與布爾代數(shù)29第六章第六章3 習(xí)題課習(xí)題課主要內(nèi)容主要內(nèi)容l 格的兩個(gè)等價(jià)定義格的兩個(gè)等價(jià)定義l 格的性質(zhì)格的性質(zhì)l 子格子格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 能

29、夠判別給定的格是否為分配格、有補(bǔ)格能夠判別給定的格是否為分配格、有補(bǔ)格l 能夠判別布爾代數(shù)并證明布爾代數(shù)中的等式能夠判別布爾代數(shù)并證明布爾代數(shù)中的等式 第八章格與布爾代數(shù)30練習(xí)練習(xí)11(1) 證明格中的命題證明格中的命題, 即即 (ab)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)

30、(ac)(bd), 同理同理 (cd) (ac)(bd). 從而得到從而得到 (ab)(cd) (ac)(bd)第八章格與布爾代數(shù)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, c, e , a, d, e , b, c, e , b, d, e ；4元子格：元子格： a, b, c, e , a, b, d,

31、e , b, c, d, e ；5元子格：元子格： a, b, c, d, e 練習(xí)練習(xí)2eabcd第八章格與布爾代數(shù)32圖133判別下述格判別下述格L是否為分配格是否為分配格. L1不是分配格不是分配格, 因?yàn)樗信c鉆石格同構(gòu)的子格因?yàn)樗信c鉆石格同構(gòu)的子格. L2和和L3不是分配格不是分配格, 因?yàn)樗鼈兒信c五角格同構(gòu)的子格因?yàn)樗鼈兒信c五角格同構(gòu)的子格.L1 L2 L3練習(xí)練習(xí)3第八章格與布爾代數(shù)33L1 L2 L3圖124針對(duì)下圖，求出每個(gè)格的補(bǔ)元并說明它們是否為有補(bǔ)格針對(duì)下圖，求出每個(gè)格的補(bǔ)元并說明它們是否為有補(bǔ)格L1中中, a與與h互為補(bǔ)元互為補(bǔ)元, 其他元素沒補(bǔ)元其他元素沒補(bǔ)

32、元. L2中中, a與與g互為補(bǔ)元互為補(bǔ)元. b的補(bǔ)元為的補(bǔ)元為c, d, f；c的補(bǔ)元為的補(bǔ)元為b, d, e, f；d的補(bǔ)元為的補(bǔ)元為b, c, e；e的補(bǔ)元為的補(bǔ)元為c, d, f；f的補(bǔ)元為的補(bǔ)元為b, c, e. L3中中, a與與h互為補(bǔ)元互為補(bǔ)元, b的補(bǔ)元為的補(bǔ)元為d；c的補(bǔ)元為的補(bǔ)元為d；d的補(bǔ)元為的補(bǔ)元為b, c, g；g的補(bǔ)元為的補(bǔ)元為d. L2與與L3是有補(bǔ)格是有補(bǔ)格.練習(xí)練習(xí)4第八章格與布爾代數(shù)345對(duì)于以下各題給定的集合和運(yùn)算判斷它們是哪一類代數(shù)對(duì)于以下各題給定的集合和運(yùn)算判斷它們是哪一類代數(shù)系統(tǒng)（半群、獨(dú)異點(diǎn)、群、環(huán)、域、格、布爾代數(shù)）系統(tǒng)（半群、獨(dú)異點(diǎn)、群、環(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