第十三章格與布爾代數(shù)

第十三章格與布爾代數(shù)13.1格的定義與性質(zhì)

一、格作為偏序集的定義

定義13.1設(shè)<S,

>是偏序集,如果x,y∈S,{x,y}都有最小上界和最大下界,則稱S關(guān)于偏序

為一個(gè)格。由于最小上界和最大下界的唯一性,可以把求{x,y}的最小上界和最大下界看成x與y的二元運(yùn)算∨和∧,即求x∨y和x∧y分別表示x與y的最小上界和最大下界。

本章中出現(xiàn)的∨和∧符號(hào)只代表格中的運(yùn)算，而不再有其它的含義。例13.1設(shè)n是正整數(shù),Sn是n的正因子的集合。D為整除關(guān)系,則偏序集<Sn,D>構(gòu)成格。

x,y∈Sn,x∨y是lcm(x,y),即x與y的最小公倍數(shù)。x∧y是gcd(x,y),即x與y的最大公約數(shù)。圖13.1給出了格<S8,D>，<S6,D>和<S30,D>.例13.2判斷下列偏序集是否構(gòu)成格,并說(shuō)明理由。(1)<P(B),>,其中P(B)是集合B的冪集。解:是格。

x,y∈P(B),x∨y就是x∪y,x∧y就是x∩y.由于∪和∩運(yùn)算在P(B)上是封閉的,所以x∪y,x∩y∈P(B).稱<P(B),>,為B的冪集格。(2)<Z,≤>,其中Z是整數(shù)集,≤為小于或等于關(guān)系。解:是格。x,y∈Z,x∨y=max(x,y),x∧y=min(x,y),它們都是整數(shù)。(3)偏序集的哈斯圖分別在圖13.2中給出。

{a,b}沒有最大下界不是格{b,d}有兩個(gè)上界c和e,但沒有最小上界不是格{b,c}有三個(gè)上界d,e,f,但沒有最小上界。不是格不是格{a,g}沒有最大下界。例13.3設(shè)G是群,L(G)是G的所有子群的集合。即L(G)={H|H≤G}，在L(G)上定義包含關(guān)系

,則L(G)關(guān)于包含關(guān)系構(gòu)成一個(gè)格,稱為G的子群格。對(duì)任意的H1,H2∈L(G),H1∩H2也是G的子群,而<H1∪H2>是由H1∪H2生成的子群（即包含著H1∪H2的最小的子群）.易見在L(G)中,H1∧H2就是H1∩H2,H1∨H2就是<H1∪H2>.

二．格的性質(zhì)定義13.2設(shè)f是含有格中元素以及符號(hào)=,

,

,∨和∧的命題。令f*是將f中的

替換成

,

替換成

,∨替換成∧,∧替換成∨所得到的命題。稱f*為f的對(duì)偶命題。

格的對(duì)偶原理

設(shè)f是含有格中元素以及符號(hào)=,

,

,∨和∧等的命題。若f對(duì)一切格為真,則f的對(duì)偶命題f*也對(duì)一切格為真。例如,在格中令f是(a∨b)∧c

c,則f*是(a∧b)∨c

c.例如,對(duì)一切格L都有

a,b∈L,a∧b

a

那么對(duì)一切格L都有

a,b∈L,a∨b

a

許多格的性質(zhì)都是互為對(duì)偶命題的。有了格的對(duì)偶原理,在證明格的性質(zhì)時(shí),只須證明其中的一個(gè)命題就可以了。2.運(yùn)算性質(zhì)

定理13.1設(shè)<L,

>是格,則運(yùn)算∨和∧適合交換律、

結(jié)合律、冪等律和吸收律,即(1)

a,b∈L有a∨b=b∨a,

a∧b=b∧a

a,b,c∈L

有(a∨b)∨c=a∨(b∨c),

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

(3)

a∈L有a∨a=a,

a∧a=a

(4)

a,b∈L有a∨(a∧b)=a,

a∧(a∨b)=a(1)證：a∨b和b∨a分別是{a,b}和{b,a}的最小上界。

由于{a,b}={b,a},所以a∨b=b∨a.

由對(duì)偶原理,a∧b=b∧a得證。(2)證：由最小上界定義有

(a∨b)∨ca∨ba

①(a∨b)∨ca∨bb

