離散數(shù)學(xué)ch11v0506

1、1第十一章第十一章 格與布爾代數(shù)格與布爾代數(shù)主要內(nèi)容主要內(nèi)容l 格的定義及性質(zhì)格的定義及性質(zhì) l 子格子格l 分配格、有補格分配格、有補格l 布爾代數(shù)布爾代數(shù)211.1 格的定義與性質(zhì)格的定義與性質(zhì) 定義定義11.1 設(shè)設(shè)是偏序集，如果是偏序集，如果 x,y S，x,y都有最小上都有最小上界和最大下界，則稱界和最大下界，則稱S關(guān)于偏序關(guān)于偏序 作成一個作成一個格格. 求求x,y 最小上界和最大下界看成最小上界和最大下界看成 x 與與 y 的二元運算的二元運算和和，例例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ù). 3圖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

3、(x,y)，(3) 都不是格都不是格. 可以找到兩個結(jié)點缺少最大下界或最小上界可以找到兩個結(jié)點缺少最大下界或最小上界4實例實例例例 偏序集偏序集的的哈斯圖哈斯圖.5實例：子群格實例：子群格例例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的子群格的子群格. 在在

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

5、切格為真一切格為真, 則則 f 的對偶命題的對偶命題 f*也對一切格為真也對一切格為真. 例如例如, 如果對一切格如果對一切格L都有都有 a,bL, ab a，那么對一切格那么對一切格L都有都有 a,bL, ab a l 注意：對偶是相互的，即注意：對偶是相互的，即 ( f*)*= f7格的性質(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 有有

6、aa = a, aa = a(4) a,bL 有有 a(ab) = a, a(ab) = a 8證明證明(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ù)

7、反對稱性 (ab)c = a(bc)由對偶原理由對偶原理, (ab)c = a(bc)9證明證明(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 10格的性質(zhì)：序與運算的關(guān)系格的性質(zhì)：序與運算的關(guān)系定理定理11.2 設(shè)設(shè)L是格是格, 則則 a,bL有有a b ab = a a

8、b = b證證 (1) 先證先證 a b ab = 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 11格的性質(zhì)：保序格的性質(zhì)：保序定理定理11.3 設(shè)設(shè)L是格是格, a,b,c,dL，若若a b 且且 c d, 則則 ac bd, a

9、c 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)注意：一般說來注意：一般說來, 格中的格中的和和運算不滿足分配律運算不滿足分配律. 12格作為代數(shù)系統(tǒng)的定義格作為代數(shù)系統(tǒng)的定義定理定理11.4 設(shè)設(shè)是具有兩個二元運算的代數(shù)系統(tǒng)是具有兩個二元運算的代數(shù)系統(tǒng), 若對若對于于 和和 運算適合交換律、結(jié)合律、吸收律運算適合交換

10、律、結(jié)合律、吸收律, 則可以適當(dāng)定義則可以適當(dāng)定義S中中的偏序的偏序 ,使得使得 構(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)成格.13子格及其判別法子格及其判別法定義定義11.4 設(shè)設(shè)是格是格, S是是L的非空子集的非空子集, 若若S關(guān)于關(guān)于L中中的運算的運算和和仍構(gòu)成格仍構(gòu)成格, 則稱則稱S是是L的

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

12、格. 稱稱 L3為為鉆石格鉆石格, L4為為五角格五角格.實例實例15分配格的判別及性質(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的子格的子

13、格, 同構(gòu)于五角格；同構(gòu)于五角格； a,c,b,e,f 是是L3的子格的子格 同構(gòu)于鉆石格同構(gòu)于鉆石格. 16有界格的定義有界格的定義定義定義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存在全下界和全上界存在全下界和全上界, 則稱則稱

14、L 為為有界有界格格, 一般將有界格一般將有界格L記為記為.17 定理定理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, 在求該命題的對偶命題時在求該命

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

16、界, 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 為全上界為全上界, b

17、的補的補 元是元是 c 和和 d ; c 的補元是的補元是 b ; d 的補元是的補元是 b . 20有界分配格的補元惟一性有界分配格的補元惟一性定理定理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 在任何有界格中在任何有界格中, 全下界全下界0與

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

19、例定義定義11.10 如果一個格是有補分配格如果一個格是有補分配格, 則稱它為布爾格或布則稱它為布爾格或布爾代數(shù)爾代數(shù). 布爾代數(shù)標記為布爾代數(shù)標記為, 為求補運算為求補運算. 例例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)成格運算構(gòu)成格. (略略)(2) 驗證分配律驗證分配律 x,

20、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ù). 23實例實例例例9 設(shè)設(shè)B為任意集合為任意集合, 證明證明B的冪集格的冪集格構(gòu)成布爾代數(shù)構(gòu)成布爾代數(shù), 稱為集合代數(shù)稱為集合代數(shù).證證 (1) P(B)關(guān)于關(guān)于和和構(gòu)成格構(gòu)成格, 因為因為和和運算滿足交換律運算

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

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

