離散數(shù)學(xué)格與布爾代數(shù)

1、第11章 格與布爾代數(shù),離 散 數(shù) 學(xué),本章內(nèi)容,11.1 格的定義與性質(zhì) 11.2 分配格、有補(bǔ)格與布爾代數(shù) 本章總結(jié) 作業(yè),11.1 格的定義與性質(zhì),定義11.1 設(shè)是偏序集，如果x,ys，x,y都有最小上界和最大下界，則稱s關(guān)于偏序作成一個(gè)格(lattice)。 說明：由于最小上界和最大下界的唯一性，可以把求x,y的最小上界和最大下界看成x與y的二元運(yùn)算和。 xy：表示x與y的最小上界 xy：表示x和y的最大下界。 本章出現(xiàn)的和符號(hào)只代表格中的運(yùn)算，而不再有其它的含義。,格的實(shí)例,例11.1 設(shè)n是正整數(shù)，sn是n的正因子的集合。d為整除關(guān)系，則偏序集構(gòu)成格。x,ysn， xy是lcm(

2、x,y)，即x與y的最小公倍數(shù)。 xy是gcd(x,y)，即x與y的最大公約數(shù)。 下圖給出了格，和。,例11.2,例11.2 判斷下列偏序集是否構(gòu)成格,并說明理由。 (1) ，其中p(b)是集合b的冪集。 (2) ，其中z是整數(shù)集,為小于或等于關(guān)系。 (3) 偏序集的哈斯圖分別在下圖給出。,例11.2,解答 (1)是格。 x,yp(b)，xy就是xy，xy就是xy。 由于和運(yùn)算在p(b)上是封閉的，所以xy，xyp(b)。 稱,為b的冪集格。 (2)是格。 x,yz,xymax(x,y)，xymin(x,y)，它們都是整數(shù)。 (3)都不是格。 (a)中的a,b沒有最大下界。 (b)中的b,d有

3、兩個(gè)上界c和e,但沒有最小上界。 (c)中的b,c有三個(gè)上界d,e,f,但沒有最小上界。 (d)中的a,g沒有最大下界。,例11.3,例11.3 設(shè)g是群，l(g)是g的所有子群的集合。即 l(g) h|hg 對(duì)任意的h1,h2l(g)，h1h2也是g的子群，而是由h1h2生成的子群（即包含著h1h2的最小的子群）。 在l(g)上定義包含關(guān)系，則l(g)關(guān)于包含關(guān)系構(gòu)成一個(gè)格，稱為g的子群格。 易見在l(g)中，h1h2就是h1h2，h1h2就是。,對(duì)偶原理,定義11.2 設(shè)f是含有格中元素以及符號(hào)、和的命題。令f*是將f中的替換成，替換成，替換成，替換成所得到的命題。稱f*為f的對(duì)偶命題。

4、例如 在格中令f是(ab)cc，則f*是(ab)cc。 格的對(duì)偶原理 設(shè)f是含有格中元素以及符號(hào)、和的命題。若f對(duì)一切格為真，則f的對(duì)偶命題f*也對(duì)一切格為真。 例如 對(duì)一切格l都有 a,bl，aba (因?yàn)閍和b的交是a的一個(gè)下界) 那么對(duì)一切格l都有 a,bl，aba 說明許多格的性質(zhì)都是互為對(duì)偶命題的。 有了格的對(duì)偶原理，在證明格的性質(zhì)時(shí)，只須證明其中的一個(gè)命題即可。,格的運(yùn)算性質(zhì),定理11.1 設(shè)是格，則運(yùn)算和適合交換律、結(jié)合律、冪等律和吸收律，即 (1)交換律 a,bl 有 abbaabba (2)結(jié)合律 a,b,cl 有 (ab)ca(bc)(ab)ca(bc) (3)冪等律 al

