格與布爾代數格的定義格是任二元都(在其中)有glb

和lub

的偏序集,具體說:偏序集

S,

稱為格,如果

ab(a,bSglb{a,b}S∧lub{a,b}S).我們知道:glb

或lub

若存在必唯一,故對于格

S

,glb:SSS,lub:SSS

都是映射,從而定義格

S

中的兩個二元運算,我們分別把它們記為a*b=

glb{a,b}

和

a

b=

lub{a,b},并分別稱為的

a

與

b

保交與保聯.a,b可比較

a*b,ab都存在格的舉例對有限偏序集常用它的Hasse圖驗證它是否組成一個格,例如教本p215的圖7.1-1(a)—(e)是格,7.1-2(a)—(c)不是格.例①

集S的冪集(S)和包含關系組成偏序集,對任意A,B(S),glb{A,B}=A∩B(S);

lub{A,B}=A∪B(S).因此,(S),

是格.例如

({a,b,c}),

的Hasse圖如圖7.1-1(c)所示.abcababcbcac

abcd例②

每個線性序集,例如

R,

及其子集,都是格,

glb{a,b}=

min{a,b};lub{a,b}=max{a,b}.例③

正整數集I+與整除關系組成偏序集

I+,|是格,對任意

a,bI+,a*b=glb{a,b}=GCD(a,b)I+;a

b=lub{a,b}=LCM(a,b)I+.

因此,I+,|是格.

特別,對任意正整數

nI+,令

Sn

記

n

的所有正因子的集,則

Sn,|

是格.§7.1#3畫出格S72,|的Hasse圖72=2332;x=2i3j,i=0,1,2,3;j=0,1,2.glb{2i3j,2k3m}=2min{i,k}3min{j,m};lub{2i3j,2k3m}=2max{i,k}3max{j,m}

S72={72,36,24,18,12,9,8,6,4,3,2,1}91836722481243612§7.1#2S={1,2,3,4,5},S,是格嗎?解

S,

是格,a

b=min(a,b);ab=max(a,b).一般地,任何線性序集都是格.15432格的對偶原理因偏序

的逆關系

也是偏序;故B=S,

是格

B=

S,

是格;

原因是:對任意AB,lub(A)=glb(A),glb(A)=lub(A);(

記格B中的對應運算)特別對任意

a,bS,a*b=ab,ab=a*b.對偶原理:對于格

S,

中任何有效命題,把

與

;

*

與

互換后仍為有效命題.格的基本公式及其證明⑹交換律:a*b=b*a;ab=ba.(其中a,bS為任意元素,下同)證:此二式互為對偶,由對偶原理,只須證其中一個.第一式證明如下:a*b

=

glb{a,b}=

glb{b,a}=

b*a.⑺結合律:(a*b)*c

=

a*(b*c);(ab)c=(ab)c.證:w

(a*b)*c

a*b

和

c

w

a,b

和

c

w

a

和

b*c

w

a*(b*c),即(a*b)*c

a*(b*c).同理可得a*(b*c)(a*b)*c.得證二者相等.⑻等冪律:a*a=a;aa=a.證:aa

aa*a(用⑸).又按*定義有a*aa.所以a*a=a.⑼吸收律:a*(ab)=a;a(a*b)=a.證:aa∧aab

aa*(ab);此外a*(ab)a,故

a*(ab)=a.⑽重要公式:a*b=a

ab

ab=b.證:因ab

a*b=a(1)的對偶為:ab

ab=a,故只須證(1)即可.事實上ab

aa*b.又a*ba,得證a*b=a.另一方面,a*b=a

ab,故(1)成立.(注:用冪集格的解釋易記住此公式)⑾ad∧bc

a*bd*c.(其對偶式為ad∧bc

abdc)

因a*bad,a*bbc,故a*bd*c.⑿保序性:bc

a*ba*c∧abac.因恒有aa,故當bc時令d=a結論由⑾推出.⒀

