離散數(shù)學(xué)課件(第6章)

1、離散數(shù)學(xué)離散數(shù)學(xué)教案教案計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院課程學(xué)時(shí)：課程學(xué)時(shí)：64主主 講：宋講：宋 成成河南理工大學(xué)河南理工大學(xué)電子教案電子教案第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)6.1 格的概念格的概念6.2 分配格分配格6.3 有補(bǔ)格有補(bǔ)格6.4* 布爾代數(shù)布爾代數(shù)第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)教學(xué)目的及要求：教學(xué)目的及要求： 深刻理解和掌握格與布爾代數(shù)的基本概念和基本運(yùn)深刻理解和掌握格與布爾代數(shù)的基本概念和基本運(yùn)算算教學(xué)類容：教學(xué)類容： 格的概念、有補(bǔ)格，分配格、布爾代數(shù)和布爾表格的概念、有補(bǔ)格，分配格、布爾代數(shù)和布爾表達(dá)式。達(dá)式。教學(xué)重點(diǎn)：教學(xué)重點(diǎn)： 格、布爾代數(shù)

2、和布爾表達(dá)式。格、布爾代數(shù)和布爾表達(dá)式。教學(xué)難點(diǎn)：教學(xué)難點(diǎn)： 布爾代數(shù)和布爾表達(dá)式。布爾代數(shù)和布爾表達(dá)式。6.1 格的概念格的概念【定義【定義6.1.1】 設(shè)設(shè) X, 是偏序集，如果是偏序集，如果 x,y X，集合，集合 x,y 都有最小上界和最大下界，則稱都有最小上界和最大下界，則稱 X, 是格。是格?！纠纠?.1】設(shè)設(shè)S12 1,2,3,4,6,12 是是12的因子構(gòu)成的集合。其的因子構(gòu)成的集合。其上的整除關(guān)系上的整除關(guān)系R=x,y | x S12y S12x整除整除y ，R是是S12上上的偏序關(guān)系，的偏序關(guān)系， S12,R 是偏序集。寫(xiě)出是偏序集。寫(xiě)出S12上的蓋住關(guān)系上的蓋住關(guān)系CO

3、V S12，畫(huà)出哈斯圖，驗(yàn)證偏序集，畫(huà)出哈斯圖，驗(yàn)證偏序集 S12,R 是格。是格。 解：解：S12上的蓋住關(guān)系上的蓋住關(guān)系 COV S121,2 , 1,3 , 2,4 , 2,6 , 3,6 , 4,12 , 6,12，哈斯圖如圖哈斯圖如圖6.1所示。從哈斯圖中可看出，集合所示。從哈斯圖中可看出，集合S12的任意兩的任意兩個(gè)元素都有最小上界和最大下界，故偏序集個(gè)元素都有最小上界和最大下界，故偏序集 S12,R 是格。是格。 第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【例【例6.2】圖圖8.2中給出了一些偏序集的哈斯圖，判斷它們是中給出了一些偏序集的哈斯

4、圖，判斷它們是否構(gòu)成格。否構(gòu)成格。 解：解：它們都不是格。在它們都不是格。在(a)中，中， 1,2 沒(méi)有下界，因而沒(méi)沒(méi)有下界，因而沒(méi)有最大下界。在有最大下界。在(b)中，中， 2,4 雖有兩個(gè)上界，但沒(méi)有最小上雖有兩個(gè)上界，但沒(méi)有最小上界。在界。在(c)中，中， 1,3 沒(méi)有下界，因而沒(méi)有最大下界。在沒(méi)有下界，因而沒(méi)有最大下界。在(d)中，中， 2,3 雖有三個(gè)上界，但沒(méi)有最小上界。雖有三個(gè)上界，但沒(méi)有最小上界。第六章：格和布爾代數(shù)第六章：格和布爾代數(shù) 設(shè)設(shè) X, 是格，是格， x,y X，今后用，今后用xy表示集合表示集合 x,y 的最的最小上界，二元運(yùn)算小上界，二元運(yùn)算稱為并運(yùn)算；用稱為并

5、運(yùn)算；用xy表示集合表示集合 x,y 的最的最大下界，二元運(yùn)算大下界，二元運(yùn)算稱為交運(yùn)算。稱為交運(yùn)算。 【定義定義6.1.2】 設(shè)設(shè) X, 是格，是格，是是X上的并運(yùn)算，上的并運(yùn)算，是是X上的上的交運(yùn)算。則稱交運(yùn)算。則稱 X, 是格是格 X, 導(dǎo)出的代數(shù)系統(tǒng)。導(dǎo)出的代數(shù)系統(tǒng)。 x,y P (A)，xy=xy，xy=xy。這樣，格。這樣，格 P (A),R 導(dǎo)出的代數(shù)系統(tǒng)導(dǎo)出的代數(shù)系統(tǒng) P (A), 實(shí)際就是代數(shù)系統(tǒng)實(shí)際就是代數(shù)系統(tǒng) P (A), ，所以，二元運(yùn)算所以，二元運(yùn)算和和的運(yùn)算表如表的運(yùn)算表如表6.1和表和表6.2所示。所示。 在例在例6.1中，根據(jù)圖中，根據(jù)圖6.1，集合，集合 4,

6、6 的最小上界為的最小上界為12，即，即46=12=4和和6的最小公倍數(shù)；它的最大下界為的最小公倍數(shù)；它的最大下界為2，即，即46=2=4和和6的最大公約數(shù)。同樣，這個(gè)結(jié)果也可以推廣到一的最大公約數(shù)。同樣，這個(gè)結(jié)果也可以推廣到一般情況。即在格般情況。即在格 S12,R 導(dǎo)出的代數(shù)系統(tǒng)導(dǎo)出的代數(shù)系統(tǒng) S12, 中，二元中，二元運(yùn)算運(yùn)算是求最小公倍數(shù)；二元運(yùn)算是求最小公倍數(shù)；二元運(yùn)算是求最大公約數(shù)。是求最大公約數(shù)。 第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)表6. 1 表6. 2aabba,baaaa,ba,ba,bbba,ba,ba,ba,ba,bba,ba,baba,baaabbba,baba,

7、b第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)定義定義6.1.3 設(shè)設(shè)f是含有格中元素以及符號(hào)是含有格中元素以及符號(hào)=, , ,和和的命的命題。將題。將f中的中的 替換成替換成 ， 替換成替換成 ，替換成替換成，替換成替換成，得到一個(gè)新命題，所得的命題叫做，得到一個(gè)新命題，所得的命題叫做f的對(duì)偶命的對(duì)偶命題，記為題，記為f *。 例如，在格中，例如，在格中，f為為a(bc) a，則，則f的對(duì)偶命題的對(duì)偶命題f *為為a(bc) a 命題命題f和它的對(duì)偶命題和它的對(duì)偶命題f *遵循下列的規(guī)則，這規(guī)則叫遵循下列的規(guī)則，這規(guī)則叫做格的對(duì)偶原理。做格的對(duì)偶原理。 設(shè)設(shè)f是含有格中元素以及符號(hào)是含有格中元素

