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

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

2、和布爾表達式。格、布爾代數(shù)和布爾表達式。教學(xué)難點：教學(xué)難點： 布爾代數(shù)和布爾表達式。布爾代數(shù)和布爾表達式。6.1 格的概念格的概念【定義【定義6.1.1】 設(shè)設(shè) X, 是偏序集，如果是偏序集，如果 x,y X，集合，集合 x,y 都有最小上界和最大下界，則稱都有最小上界和最大下界，則稱 X, 是格。是格。【例【例6.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 是偏序集。寫出是偏序集。寫出S12上的蓋住關(guān)系上的蓋住關(guān)系CO

3、V S12，畫出哈斯圖，驗證偏序集，畫出哈斯圖，驗證偏序集 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的任意兩的任意兩個元素都有最小上界和最大下界，故偏序集個元素都有最小上界和最大下界，故偏序集 S12,R 是格。是格。 第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【例【例6.2】圖圖8.2中給出了一些偏序集的哈斯圖，判斷它們是中給出了一些偏序集的哈斯

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

5、運算；用xy表示集合表示集合 x,y 的最的最大下界，二元運算大下界，二元運算稱為交運算。稱為交運算。 【定義定義6.1.2】 設(shè)設(shè) X, 是格，是格，是是X上的并運算，上的并運算，是是X上的上的交運算。則稱交運算。則稱 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ù)系統(tǒng)實際就是代數(shù)系統(tǒng) P (A), ，所以，二元運算所以，二元運算和和的運算表如表的運算表如表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ù)。同樣，這個結(jié)果也可以推廣到一的最大公約數(shù)。同樣，這個結(jié)果也可以推廣到一般情況。即在格般情況。即在格 S12,R 導(dǎo)出的代數(shù)系統(tǒng)導(dǎo)出的代數(shù)系統(tǒng) S12, 中，二元中，二元運算運算是求最小公倍數(shù)；二元運算是求最小公倍數(shù)；二元運算是求最大公約數(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是含有格中元素以及符號是含有格中元素以及符號=, , ,和和的命的命題。將題。將f中的中的 替換成替換成 ， 替換成替換成 ，替換成替換成，替換成替換成，得到一個新命題，所得的命題叫做，得到一個新命題，所得的命題叫做f的對偶命的對偶命題，記為題，記為f *。 例如，在格中，例如，在格中，f為為a(bc) a，則，則f的對偶命題的對偶命題f *為為a(bc) a 命題命題f和它的對偶命題和它的對偶命題f *遵循下列的規(guī)則，這規(guī)則叫遵循下列的規(guī)則，這規(guī)則叫做格的對偶原理。做格的對偶原理。 設(shè)設(shè)f是含有格中元素以及符號是含有格中元素

8、以及符號=,和和的命題。的命題。 若若f對一切格為真，則對一切格為真，則f的對偶命題的對偶命題f *也對一切格為真。也對一切格為真。 格的許多性質(zhì)都是互為對偶命題的。有了格的對偶原格的許多性質(zhì)都是互為對偶命題的。有了格的對偶原理，在證明格的性質(zhì)時，只需證明其中的一個就可以了。理，在證明格的性質(zhì)時，只需證明其中的一個就可以了。 第六章：格和布爾代數(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)系的反對稱性有根據(jù)偏序關(guān)系的反對稱性有(ab)c= a(bc) 由對偶原理得由對偶原理得 (ab)c= a(bc) 顯然顯然a aa，又由，又由 的自反性得的自反性得a a，從而推出，從而推出aa a，根據(jù)偏序關(guān)系的反對稱性有，根據(jù)偏序關(guān)系的反對稱性有aa=a 由對偶原理得由對偶原理得aa=a 顯然顯然 a a(ab)， 又由又由a a，ab a得得a(ab) a，從而得，從而得 a(ab)=a。 由對偶原理得由對偶原理得a(ab)=a第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【定理【定理6.1.2】 設(shè)設(shè) X, 是代數(shù)系統(tǒng)，其中是代數(shù)系統(tǒng)，其中,都是二元運算。都是二元運算。如果如果和和滿足

11、吸收律，則滿足吸收律，則和和滿足冪等律。滿足冪等律。 證明證明：aa=a(a(ab)=a，同理可證，同理可證aa=a【定理定理6.1.3】 設(shè)設(shè) X, 是代數(shù)系統(tǒng)，其中是代數(shù)系統(tǒng)，其中,都是二元運算，都是二元運算，滿足交換律、結(jié)合律和吸收律，則可適當(dāng)定義滿足交換律、結(jié)合律和吸收律，則可適當(dāng)定義X的偏序關(guān)系的偏序關(guān)系 ，使，使 X, 構(gòu)成一個格。構(gòu)成一個格。 證明證明：定義定義X上的一個二元關(guān)系上的一個二元關(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。所以所以 是反對稱的。是反對稱的。 設(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 的最大下界。因為的最大下界。因為 (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、價的定義為：可以等價的定義為： =a,b |a,b X且且ab=b ，用這個定義和類似于用這個定義和類似于的方法可以證明的方法可以證明ab是集合是集合 a,b 的的最小上界。最小上界。 因此，因此， X, 構(gòu)成一個格。構(gòu)成一個格。 根據(jù)定理根據(jù)定理6.1.3，可以給出格的另一個等價定義。，可以給出格的另一個等價定義。 【定義定義6.1.4】 設(shè)設(shè) X,* *, 是代數(shù)系統(tǒng)，其中是代數(shù)系統(tǒng)，其中* *和和 都是二都是二元運算，如果元運算，如果* *和和 在在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上的并運算，上的并運算，是是X上的交運算。則上的交運算。則 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)系的反對稱性得。根據(jù)偏序關(guān)系的反對稱性得ab=a 設(shè)設(shè)ab=a，下證，下證a b a=ab b，即，即a b 可類似可類似進行證明。進行證明。第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【 定理定理6.1.5】 設(shè)設(shè) X, 是格，是格，是是X上的并運算，上的并運算，是是X上的上的交運算。交運算。 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上的并運算，上的并運算，是是X上的交上的交運算。則運算。則 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) 利用對偶原理，即得利用對偶原理，即得。 一般地說，格中的一般地說，格中的和和并不滿足分配律。并不滿足分配律。 第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【定義【定義6.1.5】 設(shè)設(shè) X, 是格，是格，B是是X的非空子集，如果的非空子集，如果B關(guān)于運算關(guā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都是二元運算。都是二元運算。f是從是從X1到到X2的一個映射，對任的一個映射，對任意的意的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說明格同態(tài)是保序的。一般地說，定理說明格同態(tài)是保序的。一般地說，定理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是保序的。是保序的。 對于對于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)時，是格同構(gòu)時，定理定理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)系的反對稱性有反對稱性有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)?！径x定義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都是二元運算。都是二元運算。a1,b1X1X2和和a2,b2X1X2，定，定義義X1X2上的二元運算上的二元運算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) (并運算對交運算可分配并運算對交運算可分配) a(bc)=(ab)(ac) (交運算對并運算可分配交運算對并運算可分配)則

