離散數學課件(第6章)

《離散數學》教案計算機科學與技術學院課程學時：64主講：宋成河南理工大學電子教案第六章：格和布爾代數§6.1格的概念§6.2分配格§6.3

有補格§6.4*

布爾代數第六章：格和布爾代數教學目的及要求：深刻理解和掌握格與布爾代數的基本概念和基本運算教學類容：格的概念、有補格，分配格、布爾代數和布爾表達式。教學重點：格、布爾代數和布爾表達式。教學難點：布爾代數和布爾表達式?！?.1格的概念【定義6.1.1】設X,?是偏序集，如果x,yX，集合x,y都有最小上界和最大下界，則稱X,?是格?！纠?.1】設S12＝1,2,3,4,6,12是12的因子構成的集合。其上的整除關系R=x,y|xS12∧yS12∧x整除y，R是S12上的偏序關系，S12,R是偏序集。寫出S12上的蓋住關系COVS12，畫出哈斯圖，驗證偏序集S12,R是格。

解：S12上的蓋住關系COVS12＝1,2,1,3,2,4,2,6,3,6,4,12,6,12，哈斯圖如圖6.1所示。從哈斯圖中可看出，集合S12的任意兩個元素都有最小上界和最大下界，故偏序集S12,R是格。

第六章：格和布爾代數第六章：格和布爾代數【例6.2】圖8.2中給出了一些偏序集的哈斯圖，判斷它們是否構成格。

解：它們都不是格。在(a)中，1,2沒有下界，因而沒有最大下界。在(b)中，2,4雖有兩個上界，但沒有最小上界。在(c)中，1,3沒有下界，因而沒有最大下界。在(d)中，2,3雖有三個上界，但沒有最小上界。第六章：格和布爾代數設X,?是格，x,yX，今后用x∨y表示集合x,y的最小上界，二元運算∨稱為并運算；用x∧y表示集合x,y的最大下界，二元運算∧稱為交運算。

【定義6.1.2】設X,?是格，∨是X上的并運算，∧是X上的交運算。則稱X,∨,∧是格X,?導出的代數系統。

x,yP

(A)，x∨y=x∪y，x∧y=x∩y。這樣，格P(A),R導出的代數系統P(A),∨,∧實際就是代數系統P(A),∪,∩，所以，二元運算∨和∧的運算表如表6.1和表6.2所示。在例6.1中，根據圖6.1，集合4,6的最小上界為12，即4∨6=12=4和6的最小公倍數；它的最大下界為2，即4∧6=2=4和6的最大公約數。同樣，這個結果也可以推廣到一般情況。即在格S12,R導出的代數系統S12,∨,∧中，二元運算∨是求最小公倍數；二元運算∧是求最大公約數。

第六章：格和布爾代數表6.1

表6.2∨?a??abba,baaaa,ba,ba,bbba,ba,ba,ba,ba,bba,ba,b∧?aba,b?????a?a?ab??bba,b?aba,b第六章：格和布爾代數定義6.1.3

設f是含有格中元素以及符號=,?,?,∨和∧的命題。將f中的?替換成?，?替換成?，∨替換成∧，∧替換成∨，得到一個新命題，所得的命題叫做f的對偶命題，記為f*。例如，在格中，f為a∧(b∨c)?a，則f的對偶命題f*為a∨(b∧c)?a命題f和它的對偶命題f*遵循下列的規(guī)則，這規(guī)則叫做格的對偶原理。設f是含有格中元素以及符號=,?,?,∨和∧的命題。若f對一切格為真，則f的對偶命題f*也對一切格為真。格的許多性質都是互為對偶命題的。有了格的對偶原理，在證明格的性質時，只需證明其中的一個就可以了。

第六章：格和布爾代數【定理6.1.1】設X,?是格，X,∨,∧是格X,?導出的代數系統。則a,b,cX有⑴a∨b=b∨a，a∧b=b∧a(交換律)⑵(a∨b)∨c=a∨(b∨c) (a∧b)∧c=a∧(b∧c)(結合律)⑶a∨a=a，a∧a=a(冪等律)⑷a∨(a∧b)=a

a∧(a∨b)=a(吸收律)

證明：⑴a,bX，a,b=b,a，所以它們的最小上界相等。即a∨b=b∨a，同理可證a∧b=b∧a⑵a和b的最大下界一定是a、b的下界，即a∧b?a，同理，(a∧b)∧c?a∧b，所以，(a∧b)∧c?a∧b?a同理有(a∧b)∧c?a∧b?b