23、義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, a a = 1 則稱則稱 是一個布爾代數(shù)是一個布爾代數(shù).可以證明，布爾代數(shù)的兩種定義是等

24、價的可以證明，布爾代數(shù)的兩種定義是等價的. 26有限布爾代數(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) 圖中圖中L1的原子是的原子是a, L2的原子是的原子是a, b, c, L3的原子是的原子是a 和和 b

25、27實例實例28實例實例例例 偏序集偏序集的哈斯圖的哈斯圖.29有限布爾代數(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,2,11,5,11,2,5,11. 冪集代數(shù)是冪集代

26、數(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)映射. 30推論推論推論推論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, 所

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

28、格：分配格、有界格、有補格、布爾代數(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ù)中的等式 33練習(xí)練習(xí)11(1) 證明格中的命題證明格中的命題, 即即 (ab)b = b(2) 證明證明 (ab)(cd) (ac)(bd)(

29、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)34解2求圖中格的所有子格求圖中格的所有子格.1元子格：元子格： a , b , c , d , e ；2元子格：元子格： a, b , a, c , a, d , a, e , b, c ,

30、 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, e , b, c, d, e ；5元子格：元子格： a, b, c, d, e 練習(xí)練習(xí)2eabcd35圖133判別下述格判別下述格L是否為分配格是否為分配格. L1不是分配格不是分配格, 因為它含有與鉆石格同構(gòu)的子格因為它含有與鉆石格同構(gòu)的子格. L2和和L3不是分配格不是分配格, 因為它們含有與五角格同構(gòu)的子格因為它

31、們含有與五角格同構(gòu)的子格.L1 L2 L3練習(xí)練習(xí)336L1 L2 L3圖124針對下圖，求出每個格的補元并說明它們是否為有補格針對下圖，求出每個格的補元并說明它們是否為有補格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的補元為的補元

32、為d. L2與與L3是有補格是有補格.練習(xí)練習(xí)4375對于以下各題給定的集合和運算判斷它們是哪一類代數(shù)對于以下各題給定的集合和運算判斷它們是哪一類代數(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,

33、 x,yS4, x y與與x y分別表示分別表示 x 與與 y 的的最小公倍數(shù)和最大公約數(shù)最小公倍數(shù)和最大公約數(shù).(5) S5 = 0, 1, 為模為模2加法加法, 為模為模2乘法乘法. 練習(xí)練習(xí)538解： 解答解答(1) 不是代數(shù)系統(tǒng)不是代數(shù)系統(tǒng), 因為乘法不封閉因為乘法不封閉, 例如例如4 4=16.(2) 是半群但不是獨異點是半群但不是獨異點, 因為因為 運算滿足結(jié)合律運算滿足結(jié)合律, 但是沒有但是沒有單單 位元位元.(3) 是獨異點但不是群是獨異點但不是群. 因為因為 運算滿足結(jié)合律運算滿足結(jié)合律, 單位元是單位元是1, 可可 是是0沒有乘法逆元沒有乘法逆元. (4) 是格是格, 也是

34、布爾代數(shù)也是布爾代數(shù). 因為這兩個運算滿足交換律和分配因為這兩個運算滿足交換律和分配 律；求最小公倍數(shù)運算的單位元是律；求最小公倍數(shù)運算的單位元是1, 求最大公約數(shù)運算求最大公約數(shù)運算 的單位元是的單位元是6, 滿足同一律；兩個運算滿足補元律滿足同一律；兩個運算滿足補元律. (5) 是域是域. 對于模對于模 n 的環(huán)的環(huán)Zn, 當(dāng)當(dāng)n為素數(shù)時構(gòu)成域為素數(shù)時構(gòu)成域. 39證證(2) 由由 反之也對反之也對.下面證下面證明它們都等價于明它們都等價于ab. 由由 得得即即 ab, 又由又由 ab 得得 bababa 10)2(6設(shè)設(shè)是布爾代數(shù)是布爾代數(shù), 證明對于證明對于B中任意元素中任意元素 a,

35、bbabaa )()1(練習(xí)練習(xí)6; 1, 10 bababa即即得得00)()( abbabbababababaaabaa )(1)()()()1(1 babababaaabaaaa )(0)()()(140練習(xí)練習(xí)77. 判斷下述代數(shù)系統(tǒng)是否為格？是不是布爾代數(shù)？判斷下述代數(shù)系統(tǒng)是否為格？是不是布爾代數(shù)？(1) S = 1, 3, 4, 12; 任給任給 x, yS, x y = lcm(x,y), x y = gcd(x,y), 其中其中 lcm 是求最小公倍數(shù)是求最小公倍數(shù), gcd 是求最大公約數(shù)是求最大公約數(shù). (2) S = 0, 1, 2; 是模是模3加法加法, 是模是模3乘法

36、乘法(3) S = 0, ., n, 其中其中n2; 任給任給 x, yS, x y = max(x,y), x y = min(x,y) (1) 是布爾代數(shù)是布爾代數(shù). (2) 不是格不是格. (3) 是格是格, 但不是布爾代數(shù)但不是布爾代數(shù). 4142半群、獨異點與群的定義半群、獨異點與群的定義定義定義10.1(1) 設(shè)設(shè)V=是代數(shù)系統(tǒng)，是代數(shù)系統(tǒng)， 為二元運算，如果為二元運算，如果 運算是運算是可可 結(jié)合的，則稱結(jié)合的，則稱V為為半群半群.(2) 設(shè)設(shè)V=是半群，若是半群，若eS是關(guān)于是關(guān)于 運算的單位元，則運算的單位元，則稱稱V 是是含幺半群含幺半群，也叫做，也叫做獨異點獨異點. 有時

37、也將獨異點有時也將獨異點V 記作記作 V=. (3) 設(shè)設(shè)V=是獨異點，是獨異點，e S關(guān)于關(guān)于 運算的單位元，若運算的單位元，若 a S，a 1 S，則稱，則稱V是是群群. 通常將群記作通常將群記作G. 4310.4 環(huán)與域環(huán)與域 定義定義10.12 設(shè)設(shè)是代數(shù)系統(tǒng)，是代數(shù)系統(tǒng)，+和和是二元運算是二元運算. 如果滿足如果滿足以下條件以下條件:(1) 構(gòu)成交換群構(gòu)成交換群(2) 構(gòu)成半群構(gòu)成半群(3) 運算關(guān)于運算關(guān)于+運算適合分配律運算適合分配律則稱則稱是一個是一個環(huán)環(huán). 通常稱通常稱+運算為環(huán)中的運算為環(huán)中的加法加法，運算為環(huán)中的運算為環(huán)中的乘法乘法.環(huán)中加法單位元記作環(huán)中加法單位元記作

38、0，乘法單位元（如果存在）記作，乘法單位元（如果存在）記作1. 對任何元素對任何元素 x，稱，稱 x 的加法逆元為的加法逆元為負元負元，記作，記作 x. 若若 x 存在乘法逆元的話，則稱之為存在乘法逆元的話，則稱之為逆元逆元，記作，記作x 1. 44環(huán)的實例環(huán)的實例例例15(1) 整數(shù)集、有理數(shù)集、實數(shù)集和復(fù)數(shù)集關(guān)于普通的加法和整數(shù)集、有理數(shù)集、實數(shù)集和復(fù)數(shù)集關(guān)于普通的加法和 乘法構(gòu)成環(huán)，分別稱為乘法構(gòu)成環(huán)，分別稱為整數(shù)環(huán)整數(shù)環(huán)Z，有理數(shù)環(huán)有理數(shù)環(huán)Q，實數(shù)環(huán)實數(shù)環(huán)R 和和復(fù)數(shù)環(huán)復(fù)數(shù)環(huán)C.(2) n(n2)階實矩陣的集合階實矩陣的集合Mn(R)關(guān)于矩陣的加法和乘法構(gòu)關(guān)于矩陣的加法和乘法構(gòu) 成環(huán)，稱為成環(huán)，稱為 n 階實矩陣環(huán)階實矩陣環(huán).(3) 集合的冪集集合的冪集P(B)關(guān)于集合的對稱差運算和交運算構(gòu)成環(huán)關(guān)于集合的對稱差運算和交運算構(gòu)成環(huán).(4) 設(shè)設(shè)Zn0,1, . , n1， 和和 分別表示模分別表示模n的加法和乘的加法和乘 法，則法，則構(gòu)成環(huán)，稱為構(gòu)成環(huán)，稱為模模 n的整數(shù)環(huán)的整數(shù)環(huán). 45特殊的環(huán)特殊的環(huán)定義定義10.13 設(shè)設(shè)是環(huán)是環(huán)(1) 若環(huán)中乘法若環(huán)中乘法 適合交換律，則稱適合交換律，則稱R是是交換環(huán)交換環(huán)(2) 若環(huán)中乘法若環(huán)中乘法 存在單位元，則稱存在單位元，則稱R是是含幺環(huán)含幺環(huán)(3) 若若 a,bR，ab=0 a=0b=0，則稱，則稱R是是無零因子