离散数学格与布尔代数-课件

第11章格与布尔代数离散数学中国地质大学本科生课程第11章格与布尔代数离散数学中国地质大学本科生课程本章内容11.1 格的定义与性质11.2 分配格、有补格与布尔代数

本章总结

作业本章内容11.1 格的定义与性质211.1格的定义与性质定义11.1设<S,≤>是偏序集，如果

x,y∈S，{x,y}都有最小上界和最大下界，则称S关于偏序≤作成一个格(lattice)。说明：由于最小上界和最大下界的唯一性，可以把求{x,y}的最小上界和最大下界看成x与y的二元运算∨和∧。

x∨y：表示x与y的最小上界

x∧y：表示x和y的最大下界。

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

x,y∈Sn， x∨y是lcm(x,y)，即x与y的最小公倍数。 x∧y是gcd(x,y)，即x与y的最大公约数。 下图给出了格<S8,D>，<S6,D>和<S30,D>。格的实例例11.1设n是正整数，Sn是n的正因子的集合。D4例11.2例11.2判断下列偏序集是否构成格,并说明理由。 (1)<P(B),

>，其中P(B)是集合B的幂集。 (2)<Z,≤>，其中Z是整数集,≤为小于或等于关系。 (3)偏序集的哈斯图分别在下图给出。例11.2例11.2判断下列偏序集是否构成格,并说明理由。5例11.2解答(1)是格。

x,y∈P(B)，x∨y就是x∪y，x∧y就是x∩y。 由于∪和∩运算在P(B)上是封闭的，所以x∪y，x∩y∈P(B)。 称<P(B),

>,为B的幂集格。(2)是格。

x,y∈Z,x∨y＝max(x,y)，x∧y＝min(x,y)，它们都是整数。(3)都不是格。 (a)中的{a,b}没有最大下界。 (b)中的{b,d}有两个上界c和e,但没有最小上界。 (c)中的{b,c}有三个上界d,e,f,但没有最小上界。 (d)中的{a,g}没有最大下界。例11.2解答(1)是格。6例11.3例11.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∩H2，H1∨H2就是<H1∪H2>。例11.3例11.3设G是群，L(G)是G的所有子群的集合7对偶原理定义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 (因为a和b的交是a的一个下界) 那么对一切格L都有

a,b∈L，a∨b≥a说明 许多格的性质都是互为对偶命题的。 有了格的对偶原理，在证明格的性质时，

只须证明其中的一个命题即可。对偶原理定义11.2设f是含有格中元素以及符号＝、≤、≥、8格的运算性质定理11.1设<L,≤>是格，则运算∨和∧适合交换律、结合律、幂等律和吸收律，即 (1)交换律

a,b∈L有 a∨b＝b∨a a∧b＝b∧a (2)结合律

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格的运算性质定理11.1设<L,≤>是格，则运算∨和∧适合9定理11.1(1)a∨b和b∨a分别是{a,b}和{b,a}的最小上界。 由于{a,b}＝{b,a}，所以a∨b＝b∨a。 由对偶原理，a∧b＝b∧a得证。(2)由最小上界的定义有 (a∨b)∨c≥a∨b≥a (13.1) (a∨b)∨c≥a∨b≥b (13.2) (a∨b)∨c≥c (13.3) 由式13.2和13.3有 (a∨b)∨c≥b∨c (13.4) 再由式13.1和13.4有 (a∨b)∨c≥a∨(b∨c) 同理可证 (a∨b)∨c≤a∨(b∨c) 根据偏序关系的反对称性有 (a∨b)∨c＝a∨(b∨c) 由对偶原理，(a∧b)∧c＝a∧(b∧c)得证。定理11.1(1)a∨b和b∨a分别是{a,b}和{b,a}10定理11.1(3)显然a≤a∨a, 又由a≤a可得 a∨a≤a。 根据反对称性有 a∨a＝a， 由对偶原理，a∧a＝a得证。(4)显然 a∨(a∧b)≥a (13.5) 又由a≤a，a∧b≤a可得 a∨(a∧b)≤a (13.6) 由式13.5和13.6可得

a∨(a∧b)＝a， 根据对偶原理，a∧(a∨b)＝a得证。定理11.1(3)显然a≤a∨a,11定理11.2定理11.2设<S,*,

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

运算适合交换律、结合律、吸收律，则可以适当定义S中的偏序≤，使得<S,≤>构成一个格，且a,b∈S有a∧b＝a*b，a∨b＝a

b。思路

