离散数学-ch格与代数

第十一章格与布尔代数主要内容格的定义及性质分配格、有补格布尔代数11.1

格的定义与性质定义11.1

设<S,≼>是偏序集，如果x,yS，{x,y}都有最小上界和最大下界，则称S关于偏序≼作成一个格(lattice).求{x,y}最小上界和最大下界看成x

与y

的二元运算∨和∧，例1

设n是正整数，Sn是n的正因子的集合.D为整除关系，则偏序集<Sn,D>构成格.

x,y∈Sn，x∨y是lcm(x,y)，即x与y的最小公倍数.

x∧y是

(x,y)，即x与y的最大公约数.例2

判断下列偏序集是否构成格，并说明理由.<P(B),

>，其中P(B)是集合B的幂集.<Z,≤>，其中Z是整数集，≤为小于或等于关系.偏序集的哈斯图分别在下图给出.实例幂集格.x,y∈P(B)，x∨y就是x∪y，x∧y就是x∩y.是格.x,y∈Z，x∨y

=max(x,y)，x∧y

=min(x,y)，都不是格.可以找到两个结点缺少最大下界或最小上界实例：子群格例3

设G是群，L(G)是G

的所有子群的集合.

即L(G)

=

{

H

|

H≤G

}，对任意的H1,H2∈L(G)，H1∩H2是G

的子群，<H1∪H2>是由H1∪H2生成的子群（即包含着H1∪H2的最小子群）.在L(G)上定义包含关系，则L(G)关于包含关系构成一个格，称为G的子群格.在L(G)中，H1∧H2

就是H1∩H2H1∨H2

就是<H1∪H2>格的性质：对偶原理定义11.2

设

f是含有格中元素以及符号=,≼,≽,∨和∧题.令f*是将f

中的≼替换成≽,≽替换成≼,∨替换成∧,∧替换成∨所得到 题.

称

f*为

f

的对偶命题.格例的如,对在偶格原中理令

f是

(a∨b)∧c≼c,

f*是

(a∧b)∨c≽c

.设

f

是含有格中元素以及符号=,≼,≽,∨和∧等

题.

若

f

对一切格为真,则f

的对偶命题f*也对一切格为真.例如,如果对一切格L都有a,b∈L,a∧b≼a，那么对一切格L都有a,b∈L,a∨b≽a注意：对偶是相互的，即(f*)*=

f格的性质：算律定理11.1

设<L,≼>是格,则运算∨和∧适合交换律、结合律、幂等律和吸收律,即a,b∈L

有a∨b

=

b∨a,

a∧b

=

b∧aa,b,c∈L

有(a∨b)∨c

=

a∨(b∨c), (a∧b)∧c

=

a∧(b∧c)a∈L

有a∨a

=

a,

a∧a

=aa,b∈L

有a∨(a∧b)

=

a,

a∧(a∨b)

=

a证明(1)

a∨b是{

a,

b

}的最小上界,

b∨a是{b,

a

}的最小上界.

由于{a,b

}={b,a

},所以a∨b

=b∨a.由对偶原理,a∧b

=b∧a.(2)

由最小上界的定义有(a∨b)∨c≽a∨b≽a(a∨b)∨c≽a∨b≽b(a∨b)∨c≽c(1)(2)(3)(4)由式(2)和(3)有由式(1)和(4)有同理可证(a∨b)∨c≽b∨c(a∨b)∨c≽a∨(b∨c)(a∨b)∨c≼a∨(b∨c)(a∨b)∨c

=

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

=

a∧(b∧c)由对偶原理,证明称性(3)

显然

a

≼

a∨a,

又由

a

≼

a

可得

a∨a

≼a.

根据有a∨a

=

a

.

由对偶原理,

a∧a

=

a

得证.(4)

显然由a

≼a,a∧b

≼a

可得a∨(a∧b)≽

a(5)由式(5)和(6)

可得a∨(a∧b)

≼aa∨(a∧b)

=

a,(6)根据对偶原理,a∧(a∨b)

=

a格的性质：序与运算的关系定理11.2

设L是格,

则a,b∈L有a

≼

b

a∧b

=

a

a∨b

=

b证(1)

先证a

≼b

a∧b=a由a

≼a

和a

≼b

可知a

是{a,b

}的下界,故a

≼a∧b.显然有a∧b

≼

a.

由

称性得

a∧b=

a.再证a∧b

=a

a∨b

=b根据吸收律有b

=b∨(b∧a)由a∧b

=a

和上面的等式得b=b∨a,即a∨b