②(a∨b)∨cc

③由②和③有

(a∨b)∨cb∨c

④由①和④有

(a∨b)∨ca∨（b∨c）同理可證

(a∨b)∨ca∨(b∨c)根據(jù)偏序關(guān)系的反對(duì)稱性有

(a∨b)∨c=a∨(b∨c)由對(duì)偶原理，

(a∧b)∧c=a∧(b∧c)得證。

（3）證：顯然aa∨a,又由aa可得a∨aa。根據(jù)偏序關(guān)系的反對(duì)稱性有a∨a=a由對(duì)偶原理，a∧a=a得證。

（4）證：顯然a∨(a∧b)a

⑤又由aa，a∧ba可得a∨(a∧b)a

⑥由⑤和⑥可得

a∨(a∧b)=a由對(duì)偶原理，a∧(a∨b)=a得證。

三．格作為代數(shù)系統(tǒng)的定義定理13.2設(shè)<S,*,

>是具有兩個(gè)二元運(yùn)算的代數(shù)系統(tǒng),若對(duì)于*和

運(yùn)算適合交換律、結(jié)合律、吸收律,則可以適當(dāng)定義S中的偏序

,使得<S,

>構(gòu)成一個(gè)格,且

a,b∈S有a∧b=a*b,a∨b=a

b.

根據(jù)定理13.2,可以給出格的另一個(gè)等價(jià)定義。

定義13.3設(shè)<S,*,

>是代數(shù)系統(tǒng),*和

是二元運(yùn)算,如果*和

滿足交換律,結(jié)合律和吸收律,則<S,*,

>構(gòu)成一個(gè)格。格中運(yùn)算滿足四條算律,還有一條冪等律(見定理13.1),但冪等律可以由吸收律推出,所以定義13.3中只須滿足三條算律即可。證：(1)先證在S中*和運(yùn)算都適合冪等律。aS，由吸收律得a*a=a*(a(a*a))=a同理有aa=a(2)在S上定義二元關(guān)系R，a，bS有<a,b>Rab=b下面證明R是S上的偏序。根據(jù)冪等律，aS都有aa=a，即<a,a>R所以R在S上是自反的。a，bS有aRb且bRaab=b且ba=aa=ba=ab=b這就證明了R在S上是反對(duì)稱的。a，b，cS有aRb且bRcab=b且bc=cac=a(bc）ac=（ab)cac=bc=caRc這就證明了R在S上是傳遞的。綜上所述，R為S上的偏序，記為。證明<S,>構(gòu)成格。a，bS有a(ab)=(aa)b=abb(ab)=(a(bb)=ab這就推出aab和bab，所以ab是{a,b}的上界。假設(shè)c為{a,b}的上界，則有ac=c和bc=c，從而有(ab)c=a(bc)=ac=c這就證明了abc，所以ab是{a,b}的最小上界，即ab=ab為證明a*b是{a，b}的最大下界，先證ab=ba*b=a首先由ab=b可知a*b=a*(ab)=a反之由a*b=a可知ab=(a*b)b=b(b*a)=b由ab=ba*b=a有aba*b=a類似可證明a*b是{a，b}的最大下界，即ab=a*b無(wú)論是偏序集定義的格,還是代數(shù)系統(tǒng)定義的格,都統(tǒng)稱為格L.

定理13.3設(shè)L是格，則a,b∈L有aba∧b=aa∨b=b由于aa和ab可知a是{a,b}的下界故aa∧b顯然a∧ba根據(jù)關(guān)系的反對(duì)稱性得a∧b=a因?yàn)閍∧b=a，所以a∨b=(a∧b)∨b=b證明：先證aba∧b=a再證a∧b=aa∨b=b最后證a∨b=bab因?yàn)閍a∨b,即ab定理13.4設(shè)L是格，則a,b,c,d∈L,若ab且cd,則a∧cb∧d,a∨cb∨d證明：a∧caba∧ccd因此a∧cb∧d同理可證a∨cb∨d例13.4設(shè)L是格，證明a,b,c∈L有a∨(b∧c)(a∨b)∧(a∨c)證明：由aa,b∧cb得

a∨(b∧c)a∨b由aa,b∧cc得