5、 有 aaaaaa (4)吸收律 a,bl 有 a(ab)aa(ab)a,定理11.1,(1)ab和ba分別是a,b和b,a的最小上界。 由于a,bb,a，所以abba。 由對(duì)偶原理，abba得證。 (2)由最小上界的定義有 (ab)caba (13.1) (ab)cabb (13.2) (ab)cc (13.3) 由式13.2和13.3有(ab)cbc(13.4) 再由式13.1和13.4有(ab)ca(bc) 同理可證(ab)ca(bc) 根據(jù)偏序關(guān)系的反對(duì)稱性有(ab)ca(bc) 由對(duì)偶原理，(ab)ca(bc)得證。,定理11.1,(3)顯然aaa, 又由aa可得 aaa。 根據(jù)反對(duì)

6、稱性有 aaa， 由對(duì)偶原理，aaa 得證。 (4)顯然a(ab)a(13.5) 又由 aa，aba 可得 a(ab)a (13.6) 由式13.5和13.6可得 a(ab)a， 根據(jù)對(duì)偶原理，a(ab)a 得證。,定理11.2,定理11.2 設(shè)是具有兩個(gè)二元運(yùn)算的代數(shù)系統(tǒng)，若對(duì)于*和運(yùn)算適合交換律、結(jié)合律、吸收律，則可以適當(dāng)定義s中的偏序，使得構(gòu)成一個(gè)格，且a,bs有aba*b，abab。 思路 (1)證明在s中*和運(yùn)算都適合冪等律。 (2)在s上定義二元關(guān)系r，并證明r為偏序關(guān)系。 (3)證明構(gòu)成格。 說明通過規(guī)定運(yùn)算及其基本性質(zhì)可以給出格的定義。,定理11.2,as，由吸收律得,(1)證

7、明在s中*和運(yùn)算都適合冪等律。,a*a, a*(a(a*a), a,同理有 aaa。,(2)在s上定義二元關(guān)系r，,a,bs 有,r abb,下面證明r在s上的偏序。,根據(jù)冪等律，,as都有aaa，,即r，,所以r在s上是自反的。,a,bs 有,arb且bra, abb且baa, abaabb (由于a b=ba),所以r在s上是反對(duì)稱的。,定理11.2,a,b,cs 有 arb且brc abb 且 bcc aca(bc) ac(ab)c acbcc arc 這就證明了r在s上是傳遞的。 綜上所述，r為s上的偏序。 以下把r記作。,定理11.2,(3) 證明構(gòu)成格。 即證明abab，aba*b

8、 。,a,bs 有,a(ab)(aa)bab,b(ab)a(bb)ab,根據(jù)的定義有 aab和bab，,所以ab是a,b的上界。,假設(shè) c為a,b的上界，,則有acc和bcc，,從而有,(ab)c, a(bc), ac, c,這就證明了abc，,所以ab是a,b的最小上界，即,abab,為證a*b是a,b的最大下界，,先證,首先由abb 可知,a*b,a*(ab),a,反之由a*ba 可知,ab,(a*b)b,b(b*a),b,再由式(13.7)和的定義有 ab a*ba，,依照前邊的證明,類似地可證 a*b是a,b的最大下界，,即 aba*b。,abb a*ba(13.7),格的等價(jià)定義,根

9、據(jù)定理11.2，可以給出格的另一個(gè)等價(jià)定義。 定義11.3 設(shè)是代數(shù)系統(tǒng)，*和是二元運(yùn)算，如果*和滿足交換律，結(jié)合律和吸收律，則構(gòu)成一個(gè)格(lattice)。 說明格中的冪等律可以由吸收律推出。 以后我們不再區(qū)別是偏序集定義的格，還是代數(shù)系統(tǒng)定義的格，而統(tǒng)稱為格l。,格的性質(zhì),定理11.3 設(shè)l是格，則a,bl 有 ab aba abb 證明 先證 ab aba 由aa和ab可知，a是a,b的下界， 故aab。顯然又有aba。 由反對(duì)稱性得aba。 再證 aba abb。 根據(jù)吸收律有 bb(ba) 由aba得 bba, 即abb。 最后證abb ab。 由aab得 aabb。,格的性質(zhì),定理

10、11.4 設(shè)l是格，a,b,c,dl，若ab且cd，則 acbd，acbd 證明 acab accd 因此， acbd。 同理可證 acbd。,例11.5,例11.5 設(shè)l是格，證明 a,b,cl 有 a(bc)(ab)(ac) 證明由 aa，bcb 得 a(bc)ab 由 aa，bcc 得 a(bc)ac 從而得到 a(bc)(ab)(ac) 說明在格中分配不等式成立。 一般說來，格中的和運(yùn)算并不是滿足分配律的。,本節(jié)小結(jié),偏序集構(gòu)成格的條件：任意二元子集都有最大下界和最小上界。 格的實(shí)例：正整數(shù)的因子格，冪集格，子群格。 格的性質(zhì)：對(duì)偶原理，格中算律（交換、結(jié)合、冪等、吸收），保序性，分配

11、不等式。 格作為代數(shù)系統(tǒng)的定義。 格的證明方法,子格,定義11.4 設(shè)是格，s是l的非空子集，若s關(guān)于l中的運(yùn)算和仍構(gòu)成格，則稱s是l的子格。,例11.6 設(shè)格l如右圖所示。令,s1a,e,f,g s2a,b,e,g,則s1不是l的子格，s2是l的子格。 因?yàn)閷?duì)于e和f,有efc， 但cs1。,11.2 分配格、有補(bǔ)格與布爾代數(shù),一般說來，格中運(yùn)算對(duì)滿足分配不等式， 即a,b,cl，有 a(bc)(ab)(ac) 但是不一定滿足分配律。滿足分配律的格稱為分配格。 定義11.5 設(shè)是格，若a,b,cl，有 a(bc)(ab)(ac) a(bc)(ab)(ac) 則稱l為分配格。 說明上面兩個(gè)等式