和(a∧b)∧c?c第六章：格和布爾代數由以上3式得(a∧b)∧c?b∧c和(a∧b)∧c?a∧(b∧c)類似地可證a∧(b∧c)?(a∧b)∧c根據偏序關系的反對稱性有(a∧b)∧c=a∧(b∧c)由對偶原理得(a∨b)∨c=a∨(b∨c)⑶顯然a?a∨a，又由?的自反性得a?a，從而推出a∨a?a，根據偏序關系的反對稱性有a∨a=a由對偶原理得a∧a=a⑷顯然a?a∨(a∧b)，又由a?a，a∧b?a得a∨(a∧b)?a，從而得a∨(a∧b)=a。由對偶原理得a∧(a∨b)=a第六章：格和布爾代數【定理6.1.2】

設X,∨,∧是代數系統，其中∨,∧都是二元運算。如果∨和∧滿足吸收律，則∨和∧滿足冪等律。

證明：a∨a=a∨(a∧(a∨b))=a，同理可證a∧a=a【定理6.1.3】設X,∨,∧是代數系統，其中∨,∧都是二元運算，滿足交換律、結合律和吸收律，則可適當定義X的偏序關系?，使X,?構成一個格。

證明：定義X上的一個二元關系

?=a,b|a,bX且a∧b=a⑴證明?是X上的偏序關系。由定理6.1.2知∧滿足冪等律，即a∧a=a，所以a?a。故?是自反的。設a?b且b?a，則a∧b=a且b∧a=b，于是a=a∧b=b∧a=b。所以?是反對稱的。設a?b且b?c，則a∧b=a且b∧c=b，于是a∧c=(a∧b)∧c=a∧(b∧c)=a∧b=a，即a?c，故?是傳遞的。這就證明了?是X上的偏序關系。

第六章：格和布爾代數⑵證明a,bX，a∧b是集合a,b的最大下界。因為(a∧b)∧a=a∧b和(a∧b)∧b=a∧b所以a∧b?a且a∧b?b，即a∧b是a,b的下界。下證a∧b是a,b的最大下界。設c是a,b的任一下界，即c?a，c?b，那么有c∧a=c，c∧b=c而

c∧(a∧b)=(c∧a)∧b=c∧b=c所以

c?a∧b，即a∧b是a,b的最大下界。⑶

證明a∧b=a的充分必要條件是a∨b=b設a∧b=a，由吸收率可得

a∨b=(a∧b)∨b=b∨(b∧a)=b，即a∨b=b設a∨b=b，由吸收率可得

a∧b=a∧(a∨b)=a，即a∧b=a第六章：格和布爾代數⑷

證明a,bX，a∨b是集合a,b的最小上界。根據⑶，偏序關系?可以等價的定義為：

?=a,b|a,bX且a∨b=b，用這個定義和類似于⑵的方法可以證明a∨b是集合a,b的最小上界。因此，X,?構成一個格。根據定理6.1.3，可以給出格的另一個等價定義?！径x6.1.4】

設X,*,°是代數系統，其中*和°都是二元運算，如果*和°在X上封閉且滿足交換律、結合律和吸收律，則稱X,*,°為格。根據定義6.1.4和定理6.1.1，格X,?導出的代數系統X,∨,∧是格，以后不再區(qū)分偏序集定義的格和代數系統定義的格，統稱為格。第六章：格和布爾代數【定理6.1.4】

設X,?是格，∨是X上的并運算，∧是X上的交運算。則a,bX有⑴a?b當且僅當a∧b=a⑵a?b當且僅當a∨b=b證明：⑴設a?b，下證a∧b=a由a?a且a?b知a是集合a,b的下界，故有a?a∧b；另一方面，由于a∧b是a,b的最大下界，所以是a,b的下界，即a∧b?a。根據偏序關系的反對稱性得a∧b=a設a∧b=a，下證a?ba=a∧b?b，即a?b⑵可類似⑴進行證明。第六章：格和布爾代數【定理6.1.5】設X,?是格，∨是X上的并運算，∧是X上的交運算。a,b,c,dX，若a?b且c?d，則a∨c?b∨d，a∧c?b∧d

證明：

a?b?b∨d，c?d?b∨d，因此a∨c?b∨d類似的可以證明a∧c?b∧d【定理6.1.6】設X,?是格，∨是X上的并運算，∧是X上的交運算。則a,b,cX有⑴a∨(b∧c)?(a∨b)∧(a∨c)⑵(a∧b)∨(a∧c)?