(1)证明在S中*和运算都适合幂等律。 (2)在S上定义二元关系R，并证明R为偏序关系。 (3)证明<S,≤>构成格。说明 通过规定运算及其基本性质可以给出格的定义。定理11.2定理11.2设<S,*,>是具有两个二元运算12定理11.2a∈S，由吸收律得(1)证明在S中*和运算都适合幂等律。a*a＝a*(a

(a*a))＝a同理有a

a＝a。(2)在S上定义二元关系R，a,b∈S有<a,b>∈Rab＝b下面证明R在S上的偏序。根据幂等律，a∈S都有a

a＝a，即<a,a>∈R，所以R在S上是自反的。

a,b∈S有aRb且bRa

a

b＝b且b

a＝aa＝ba＝ab＝b(由于ab=ba)所以R在S上是反对称的。定理11.2a∈S，由吸收律得(1)证明在S中*和运算都13定理11.2a,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.2a,b,c∈S有14定理11.2(3)证明<S，≤>构成格。即证明a∨b＝a

b，a∧b＝a*b。a,b∈S有a(ab)＝(aa)b＝abb(ab)＝a(bb)＝ab根据≤的定义有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*(ab)＝a反之由a*b＝a可知ab＝(a*b)b＝b(b*a)＝b再由式(13.7)和≤的定义有a≤ba*b＝a，依照前边的证明,类似地可证a*b是{a,b}的最大下界，即a∧b＝a*b。ab＝ba*b＝a (13.7)定理11.2(3)证明<S，≤>构成格。即证明a∨b＝a15格的等价定义根据定理11.2，可以给出格的另一个等价定义。定义11.3设<S,*,

>是代数系统，*和

是二元运算，如果*和

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

>构成一个格(lattice)。说明 格中的幂等律可以由吸收律推出。 以后我们不再区别是偏序集定义的格，

还是代数系统定义的格，而统称为格L。格的等价定义根据定理11.2，可以给出格的另一个等价定义。16格的性质定理11.3

设L是格，则

a,b∈L有 a≤b

a∧b＝a

a∨b＝b证明

先证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∈L有17格的性质定理11.4设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。格的性质定理11.4设L是格，a,b,c,d∈L，若a≤18例11.5

例11.5设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∨c 从而得到a∨(b∧c)≤(a∨b)∧(a∨c)说明 在格中分配不等式成立。 一般说来，格中的∨和∧运算并不是满足分配律的。例11.5

例11.5设L是格，证明a,b,c∈L有19本节小结偏序集构成格的条件：任意二元子集都有最大下界和最小上界。

格的实例：正整数的因子格，幂集格，子群格。格的性质：对偶原理，格中算律（交换、结合、幂等、吸收），保序性，分配不等式。

格作为代数系统的定义。格的证明方法本节小结偏序集构成格的条件：任意二元子集都有最大下界和最小上20子格定义11.4设<L,∧,∨>是格，S是L的非空子集，若S关于L中的运算∧和∨仍构成格，则称S是L的子格。例11.6设格L如右图所示。令S1＝{a,e,f,g}S2＝{a,b,e,g}则S1不是L的子格，S2是L的子格。因为对于e和f,有e∧f＝c，但c

S1。子格定义11.4设<L,∧,∨>是格，S是L的非空子集，若2111.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为分配格。说明 上面两个等式互为对偶式。 在证明L为分配格时，只须证明其中的一个等式即可。11.2分配格、有补格与布尔代数一般说来，格中运算∨对∧满22例11.7L1和L2是分配格，L3和L4不是分配格。在L3中， b∧(c∨d)＝b∧e＝b(b∧c)∨(b∧d)＝a∨a＝a在L4中, c∨(b∧d)＝c∨a＝c(c∨b)∧(c∨d)＝e∧d＝d钻石格五角格例11.7L1和L2是分配格，L3和L4不是分配格。在L3中23分配格的判别定理11.5设L是格，则L是分配格当且仅当L中不含有与钻石格或五角格同构的子格。证明 略。推论 (1)小于五元的格都是分配格。 (2)任何一条链都是分配格。分配格的判别定理11.5设L是格，则L是分配格当且仅当L中24例11.8说明下图中的格是否为分配格，为什么？L1,L2和L3都不是分配格。{a,b,c,d,e}是L1的子格，并且同构于钻石格。{a,b,c,e,f}是L2的子格，并且同构于五角格。{a,c,b,e,f}是L3的子格，也同构于钻石格。

