第十三章格与布尔代数

第十三章格与布尔代数13.1格的定义与性质

一、格作为偏序集的定义

定义13.1设<S,

>是偏序集,如果x,y∈S,{x,y}都有最小上界和最大下界,则称S关于偏序

为一个格。由于最小上界和最大下界的唯一性,可以把求{x,y}的最小上界和最大下界看成x与y的二元运算∨和∧,即求x∨y和x∧y分别表示x与y的最小上界和最大下界。

本章中出现的∨和∧符号只代表格中的运算，而不再有其它的含义。例13.1设n是正整数,Sn是n的正因子的集合。D为整除关系,则偏序集<Sn,D>构成格。

x,y∈Sn,x∨y是lcm(x,y),即x与y的最小公倍数。x∧y是gcd(x,y),即x与y的最大公约数。图13.1给出了格<S8,D>，<S6,D>和<S30,D>.例13.2判断下列偏序集是否构成格,并说明理由。(1)<P(B),>,其中P(B)是集合B的幂集。解:是格。

x,y∈P(B),x∨y就是x∪y,x∧y就是x∩y.由于∪和∩运算在P(B)上是封闭的,所以x∪y,x∩y∈P(B).称<P(B),>,为B的幂集格。(2)<Z,≤>,其中Z是整数集,≤为小于或等于关系。解:是格。x,y∈Z,x∨y=max(x,y),x∧y=min(x,y),它们都是整数。(3)偏序集的哈斯图分别在图13.2中给出。

{a,b}没有最大下界不是格{b,d}有两个上界c和e,但没有最小上界不是格{b,c}有三个上界d,e,f,但没有最小上界。不是格不是格{a,g}没有最大下界。例13.3设G是群,L(G)是G的所有子群的集合。即L(G)={H|H≤G}，在L(G)上定义包含关系

,则L(G)关于包含关系构成一个格,称为G的子群格。对任意的H1,H2∈L(G),H1∩H2也是G的子群,而<H1∪H2>是由H1∪H2生成的子群（即包含着H1∪H2的最小的子群）.易见在L(G)中,H1∧H2就是H1∩H2,H1∨H2就是<H1∪H2>.

二．格的性质定义13.2设f是含有格中元素以及符号=,

,

,∨和∧的命题。令f*是将f中的

替换成

,

替换成

,∨替换成∧,∧替换成∨所得到的命题。称f*为f的对偶命题。

格的对偶原理

设f是含有格中元素以及符号=,

,

,∨和∧等的命题。若f对一切格为真,则f的对偶命题f*也对一切格为真。例如,在格中令f是(a∨b)∧c

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

c.例如,对一切格L都有

a,b∈L,a∧b

a

那么对一切格L都有

a,b∈L,a∨b

a

许多格的性质都是互为对偶命题的。有了格的对偶原理,在证明格的性质时,只须证明其中的一个命题就可以了。2.运算性质

定理13.1设<L,

>是格,则运算∨和∧适合交换律、

结合律、幂等律和吸收律,即(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.

由对偶原理,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)根据偏序关系的反对称性有

(a∨b)∨c=a∨(b∨c)由对偶原理，

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

（3）证：显然aa∨a,又由aa可得a∨aa。根据偏序关系的反对称性有a∨a=a由对偶原理，a∧a=a得证。

（4）证：显然a∨(a∧b)a

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

⑥由⑤和⑥可得

a∨(a∧b)=a由对偶原理，a∧(a∨b)=a得证。

三．格作为代数系统的定义定理13.2设<S,*,

>是具有两个二元运算的代数系统,若对于*和

运算适合交换律、结合律、吸收律,则可以适当定义S中的偏序

,使得<S,

>构成一个格,且

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

b.

根据定理13.2,可以给出格的另一个等价定义。

定义13.3设<S,*,

>是代数系统,*和

是二元运算,如果*和

满足交换律,结合律和吸收律,则<S,*,

