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

第六章格和布爾代數(shù)2014-2015學(xué)年第二學(xué)期陳磊6.1格的概念對(duì)于偏序集來(lái)說(shuō),它的任一子集不是必定存在最小上界或最大下界的.【例】由右圖所示的偏序集中,

{2,3}的最小上界是6,但沒(méi)有最大下界

{24,36}的最大下界是12,但沒(méi)有最小上界約定把{a,b}的最小上界(最大下界)稱為元素a,b的最小上界(最大下界).有沒(méi)有一種偏序集使得任何兩個(gè)元素都有最小上界和最大下界?定義6-1.1設(shè)A,?是一個(gè)偏序集，如果A中任意兩個(gè)元素都有最小上界和最大下界，則稱A,?是格。【例】1.設(shè)I+表示所有的正整數(shù),定義I+上的二元關(guān)系為整除關(guān)系|,則<I+,|>是一個(gè)偏序關(guān)系.進(jìn)一步,任意兩個(gè)元素的最大下界就是兩個(gè)數(shù)的最大公約數(shù),而最小上界為兩個(gè)數(shù)的最小公倍數(shù),因此<I+,|>是格

2.<P(S),>也是格,任意兩個(gè)元素S1,S2,最大下界為S1∩S2,最小上界為S1∪S2【例】下圖中給出了一些偏序集的哈斯圖，判斷它們是否構(gòu)成格。定義6-1.2設(shè)A,?是一個(gè)格,如果在A上定義兩個(gè)二元運(yùn)算∨和∧,使得對(duì)于任意的a,b∈A,a∨b等于a和b的最小上界,

a∧b等于a和b的最大下界,那么就稱<A,∨,∧>為由格<A,?>所誘導(dǎo)的代數(shù)系統(tǒng),二元運(yùn)算∨和∧稱為并運(yùn)算和交運(yùn)算.【例】S={a,b},P(S)={?,{a},,{a,b}},那么<P(S),>是一個(gè)格由這個(gè)格所誘導(dǎo)的代數(shù)系統(tǒng)為<P(S),∨,∧>,其中∨是集合的并,

∧是集合的交,這兩個(gè)運(yùn)算的運(yùn)算表見(jiàn)下表

∨?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

設(shè)A,?>是一個(gè)格，由A,?>誘導(dǎo)的代數(shù)系統(tǒng)A,∨,∧,設(shè)

BA且B≠?,如果A中兩個(gè)運(yùn)算∨和∧關(guān)于B是封閉的，則稱B,?是A,?的子格。子格一定是格【例】<I+,|>是一個(gè)格,E+是正偶數(shù)的全體,則<E+,|>是<I+,|>的一個(gè)子格注對(duì)于格<A,?>,B是A的非空子集,<B,?>也是一個(gè)偏序集<B,?>不一定是格即使是格,也不一定是<A,?>的子格【例】設(shè)<S,?>是一個(gè)格,其中S={a,b,c,d,e,f,g,h},哈斯圖如下所示S1={a,b,d,f}S2={c,e,g,h}S3={a,b,c,d,e,g,h}<S1,?>,<S2,?>,<S3,?>都是格,其中<S1,?>和<S2,?>是<S,?>的子格,而>,<S3,?>不是<S,?>的子格.設(shè)A,?>是一個(gè)偏序集,在A上定義一個(gè)新的二元關(guān)系?R,使得對(duì)于A中兩個(gè)元素a,b,有關(guān)系a?Rb當(dāng)且僅當(dāng)b?a<A,?R>也是一個(gè)偏序集A,?>和<A,?R>稱為是彼此對(duì)偶的若A,?>是一個(gè)格,則<A,?R>也是一個(gè)格?R一般用?表示設(shè)P是對(duì)任意格都為真的命題,如果在命題P中把?換成?,∨換成∧，∧換成∨,就得到另一個(gè)命題P1,稱P1為P的對(duì)偶命題.同時(shí)P1對(duì)任意格也是真命題定理6-1.1在一個(gè)格A,?>中,對(duì)任意的a,bA,都有

a?a∨b,b?a∨b

a∧b?a,a∧b?b定理6-1.2在一個(gè)格A,?>中,對(duì)于a,b,c,dA,如果a?b和c?d,則

a∨c?b∨d,a∧c?b∧d推論在一個(gè)格A,?>中,對(duì)于a,b,cA,如果b?c,則a∨b