a∧(b∨c)

證明：⑴根據定理8.1.5，由a?a和b∧c?b得a∨(b∧c)?a∨b又由a?a且b∧c?c得a∨(b∧c)?a∨c

從而得到a∨(b∧c)?(a∨b)∧(a∨c)利用對偶原理，即得⑵。一般地說，格中的∨和∧并不滿足分配律。

第六章：格和布爾代數【定義6.1.5】

設X,∨,∧是格，B是X的非空子集，如果B關于運算∨和∧也構成格，則稱B,∨,∧是X,∨,∧的子格。在例6.1中，令B1＝1,2,3,6，B2＝2,4,6,12，則B1,∨,∧和B2,∨,∧是格S12,∨,∧的子格。令B3＝1,2,3,12，由于2∨3=6，而6B3，所以B3,∨,∧不是格S12,∨,∧的子格。以下定義格的同態(tài)。【定義6.1.6】設X1,∨1,∧1和X2,∨2,∧2是格，其中∨1,∧1,∨2和∧2都是二元運算。f是從X1到X2的一個映射，對任意的a,bX1有f(a∨1b)=f(a)∨2f(b)，f(a∧1b)=f(a)∧2f(b)則稱f是格X1,∨1,∧1到格X2,∨2,∧2的格同態(tài)。如果f是單射、滿射和雙射，分別稱f是格單同態(tài)、格滿同態(tài)和格同構。稱f(X1),∨2,∧2是X1,∨1,∧1的格同態(tài)像。第六章：格和布爾代數【定理6.1.7】設X1,?1和X2,?2是格，X1,∨1,∧1和X2,∨2,∧2是它們導出的代數系統。f是格X1,∨1,∧1到格X2,∨2,∧2的格同態(tài)，則a,bX1，如果a?1b，必有f(a)?2f(b)證明：設a?1b，根據定理6.1.4，a∧1b=a，由于f是格X1,∨1,∧1到格X2,∨2,∧2的格同態(tài)，所以f(a)=f(a∧1b)=f(a)∧2f(b)，再由定理6.1.4，f(a)?2f(b)。定理6.1.7說明格同態(tài)是保序的。一般地說，定理6.1.7的逆并不成立。【例6.3】設A=a,b,c,d,e，A,?是格，其哈斯圖如圖8.3所示，P(A)是A的冪集合，R=x,y|xP(A)∧yP

(A)∧xy是P(A)上的偏序關系。P(A),R也是格。作映射f：A→P(A)，定義為：xA，f(x)=y|yA且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)。第六章：格和布爾代數證明：a,bA，設a?b，cf(a)，c?a，由偏序關系的傳遞性得c?b，所以cf(b)，即f(a)f(b)，于是f(a)Rf(b)。故f是保序的。對于b,dA，b∨d=af(b∨d)=f(a)=Af(b)∪f(d)=b,e∪d,e=b,d,e

f(b∨d)≠f(b)∪f(d)f不是格同態(tài)。但是，當f是格同構時，定理6.1.7的逆成立。

第六章：格和布爾代數【定理6.1.8】設X1,?1和X2,?2是格，X1,∨1,∧1和X2,∨2,∧2是它們導出的代數系統。f是X1到X2的雙射，則f是X1,∨1,∧1到X2,∨2,∧2的格同構的充分必要條件是a,bX1，a?1bf(a)?2f(b)

證明：設f是X1,∨1,∧1到X2,∨2,∧2的格同構，下證a,bX1，a?1bf(a)?2f(b)由定理6.1.7可知，a,bX1，如果a?1b，必有f(a)?2f(b)設f(a)?2f(b)，由定理6.1.4有f(a)=f(a)∧2f(b)=f(a∧1b)，由于f是雙射，故a∧1b=a，所以a?1b這就證明a?1bf(a)?2f(b)設a,bX1，a?1bf(a)?2f(b)，下證f是X1,∨1,∧1到X2,∨2,∧2的格同構。設a∧1b=c，則c?1a，c?1b，f(c)=f(a∧1b)，f(c)?2f(a)，f(c)?2f(b)，故f(c)?2f(a)∧2f(b)。設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，

第六章：格和布爾代數于是d?1a∧1b，即d?1c，故f(d)?2f(c)，再由偏序關系的反對稱性有f(c)=f(d)。即f(a∧1b)=f(c)=f(d)=f(a)∧2f(b)類似地可以證明f(a∨1b)=f(a)∨2f(b)這就證明了f是X1,∨1,∧1到X2,∨2,∧2的格同構。【定義6.1.7】