8、以及符號(hào)=,和和的命題。的命題。 若若f對(duì)一切格為真，則對(duì)一切格為真，則f的對(duì)偶命題的對(duì)偶命題f *也對(duì)一切格為真。也對(duì)一切格為真。 格的許多性質(zhì)都是互為對(duì)偶命題的。有了格的對(duì)偶原格的許多性質(zhì)都是互為對(duì)偶命題的。有了格的對(duì)偶原理，在證明格的性質(zhì)時(shí)，只需證明其中的一個(gè)就可以了。理，在證明格的性質(zhì)時(shí)，只需證明其中的一個(gè)就可以了。 第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【定理定理6.1.1】 設(shè)設(shè) X, 是格，是格， X, 是格是格 X, 導(dǎo)出導(dǎo)出的代數(shù)系統(tǒng)。則的代數(shù)系統(tǒng)。則 a,b,c X有有 ab=ba， ab=ba (交換律交換律) (ab)c=a(bc) (ab)c=a(bc) (結(jié)合律結(jié)

9、合律) aa= a， aa= a (冪等律冪等律) a(ab)=a a(ab)=a (吸收律吸收律) 證明：證明： a,b X， a,b = b,a ，所以它們的最小上界相，所以它們的最小上界相等。即等。即ab=ba，同理可證，同理可證ab=ba a和和b的最大下界一定是的最大下界一定是a、b的下界，即的下界，即ab a，同理，同理，(ab)c ab，所以，所以，(ab)c ab a 同理有同理有 (ab)c ab b 和和 (ab)c c第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)由以上由以上3式得式得 (ab)c bc和和(ab)c a(bc)類似地可證類似地可證 a(bc) (ab)c根據(jù)偏

10、序關(guān)系的反對(duì)稱性有根據(jù)偏序關(guān)系的反對(duì)稱性有(ab)c= a(bc) 由對(duì)偶原理得由對(duì)偶原理得 (ab)c= a(bc) 顯然顯然a aa，又由，又由 的自反性得的自反性得a a，從而推出，從而推出aa a，根據(jù)偏序關(guān)系的反對(duì)稱性有，根據(jù)偏序關(guān)系的反對(duì)稱性有aa=a 由對(duì)偶原理得由對(duì)偶原理得aa=a 顯然顯然 a a(ab)， 又由又由a a，ab a得得a(ab) a，從而得，從而得 a(ab)=a。 由對(duì)偶原理得由對(duì)偶原理得a(ab)=a第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【定理【定理6.1.2】 設(shè)設(shè) X, 是代數(shù)系統(tǒng)，其中是代數(shù)系統(tǒng)，其中,都是二元運(yùn)算。都是二元運(yùn)算。如果如果和和滿足

11、吸收律，則滿足吸收律，則和和滿足冪等律。滿足冪等律。 證明證明：aa=a(a(ab)=a，同理可證，同理可證aa=a【定理定理6.1.3】 設(shè)設(shè) X, 是代數(shù)系統(tǒng)，其中是代數(shù)系統(tǒng)，其中,都是二元運(yùn)算，都是二元運(yùn)算，滿足交換律、結(jié)合律和吸收律，則可適當(dāng)定義滿足交換律、結(jié)合律和吸收律，則可適當(dāng)定義X的偏序關(guān)系的偏序關(guān)系 ，使，使 X, 構(gòu)成一個(gè)格。構(gòu)成一個(gè)格。 證明證明：定義定義X上的一個(gè)二元關(guān)系上的一個(gè)二元關(guān)系 =a,b |a,b X且且ab=a 證明證明 是是X上的偏序關(guān)系。上的偏序關(guān)系。 由定理由定理6.1.2知知滿足冪等律，即滿足冪等律，即aa=a，所以，所以a a。故。故 是自反是自反的

12、。的。 設(shè)設(shè)a b且且b a，則，則ab=a且且ba=b，于是，于是a=ab=ba=b。所以所以 是反對(duì)稱的。是反對(duì)稱的。 設(shè)設(shè)a b且且b c，則，則ab=a且且bc=b，于是，于是ac=(ab)c=a(bc)=ab=a，即，即a c，故，故 是傳遞的。是傳遞的。 這就證明了這就證明了 是是X上的偏序關(guān)系。上的偏序關(guān)系。 第六章：格和布爾代數(shù)第六章：格和布爾代數(shù) 證明證明 a,b X，ab是集合是集合 a,b 的最大下界。因?yàn)榈淖畲笙陆?。因?yàn)?(ab)a=ab和和(ab)b=ab所以所以ab a且且ab b，即，即ab是是 a,b 的下界。的下界。 下證下證ab是是 a,b 的最大下界。的最

13、大下界。 設(shè)設(shè)c是是 a,b 的任一下界，即的任一下界，即c a，c b，那么有，那么有 ca=c，cb=c而而 c(ab)=(ca)b=cb=c所以所以 c ab，即，即ab是是 a,b 的最大下界。的最大下界。 證明證明ab=a的充分必要條件是的充分必要條件是ab= b 設(shè)設(shè)ab=a，由吸收率可得，由吸收率可得 ab=(ab)b=b(ba)=b，即，即ab= b 設(shè)設(shè)ab=b，由吸收率可得，由吸收率可得 ab=a(ab)=a，即，即ab=a第六章：格和布爾代數(shù)第六章：格和布爾代數(shù) 證明證明 a,b X，ab是集合是集合 a,b 的最小上界。的最小上界。 根據(jù)根據(jù)，偏序關(guān)系，偏序關(guān)系 可以等

14、價(jià)的定義為：可以等價(jià)的定義為： =a,b |a,b X且且ab=b ，用這個(gè)定義和類似于用這個(gè)定義和類似于的方法可以證明的方法可以證明ab是集合是集合 a,b 的的最小上界。最小上界。 因此，因此， X, 構(gòu)成一個(gè)格。構(gòu)成一個(gè)格。 根據(jù)定理根據(jù)定理6.1.3，可以給出格的另一個(gè)等價(jià)定義。，可以給出格的另一個(gè)等價(jià)定義。 【定義定義6.1.4】 設(shè)設(shè) X,* *, 是代數(shù)系統(tǒng)，其中是代數(shù)系統(tǒng)，其中* *和和 都是二都是二元運(yùn)算，如果元運(yùn)算，如果* *和和 在在X上封閉且滿足交換律、結(jié)合律和吸上封閉且滿足交換律、結(jié)合律和吸收律，則稱收律，則稱 X,* *, 為格。為格。 根據(jù)定義根據(jù)定義6.1.4和

15、定理和定理6.1.1，格，格 X, 導(dǎo)出的代數(shù)系統(tǒng)導(dǎo)出的代數(shù)系統(tǒng) X, 是格，以后不再區(qū)分偏序集定義的格和代數(shù)系統(tǒng)是格，以后不再區(qū)分偏序集定義的格和代數(shù)系統(tǒng)定義的格，統(tǒng)稱為格。定義的格，統(tǒng)稱為格。第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【定理【定理6.1.4】 設(shè)設(shè) X, 是格，是格，是是X上的并運(yùn)算，上的并運(yùn)算，是是X上的交運(yùn)算。則上的交運(yùn)算。則 a,b X有有 a b當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)ab=a a b當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)ab=b 證明：證明： 設(shè)設(shè)a b，下證，下證ab=a 由由a a且且a b知知a是集合是集合 a,b 的下界，故有的下界，故有a ab；另一方面，由于另一方面，由于ab是是 a

