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

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

有補(bǔ)格§6.4*

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

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

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

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

【定義6.1.2】設(shè)X,?是格，∨是X上的并運(yùn)算，∧是X上的交運(yùn)算。則稱X,∨,∧是格X,?導(dǎo)出的代數(shù)系統(tǒng)。

x,yP

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

第六章：格和布爾代數(shù)表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第六章：格和布爾代數(shù)定義6.1.3

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

第六章：格和布爾代數(shù)【定理6.1.1】設(shè)X,?是格，X,∨,∧是格X,?導(dǎo)出的代數(shù)系統(tǒng)。則a,b,cX有⑴a∨b=b∨a，a∧b=b∧a(交換律)⑵(a∨b)∨c=a∨(b∨c) (a∧b)∧c=a∧(b∧c)(結(jié)合律)⑶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第六章：格和布爾代數(shù)由以上3式得(a∧b)∧c?b∧c和(a∧b)∧c?a∧(b∧c)類似地可證a∧(b∧c)?(a∧b)∧c根據(jù)偏序關(guān)系的反對稱性有(a∧b)∧c=a∧(b∧c)由對偶原理得(a∨b)∨c=a∨(b∨c)⑶顯然a?a∨a，又由?的自反性得a?a，從而推出a∨a?a，根據(jù)偏序關(guān)系的反對稱性有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第六章：格和布爾代數(shù)【定理6.1.2】

設(shè)X,∨,∧是代數(shù)系統(tǒng)，其中∨,∧都是二元運(yùn)算。如果∨和∧滿足吸收律，則∨和∧滿足冪等律。

證明：a∨a=a∨(a∧(a∨b))=a，同理可證a∧a=a【定理6.1.3】設(shè)X,∨,∧是代數(shù)系統(tǒng)，其中∨,∧都是二元運(yùn)算，滿足交換律、結(jié)合律和吸收律，則可適當(dāng)定義X的偏序關(guān)系?，使X,?構(gòu)成一個格。

證明：定義X上的一個二元關(guān)系

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

第六章：格和布爾代數(shù)⑵證明a,bX，a∧b是集合a,b的最大下界。因?yàn)?a∧b)∧a=a∧b和(a∧b)∧b=a∧b所以a∧b?a且a∧b?b，即a∧b是a,b的下界。下證a∧b是a,b的最大下界。設(shè)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設(shè)a∧b=a，由吸收率可得

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

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

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

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

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

設(shè)X,?是格，∨是X上的并運(yùn)算，∧是X上的交運(yùn)算。則a,bX有⑴a?b當(dāng)且僅當(dāng)a∧b=a⑵a?b當(dāng)且僅當(dāng)a∨b=b證明：⑴設(shè)a?b，下證a∧b=a由a?a且a?b知a是集合a,b的下界，故有a?a∧b；另一方面，由于a∧b是a,b的最大下界，所以是a,b的下界，即a∧b?a。根據(jù)偏序關(guān)系的反對稱性得a∧b=a設(shè)a∧b=a，下證a?ba=a∧b?b，即a?b⑵可類似⑴進(jìn)行證明。第六章：格和布爾代數(shù)【定理6.1.5】設(shè)X,?是格，∨是X上的并運(yùn)算，∧是X上的交運(yùn)算。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】設(shè)X,?是格，∨是X上的并運(yùn)算，∧是X上的交運(yùn)算。則a,b,cX有⑴a∨(b∧c)?(a∨b)∧(a∨c)⑵(a∧b)∨(a∧c)?

a∧(b∨c)

證明：⑴根據(jù)定理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)利用對偶原理，即得⑵。一般地說，格中的∨和∧并不滿足分配律。

第六章：格和布爾代數(shù)【定義6.1.5】

