離散數(shù)學(xué)格與布爾代數(shù)-ppt課件

1、第11章 格與布爾代數(shù)離離 散散 數(shù)數(shù) 學(xué)學(xué)中國(guó)地質(zhì)大學(xué)本科生課程中國(guó)地質(zhì)大學(xué)本科生課程本章內(nèi)容本章內(nèi)容11.1 11.1 格的定義與性質(zhì)格的定義與性質(zhì)11.2 11.2 分配格、有補(bǔ)格與布爾代數(shù)分配格、有補(bǔ)格與布爾代數(shù)本章總結(jié)本章總結(jié)作業(yè)作業(yè)11.1 11.1 格的定義與性質(zhì)格的定義與性質(zhì) 定義定義11.111.1 設(shè)設(shè)是偏序集，是偏序集，如果如果 x, ,ySS， x, ,y 都有最小都有最小上界和最大下界上界和最大下界，則稱，則稱S S關(guān)于偏序關(guān)于偏序作成一個(gè)作成一個(gè)格格( (lattice) )。說(shuō)明：說(shuō)明：由于最小上界和最大下界的唯一性，可以把求由于最小上界和最大下界的唯一性，可以把

2、求 x, ,y 的最的最小上界和最大下界看成小上界和最大下界看成x x與與y y的二元運(yùn)算的二元運(yùn)算和和。xy：表示：表示x x與與y y的最小上界的最小上界xy：表示：表示x x和和y y的最大下界。的最大下界。 本章出現(xiàn)的本章出現(xiàn)的和和符號(hào)只代表格中的運(yùn)算，而不再有其它的符號(hào)只代表格中的運(yùn)算，而不再有其它的含義。含義。格的實(shí)例格的實(shí)例例例11.111.1 設(shè)設(shè)n n是正整數(shù)，是正整數(shù)，S Sn n是是n n的正因子的集合。的正因子的集合。D D為整除關(guān)系，為整除關(guān)系，則偏序集則偏序集S,D構(gòu)成格。構(gòu)成格。 x,ySx,ySn n，xyxy是是lcm(x,y)lcm(x,y)，即，即x x與

3、與y y的最小公倍數(shù)。的最小公倍數(shù)。xyxy是是gcd(x,y)gcd(x,y)，即，即x x與與y y的最大公約數(shù)。的最大公約數(shù)。下圖給出了格下圖給出了格S,D，S,D和和S,D。例例11.211.2例例11.211.2 判斷下列偏序集是否構(gòu)成格判斷下列偏序集是否構(gòu)成格, ,并說(shuō)明理由。并說(shuō)明理由。(1) P(B),(1) ，其中，其中P(B)P(B)是集合是集合B B的冪集。的冪集。(2) (2) ，其中，其中Z Z是整數(shù)集是整數(shù)集,為小于或等于關(guān)系。為小于或等于關(guān)系。(3) (3) 偏序集的哈斯圖分別在下圖給出。偏序集的哈斯圖分別在下圖給出。例例11.211.2解答解答 (1)(1)是格

4、。是格。 x,yP(B)x,yP(B)，xyxy就是就是xyxy，xyxy就是就是xyxy。由于由于和和運(yùn)算在運(yùn)算在P(B)P(B)上是封閉的，所以上是封閉的，所以xyxy，xyP(B)xyP(B)。稱稱P(B), ,為為B B的的冪集格冪集格。(2)(2)是格。是格。 x,yZ,xyx,yZ,xymax(x,y)max(x,y)，xyxymin(x,y)min(x,y)，它們都是整數(shù)。，它們都是整數(shù)。(3)(3)都不是格。都不是格。(a)(a)中的中的a,ba,b沒(méi)有最大下界。沒(méi)有最大下界。(b)(b)中的中的b,db,d有兩個(gè)上界有兩個(gè)上界c c和和e,e,但沒(méi)有最小上界。但沒(méi)有最小上界。

5、(c)(c)中的中的b,cb,c有三個(gè)上界有三個(gè)上界d,e,f,d,e,f,但沒(méi)有最小上界。但沒(méi)有最小上界。(d)(d)中的中的a,ga,g沒(méi)有最大下界。沒(méi)有最大下界。例例11.311.3例例11.3 11.3 設(shè)設(shè)G G是群，是群，L(G)L(G)是是G G的所有子群的集合。即的所有子群的集合。即L(G)L(G) H|HG H|HG 對(duì)任意的對(duì)任意的H H1 1,H,H2 2L(G)L(G)，H H1 1HH2 2也是也是G G的子群，而的子群，而H 是由是由H H1 1HH2 2生成的子群（即包含著生成的子群（即包含著H H1 1HH2 2的最小的子群）。的最小的子群）。在在L(G)L(G

6、)上定義包含關(guān)系上定義包含關(guān)系 ，則，則L(G)L(G)關(guān)于包含關(guān)系構(gòu)成一個(gè)格，關(guān)于包含關(guān)系構(gòu)成一個(gè)格，稱為稱為G G的的子群格子群格。易見在易見在L(G)L(G)中，中，H H1 1HH2 2就是就是H H1 1HH2 2，H H1 1HH2 2就是就是H 。 對(duì)偶原理對(duì)偶原理定義定義11.211.2 設(shè)設(shè)f f是含有格中元素以及符號(hào)、是含有格中元素以及符號(hào)、和和的的命題。令命題。令f f* *是將是將f f中的中的替換成替換成，替換成替換成，替換成替換成，替換成替換成所得到的命題。稱所得到的命題。稱f f* *為為f f的的對(duì)偶命題對(duì)偶命題。例如例如 在格中令在格中令f f是是(ab)cc