16、,b 的最大下界，所以是的最大下界，所以是 a,b 的下的下界，即界，即ab a。根據(jù)偏序關(guān)系的反對(duì)稱性得。根據(jù)偏序關(guān)系的反對(duì)稱性得ab=a 設(shè)設(shè)ab=a，下證，下證a b a=ab b，即，即a b 可類似可類似進(jìn)行證明。進(jìn)行證明。第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【 定理定理6.1.5】 設(shè)設(shè) X, 是格，是格，是是X上的并運(yùn)算，上的并運(yùn)算，是是X上的上的交運(yùn)算。交運(yùn)算。 a,b,c,d X，若，若a b且且c d，則，則ac bd，ac bd 證明證明： a b bd ，c d bd，因此，因此ac bd 類似的可以證明類似的可以證明ac bd【定理【定理6.1.6】 設(shè)設(shè) X,

17、是格，是格，是是X上的并運(yùn)算，上的并運(yùn)算，是是X上的交上的交運(yùn)算。則運(yùn)算。則 a,b,c X有有 a(bc) (ab)(ac) (ab)(ac) a(bc) 證明證明： 根據(jù)定理根據(jù)定理8.1.5，由，由a a和和bc b得得 a(bc) ab 又由又由a a且且bc c得得 a(bc) ac 從而得到從而得到 a(bc) (ab)(ac) 利用對(duì)偶原理，即得利用對(duì)偶原理，即得。 一般地說(shuō)，格中的一般地說(shuō)，格中的和和并不滿足分配律。并不滿足分配律。 第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【定義【定義6.1.5】 設(shè)設(shè) X, 是格，是格，B是是X的非空子集，如果的非空子集，如果B關(guān)于運(yùn)算關(guān)于運(yùn)

18、算和和也構(gòu)成格，則稱也構(gòu)成格，則稱 B, 是是 X, 的子的子格。格。 在例在例6.1中，令中，令B1 1,2,3,6 ，B2 2,4,6,12 ，則，則 B1, 和和 B2, 是格是格 S12, 的子格。的子格。 令令B3 1,2,3,12 ，由于，由于23=6，而，而6 B3，所以，所以 B3, 不是格不是格 S12, 的子格。的子格。 以下定義格的同態(tài)。以下定義格的同態(tài)?！径x定義6.1.6】 設(shè)設(shè) X1,1,1 和和 X2,2,2 是格，其中是格，其中1,1,2和和2都是二元運(yùn)算。都是二元運(yùn)算。f是從是從X1到到X2的一個(gè)映射，對(duì)任的一個(gè)映射，對(duì)任意的意的a,b X1有有f(a1b)=

19、f(a)2 f(b)， f(a1b)=f(a)2f(b)則稱則稱f是格是格 X1,1,1 到格到格 X2,2,2 的格同態(tài)。如果的格同態(tài)。如果f是單是單射、滿射和雙射，分別稱射、滿射和雙射，分別稱f是格單同態(tài)、格滿同態(tài)和格同構(gòu)。是格單同態(tài)、格滿同態(tài)和格同構(gòu)。稱稱 f(X1),2,2 是是 X1,1,1 的格同態(tài)像。的格同態(tài)像。第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【定理【定理6.1.7】 設(shè)設(shè) X1, 1 和和 X2, 2 是格，是格， X1,1,1 和和 X2,2,2 是它們導(dǎo)出的代數(shù)系統(tǒng)。是它們導(dǎo)出的代數(shù)系統(tǒng)。f是格是格 X1,1,1 到格到格 X2,2,2 的格同態(tài)，則的格同態(tài)，則 a

20、,b X1，如果，如果a 1b，必有，必有f(a) 2f(b) 證明：證明：設(shè)設(shè)a 1b，根據(jù)定理，根據(jù)定理6.1.4，a1b=a，由于，由于 f 是格是格 X1,1,1 到格到格 X2,2,2 的格同態(tài)，所以的格同態(tài)，所以 f(a)=f(a1b)=f (a)2f (b)，再由定理，再由定理6.1.4，f (a) 2f (b)。 定理定理6.1.7說(shuō)明格同態(tài)是保序的。一般地說(shuō)，定理說(shuō)明格同態(tài)是保序的。一般地說(shuō)，定理6.1.7的逆并不成立。的逆并不成立?！纠?.3】設(shè)設(shè)A= a,b,c,d,e ， A, 是格，其哈斯圖如圖是格，其哈斯圖如圖8.3所示，所示，P(A)是是A的冪集合，的冪集合，R

21、 =x,y |x P(A)y P (A)x y 是是P(A)上的偏序關(guān)系。上的偏序關(guān)系。 P(A), R 也是格。作映射也是格。作映射f：AP (A)，定義為：，定義為： x A，f(x)= y|y A且且y x ，即：即：f(a)= a,b,c,d,e =A，f(b)= b,e ，f(c)= c,e ，f(d)= d,e ，f(e)= e 。證明。證明f是保序的，但不是格同態(tài)。是保序的，但不是格同態(tài)。第六章：格和布爾代數(shù)第六章：格和布爾代數(shù) 證明證明： a,b A，設(shè)，設(shè)a b， c f(a)，c a，由偏序關(guān)系，由偏序關(guān)系的傳遞性得的傳遞性得c b，所以，所以c f(b)，即即f(a) f

22、(b)，于是，于是f(a)R f(b)。故故f是保序的。是保序的。 對(duì)于對(duì)于b,d A，bd=a f(bd)=f(a)=A f(b)f (d)= b,e d,e = b,d,e f(bd)f(b)f (d) f不是格同態(tài)。不是格同態(tài)。 但是，當(dāng)?shù)?，?dāng)f是格同構(gòu)時(shí)，是格同構(gòu)時(shí)，定理定理6.1.7的逆成立。的逆成立。 第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【定理【定理6.1.8】 設(shè)設(shè) X1, 1 和和 X2, 2 是格，是格， X1,1,1 和和 X2,2,2 是它們導(dǎo)出的代數(shù)系統(tǒng)。是它們導(dǎo)出的代數(shù)系統(tǒng)。f 是是X1到到X2的雙射，則的雙射，則 f 是是 X1,1,1 到到 X2,2,2 的

23、格同構(gòu)的充分必要條件是的格同構(gòu)的充分必要條件是 a,b X1，a 1bf(a) 2f(b) 證明證明：設(shè)設(shè)f是是 X1,1,1 到到 X2,2,2 的格同構(gòu)，下證的格同構(gòu)，下證 a,b X1，a 1bf(a) 2f(b) 由定理由定理6.1.7可知，可知， a,b X1，如果，如果a 1b，必有，必有f(a) 2f(b) 設(shè)設(shè)f(a) 2f(b)，由定理，由定理6.1.4有有f(a)=f(a)2f(b)=f(a1b)，由于，由于f是雙射，故是雙射，故a1b=a，所以，所以a 1b 這就證明這就證明a 1bf(a) 2f(b) 設(shè)設(shè) a,b X1，a 1bf(a) 2f(b)，下證，下證 f 是