設(shè)X,∨,∧是格，B是X的非空子集，如果B關(guān)于運(yùn)算∨和∧也構(gòu)成格，則稱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)?！径x6.1.6】設(shè)X1,∨1,∧1和X2,∨2,∧2是格，其中∨1,∧1,∨2和∧2都是二元運(yùn)算。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)和格同構(gòu)。稱f(X1),∨2,∧2是X1,∨1,∧1的格同態(tài)像。第六章：格和布爾代數(shù)【定理6.1.7】設(shè)X1,?1和X2,?2是格，X1,∨1,∧1和X2,∨2,∧2是它們導(dǎo)出的代數(shù)系統(tǒng)。f是格X1,∨1,∧1到格X2,∨2,∧2的格同態(tài)，則a,bX1，如果a?1b，必有f(a)?2f(b)證明：設(shè)a?1b，根據(jù)定理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】設(shè)A=a,b,c,d,e，A,?是格，其哈斯圖如圖8.3所示，P(A)是A的冪集合，R=x,y|xP(A)∧yP

(A)∧xy是P(A)上的偏序關(guān)系。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)。第六章：格和布爾代數(shù)證明：a,bA，設(shè)a?b，cf(a)，c?a，由偏序關(guān)系的傳遞性得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)。但是，當(dāng)f是格同構(gòu)時，定理6.1.7的逆成立。

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

證明：設(shè)f是X1,∨1,∧1到X2,∨2,∧2的格同構(gòu)，下證a,bX1，a?1bf(a)?2f(b)由定理6.1.7可知，a,bX1，如果a?1b，必有f(a)?2f(b)設(shè)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)設(shè)a,bX1，a?1bf(a)?2f(b)，下證f是X1,∨1,∧1到X2,∨2,∧2的格同構(gòu)。設(shè)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)。設(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ù)于是d?1a∧1b，即d?1c，故f(d)?2f(c)，再由偏序關(guān)系的反對稱性有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的格同構(gòu)?！径x6.1.7】

設(shè)X1,?1和X2,?2是格，X1,∨1,∧1和X2,∨2,∧2是它們導(dǎo)出的代數(shù)系統(tǒng)。其中∨1,∧1,∨2和∧2都是二元運(yùn)算。a1,b1X1×X2和a2,b2X1×X2，定義X1×X2上的二元運(yùn)算∨3和∧3為：a1,b1∨3a2,b2=a1∨1a2,b1∨2b2a1,b1∧3a2,b2=a1∧1a2,b1∧2b2代數(shù)系統(tǒng)

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

§6.2分配格【定義6.2.1】

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

(A)∧yP

(A)∧xy是P

(A)上的偏序關(guān)系。P

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

證明：前面已經(jīng)證明了格P(A),R導(dǎo)出的代數(shù)系統(tǒng)P

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

(A)

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

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

【例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,?不是分配格。

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

第六章：格和布爾代數(shù)【例6.6】設(shè)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,?不是分配格。本例中的格叫做五角格，五角格也不是分配格。鉆石格和五角格是兩個很重要的格。第六章：格和布爾代數(shù)【定理6.2.1】一個格是分配格的充分必要條件是該格中不含有與鉆石格或五角格同構(gòu)的子格。這個定理的證明已經(jīng)超過了本書的范圍，故略去?！就普?】設(shè)A,?是格，如果|A|＜5，則A,?一定是分配格?！就普?】設(shè)A,?是格，如果A,?是全序集，則A,?一定是分配格?！纠?.7】圖8.6給出了兩個格的哈斯圖。試證明它們都不是分配格。證明：在圖8.6

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

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

第六章：格和布爾代數(shù)第六章：格和布爾代數(shù)【定理6.2.2】

設(shè)X,?是格，X,∨,∧是格X,?導(dǎo)出的代數(shù)系統(tǒng)。X,?是分配格的充分必要條件是a,b,cX，當(dāng)a∧b=a∧c且a∨b=a∨c時，必有b=c證明：設(shè)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(交換律和吸收律) 設(shè)a,b,cX，當(dāng)a∧b=a∧c且a∨b=a∨c時，有b=c，但X,∨,∧不是分配格。由定理6.2.1知X,∨,∧中必含有與鉆石格或五角格同構(gòu)的子格。假設(shè)X,∨,∧含有與鉆石格同構(gòu)的子格，且此子格為S,∨,∧，其中S=u,v,x,y,z，u為它的最大元，v為它的最小元。從而x∨y=u=x∨z，x∧y=v=x∧z，但y≠z，與已知矛盾。第六章：格和布爾代數(shù)對五角格的情況，可類似證明。例如，在圖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。根據(jù)定理6.2.2它們不是分配格。