?a∨c,a∧b?a∧c.這個(gè)性質(zhì)稱為格的保序性定理6-1.3設(shè)A,?是一個(gè)格，由格A,?所誘導(dǎo)的代數(shù)系統(tǒng)為A,∨,∧,則對(duì)任意的a,b,c,dA有⑴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(吸收律)引理6-1.1

設(shè)A,∨,∧是一個(gè)代數(shù)系統(tǒng)，其中∨,∧都是二元運(yùn)算且滿足吸收性，則∨和∧滿足冪等性。定理6-1.4設(shè)A,∨,∧是一個(gè)代數(shù)系統(tǒng)，其中∨,∧都是二元運(yùn)算且滿足交換性、結(jié)合性和吸收性，則A上存在偏序關(guān)系?，使A,?是一個(gè)格。定理6-1.5在一個(gè)格A,?中，對(duì)任意的a,b,c∈A,都有

a∨(b∧c)?(a∨b)∧(a∨c)

(a∧b)∨(a∧c)?a∧(b∨c)定理6-1.6設(shè)A,?是一個(gè)格，那么對(duì)于任意的a,b∈A,有

a?ba∧b=aa∨b=b定理6-1.7設(shè)A,?是一個(gè)格，那么對(duì)于任意的a,b,c∈A,有

a?ca∨(b∧c)?(a∨b)∧c推論在一個(gè)格A,?中，對(duì)于任意的a,b,c∈A，必有

(a∧b)∨(a∧c)?a∧(b∨(a∧c))

a∨(b∧(a∨c))?(a∨b)∧(a∨c)定義6-1.4設(shè)A1,?1和A2,?2>是兩個(gè)格，由它們誘導(dǎo)的代數(shù)系統(tǒng)為A1,∨1,∧1和A2,∨2,∧2，如果存在著一個(gè)從A1到A2的映射，使得對(duì)任意的a,bA1,有

f(a∨1b)=f(a)∨2f(b)

f(a∧1b)=f(a)∧2f(b)則稱f是從A1,∨1,∧1到A2,∨2,∧2的格同態(tài)，亦可稱<f(A1),?2>是A1,?1的格同態(tài)象。當(dāng)f是雙射時(shí)，則稱為從A1,∨1,∧1到A2,∨2,∧2的格同構(gòu)，亦稱A1,?1和A2,?2>這兩個(gè)格同構(gòu)定理6-1.8設(shè)f是格A1,?1到A2,?2的格同態(tài)，則對(duì)任意的x,yA1，如果x?1y，必有f(x)?2f(y)定理6-1.8說(shuō)明格同態(tài)是保序的。一般地，定理6-1.8的逆并不成立【例】設(shè)A=a,b,c,d,e，A,?是格，其哈斯圖如下圖所示，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)。

f(b∨d)=f(a)={a,b,c,d,e}

f(b)∪f(wàn)(d)={b,e}∪{d,e}={b,d,e}

f(b∨d)≠f(b)∪f(wàn)(d)定理6-1.9設(shè)A1,?1和A2,?2是兩個(gè)格，f是A1到A2的雙射，則f是A1,?1到A2,?2的格同構(gòu)，當(dāng)且僅當(dāng)對(duì)于任意的a,bA1，a?1bf(a)?2f(b)。作業(yè)(1)(4)(8)

6.2分配格由定理6-1.5可知在一個(gè)格A,?中，對(duì)任意的a,b,c∈A,都有

a∨(b∧c)?(a∨b)∧(a∨c)

(a∧b)∨(a∧c)?a∧(b∨c)當(dāng)上述兩個(gè)式子中的等號(hào)都成立時(shí),即

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

(a∧b)∨(a∧c)=a∧(b∨c)定義一類特殊的格定義6-2.1

設(shè)A,∨,∧是由格A,?所誘導(dǎo)的代數(shù)系統(tǒng)，如果對(duì)任意的a,b,cA滿足

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

(并運(yùn)算對(duì)交運(yùn)算可分配)

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

(交運(yùn)算對(duì)并運(yùn)算可分配)則稱A,?為分配格?！纠吭O(shè)A=a,b,c，P(A)=?,a,b,c,a,b,a,c,b,c,a,b,c是A的冪集合，<P(A),>是一個(gè)格.則它誘導(dǎo)的代數(shù)系統(tǒng)P

(A),∩,∪,

其中∪是集合的并運(yùn)算，∩是集合的交運(yùn)算.

因?yàn)榧系牟?、交運(yùn)算滿足分配律：任意的P,Q,RP

(A),有

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