24、是 X1,1,1 到到 X2,2,2 的格同構(gòu)。的格同構(gòu)。 設(shè)設(shè)a1b=c，則，則c 1a，c 1b，f(c)=f(a1b)，f(c) 2f(a)，f(c) 2f(b)，故，故 f(c) 2f(a)2f(b)。 設(shè)設(shè)f(a)2f(b)=f(d)，則有，則有f(c) 2f(a)2f(b)=f(d)，即，即f(c) 2f(d)；還有；還有f(d) 2f(a)和和f(d) 2f(b)。所以有。所以有d 1a和和d 1b， 第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)于是于是d 1a1b，即，即d 1c，故，故f(d) 2f(c)，再由偏序關(guān)系的，再由偏序關(guān)系的反對(duì)稱性有反對(duì)稱性有f(c)=f(d)。即。

25、即f(a1b)=f(c)=f(d)=f (a)2f(b) 類似地可以證明類似地可以證明 f(a1b)=f (a)2f(b) 這就證明了這就證明了f是是 X1,1,1 到到 X2,2,2 的格同構(gòu)。的格同構(gòu)。【定義定義6.1.7】 設(shè)設(shè) X1, 1 和和 X2, 2 是格，是格， X1,1,1 和和 X2,2,2 是它們導(dǎo)出的代數(shù)系統(tǒng)。其中是它們導(dǎo)出的代數(shù)系統(tǒng)。其中1,1,2和和2都是二元運(yùn)算。都是二元運(yùn)算。a1,b1X1X2和和a2,b2X1X2，定，定義義X1X2上的二元運(yùn)算上的二元運(yùn)算3和和3為：為： a1,b1 3 a2,b2 = a11a2, b12b2 a1,b1 3 a2,b2 =

26、 a11a2, b12b2 代數(shù)系統(tǒng)代數(shù)系統(tǒng) X1X2,3,3 稱為格稱為格 X1,1,1 到格到格 X2,2,2 的直積。的直積。 如果如果 X1,1,1 和和 X2,2,2 是格，可以證明代數(shù)系是格，可以證明代數(shù)系統(tǒng)統(tǒng) X1X2,3,3 也是格也是格 第六章：格和布爾代數(shù)第六章：格和布爾代數(shù) 6.2 分配格分配格【定義定義6.2.1】 設(shè)設(shè) X, 是格，是格， X, 是是 X, 導(dǎo)出的代導(dǎo)出的代數(shù)系統(tǒng)，如果數(shù)系統(tǒng)，如果 a,b,c X有有 a(bc)=(ab)(ac) (并運(yùn)算對(duì)交運(yùn)算可分配并運(yùn)算對(duì)交運(yùn)算可分配) a(bc)=(ab)(ac) (交運(yùn)算對(duì)并運(yùn)算可分配交運(yùn)算對(duì)并運(yùn)算可分配)則

27、稱則稱 X, 為分配格。為分配格。 因?yàn)橐驗(yàn)閍(bc)=(ab)(ac)和和 a(bc)=(ab)(ac) 互為對(duì)偶命題，根據(jù)對(duì)偶原理，定義互為對(duì)偶命題，根據(jù)對(duì)偶原理，定義6.2.1還可以改寫(xiě)為：還可以改寫(xiě)為：一個(gè)格如果交運(yùn)算對(duì)并運(yùn)算可分配或并運(yùn)算對(duì)交運(yùn)算可分一個(gè)格如果交運(yùn)算對(duì)并運(yùn)算可分配或并運(yùn)算對(duì)交運(yùn)算可分配，則稱該格為分配格。配，則稱該格為分配格。第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【例【例6.4】 設(shè)設(shè)A= a,b,c ，P (A)= , a , b , c , a,b , a,c , b,c , a,b,c是是A的冪集合，的冪集合，P (A)上的包含關(guān)系上的包含關(guān)系R =x,y |

28、 x P (A)y P (A)x y 是是P (A)上的偏序關(guān)系。上的偏序關(guān)系。 P (A), R 是偏序集，是偏序集，P (A)上的蓋住關(guān)系上的蓋住關(guān)系 COVP(A)=, a, , b, , c,a , a,b, b , a,b,a , a,c,c , a,c, b , b,c,c , b,c,a,b , a,b,c, a,c , a,b,c,b,c , a,b,c其哈斯圖如圖其哈斯圖如圖8.4所示。所示。 P (A), 是是 P (A), R 導(dǎo)出導(dǎo)出的代數(shù)系統(tǒng)，證明的代數(shù)系統(tǒng)，證明 P (A), 是分配格。是分配格。 證明證明：前面已經(jīng)證明了格前面已經(jīng)證明了格 P (A), R 導(dǎo)出的

29、代數(shù)系導(dǎo)出的代數(shù)系統(tǒng)統(tǒng) P (A), 實(shí)際就是代數(shù)系統(tǒng)實(shí)際就是代數(shù)系統(tǒng) P (A), ，其中，其中是集合的并運(yùn)算，是集合的并運(yùn)算，是集合的交運(yùn)算。而集合的并、交運(yùn)是集合的交運(yùn)算。而集合的并、交運(yùn)算滿足分配律：算滿足分配律：第六章：格和布爾代數(shù)第六章：格和布爾代數(shù) P,Q,R P (A) P(QR)=(PQ)(PR) P(QR)=(PQ)(PR) 所以，所以， P (A), 分配格。分配格。第六章：格和布爾代數(shù)第六章：格和布爾代數(shù) 【例【例6.5】 A= a,b,c,d,e ， A, 是格，其哈斯圖如圖是格，其哈斯圖如圖8.3所所示，證明示，證明 A, 不是分配格。不是分配格。 證明：證明：b(

30、cd)=be=b (bc)(bd)=aa=a b(cd)(bc)(bd) 所以，所以， A, 不是分配格。不是分配格。 本例中的格叫做鉆石格，鉆石格不是分配格。本例中的格叫做鉆石格，鉆石格不是分配格。 第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【例例6.6】設(shè)設(shè)A= a,b,c,d,e ， A, 是格，其哈斯圖如圖是格，其哈斯圖如圖8.5所示，證明所示，證明 A, 不是分配格。不是分配格。 證明證明： d(bc)=de=d (db)(dc)=ac=c d(bc)(db)(dc)所以，所以， A, 不是分配格。不是分配格。 本例中的格叫做五角格，五角格本例中的格叫做五角格，五角格也不是分配格。鉆石