a∨(b∧c)a∨c所以a∨(b∧c)(a∨b)∧(a∨c)格中∨、∧運(yùn)算不一定滿足分配律1.判斷下述偏序集是否構(gòu)成格？如果不是說(shuō)明理由。不能構(gòu)成格可以構(gòu)成格可以構(gòu)成格2.求下述命題的對(duì)偶命題。（1）(a∧b)∨b=b

(a∨b)∧b=b（2）b∨(c∧a)

(b∨c)∧ab∧(c∨a)

(b∧c)∨a3.證明：(a∧b)∨(c∧d)

(a∨c)∧(b∨d)證明：a∧b

a

a∨c，a∧b

b

b∨d，所以(a∧b)

(a∨c)∧(b∨d)，同理(c∧d)

(a∨c)∧(b∨d)從而得到(a∧b)∨(c∧d)

(a∨c)∧(b∨d)方法二：所以(c∧d)

(a∨c)∧(b∨d)，所以由定理4得(a∧b)

(a∨c)∧(b∨d)，同理由ca∨c和db∨d從而得到(a∧b)∨(c∧d)

(a∨c)∧(b∨d)aa∨cbb∨d13.2子格與格同態(tài)定義13.4設(shè)<L,∧,∨>是格,S是L的非空子集,若S關(guān)于L中的運(yùn)算∧和∨仍構(gòu)成格,則稱S是L的子格。解：S1不是L的子格對(duì)于e和f,有e∧f=c,但c

S1.S2是L的子格例13.5設(shè)格L如圖13.3所示。令

S1={a,e,f,g}，

S2={a,b,e,g}問(wèn)S1和S2是否是L的子格？圖13.3二．格同態(tài)的定義及其性質(zhì)

1．格同態(tài)的定義定義13.5設(shè)L1和L2是格,f:L1→L2,若

a,b∈L1有

f(a∧b)=f(a)∧f(b),

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

成立，則稱f為格L1到L2的同態(tài)映射,簡(jiǎn)稱格同態(tài)。例13.6(1)設(shè)L1={2n|n∈Z+}，L2={2n＋1|n∈N}則L1和L2關(guān)于通常數(shù)的小于或等于關(guān)系構(gòu)成格。令f:L1→L2,f(x)=x-1驗(yàn)證f是L1到L2的同態(tài)映射

證明：對(duì)任意的x,y∈L1有x∨y＝max(x,y)f(x∨y)=f(max(x,y))=max(x,y)-1f(x)∨f(y)=(x-1)∨(y-1)=max(x-1,y-1)=max(x,y)-1即有f(x∨y)=f(x)∨f(y),

同理f(x∧y)=f(min(x,y))=min(x,y)-1

f(x)∧f(y)=(x-1)∧(y-1)=min(x-1,y-1)=min(x,y)-1即f(x∧y)=f(x)∧f(y)所以f是L1到L2的同態(tài)映射

(2)如圖13.4中的格L1,L2和L3，若定義f1:L1→L2f1(a)=f1(b)=f1(c)=a1,f1(d)=d1f2:L1→L3

f2(a)=a2,f2(b)=b2,f2(c)=c2,f2(d)=d2問(wèn)f1和f2是否格同態(tài)？L1L2L3解：f1和f2都不是格同態(tài)，f1(b∨c)=f1(d)=d1

f1(b)∨f1(c)=a1∨a1=a1f1(b∨c)≠f1(b)∨f1(c)f2(b∨c)=f2(d)=d2f2(b)∨f2(c)=b2∨c2=c2f2(b∨c)≠f2(b)∨f2(c)定理13.5設(shè)f是格L1到L2的映射，

（1）若f是格同態(tài)映射，則f是保序映射，即x,y∈L1,有xyf(x)f(y)（2）若f是雙射，則f是格同構(gòu)映射，當(dāng)且僅當(dāng)x,y∈L1有xyf(x)f(y)（1）證明：任取x,y∈L1,xy由定理13.3知x∨y＝y(tǒng)又由于f是格同態(tài)映射，必有f(y)＝f(x∨y)=f(x)∨f(y),

所以有f(x)f(y)(2)證明：充分性：只需證明是L1到L2的同態(tài)映射即可。任取x,y∈L1,令x∨y=z，由xz和y

