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

1、第11章 格與布爾代數(shù)離離 散散 數(shù)數(shù) 學學中國地質(zhì)大學本科生課程中國地質(zhì)大學本科生課程本章內(nèi)容本章內(nèi)容11.1 11.1 格的定義與性質(zhì)格的定義與性質(zhì)11.2 11.2 分配格、有補格與布爾代數(shù)分配格、有補格與布爾代數(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)于偏序作成一個作成一個格格( (lattice) )。說明：說明：由于最小上界和最大下界的唯一性，可以把求由于最小上界和最大下界的唯一性，可以把

2、求 x, ,y 的最的最小上界和最大下界看成小上界和最大下界看成x x與與y y的二元運算的二元運算和和。xy：表示：表示x x與與y y的最小上界的最小上界xy：表示：表示x x和和y y的最大下界。的最大下界。 本章出現(xiàn)的本章出現(xiàn)的和和符號只代表格中的運算，而不再有其它的符號只代表格中的運算，而不再有其它的含義。含義。格的實例格的實例例例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)成格, ,并說明理由。并說明理由。(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。由于由于和和運算在運算在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沒有最大下界。沒有最大下界。(b)(b)中的中的b,db,d有兩個上界有兩個上界c c和和e,e,但沒有最小上界。但沒有最小上界。

5、(c)(c)中的中的b,cb,c有三個上界有三個上界d,e,f,d,e,f,但沒有最小上界。但沒有最小上界。(d)(d)中的中的a,ga,g沒有最大下界。沒有最大下界。例例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 對任意的對任意的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)成一個格，關(guān)于包含關(guān)系構(gòu)成一個格，稱為稱為G G的的子群格子群格。易見在易見在L(G)L(G)中，中，H H1 1HH2 2就是就是H H1 1HH2 2，H H1 1HH2 2就是就是H 。 對偶原理對偶原理定義定義11.211.2 設(shè)設(shè)f f是含有格中元素以及符號、是含有格中元素以及符號、和和的的命題。令命題。令f f* *是將是將f f中的中的替換成替換成，替換成替換成，替換成替換成，替換成替換成所得到的命題。稱所得到的命題。稱f f* *為為f f的的對偶命題對偶命題。例如例如 在格中令在格中令f f是是(ab)cc

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

8、，有了格的對偶原理，在證明格的性質(zhì)時，只須證明其中的一個命題即可。只須證明其中的一個命題即可。格的運算性質(zhì)格的運算性質(zhì)定理定理11.111.1 設(shè)設(shè)是格，則運算是格，則運算和和適合適合交換律交換律、結(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。由對偶原理，由對偶原理，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)系的反對稱性有根據(jù)偏序關(guān)系的反對稱性有(ab)c(ab)ca(bc)a(bc)由對偶原理，由對偶原理，(ab)c(ab)ca(bc)a(bc)得證。得證。定理定理11.111.1(3)(3)顯然顯然aaa,aaa,又由又由aaaa可得可得 aaaaaa。根據(jù)反對稱性有根據(jù)反對稱性有 aaaaa a，由對偶原理，由對偶原理，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ù)對偶原理，根據(jù)對偶原理，a(ab)a(ab)a a 得證。得證。定理定理11.211.2定理定理11.211.2 設(shè)設(shè)S, 是具有兩個二元運算的代數(shù)系統(tǒng)，若對是具有兩個二元運算的代數(shù)系統(tǒng)，若對于于* *和和 運算適合運算適合交換律交換律、結(jié)合律結(jié)合律、吸收律吸收律，則可以適當定，則可以適當定義義S S中的偏序中的偏序，使得，使得構(gòu)成一個格，且構(gòu)成一個格，且a,bSa,bS有有ababa a* *b b，ababa a b b。思路思路 (1

12、)(1)證明證明在在S S中中* *和和 運算都適合冪等律運算都適合冪等律。(2)(2)在在S S上定義二元關(guān)系上定義二元關(guān)系R R，并證明，并證明R R為偏序關(guān)系。為偏序關(guān)系。(3)(3)證明證明構(gòu)成格。構(gòu)成格。說明說明通過規(guī)定運算及其基本性質(zhì)可以給出格的定義。通過規(guī)定運算及其基本性質(zhì)可以給出格的定義。定理定理11.211.2 a aSS，由吸收律得，由吸收律得(1)(1)證明在證明在S S中中* *和和 運算都適合冪等律運算都適合冪等律。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上是反對稱的。上是反對稱的。定理定理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)格的等價定義格的等價定義根據(jù)定理根據(jù)定理11.211.2，可以給出格的另一個等價定義。，可以給出格的另一個等價定義。定義定義11.311.3