31、格和五角格是也不是分配格。鉆石格和五角格是兩個(gè)很重要的格。兩個(gè)很重要的格。第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【定理定理6.2.1 】一個(gè)格是分配格的充分必要條件是該格中不一個(gè)格是分配格的充分必要條件是該格中不含有與鉆石格或五角格同構(gòu)的子格。含有與鉆石格或五角格同構(gòu)的子格。 這個(gè)定理的證明已經(jīng)超過(guò)了本書(shū)的范圍，故略去。這個(gè)定理的證明已經(jīng)超過(guò)了本書(shū)的范圍，故略去。【 推論推論1】 設(shè)設(shè) A, 是格，如果是格，如果|A|5，則，則 A, 一定是一定是分配格。分配格?！就普撏普?】 設(shè)設(shè) A, 是格，如果是格，如果 A, 是全序集，則是全序集，則 A, 一定是分配格。一定是分配格?！纠?.7】

32、圖圖8.6給出了兩個(gè)格的哈斯圖。試證明它們都不給出了兩個(gè)格的哈斯圖。試證明它們都不是分配格。是分配格。 證明：證明：在圖在圖8.6 (a)中含有與五角格同構(gòu)的子格，所以中含有與五角格同構(gòu)的子格，所以不是分配格；在圖不是分配格；在圖8.6 (b)中含有與鉆石格同構(gòu)的子格，所中含有與鉆石格同構(gòu)的子格，所以不是分配格。以不是分配格。 第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【定理定理6.2.2】 設(shè)設(shè) X, 是格，是格， X, 是格是格 X, 導(dǎo)出的代數(shù)系導(dǎo)出的代數(shù)系統(tǒng)。統(tǒng)。 X, 是分配格的充分必要條件是是分配格的充分必要條件是 a,b,c X，當(dāng)，當(dāng)ab=

33、ac且且ab=ac時(shí)，必有時(shí)，必有b= c 證明：證明：設(shè)設(shè) X, 是分配格，是分配格， a,b,c X， ab=ac且且ab=ac b=b(ba)=b(ab) (吸收律和交換律吸收律和交換律) =b(ac)= (ba)(bc) (已知代入和分配律已知代入和分配律) =(ac)(bc) (交換律和已知代入交換律和已知代入) =(ab)c (分配律分配律) =(ac)c (已知條件代入已知條件代入) =c (交換律和吸收律交換律和吸收律) 設(shè)設(shè) a,b,c X，當(dāng)，當(dāng)ab=ac且且ab=ac時(shí)，有時(shí)，有b=c，但，但 X, 不是分配格。由定理不是分配格。由定理6.2.1知知 X, 中必含有與鉆石

34、格中必含有與鉆石格或五角格同構(gòu)的子格。假設(shè)或五角格同構(gòu)的子格。假設(shè) X, 含有與鉆石格同構(gòu)的子格，且含有與鉆石格同構(gòu)的子格，且此子格為此子格為 S, ，其中，其中S= u,v,x,y,z ，u為它的最大元，為它的最大元，v為它的為它的最小元。從而最小元。從而xy=u=xz，xy=v=xz，但，但yz，與已知矛盾。，與已知矛盾。第六章：格和布爾代數(shù)第六章：格和布爾代數(shù) 對(duì)五角格的情況，可類似證明。對(duì)五角格的情況，可類似證明。 例如，在圖例如，在圖8.6 (a)中，中，bc=g=bf且且bc=a=bf，但，但cf；在圖；在圖8.6 (b)中，中，bc=f= be且且bc=a= be，但，但ce。根

35、據(jù)定理根據(jù)定理6.2.2它們不是分配格。它們不是分配格。 6.3 有補(bǔ)格有補(bǔ)格 【定義定義6.3.1】 設(shè)設(shè) X, 是格，如果是格，如果 a X， x X都有都有 a x (x a)則稱則稱a為格為格 X, 的全下的全下(上上)界，記為界，記為0(1)?！径ɡ矶ɡ?.3.1】 設(shè)設(shè) X, 是格，若格是格，若格 X, 有全下界或全上有全下界或全上界，則它們一定是惟一的。界，則它們一定是惟一的。 證明證明：用反證法。用反證法。 如果有兩個(gè)全下界如果有兩個(gè)全下界a和和b，a,b X。因?yàn)?。因?yàn)閍是全下界，所是全下界，所以以a b；又因?yàn)?；又因?yàn)閎是全下界，所以是全下界，所以b a。再由。再由 的反對(duì)

36、稱性的反對(duì)稱性有有a=b 類似地可證明全上界的惟一性。類似地可證明全上界的惟一性。第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【定義定義6.3.2】設(shè)設(shè) X, 是格，是格， X, 是格是格 X, 導(dǎo)出的代數(shù)系導(dǎo)出的代數(shù)系統(tǒng)。若格統(tǒng)。若格 X, 存在全下界存在全下界0和全上界和全上界1，則稱，則稱 X, 為有界為有界格，記為格，記為 X,0,1 。 在例在例8.4中，中， P (A), R 是格。是格。 P (A), 是是 P (A), R 導(dǎo)導(dǎo)出的代數(shù)系統(tǒng)。空集出的代數(shù)系統(tǒng)。空集是格的全下界，而集合是格的全下界，而集合A是格的全上界。因是格的全上界。因而而 P (A), 是有界格，可記為是有界格，

37、可記為 P (A),A 。在例。在例6.6中，從哈斯圖中，從哈斯圖(圖圖8.5)中可以看出，中可以看出，a是全上界，是全上界，而而e是全下界，所以是全下界，所以 A, 是有界格。是有界格。【定理定理6.3.2】 設(shè)設(shè) X,0,1 為有界格，則為有界格，則 a X有有 a0=0，a0=a； a1=a，a1=1 證明證明：因?yàn)橐驗(yàn)?是全下界且是全下界且a0 X，所以，所以0 a0，又因?yàn)椋忠驗(yàn)閍0 0，由，由 的反對(duì)稱性有的反對(duì)稱性有a0=0 顯然顯然a a，由于，由于1是全上界，所以有是全上界，所以有a 1，從而推出，從而推出 a a1，又因?yàn)橛忠驗(yàn)閍1 a，再由，再由 的反對(duì)稱性有的反對(duì)稱性

38、有a1=a a0=a 和和a1=1可以類似地證明?？梢灶愃频刈C明。第六章：格和布爾代數(shù)第六章：格和布爾代數(shù) 設(shè)設(shè) X,0,1 為有界格，為有界格，a X有有a0=0，因?yàn)楦駶M足，因?yàn)楦駶M足交換律，所以交換律，所以0a=0，這說(shuō)明，這說(shuō)明0是交運(yùn)算的零元；同樣的道是交運(yùn)算的零元；同樣的道理，理，0是并運(yùn)算的幺元，而是并運(yùn)算的幺元，而1是交運(yùn)算的幺元和并運(yùn)算的零元。是交運(yùn)算的幺元和并運(yùn)算的零元。 【定義定義6.3.3】 設(shè)設(shè) X,0,1 為有界格，如果對(duì)于為有界格，如果對(duì)于 a X， b X，使得，使得ab=1且且ab=0，則稱，則稱b是是a的補(bǔ)元。的補(bǔ)元。 如果如果b是是a的補(bǔ)元，從定義的補(bǔ)元，