z知(x)(z),(y)(z)從而有(x)(y)(z)=(xy)另一方面，由(x)(y)L2和的滿射性可知，必存在uL1使得(u)=(x)(y)因此有(x)(u),(y)(u)由已知條件可得xu和y

u從而推出xyu再由已知條件得(x)(y)(u)=(xy)綜合上述有(x)(y)=(xy)同理可證(x)(y)=(xy)必要性：由(1)的結(jié)論必有xy(x)(y)反之，若(x)(y)由于是同構(gòu)映射，則(xy)=(x)(y)=(y)由于是雙射，必有xy=y從而證明了xy例13.7設(shè)L1＝<S12,D>,L2＝<S12,≤>是格,其中S12是12的所有正因子構(gòu)成的集合，D為整除關(guān)系，≤為通常數(shù)的小于等于關(guān)系，令f:S12→S12,f(x)=x問(wèn)f是否是L1到L2的格同構(gòu)？解：不是。因?yàn)閒(2)=2f(3)=3f(2)≤f(3)但是2并不能整除3三．格的直積

類似于半群,群和環(huán),也可以定義格的直積。定義13.6設(shè)L1和L2是格,定義L1×L2上的運(yùn)算∩,∪:

<a1,b1>,<a2,b2>∈L1×L2

<a1,b1>∩<a2,b2>=<a1∧a2,b1∧b2>

<a1,b1>∪<a2,b2>=<a1∨a2,b1∨b2>

稱<L1×L2,∩,∪>為格L1和L2的直積?？梢宰C明<L1×L2,∩,∪>仍是格。

<a1,b1>,<a2,b2>,<a3,b3>∈L1×L2,有

<a1,b1>∩<a2,b2>=<a1∧a2,b1∧b2>

<a2,b2>∩<a1,b1>=<a2∧a1,b2∧b1>交換律

(<a1,b1>∩<a2,b2>)∩<a3,b3>=<a1∧a2,b1∧b2>∩<a3,b3>

=<(a1∧a2)∧a3,(b1∧b2)∧b3>=<a1∧a2∧a3,b1∧b2∧b3>結(jié)合律

<a1,b1>∩(<a2,b2>∩<a3,b3>)=<a1,b1>∩<a2∧a3,b2∧b3>

=<a1∧(a2∧a3),b1∧(b2∧b3)>=<a1∧a2∧a3,b1∧b2∧b3><a1,b1>∩(<a1,b1>∪<a2,b2>)=<a1,b1>∩<a1∨a2,b1∨b2>

=<a1∧(a1∨a2),b1∧(b1∨b2)>=<a1,b1>同理有

<a1,b1>∪(<a1,b1>∩<a2,b2>)=<a1,b1>∩和∪運(yùn)算滿足吸收律

同理可證∪運(yùn)算也滿足交換律和結(jié)合律、吸收律從而證明L1×L2仍是格。

例如：格L=<{0,1},≤>,≤為通常的小于或等于關(guān)系,則<L×L,∪,∩>是L與L的直積，是格<0,0>∪<0,1>＝<max(0,0),max(0,1)>＝<0,1><0,0>∪<1,1>＝<max(0,1),max(0,1)>＝<1,1><0,1>∪<1,1>＝<max(0,1),max(1,1)>＝<1,1><0,0>是格L×L的最小元,<1,1>是最大元<0,1>與<1,0>是不可比的<0,0><0,1><1,0><1,1>其中L×L={<0,0>,<0,1>,<1,0>,<1,1>},畫出該格對(duì)應(yīng)偏序集<L×L,>的哈斯圖。<0,0><1,0><1,1>,所以<0,0><0,1><1,1>,13.3分配格與有補(bǔ)格

1．分配格的定義及實(shí)例一般說(shuō)來(lái),格中運(yùn)算∨對(duì)∧滿足分配不等式,即

a,b,c∈L,有a∨(b∧c)

(a∨b)∧(a∨c)

但是不一定滿足分配律.滿足分配律的格稱為分配格。定義13.7設(shè)<L,∧,∨>是格,若

a,b,c∈L,有

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

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

則稱L為分配格。

上面兩個(gè)等式互為對(duì)偶式。在證明L為分配格時(shí),只須證明其中的一個(gè)等式即可。例13.8

分配格分配格b∧(c∨d)=b∧e=b

(b∧c)∨(b∧d)=a∨a=a不是分配格c∨(b∧d)=c∨a=c