27、稱則稱 X, 為分配格。為分配格。 因為因為a(bc)=(ab)(ac)和和 a(bc)=(ab)(ac) 互為對偶命題，根據(jù)對偶原理，定義互為對偶命題，根據(jù)對偶原理，定義6.2.1還可以改寫為：還可以改寫為：一個格如果交運算對并運算可分配或并運算對交運算可分一個格如果交運算對并運算可分配或并運算對交運算可分配，則稱該格為分配格。配，則稱該格為分配格。第六章：格和布爾代數(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ù)系統(tǒng)實際就是代數(shù)系統(tǒng) P (A), ，其中，其中是集合的并運算，是集合的并運算，是集合的交運算。而集合的并、交運是集合的交運算。而集合的并、交運算滿足分配律：算滿足分配律：第六章：格和布爾代數(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、格和五角格是也不是分配格。鉆石格和五角格是兩個很重要的格。兩個很重要的格。第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【定理定理6.2.1 】一個格是分配格的充分必要條件是該格中不一個格是分配格的充分必要條件是該格中不含有與鉆石格或五角格同構(gòu)的子格。含有與鉆石格或五角格同構(gòu)的子格。 這個定理的證明已經(jīng)超過了本書的范圍，故略去。這個定理的證明已經(jīng)超過了本書的范圍，故略去。【 推論推論1】 設(shè)設(shè) A, 是格，如果是格，如果|A|5，則，則 A, 一定是一定是分配格。分配格。【推論推論2】 設(shè)設(shè) A, 是格，如果是格，如果 A, 是全序集，則是全序集，則 A, 一定是分配格。一定是分配格?！纠?.7】

32、圖圖8.6給出了兩個格的哈斯圖。試證明它們都不給出了兩個格的哈斯圖。試證明它們都不是分配格。是分配格。 證明：證明：在圖在圖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時，必有時，必有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時，有時，有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ù) 對五角格的情況，可類似證明。對五角格的情況，可類似證明。 例如，在圖例如，在圖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 有補格有補格 【定義定義6.3.1】 設(shè)設(shè) X, 是格，如果是格，如果 a X， x X都有都有 a x (x a)則稱則稱a為格為格 X, 的全下的全下(上上)界，記為界，記為0(1)?！径ɡ矶ɡ?.3.1】 設(shè)設(shè) X, 是格，若格是格，若格 X, 有全下界或全上有全下界或全上界，則它們一定是惟一的。界，則它們一定是惟一的。 證明證明：用反證法。用反證法。 如果有兩個全下界如果有兩個全下界a和和b，a,b X。因為。因為a是全下界，所是全下界，所以以a b；又因為；又因為b是全下界，所以是全下界，所以b a。再由。再由 的反對