設X1,?1和X2,?2是格，X1,∨1,∧1和X2,∨2,∧2是它們導出的代數系統。其中∨1,∧1,∨2和∧2都是二元運算。a1,b1X1×X2和a2,b2X1×X2，定義X1×X2上的二元運算∨3和∧3為：a1,b1∨3a2,b2=a1∨1a2,b1∨2b2a1,b1∧3a2,b2=a1∧1a2,b1∧2b2代數系統

X1×X2,∨3,∧3稱為格X1,∨1,∧1到格X2,∨2,∧2的直積。如果X1,∨1,∧1和X2,∨2,∧2是格，可以證明代數系統X1×X2,∨3,∧3也是格第六章：格和布爾代數

§6.2分配格【定義6.2.1】

設X,?是格，X,∨,∧是X,?導出的代數系統，如果a,b,cX有a∨(b∧c)=(a∨b)∧(a∨c)(并運算對交運算可分配)a∧(b∨c)=(a∧b)∨(a∧c)(交運算對并運算可分配)則稱X,∨,∧為分配格。因為a∨(b∧c)=(a∨b)∧(a∨c)和a∧(b∨c)=(a∧b)∨(a∧c)互為對偶命題，根據對偶原理，定義6.2.1還可以改寫為：一個格如果交運算對并運算可分配或并運算對交運算可分配，則稱該格為分配格。第六章：格和布爾代數【例6.4】設A=a,b,c，P(A)=?,a,b,c,a,b,a,c,b,c,a,b,c是A的冪集合，P(A)上的包含關系R=x,y|xP

(A)∧yP

(A)∧xy是P

(A)上的偏序關系。P

(A),R是偏序集，P(A)上的蓋住關系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導出的代數系統，證明P(A),∨,∧是分配格。

證明：前面已經證明了格P(A),R導出的代數系統P

(A),∨,∧實際就是代數系統P(A),∪,∩，其中∪是集合的并運算，∩是集合的交運算。而集合的并、交運算滿足分配律：第六章：格和布爾代數P,Q,RP

(A)

P∪(Q∩R)=(P∪Q)∩(P∪R)P∩(Q∪R)=(P∩Q)∪(P∩R)所以，P

(A),∨,∧分配格。第六章：格和布爾代數

【例6.5】

A=a,b,c,d,e，A,?是格，其哈斯圖如圖8.3所示，證明A,?不是分配格。

證明：

b∨(c∧d)=b∨e=b

(b∨c)∧(b∨d)=a∧a=a b∨(c∧d)≠(b∨c)∧(b∨d)

所以，A,?不是分配格。

本例中的格叫做鉆石格，鉆石格不是分配格。

第六章：格和布爾代數【例6.6】設A=a,b,c,d,e，A,?是格，其哈斯圖如圖8.5所示，證明A,?不是分配格。證明：

d∨(b∧c)=d∨e=d(d∨b)∧(d∨c)=a∧c=cd∨(b∧c)≠(d∨b)∧(d∨c)所以，A,?不是分配格。本例中的格叫做五角格，五角格也不是分配格。鉆石格和五角格是兩個很重要的格。第六章：格和布爾代數【定理6.2.1】一個格是分配格的充分必要條件是該格中不含有與鉆石格或五角格同構的子格。這個定理的證明已經超過了本書的范圍，故略去?！就普?】設A,?是格，如果|A|＜5，則A,?一定是分配格?！就普?】設A,?是格，如果A,?是全序集，則A,?一定是分配格?！纠?.7】圖8.6給出了兩個格的哈斯圖。試證明它們都不是分配格。證明：在圖8.6

(a)中含有與五角格同構的子格，所以不是分配格；在圖8.6

(b)中含有與鉆石格同構的子格，所以不是分配格。

第六章：格和布爾代數第六章：格和布爾代數【定理6.2.2】

設X,?是格，X,∨,∧是格X,?導出的代數系統。X,?是分配格的充分必要條件是a,b,cX，當a∧b=a∧c且a∨b=a∨c時，必有b=c證明：設X,?是分配格，a,b,cX，a∧b=a∧c且a∨b=a∨cb=b∨(b∧a)=b∨(a∧b)