=b.最后证a∨b

=b

a≼b由a

≼a∨b

得a

≼a∨b

=b格的性质：保序定理11.3

设L是格,

a,b,c,d∈L，若a

≼

b

且

c

≼

d,

则a∧c

≼

b∧d,

a∨c≼

b∨d证

a∧c

≼

a

≼

b,

a∧c

≼

c

≼

d因此a∧c≼b∧d.同理可证a∨c

≼b∨d例4

设L是格,

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

≼

(a∨b)∧(a∨c).证

由

a≼

a,

b∧c

≼

b

得

a∨(b∧c)

≼

a∨b由a

≼a,b∧c

≼c

得a∨(b∧c)≼a∨ca∨(b∧c)

≼

(a∨b)∧(a∨c)注意：一般说来,格中的∨和∧运算不满足分配律.格作为代数系统的定义定理11.4

设<S,∗,◦>是具有两个二元运算的代数系统,

若对于∗和◦运算适合交换律、结合律、吸收律,则可以适当定义S中的偏序≼,使得<S,≼>构成格,且a,b∈S

有a∧b

=

a∗b,

a∨b

=a◦b.思路证明在S中*和运算都适合幂等律。在S上定义二元关系R，并证明R为偏序关系。证明<S,≤>构成格。定理11.4的证明证明在S中*和运算都适合幂等律。a∈S，由吸收律得

a*a

＝

a*(a(a*a))

＝

a同理有a◦a＝a。在S上定义二元关系R，

a,b∈S

有

<a,b>∈R

ab＝b下面证明R在S上的偏序。根据幂等律，a∈S都有aa＝a，即<a,a>∈R，所以R在S上是自反的。a,b∈S

有aRb且bRa(由于a

b=ba)所以R在S上是

ab＝b且ba＝a

a＝ba＝ab＝b称的。定理11.4的证明a,b,c∈S

如果

aRb且bRc

ab＝b

且bc＝c

ac＝a(bc)

ac＝(ab)c

ac＝bc＝c

aRc这就证明了R在S上是传递的。综上所述，R为S上的偏序。以下把R记作≤。定理11.4的证明(3)

证明<S，≤>构成格。即证明a∨b＝ab，a∧b＝a*b

。a,b∈S有a(ab)＝(aa)b＝abb(ab)＝a(bb)＝ab首先由ab＝b

可知反之由a*b＝a

可知a*b

＝a*(ab)＝aab

＝(a*b)b

＝b(b*a)＝b根据≤的定义有a≤ab和b≤ab，

所以ab是{a,b}的上界。假设

c为{a,b}的上界，

则有ac＝c和bc＝c，从而有(ab)c

＝

a(bc)

＝

ac

＝

c这就证明了ab≤c，所以ab是{a,b}的最小上界，即

a∨b＝ab为证a*b是{a,b}的最大下界，先证ab＝b

a*b＝a由≤的定义有

a≤b

a*b＝a，类似地可证a*b是{a,b}的最大下界，即a∧b＝a*b。格作为代数系统的定义根据定理11.4,

可以给出格的另一个等价定义.定义11.3

设<S,

∗,

◦

>是代数系统,

∗和◦是二元运算,

如果∗和◦满

换律、结合律和吸收律,

则<S,

∗,◦>构成格.及其判别法定义11.4

设<L,∧,∨>是格,

S是L的非空子集,

若S关于L中的运算∧和∨仍构成格,则称S是L的

..令例5

设格LS1={a,

e,

f,

g},S2={a,

b,

e,

g}S1不是L的

,

因为e,

fS1

但e∧f

=

cS1.S2是L的

.11.2

分配格、有补格与布尔代数一般说来，格中运算∨对∧满足分配不等式，即a,b,c∈L，有a∨(b∧c)≤(a∨b)∧(a∨c)但是不一定满足分配律。满足分配律的格称为分配格。定义11.5

设<L,∧,∨>是格,

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

=

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

=(a∨b)∧(a∨c)则称L为分配格.注意：可以证明以上两个条件互为充分必要条件L1

和L2

是分配格,L3和L4不是分配格.称L3为钻石格,L4为五角格.实例在L3中，b∧(c∨d)

＝b∧e＝b(b∧c)∨(b∧d)＝a∨a＝ac∨(b∧d)

＝c∨a＝c(c∨b)∧(c∨d)＝e∧d＝d在L4中,分配格的判别及性质分配格的判定定理11.5(1)设L是格,则L是分配格当且仅当L不含有与钻石格或五角格同构的