例11.8说明下图中的格是否为分配格，为什么？L1,L2和25格的全下界和全上界定义11.6设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。格的全下界和全上界定义11.6设L是格，26有界格定义11.7设L是格，若L存在全下界和全上界，则称L为有界格，并将L记为<L,∧,∨,0,1>。说明 有限格L一定是有界格。举例设L是n元格，且L＝{a1,a2,…,an}，那么a1∧a2∧…∧an是L的全下界，而a1∨a2∨…∨an是L的全上界。因此L是有界格。对于无限格L来说，有的是有界格，有的不是有界格。如集合B的幂集格<P(B),∩,∪>，不管B是有穷集还是无穷集，它都是有界格。它的全下界是空集，全上界是B。整数集Z关于通常数的小于或等于关系构成的格不是有界格，因为不存在最小和最大的整数。有界格定义11.7设L是格，若L存在全下界和全上界，则称L27有界格的性质定理（补充）设<L,∧,∨,0,1>是有界格，则

a∈L有 a∧0＝0 a∨0＝a a∧1＝a a∨1＝1证明 由a∧0≤0和0≤a∧0可知a∧0＝0。说明 在有界格中， 全下界0是关于∧运算的零元，∨运算的单位元。 全上界1是关于∨运算的零元，∧运算的单位元。对偶原理对于涉及到有界格的命题，如果其中含有全下界0或全上界1，在求该命题的对偶命题时，必须将0替换成1，而将1替换成0。例如 a∧0＝0和a∨1＝1互为对偶命题， a∨0＝a和a∧1＝a互为对偶命题。有界格的性质定理（补充）设<L,∧,∨,0,1>是有界格，28有界格中的补元定义11.8设<L,∧,∨,0,1>是有界格，a∈L， 若存在b∈L使得

a∧b＝0和a∨b＝1 成立，则称b是a的补元。说明 若b是a的补元，那么a也是b的补元。 换句话说，a和b互为补元。有界格中的补元定义11.8设<L,∧,∨,0,1>是有界格29例11.9考虑下图中的四个格。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.9考虑下图中的四个格。L1中的a与c互为补元，其中a30有界格中补元的说明在任何有界格中，全下界0与全上界1互补。对于其他元素，可能存在补元，也可能不存在补元。如果存在，可能是唯一的，也可能是多个补元。对于有界分配格，如果它的元素存在补元，一定是唯一的。有界格中补元的说明在任何有界格中，31有界分配格中补元的唯一性定理11.6设<L,∧,∨,0,1>是有界分配格。 若a∈L，且对于a存在补元b，则b是a的唯一补元。证明 假设c∈L也是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。有界分配格中补元的唯一性定理11.6设<L,∧,∨,0,32有补格的定义定义11.9设<L,∧,∨,0,1>是有界格，若L中所有元素都有补元存在，则称L为有补格。L2,L3和L4是有补格，L1不是有补格。L2和L3是有补格，L1不是有补格。有补格的定义定义11.9设<L,∧,∨,0,1>是有界格，33本节小结如果格中一个运算对另一个运算是可分配的，称这个格是分配格。

分配格的两种判别法： 不存在与钻石格或五角格同构的子格； 对于任意元素a,b,c,有a∧b＝a∧c且a∨b＝a∨c

b＝c。

有界格的定义及其实例。

格中元素的补元及其性质（分配格中补元的唯一性）。

有补格的定义。本节小结如果格中一个运算对另一个运算是可分配的，称这个格是分34布尔代数定义11.10如果一个格是有补分配格，则称它为布尔格或布尔代数。说明 在布尔代数中，每个元素都存在着唯一的补元。 可以把求补元的运算看作是布尔代数中的一元运算。 可以把一个布尔代数标记为<B,∧,∨,＇,0,1>，

＇为求补运算,

a∈B，a＇是a的补元。布尔代数定义11.10如果一个格是有补分配格，则称它为布尔35例11.10例11.10

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

证明<S110,gcd,lcm>构成格。容易验证

x,y,z∈S110，有gcd(x,y)∈S110 lcm(x,y)∈S110gcd(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))＝xlcm(x,gcd(x,y))＝x二元运算交换律结合律吸收律例11.10例11.10