(吸收律和交換律)=b∨(a∧c)=(b∨a)∧(b∨c)(已知代入和分配律)=(a∨c)∧(b∨c)(交換律和已知代入)=(a∧b)∨c(分配律)=(a∧c)∨c(已知條件代入)=c(交換律和吸收律) 設a,b,cX，當a∧b=a∧c且a∨b=a∨c時，有b=c，但X,∨,∧不是分配格。由定理6.2.1知X,∨,∧中必含有與鉆石格或五角格同構的子格。假設X,∨,∧含有與鉆石格同構的子格，且此子格為S,∨,∧，其中S=u,v,x,y,z，u為它的最大元，v為它的最小元。從而x∨y=u=x∨z，x∧y=v=x∧z，但y≠z，與已知矛盾。第六章：格和布爾代數對五角格的情況，可類似證明。例如，在圖8.6(a)中，b∧c=g=b∧f且b∨c=a=b∨f，但c≠f；在圖8.6(b)中，b∧c=f=b∧e且b∨c=a=b∨e，但c≠e。根據定理6.2.2它們不是分配格。

§6.3有補格

【定義6.3.1】

設X,?是格，如果aX，xX都有a?x(x?a)則稱a為格X,?的全下(上)界，記為0(1)?！径ɡ?.3.1】設X,?是格，若格X,?有全下界或全上界，則它們一定是惟一的。

證明：用反證法。如果有兩個全下界a和b，a,bX。因為a是全下界，所以a?b；又因為b是全下界，所以b?a。再由?的反對稱性有a=b類似地可證明全上界的惟一性。第六章：格和布爾代數【定義6.3.2】設X,?是格，X,∨,∧是格X,?導出的代數系統。若格X,∨,∧存在全下界0和全上界1，則稱X,∨,∧為有界格，記為X,∨,∧,0,1。在例8.4中，P(A),R是格。P

(A),∨,∧是P(A),R導出的代數系統?？占?是格的全下界，而集合A是格的全上界。因而P

(A),∨,∧是有界格，可記為P(A)∨,∧,?,A。在例6.6中，從哈斯圖(圖8.5)中可以看出，a是全上界，而e是全下界，所以A,?是有界格?！径ɡ?.3.2】設X,∨,∧,0,1為有界格，則aX有

a∧0=0，a∨0=a；a∧1=a，a∨1=1

證明：因為0是全下界且a∧0X，所以0?a∧0，又因為a∧0?0，由?的反對稱性有a∧0=0顯然a?a，由于1是全上界，所以有a?1，從而推出a?a∧1，又因為a∧1?a，再由?的反對稱性有a∧1=aa∨0=a和a∨1=1可以類似地證明。第六章：格和布爾代數設X,∨,∧,0,1為有界格，aX有a∧0=0，因為格滿足交換律，所以0∧a=0，這說明0是交運算的零元；同樣的道理，0是并運算的幺元，而1是交運算的幺元和并運算的零元。

【定義6.3.3】設X,∨,∧,0,1為有界格，如果對于aX，bX，使得a∨b=1且a∧b=0，則稱b是a的補元。如果b是a的補元，從定義6.3.3可以看出，a也是b的補元。因此，可以說a和b是互補的，或者說a和b互為補元。例如，在例6.6中，從哈斯圖(圖8.5)中可以看出，b和c互為補元，b和d也互為補元，b有兩個補元c和d。所以格中元素的補元并不惟一。第六章：格和布爾代數【例6.8】圖8.7是一個有界格的哈斯圖。找出a,b,c,d,e的補元。

解：從圖8.7中可以看出，a的補元是e；b沒有補元；c的補元是d；d的補元是c和e，e的補元是a和d，0和1互為補元。顯然，在有界格中，全上界1的惟一補元是全下界0，而全下界0的惟一補元是全上界1。除了1和0，其它元素有的有補元，有的沒有補元。如果某個元素的補元存在，補元可能有一個，也可能有多個。但在有界分配格中，如果元素的補元存在，則一定惟一。

第六章：格和布爾代數【定理6.3.3】設X,∨,∧,0,1為有界分配格，如果對于aX，a存在補元b，則b是a的惟一補元。

證明：因為b是a的補元，所以有a∨b=1，a∧b=0設cX，c是a的另一個補元，同樣也有a∨c=1，a∧c=0從而有a∨b=a∨c，a∧b=a∧c由于X,∨,∧,0,1為分配格，根據定理6.6.6必有b=c，即a的補元惟一?！径x6.3.4】設X,∨,∧,0,1為有界格，如果aX，在X中都有a的補元存在，則稱X,∨,∧,0,1為有補格例如，圖8.8是三個有界格的哈斯圖，由于每一個元素至少有一個補元，所以它們都是有補格。