.证明省略.推论(1)

小于五元的格都是分配格.(2)

任何一条链都是分配格.例6

说明图中的格是否为分配格,

为什么？解

都不是分配格.{

a,b,c,d,e

}是L1的

,同构于钻石格{

a,b,c,e,f

}是L2的

,同构于五角格；{a,c,b,e,f

}是L3的同构于钻石格.分配格的判定定理11.5(2)格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(吸收律,交换律)(已知条件代入)(分配律)(已知条件代入,交换律)(分配律)(已知条件代入)(交换律,吸收律)定理11.5充分性假若a,b,c∈L，有a∧b＝a∧c且a∨b＝a∨c

b＝c成立，而L不是分配格。根据定理11.5(1)，L中必含有与钻石格或五角格同构的。为{u,v,x,y,z}，其假设L中含有与钻石格同构的

，且该中u为它的最小元，v为它的最大元。从而推出x∧y＝x∧z＝u，x∨y＝x∨z＝v但y≠z，与已知

。对五角格的情况同理可证。vuxy

z有界格的定义定义11.6

设L是格,若存在a∈L使得x∈L有a

≼x,则称a为L的全下界若存在b∈L使得x∈L有x

≼b,则称b为L的全上界说明：格L若存在全下界或全上界,一定是惟一的.一般将格L的全下界记为0,全上界记为1.定义11.7

设L是格,若L存在全下界和全上界,则称L

为有界格,一般将有界格L记为<L,∧,∨,0,1>.定理11.6

设<L,∧,∨,0,1>是有界格,

则a∈L有a∧0

=0,

a∨0

=a,

a∧1

=

a,

a∨1=1注意：有限格L={a1,a2,…,an}是有界格,a1∧a2∧…∧an是L的全下界,

a1∨a2∨…∨an是L的全上界.0是关于∧运算的零元,∨运算的单位元；1是关于∨运算的零元,∧运算的单位元.对于涉及到有界格 题,如果其中含有全下界0或全上界1,在求该命题的对偶命题时,

必须将0替换成1,

而将1替换成0.

对于无限格L来说，有的是有界格，有的不是有界格。如集合B的幂集格<P(B),∩,∪>，不管B是有穷集还是无穷集，它都是有界格。它的全下界是空集，全上界是B。整数集Z关于通常数的小于或等于关系构成的格不是有界格，因为不存在最小和最大的整数。有界格的性质有界格中的补元及实例定义11.8

设<L,∧,∨,0,1>是有界格,

a∈L,

若存在b∈L

使得a∧b

=0

和a∨b=1成立,则称b是a的补元.注意：若b是a的补元,那么a也是b的补元.a和b互为补元.例7

考虑下图中的格.

针对不同的元素，求出所有的补元.解答L1中a

与c互为补元,其中a

为全下界,c为全上界,b

没有补元.L2中a

与d

互为补元,其中a

为全下界,d

为全上界,b与c也互为补元.L3中a

与e

互为补元,其中a

为全下界,e为全上界,b

的补元是c

和

d;

c

的补元是

b

和

d

;

d

的补元是

b

和

c

;b,c,

d

每个元素都有两个补元.L4中a

与e

互为补元,其中a

为全下界,e

为全上界,b

的补元是c

和

d;

c

的补元是

b

;

d

的补元是

b

.有界分配格的补元惟一性定理11.7

设<L,∧,∨,0,1>是有界分配格.

若L中元素

a

存在补元,

则存在惟一的补元.证假设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是分配格,

b

=

c.注意：在任何有界格中,全下界0与全上界1互补.对于一般元素,可能存在补元,也可能不存在补元.如果存在补元,可能是惟一的,也可能是多个补元.对于有界分配格,如果元素存在补元,一定是惟一的.有补格的定义定义11.9

设<L,∧,∨,0,1>是有界格,

若L中所有元素都有补元存在,

则称L为有补格.例如,图中的L2,L3和L4是有补格,L1不是有补格.布尔代数的定义与实例定义11.10

如果一个格是有补分配格,则称它为布尔格或布尔代数.

布尔代数标记为<B,∧,∨,,

0,

1>,

为求补运算.例8

设

S110

=

{1,

2,

5,

10,

11,

22,

55,

110}是110的正因子集合，表示求最大公约数的运算，lcm表示求最小公倍数的运算，问<S110, ,

lcm>是否构成布尔代数？为什么？解

(1)

不难验证S110关于

和lcm

运算构成格.

(略)验证分配律x,y,z∈S110

