離散數(shù)學(xué)第11章課件_高等教育出版社_屈婉玲_耿素云_張立昂主編

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

2、，則偏序集偏序集構(gòu)成格構(gòu)成格. 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) 偏序集的哈斯圖分別在下圖給出偏序集的哈斯圖分別在下圖給出. 實(shí)例實(shí)例 (1) 冪集格冪集格. x,yP(B)，xy就是就是xy，xy就是就是xy. (2) 是格是格. x,yZ，xy = ma

3、x(x,y)，xy = min(x,y)，(3) 都不是格都不是格. 可以找到兩個(gè)結(jié)點(diǎn)缺少最大下界或最小上界可以找到兩個(gè)結(jié)點(diǎn)缺少最大下界或最小上界4格的性質(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 5格的性質(zhì)：序與運(yùn)算的關(guān)系格的性質(zhì)：序與運(yùn)算的

4、關(guān)系定理定理11.3 設(shè)設(shè)L是格是格, 則則 a,bL有有a b ab = a ab = b 可以用集合的例子來驗(yàn)證可以用集合的例子來驗(yàn)證 冪集格冪集格，其中，其中P(B)是集合是集合B的冪集的冪集.冪集格冪集格. x,yP(B)，xy就是就是xy，xy就是就是xy.6格的性質(zhì)：保序格的性質(zhì)：保序定理定理11.4 設(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).證證 ac a b, ac c d 因此因此 ac bd. 同理可證同理可證 ac bd 證證 由由 a

5、a, bc b 得得 a(bc) ab由由 a a, bc c 得得 a(bc) ac從而得到從而得到a(bc) (ab)(ac) （注意最大下界）（注意最大下界）注意：一般說來注意：一般說來, 格中的格中的和和運(yùn)算不滿足分配律運(yùn)算不滿足分配律. 7格作為代數(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中中的偏序的偏序 ,使得使得 構(gòu)成格構(gòu)成格, 且且 a,bS 有有 ab = a b, ab = a b.證明省略

6、證明省略. 根據(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)成格.811.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 是分配格是分配

7、格, L3 和和 L4不是分配格不是分配格. 稱稱 L3為為鉆石格鉆石格, L4為為五角格五角格.實(shí)例實(shí)例9有界格的定義有界格的定義定義定義11.6 設(shè)設(shè)L是格是格,(1) 若存在若存在aL使得使得 xL有有 a x, 則稱則稱a為為L(zhǎng)的的全下界全下界(2) 若存在若存在bL使得使得 xL有有 x b, 則稱則稱b為為L(zhǎng)的的全上界全上界 說明：說明：l 格格L若存在全下界或全上界若存在全下界或全上界, 一定是惟一的一定是惟一的. l 一般將格一般將格L的全下界記為的全下界記為0, 全上界記為全上界記為1.定義定義11.7 設(shè)設(shè)L是格是格,若若L存在全下界和全上界存在全下界和全上界, 則稱則稱L

8、 為為有界有界格格, 一般將有界格一般將有界格L記為記為.10 定理定理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)算的單位元. 有界格的性質(zhì)有界格的性質(zhì)11有界格中的補(bǔ)元及實(shí)例有界格中的補(bǔ)元及實(shí)例定義定義11.8 設(shè)設(shè)是有界格是有界格, aL, 若存在若存在bL 使得使得

9、 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ǔ)元.12解答解答(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 與與

10、 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 為全上界為全上界, b 的補(bǔ)的補(bǔ) 元是元是 c 和和 d ; c 的補(bǔ)元是的補(bǔ)元是 b ; d 的補(bǔ)元是的補(bǔ)元是 b . 13有界分配格的補(bǔ)元惟一性有界分配格的補(bǔ)元惟一性定理定理11.7 設(shè)設(shè)是有界分配格是有界分配格. 若若L中元素中元素 a

11、存在存在補(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=b (ba) = b (ca )= (b c) (b a )= (ac ) c=c注意：注意：l 在任何有界格中在任何有界格中, 全下界全下界0與全上界與全上界1互補(bǔ)互補(bǔ).l 對(duì)于一般元素對(duì)于一般元素, 可能存在補(bǔ)元可能存在補(bǔ)元, 也可能不存在補(bǔ)元也可能不存在補(bǔ)元. 如果如果存在補(bǔ)元存在補(bǔ)元,

12、可能是惟一的可能是惟一的, 也可能是多個(gè)補(bǔ)元也可能是多個(gè)補(bǔ)元. 對(duì)于有界對(duì)于有界分配格分配格, 如果元素存在補(bǔ)元如果元素存在補(bǔ)元, 一定是惟一的一定是惟一的.14圖9有補(bǔ)格的定義有補(bǔ)格的定義定義定義11.9 設(shè)設(shè)是有界格是有界格, 若若L中所有元素都有補(bǔ)中所有元素都有補(bǔ)元存在元存在, 則稱則稱L為為有補(bǔ)格有補(bǔ)格. 例如例如, 圖中的圖中的L2, L3和和L4是有補(bǔ)格是有補(bǔ)格, L1不是有補(bǔ)格不是有補(bǔ)格. 15布爾代數(shù)的定義與實(shí)例布爾代數(shù)的定義與實(shí)例定義定義11.10 如果一個(gè)格是有補(bǔ)分配格如果一個(gè)格是有補(bǔ)分配格, 則稱它為布爾格或布則稱它為布爾格或布爾代數(shù)爾代數(shù). 布爾代數(shù)標(biāo)記為布爾代數(shù)標(biāo)記為

13、, 為求補(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)算，問算，問是否構(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)證

14、它是有補(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ù). 16布爾代數(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 ) 是是a 的補(bǔ)元的補(bǔ)元, a也是也是a 的補(bǔ)元的補(bǔ)元. 由補(bǔ)元惟一性得由補(bǔ)元惟一性得(a ) =a.

15、(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 = 0a b 是是ab的補(bǔ)元的補(bǔ)元, 根據(jù)補(bǔ)元惟一性有根據(jù)補(bǔ)元惟一性有(ab) = a b , 同理同理可證可證 (ab) = a b . l 注意：德摩根律對(duì)有限個(gè)元素也是正確的注意：德摩根律對(duì)有限個(gè)元素也是正確的. 17圖11實(shí)例實(shí)例下圖給出了下圖給出了 1 元元, 2 元元, 4 元和元和 8 元的布爾代數(shù)元的布爾代數(shù). 18第十一章第十一章 習(xí)題課習(xí)題課主要內(nèi)容主要內(nèi)

16、容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 能夠判別給定的格是否為分配格、有補(bǔ)格能夠判別給定的格是否為分配格、有補(bǔ)格l 能夠判別布爾代數(shù)并證明布爾代數(shù)中的等式能夠判別布爾代數(shù)并證明布爾代數(shù)中的等式 19解1求圖中格

17、的所有子格求圖中格的所有子格.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, e , b, c, d, e ；5元子格：元子格： a, b, c, d, e 練習(xí)練習(xí)1eabcd20L1 L2 L3圖122針對(duì)下圖，求出每個(gè)格的補(bǔ)元并說明它們是否為有補(bǔ)格針對(duì)下圖，求出每個(gè)格的補(bǔ)元并說明它們是否為有補(bǔ)格L1中中, a與與h互為補(bǔ)元互為補(bǔ)元, 其他元素沒補(bǔ)元其他元素沒補(bǔ)元. 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,