(A),∩,∪是一個(gè)分配格。【例】A=a,b,c,d,e，A,?是格，其哈斯圖如下左圖所示，證明A,?不是分配格?！纠吭O(shè)A=a,b,c,d,e，A,?是格，其哈斯圖如上右圖所示，證明A,?不是分配格。注:一個(gè)格是分配格的充分必要條件是該格中不含有與鉆石格或五角格同構(gòu)的子格。鉆石格五角格計(jì)算b∧(c∨d)和(b∧c)∨(b∧d)計(jì)算c∧(b∨d)和(c∧b)∨(c∧d)【例】下圖給出了兩個(gè)格的哈斯圖。試證明它們都不是分配格。注:

設(shè)A,?是格，如果|A|＜5，則A,?一定是分配格。定理6-2.1如果在一個(gè)格中交運(yùn)算對(duì)于并運(yùn)算可分配,則并運(yùn)算對(duì)交運(yùn)算一定是可分配的.反之亦然.定理6-2.2每個(gè)鏈?zhǔn)欠峙涓穸ɡ?-2.3

設(shè)A,?是一個(gè)分配格,那么對(duì)于任意的a,b,cA，如果有

a∧b=a∧c和a∨b=a∨c

成立,則必有b=c定義6-2.2設(shè)A,?是一個(gè)格,由它誘導(dǎo)的代數(shù)系統(tǒng)為A,∨,∧,如果對(duì)于任意的a,b,cA,當(dāng)b?a時(shí),有

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

則稱A,?為模格定理6-2.4

格A,?是模格,當(dāng)且僅當(dāng)在A中不含有適合下述條件的元素u,v,w

v

u

且u∨w=v∨w,u∧w=v∧w

在一般格中,對(duì)于任意的a,b,c,有以下三個(gè)式子成立

a∨(b∧c)?(a∨b)∧(a∨c)

(a∧b)∨(a∧c)?a∧(b∨c)

(a∧b)∨(b∧c)∨(c∧a)?(a∨b)∧(b∨c)∧(c∨a)定理6-2.5對(duì)于模格,若有三個(gè)元素a,b,c,使得上述三個(gè)式子中任何一個(gè)式子中把“?”換成“=”成立,則另外兩個(gè)式子把“?”換成“=”也必成立.定理6-2.6分配格必定是模格.作業(yè)(2)(5)

6.3有補(bǔ)格定義6-3.1

設(shè)A,?是一個(gè)格，如果存在元素aA，對(duì)于任意的xA,

都有

a?x則稱a為格A,?的全下界，記格的全下界為0。定理6-3.1

一個(gè)格A,?，若有全下界，則是惟一的。定義6-3.2

設(shè)A,?是一個(gè)格，如果存在元素bA，對(duì)于任意的xA,

都有

x?b則稱b為格A,?的全上界，記格的全上界為1。定理6-3.2

一個(gè)格A,?，若有全上界，則是惟一的。【例】1.在格<P(A),>中,空集?是全下界,而A是全上界

2.如下圖所示的格中,

e是全下界,而a是全上界定義6-3.3如果一個(gè)格中存在全下界和全上界,則稱該格為有界格定理6-3.3

設(shè)A,?為一個(gè)有界格，則對(duì)任意的aA,必有a∨1=1,a∧1=aa∨0=a,a∧0=0設(shè)A,∨,∧是由有界格A,?所誘導(dǎo)的代數(shù)系統(tǒng)

，aA有a∧0=0，因?yàn)楦駶M足交換律，所以0∧a=0，這說(shuō)明0是交運(yùn)算的零元；同樣的道理，0是并運(yùn)算的幺元，而1是交運(yùn)算的幺元和并運(yùn)算的零元定義6-3.4設(shè)A,?是一個(gè)有界格，對(duì)于A中的一個(gè)元素a，如果存在bA，使得a∨b=1且a∧b=0，則稱b是a的補(bǔ)元。如果b是a的補(bǔ)元，從上述定義可以看出，a也是b的補(bǔ)元。因此，可以說(shuō)a和b是互補(bǔ)的，或者說(shuō)a和b互為補(bǔ)元。【例】如下圖所示的格中,

b和c互為補(bǔ)元，b和d也互為補(bǔ)元，b有兩個(gè)補(bǔ)元c和d。注:格中元素的補(bǔ)元并不惟一,也可能不存在【例】下圖是一個(gè)有界格的哈斯圖。找出a,b,c,d,e的補(bǔ)元。

a的補(bǔ)元:

ec的補(bǔ)元:

dd的補(bǔ)元:

c,ee的補(bǔ)元:

a,db沒(méi)有補(bǔ)元注:在有界格中，全上界1的惟一補(bǔ)元是全下界0，而全下界0的惟一補(bǔ)元是全上界1。定義6-3.5

在一個(gè)有界格中，如果每個(gè)元素都至少有一個(gè)補(bǔ)元,

則稱此格為有補(bǔ)格【例】如下圖所示三個(gè)格均為有補(bǔ)格定理6-3.4

在有界分配格中,若有一個(gè)元素有補(bǔ)元,則必是唯一的定義6-3.6

一個(gè)格如果它既是有補(bǔ)格又是分配格,則稱為有補(bǔ)分配格.并記格中任一元素a的唯一補(bǔ)元為ā作業(yè)(1)(4)(6)

6.4布爾代數(shù)定義6-4.1

有補(bǔ)分配格稱為布爾格。在布爾格中每一個(gè)元素a都有補(bǔ)元,并且是唯一的,這唯一的補(bǔ)元記為ā

對(duì)于一個(gè)有補(bǔ)分配格,計(jì)算一個(gè)元素的補(bǔ)元可以確定一個(gè)一元運(yùn)算,記為“-”,稱為補(bǔ)運(yùn)算定義6-4.2

由布爾格A,?，可以誘導(dǎo)一個(gè)代數(shù)系統(tǒng)A,∨,∧,-,這個(gè)代數(shù)系統(tǒng)稱為布爾代數(shù)?！纠縎是一個(gè)非空有限集合,

P

(S),

是一個(gè)格,P

(S),∪,∩是由P

(S),導(dǎo)出的代數(shù)系統(tǒng).集合的并(交)對(duì)于交(并)是可分配的,而且其全上界為S,全下界為?.因此P(S),∪,∩是有界分配格.對(duì)任意TP

(S)，都有一個(gè)補(bǔ)元S–T.P(S),∪,∩,~是一個(gè)布爾代數(shù).定理6-4.1對(duì)于布爾代數(shù)中任意兩個(gè)元素a,b,必定有定義6-4.3具有有限個(gè)元素的布爾代數(shù)稱為有限布爾代數(shù)定義6-4.4設(shè)A,∨,∧,-和B,∨,∧,-是兩個(gè)布爾代數(shù),如果存在著A到B的雙射f,對(duì)于任意的a,b∈A,都有

f(a∨b)=f(a)∨f(b)

f(a∧b)=f(a)∧f(b)則稱A,∨,∧,-和B,∨,∧,-同構(gòu)接下來(lái)用同構(gòu)的觀點(diǎn)來(lái)討論有限布爾代數(shù)的結(jié)構(gòu)定義6-4.5設(shè)A,?是一個(gè)格，具有全下界0，如果有元素a蓋住0，則稱元素a為原子。【例】如下圖所示是三個(gè)格的哈斯圖,試找出每個(gè)格的原子注:若a,b是原子,且a≠b,則a∧b=0定理6-4.2

設(shè)A,?是一個(gè)具有全下界0的有限格，則對(duì)于任何一個(gè)非零元素b(即b≠0)，至少存在一個(gè)原子a，使得a?b。注:上述定理中的原子a不一定惟一引理6-4.1

在一個(gè)布爾格中,當(dāng)且僅當(dāng)b?c。引理6-4.2設(shè)A,∨,∧,-是一個(gè)有限布爾代數(shù)，若b是A中任意非零元素,

a1,a2,…,ak是A中滿足aj?b的所有原子，則b=a1∨a2∨…∨ak引理6-4.3

設(shè)A,∨,∧,-是一個(gè)有限布爾代數(shù),

bA且b≠0，a1,a2,…,ak是滿足ai?b(i=1,…,k)的A中的所有原子,則b=a1∨a2∨…∨ak是將b表示為原子的并的惟一形式。引理6-4.4在一個(gè)布爾代數(shù)A,?中,對(duì)A中任意一個(gè)原子a和另一個(gè)非零元素b,

a?b和a?兩式中有且僅有一式成立.定理6-4.3(Stone表示定理)設(shè)A,∨,∧,-是由有限布爾格A,?所誘導(dǎo)的一個(gè)有限布爾代數(shù)，S是布爾格A,?中所有原子的集合，則A,∨,∧,-和P

(S),∪,∩,~同構(gòu)。推論6-4.1