(c∨b)∧(c∨d)=e∧d=d不是分配格鉆石格五角格分配格的判別及性質(zhì)定理13.6設(shè)L是格,則L是分配格當(dāng)且僅當(dāng)L中不含有與鉆石格或五角格同構(gòu)的子格。推論(1)小于五元的格都是分配格。

(2)任何一條鏈都是分配格。例13.9說(shuō)明圖13.6中的格是否為分配格,為什么？不是分配格

因?yàn)閧a,b,c,d,e}是L1的子格,并且同構(gòu)于鉆石格

不是分配格

{a,b,c,e,f}是L2的子格,并且同構(gòu)于五角格

{a,c,b,e,f}是L3的子格,也同構(gòu)于鉆石格。

不是分配格

定理13.7格L是分配格當(dāng)且僅當(dāng)

a,b,c∈L,a∧b=a∧c且a∨b=a∨c

b=c.證:必要性。

a,b,c∈L,有b=b∨(a∧b)(吸收律,交換律)=b∨(a∧c)(已知條件代入)=(b∨a)∧(b∨c)(分配律)=(a∨c)∧(b∨c)(已知條件代入,交換律)

=(a∧b)∨c(分配律)=(a∧c)∨c(已知條件代入)=c(交換律,吸收律)充分性。（反證法）

假若

a,b,c∈L,有

a∧b=a∧c且a∨b=a∨c

b=c

成立，而L不是分配格.根據(jù)定理13.6，L中必含有與鉆石格或五角格同構(gòu)的子格。

從而推出

x∧y=x∧z=u,

x∨y=x∨z=v

但y≠z,與已知矛盾。

對(duì)五角格的情況同理可證。假設(shè)L中含有與鉆石格同構(gòu)的子格,且該子格為{u,v,x,y,z},其中u為它的最小元,v為它的最大元。

xyzuv使用定理13.7也可以判別一個(gè)格是否為分配格。

在L1中有

b∨c=b∨d,

b∧c=b∧d,但c≠d在L2中有

b∧c=b∧e,

b∨c=b∨e,但c≠e在L3中有

c∧b=c∧d,

c∨b=c∨d,但b≠d

有補(bǔ)格

定義13.8設(shè)L是格,

若存在a∈L使得x∈L有a

x,則稱a為L(zhǎng)的全下界；

若存在b∈L使得x∈L有x

b,則稱b為L(zhǎng)的全上界。格L若存在全下界或全上界,一定是唯一的。假若a1和a2都是格L的全下界,則有a1

a2和a2

a1.根據(jù)偏序關(guān)系

的反對(duì)稱性必有a1=a2.由于全下界和全上界的唯一性,一般將格L的全下界記為0,全上界記為1.全上界和全下界是格中最大元和最小元。定義13.9設(shè)L是格,若L存在全下界和全上界,則稱

L為有界格,并將L記為<L,∧,∨,0,1>.不難看出,有限格L一定是有界格。

設(shè)L是n元格,且L={a1,a2,…,an},那么a1∧a2∧…∧an是L的全下界,而a1∨a2∨…∨an是L的全上界。

對(duì)于無(wú)限格L來(lái)說(shuō),有的是有界格,有的不是有界格。

如集合B的冪集格<P(B),∩,∪>,不管B是有窮集還是無(wú)窮集,它都是有界格。

它的全下界是空集

,全上界是B.整數(shù)集Z關(guān)于通常數(shù)的小于或等于關(guān)系構(gòu)成的格不是有界格,因?yàn)椴淮嬖谧钚『妥畲蟮恼麛?shù)。因此L是有界格。定理13.8設(shè)<L,∧,∨,0,1>是有界格,則

a∈L有

a∧0=0,

a∨0=a，a∧1=a,

a∨1=1全下界0是關(guān)于∧運(yùn)算的零元,∨運(yùn)算的單位元。

全上界1是關(guān)于∨運(yùn)算的零元,∧運(yùn)算的單位元。對(duì)于涉及到有界格的命題,如果其中含有全下界0或全上界1,在求該命題的對(duì)偶命題時(shí),必須將0替換成1,而將1替換成0.

在有界格中,定義13.10設(shè)<L,∧,∨,0,1>是有界格,a∈L,若存在b∈L