设S110＝{1,2,5,10,36例11.10证明<S110,gcd,lcm>是分配格。 易验证

x,y,z∈S110有 gcd(x,lcm(y,z))＝lcm(gcd(x,y),gcd(x,z))证明<S110,gcd,lcm>是有补格。 1为S110中的全下界 110为S110中的全上界 1和110互为补元，2和55互为补元， 5和22互为补元，10和11互为补元。综上所述，<S110,gcd,lcm>为布尔代数。例11.10证明<S110,gcd,lcm>是分配格。37例11.10（2）例11.10（2）设B为任意集合,证明B的幂集格<P(B),∩,∪,～,

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

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

x∈P(B)，～x是x的补元。 从而证明P(B)是有补分配格，即布尔代数。例11.10（2）例11.10（2）设B为任意集合,证明B38布尔代数的性质定理11.7设<B,∧,∨,′,0,1>是布尔代数，则(1)

a∈B，(a＇)＇＝a(2)

a,b∈B，(a∧b)＇＝a＇∨b＇,(a∨b)＇＝a＇∧b＇说明 (1)称为双重否定律。 (2)称为德摩根律。 命题代数与集合代数的双重否定律与德摩根律实际上

是这个定理的特例。 可以证明德摩根律对有限个元素也是正确的。证明 (1)(a′)′是a′的补元，a也是a′的补元。 由补元的唯一性得(a′)′＝a。布尔代数的性质定理11.7设<B,∧,∨,′,0,1>是布39定理11.7(2)的证明(2)

a,b∈B，(a∧b)＇＝a＇∨b＇,(a∨b)＇＝a＇∧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＇。定理11.7(2)的证明(2)a,b∈B，(a∧b)＇＝40布尔代数作为代数系统的定义定义11.11设<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,*,

>是一个布尔代数。

布尔代数作为代数系统的定义定义11.11设<B,*,>是41关于布尔代数定义的说明所谓同一律就是指运算含有单位元的性质，这里的1是*运算的单位元，0是运算

的单位元。可以证明1和0分别也是

和*运算的零元。

a∈B有 a1 ＝(a1)*1 （同一律） ＝1*(a1) （交换律） ＝(a

a′)*(a

1) （补元律） ＝a(a′*1) （分配律） ＝a

a′ （同一律） ＝1（补元律）同理可证a*0＝0。关于布尔代数定义的说明所谓同一律就是指运算含有单位元的性质，42关于布尔代数定义的说明为证明以上定义的<B,*,°>是布尔代数，只需证明它是一个格，即证明*和°运算满足结合律和吸收律。证明吸收律，

a,b∈B有

a(a*b) ＝(a*1)(a*b) （同一律） ＝a*(1b) （分配律） ＝a*1 （1是运算的零元) ＝a （同一律）同理有a*(ab)＝a。关于布尔代数定义的说明为证明以上定义的<B,*,°>是布尔代43关于布尔代数定义的说明为证结合律，先证以下命题：

a,b,c∈B，ab＝ac且ab＝acb＝c由ab＝ac且ab＝ac可得 (ab)*(ab)＝(ac)*(ac)由分配律和交换律得 (a*a)b＝(a*a)c由补元律得 0b＝0c由同一律和交换律得 b＝c关于布尔代数定义的说明为证结合律，先证以下命题：44关于布尔代数定义的说明使用这个命题，为证明(a*b)*c＝a*(b*c)，只需证明以下两个等式：(1)a((a*b)*c)＝a(a*(b*c))(2)a((a*b)*c)＝a(a*(b*c))先证明第一个等式，由吸收律有 a(a*(b*c))＝a a((a*b)*c) ＝(a(a*b))*(ac) (分配律) ＝a*(ac) (吸收律) ＝a所以(1)式成立。关于布尔代数定义的说明使用这个命题，为证明(a*b)*c＝45关于布尔代数定义的说明下面证明(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）式成立。关于布尔代数定义的说明下面证明(2)式：a((a*b)46有限布尔代数的结构定义11.12设L是格，0∈L，a∈L，若

b∈L有 0＜b≤a

b＝a 则称a是L中的原子。考虑右图中的几个格。L1的原子是a。L2的原子是a,b,c。L3的原子是a和b。若L是正整数n的全体正因子关于整除关系构成的格，则L的原子恰为n的全体质因子。若L是集合B的幂集合，则L的原子就是由B中元素构成的单元集。有限布尔代数的结构定义11.12设L是格，0∈L，a∈L，47有限布尔代数的表示定理定理11.8(有限布尔代数的表示定理)设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,y

B有

(x∧y)＝

(x)∩

(y)。有限布尔代数的表示定理定理11.8(有限布尔代数的表示定理48定理11.8证明任取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.8证明任取x,y∈B，设49定理11.8证明任取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.8证明任取x∈B，存在x∈B使得50定理11.8证明下面证明

为双射。假设

(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}于是

为满射。定理得证。定理11.8证明下面证明为双射。51例子考虑110的正因子的集合S110关于gcd,lcm运算构成的布尔代数。它的原子是2、5和11，因此原子的集合A＝{2,5,11}。幂集P(A)＝{

,{2},{5},{11},{2,5