7、(ab)cc，則，則f f* *是是(ab)cc(ab)cc。格的對(duì)偶原理格的對(duì)偶原理 設(shè)設(shè)f f是含有格中元素以及符號(hào)、是含有格中元素以及符號(hào)、和和的命題。若的命題。若f f對(duì)一切格為真，則對(duì)一切格為真，則f f的對(duì)偶命題的對(duì)偶命題f f* *也對(duì)一切格也對(duì)一切格為真。為真。例如例如 對(duì)一切格對(duì)一切格L L都有都有 a,bLa,bL，abaaba( (因?yàn)橐驗(yàn)閍 a和和b b的交是的交是a a的一個(gè)下界的一個(gè)下界) )那么那么對(duì)一切格對(duì)一切格L L都有都有 a,bLa,bL，abaaba說(shuō)明說(shuō)明許多格的性質(zhì)都是互為對(duì)偶命題的。許多格的性質(zhì)都是互為對(duì)偶命題的。有了格的對(duì)偶原理，在證明格的性質(zhì)時(shí)

8、，有了格的對(duì)偶原理，在證明格的性質(zhì)時(shí)，只須證明其中的一個(gè)命題即可。只須證明其中的一個(gè)命題即可。格的運(yùn)算性質(zhì)格的運(yùn)算性質(zhì)定理定理11.111.1 設(shè)設(shè)是格，則運(yùn)算是格，則運(yùn)算和和適合適合交換律交換律、結(jié)合結(jié)合律律、冪等律冪等律和和吸收律吸收律，即，即(1)(1)交換律交換律 a,bL a,bL 有有ababbabaababbaba(2)(2)結(jié)合律結(jié)合律 a,b,cL a,b,cL 有有(ab)c(ab)ca(bc)a(bc)(ab)c(ab)ca(bc)a(bc)(3)(3)冪等律冪等律 aL aL 有有aaaaa aaaaaa a(4)(4)吸收律吸收律 a,bL a,bL 有有a(ab)a

9、(ab)a aa(ab)a(ab)a a定理定理11.111.1(1)ab(1)ab和和baba分別是分別是a,ba,b和和b,ab,a的最小上界。的最小上界。由于由于a,ba,bb,ab,a，所以，所以ababbaba。由對(duì)偶原理，由對(duì)偶原理，ababbaba得證。得證。(2)(2)由最小上界的定義有由最小上界的定義有(ab)caba (ab)caba (13.1)(13.1)(ab)cabb (ab)cabb (13.2)(13.2)(ab)cc (ab)cc (13.3)(13.3)由式由式13.213.2和和13.313.3有有(ab)cbc(ab)cbc(13.4)(13.4)再由式

10、再由式13.113.1和和13.413.4有有(ab)ca(bc)(ab)ca(bc)同理可證同理可證(ab)ca(bc)(ab)ca(bc)根據(jù)偏序關(guān)系的反對(duì)稱性有根據(jù)偏序關(guān)系的反對(duì)稱性有(ab)c(ab)ca(bc)a(bc)由對(duì)偶原理，由對(duì)偶原理，(ab)c(ab)ca(bc)a(bc)得證。得證。定理定理11.111.1(3)(3)顯然顯然aaa,aaa,又由又由aaaa可得可得 aaaaaa。根據(jù)反對(duì)稱性有根據(jù)反對(duì)稱性有 aaaaa a，由對(duì)偶原理，由對(duì)偶原理，aaaaa a 得證。得證。(4)(4)顯然顯然a(ab)aa(ab)a(13.5)(13.5)又由又由 aaaa，aba