使得a∧b=0和a∨b=1

成立,則稱b是a的補(bǔ)元。a和b互為補(bǔ)元。

例13.10考慮下圖中的四個(gè)格。a與c互為補(bǔ)元,b沒有補(bǔ)元。L1L1是有界格,a是全下界,c是全上界a與d互為補(bǔ)元,b與c也互為補(bǔ)元。L3中的a與e互為補(bǔ)元,b的補(bǔ)元是c和d,c的補(bǔ)元是b和d,d的補(bǔ)元是b和c.b,c,d每個(gè)元素都有兩個(gè)補(bǔ)元。L2L3L2是有界格,a是全下界,d是全上界L3是有界格,其中a為全下界,e為全上界,L4中的a與e互為補(bǔ)元,b的補(bǔ)元是c和d,c的補(bǔ)元是b,d的補(bǔ)元是b。

L4是有界格,其中a為全下界,e為全上界,在任何有界格中，全下界0與全上界1互補(bǔ)。對(duì)于其他元素，可能存在補(bǔ)元，也可能不存在補(bǔ)元。如果存在，可能是惟一的，也可能是多個(gè)補(bǔ)元。對(duì)于有界分配格，如果它的元素存在補(bǔ)元，一定是唯一的。定理13.9設(shè)<L,∧,∨,0,1>是有界分配格。若L中元素a存在補(bǔ)元，則存在唯一的補(bǔ)元。

證:假設(shè)b,c是a的補(bǔ)元，則有a∨c=1,a∧c=0,

又知b是a的補(bǔ)元，故a∨b=1,a∧b=0

從而得到a∨c=a∨b,a∧c=a∧b,由于L是分配格，根據(jù)定理13.7，b=c.定義13.11設(shè)<L,∧,∨,0,1>是有界格,若L中所有元素都有補(bǔ)元存在，則稱L為有補(bǔ)格。

例如，圖13.5中:

L2,L3和L4是有補(bǔ)格，L1不是有補(bǔ)格。

圖13.6中L2和L3是有補(bǔ)格，L1不是有補(bǔ)格。1.判別下述格L是否為分配格。求出每個(gè)格的補(bǔ)元。說(shuō)明它們是否為有補(bǔ)格。

L1

L2

不是分配格它含有與鉆石格同構(gòu)的子格{a,b,c,d,e}。含有與五角格同構(gòu)的子格不是分配格a與h互為補(bǔ)元，其它元素沒有補(bǔ)元。a與g互為補(bǔ)元；b的補(bǔ)元為c,d,f；c的補(bǔ)元為b,d,e,f;d的補(bǔ)元為b,c,e；e的補(bǔ)元為c,d,f；f的補(bǔ)元為b,c,e。是有補(bǔ)格不是有補(bǔ)格。

L3含有與五角格同構(gòu)的子格{a,b,g,h,d}不是分配格a與h互為補(bǔ)元，b的補(bǔ)元為d；c的補(bǔ)元為d；d的補(bǔ)元為b,c,g；g的補(bǔ)元為d。是有補(bǔ)格13.4布爾代數(shù)1．布爾代數(shù)作為格的定義及實(shí)例定義13.12如果一個(gè)格是有補(bǔ)分配格,則稱它為布爾格或布爾代數(shù)。根據(jù)定理13.9,在分配格中,如果一個(gè)元素存在補(bǔ)元,則是唯一的。

因此,在布爾代數(shù)中,每個(gè)元素都存在著唯一的補(bǔ)元,可以把求補(bǔ)元的運(yùn)算看作是布爾代數(shù)中的一元運(yùn)算。

從而可以把一個(gè)布爾代數(shù)標(biāo)記為<B,∧,∨,＇,0,1>,其中∧,∨,0,1和有界格一樣,＇為求補(bǔ)運(yùn)算,

a∈B,a＇是a的補(bǔ)元。例13.11

設(shè)S110={1,2,5,10,11,22,55,110}是110的正因子集合。令gcd,lcm分別表示求最大公約數(shù)和最小公倍數(shù)的運(yùn)算。問(wèn)<S110,gcd,lcm>是否構(gòu)成布爾代數(shù)？為什么？解:容易驗(yàn)證

x,y∈S110有g(shù)cd(x,y)∈S110和lcm(x,y)∈S110.且