>构成一个格。格中运算满足四条算律,还有一条幂等律(见定理13.1),但幂等律可以由吸收律推出,所以定义13.3中只须满足三条算律即可。证：(1)先证在S中*和运算都适合幂等律。aS，由吸收律得a*a=a*(a(a*a))=a同理有aa=a(2)在S上定义二元关系R，a，bS有<a,b>Rab=b下面证明R是S上的偏序。根据幂等律，aS都有aa=a，即<a,a>R所以R在S上是自反的。a，bS有aRb且bRaab=b且ba=aa=ba=ab=b这就证明了R在S上是反对称的。a，b，cS有aRb且bRcab=b且bc=cac=a(bc）ac=（ab)cac=bc=caRc这就证明了R在S上是传递的。综上所述，R为S上的偏序，记为。证明<S,>构成格。a，bS有a(ab)=(aa)b=abb(ab)=(a(bb)=ab这就推出aab和bab，所以ab是{a,b}的上界。假设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无论是偏序集定义的格,还是代数系统定义的格,都统称为格L.

定理13.3设L是格，则a,b∈L有aba∧b=aa∨b=b由于aa和ab可知a是{a,b}的下界故aa∧b显然a∧ba根据关系的反对称性得a∧b=a因为a∧b=a，所以a∨b=(a∧b)∨b=b证明：先证aba∧b=a再证a∧b=aa∨b=b最后证a∨b=bab因为aa∨b,即ab定理13.4设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设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)格中∨、∧运算不一定满足分配律1.判断下述偏序集是否构成格？如果不是说明理由。不能构成格可以构成格可以构成格2.求下述命题的对偶命题。（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子格与格同态定义13.4设<L,∧,∨>是格,S是L的非空子集,若S关于L中的运算∧和∨仍构成格,则称S是L的子格。解：S1不是L的子格对于e和f,有e∧f=c,但c

S1.S2是L的子格例13.5设格L如图13.3所示。令

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

S2={a,b,e,g}问S1和S2是否是L的子格？图13.3二．格同态的定义及其性质

1．格同态的定义定义13.5设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的同态映射,简称格同态。例13.6(1)设L1={2n|n∈Z+}，L2={2n＋1|n∈N}则L1和L2关于通常数的小于或等于关系构成格。令f:L1→L2,f(x)=x-1验证f是L1到L2的同态映射

证明：对任意的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的同态映射

(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问f1和f2是否格同态？L1L2L3解：f1和f2都不是格同态，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设f是格L1到L2的映射，

（1）若f是格同态映射，则f是保序映射，即x,y∈L1,有xyf(x)f(y)（2）若f是双射，则f是格同构映射，当且仅当x,y∈L1有xyf(x)f(y)（1）证明：任取x,y∈L1,xy由定理13.3知x∨y＝y又由于f是格同态映射，必有f(y)＝f(x∨y)=f(x)∨f(y),

所以有f(x)f(y)(2)证明：充分性：只需证明是L1到L2的同态映射即可。任取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)的结论必有xy(x)(y)反之，若(x)(y)由于是同构映射，则(xy)=(x)(y)=(y)由于是双射，必有xy=y从而证明了xy例13.7设L1＝<S12,D>,L2＝<S12,≤>是格,其中S12是12的所有正因子构成的集合，D为整除关系，≤为通常数的小于等于关系，令f:S12→S12,f(x)=x问f是否是L1到L2的格同构？解：不是。因为f(2)=2f(3)=3f(2)≤f(3)但是2并不能整除3三．格的直积

类似于半群,群和环,也可以定义格的直积。定义13.6设L1和L2是格,定义L1×L2上的运算∩,∪:

<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的直积。可以证明<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>结合律

<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>∩和∪运算满足吸收律

同理可证∪运算也满足交换律和结合律、吸收律从而证明L1×L2仍是格。

例如：格L=<{0,1},≤>,≤为通常的小于或等于关系,则<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>},画出该格对应偏序集<L×L,>的哈斯图。<0,0><1,0><1,1>,所以<0,0><0,1><1,1>,13.3分配格与有补格

1．分配格的定义及实例一般说来,格中运算∨对∧满足分配不等式,即

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

(a∨b)∧(a∨c)

但是不一定满足分配律.满足分配律的格称为分配格。定义13.7设<L,∧,∨>是格,若

a,b,c∈L,有

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

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

则称L为分配格。

上面两个等式互为对偶式。在证明L为分配格时,只须证明其中的一个等式即可。例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不是分配格钻石格五角格分配格的判别及性质定理13.6设L是格,则L是分配格当且仅当L中不含有与钻石格或五角格同构的子格。推论(1)小于五元的格都是分配格。

(2)任何一条链都是分配格。例13.9说明图13.6中的格是否为分配格,为什么？不是分配格

因为{a,b,c,d,e}是L1的子格,并且同构于钻石格

不是分配格

{a,b,c,e,f}是L2的子格,并且同构于五角格

{a,c,b,e,f}是L3的子格,也同构于钻石格。

不是分配格

定理13.7格L是分配格当且仅当

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不是分配格.根据定理13.6，L中必含有与钻石格或五角格同构的子格。

从而推出

x∧y=x∧z=u,

x∨y=x∨z=v

但y≠z,与已知矛盾。

对五角格的情况同理可证。假设L中含有与钻石格同构的子格,且该子格为{u,v,x,y,z},其中u为它的最小元,v为它的最大元。

xyzuv使用定理13.7也可以判别一个格是否为分配格。

在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

有补格