11、aba 可得可得a(ab)a a(ab)a (13.6)(13.6)由式由式13.513.5和和13.613.6可得可得 a(ab) a(ab)a a，根據(jù)對(duì)偶原理，根據(jù)對(duì)偶原理，a(ab)a(ab)a a 得證。得證。定理定理11.211.2定理定理11.211.2 設(shè)設(shè)S, 是具有兩個(gè)二元運(yùn)算的代數(shù)系統(tǒng)，若對(duì)是具有兩個(gè)二元運(yùn)算的代數(shù)系統(tǒng)，若對(duì)于于* *和和 運(yùn)算適合運(yùn)算適合交換律交換律、結(jié)合律結(jié)合律、吸收律吸收律，則可以適當(dāng)定，則可以適當(dāng)定義義S S中的偏序中的偏序，使得，使得構(gòu)成一個(gè)格，且構(gòu)成一個(gè)格，且a,bSa,bS有有ababa a* *b b，ababa a b b。思路思路 (1

12、)(1)證明證明在在S S中中* *和和 運(yùn)算都適合冪等律運(yùn)算都適合冪等律。(2)(2)在在S S上定義二元關(guān)系上定義二元關(guān)系R R，并證明，并證明R R為偏序關(guān)系。為偏序關(guān)系。(3)(3)證明證明構(gòu)成格。構(gòu)成格。說(shuō)明說(shuō)明通過(guò)規(guī)定運(yùn)算及其基本性質(zhì)可以給出格的定義。通過(guò)規(guī)定運(yùn)算及其基本性質(zhì)可以給出格的定義。定理定理11.211.2 a aSS，由吸收律得，由吸收律得(1)(1)證明在證明在S S中中* *和和 運(yùn)算都適合冪等律運(yùn)算都適合冪等律。a a* *a a a a* *( (a a (a(a* *a)a) a a同理有同理有 a a a aa a。(2)(2)在在S S上定義二元關(guān)系上定義

13、二元關(guān)系R R， a,ba,bS S 有有 R R a a b bb b下面證明下面證明R R在在S S上的偏序。上的偏序。根據(jù)冪等律，根據(jù)冪等律， a aSS都有都有a a a aa a，即即RR，所以所以R R在在S S上是自反的。上是自反的。 a,bS a,bS 有有aRbaRb且且bRabRa a a b bb b且且b b a aa a a ab b a aa a b bb (b (由于由于a a b=b b=b a)a)所以所以R R在在S S上是反對(duì)稱的。上是反對(duì)稱的。定理定理11.211.2 a,b,ca,b,cSS 有有aRbaRb且且bRc bRc a a b bb b 且

14、且 b b c cc c a a c ca a (b(b c)c) a a c c(a(a b)b) c c a a c cb b c cc c aRc aRc這就證明了這就證明了R R在在S S上是傳遞的。上是傳遞的。綜上所述，綜上所述，R R為為S S上的偏序。上的偏序。以下把以下把R R記作記作。定理定理11.211.2(3) (3) 證明證明S構(gòu)成格。構(gòu)成格。 即證明即證明ababa a b b，ababa a* *b b 。 a,ba,bSS 有有a a (a(a b)b)(a(a a)a) b ba a b bb b (a(a b)b)a a (b(b b)b)a a b b根據(jù)根

15、據(jù)的定義有的定義有 aaaa b b和和baba b b，所以所以a a b b是是a,ba,b的上界。的上界。假設(shè)假設(shè) c c為為a,ba,b的上界，的上界，則有則有a a c cc c和和b b c cc c，從而有從而有(a(a b)b) c c a a (b(b c)c) a a c c c c這就證明了這就證明了a a bcbc，所以所以a a b b是是a,ba,b的最小上界，即的最小上界，即 ababa a b b為證為證a a* *b b是是a,ba,b的最大下界，的最大下界， 先證先證首先由首先由a a b bb b 可知可知 a a* *b b a a* *(a(a b)b

16、) a a反之由反之由a a* *b ba a 可知可知a a b b (a(a* *b)b) b b b b (b(b* *a)a)b b再由式再由式(13.7)(13.7)和和的定義有的定義有 ab ab a a* *b ba a， 依照前邊的證明依照前邊的證明, ,類似地可證類似地可證 a a* *b b是是a,ba,b的最大下界，的最大下界， 即即 ababa a* *b b。a a b bb b a a* *b ba a(13.7)(13.7)格的等價(jià)定義格的等價(jià)定義根據(jù)定理根據(jù)定理11.211.2，可以給出格的另一個(gè)等價(jià)定義。，可以給出格的另一個(gè)等價(jià)定義。定義定義11.311.3

17、設(shè)設(shè)S, 是代數(shù)系統(tǒng)，是代數(shù)系統(tǒng)，* *和和 是二元運(yùn)算，如果是二元運(yùn)算，如果* *和和 滿滿足交換律，結(jié)合律和吸收律，則足交換律，結(jié)合律和吸收律，則S, 構(gòu)成一個(gè)構(gòu)成一個(gè)格格( (lattice) )。說(shuō)明說(shuō)明格中的冪等律可以由吸收律推出。格中的冪等律可以由吸收律推出。以后我們不再區(qū)別是偏序集定義的格，以后我們不再區(qū)別是偏序集定義的格，還是代數(shù)系統(tǒng)定義的格，而統(tǒng)稱為格還是代數(shù)系統(tǒng)定義的格，而統(tǒng)稱為格L L。格的性質(zhì)格的性質(zhì)定理定理11.311.3 設(shè)設(shè)L L是格，則是格，則 a,bL a,bL 有有ab ab ababa a ab abb b證明證明 先證先證 ab ab ab aba a由

18、由aaaa和和abab可知，可知，a a是是a,ba,b的下界，的下界，故故aabaab。顯然又有。顯然又有abaaba。由反對(duì)稱性得由反對(duì)稱性得ababa a。再證再證 ababa a ab abb b。根據(jù)吸收律有根據(jù)吸收律有 b bb(ba)b(ba)由由ababa a得得 b bba, ba, 即即ababb b。最后證最后證ababb b ab ab。由由aabaab得得 aabaabb b。 格的性質(zhì)格的性質(zhì)定理定理11.411.4 設(shè)設(shè)L L是格，是格， a,b,c,dLa,b,c,dL，若，若abab且且cdcd，則，則acbdacbd，acbdacbd證明證明 acabaca

19、baccdaccd因此，因此， acbdacbd。同理可證同理可證 acbdacbd。例例11.511.5 例例11.511.5 設(shè)設(shè)L L是格，證明是格，證明 a,b,cL a,b,cL 有有a(bc)(ab)(ac)a(bc)(ab)(ac)證明證明由由 aaaa，bcb bcb 得得a(bc)aba(bc)ab由由 aaaa，bcc bcc 得得a(bc)aca(bc)ac從而得到從而得到 a(bc)(ab)(ac)a(bc)(ab)(ac)說(shuō)明說(shuō)明在格中分配不等式成立。在格中分配不等式成立。一般說(shuō)來(lái)，格中的一般說(shuō)來(lái)，格中的和和運(yùn)算并不是滿足分配律的。運(yùn)算并不是滿足分配律的。本節(jié)小結(jié)本節(jié)

20、小結(jié)q 偏序集構(gòu)成格的條件：任意二元子集都有最大下界和最偏序集構(gòu)成格的條件：任意二元子集都有最大下界和最小上界。小上界。q 格的實(shí)例：正整數(shù)的因子格，冪集格，子群格。格的實(shí)例：正整數(shù)的因子格，冪集格，子群格。q 格的性質(zhì)：對(duì)偶原理，格中算律（交換、結(jié)合、冪等、格的性質(zhì)：對(duì)偶原理，格中算律（交換、結(jié)合、冪等、吸收），保序性，分配不等式。吸收），保序性，分配不等式。q 格作為代數(shù)系統(tǒng)的定義。格作為代數(shù)系統(tǒng)的定義。q 格的證明方法格的證明方法子格子格定義定義11.411.4 設(shè)設(shè)是格，是格，S S是是L L的非空子集，若的非空子集，若S S關(guān)于關(guān)于L L中中的運(yùn)算的運(yùn)算和和仍構(gòu)成格，則稱仍構(gòu)成格，則

21、稱S S是是L L的的子格子格。例例11.611.6 設(shè)格設(shè)格L L如右圖所示。令如右圖所示。令S S1 1a,e,f,ga,e,f,gS S2 2a,b,e,ga,b,e,g則則S S1 1不是不是L L的子格，的子格，S S2 2是是L L的子格。的子格。因?yàn)閷?duì)于因?yàn)閷?duì)于e e和和f,f,有有efefc c，但但c c S S1 1。11.2 11.2 分配格、有補(bǔ)格與布爾代數(shù)分配格、有補(bǔ)格與布爾代數(shù)q 一般說(shuō)來(lái)，格中運(yùn)算一般說(shuō)來(lái)，格中運(yùn)算對(duì)對(duì)滿足分配不等式，滿足分配不等式，即即 a,b,cLa,b,cL，有，有a(bc)(ab)(ac)a(bc)(ab)(ac)但是不一定滿足分配律。滿足