有限布爾格的元素個(gè)數(shù)必定等于2n，其中n是該布爾格中所有原子的個(gè)數(shù)。推論6-4.2

任何一個(gè)具有2n個(gè)元素的有限布爾代數(shù)都是同構(gòu)的.定理6-4.3(Stone表示定理)設(shè)A,∨,∧,-是由有限布爾格A,?所誘導(dǎo)的一個(gè)有限布爾代數(shù)，S是布爾格A,?中所有原子的集合，則A,∨,∧,-和P

(S),∪,∩,~同構(gòu)。推論6-4.1

有限布爾格的元素個(gè)數(shù)必定等于2n，其中n是該布爾格中所有原子的個(gè)數(shù)。推論6-4.2

任何一個(gè)具有2n個(gè)元素的有限布爾代數(shù)都是同構(gòu)的.作業(yè)(2)(3)(6)

6.5布爾表達(dá)式設(shè)A,∨,∧,-是一個(gè)布爾代數(shù),考慮一個(gè)從An到A的函數(shù)【例】1.

A={0,1},下表給出了一個(gè)從A3到A的一個(gè)函數(shù)2.B={0,1,2,3},下表給出了一個(gè)從B2到B的一個(gè)函數(shù)<0,0,0>0<0,0,1>0<0,1,0>1<0,1,1>0<1,0,0>1<1,0,1>1<1,1,0>0<1,1,1>1<0,0>1<2,0>2<0,1>0<2,1>0<0,2>0<2,2>1<0,3>3<2,3>1<1,0>1<3,0>3<1,1>1<3,1>0<1,2>0<3,2>2<1,3>3<3,3>2定義6-5.1設(shè)A,∨,∧,-是一個(gè)布爾代數(shù),并在這個(gè)布爾代數(shù)上定義布爾表達(dá)式如下:

(1)A中任何元素是一個(gè)布爾表達(dá)式

(2)任何變?cè)且粋€(gè)布爾表達(dá)式

(3)如果e1和e2是布爾表達(dá)式,那么,(e1∨e2)和

(e1∧e2)也是布爾表達(dá)式

(4)只有通過(guò)有限次運(yùn)用規(guī)則(2)和(3)所構(gòu)造的符號(hào)串是布爾表達(dá)式【例】{0,1,2,3},∨,∧,-是一個(gè)布爾代數(shù),下列三個(gè)符號(hào)串都是布爾表達(dá)式

0∧x1,,定義6-5.2一個(gè)含有n個(gè)變?cè)牟紶柋磉_(dá)式,稱為含有n元的布爾表達(dá)式.記為E(x1,x2,…,xn),其中x1,x2,…,xn為變?cè)x6-5.3布爾代數(shù)A,∨,∧,-上的一個(gè)含有n元的布爾表達(dá)式E(x1,x2,…,xn)的值是指:將A中元素作為變?cè)獂i的值來(lái)代替表達(dá)式中相應(yīng)的變?cè)?即對(duì)變?cè)x值),從而計(jì)算出表達(dá)式的值.【例】設(shè)布爾代數(shù){0,1},∨,∧,-上的布爾表達(dá)式為:

定義6-5.4

設(shè)布爾代數(shù)A,∨,∧,-上兩個(gè)n元的布爾代數(shù)為E1(x1,x2,…,xn)和E2(x1,x2,…,xn),如果對(duì)于n個(gè)變?cè)娜我赓x值,時(shí),均有則稱這兩個(gè)布爾表達(dá)式是等價(jià)的.【例】在布爾代數(shù)<{0,1},

∨,∧,->上定義:

一個(gè)n元布爾表達(dá)式確定一個(gè)從An到A的函數(shù)?！纠緼={0,1},右表給出了一個(gè)從A3到A的一個(gè)函數(shù)

<0,0,0>0<0,0,1>0<0,1,0>1<0,1,1>0<1,0,0>1<1,0,1>1<1,1,0>0<1,1,1>1定義6-5.5設(shè)<A,∨,∧,->為布爾代數(shù),一個(gè)從An到A的函數(shù)，如果它能夠用<A,∨,∧,->上的n元布爾表達(dá)式表示，那么，這個(gè)函數(shù)就稱為布爾函數(shù)。定理6-5.1對(duì)于兩個(gè)元素的布爾代數(shù)<{0,1},∨,∧,->,任何一個(gè)從{0,1}n到{0,1}的函數(shù),都是布爾函數(shù).布爾小項(xiàng)形如,其中是xi或中的任一個(gè)