第六章：格和布爾代數第六章：格和布爾代數§6.4布爾代數【定義6.4.1】

有補分配格稱為布爾格。在布爾格中每一個元素都有補元。因為有補格一定是有界格，所以布爾格一定是有界分配格，根據定理6.3.3，布爾格中的每一個元素的補元存在且惟一。于是可以將求補元的運算看作一元運算且把a的補元記為a′?！径x6.4.2】設X,?是布爾格，X,∨,∧,′是格X,?導出的代數系統。稱代數系統X,∨,∧,′為布爾代數。在6.1節(jié)中證明了P

(A),R是格，其中A=a,b。P

(A),∪,∩是P

(A),R導出的代數系統，其中∪和∩是集合并運算和交運算。以后又進一步說明了P

(A),∪,∩是分配格和有界格，?是全下界、A是全上界。從而P(A),∪,∩是有界分配格。令A為全集，TP

(A)，T的補集~T=A–TP

(A)，滿足T∪~T=A和T∩~T=?，所以T的補元T′=~T。根據定義6.4.2，P(A),∪,∩,~是布爾代數。

第六章：格和布爾代數

可以證明，當A為任意集合時，P(A),∪,∩,~也是布爾代數。稱為集合代數。集合代數是布爾代數的一個具體模型。布爾代數一定是格。根據定理8.1.1，布爾代數中的兩個二元運算滿足交換律、結合律、冪等律和吸收律。此外，布爾代數還有下面的性質：【定理6.4.1】

設X,∨,∧,′為布爾代數，a,bX，必有⑴(a′)′=a⑵(a∨b)′=a′∧b′⑶(a∧b)′=a′∨b′證明：⑴a′是a的補元，a也是a′的補元，由布爾代數中補元的惟一性有(a′)′=a第六章：格和布爾代數⑵(a∨b)∨(a′∧b′)=((a∨b)∨a′)∧((a∨b)∨b′)=(b∨(a∨a′))∧(a∨(b∨b′))=(b∨1)∧(a∨1)=1∧1=1(a∨b)∧(a′∧b′)=(a∧(a′∧b′))∨(b∧(a′∧b′))=((a∧a′)∧b′)∨((b∧b′)∧a′)=(0∧b′)∨(0∧a′)=0∨0=0所以(a∨b)′=a′∧b′⑶同理可證(a∧b)′=a′∨b′定理6.4.1中的⑴稱為雙重否定律，⑵和⑶稱為德摩根律。布爾代數滿足雙重否定律和德摩根律。第六章：格和布爾代數【定理6.4.2】

設X,*,°,′是代數系統，其中*和°都是二元運算，′是一元運算。X,*,°,′是布爾代數的充分必要條件是：⑴*和°在X上封閉且滿足交換律。⑵*和°滿足分配律(滿足*對°的分配律和°對*的分配律)。⑶X中存在運算*的幺元和運算°的幺元。設運算*的幺元為0，運算°的幺元為1。即aX，有a*0=a，a°1=a⑷

aX，a′X，使得a*a′=1，a°a′=0由于篇幅的限制，證明從略。定理6.4.2給出的四個條件可以作為布爾代數的等價定義。布爾代數X,*,°,′也可以表示成為X,*,°,′,0,1，其中0是運算*的幺元，1是運算°的幺元。第六章：格和布爾代數【例6.9】設P是所有命題構成的集合，∨,∧和?分別是命題的析取、合取和否定聯結詞。證明代數系統P,∨,∧,?是布爾代數。

證明：根據第1章的內容，∨和∧在P上封閉且滿足交換律、分配律。命題常元0(假)和1(真)是集合P的元素，滿足qP，q∨0=q，q∧1=q。

qP，?qP，滿足q∨?q=1，q∧?q=0。根據定理6.4.2，P,∨,∧,?是布爾代數。例6.9中的布爾代數P,∧,∨,?叫做命題代數，它是布爾代數的又一個模型?！径x6.4.3】

設X,∨,∧,′,0,1是布爾代數，B是X的非空子集，若0,1B且B,∨,∧,′,0,1也是布爾代數。則稱B,∨,∧,′,0,1是X,∨,∧,′,0,1子布爾代數。第六章：格和布爾代數【定理6.4.3】設X,∨,∧,′,0,1是布爾代數，B是X的非空子集，若0,1B且運算∨,∧,′在B上封閉，則B,∨,∧,′,0,1是X,∨,∧,′,0,1子布爾代數