22、分配律的格稱為但是不一定滿足分配律。滿足分配律的格稱為分配格分配格。定義定義11.511.5 設(shè)設(shè)是格，若是格，若 a,b,cLa,b,cL，有，有a(bc)a(bc)(ab)(ac)(ab)(ac)a(bc)a(bc)(ab)(ac)(ab)(ac)則稱則稱L L為為分配格分配格。說(shuō)明說(shuō)明上面兩個(gè)等式互為對(duì)偶式。上面兩個(gè)等式互為對(duì)偶式。在證明在證明L L為分配格時(shí)，只須證明其中的一個(gè)等式即可。為分配格時(shí)，只須證明其中的一個(gè)等式即可。例例11.711.7L L1 1和和L L2 2是分配格，是分配格，L L3 3和和L L4 4不是分配格。不是分配格。在在L L3 3中，中，b(cd)b(cd

23、) bebeb b(bc)(bd)(bc)(bd)aaaaa a在在L L4 4中中, ,c(bd)c(bd) cacac c(cb)(cd)(cb)(cd)ededd d鉆石格鉆石格五角格五角格分配格的判別分配格的判別定理定理11.511.5 設(shè)設(shè)L L是格，則是格，則L L是分配格當(dāng)且僅當(dāng)是分配格當(dāng)且僅當(dāng)L L中不含有與鉆石中不含有與鉆石格或五角格同構(gòu)的子格。格或五角格同構(gòu)的子格。證明證明略。略。推論推論(1) (1) 小于五元的格都是分配格。小于五元的格都是分配格。(2) (2) 任何一條鏈都是分配格。任何一條鏈都是分配格。例例11.811.8說(shuō)明下圖中的格是否為分配格，為什么？說(shuō)明下圖

24、中的格是否為分配格，為什么？L L1 1, L, L2 2和和L L3 3都不是分配格。都不是分配格。a,b,c,d,ea,b,c,d,e是是L L1 1的子格，并且同構(gòu)于鉆石格。的子格，并且同構(gòu)于鉆石格。a,b,c,e,fa,b,c,e,f是是L L2 2的子格，并且同構(gòu)于五角格。的子格，并且同構(gòu)于五角格。a,c,b,e,fa,c,b,e,f是是L L3 3的子格，也同構(gòu)于鉆石格。的子格，也同構(gòu)于鉆石格。 格的全下界和全上界格的全下界和全上界定義定義11.611.6 設(shè)設(shè)L L是格，是格，若存在若存在aLaL使得使得 xLxL有有axax，則稱，則稱a a為為L(zhǎng) L的的全下界全下界；若存在若

25、存在bLbL使得使得 xLxL有有xbxb，則稱，則稱b b為為L(zhǎng) L的的全上界全上界。 命題命題格格L L若存在全下界或全上界，一定是唯一的。若存在全下界或全上界，一定是唯一的。證明證明以全下界為例，假若以全下界為例，假若a a1 1和和a a2 2都是格都是格L L的全下界的全下界, ,則有則有a a1 1aa2 2和和a a2 2aa1 1。根據(jù)偏序關(guān)系的反對(duì)稱性必有根據(jù)偏序關(guān)系的反對(duì)稱性必有a a1 1a a2 2。記法記法將格將格L L的的全下界記為全下界記為0 0，全上界記為全上界記為1 1。有界格有界格定義定義11.711.7 設(shè)設(shè)L L是格，若是格，若L L存在全下界和全上界，

26、則稱存在全下界和全上界，則稱L L為為有界格有界格，并將并將L L記為記為。說(shuō)明說(shuō)明有限格有限格L L一定是有界格。一定是有界格。舉例舉例q 設(shè)設(shè)L L是是n n元格元格，且，且L Laa1 1,a,a2 2,a,an n ，那么，那么a a1 1aa2 2aan n是是L L的的全下界，而全下界，而a a1 1aa2 2aan n是是L L的全上界。因此的全上界。因此L L是有界格。是有界格。q 對(duì)于對(duì)于無(wú)限格無(wú)限格L L來(lái)說(shuō)，有的是有界格，有的不是有界格。來(lái)說(shuō)，有的是有界格，有的不是有界格。q 如集合如集合B B的的冪集格冪集格，不管，不管B B是有窮集還是無(wú)窮集，是有窮集還是無(wú)窮集，它都

27、是有界格。它的全下界是空集它都是有界格。它的全下界是空集，全上界是全上界是B B。q 整數(shù)集整數(shù)集Z Z關(guān)于通常數(shù)的小于或等于關(guān)系構(gòu)成的格不是有界格，關(guān)于通常數(shù)的小于或等于關(guān)系構(gòu)成的格不是有界格，因?yàn)椴淮嬖谧钚『妥畲蟮恼麛?shù)。因?yàn)椴淮嬖谧钚『妥畲蟮恼麛?shù)。有界格的性質(zhì)有界格的性質(zhì)定理（補(bǔ)充）定理（補(bǔ)充） 設(shè)設(shè)是有界格，則是有界格，則 aLaL有有a0a00 0a0a0a aa1a1a aa1a11 1證明證明由由 a00 a00 和和 0a0 0a0 可知可知 a0a00 0。說(shuō)明說(shuō)明 在有界格中，在有界格中，全下界全下界0 0是關(guān)于是關(guān)于運(yùn)算的零元，運(yùn)算的零元，運(yùn)算的單位元。運(yùn)算的單位元。全上界