分配不等式:a

(b*c)

(ab)*(ac)(其對偶式?)因b*cb;b*cc,故由保序性⑿推出:a(b*c)ab和a(b*c)ac,進而由⑸推出分配不等式⒀.§7.1#8元素不多于3個的格全是鏈證設S,是格.

若|S|=1,它顯然是鏈(全序集);

若|S|=2,不妨設|S|={a,b}且a*b=a,即ab,則S為二元鏈;

若|S|=3,不妨設|S|={a,b,c}.今用反證法證S中任二元a,b都可比較.設a,b不可比較,則glb{a,b},lub{a,b}{a,b},由此得glb{a,b}=c=lub{a,b}.進一步又有ca∧ca

c=a,

產生矛盾.§7.1作業布置#1;#5;#6提示:反復利用下列公式:

a*b=a

ab

ab=b.格的另一個等價定義有兩個二元運算的代數

L,*,

稱為一個格,如果*,都滿足交換律,結合律和等冪律并且滿足吸收律:對L中任意元素a,b,c(交換)a*b=b*a;ab=ba;(結合)(a*b)*c=a*(b*c);(ab)c=a(bc);(等冪)a*a=a;aa=a;(吸收)a*(ab)=a=a(a*b);注:等冪律可由吸收律推出(aa=a(a*(ab))=a),故等冪律可從上述定義中刪去.格的兩個定義等價證由格S的前一個定義可定義S的兩個二元運算:*,,并已證明*,都滿足交換律,結合律,等冪律和吸收律(見表7.1-1),故它蘊涵格的后一個定義.反之,由格

L

的后一定義可證明

L

是任二元的lub,glb

都在

L

中的偏序集,從而滿足格的前一定義.事實上,在

L

中定義關系

:ab

a*b=a(或ab=b),則等冪律:a*a=a

保證自反律

aa.下證反對稱律.ab∧ba

a*b=a∧b*a=b

(交換律)a=b;最后證傳遞律:ab∧bc

a*b=a∧b*c=b

a*c=(a*b)*c=a*(b*c)=a*b=a,即

ac.∴

L,

是偏序集.下證任二元有glu和lub.對任意a,bL,設c是a,b的下界,則c*a=c∧c*b=c

c*a*b=c*b=c,即ca*b;又a*b*b=a*b

a*b

b,類似有

a*b

a.

glu{a,b}=a*bL.同理可證lub{a,b}=

abL.(注

a*b=a

ab=(a*b)b=b

吸收律)子格與格的直接積

作為代數的格

L,*,的子代數稱為子格.

若H

L,且H對

*,

封閉,則交換律,結合律,吸收律在L中成立必在H中成立,從而

H,*,

也是格.

設L,L

是格,則積代數:L

L,*,,其中a,b*c,d=a*c,b*d;

a,bc,d=ac,bd,也是格,稱為格L

與L

的直接積.(L

L

對*,封閉由L,L

對*,封閉推出;交換律,結合律,吸收律在L,L

中成立推出在L中也成立.)(看221頁例2(a))求下圖表示的格

S,的所有真子格

S,

的2元子格(只寫載體):{e,d},{e,c},{e,b},{e,a},{b,a},{c,a},{d,a};線段

S的3元子格:{e,d,a},{e,c,a},{e,b,a};

3點路徑

S的4元子格:{e,d,c,a},{e,d,b,a},{e,c,b,a}.

四邊形abcde§7.2#3格的封閉區間[a,b]是子格

格

L,

的封閉區間[a,b]定義為由a,b界定的線性序子集:[a,b]={x|xL∧axb},其中

a,bL.

[a,b]是L的子格證:

[a,b]顯然是

L

的子集;x,y[a,b]axb∧ayb即a(b)為{x,y}的下(上)界

ax*yxyb即x*y,xy[a,b]