39、從定義6.3.3可以看出，可以看出，a也是也是b的補(bǔ)的補(bǔ)元。因此，可以說(shuō)元。因此，可以說(shuō)a和和b是互補(bǔ)的，或者說(shuō)是互補(bǔ)的，或者說(shuō)a和和b互為補(bǔ)元。互為補(bǔ)元。 例如，在例例如，在例6.6中，從哈斯圖中，從哈斯圖(圖圖8.5)中可以看出，中可以看出，b和和c互互為補(bǔ)元，為補(bǔ)元，b和和d也互為補(bǔ)元，也互為補(bǔ)元，b有兩個(gè)補(bǔ)元有兩個(gè)補(bǔ)元c和和d。所以格中元。所以格中元素的補(bǔ)元并不惟一。素的補(bǔ)元并不惟一。 第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【例【例6.8】圖圖8.7是一個(gè)有界格的哈是一個(gè)有界格的哈斯圖。找出斯圖。找出a,b,c,d,e的補(bǔ)元。的補(bǔ)元。 解解：從圖從圖8.7中可以看出，中可以看出，a的

40、的補(bǔ)元是補(bǔ)元是e；b沒(méi)有補(bǔ)元；沒(méi)有補(bǔ)元；c的補(bǔ)元是的補(bǔ)元是d；d的補(bǔ)元是的補(bǔ)元是c和和e，e的補(bǔ)元是的補(bǔ)元是a和和d，0和和1互為補(bǔ)元?；檠a(bǔ)元。 顯然，在有界格中，全上界顯然，在有界格中，全上界1的惟一補(bǔ)元是全下界的惟一補(bǔ)元是全下界0，而全下界，而全下界0的惟一補(bǔ)元是全上界的惟一補(bǔ)元是全上界1。除了。除了1和和0，其它元素有的有補(bǔ)元，有的沒(méi)有補(bǔ)其它元素有的有補(bǔ)元，有的沒(méi)有補(bǔ)元。如果某個(gè)元素的補(bǔ)元存在，補(bǔ)元。如果某個(gè)元素的補(bǔ)元存在，補(bǔ)元可能有一個(gè)，也可能有多個(gè)。但元可能有一個(gè)，也可能有多個(gè)。但在有界分配格中，如果元素的補(bǔ)元在有界分配格中，如果元素的補(bǔ)元存在，則一定惟一。存在，則一定惟一。 第六

41、章：格和布爾代數(shù)第六章：格和布爾代數(shù)【定理定理6.3.3】設(shè)設(shè) X,0,1 為有界分配格，如果對(duì)于為有界分配格，如果對(duì)于a X，a存在補(bǔ)元存在補(bǔ)元b，則，則b是是a的惟一補(bǔ)元。的惟一補(bǔ)元。 證明證明：因?yàn)橐驗(yàn)閎是是a的補(bǔ)元，所以有的補(bǔ)元，所以有 ab=1，ab=0 設(shè)設(shè)c X，c是是a的另一個(gè)補(bǔ)元，同樣也有的另一個(gè)補(bǔ)元，同樣也有ac=1，ac=0 從而有從而有 ab= ac，ab= ac 由于由于 X,0,1 為分配格，根據(jù)定理為分配格，根據(jù)定理6.6.6必有必有b=c，即即a的補(bǔ)元惟一。的補(bǔ)元惟一?！径x定義6.3.4】設(shè)設(shè) X,0,1 為有界格，如果為有界格，如果 a X，在，在X中都有中

42、都有a的補(bǔ)元存在，則稱的補(bǔ)元存在，則稱 X,0,1 為有補(bǔ)格為有補(bǔ)格 例如，圖例如，圖8.8是三個(gè)有界格的哈斯圖，由于每一個(gè)元是三個(gè)有界格的哈斯圖，由于每一個(gè)元素至少有一個(gè)補(bǔ)元，所以它們都是有補(bǔ)格。素至少有一個(gè)補(bǔ)元，所以它們都是有補(bǔ)格。 第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)6.4 布爾代數(shù)布爾代數(shù) 【定義定義6.4.1】 有補(bǔ)分配格稱為布爾格。有補(bǔ)分配格稱為布爾格。 在布爾格中每一個(gè)元素都有補(bǔ)元。因?yàn)橛醒a(bǔ)格一定是有界在布爾格中每一個(gè)元素都有補(bǔ)元。因?yàn)橛醒a(bǔ)格一定是有界格，所以布爾格一定是有界分配格，根據(jù)定理格，所以布爾格一定是有界分配格，根據(jù)定理6.3

43、.3，布爾格中，布爾格中的每一個(gè)元素的補(bǔ)元存在且惟一。于是可以將求補(bǔ)元的運(yùn)算看的每一個(gè)元素的補(bǔ)元存在且惟一。于是可以將求補(bǔ)元的運(yùn)算看作一元運(yùn)算且把作一元運(yùn)算且把a(bǔ)的補(bǔ)元記為的補(bǔ)元記為a?！径x定義6.4.2】 設(shè)設(shè) X, 是布爾格，是布爾格， X, 是格是格 X, 導(dǎo)出導(dǎo)出的代數(shù)系統(tǒng)。稱代數(shù)系統(tǒng)的代數(shù)系統(tǒng)。稱代數(shù)系統(tǒng) X, 為布爾代數(shù)。為布爾代數(shù)。 在在6.1節(jié)中證明了節(jié)中證明了 P (A), R 是格，其中是格，其中 A= a,b 。 P (A), 是是 P (A), R 導(dǎo)出的代數(shù)系統(tǒng)，其中導(dǎo)出的代數(shù)系統(tǒng)，其中和和是集合是集合并運(yùn)算和交運(yùn)算。以后又進(jìn)一步說(shuō)明了并運(yùn)算和交運(yùn)算。以后又進(jìn)一步說(shuō)

44、明了 P (A), 是分配格和有界格，是分配格和有界格，是全下界、是全下界、A是全上界。從而是全上界。從而 P(A), 是有界分配格。令是有界分配格。令A(yù)為全集，為全集， T P (A)，T的補(bǔ)集的補(bǔ)集T=AT P (A)，滿足，滿足TT= A和和TT=，所以，所以T的補(bǔ)元的補(bǔ)元T=T。根據(jù)定義。根據(jù)定義6.4.2， P (A), 是布爾代數(shù)。是布爾代數(shù)。 第六章：格和布爾代數(shù)第六章：格和布爾代數(shù) 可以證明，當(dāng)可以證明，當(dāng)A為任意集合時(shí)，為任意集合時(shí)， P (A), 也是布爾也是布爾代數(shù)。稱為集合代數(shù)。集合代數(shù)是布爾代數(shù)的一個(gè)具體模型。代數(shù)。稱為集合代數(shù)。集合代數(shù)是布爾代數(shù)的一個(gè)具體模型。 布