定义13.8设L是格,

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

x,则称a为L的全下界；

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

b,则称b为L的全上界。格L若存在全下界或全上界,一定是唯一的。假若a1和a2都是格L的全下界,则有a1

a2和a2

a1.根据偏序关系

的反对称性必有a1=a2.由于全下界和全上界的唯一性,一般将格L的全下界记为0,全上界记为1.全上界和全下界是格中最大元和最小元。定义13.9设L是格,若L存在全下界和全上界,则称

L为有界格,并将L记为<L,∧,∨,0,1>.不难看出,有限格L一定是有界格。

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

对于无限格L来说,有的是有界格,有的不是有界格。

如集合B的幂集格<P(B),∩,∪>,不管B是有穷集还是无穷集,它都是有界格。

它的全下界是空集

,全上界是B.整数集Z关于通常数的小于或等于关系构成的格不是有界格,因为不存在最小和最大的整数。因此L是有界格。定理13.8设<L,∧,∨,0,1>是有界格,则

a∈L有

a∧0=0,

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

a∨1=1全下界0是关于∧运算的零元,∨运算的单位元。

全上界1是关于∨运算的零元,∧运算的单位元。对于涉及到有界格的命题,如果其中含有全下界0或全上界1,在求该命题的对偶命题时,必须将0替换成1,而将1替换成0.

在有界格中,定义13.10设<L,∧,∨,0,1>是有界格,a∈L,若存在b∈L

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

成立,则称b是a的补元。a和b互为补元。

例13.10考虑下图中的四个格。a与c互为补元,b没有补元。L1L1是有界格,a是全下界,c是全上界a与d互为补元,b与c也互为补元。L3中的a与e互为补元,b的补元是c和d,c的补元是b和d,d的补元是b和c.b,c,d每个元素都有两个补元。L2L3L2是有界格,a是全下界,d是全上界L3是有界格,其中a为全下界,e为全上界,L4中的a与e互为补元,b的补元是c和d,c的补元是b,d的补元是b。

L4是有界格,其中a为全下界,e为全上界,在任何有界格中，全下界0与全上界1互补。对于其他元素，可能存在补元，也可能不存在补元。如果存在，可能是惟一的，也可能是多个补元。对于有界分配格，如果它的元素存在补元，一定是唯一的。定理13.9设<L,∧,∨,0,1>是有界分配格。若L中元素a存在补元，则存在唯一的补元。

证:假设b,c是a的补元，则有a∨c=1,a∧c=0,

又知b是a的补元，故a∨b=1,a∧b=0

从而得到a∨c=a∨b,a∧c=a∧b,由于L是分配格，根据定理13.7，b=c.定义13.11设<L,∧,∨,0,1>是有界格,若L中所有元素都有补元存在，则称L为有补格。

例如，图13.5中:

L2,L3和L4是有补格，L1不是有补格。

图13.6中L2和L3是有补格，L1不是有补格。1.判别下述格L是否为分配格。求出每个格的补元。说明它们是否为有补格。

L1

L2

不是分配格它含有与钻石格同构的子格{a,b,c,d,e}。含有与五角格同构的子格不是分配格a与h互为补元，其它元素没有补元。a与g互为补元；b的补元为c,d,f；c的补元为b,d,e,f;d的补元为b,c,e；e的补元为c,d,f；f的补元为b,c,e。是有补格不是有补格。

L3含有与五角格同构的子格{a,b,g,h,d}不是分配格a与h互为补元，b的补元为d；c的补元为d；d的补元为b,c,g；g的补元为d。是有补格13.4布尔代数1．布尔代数作为格的定义及实例定义13.12如果一个格是有补分配格,则称它为布尔格或布尔代数。根据定理13.9,在分配格中,如果一个元素存在补元,则是唯一的。

因此,在布尔代数中,每个元素都存在着唯一的补元,可以把求补元的运算看作是布尔代数中的一元运算。

从而可以把一个布尔代数标记为<B,∧,∨,＇,0,1>,其中∧,∨,0,1和有界格一样,＇为求补运算,

a∈B,a＇是a的补元。例13.11

设S110={1,2,5,10,11,22,55,110}是110的正因子集合。令gcd,lcm分别表示求最大公约数和最小公倍数的运算。问<S110,gcd,lcm>是否构成布尔代数？为什么？解:容易验证

x,y∈S110有gcd(x,y)∈S110和lcm(x,y)∈S110.且

x,y,z∈S110有gcd(x,y)=gcd(y,x)

lcm(x,y)=lcm(y,x)交换律结合律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>构成格。先证明它是格。下面证明它是分配格。

易验证

x,y,z∈S110有

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

1和110互为补元,2和55互为补元,