x,y,z∈S110有g(shù)cd(x,y)=gcd(y,x)

lcm(x,y)=lcm(y,x)交換律結(jié)合律gcd(gcd(x,y),z)=gcd(x,gcd(y,z))

lcm(lcm(x,y),z)=lcm(x,lcm(y,z))吸收律gcd(x,lcm(x,y))=x

lcm(x,gcd(x,y))=x因此,<S110,gcd,lcm>構(gòu)成格。先證明它是格。下面證明它是分配格。

易驗(yàn)證

x,y,z∈S110有

gcd(x,lcm(y,z))=lcm(gcd(x,y),gcd(x,z))1作為S110中的全下界,110為全上界,且

1和110互為補(bǔ)元,2和55互為補(bǔ)元,

5和22互為補(bǔ)元,10和11互為補(bǔ)元,最后證明它是有補(bǔ)格。從而證明了<S110,gcd,lcm>為布爾代數(shù)。例13.12設(shè)B為任意集合,證明B的冪集格<P(B),∩,∪,~,

,B>構(gòu)成布爾代數(shù),稱為集合代數(shù)。證:因?yàn)椤珊汀冗\(yùn)算滿足交換律,結(jié)合律和吸收律,所以P(B)關(guān)于∩和∪構(gòu)成格由于∩和∪互相可分配,因此P(B)是分配格,且全下界是空集

,全上界是B.根據(jù)絕對(duì)補(bǔ)的定義,取全集為B,

x∈P(B),~x是x的補(bǔ)元。從而證明P(B)是有補(bǔ)分配格,即布爾代數(shù)。

所以P(B)是有補(bǔ)格2.布爾代數(shù)的性質(zhì)定理13.10設(shè)<B,∧,∨,＇,0,1>是布爾代數(shù),則

(1)

a∈B,

(a＇)＇=a.

(2)

a,b∈B,

(a∧b)＇=a＇∨b＇,(a∨b)＇=a＇∧b＇證:(1)(a‘)’是a‘的補(bǔ)元。a也是a’的補(bǔ)元。由補(bǔ)元的唯一性得(a＇)＇=a.(2)對(duì)任意a,b∈B有(a∧b)∨(a＇∨b＇)=(a∨a＇∨b＇)∧(b∨a＇∨b＇)=(1∨b＇)∧(a＇∨1)=1∧1=1,(a∧b)∧(a＇∨b＇)=(a∧b∧a＇)∨(a∧b∧b＇)=(0∧b)∨(a∧0)=0∨0=0.所以a＇∨b＇是a∧b的補(bǔ)元,根據(jù)補(bǔ)元的唯一性有

(a∧b)＇=a＇∨b＇

同理可證(a∨b)＇=a＇∧b＇.(1)稱為雙重否定律,(2)稱為德摩根律。3.布爾代數(shù)作為代數(shù)系統(tǒng)的定義

定義13.13設(shè)<B,*,

>是代數(shù)系統(tǒng),*和

是二元運(yùn)算。若*和

運(yùn)算滿足：(1)交換律,即

a,b∈B有a*b=b*a,a

b=b

a(2)分配律,即

a,b,c∈B有

a*(b

c)=(a*b)

(a*c)，a

(b*c)=(a

b)*(a

c)(3)同一律,即存在0,1∈B,使得

a∈B有a*1=a,a

0=a(4)補(bǔ)元律,即

a∈B,存在a＇∈B使得a*a＇=0,a

a＇=1則稱<B,*,

>是一個(gè)布爾代數(shù)。同一律就是指運(yùn)算含有單位元的性質(zhì)，這里的1是*運(yùn)算的單位元,0是

運(yùn)算的單位元。可以證明這個(gè)定義與有補(bǔ)分配格的定義是等價(jià)的。例13.11

設(shè)S110={1,2,5,10,11,22,55,110}是110的正因子集合。令gcd,lcm分別表示求最大公約數(shù)和最小公倍數(shù)的運(yùn)算。問(wèn)<S110,gcd,lcm>是否構(gòu)成布爾代數(shù)？為什么？例13.12設(shè)B為任意集合,證明B的冪集格<P(B),∩,∪,~,