45、爾代數(shù)一定是格。根據(jù)定理布爾代數(shù)一定是格。根據(jù)定理8.1.1，布爾代數(shù)中的兩個(gè)，布爾代數(shù)中的兩個(gè)二元運(yùn)算滿足交換律、結(jié)合律、冪等律和吸收律。此外，布二元運(yùn)算滿足交換律、結(jié)合律、冪等律和吸收律。此外，布爾代數(shù)還有下面的性質(zhì)：爾代數(shù)還有下面的性質(zhì)：【定理定理6.4.1】 設(shè)設(shè) X, 為布爾代數(shù)，為布爾代數(shù)， a,b X，必有，必有 (a)=a (ab)= ab (ab)= ab 證明：證明： a是是a的補(bǔ)元，的補(bǔ)元，a也是也是a的補(bǔ)元，由布爾代數(shù)中的補(bǔ)元，由布爾代數(shù)中補(bǔ)元的惟一性有補(bǔ)元的惟一性有(a)=a第六章：格和布爾代數(shù)第六章：格和布爾代數(shù) (ab)(ab)=(ab)a)(ab)b) =(b(

46、aa)(a(bb) =(b1)(a1)=11=1 (ab)(ab)=(a(ab)(b(ab) =(aa)b)(bb)a) =(0b)(0a)=00=0所以所以 (ab)= ab 同理可證同理可證 (ab)= ab 定理定理6.4.1中的中的稱為雙重否定律，稱為雙重否定律，和和稱為德摩根稱為德摩根律。布爾代數(shù)滿足雙重否定律和德摩根律。律。布爾代數(shù)滿足雙重否定律和德摩根律。第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【定理定理6.4.2】 設(shè)設(shè) X,* *, , 是代數(shù)系統(tǒng)，其中是代數(shù)系統(tǒng)，其中* *和和 都是二都是二元運(yùn)算，元運(yùn)算，是一元運(yùn)算。是一元運(yùn)算。 X,* *, , 是布爾代數(shù)的充分必要是布

47、爾代數(shù)的充分必要條件是：條件是：* *和和 在在X上封閉且滿足交換律。上封閉且滿足交換律。 * *和和 滿足分配律滿足分配律(滿足滿足* *對(duì)對(duì) 的分配律和的分配律和 對(duì)對(duì)* *的分的分配律配律)。 X中存在運(yùn)算中存在運(yùn)算* *的幺元和運(yùn)算的幺元和運(yùn)算 的幺元。設(shè)運(yùn)算的幺元。設(shè)運(yùn)算* *的的幺元為幺元為0，運(yùn)算，運(yùn)算 的幺元為的幺元為1。即。即 a X，有，有a* *0=a，a 1=a a X， a X，使得，使得a* *a=1，a a=0 由于篇幅的限制，證明從略。由于篇幅的限制，證明從略。 定理定理6.4.2給出的四個(gè)條件可以作為布爾代數(shù)的等價(jià)定給出的四個(gè)條件可以作為布爾代數(shù)的等價(jià)定義。義

48、。 布爾代數(shù)布爾代數(shù) X,* *, , 也可以表示成為也可以表示成為 X,* *, ,0,1 ，其中其中0是運(yùn)算是運(yùn)算* *的幺元，的幺元，1是運(yùn)算是運(yùn)算 的幺元。的幺元。第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【例【例6.9】設(shè)設(shè)P是所有命題構(gòu)成的集合，是所有命題構(gòu)成的集合，,和和分別是命題分別是命題的析取、合取和否定聯(lián)結(jié)詞。證明代數(shù)系統(tǒng)的析取、合取和否定聯(lián)結(jié)詞。證明代數(shù)系統(tǒng) P, 是是布爾代數(shù)。布爾代數(shù)。 證明證明：根據(jù)第根據(jù)第1章的內(nèi)容，章的內(nèi)容，和和在在P上封閉且滿足交上封閉且滿足交換律、分配律。命題常元換律、分配律。命題常元0(假假)和和1(真真)是集合是集合P的元素，滿足的元素，滿

49、足 q P，q0=q，q1=q。 q P，q P，滿足，滿足qq=1，qq=0。 根據(jù)定理根據(jù)定理6.4.2， P, 是布爾代數(shù)。是布爾代數(shù)。 例例6.9中的布爾代數(shù)中的布爾代數(shù) P, 叫做命題代數(shù)，它是布叫做命題代數(shù)，它是布爾代數(shù)的又一個(gè)模型。爾代數(shù)的又一個(gè)模型。 【定義定義6.4.3 】 設(shè)設(shè) X, 0,1 是布爾代數(shù)，是布爾代數(shù)，B 是是X的非的非空子集，若空子集，若0,1 B且且 B, 0,1 也是布爾代數(shù)。則稱也是布爾代數(shù)。則稱 B, 0,1 是是 X, , 0,1 子布爾代數(shù)。子布爾代數(shù)。 第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【定理定理6.4.3】 設(shè)設(shè) X,0,1 是布爾代數(shù)

50、，是布爾代數(shù)，B是是X的非空的非空子集，若子集，若0,1 B且運(yùn)算且運(yùn)算,在在B上封閉，則上封閉，則 B, 0,1 是是 X, 0,1 子布爾代數(shù)子布爾代數(shù) 證明證明： a,b B，因?yàn)椋驗(yàn)?B X，所以，所以 a,b X。又因?yàn)?。又因?yàn)?X,0,1 是布爾代數(shù)，故是布爾代數(shù)，故 ab=ba，ab=ba 類似類似可以證明可以證明* *和和 滿足分配律。滿足分配律。 已知已知0,1 B， a B X，a X，有，有a0=a和和a1=a a B，由，由在在B上封閉知有上封閉知有a B，使得，使得aa=1，aa=0 根據(jù)定理根據(jù)定理 6.4.2， B, 0,1 是布爾代數(shù)，它是是布爾代數(shù)，它是 X

51、,0,1 的子布爾代數(shù)。的子布爾代數(shù)。 為了方便，以下將為了方便，以下將x y且且xy記為記為x y。 第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【例例4.10】設(shè)設(shè) X, 0,1 是布爾代數(shù)，是布爾代數(shù)，a,b X，a b，令令S= x| x X，a x且且x b 試證明試證明 S,0,1 是是 X,0,1 的子布爾代數(shù)。的子布爾代數(shù)。 證明證明：由于由于a a且且a b，所以，所以a S，S是是X的非空子集，的非空子集，由由S的定義知的定義知 a是是S的全下界，的全下界，b是是S的全上界。的全上界。 x, y S， a x且且x b，a y且且y b a xy且且xy b，a xy且且xy