有(x,

lcm(y,

z))

=lcm( (x,

y), (x,z))验证它是有补格, 1作为S110中的全下界,

110为全上界,

1和110互为补元,

2和55互为补元,

5和22互为补元,

10和11互为补元,

从而证明了<S110, ,

lcm>为布尔代数.实例例9

设B为任意集合,

证明B的幂集格<P(B),

∩,∪,

~,

,

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

根据绝对补的定义,取全集为B,

x∈P(B),~x是x的补元.从而证明P(B)是有补分配格,即布尔代数.布尔代数的性质定理11.8

设<B,∧,∨,,0,

1>是布尔代数,则a∈B,

(a)

=a.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

=

0a∨b是a∧b的补元,根据补元惟一性有(a∧b)

=a∨b,同理可证(a∨b)

=a∧b.注意：德 律对有限个元素也是正确的.布尔代数作为代数系统的定义定义11.11设<B,∗,◦>是代数系统,∗和◦是二元运算.若∗和◦运算满足：交换律,

即a,b∈B a∗b

=b∗a,

a◦b

=

b◦a分配律,即a,b,c∈Ba∗(b◦c)

=(a∗b)◦(a∗c),

a◦(b∗c)

=

(a◦b)

∗

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

∗1=a,a◦0=a补元律,即a∈B,存在a∈B

使得a

∗a

=0,

a◦a

=1则称<B,∗,◦>是一个布尔代数.可以证明，布尔代数的两种定义是等价的.关于布尔代数定义的说明所谓同一律就是指运算含有单位元的性质，这里的1是*运算的单位元，0是运算的单位元。可以证明1和0分别也是和*运算的零元。

a∈B有a1

＝

(a1)*1＝

1*(a1)＝

(aa′)*(a1)（同一律）（交换律）（补元律）（分配律）（同一律）（补元律）＝

a(a′*1)＝

aa′＝

1同理可证a*0＝0。关于布尔代数定义的说明为证明以上定义的<B,*,°>是布尔代数，只需证明它是一个格，即证明*和°运算满足结合律和吸收律。证明吸收律，a,b∈B有a(a*b)＝

(a*1)(a*b)＝

a*(1b)＝

a*1（同一律）（分配律）（1是运算的零元)＝

a（同一律）同理有a*(ab)＝a。关于布尔代数定义的说明为证结合律，先证以下命题：a,b,c∈B，ab＝ac

且ab＝ac

b＝c由ab＝ac

且ab＝ac

可得(ab)*(ab)＝(ac)*(ac)由分配律和交换律得(a*a)b＝(a*a)c由补元律得0b＝0c由同一律和交换律得b＝c关于布尔代数定义的说明使用这个命题，为证明(a*b)*c＝a*(b*c)，只需证明以下两个等式：a((a*b)*c)＝a(a*(b*c))a((a*b)*c)＝a(a*(b*c))先证明第一个等式，由吸收律有a(a*(b*c))＝aa((a*b)*c)(分配律)(吸收律)＝

(a(a*b))*(ac)＝

a*(ac)＝

a所以(1)式成立。关于布尔代数定义的说明下面证明(2)式：a((a*b)*c)＝a(a*(b*c))a(a*(b*c))(分配律)(交换律,补元律)(交换律,同一律)＝

(aa)*(a(b*c))＝

1*(a(b*c))＝

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

(a(a*b))*(ac)(分配律)＝

((aa)*(ab))*(ac)＝

(1*(ab))*(ac)(分配律)(交换律,补元律)(交换律,同一律)(分配律)＝

(ab)*(ac)＝

a(b*c)所以（2）式成立。布尔代数的子代数定义设<B,∧,∨,,0,1>是布尔代数，S是B的非空子集，若

0,1∈S，且S对∧,∨和运算都是封闭的，则称S是B的子布尔代数。例11.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都有a≤x≤b，从而有

a≤x∧y≤b,a≤y≤ba≤x∨y≤bS关于∧和∨运算是封闭的。易见∧和∨运算在S上适合交换律和分配律。例11.13对任意的

x∈S，

令

y＝(a∨x)∧b (下面证明y为x得补元。)由于

a≤a∨x，a≤b，故

a≤(a∨x)∧b。同时(a∨x)∧b≤b，因此y∈S。又x∨y

＝x∨((a∨x)∧b)＝x∨((a∧b)∨(x∧b))(分配律)＝x∨a∨(x∧b)(a＜b)＝x∨(x∧b)(a≤x)＝(x∨x)∧(x∨b)(分配律)＝1∧(x∨b)(补元律)＝x∨b(交换律，同一律)＝b(x≤b)例11.13x∧y