[a,b]對*,封閉,從而是L的一個子格.格的同態

作為代數的格

L,*,的代數同態稱為格同態,具體講,f:L,*,L,*,稱為格同態,如果對任何a,bL,有

f(a*b)=f(a)*f(b),f(ab)=f(a)f(b).

格的同態象是陪域格L的子格(定理6.3-2)(習題7.2#6只須證封閉性)

格同態的保序性定理7.2-2:格同態f:L,*,;L,*,,是保序的,即對任何

a,bL

都有

a

bf(a)

f(b).(*)證:aba*b=a

f(a)=f(a*b)=f(a)*f(b)

f(a)f(b).(注:可以用此性質—公式(*),給出作為偏序集的格的同態定義.)格的同構

雙射的格同態稱為格同構.

任意格同構的定義域格與陪域格的Hasse圖除標記外完全相同.

在習題§7.1#8中證明了:(不計同構差別)元素不多于3個的格全是鏈

(p220例1(b))不計同構差別只有2個4元格,如圖7.2-4所示;不計同構差別只有5個5元格,如圖7.2-5所示.(利用性質:任何有限格必有最大元和最小元及一些顯然的分析)沒有四元鏈子格沒有四邊形子格鏈§7.2作業布置#2提示:說明滿足格的條件但不滿足子格的條件#4提示:畫出hasse圖,分析此圖的所有能組成子格的部分.它自己為6元子格;每個點都組成1元子格;有整除關系的任意兩個點組成2元子格;3元子格是圖中長為2的線段;4元子格是圖中長為3的線段或四邊形;5元子格只能是四邊形連一線段.分配格的定義

其兩個運算滿足分配律的格稱為分配格,具體講,格

L,*,稱為分配格,如果對任何

a,b,cL

有

a*(bc)=(a*b)(a*c),(1)和a(b*c)=(ab)*(ac).

(2)

由格的對偶原理,(1)成立當且僅當(2)成立,故

L,*,為分配格當且僅當(1)和(2)之一成立即可.

(§7.3#1)用吸收律證(1)(2).(ab)*(ac)=((ab)*a)((ab)*c)用(1)=a((a*c)(b*c))用吸收律和(1)=a(b*c)用結合律和吸收律分配格舉例①集S的冪集格

(S),∪,∩,

是分配格證:由集合論知(定理2.2-2):A∩(B∪C)=(A∩B)∪(A∩C).②鏈(線性序集)是分配格.例如,I,min,max,

(§7.3#5)是分配格.證:設a,b,c為鏈

S,

的任意3元.若a=glb{a,b,c},則a*(bc)=a=aa=(a*b)(a*c);若a=lub{a,b,c},則a*(bc)=bc=(a*b)(a*c);若bac,則a*(bc)=a*c=a=ba=(a*b)(a*c).對任意正整數n

Sn,GCD,LCM

是分配格

證:對任意x,ySn,由

I,min,max,

是分配格知min(ai,max(bi,ci))=max(min(ai,bi),min(ai,ci))由此立即推出分配律:GCD(x,LCM(y,z))=

LCM(GCD(x,y),GCD(x,z)).所以,格

Sn,GCD,LCM

是分配格.非分配格的舉例a*(bc)=a*1=a,b*(ac)=b*1=b(a*b)(a*c)=00=0,(b*a)(b*c)=0c=c注①可以證明:格L是分配格當且僅當L沒有同構于例1或例2的子格.②此兩例都不滿足雙消去律:a*b=a*c∧ab=acb=c.1bc01ab0ca例1例2分配格的充要條件定理:格

L,*,是分配格當且僅當在L中成立雙消去律:a*b=a*c∧ab=ac

b=c.證:由已知條件,分配律,交換律及吸收律立即推出必要性:c=c*(ac)=c*(ab)=(c*a)(c*b)=(b*a)(c*b)=(ac)*b=(ab)*b=b.充分性(7.3#2)(由逆反律)等價于:若L不是分配格,則在L中雙消去律不成立.但這一結論可由上面關于非分配格的注①和②推出(在L中有同構于例1或例2的子格,它們都不滿足雙消去律).格的全下界與全上界的概念格

L,(視為偏序集)的元素

a

稱為L的全下(上)界,如果

b(bLab)(b(bLba))

格的全下(上)界至多有一個,并記為

0(1).若有兩個:u,v,則uv∧vu,進而推出u=v.由定義得:對任意bL有

b*0=0,b0=b;b*1=b,b1=1.例①對任何有限格

L={a1,…,an}有0=a1**an,

1=a1an(L

a1**an=

ai*b

ai).②I,

全下界,全上界皆無,N,

有全下界0

而無全上界;[0,1],有全下,全上界有界格與有補格定義:同時有全下界0和全上界1的格稱為有界格;有界格

L,*,,0,1

的元素a的補元是滿足

a*b=0∧ab=1的元素

bL;每元都有補元的有界格稱為有補格.例:冪集格

(S),∪,∩,,,S及圖7.3-4c中的格.注①

0和1互為補元,且是唯一的(定理7.3-7)②a{0,1}的補元一般不唯一(p225例4b).③分配格中任何元

a

的補元唯一(定理7.3-8)證:設b,c為a的補元,即a*b=0=a*c∧ab=1=ac,則因分配格中雙消去律成立,故由上式導出b=c.有補分配格的性質①定義:有補分配格中每元的補元唯一,從而可定義一個“取補”的一元運算.因此,此種格是一個有兩個二元運算,一個一元運算和常數0,1的代數

L,*,,,0,1,稱為布爾代數.(例如,冪集格

(S),∪,∩,,,S是布爾代數.)②對有補分配格的任一元

a,(a)=a.證:根據是:a*a=0=a*a,aa=1=aa中a,a的地位對稱和補元唯一.③(a*b)=ab,(ab)=a*b(摩根律).證:(a*b)*(ab)=(a*b*a)(a*b*b)=00=0;(a*b)

(ab)=(aab)*(bab)=1*1=1.④(§7.3#11)有界分配格

L

的所有補元的集

S

構成

L

的一個有補分配子格.證:對

S

中任二元

a,b,有

a,bS(用②);由③

a*b

有補元

ab,ab

有補元

a*b,由此推出

a*b,abS;又

0,1S,所以S對三個運算及兩個常數封閉.⑤ab

a*b=0

ab=1.證:只證前部分(后部分由摩根律推出).ab

a*b=a

a*b=a*b*b=a*0=0;a*b=0

b(a*b)(=b0)=b

(ba)*(bb)=b分配律

ba=b

ab.bb=1

布爾代數的兩個等價定義定義1:布爾代數是有補分配格.定義2(公理化定義):有兩個二元運算的代數B,*,

稱為布爾代數,如果對任意元素a,b,cB,成立

①(交換律)a*b=b*a,ab=ba;

②(分配律)a*(bc)=(a*b)(a*c),a(b*c)=(ab)*(ac);③(有界律)存在0,1B,使得a*1=a,a0=a,aB;④(有補律)B的每一元a都有(唯一)aS,使得a*a=0,aa=1.注:布爾代數的兩個定義是等價的(證明略).布爾代數舉例(只須驗證4條公理)①冪集代數:(S),∪,∩,,,S;②命題代數:B,∨,∧,?,F,T;注:在B中把互相邏輯等價命題視為相等.命題代數B中的偏序關系是邏輯蘊涵關系:,因為:A∧B=A

?A∨B=(?A∨?B)∨B=?A∨T=T

AB.③n元開關代數:(∧,∨為布爾乘,布爾加運算)Bn,*,,?,0,1,其中B={x1,…,xn|x1,…,xn{0,1}},0=0,…,0,1=1,…,1,?x1,…,xn=?x1,…,?xn,x1,…,xn*y1,…,yn=x1∧y1,…,xn∧yn,x1,…,xny1,…,yn=x1∨y1,…,xn∨yn.布爾同態與布爾同構二布爾代數之間的映射f:B,*,,,0,1B,*,,?,0,1稱為布爾同態,如果對任意a,bB,有f(a*b)=f(a)*f(b);f(ab)=f(a)f(b);f(a)=?f(a);f(0)=0,f(1)=1.若f為雙射,則稱f為布爾同構.若用Bn的元素表示n元集S冪集

(S)的元素,則可用X∧Y表示X∩Y;X∨Y表示X∪Y;?X表示補集X和用0,1分別表示,S.由此不難看出:

n元集的冪集代數與n元開關代數布爾同構.類似地,利用n元命題的主合,析取范式及其合,析取運算與否定運算也能證明n元命題代數與n元開關代數布爾同構.布爾代數的一個基本定理

定理:任何布爾代數都同構于一個冪集代數(要建立一整套布爾原子理論進行證明,從略).

推論:有限布爾代數都同構于某個開關代數,從而有限布爾代數的元素個數是2的整數冪.

應用舉例:格

S12,GCD.LCM是布爾代數嗎?解:S12={1,2,3,4,6,12}的元素個數6不是2的整數冪,故不是布爾代數.不難看出2沒有補元,因為2x=LCM(2,x)=12當且僅當x=12,而12的補元是1而不是2.布爾代數的子代數與積代數

布爾代數B,*,,,0,1的子集S稱為B的子布爾代數,如果S對運算*,,封閉和0,1S.布爾代數B1,*1,1,,01,11,B2,*2,2,?,02,12

的積代數是B1B2,*,,,0,1,其中a,c=a,?c;a,c*b,d=a*1b,c*2d;a,cb,d=a1b,c2d;0=01,02;1=11,12

子布爾代數與積布爾代數本身都是布爾代數.每個布爾代數B,*,,,0,1都有兩個平凡的子布爾代數:自身和{0,1}.(封閉性:0*0=0*1=0;1*1=1;01=11=1;00=0;0=1;1=0.)§7.3--7.4作業布置§7.3習題#6(改為)是有補格嗎?為什麼?(思考:由此二例你能得出怎樣的一般結論?)#8(提示:01)#10.§7.4習題#1(a),*(e)#2(e)#3(提示:利用摩根律,全下,上界的性質及補元性質)布爾表達式與布爾函數

設B,*,,,0,1為布爾代數.取值于B中元素的變元稱為布爾變元;B中元素(包括0,1)稱為布爾常元.

由布爾變元,布爾常元經有限次*,,運算形成的式子稱為B上布爾表達式.

例:對布爾代數B={a,b,0,1},*,,,0,1來說,以下各式都是B上布爾表達式:f=a*(0b)*(ab);g=(a*x1)(a*b*x2)(x1*x2*0);h=x1*(x2x3).

布爾代數B上含n個布爾變元的布爾表達式稱為B上一個n元布爾函數.§7.4#1(c)證明布爾恒等式試證:(a*c)

(a

*b)(b*c)=(a*c)

(a

*b).解:

(a*c)

(a

*b)(b*c)=(a*c)

(a

*b)((b*c)*(a

a

))=(a*c)

(a

*b)((b*c)*a)((b*c)*a))=((a*c)

(a*c*b))

((a

*b)

(a

*b*c))

=(a*c)

(a

*b).(第一等式用了幺律;第2等式用了分配律;第3等式用了交換律與結合律;第4等式用了吸收律)§7.4#1(d)試證:(ab)*(bc

)*(c

a)=(ab)*(bc)*(c

a).解:用分配律分別展開上式兩邊并用補元及全下界性質化簡得(式中*省略)左邊=abc

aba

acc

aca

bbc

bba

bccbca=a