52、b從而從而xy S且且xy S，即運(yùn)算，即運(yùn)算和和在在S上封閉。上封閉。 x S，令，令y=(ax)b 由于由于a ax，a b，故，故a (ax)b； 又由于又由于(ax)b b，所以，所以y=(ax)b S，又，又 xy=x(ax)b) =x(ab)(xb) (分配律分配律) =x(a(xb) (a bab=a) = (xa)(xb) (結(jié)合律結(jié)合律)第六章：格和布爾代數(shù)第六章：格和布爾代數(shù) = x(xb) (a xax=x) =(xx)(xb) (分配律分配律) =1(xb) (x是是x的補(bǔ)元的補(bǔ)元) =xb (1是是的幺元的幺元) =b (x b xb=b) xy=x(ax)b) =(

53、xb)(ax) (交換律和結(jié)合律交換律和結(jié)合律) =x(ax) (由定理由定理8.1.4，x bxb=x) =(xa)(xx) (分配律分配律) =(xa)0 (x是是x的補(bǔ)元的補(bǔ)元) =(xa) (0是是的幺元的幺元) =a (由定理由定理8.1.4，a xax=a)所以所以x=y S，一元運(yùn)算，一元運(yùn)算在在S上封閉。上封閉。 根據(jù)定理根據(jù)定理6.4.3， S, , 0,1 是是 X, 0,1 的子布的子布爾代數(shù)。爾代數(shù)。第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【定義定義6.4.4】 設(shè)設(shè) X1,1,1,0,1 和和 X2,2,2, ,E 是是兩個(gè)布爾代數(shù)，其中兩個(gè)布爾代數(shù)，其中1,1,2和

54、和2都是二元運(yùn)算，都是二元運(yùn)算，和和是一元運(yùn)算，是一元運(yùn)算， 0和和1 是是X1的全下界和全上界，的全下界和全上界， ,E是是X2的全的全下界和全上界。下界和全上界。f是從是從X1到到X2的一個(gè)映射，對(duì)任意的的一個(gè)映射，對(duì)任意的a,b X1有有 f (a1b)=f (a)2f (b) f (a1b)=f (a)2 f (b) f (a)=(f (a)則稱則稱f是布爾代數(shù)是布爾代數(shù) X1,1,1,0,1 到到 X2,2,2, ,E 的的同態(tài)，簡(jiǎn)稱布爾代數(shù)同態(tài)。如果同態(tài)，簡(jiǎn)稱布爾代數(shù)同態(tài)。如果f是單射、滿射和雙射，是單射、滿射和雙射，分別稱分別稱f是布爾代數(shù)單同態(tài)、布爾代數(shù)滿同態(tài)和布爾代數(shù)是布爾代

55、數(shù)單同態(tài)、布爾代數(shù)滿同態(tài)和布爾代數(shù)同構(gòu)。稱同構(gòu)。稱 f (X1),2,2, ,E 是是 X1,1,1, 0,1 的布爾的布爾代數(shù)同態(tài)像。代數(shù)同態(tài)像。 第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【定義定義8.2.5】 設(shè)設(shè) X, 是格，具有全下界是格，具有全下界0，若，若X中的元素中的元素a蓋住了蓋住了0，則，則稱元素稱元素a為原子。為原子。 根據(jù)蓋住的定義，根據(jù)蓋住的定義，a蓋住了蓋住了0可以描述為：可以描述為：0 a且且 b X，如果有，如果有0 b a，則，則a=b。 圖圖8.10是三個(gè)格的哈是三個(gè)格的哈斯圖，在斯圖，在(a)中，中，a是原子；是原子；在在(b)中，中，a,b,c是原子；是原

56、子；在在(c)中，中，a,b是原子是原子?！径ɡ矶ɡ?.4.4】 設(shè)設(shè) X, 是格，具有全下界是格，具有全下界0，a和和b是原子，是原子，如果如果ab，則，則ab=0。 證明證明：設(shè)設(shè)ab0，0 ab a且且0 ab b，因?yàn)?，因?yàn)閍是是原子，所以原子，所以ab=a。同樣的道理。同樣的道理ab=b。于是，。于是，a=ab=b。與假設(shè)矛盾。與假設(shè)矛盾。 在圖在圖8.10的的(b)中，中，ab=0，ac0，bc=0；在圖；在圖8.10的的(c)中，中，ab=0。 設(shè)設(shè) X, 是格，如果集合是格，如果集合X是有限集，則稱是有限集，則稱 X, 是有是有限格。限格。 【定理定理6.4.5】 設(shè)設(shè) X,

57、是有限格，具有全下界是有限格，具有全下界0，則，則 b X且且b0，至少存在一個(gè)原子，至少存在一個(gè)原子a，使得，使得a b。 證明證明：如果：如果b是一個(gè)原子，則是一個(gè)原子，則b b。定理得證。定理得證。 如果如果b不是原子，必有不是原子，必有b1使得使得0 b1 b。如果。如果b1是一個(gè)原是一個(gè)原子，定理得證。否則，必有子，定理得證。否則，必有b2使得使得0 b2 b1 b。 第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)由于由于 X, 是有限格，通過(guò)有限步總可找到一個(gè)原子是有限格，通過(guò)有限步總可找到一個(gè)原子bi，使，使得得 0 bi b2 b1 b 由由 的傳遞性，的傳遞性，bi b 定理定理6

58、.4.5中的原子中的原子a不一定惟一，圖不一定惟一，圖8.10的的(c)是有限格，是有限格，元素元素c有惟一的原子有惟一的原子b，使得，使得b c。圖。圖8.10的的(b)也是有限格，也是有限格，元素元素d卻有三個(gè)原子卻有三個(gè)原子a,b,c，使得，使得a d, b d, c d。 【引理引理6.4.1】 設(shè)設(shè) X, 是布爾格，是布爾格，0是全下界，是全下界，a,b X，則，則ab=0當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)a b。 證明：證明：設(shè)設(shè)ab=0，由，由0b=b，有，有 b=0b=(ab)b=(ab)(bb)=(ab)1=ab由前面的定理知，由前面的定理知，a b。 設(shè)設(shè)a b，由于，由于b b， 因有因有

59、ab bb，而，而bb=0，所以，所以ab 0。又因?yàn)?。又因?yàn)? a且且0 b，故有，故有0 ab。由由 的反對(duì)稱性知的反對(duì)稱性知ab=0。 第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【引理引理6.4.2】設(shè)設(shè) X, 是有限布爾代數(shù)，是有限布爾代數(shù)，0是全下界，是全下界，如果如果 b X且且b0，a1,a2,ak是是X中滿足中滿足aj b(j=1,k)的所的所有原子，則有原子，則b=a1a2ak 證明證明：因?yàn)椋阂驗(yàn)閍j b(j=1,k)，所以，所以a1a2ak b 再證再證b a1a2ak，根據(jù)引理，根據(jù)引理8.2.1，只需證明，只需證明 b(a1a2ak)=0。 用反證法。設(shè)用反證法。設(shè)b(

60、a1a2ak)0 由定理由定理6.4.5，至少存在一個(gè)原子，至少存在一個(gè)原子a，使得，使得 a b(a1a2ak)又因?yàn)橛忠驗(yàn)閎(a1a2ak) b和和 b(a1a2ak) (a1a2ak) 由由 的傳遞性可得的傳遞性可得a b和和a (a1a2ak) 因?yàn)橐驗(yàn)閍是原子且滿足是原子且滿足a b，所以，所以a必是原子必是原子a1,a2, ak中中的一個(gè)，因此的一個(gè)，因此第六章：格和布爾代數(shù)第六章：格和布爾代數(shù) a a1a2ak于是有于是有 a (a1a2ak)(a1a2ak)=0即即 a 0 這與這與a是原子相矛盾。所以是原子相矛盾。所以b(a1a2ak)0，根據(jù)引理根據(jù)引理8.2.1有有 b