17、設(shè)設(shè)S, 是代數(shù)系統(tǒng)，是代數(shù)系統(tǒng)，* *和和 是二元運算，如果是二元運算，如果* *和和 滿滿足交換律，結(jié)合律和吸收律，則足交換律，結(jié)合律和吸收律，則S, 構(gòu)成一個構(gòu)成一個格格( (lattice) )。說明說明格中的冪等律可以由吸收律推出。格中的冪等律可以由吸收律推出。以后我們不再區(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。由反對稱性得由反對稱性得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)說明說明在格中分配不等式成立。在格中分配不等式成立。一般說來，格中的一般說來，格中的和和運算并不是滿足分配律的。運算并不是滿足分配律的。本節(jié)小結(jié)本節(jié)

20、小結(jié)q 偏序集構(gòu)成格的條件：任意二元子集都有最大下界和最偏序集構(gòu)成格的條件：任意二元子集都有最大下界和最小上界。小上界。q 格的實例：正整數(shù)的因子格，冪集格，子群格。格的實例：正整數(shù)的因子格，冪集格，子群格。q 格的性質(zhì)：對偶原理，格中算律（交換、結(jié)合、冪等、格的性質(zhì)：對偶原理，格中算律（交換、結(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中中的運算的運算和和仍構(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的子格。的子格。因為對于因為對于e e和和f,f,有有efefc c，但但c c S S1 1。11.2 11.2 分配格、有補格與布爾代數(shù)分配格、有補格與布爾代數(shù)q 一般說來，格中運算一般說來，格中運算對對滿足分配不等式，滿足分配不等式，即即 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為為分配格分配格。說明說明上面兩個等式互為對偶式。上面兩個等式互為對偶式。在證明在證明L L為分配格時，只須證明其中的一個等式即可。為分配格時，只須證明其中的一個等式即可。例例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是分配格當且僅當是分配格當且僅當L L中不含有與鉆石中不含有與鉆石格或五角格同構(gòu)的子格。格或五角格同構(gòu)的子格。證明證明略。略。推論推論(1) (1) 小于五元的格都是分配格。小于五元的格都是分配格。(2) (2) 任何一條鏈都是分配格。任何一條鏈都是分配格。例例11.811.8說明下圖中的格是否為分配格，為什么？說明下圖

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 L的的全下界全下界；若存在若

25、存在bLbL使得使得 xLxL有有xbxb，則稱，則稱b b為為L L的的全上界全上界。 命題命題格格L L若存在全下界或全上界，一定是唯一的。若存在全下界或全上界，一定是唯一的。證明證明以全下界為例，假若以全下界為例，假若a a1 1和和a a2 2都是格都是格L L的全下界的全下界, ,則有則有a a1 1aa2 2和和a a2 2aa1 1。根據(jù)偏序關(guān)系的反對稱性必有根據(jù)偏序關(guān)系的反對稱性必有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記為記為。說明說明有限格有限格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 對于對于無限格無限格L L來說，有的是有界格，有的不是有界格。來說，有的是有界格，有的不是有界格。q 如集合如集合B B的的冪集格冪集格，不管，不管B B是有窮集還是無窮集，是有窮集還是無窮集，它都

27、是有界格。它的全下界是空集它都是有界格。它的全下界是空集，全上界是全上界是B B。q 整數(shù)集整數(shù)集Z Z關(guān)于通常數(shù)的小于或等于關(guān)系構(gòu)成的格不是有界格，關(guān)于通常數(shù)的小于或等于關(guān)系構(gòu)成的格不是有界格，因為不存在最小和最大的整數(shù)。因為不存在最小和最大的整數(shù)。有界格的性質(zhì)有界格的性質(zhì)定理（補充）定理（補充） 設(shè)設(shè)是有界格，則是有界格，則 aLaL有有a0a00 0a0a0a aa1a1a aa1a11 1證明證明由由 a00 a00 和和 0a0 0a0 可知可知 a0a00 0。說明說明 在有界格中，在有界格中，全下界全下界0 0是關(guān)于是關(guān)于運算的零元，運算的零元，運算的單位元。運算的單位元。全上界

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

29、b0 0 和和 abab1 1成立，則稱成立，則稱b b是是a a的的補元補元。說明說明若若b b是是a a的補元，那么的補元，那么a a也是也是b b的補元。的補元。換句話說，換句話說，a a和和b b互為補元?；檠a元。例例11.911.9考慮下圖中的四個格。考慮下圖中的四個格。L L1 1中的中的a a與與c c互為補元，其中互為補元，其中a a為全下界，為全下界，c c為全上界，為全上界，b b沒有補元。沒有補元。L L2 2中的中的a a與與d d互為補元，其中互為補元，其中a a為全下界，為全下界，d d為全上界，為全上界，b b與與c c也互為也互為補元。補元。L L3 3中的中

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

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

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

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

34、有補分配格，則稱它為，則稱它為布爾格布爾格或或布爾布爾代數(shù)代數(shù)。說明說明在布爾代數(shù)中，每個元素都存在著唯一的補元。在布爾代數(shù)中，每個元素都存在著唯一的補元。可以把求補元的運算看作是布爾代數(shù)中的一元運算?？梢园亚笱a元的運算看作是布爾代數(shù)中的一元運算?？梢园岩粋€布爾代數(shù)標記為可以把一個布爾代數(shù)標記為B,0,1，為求補運算為求補運算, , aBaB，a a是是a a的補元。的補元。例例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ù)的運算。問分別表示求最大公約數(shù)和最小公倍數(shù)的運算。問S,gcd,lcm是否構(gòu)成布爾代數(shù)？為什么？是否構(gòu)成布爾代數(shù)？為什么？解答解答 證明證明S,gcd,lcm構(gòu)成格。構(gòu)成格。容易驗證容易驗證 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二元運算二元運算交換律交換律結(jié)合律結(jié)合律吸收律吸收律例例11.1011.10證明證明 S,gcd,lcm是分配格。是分配格。易驗證易驗證 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是有補格。是有補格。1 1 為為S S110110中的全下界中的全下界110110為為S S110110中的全上界中的全上界1 1和和110110互為補元，互為補元，2 2和和5555互為補元，互為補元，5 5和和2222互為補元，互為補元，1010和和1111互為補元?；檠a元。綜上所述，綜上所述，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、，因為構(gòu)成格，因為和和運算滿足交換律、結(jié)合律和吸收律。運算滿足交換律、結(jié)合律和吸收律。由于由于和和互相可分配，因此互相可分配，因此P(B)P(B)是分配格，是分配格，且全下界是空集且全下界是空集, ,全上界是全上界是B B。根據(jù)絕對補的定義，取全集為根據(jù)絕對補的定義，取全集為B B， xP(B)xP(B)，x x是是x x的補元。的補元。從而證明從而證明P(B)P(B)是有補分配格，即布爾代數(shù)。是有補分配格，即布爾代數(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說明說明(1)(1)稱為稱為雙重否定律雙重否定律。(2)(2)稱為稱為德摩根律德摩根律。命題代數(shù)與集合代數(shù)的雙重否定律與德摩根律實際上命題代數(shù)與集合代數(shù)的雙重否定律與德摩根律實際上是這個定理的特例。是這個定理的特例?？梢宰C明德摩根律對有限個元素也是正確的?？梢宰C明德摩根律對有限個元素也是正確的。證明證明(1) (a(1) (a) )是是a a的補元，的補元，a a也是也是a a的補元。的補元。由補元的唯一性得由補元的唯一性得(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的補元，根據(jù)補元的唯一性有的補元，根據(jù)補元的唯一性有(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、*和和 是二元運算。是二元運算。若若* *和和運算滿足：運算滿足：(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) 補元律補元律，即，即 aB,aB,存在存在

42、a aBB，使得，使得a a* *a a0 0，a a a a1 1 則稱則稱B, 是一個是一個布爾代數(shù)布爾代數(shù)。 關(guān)于布爾代數(shù)定義的說明關(guān)于布爾代數(shù)定義的說明所謂所謂同一律就是指運算含有單位元的性質(zhì)同一律就是指運算含有單位元的性質(zhì)，這里的，這里的1 1是是* *運算的運算的單位元，單位元，0 0是運算是運算 的單位元。的單位元?？梢宰C明可以證明1 1和和0 0分別也是分別也是 和和* *運算的零元。運算的零元。 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) （補元律）（補元律） a a ( (aa* *1 1) ) （分配律）（分配律） a a aa （同一律）（同一律） 1 1 （補元律）（補元律）同理可證同理可證 a a* *0 00 0。關(guān)于布爾代數(shù)定義的說明關(guān)于布爾代數(shù)定義的說明為證明以上定義的為證明以上定義的B, 是布爾代數(shù)，只需證明它是一是布爾代數(shù)，只需證明它是一個格，即個格，即證明證明* *和和運算滿足結(jié)合律和吸收律。運算滿足結(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是是 運算的零元運算的零元) ) a a （同一律）（同一律）同理有同理有 a a* *(a(a b)b)a a。關(guān)于布爾代數(shù)定義的說明關(guān)于布爾代數(shù)定義的說明為證結(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由補元律得由補元律得 0 0 b b0 0 c c由同一律和交換律得由同一律和交換律得b bc c關(guān)于布爾代數(shù)定義的說明關(guān)于布爾代數(shù)定義的說明使用這個命題，為證明使用這個命題，為證明 (a(a* *b)b)* *c ca a* *( (b b* *c c) )，只需證明以下，只需證明以下兩個等式：兩個等式：(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)先證明第一個等式

46、，由吸收律有先證明第一個等式，由吸收律有 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ù)定義的說明關(guān)于布爾代數(shù)定義的說明下面證明下面證明(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) ) ( (交換律交換律, ,補元律補元律) ) 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) ( (交換律交換律, ,補元律補元律) ) ( (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中的中的原子原子。 考慮右圖中的幾個格。考慮右圖中的幾個格。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) )中的補元，即中的補元，即 (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運算構(gòu)成的布爾代數(shù)。運算構(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(