＝

x∧((a∨x)∧b)＝

x∧(a∨x)＝

(x∧a)∨(x∧x)＝

(x∧a)∨0＝

x∧a＝

a(x≤b,交换律)(分配律)(补元律)(同一律)(a≤x)根据定义，<S,∧,∨>构成布尔代数。其全上界是a，全下界是b。x∈[a,b]，x关于这个全上界和全下界的补元是(a∨x)∧b。当a＝0且b＝1时，[a,b]是B的子布尔代数。但当a≠0或b≠1时，[a,b]不是B的子布尔代数。例考虑110的正因子集合S110关于,lcm运算构成的布尔代数。它有以下的子布尔代数：{1,110}{1,2,55,110}{1,5,22,110}{1,10,11,110}{1,2,5,10,11,22,55,110}有限布尔代数的结构定义11.12

设L

是格,0∈L,若b∈L有0

≺b

≼a

b

=a,

则称a

是L

中的原子.实例：(1)

L是正整数

n的全体正因子关于整除关系构成的格,

则L的原子恰为n的全体素因子.若L是B的幂集,则L的原子就是B中元素构成的单元集图中L1的原子是?,L2的原子是?,L3的原子是?引理１引理1

设Ｌ是格，a,b是Ｌ中的原子，若a≠b，则a∧b＝0。证明

假设a∧b≠0，则有0＜a∧b≤a

和0＜a∧b≤b由于a,b是原子，则有

a∧b＝a

和

a∧b＝b，从而有a＝b，与已知

。引理２引理２

设B是有限的布尔代数，x∈B，x≠0，令T(x)＝{a1,a2,…,an}是B中所有小于或等于x的原子构成的集合，则x＝a1∨a2∨…∨an称这个表示式为x的原子表示，且是唯一的表示。这里的唯一性是指：若x＝a1∨a2∨…∨an，x＝b1∨b2∨…∨bn都是x的原子表示，则有{a1,a2,…an}＝{b1,b2,…bn}引理2的证明令y＝a1∨a2∨…∨an。由于ai≤x，i＝1,2,…n，所以必有y≤x。现证明x∧y＝0。假如x∧y≠0，则存在B中元素t1,t2,…,ts，使得t1覆盖0，t2覆盖t1，…，ts覆盖ts-1，且ts＝x∧y。由此可知t1是原子，且t1≤x和t1≤y。由t1≤x可知t1∈T(x)。即存在ai∈T(x)，使得t1＝ai。又由t1≤y可知t1∧y＝t1，从而有t1＝t1∧y＝ai∧y

＝ai∧(a1∨a2∨…∨an)＝ai∧(a1∧a2∧…∧ai∧…∧an)＝(ai∧ai)∧(a1∧…∧ai-1∧ai+1∧…∧an)＝0∧a1∧…∧ai-1∧ai+1∧…∧an＝0这与t1覆盖0

。从而证明了x∧y＝0。引理２由

y＝y∨0

＝y∨(x∧y)＝(y∨x)∧(y∨y)＝(y∨x)∧1＝y∨x可知

x≤y。

综合上述得x＝y，

即x＝a1∨a2∨…∨an。设x＝b1∨b2∨…∨bm是x的另一个原子表示，任取ai∈{a1,a2,…,an}，假若ai{b1,b2,…,bm}。由引理1必有ai∧bj＝0，j＝1,2,…m。又由于ai≤x，于是ai＝ai∧x＝ai∧(b1∨b2∨…∨bn)＝(ai∧b1)∨(ai∧b2)∨…∨(ai∧bm)＝0∨0∨…∨0＝0这与ai是原子。从而证明了ai∈{b1,b2,…,bm}。同理可证，bj∈{b1,b2,…,bm}，必有bj∈{a1,a2,…,an}，于是{a1,a2,…,an}＝{b1,b2,…,bm}。有限布尔代数的表示定理定理11.9(有限布尔代数的表示定理)设B是有限布尔代数，A是B的全体原子构成的集合，则B同构于A的幂集代数P(A)。证明

任取x∈B，令T(x)＝{a|a∈B,a是原子且a≤x}则T(x)A，定义函数：B→P(A)，(x)＝T(x)，x∈B。下面证明是B到P(A)的同构任取x,y∈B，b

有b∈T(x∧y)

b∈A

且b≤x∧y