12、互為對(duì)偶式。 在證明l為分配格時(shí)，只須證明其中的一個(gè)等式即可。,例11.7,l1和l2是分配格，l3和l4不是分配格。,在l3中，b(cd),beb,(bc)(bd),aaa,在l4中,c(bd),cac,(cb)(cd),edd,鉆石格,五角格,分配格的判別,定理11.5 設(shè)l是格，則l是分配格當(dāng)且僅當(dāng)l中不含有與鉆石格或五角格同構(gòu)的子格。 證明略。 推論(1) 小于五元的格都是分配格。 (2) 任何一條鏈都是分配格。,例11.8,說明下圖中的格是否為分配格，為什么？,l1, l2和l3都不是分配格。 a,b,c,d,e是l1的子格，并且同構(gòu)于鉆石格。 a,b,c,e,f是l2的子格，并且同

13、構(gòu)于五角格。 a,c,b,e,f是l3的子格，也同構(gòu)于鉆石格。,格的全下界和全上界,定義11.6 設(shè)l是格， 若存在al使得xl有ax，則稱a為l的全下界； 若存在bl使得xl有xb，則稱b為l的全上界。 命題格l若存在全下界或全上界，一定是唯一的。 證明以全下界為例，假若a1和a2都是格l的全下界, 則有a1a2和a2a1。 根據(jù)偏序關(guān)系的反對(duì)稱性必有a1a2。 記法將格l的全下界記為0，全上界記為1。,有界格,定義11.7 設(shè)l是格，若l存在全下界和全上界，則稱l為有界格，并將l記為。 說明有限格l一定是有界格。 舉例 設(shè)l是n元格，且la1,a2,an，那么a1a2an是l的全下界，而a

14、1a2an是l的全上界。因此l是有界格。 對(duì)于無限格l來說，有的是有界格，有的不是有界格。 如集合b的冪集格，不管b是有窮集還是無窮集，它都是有界格。它的全下界是空集，全上界是b。 整數(shù)集z關(guān)于通常數(shù)的小于或等于關(guān)系構(gòu)成的格不是有界格，因?yàn)椴淮嬖谧钚『妥畲蟮恼麛?shù)。,有界格的性質(zhì),定理（補(bǔ)充） 設(shè)是有界格，則al有 a00a0a a1aa11 證明由 a00 和 0a0 可知 a00。 說明 在有界格中， 全下界0是關(guān)于運(yùn)算的零元，運(yùn)算的單位元。 全上界1是關(guān)于運(yùn)算的零元，運(yùn)算的單位元。 對(duì)偶原理 對(duì)于涉及到有界格的命題，如果其中含有全下界0或全上界1，在求該命題的對(duì)偶命題時(shí)，必須將0替換成1，

