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

《離散數(shù)學(xué)》教案計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院課程學(xué)時(shí)：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的任意兩個(gè)元素都有最小上界和最大下界，故偏序集S12,R是格。

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

解：它們都不是格。在(a)中，1,2沒有下界，因而沒有最大下界。在(b)中，2,4雖有兩個(gè)上界，但沒有最小上界。在(c)中，1,3沒有下界，因而沒有最大下界。在(d)中，2,3雖有三個(gè)上界，但沒有最小上界。第六章：格和布爾代數(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ù)。同樣，這個(gè)結(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是含有格中元素以及符號(hào)=,?,?,∨和∧的命題。將f中的?替換成?，?替換成?，∨替換成∧，∧替換成∨，得到一個(gè)新命題，所得的命題叫做f的對(duì)偶命題，記為f*。例如，在格中，f為a∧(b∨c)?a，則f的對(duì)偶命題f*為a∨(b∧c)?a命題f和它的對(duì)偶命題f*遵循下列的規(guī)則，這規(guī)則叫做格的對(duì)偶原理。設(shè)f是含有格中元素以及符號(hào)=,?,?,∨和∧的命題。若f對(duì)一切格為真，則f的對(duì)偶命題f*也對(duì)一切格為真。格的許多性質(zhì)都是互為對(duì)偶命題的。有了格的對(duì)偶原理，在證明格的性質(zhì)時(shí)，只需證明其中的一個(gè)就可以了。

第六章：格和布爾代數(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)系的反對(duì)稱性有(a∧b)∧c=a∧(b∧c)由對(duì)偶原理得(a∨b)∨c=a∨(b∨c)⑶顯然a?a∨a，又由?的自反性得a?a，從而推出a∨a?a，根據(jù)偏序關(guān)系的反對(duì)稱性有a∨a=a由對(duì)偶原理得a∧a=a⑷顯然a?a∨(a∧b)，又由a?a，a∧b?a得a∨(a∧b)?a，從而得a∨(a∧b)=a。由對(duì)偶原理得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)成一個(gè)格。

證明：定義X上的一個(gè)二元關(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。所以?是反對(duì)稱的。設(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)系?可以等價(jià)的定義為：

?=a,b|a,bX且a∨b=b，用這個(gè)定義和類似于⑵的方法可以證明a∨b是集合a,b的最小上界。因此，X,?構(gòu)成一個(gè)格。根據(jù)定理6.1.3，可以給出格的另一個(gè)等價(jià)定義。【定義6.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)系的反對(duì)稱性得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)利用對(duì)偶原理，即得⑵。一般地說，格中的∨和∧并不滿足分配律。

第六章：格和布爾代數(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的一個(gè)映射，對(duì)任意的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的逆并不成立?！纠?.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是保序的。對(duì)于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)時(shí)，定理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)系的反對(duì)稱性有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)。【定義6.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)算對(duì)交運(yùn)算可分配)a∧(b∨c)=(a∧b)∨(a∧c)(交運(yùn)算對(duì)并運(yùn)算可分配)則稱X,∨,∧為分配格。因?yàn)閍∨(b∧c)=(a∨b)∧(a∨c)和a∧(b∨c)=(a∧b)∨(a∧c)互為對(duì)偶命題，根據(jù)對(duì)偶原理，定義6.2.1還可以改寫為：一個(gè)格如果交運(yùn)算對(duì)并運(yùn)算可分配或并運(yùn)算對(duì)交運(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,?不是分配格。本例中的格叫做五角格，五角格也不是分配格。鉆石格和五角格是兩個(gè)很重要的格。第六章：格和布爾代數(shù)【定理6.2.1】一個(gè)格是分配格的充分必要條件是該格中不含有與鉆石格或五角格同構(gòu)的子格。這個(gè)定理的證明已經(jīng)超過了本書的范圍，故略去?！就普?】設(shè)A,?是格，如果|A|＜5，則A,?一定是分配格?！就普?】設(shè)A,?是格，如果A,?是全序集，則A,?一定是分配格。【例6.7】圖8.6給出了兩個(gè)格的哈斯圖。試證明它們都不是分配格。證明：在圖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時(shí)，必有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時(shí)，有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ù)對(duì)五角格的情況，可類似證明。例如，在圖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)。【定理6.3.1】設(shè)X,?是格，若格X,?有全下界或全上界，則它們一定是惟一的。

證明：用反證法。如果有兩個(gè)全下界a和b，a,bX。因?yàn)閍是全下界，所以a?b；又因?yàn)閎是全下界，所以b?a。再由?的反對(duì)稱性有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，由?的反對(duì)稱性有a∧0=0顯然a?a，由于1是全上界，所以有a?1，從而推出a?a∧1，又因?yàn)閍∧1?a，再由?的反對(duì)稱性有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為有界格，如果對(duì)于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有兩個(gè)補(bǔ)元c和d。所以格中元素的補(bǔ)元并不惟一。第六章：格和布爾代數(shù)【例6.8】圖8.7是一個(gè)有界格的哈斯圖。找出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ǔ)元。如果某個(gè)元素的補(bǔ)元存在，補(bǔ)元可能有一個(gè)，也可能有多個(gè)。但在有界分配格中，如果元素的補(bǔ)元存在，則一定惟一。

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

證明：因?yàn)閎是a的補(bǔ)元，所以有a∨b=1，a∧b=0設(shè)cX，c是a的另一個(gè)補(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ǔ)元惟一?！径x6.3.4】設(shè)X,∨,∧,0,1為有界格，如果aX，在X中都有a的補(bǔ)元存在，則稱X,∨,∧,0,1為有補(bǔ)格例如，圖8.8是三個(gè)有界格的哈斯圖，由于每一個(gè)元素至少有一個(gè)補(bǔ)元，所以它們都是有補(bǔ)格。

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

有補(bǔ)分配格稱為布爾格。在布爾格中每一個(gè)元素都有補(bǔ)元。因?yàn)橛醒a(bǔ)格一定是有界格，所以布爾格一定是有界分配格，根據(jù)定理6.3.3，布爾格中的每一個(gè)元素的補(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為任意集合時(shí)，P(A),∪,∩,~也是布爾代數(shù)。稱為集合代數(shù)。集合代數(shù)是布爾代數(shù)的一個(gè)具體模型。布爾代數(shù)一定是格。根據(jù)定理8.1.1，布爾代數(shù)中的兩個(gè)二元運(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上封閉且滿足交換律。⑵*和°滿足分配律(滿足*對(duì)°的分配律和°對(duì)*的分配律)。⑶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給出的四個(gè)條件可以作為布爾代數(shù)的等價(jià)定義。布爾代數(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ù)的又一個(gè)模型?！径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是兩個(gè)布爾代數(shù)，其中∨1,∧1,∨2和∧2都是二元運(yùn)算，′和"是一元運(yùn)算，0和1是X1的全下界和全上界，,E是X2的全下界和全上界。f是從X1到X2的一個(gè)映射，對(duì)任意的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)，簡(jiǎn)稱布爾代數(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是三個(gè)格的哈斯圖，在(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，至少存在一個(gè)原子a，使得a?b。

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

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

0?bi?…?b2?b1?b由?的傳遞性，bi?b定理6.4.5中的原子a不一定惟一，圖8.10的(c)是有限格，元素c有惟一的原子b，使得b?c。圖8.10的(b)也是有限格，元素d卻有三個(gè)原子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′。由?的反對(duì)稱性知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，至少存在一個(gè)原子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中的一個(gè)，因此第六章：格和布爾代數(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由?的反對(duì)稱性知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時(shí)，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，對(duì)于任意的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