36、稱性的反對稱性有有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 證明證明：因為因為0是全下界且是全下界且a0 X，所以，所以0 a0，又因為，又因為a0 0，由，由 的反對稱性有的反對稱性有a0=0 顯然顯然a a，由于，由于1是全上界，所以有是全上界，所以有a 1，從而推出，從而推出 a a1，又因為又因為a1 a，再由，再由 的反對稱性有的反對稱性

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

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

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

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

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

43、.3，布爾格中，布爾格中的每一個元素的補元存在且惟一。于是可以將求補元的運算看的每一個元素的補元存在且惟一。于是可以將求補元的運算看作一元運算且把作一元運算且把a的補元記為的補元記為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)，其中和和是集合是集合并運算和交運算。以后又進一步說明了并運算和交運算。以后又進一步說

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

45、爾代數(shù)一定是格。根據(jù)定理布爾代數(shù)一定是格。根據(jù)定理8.1.1，布爾代數(shù)中的兩個，布爾代數(shù)中的兩個二元運算滿足交換律、結(jié)合律、冪等律和吸收律。此外，布二元運算滿足交換律、結(jié)合律、冪等律和吸收律。此外，布爾代數(shù)還有下面的性質(zhì)：爾代數(shù)還有下面的性質(zhì)：【定理定理6.4.1】 設(shè)設(shè) X, 為布爾代數(shù)，為布爾代數(shù)， a,b X，必有，必有 (a)=a (ab)= ab (ab)= ab 證明：證明： a是是a的補元，的補元，a也是也是a的補元，由布爾代數(shù)中的補元，由布爾代數(shù)中補元的惟一性有補元的惟一性有(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)，其中* *和和 都是二都是二元運算，元運算，是一元運算。是一元運算。 X,* *, , 是布爾代數(shù)的充分必要是布

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

48、。 布爾代數(shù)布爾代數(shù) X,* *, , 也可以表示成為也可以表示成為 X,* *, ,0,1 ，其中其中0是運算是運算* *的幺元，的幺元，1是運算是運算 的幺元。的幺元。第六章：格和布爾代數(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ù)的又一個模型。爾代數(shù)的又一個模型。 【定義定義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且運算且運算,在在B上封閉，則上封閉，則 B, 0,1 是是 X, 0,1 子布爾代數(shù)子布爾代數(shù) 證明證明： a,b B，因為，因為 B X，所以，所以 a,b X。又因為。又因為 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，即運算，即運算和和在在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的補元的補元) =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的補元的補元) =(xa) (0是是的幺元的幺元) =a (由定理由定理8.1.4，a xax=a)所以所以x=y S，一元運算，一元運算在在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 是是兩個布爾代數(shù)，其中兩個布爾代數(shù)，其中1,1,2和

54、和2都是二元運算，都是二元運算，和和是一元運算，是一元運算， 0和和1 是是X1的全下界和全上界，的全下界和全上界， ,E是是X2的全的全下界和全上界。下界和全上界。f是從是從X1到到X2的一個映射，對任意的的一個映射，對任意的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)，簡稱布爾代數(shù)同態(tài)。如果同態(tài)，簡稱布爾代數(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是三個格的哈是三個格的哈斯圖，在斯圖，在(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，因為，因為a是是原子，所以原子，所以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，至少存在一個原子，至少存在一個原子a，使得，使得a b。 證明證明：如果：如果b是一個原子，則是一個原子，則b b。定理得證。定理得證。 如果如果b不是原子，必有不是原子，必有b1使得使得0 b1 b。如果。如果b1是一個原是一個原子，定理得證。否則，必有子，定理得證。否則，必有b2使得使得0 b2 b1 b。 第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)由于由于 X, 是有限格，通過有限步總可找到一個原子是有限格，通過有限步總可找到一個原子bi，使，使得得 0 bi b2 b1 b 由由 的傳遞性，的傳遞性，bi b 定理定理6

58、.4.5中的原子中的原子a不一定惟一，圖不一定惟一，圖8.10的的(c)是有限格，是有限格，元素元素c有惟一的原子有惟一的原子b，使得，使得b c。圖。圖8.10的的(b)也是有限格，也是有限格，元素元素d卻有三個原子卻有三個原子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。又因為。又因為0 a且且0 b，故有，故有0 ab。由由 的反對稱性知的反對稱性知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 證明證明：因為：因為aj 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，至少存在一個原子，至少存在一個原子a，使得，使得 a b(a1a2ak)又因為又因為b(a1a2ak) b和和 b(a1a2ak) (a1a2ak) 由由 的傳遞性可得的傳遞性可得a b和和a (a1a2ak) 因為因為a是原子且滿足是原子且滿足a b，所以，所以a必是原子必是原子a1,a2, ak中中的一個，因此的一個，因此第六章：格和布爾代數(shù)第六章：格和布爾代數(shù) a a1a2ak于是有于是有 a (a1a2ak)(a1a2ak)=0即即 a 0 這與這與a是原子相矛盾。所以是原子相矛盾。所以b(a1a2ak)0，根據(jù)引理根據(jù)引理8.2.1有有 b