證明：⑴a,bB，因為BX，所以a,bX。又因為X,∨,∧,′,0,1是布爾代數，故a∨b=b∨a，a∧b=b∧a⑵類似⑴可以證明*和°滿足分配律。⑶

已知0,1B，aBX，aX，有a∨0=a和a∧1=a⑷aB，由′在B上封閉知有a′B，使得a∨a′=1，a∧a′=0根據定理6.4.2，B,∨,∧,′,0,1是布爾代數，它是X,∨,∧,′,0,1的子布爾代數。為了方便，以下將x?y且x≠y記為x?y。

第六章：格和布爾代數【例4.10】設X,∨,∧,′,0,1是布爾代數，a,bX，a?b，令S=x|xX，a?x且x?b試證明S,∨,∧,′,0,1是X,∨,∧,′,0,1的子布爾代數。

證明：由于a?a且a?b，所以aS，S是X的非空子集，由S的定義知a是S的全下界，b是S的全上界。x,yS，a?x且x?b，a?y且y?ba?x∨y且x∨y?b，a?x∧y且x∧y?b從而x∨yS且x∧yS，即運算∨和∧在S上封閉。xS，令y=(a∨x′)∧b由于a?a∨x′，a?b，故a?(a∨x′)∧b；又由于(a∨x′)∧b?b，所以y=(a∨x′)∧bS，又x∨y=x∨((a∨x′)∧b)=x∨((a∧b)∨(x′∧b))(分配律)=x∨(a∨(x′∧b))(a?ba∧b=a)=(x∨a)∨(x′∧b)(結合律)第六章：格和布爾代數=x∨(x′∧b)(a?xa∨x=x)=(x∨x′)∧(x∨b)(分配律)=1∧(x∨b)(x′是x的補元)=x∨b (1是∧的幺元)=b(x?b

x∨b=b)x∧y=x∧((a∨x′)∧b)=(x∧b)∧(a∨x′)(交換律和結合律)=x∧(a∨x′)(由定理8.1.4，x?bx∧b=x)=(x∧a)∨(x∧x′)(分配律)=(x∧a)∨0(x′是x的補元)=(x∧a)(0是∨的幺元)=a(由定理8.1.4，a?xa∧x=a)所以x′=yS，一元運算′在S上封閉。

根據定理6.4.3，S,∨,∧,′,0,1是X,∨,∧,′,0,1的子布爾代數。第六章：格和布爾代數【定義6.4.4】

設X1,∨1,∧1,′,0,1和X2,∨2,∧2,",,E是兩個布爾代數，其中∨1,∧1,∨2和∧2都是二元運算，′和"是一元運算，0和1是X1的全下界和全上界，,E是X2的全下界和全上界。f是從X1到X2的一個映射，對任意的a,bX1有f(a∨1b)=f(a)∨2f(b)f(a∧1b)=f(a)∧2

f(b)f(a′)=(f(a))"則稱f是布爾代數X1,∨1,∧1,′,0,1到X2,∨2,∧2,",,E

的同態(tài)，簡稱布爾代數同態(tài)。如果f是單射、滿射和雙射，分別稱f是布爾代數單同態(tài)、布爾代數滿同態(tài)和布爾代數同構。稱f(X1),∨2,∧2,",,E

是X1,∨1,∧1,′,0,1的布爾代數同態(tài)像。第六章：格和布爾代數【定義8.2.5】設X,?是格，具有全下界0，若X中的元素a蓋住了0，則稱元素a為原子。根據蓋住的定義，a蓋住了0可以描述為：0?a且bX，如果有0?b?a，則a=b。圖8.10是三個格的哈斯圖，在(a)中，a是原子；在(b)中，a,b,c是原子；在(c)中，a,b是原子。【定理6.4.4】設X,?是格，具有全下界0，a和b是原子，如果a≠b，則a∧b=0。

證明：設a∧b≠0，0?a∧b?a且0?a∧b?b，因為a是原子，所以a∧b=a。同樣的道理a∧b=b。于是，a=a∧b=b。與假設矛盾。在圖8.10的(b)中，a∧b=0，a∧c＝0，b∧c=0；在圖8.10的(c)中，a∧b=0。設X,?是格，如果集合X是有限集，則稱X,?是有限格?！径ɡ?.4.5】

設X,?是有限格，具有全下界0，則bX且b≠0，至少存在一個原子a，使得a?b。

證明：如果b是一個原子，則b?b。定理得證。如果b不是原子，必有b1使得0?b1?b。如果b1是一個原子，定理得證。否則，必有b2使得0?b2?b1?b?！?/p>