28、全上界1 1是關(guān)于是關(guān)于運(yùn)算的零元，運(yùn)算的零元，運(yùn)算的單位元。運(yùn)算的單位元。對(duì)偶原理對(duì)偶原理 對(duì)于涉及到有界格的命題，如果其中含有全下界對(duì)于涉及到有界格的命題，如果其中含有全下界0 0或或全上界全上界1 1，在求該命題的對(duì)偶命題時(shí)，必須將，在求該命題的對(duì)偶命題時(shí)，必須將0 0替換成替換成1 1，而，而將將1 1替換成替換成0 0。例如例如a0a00 0 和和 a1a11 1 互為對(duì)偶命題，互為對(duì)偶命題， a0a0a a 和和 a1a1a a 互為對(duì)偶命題?；閷?duì)偶命題。有界格中的補(bǔ)元有界格中的補(bǔ)元定義定義11.811.8 設(shè)設(shè)是有界格，是有界格，aLaL，若存在若存在bL bL 使得使得aba

29、b0 0 和和 abab1 1成立，則稱成立，則稱b b是是a a的的補(bǔ)元補(bǔ)元。說(shuō)明說(shuō)明若若b b是是a a的補(bǔ)元，那么的補(bǔ)元，那么a a也是也是b b的補(bǔ)元。的補(bǔ)元。換句話說(shuō)，換句話說(shuō)，a a和和b b互為補(bǔ)元。互為補(bǔ)元。例例11.911.9考慮下圖中的四個(gè)格?？紤]下圖中的四個(gè)格。L L1 1中的中的a a與與c c互為補(bǔ)元，其中互為補(bǔ)元，其中a a為全下界，為全下界，c c為全上界，為全上界，b b沒(méi)有補(bǔ)元。沒(méi)有補(bǔ)元。L L2 2中的中的a a與與d d互為補(bǔ)元，其中互為補(bǔ)元，其中a a為全下界，為全下界，d d為全上界，為全上界，b b與與c c也互為也互為補(bǔ)元。補(bǔ)元。L L3 3中的中

30、的a a與與e e互為補(bǔ)元，其中互為補(bǔ)元，其中a a為全下界，為全下界，e e為全上界，為全上界，b b的補(bǔ)元是的補(bǔ)元是c c和和d d，c c的補(bǔ)元是的補(bǔ)元是b b和和d d，d d的補(bǔ)元是的補(bǔ)元是b b和和c c。b,c,db,c,d每個(gè)元素都有兩每個(gè)元素都有兩個(gè)補(bǔ)元。個(gè)補(bǔ)元。L L4 4中的中的a a與與e e互為補(bǔ)元。其中互為補(bǔ)元。其中a a為全下界。為全下界。e e為全上界。為全上界。b b的補(bǔ)元是的補(bǔ)元是c c和和d d，c c的補(bǔ)元是的補(bǔ)元是b b，d d的補(bǔ)元是的補(bǔ)元是b b。有界格中補(bǔ)元的說(shuō)明有界格中補(bǔ)元的說(shuō)明在任何有界格中，在任何有界格中，q 全下界全下界0 0與全上界與全

31、上界1 1互補(bǔ)。互補(bǔ)。 q 對(duì)于其他元素，可能存在補(bǔ)元，也可能不存在補(bǔ)元。對(duì)于其他元素，可能存在補(bǔ)元，也可能不存在補(bǔ)元。q 如果存在，可能是唯一的，也可能是多個(gè)補(bǔ)元。如果存在，可能是唯一的，也可能是多個(gè)補(bǔ)元。q 對(duì)于有界分配格，如果它的元素存在補(bǔ)元，一定是唯一的。對(duì)于有界分配格，如果它的元素存在補(bǔ)元，一定是唯一的。 有界分配格中補(bǔ)元的唯一性有界分配格中補(bǔ)元的唯一性定理定理11.611.6 設(shè)設(shè)是有界分配格。是有界分配格。若若aLaL，且對(duì)于，且對(duì)于a a存在補(bǔ)元存在補(bǔ)元b b，則，則b b是是a a的唯一補(bǔ)元。的唯一補(bǔ)元。證明證明假設(shè)假設(shè)cLcL也是也是a a的補(bǔ)元，則有的補(bǔ)元，則有acac1

32、 1，acac0 0又知又知b b是是a a的補(bǔ)元，故的補(bǔ)元，故abab1 1，abab0 0 從而得到從而得到acacabab，acacab ab 由于由于L L是分配格，根據(jù)定理是分配格，根據(jù)定理13.713.7，b bc c。 有補(bǔ)格的定義有補(bǔ)格的定義定義定義11.911.9 設(shè)設(shè)是有界格，若是有界格，若L L中所有元素都有補(bǔ)中所有元素都有補(bǔ)元存在，則稱元存在，則稱L L為為有補(bǔ)格有補(bǔ)格。L L2 2,L,L3 3和和L L4 4是有補(bǔ)是有補(bǔ)格，格，L L1 1不是有補(bǔ)格。不是有補(bǔ)格。L L2 2和和L L3 3是有補(bǔ)格，是有補(bǔ)格，L L1 1不是有補(bǔ)格。不是有補(bǔ)格。本節(jié)小結(jié)本節(jié)小結(jié)q

33、如果格中一個(gè)運(yùn)算對(duì)另一個(gè)運(yùn)算是可分配的，稱這個(gè)格是分如果格中一個(gè)運(yùn)算對(duì)另一個(gè)運(yùn)算是可分配的，稱這個(gè)格是分配格。配格。 q 分配格的兩種判別法：分配格的兩種判別法：不存在與鉆石格或五角格同構(gòu)的子格；不存在與鉆石格或五角格同構(gòu)的子格；對(duì)于任意元素對(duì)于任意元素a,b,c,a,b,c,有有 ababacac且且ababacacb bc c。 q 有界格的定義及其實(shí)例。有界格的定義及其實(shí)例。 q 格中元素的補(bǔ)元及其性質(zhì)（分配格中補(bǔ)元的唯一性）。格中元素的補(bǔ)元及其性質(zhì)（分配格中補(bǔ)元的唯一性）。 q 有補(bǔ)格的定義。有補(bǔ)格的定義。布爾代數(shù)布爾代數(shù)定義定義11.1011.10 如果一個(gè)格是如果一個(gè)格是有補(bǔ)分配格