15、而將1替換成0。 例如a00 和 a11 互為對(duì)偶命題， a0a 和 a1a 互為對(duì)偶命題。,有界格中的補(bǔ)元,定義11.8 設(shè)是有界格，al， 若存在bl 使得 ab0 和 ab1 成立，則稱b是a的補(bǔ)元。 說明若b是a的補(bǔ)元，那么a也是b的補(bǔ)元。 換句話說，a和b互為補(bǔ)元。,例11.9,考慮下圖中的四個(gè)格。,l1中的a與c互為補(bǔ)元，其中a為全下界，c為全上界，b沒有補(bǔ)元。 l2中的a與d互為補(bǔ)元，其中a為全下界，d為全上界，b與c也互為補(bǔ)元。 l3中的a與e互為補(bǔ)元，其中a為全下界，e為全上界，b的補(bǔ)元是c和d，c的補(bǔ)元是b和d，d的補(bǔ)元是b和c。b,c,d每個(gè)元素都有兩個(gè)補(bǔ)元。 l4中的a

16、與e互為補(bǔ)元。其中a為全下界。e為全上界。b的補(bǔ)元是c和d，c的補(bǔ)元是b，d的補(bǔ)元是b。,有界格中補(bǔ)元的說明,在任何有界格中， 全下界0與全上界1互補(bǔ)。 對(duì)于其他元素，可能存在補(bǔ)元，也可能不存在補(bǔ)元。 如果存在，可能是唯一的，也可能是多個(gè)補(bǔ)元。 對(duì)于有界分配格，如果它的元素存在補(bǔ)元，一定是唯一的。,有界分配格中補(bǔ)元的唯一性,定理11.6 設(shè)是有界分配格。 若al，且對(duì)于a存在補(bǔ)元b，則b是a的唯一補(bǔ)元。 證明假設(shè)cl也是a的補(bǔ)元，則有 ac1，ac0 又知b是a的補(bǔ)元，故 ab1，ab0 從而得到 acab，acab 由于l是分配格，根據(jù)定理13.7，bc。,有補(bǔ)格的定義,定義11.9 設(shè)是有

17、界格，若l中所有元素都有補(bǔ)元存在，則稱l為有補(bǔ)格。,l2,l3和l4是有補(bǔ)格， l1不是有補(bǔ)格。,l2和l3是有補(bǔ)格， l1不是有補(bǔ)格。,本節(jié)小結(jié),如果格中一個(gè)運(yùn)算對(duì)另一個(gè)運(yùn)算是可分配的，稱這個(gè)格是分配格。 分配格的兩種判別法： 不存在與鉆石格或五角格同構(gòu)的子格； 對(duì)于任意元素a,b,c,有 abac且abacbc。 有界格的定義及其實(shí)例。 格中元素的補(bǔ)元及其性質(zhì)（分配格中補(bǔ)元的唯一性）。 有補(bǔ)格的定義。,布爾代數(shù),定義11.10 如果一個(gè)格是有補(bǔ)分配格，則稱它為布爾格或布爾代數(shù)。 說明在布爾代數(shù)中，每個(gè)元素都存在著唯一的補(bǔ)元。 可以把求補(bǔ)元的運(yùn)算看作是布爾代數(shù)中的一元運(yùn)算。 可以把一個(gè)布爾代