§6.3有補(bǔ)格

【定義6.3.1】

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

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

(A),∨,∧是P(A),R導(dǎo)出的代數(shù)系統(tǒng)?？占?是格的全下界，而集合A是格的全上界。因而P

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

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

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

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

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

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

證明：因?yàn)閎是a的補(bǔ)元，所以有a∨b=1，a∧b=0設(shè)cX，c是a的另一個補(bǔ)元，同樣也有a∨c=1，a∧c=0從而有a∨b=a∨c，a∧b=a∧c由于X,∨,∧,0,1為分配格，根據(jù)定理6.6.6必有b=c，即a的補(bǔ)元惟一。【定義6.3.4】設(shè)X,∨,∧,0,1為有界格，如果aX，在X中都有a的補(bǔ)元存在，則稱X,∨,∧,0,1為有補(bǔ)格例如，圖8.8是三個有界格的哈斯圖，由于每一個元素至少有一個補(bǔ)元，所以它們都是有補(bǔ)格。

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

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

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

(A),∪,∩是P

(A),R導(dǎo)出的代數(shù)系統(tǒng)，其中∪和∩是集合并運(yùn)算和交運(yùn)算。以后又進(jìn)一步說明了P

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

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

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

第六章：格和布爾代數(shù)

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

設(shè)X,∨,∧,′為布爾代數(shù)，a,bX，必有⑴(a′)′=a⑵(a∨b)′=a′∧b′⑶(a∧b)′=a′∨b′證明：⑴a′是a的補(bǔ)元，a也是a′的補(bǔ)元，由布爾代數(shù)中補(bǔ)元的惟一性有(a′)′=a第六章：格和布爾代數(shù)⑵(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中的⑴稱為雙重否定律，⑵和⑶稱為德摩根律。布爾代數(shù)滿足雙重否定律和德摩根律。第六章：格和布爾代數(shù)【定理6.4.2】

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

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

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

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

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

證明：⑴a,bB，因?yàn)锽X，所以a,bX。又因?yàn)閄,∨,∧,′,0,1是布爾代數(shù)，故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根據(jù)定理6.4.2，B,∨,∧,′,0,1是布爾代數(shù)，它是X,∨,∧,′,0,1的子布爾代數(shù)。為了方便，以下將x?y且x≠y記為x?y。

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

證明：由于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，即運(yùn)算∨和∧在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)(結(jié)合律)第六章：格和布爾代數(shù)=x∨(x′∧b)(a?xa∨x=x)=(x∨x′)∧(x∨b)(分配律)=1∧(x∨b)(x′是x的補(bǔ)元)=x∨b (1是∧的幺元)=b(x?b

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

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

設(shè)X1,∨1,∧1,′,0,1和X2,∨2,∧2,",,E是兩個布爾代數(shù)，其中∨1,∧1,∨2和∧2都是二元運(yùn)算，′和"是一元運(yùn)算，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是布爾代數(shù)X1,∨1,∧1,′,0,1到X2,∨2,∧2,",,E

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

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

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

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

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

第六章：格和布爾代數(shù)由于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】設(shè)X,?是布爾格，0是全下界，a,bX，則a∧b′=0當(dāng)且僅當(dāng)a?b。

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

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

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

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

【引理6.4.3】

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

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

(S),∪,∩,~同構(gòu)。

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

(S)的雙射函數(shù)。設(shè)f(x)=f(y)，令f(x)=f(y)=a1,a2,…,an，由引理6.4.3知x＝a1∨a2∨…∨an＝y(tǒng)。于是f是單射。設(shè)b1,b2,…,bnP(S)，令x=b1∨b2∨…∨bn，由運(yùn)算∨的封閉性得xX且bi?x，i=1,…,n，f(x)=T(x)=b1,b2,…,bn，所以f是滿射。故f是X到P(S)的雙射函數(shù)。第六章：格和布爾代數(shù)⑵證明f是X,∨,∧,′和P(S),∪,∩,~同構(gòu)。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