,B>構(gòu)成布爾代數(shù),稱為集合代數(shù)。解：只需驗(yàn)證gcd,lcm運(yùn)算是否滿足：交換律、分配律、同一律和補(bǔ)元律。解：只需驗(yàn)證∩,∪運(yùn)算是否滿足：交換律、分配律、同一律和補(bǔ)元律。二．布爾代數(shù)的子代數(shù)及實(shí)例

定義13.14設(shè)<B,∧,∨,‘,0,1>是布爾代數(shù),S是B的非空子集,若0,1∈S,且S對(duì)∧,∨和‘運(yùn)算都是封閉的,則稱S是B的子布爾代數(shù)。例13.13設(shè)<B,∧,∨,＇,0,1>是布爾代數(shù),a,b∈B,且a

b.令S={x|x∈B,且a

x

b}

稱S為B中的區(qū)間,可簡(jiǎn)記為[a,b].證明[a,b]是一個(gè)布爾代數(shù)。證明:S為B的非空子集,且a,b分別為S的全上界和全下界.對(duì)任意的x,y∈S,都有ax∧yb和ax∨yb這說(shuō)明S關(guān)于∧和∨運(yùn)算是封閉的.易見∧和∨運(yùn)算在S上適合交換律和分配律.對(duì)任意的x∈S,都有x∨a=x,x∧b=x,滿足同一律對(duì)任意的x∈S,令y=(a∨x＇)∧baa∨x＇

,ab,故ａ

(a∨x’)∧bｂ

所以y∈S,x∨y=x∨((a∨x＇)∧b)=x∨(a∧b)∨(x＇∧b)(分配律)=(x∨x＇)∧(x∨b)(分配律)=1∧(x∨b)(補(bǔ)元律)=x∨b(交換律,同一律)=x∨a∨(x＇∧b)(由ab)=x∨(x＇∧b)(由ax)=b(由xb)下面證明y是x的補(bǔ)元x∧y=x∧((a∨x＇)∧b)=(x∧a)∨(x∧x＇)(分配律)=(x∧a)∨0(補(bǔ)元律)=a(由ax)=x∧(a∨x＇)(由xb)=x∧a(同一律)由定義<S,∧,∨>構(gòu)成一布爾代數(shù),其全下界為a,全上界為b,對(duì)任意的x∈S,x關(guān)于這個(gè)全上界和全下界的補(bǔ)元是(a∨x＇)∧b當(dāng)a=0且b=1時(shí),這時(shí)S是B的子布爾代數(shù).但當(dāng)a≠0或b≠1時(shí),S不是B的子布爾代數(shù).S滿足補(bǔ)元律例13.14考慮110的正因子集合S110關(guān)于gcd,lcm運(yùn)算構(gòu)成的布爾代數(shù)。

它有以下的子布爾代數(shù)：

{1,110}

{1,2,55,110}

{1,5,22,110}

{1,10,11,110}

{1,2,5,10,11,22,55,110}

三．布爾代數(shù)的同態(tài)映射及實(shí)例定義13.15設(shè)<B1,∧,∨,＇,0,1>和<B2,∩,∪,-,θ,E>是兩個(gè)布爾代數(shù)。這里的∩,∪,-泛指布爾代數(shù)B2中的求最大下界,最小上界和補(bǔ)元的運(yùn)算。θ和E分別是B2的全下界和全上界。

f:B1→B2.如果對(duì)于任意的a,b∈B1有f(a∨b)=f(a)∪f(wàn)(b)f(a∧b)=f(a)∩f(b)f(a＇)=-f(a)則稱f是布爾代數(shù)B1到B2的同態(tài)映射,簡(jiǎn)稱布爾代數(shù)的同態(tài)。類似于其它代數(shù)系統(tǒng),也可以定義布爾代數(shù)的單同態(tài),滿同態(tài)和同構(gòu)。例13.15設(shè)<B1,∧,∨,＇,0,1>和<B2,∩,∪,-,θ,E>是布爾代數(shù)。f:B1→B2.若

a,b∈B1有

f(a∧b)=f(a)∩f(b)

f(a＇)=-f(a)

證明f是B1到B2的同態(tài)。證:只須證明

a,b∈B1有

f(a∨b)=f(a)∪f(wàn)(b)成立即可。

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

(雙重否定律)=-f((a∨b)＇)=-f(a＇∧b＇)

(德摩根律)=-(f(a＇