(b∈A且b≤x)且(b∈A且b≤y)

b∈T(x)且b∈T(y)

b∈T(x)∩T(y)从而有T(x∧y)＝T(x)∩T(y)，即x,yB

有(x∧y)＝(x)∩(y)。定理11.11证明任取x,y∈B，设x＝a1∨a2∨…∨an，y＝b1∨b2∨…∨bm是x,y的原子表示，则x∨y＝a1∨a2∨…∨an∨b1∨b2∨…∨bm由引理2可知T(x∨y)＝{a1,a2,…,an,b1,b2,…

,bm}又由于T(x)＝{a1,a2,

…,an}，T(y)＝{b1,b2,…

,bm}所以

T(x∨y)＝T(x)∪T(y)即

(x∨y)＝(x)∪(y)定理11.11证明任取x∈B，存在x∈B

使得x∨x＝1，

x∧x＝0因此有(x)∪(x)＝(x∨x)＝(1)＝A(x)∩(x)＝(x∧x)＝(0)＝而和A分别为P(A)的全下界和全上界，因此(x)是(x)在P(A)中的补元，即(x)＝〜(x)综上所述，是B到P(A)的同态

。定理11.11证明下面证明为双射。假设(x)＝(y)，则有T(x)＝T(y)＝{a1,a2,…,an}由引理2可知x＝a1∨a2∨…∨an＝y于是为单射。任取{b1,b2,…,bm}∈P(A)，令x＝b1∨b2∨…∨bm

，则(x)＝T(x)＝{b1,b2,…

,bm}于是为满射。定理得证。例子考虑110的正因子的集合S110关于

,

lcm运算构成的布尔代数。它的原子是2、5和11，因此原子的集合A＝{2,5,11}。幂集P(A)＝{,{2},{5},{11},{2,5},{2,11},{5,11},{2,5,11}}。幂集代数是<P(A),∩,∪,∽,,A>。只要令

:

S110→P(A)，(1)＝，

(2)＝{2}，

(5)＝{5}，(11)＝{11}，

(10)＝{2,5}，

(22)＝{2,11}，(55)＝{5,11},

(110)＝A，那么f就是定理13.11中从S110到幂集P(A)的同构

。推论推论1

任何有限布尔代数的基数为2n,

n∈N.证

设B是有限布尔代数,

A是B的所有原子构成的集合,且

|A|

=n,

n∈N.

由定理得

B

P(A),

而

|P(A)|

=2n,

所以|B|

=

2n.推论2

任何等势的有限布尔代数都是同构的.

(证明省略)结论：有限布尔代数的基数都是2的幂,对于任何自然数n,仅存在一个2n元的布尔代数.实例下图给出了1

元,2

元,4

元和8

元的布尔代数.第十一章习题课主要内容格的两个等价定义格的性质特殊格：分配格、有界格、有补格、布尔代数基本要求能够判别给定偏序集或者代数系统是否构成格能够确定一个命题的对偶命题能够证明格中的等式和不等式能判别格L的子集S是否构成能够判别给定的格是否为分配格、有补格能够判别布尔代数并证明布尔代数中的等式1．(1)证明格中练题,即(a∧b)∨b

=b(2)

证明(a∧b)∨(c∧d)≼(a∨c)∧(b∨d)(1)

(a∧b)∨b是a∧b与b的最小上界,根据最小上界的定义有(a∧b)∨b≽b

.b是a∧b与b的上界,故有(a∧b)∨b≼b.由于偏序的

称性,

等式得证.(2)

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)2．求图中格的所有

.1元2元3元4元5元：{

a

},{

b

},{

c

},{

d

},{

e

}；：{

a,b

},{

a,

c

},{

a,

d},{

a,

e

},{

b,

c

},{

b,

d},{

b,

e

},{

c,

e

},{

d,

e

}；：{

a,

b,

c

},{

a,

b,

d

},{

a,b,

e

},{

a,c,

e

},{

a,

d,

e

},{

b,

c,

e

},{

b,d,e

}；：{

a,b,

c,e

},{

a,b,

d,e

},{

b,c,

d,e

}；：

{

a,b,c,d,e

}练习2eabcd3．判别下述格L是否为分配格.L1

L2

L3L1不是分配格,

因为它含有与钻石格同构的

.L2和L3不是分配格,

因为它们含有与五角格同构的

.练习3L1

L2

L3L1中,a与h互为补元,其他元素没补元.L2中,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与h互为补元,

b的补元为d；c的补元为d；d的补元为b,c,

g；g的补元为d.

L2