5和22互为补元,10和11互为补元,最后证明它是有补格。从而证明了<S110,gcd,lcm>为布尔代数。例13.12设B为任意集合,证明B的幂集格<P(B),∩,∪,~,

,B>构成布尔代数,称为集合代数。证:因为∩和∪运算满足交换律,结合律和吸收律,所以P(B)关于∩和∪构成格由于∩和∪互相可分配,因此P(B)是分配格,且全下界是空集

,全上界是B.根据绝对补的定义,取全集为B,

x∈P(B),~x是x的补元。从而证明P(B)是有补分配格,即布尔代数。

所以P(B)是有补格2.布尔代数的性质定理13.10设<B,∧,∨,＇,0,1>是布尔代数,则

(1)

a∈B,

(a＇)＇=a.

(2)

a,b∈B,

(a∧b)＇=a＇∨b＇,(a∨b)＇=a＇∧b＇证:(1)(a‘)’是a‘的补元。a也是a’的补元。由补元的唯一性得(a＇)＇=a.(2)对任意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的补元,根据补元的唯一性有

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

同理可证(a∨b)＇=a＇∧b＇.(1)称为双重否定律,(2)称为德摩根律。3.布尔代数作为代数系统的定义

定义13.13设<B,*,

>是代数系统,*和

是二元运算。若*和

运算满足：(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)补元律,即

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

a＇=1则称<B,*,

>是一个布尔代数。同一律就是指运算含有单位元的性质，这里的1是*运算的单位元,0是

运算的单位元。可以证明这个定义与有补分配格的定义是等价的。例13.11

设S110={1,2,5,10,11,22,55,110}是110的正因子集合。令gcd,lcm分别表示求最大公约数和最小公倍数的运算。问<S110,gcd,lcm>是否构成布尔代数？为什么？例13.12设B为任意集合,证明B的幂集格<P(B),∩,∪,~,

,B>构成布尔代数,称为集合代数。解：只需验证gcd,lcm运算是否满足：交换律、分配律、同一律和补元律。解：只需验证∩,∪运算是否满足：交换律、分配律、同一律和补元律。二．布尔代数的子代数及实例

定义13.14设<B,∧,∨,‘,0,1>是布尔代数,S是B的非空子集,若0,1∈S,且S对∧,∨和‘运算都是封闭的,则称S是B的子布尔代数。例13.13设<B,∧,∨,＇,0,1>是布尔代数,a,b∈B,且a

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

x

b}

称S为B中的区间,可简记为[a,b].证明[a,b]是一个布尔代数。证明:S为B的非空子集,且a,b分别为S的全上界和全下界.对任意的x,y∈S,都有ax∧yb和ax∨yb这说明S关于∧和∨运算是封闭的.易见∧和∨运算在S上适合交换律和分配律.对任意的x∈S,都有x∨a=x,x∧b=x,满足同一律对任意的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)(补元律)=x∨b(交换律,同一律)=x∨a∨(x＇∧b)(由ab)=x∨(x＇∧b)(由ax)=b(由xb)下面证明y是x的补元x∧y=x∧((a∨x＇)∧b)=(x∧a)∨(x∧x＇)(分配律)=(x∧a)∨0(补元律)=a(由ax)=x∧(a∨x＇)(由xb)=x∧a(同一律)由定义<S,∧,∨>构成一布尔代数,其全下界为a,全上界为b,对任意的x∈S,x关于这个全上界和全下界的补元是(a∨x＇)∧b当a=0且b=1时,这时S是B的子布尔代数.但当a≠0或b≠1时,S不是B的子布尔代数.S满足补元律例13.14考虑110的正因子集合S110关于gcd,lcm运算构成的布尔代数。

它有以下的子布尔代数：

{1,110}

{1,2,55,110}

{1,5,22,110}

{1,10,11,110}

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

三．布尔代数的同态映射及实例定义13.15设<B1,∧,∨,＇,0,1>和<B2,∩,∪,-,θ,E>是两个布尔代数。这里的∩,∪,-泛指布尔代数B2中的求最大下界,最小上界和补元的运算。θ和E分别是B2的全下界和全上界。

f:B1→B2.如果对于任意的a,b∈B1有f(a∨b)=f(a)∪f(b)f(a∧b)=f(a)∩f(b)f(a＇)=-f(a)则称f是布尔代数B1到B2的同态映射,简称布尔代数的同态。类似于其它代数系统,也可以定义布尔代数的单同态,满同态和同构。例13.15设<B1,∧,∨,＇,0,1>和<B2,∩,∪,-,θ,E>是布尔代数。f:B1→B2.若

a,b∈B1有

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

f(a＇)=-f(a)

证明f是B1到B2的同态。证:只须证明

a,b∈B1有

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

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

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

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