第六章：格和布爾代數由于X,?是有限格，通過有限步總可找到一個原子bi，使得

0?bi?…?b2?b1?b由?的傳遞性，bi?b定理6.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】設X,?是布爾格，0是全下界，a,bX，則a∧b′=0當且僅當a?b。

證明：設a∧b′=0，由0∨b=b，有b=0∨b=(a∧b′)∨b=(a∨b)∧(b′∨b)=(a∨b)∧1=a∨b由前面的定理知，a?b。設a?b，由于b′?b′，因有a∧b′?b∧b′，而b∧b′=0，所以a∧b′?0。又因為0?a且0?b′，故有0?a∧b′。由?的反對稱性知a∧b′=0。

第六章：格和布爾代數【引理6.4.2】設X,∨,∧,′是有限布爾代數，0是全下界，如果bX且b≠0，a1,a2,…,ak是X中滿足aj?b(j=1,…,k)的所有原子，則b=a1∨a2∨…∨ak

證明：因為aj?b(j=1,…,k)，所以a1∨a2∨…∨ak?b再證b?a1∨a2∨…∨ak，根據引理8.2.1，只需證明b∧(a1∨a2∨…∨ak)′=0。用反證法。設b∧(a1∨a2∨…∨ak)′≠0由定理6.4.5，至少存在一個原子a，使得a?b∧(a1∨a2∨…∨ak)′又因為b∧(a1∨a2∨…∨ak)′?b和

b∧(a1∨a2∨…∨ak)′?(a1∨a2∨…∨ak)′由?的傳遞性可得a?b和a?(a1∨a2∨…∨ak)′因為a是原子且滿足a?b，所以a必是原子a1,a2,…,ak中的一個，因此第六章：格和布爾代數a?a1∨a2∨…∨ak于是有a?(a1∨a2∨…∨ak)∧(a1∨a2∨…∨ak)′=0即a?0這與a是原子相矛盾。所以b∧(a1∨a2∨…∨ak)′＝0，根據引理8.2.1有b?a1∨a2∨…∨ak由?的反對稱性知b＝a1∨a2∨…∨ak

【引理6.4.3】

設X,∨,∧,′是有限布爾代數，如果bX且b≠0，a1,a2,…,ak是X中滿足aj?b(j=1,…,k)的所有原子。則b=a1∨a2∨…∨ak是將b表示為原子的惟一形式。第六章：格和布爾代數

證明：設有b的另外一種表示形式b=∨∨…∨且是X中的原子。因為b是的最小上界，所以必有?b(i=1,…,t)，而a1,a2,…,ak是X中滿足aj?b(j=1,…,k)的所有不同的原子。所以，必有t≤k。當t＜k時，a1,a2,…,ak中必有使得≠，i=1,…,t于是，∧=(∧a1)∨(∧a2)∨…∨(∧)∨…∨(∧ak)=∧(a1∨a2∨…∨ak)=∧(∨∨…∨)=(∧)∨(∧)∨…∨(∧)=0∨0∨…∨0=0第六章：格和布爾代數從而=0，與是原子矛盾。所以只能有t=k【定理6.4.6】(有限布爾代數表示定理)設X,∨,∧,′是由有限布爾格X,?導出的有限布爾代數，S是布爾格X,?中所有原子的集合，則X,∨,∧,′和P

(S),∪,∩,~同構。

證明：xX，令T(x)=a|aS且a?x，顯然T(x)S。定義函數f：X→P(S)，f(x)=T(x)，xX⑴證明f是X到P

(S)的雙射函數。設f(x)=f(y)，令f(x)=f(y)=a1,a2,…,an，由引理6.4.3知x＝a1∨a2∨…∨an＝y。于是f是單射。設b1,b2,…,bnP(S)，令x=b1∨b2∨…∨bn，由運算∨的封閉性得xX且bi?x，i=1,…,n，f(x)=T(x)=b1,b2,…,bn，所以f是滿射。故f是X到P(S)的雙射函數。第六章：格和布爾代數⑵證明f是X,∨,∧,′和P(S),∪,∩,~同構。x,yX，對于任意的bbT(x∧y)

bS且b?x∧y(bS且b?x)且(bS且b?y)bT(x)且bT(y)bT(x)∩T(y)從而有T(x∧y)=T(x)∩T(y)，因此f(x∧y)=T(x∧y)=T(x)∩T(y)=f(x)∩f(y)x,yX，令T(x)=a|aS且a?x=a1,a2,…,an