34、有補(bǔ)分配格，則稱它為，則稱它為布爾格布爾格或或布爾布爾代數(shù)代數(shù)。說(shuō)明說(shuō)明在布爾代數(shù)中，每個(gè)元素都存在著唯一的補(bǔ)元。在布爾代數(shù)中，每個(gè)元素都存在著唯一的補(bǔ)元?？梢园亚笱a(bǔ)元的運(yùn)算看作是布爾代數(shù)中的一元運(yùn)算?？梢园亚笱a(bǔ)元的運(yùn)算看作是布爾代數(shù)中的一元運(yùn)算?？梢园岩粋€(gè)布爾代數(shù)標(biāo)記為可以把一個(gè)布爾代數(shù)標(biāo)記為B,0,1，為求補(bǔ)運(yùn)算為求補(bǔ)運(yùn)算, , aBaB，a a是是a a的補(bǔ)元。的補(bǔ)元。例例11.1011.10例例11.1011.10 設(shè)設(shè)S S1101101,2,5,10,11,22,55,1101,2,5,10,11,22,55,110是是110110的正因子集合。的正因子集合。令令gcd,lcmgc

35、d,lcm分別表示求最大公約數(shù)和最小公倍數(shù)的運(yùn)算。問(wèn)分別表示求最大公約數(shù)和最小公倍數(shù)的運(yùn)算。問(wèn)S,gcd,lcm是否構(gòu)成布爾代數(shù)？為什么？是否構(gòu)成布爾代數(shù)？為什么？解答解答 證明證明S,gcd,lcm構(gòu)成格。構(gòu)成格。容易驗(yàn)證容易驗(yàn)證 x,y,zSx,y,zS110110，有，有g(shù)cd(x,y)Sgcd(x,y)S110110lcm(x,y)Slcm(x,y)S110110gcd(x,y)gcd(x,y)gcd(y,x) gcd(y,x) lcm(x,y)lcm(x,y)lcm(y,x)lcm(y,x)gcd(gcd(x,y),z)gcd(gcd(x,y),z)gcd(x,gcd(y,z)gcd

36、(x,gcd(y,z)lcm(lcm(x,y),z)lcm(lcm(x,y),z)lcm(x,lcm(y,z)lcm(x,lcm(y,z)gcd(x,lcm(x,y)gcd(x,lcm(x,y)x xlcm(x,gcd(x,y)lcm(x,gcd(x,y)x x二元運(yùn)算二元運(yùn)算交換律交換律結(jié)合律結(jié)合律吸收律吸收律例例11.1011.10證明證明 S,gcd,lcm是分配格。是分配格。易驗(yàn)證易驗(yàn)證 x,y,zS x,y,zS110110 有有g(shù)cd(x,lcm(y,z)gcd(x,lcm(y,z)lcm(gcd(x,y),gcd(x,z)lcm(gcd(x,y),gcd(x,z)證明證明 S,g

37、cd,lcm是有補(bǔ)格。是有補(bǔ)格。1 1 為為S S110110中的全下界中的全下界110110為為S S110110中的全上界中的全上界1 1和和110110互為補(bǔ)元，互為補(bǔ)元，2 2和和5555互為補(bǔ)元，互為補(bǔ)元，5 5和和2222互為補(bǔ)元，互為補(bǔ)元，1010和和1111互為補(bǔ)元?；檠a(bǔ)元。綜上所述，綜上所述，S,gcd,lcm為布爾代數(shù)。為布爾代數(shù)。例例11.1011.10（2 2）例例11.1011.10（2 2） 設(shè)設(shè)B B為任意集合為任意集合, ,證明證明B B的的冪集格冪集格P(B),B構(gòu)成布爾代數(shù)，稱為構(gòu)成布爾代數(shù)，稱為集合代數(shù)集合代數(shù)。證明證明P(B)P(B)關(guān)于關(guān)于和和構(gòu)成格

38、，因?yàn)闃?gòu)成格，因?yàn)楹秃瓦\(yùn)算滿足交換律、結(jié)合律和吸收律。運(yùn)算滿足交換律、結(jié)合律和吸收律。由于由于和和互相可分配，因此互相可分配，因此P(B)P(B)是分配格，是分配格，且全下界是空集且全下界是空集, ,全上界是全上界是B B。根據(jù)絕對(duì)補(bǔ)的定義，取全集為根據(jù)絕對(duì)補(bǔ)的定義，取全集為B B， xP(B)xP(B)，x x是是x x的補(bǔ)元。的補(bǔ)元。從而證明從而證明P(B)P(B)是有補(bǔ)分配格，即布爾代數(shù)。是有補(bǔ)分配格，即布爾代數(shù)。 布爾代數(shù)的性質(zhì)布爾代數(shù)的性質(zhì)定理定理11.711.7 設(shè)設(shè)B,0,1是布爾代數(shù)，則是布爾代數(shù)，則 (1) (1) aBaB，(a(a) )a a (2) (2) a,bBa,

39、bB，(ab)(ab)a abb,(ab),(ab)a abb說(shuō)明說(shuō)明(1)(1)稱為稱為雙重否定律雙重否定律。(2)(2)稱為稱為德摩根律德摩根律。命題代數(shù)與集合代數(shù)的雙重否定律與德摩根律實(shí)際上命題代數(shù)與集合代數(shù)的雙重否定律與德摩根律實(shí)際上是這個(gè)定理的特例。是這個(gè)定理的特例?？梢宰C明德摩根律對(duì)有限個(gè)元素也是正確的。可以證明德摩根律對(duì)有限個(gè)元素也是正確的。證明證明(1) (a(1) (a) )是是a a的補(bǔ)元，的補(bǔ)元，a a也是也是a a的補(bǔ)元。的補(bǔ)元。由補(bǔ)元的唯一性得由補(bǔ)元的唯一性得(a(a) )a a。定理定理11.7(2)11.7(2)的證明的證明(2) (2) a,bBa,bB，(ab

40、)(ab)a abb,(ab),(ab)a abb(ab)(ab)(a(abb) ) ( (aaaabb)()(b baabb) ) (1b(1b)( a)( a1)1) 1111 1 1(ab)(ab)(a(abb) ) ( (a abbaa)(a)(abbbb) ) (0b)(a0)(0b)(a0) 00000 0所以所以a abb是是abab的補(bǔ)元，根據(jù)補(bǔ)元的唯一性有的補(bǔ)元，根據(jù)補(bǔ)元的唯一性有(ab)(ab)a abb同理可證同理可證(ab)(ab)= a= abb。 布爾代數(shù)作為代數(shù)系統(tǒng)的定義布爾代數(shù)作為代數(shù)系統(tǒng)的定義定義定義11.1111.11 設(shè)設(shè)B, 是代數(shù)系統(tǒng)，是代數(shù)系統(tǒng)，*

41、*和和 是二元運(yùn)算。是二元運(yùn)算。若若* *和和運(yùn)算滿足：運(yùn)算滿足：(1)(1) 交換律交換律，即，即 a,bB a,bB 有有a a* *b bb b* *a a，a a b bb b a a (2)(2) 分配律分配律，即，即 a,b,cBa,b,cB有有a a* *(b(b c)c)(a(a* *b)b) (a(a* *c)c)a a (b(b* *c)c)(a(a b)b)* *(a(a c)c) (3)(3) 同一律同一律，即存在，即存在0,1B0,1B，使得，使得 aB aB 有有a a* *1 1a a，a a 0 0a a (4)(4) 補(bǔ)元律補(bǔ)元律，即，即 aB,aB,存在存在

42、a aBB，使得，使得a a* *a a0 0，a a a a1 1 則稱則稱B, 是一個(gè)是一個(gè)布爾代數(shù)布爾代數(shù)。 關(guān)于布爾代數(shù)定義的說(shuō)明關(guān)于布爾代數(shù)定義的說(shuō)明所謂所謂同一律就是指運(yùn)算含有單位元的性質(zhì)同一律就是指運(yùn)算含有單位元的性質(zhì)，這里的，這里的1 1是是* *運(yùn)算的運(yùn)算的單位元，單位元，0 0是運(yùn)算是運(yùn)算 的單位元。的單位元?？梢宰C明可以證明1 1和和0 0分別也是分別也是 和和* *運(yùn)算的零元。運(yùn)算的零元。 aBaB有有 a a 1 1 ( (a a 1)1)* *1 1 （同一律）（同一律） 1 1* *( (a a 1) 1) （交換律）（交換律） ( (a a a a) )* *(

43、 (a a 1) 1) （補(bǔ)元律）（補(bǔ)元律） a a ( (aa* *1 1) ) （分配律）（分配律） a a aa （同一律）（同一律） 1 1 （補(bǔ)元律）（補(bǔ)元律）同理可證同理可證 a a* *0 00 0。關(guān)于布爾代數(shù)定義的說(shuō)明關(guān)于布爾代數(shù)定義的說(shuō)明為證明以上定義的為證明以上定義的B, 是布爾代數(shù)，只需證明它是一是布爾代數(shù)，只需證明它是一個(gè)格，即個(gè)格，即證明證明* *和和運(yùn)算滿足結(jié)合律和吸收律。運(yùn)算滿足結(jié)合律和吸收律。證明吸收律證明吸收律， a,bBa,bB有有 a a (a(a* *b)b) ( (a a* *1)1) ( (a a* *b)b)（同一律）（同一律） a a* *(

44、(1 1 b b) )（分配律）（分配律） a a* *1 1 （1 1是是 運(yùn)算的零元運(yùn)算的零元) ) a a （同一律）（同一律）同理有同理有 a a* *(a(a b)b)a a。關(guān)于布爾代數(shù)定義的說(shuō)明關(guān)于布爾代數(shù)定義的說(shuō)明為證結(jié)合律，先證以下命題：為證結(jié)合律，先證以下命題： a,b,cBa,b,cB，a a b ba a c c 且且 a a b ba a c c b bc c由由 a a b ba a c c 且且 a a b ba a c c 可得可得(a(a b)b)* *(a(a b)b)(a(a c)c)* *(a(a c) c) 由分配律和交換律得由分配律和交換律得(a(a

45、* *a a ) ) b b(a(a* *a a ) ) c c由補(bǔ)元律得由補(bǔ)元律得 0 0 b b0 0 c c由同一律和交換律得由同一律和交換律得b bc c關(guān)于布爾代數(shù)定義的說(shuō)明關(guān)于布爾代數(shù)定義的說(shuō)明使用這個(gè)命題，為證明使用這個(gè)命題，為證明 (a(a* *b)b)* *c ca a* *( (b b* *c c) )，只需證明以下，只需證明以下兩個(gè)等式：兩個(gè)等式：(1) a(1) a (a(a* *b)b)* *c)c)a a (a(a* *( (b b* *c c)(2) a(2) a (a(a* *b)b)* *c)c)a a (a(a* *( (b b* *c c)先證明第一個(gè)等式

46、，由吸收律有先證明第一個(gè)等式，由吸收律有 a a (a(a* *( (b b* *c)c)a a a a (a(a* *b)b)* *c)c) ( (a a (a(a* *b)b)* *(a(a c)c)( (分配律分配律) ) a a* *(a(a c)c)( (吸收律吸收律) ) a a所以所以(1)(1)式成立。式成立。關(guān)于布爾代數(shù)定義的說(shuō)明關(guān)于布爾代數(shù)定義的說(shuō)明下面證明下面證明(2)(2)式：式： a a (a(a* *b)b)* *c)c)a a (a(a* *( (b b* *c c) a a (a(a* *( (b b* *c c) ( (a a a a) )* *( (a a

47、( (b b* *c c) ) ( (分配律分配律) ) 1 1* *( (a a ( (b b* *c c) ) ( (交換律交換律, ,補(bǔ)元律補(bǔ)元律) ) a a ( (b b* *c c) ) ( (交換律交換律, ,同一律同一律) ) a a (a(a* *b)b)* *c)c) ( (a a (a(a* *b)b)* *(a(a c) (c) (分配律分配律) ) (a a a a) )* *(a(a b)b)* *(a(a c)c) ( (分配律分配律) ) ( (1 1* *(a(a b)b)* *(a(a c) c) ( (交換律交換律, ,補(bǔ)元律補(bǔ)元律) ) ( (a a b

48、)b)* *( (a a c) (c) (交換律交換律, ,同一律同一律) ) a a ( (b b* *c c) )( (分配律分配律) )所以（所以（2 2）式成立。）式成立。有限布爾代數(shù)的結(jié)構(gòu)有限布爾代數(shù)的結(jié)構(gòu)定義定義11.1211.12 設(shè)設(shè)L L是格，是格，0L0L，aLaL，若，若 bL bL 有有0 0ba ba b ba a則稱則稱a a是是L L中的中的原子原子。 考慮右圖中的幾個(gè)格。考慮右圖中的幾個(gè)格。L L1 1的原子是的原子是a a。L L2 2的原子是的原子是a,b,ca,b,c。L L3 3的原子是的原子是a a和和b b。若若L L是正整數(shù)是正整數(shù)n n的全體正因

49、子關(guān)于整除關(guān)系構(gòu)成的格，則的全體正因子關(guān)于整除關(guān)系構(gòu)成的格，則L L的原子恰的原子恰為為n n的全體質(zhì)因子。的全體質(zhì)因子。若若L L是集合是集合B B的冪集合，則的冪集合，則L L的原子就是由的原子就是由B B中元素構(gòu)成的單元集。中元素構(gòu)成的單元集。有限布爾代數(shù)的表示定理有限布爾代數(shù)的表示定理定理定理11.8 (11.8 (有限布爾代數(shù)的表示定理有限布爾代數(shù)的表示定理) ) 設(shè)設(shè)B B是有限布爾代數(shù)，是有限布爾代數(shù)，A A是是B B的全體原子構(gòu)成的集合的全體原子構(gòu)成的集合，則，則B B同構(gòu)于同構(gòu)于A A的冪集代數(shù)的冪集代數(shù)P(A)P(A)。證明證明任取任取xBxB，令，令T(x)T(x)a|a

50、B,aa|aB,a是原子且是原子且aax x 則則T(x)T(x) A A，定義函數(shù)，定義函數(shù) ：BBP(A)P(A)， (x)(x)T(x)T(x)， xBxB下面證明下面證明 是是B B到到P(A)P(A)的同構(gòu)映射。的同構(gòu)映射。任取任取x,yBx,yB， b b 有有 bbT(xT(xy y) ) bA bA 且且 bbxxy y (bA (bA且且bbx) x) 且且 (bA(bA且且by)by) b bT(x)T(x)且且bbT(T(y y) ) b bT(x)T(y)T(x)T(y)從而有從而有 T(xT(xy y) )T(x)T(y)T(x)T(y)，即即 x,yx,y B B

51、有有 (x(xy y) ) (x)(x) (y)(y)。定理定理11.811.8證明證明任取任取x,yx,yB B，設(shè)，設(shè)x xa a1 1a a2 2a an n，y yb b1 1b b2 2b bm m是是x,yx,y的原子表示，則的原子表示，則x xy ya a1 1a a2 2a an nb b1 1b b2 2b bm m由引理由引理2 2可知可知T(xT(xy)y)aa1 1,a,a2 2, ,a,an n,b,b1 1,b,b2 2, , , ,b bm m 又由于又由于T(x)T(x)aa1 1,a,a2 2, , ,a ,an n ，T(y)T(y)bb1 1,b,b2 2

52、, , , ,b bm m 所以所以 T(xT(xy)y)T(x)T(y)T(x)T(y)即即 (x(xy)y) (x)(x) (y)(y)定理定理11.811.8證明證明任取任取xxB B，存在，存在x x B B 使得使得xxxx 1 1， xxxx 0 0因此有因此有 (x)(x) (x(x ) ) (xx(xx ) ) (1)(1)A A (x)(x) (x(x ) ) (xx(xx ) ) (0)(0)而而和和A A分別為分別為P(P(A A) )的全下界和全上界，的全下界和全上界，因此因此 (x(x ) )是是 (x)(x)在在P(P(A A) )中的補(bǔ)元，即中的補(bǔ)元，即 (x(x

53、 ) ) (x)(x)綜上所述，綜上所述， 是是B B到到P(A)P(A)的同態(tài)映射。的同態(tài)映射。定理定理11.811.8證明證明下面證明下面證明 為雙射。為雙射。假設(shè)假設(shè) (x)(x) (y)(y)，則有，則有T(x)T(x)T(y)T(y)aa1 1,a,a2 2, , ,a ,an n 由引理由引理2 2可知可知 x xa a1 1a a2 2a an ny y于是于是 為單射。為單射。任取任取bb1 1,b,b2 2, , , ,b bm mP(A)P(A)，令令x xb b1 1b b2 2b bm m ，則，則 (x)(x)T(x)T(x)bb1 1,b,b2 2, , , ,b bm m 于是于是 為滿射。為滿射。定理得證。定理得證。例子例子考慮考慮110110的正因子的集合的正因子的集合S S110110關(guān)于關(guān)于gcd, lcmgcd, lcm運(yùn)算構(gòu)成的布爾代數(shù)。運(yùn)算構(gòu)成的布爾代數(shù)。它的原子是它的原子是2 2、5 5和和1111，因此原子的集合，因此原子的集合A A2,5,112,5,11。冪集冪集P(A)P(A) ,2,5,11,2,5,2,11,5,11,2,5,11,2,5,11,2,5,2,11,5,11,2,5,11。冪集代數(shù)是冪集代數(shù)是P(