18、數(shù)標(biāo)記為， 為求補(bǔ)運(yùn)算, ab，a是a的補(bǔ)元。,例11.10,例11.10 設(shè)s1101,2,5,10,11,22,55,110是110的正因子集合。令gcd,lcm分別表示求最大公約數(shù)和最小公倍數(shù)的運(yùn)算。問是否構(gòu)成布爾代數(shù)？為什么？ 解答 證明構(gòu)成格。,容易驗(yàn)證x,y,zs110，有 gcd(x,y)s110 lcm(x,y)s110 gcd(x,y)gcd(y,x) lcm(x,y)lcm(y,x) gcd(gcd(x,y),z)gcd(x,gcd(y,z) lcm(lcm(x,y),z)lcm(x,lcm(y,z) gcd(x,lcm(x,y)x lcm(x,gcd(x,y)x,二元運(yùn)算

19、,交換律,結(jié)合律,吸收律,例11.10,證明 是分配格。 易驗(yàn)證 x,y,zs110 有 gcd(x,lcm(y,z)lcm(gcd(x,y),gcd(x,z) 證明 是有補(bǔ)格。 1 為s110中的全下界 110為s110中的全上界 1和110互為補(bǔ)元，2和55互為補(bǔ)元， 5和22互為補(bǔ)元，10和11互為補(bǔ)元。 綜上所述，為布爾代數(shù)。,例11.10（2）,例11.10（2） 設(shè)b為任意集合,證明b的冪集格構(gòu)成布爾代數(shù)，稱為集合代數(shù)。 證明p(b)關(guān)于和構(gòu)成格，因?yàn)?和運(yùn)算滿足交換律、結(jié)合律和吸收律。 由于和互相可分配，因此p(b)是分配格， 且全下界是空集,全上界是b。 根據(jù)絕對(duì)補(bǔ)的定義，取全

20、集為b， xp(b)，x是x的補(bǔ)元。 從而證明p(b)是有補(bǔ)分配格，即布爾代數(shù)。,布爾代數(shù)的性質(zhì),定理11.7 設(shè)是布爾代數(shù)，則 (1) ab，(a)a (2) a,bb，(ab)ab,(ab)ab 說明(1)稱為雙重否定律。 (2)稱為德摩根律。 命題代數(shù)與集合代數(shù)的雙重否定律與德摩根律實(shí)際上是這個(gè)定理的特例。 可以證明德摩根律對(duì)有限個(gè)元素也是正確的。 證明(1) (a)是a的補(bǔ)元，a也是a的補(bǔ)元。 由補(bǔ)元的唯一性得(a)a。,定理11.7(2)的證明,(2) a,bb，(ab)ab,(ab)ab (ab)(ab) (aab)(bab) (1b)( a1) 11 1 (ab)(ab) (ab

21、a)(abb) (0b)(a0) 000 所以ab是ab的補(bǔ)元，根據(jù)補(bǔ)元的唯一性有 (ab)ab 同理可證(ab)= ab。,布爾代數(shù)作為代數(shù)系統(tǒng)的定義,定義11.11 設(shè)是代數(shù)系統(tǒng)，*和是二元運(yùn)算。 若*和運(yùn)算滿足： (1)交換律，即a,bb 有 a*bb*a，abba (2)分配律，即a,b,cb有 a*(bc)(a*b)(a*c) a(b*c)(ab)*(ac) (3)同一律，即存在0,1b，使得ab 有 a*1a，a0a (4)補(bǔ)元律，即ab,存在ab，使得 a*a0，aa1 則稱是一個(gè)布爾代數(shù)。,關(guān)于布爾代數(shù)定義的說明,所謂同一律就是指運(yùn)算含有單位元的性質(zhì)，這里的1是*運(yùn)算的單位元，

22、0是運(yùn)算的單位元。 可以證明1和0分別也是和*運(yùn)算的零元。 ab有 a1 (a1)*1 （同一律） 1*(a1) （交換律） (aa)*(a1) （補(bǔ)元律） a(a*1) （分配律） aa （同一律） 1 （補(bǔ)元律） 同理可證 a*00。,關(guān)于布爾代數(shù)定義的說明,為證明以上定義的是布爾代數(shù)，只需證明它是一個(gè)格，即證明*和運(yùn)算滿足結(jié)合律和吸收律。 證明吸收律，a,bb有 a(a*b) (a*1)(a*b)（同一律） a*(1b)（分配律） a*1 （1是運(yùn)算的零元) a （同一律） 同理有 a*(ab)a。,關(guān)于布爾代數(shù)定義的說明,為證結(jié)合律，先證以下命題： a,b,cb，abac 且 abac

23、 bc 由 abac 且 abac 可得 (ab)*(ab)(ac)*(ac) 由分配律和交換律得 (a*a)b(a*a)c 由補(bǔ)元律得 0b0c 由同一律和交換律得 bc,關(guān)于布爾代數(shù)定義的說明,使用這個(gè)命題，為證明 (a*b)*ca*(b*c)，只需證明以下兩個(gè)等式： (1) a(a*b)*c)a(a*(b*c) (2) a(a*b)*c)a(a*(b*c) 先證明第一個(gè)等式，由吸收律有 a(a*(b*c)a a(a*b)*c) (a(a*b)*(ac)(分配律) a*(ac)(吸收律) a 所以(1)式成立。,關(guān)于布爾代數(shù)定義的說明,下面證明(2)式： a(a*b)*c)a(a*(b*c

24、) a(a*(b*c) (aa)*(a(b*c) (分配律) 1*(a(b*c) (交換律,補(bǔ)元律) a(b*c) (交換律,同一律) a(a*b)*c) (a(a*b)*(ac) (分配律) (aa)*(ab)*(ac)(分配律) (1*(ab)*(ac) (交換律,補(bǔ)元律) (ab)*(ac) (交換律,同一律) a(b*c)(分配律) 所以（2）式成立。,有限布爾代數(shù)的結(jié)構(gòu),定義11.12 設(shè)l是格，0l，al，若 bl 有 0ba ba 則稱a是l中的原子。,考慮右圖中的幾個(gè)格。 l1的原子是a。 l2的原子是a,b,c。 l3的原子是a和b。,若l是正整數(shù)n的全體正因子關(guān)于整除關(guān)系構(gòu)

25、成的格，則l的原子恰為n的全體質(zhì)因子。 若l是集合b的冪集合，則l的原子就是由b中元素構(gòu)成的單元集。,有限布爾代數(shù)的表示定理,定理11.8 (有限布爾代數(shù)的表示定理) 設(shè)b是有限布爾代數(shù)，a是b的全體原子構(gòu)成的集合，則b同構(gòu)于a的冪集代數(shù)p(a)。 證明任取xb，令t(x)a|ab,a是原子且ax 則t(x)a，定義函數(shù) ：bp(a)，(x)t(x)，xb 下面證明是b到p(a)的同構(gòu)映射。 任取x,yb，b 有 bt(xy) ba 且 bxy (ba且bx) 且 (ba且by) bt(x)且bt(y) bt(x)t(y) 從而有 t(xy)t(x)t(y)， 即x,yb 有 (xy)(x)(

26、y)。,定理11.8證明,任取x,yb，設(shè) xa1a2an， yb1b2bm 是x,y的原子表示，則 xya1a2anb1b2bm 由引理2可知 t(xy)a1,a2,an,b1,b2, ,bm 又由于 t(x)a1,a2, ,an， t(y)b1,b2, ,bm 所以 t(xy)t(x)t(y) 即(xy)(x)(y),定理11.8證明,任取xb，存在xb 使得 xx1， xx0 因此有 (x)(x)(xx)(1)a (x)(x)(xx)(0) 而和a分別為p(a)的全下界和全上界， 因此(x)是(x)在p(a)中的補(bǔ)元，即 (x)(x) 綜上所述，是b到p(a)的同態(tài)映射。,定理11.8證

27、明,下面證明為雙射。 假設(shè)(x)(y)，則有 t(x)t(y)a1,a2, ,an 由引理2可知 xa1a2any 于是為單射。 任取b1,b2, ,bmp(a)， 令xb1b2bm ，則 (x)t(x)b1,b2, ,bm 于是為滿射。 定理得證。,例子,考慮110的正因子的集合s110關(guān)于gcd, lcm運(yùn)算構(gòu)成的布爾代數(shù)。 它的原子是2、5和11，因此原子的集合a2,5,11。 冪集p(a),2,5,11,2,5,2,11,5,11,2,5,11。 冪集代數(shù)是。 只要令 : s110p(a)， (1)，(2)2，(5)5， (11)11，(10)2,5，(22)2,11， (55)5,11, (110)a， 那么f就是定理13.11中從s110到冪集p(a)的同構(gòu)映射。,推論1,推論1任何有限布爾代數(shù)的基數(shù)為2n，nn。 證明 設(shè)b是有限布爾代數(shù)，a是b的所有原子構(gòu)成的集合， 且|a|n，nn。 由定理