《离散数学：13格与布尔代数》由会员分享，可在线阅读，更多相关《离散数学：13格与布尔代数（84页珍藏版）》请在金锄头文库上搜索。
1、第第1313章章 格与布尔代数格与布尔代数离离 散散 数数 学学大学本科生课程大学本科生课程计算机系计算机系计算机系计算机系本章内容本章内容本章内容本章内容13.1 13.1 格的定义与性质格的定义与性质13.2 13.2 子格与格同态子格与格同态13.3 13.3 分配格与有补格分配格与有补格13.4 13.4 布尔代数布尔代数本章总结本章总结作业作业13.1 13.1 13.1 13.1 格的定义与性质格的定义与性质格的定义与性质格的定义与性质 定义定义13.113.1 设设S, 是偏序集，是偏序集，如果如果 x, ,yS S， x, ,y 都有最小都有最小上界和最大下界上界和最大下界，则
2、称，则称S S关于偏序关于偏序作成一个作成一个格格( (lattice) )。说明：说明：由于最小上界和最大下界的唯一性，可以把求由于最小上界和最大下界的唯一性，可以把求 x, ,y 的最的最小上界和最大下界看成小上界和最大下界看成x x与与y y的二元运算的二元运算和和。xy：表示表示x x与与y y的最小上界的最小上界xy：表示表示x x和和y y的最大下界。的最大下界。 本章出现的本章出现的和和符号只代表格中的运算，而不再有其它的符号只代表格中的运算，而不再有其它的含义。含义。格的格的格的格的实实例例例例例例13.113.1 设n n是正整数，是正整数，S Sn n是是n n的正因子的集
3、合。的正因子的集合。D D为整除关系，整除关系，则偏序集偏序集 ,D构成格。构成格。 x,yx,yS Sn n，x xy y是是lcm(x,y)lcm(x,y)，即即x x与与y y的最小公倍数。的最小公倍数。x xy y是是gcdgcd(x,y)(x,y)，即即x x与与y y的最大公的最大公约数。数。下下图给出了格出了格S,D，S,D和和S,D。例例例例13.213.213.213.2例例13.213.2 判断下列偏序集是否构成格判断下列偏序集是否构成格, ,并说明理由。并说明理由。( (1) P(B),1) ，其中其中P(B)P(B)是集合是集合B B的幂集。的幂集。( (2) Z,2)
4、 ，其中其中Z Z是整数集是整数集, ,为小于或等于关系。为小于或等于关系。( (3) 3) 偏序集的哈斯图分别在下图给出。偏序集的哈斯图分别在下图给出。例例例例13.213.213.213.2解答解答 (1)(1)是格。是格。 x,yx,yP(B)P(B)，x xy y就是就是x xy y，x xy y就是就是x xy y。由于由于和和运算在运算在P(B)P(B)上是封闭的，所以上是封闭的，所以x xy y，x xy yP(B)P(B)。称称P(B), ,为为B B的的幂集格幂集格。( (2)2)是格。是格。 x,yx,yZ,xZ,xy ymax(x,y)max(x,y)，x xy ymin
5、(x,y)min(x,y)，它们都是整数。它们都是整数。( (3)3)都不是格。都不是格。( (a)a)中的中的a,ba,b没有最大下界。没有最大下界。( (b)b)中的中的b,db,d有两个上界有两个上界c c和和e,e,但没有最小上界。但没有最小上界。( (c)c)中的中的b,cb,c有三个上界有三个上界d,e,f,d,e,f,但没有最小上界。但没有最小上界。( (d)d)中的中的a,ga,g没有最大下界。没有最大下界。例例例例13.313.313.313.3例例13.3 13.3 设设G G是群，是群，L(G)L(G)是是G G的所有子群的集合。即的所有子群的集合。即L(G)L(G) H
6、|H H|HG G 对任意的对任意的H H1 1,H,H2 2L(G)L(G)，H H1 1H H2 2也是也是G G的子群，而的子群，而H 是由是由H H1 1H H2 2生成的子群（即包含着生成的子群（即包含着H H1 1H H2 2的最小的子群）。的最小的子群）。在在L(G)L(G)上定义包含关系上定义包含关系 ，则，则L(G)L(G)关于包含关系构成一个格，关于包含关系构成一个格，称为称为G G的的子群格子群格。易见在易见在L(G)L(G)中，中，H H1 1H H2 2就是就是H H1 1H H2 2，H H1 1H H2 2就是就是H 。 对对偶原理偶原理偶原理偶原理定定义13.2
7、13.2 设f f是含有格中元素以及符号、是含有格中元素以及符号、和和的的命命题。令。令f f* *是将是将f f中的中的替替换成成，替替换成成，替替换成成，替替换成成所得到的命所得到的命题。称。称f f* *为f f的的对偶命偶命题。例如例如 在格中令在格中令f f是是(ab)cc(ab)cc，则f f* *是是( (ab)ccab)cc。格的格的对偶原理偶原理 设f f是含有格中元素以及符号、是含有格中元素以及符号、和和的命的命题。若。若f f对一切格一切格为真，真，则f f的的对偶命偶命题f f* *也也对一切格一切格为真。真。例如例如 对一切格一切格L L都有都有 a,bLa,bL，a
8、baba a( (因因为a a和和b b的交是的交是a a的一个下界的一个下界) )那么那么对一切格一切格L L都有都有 a,bLa,bL，ababa a说明明许多格的性多格的性质都是互都是互为对偶命偶命题的。的。有了格的有了格的对偶原理，在偶原理，在证明格的性明格的性质时，只只须证明其中的一个命明其中的一个命题即可。即可。格的运算性质格的运算性质格的运算性质格的运算性质定理定理13.113.1 设设L, 是格，则运算是格，则运算和和适合适合交换律交换律、结合结合律律、幂等律幂等律和和吸收律吸收律，即，即( (1)1)交换律交换律 a,bL a,bL 有有ababbabaababbaba(2)
9、(2)结合律结合律 a,b,cL a,b,cL 有有( (ab)cab)ca(bc)a(bc)(ab)c(ab)ca(bc)a(bc)(3)(3)幂等律幂等律 aL aL 有有aaaaa aaaaaa a(4)(4)吸收律吸收律 a,bL a,bL 有有a(ab)a(ab)a aa(ab)a(ab)a a定理定理定理定理13.113.113.113.1(1)ab(1)ab和和baba分别是分别是a,ba,b和和b,ab,a的最小上界。的最小上界。由于由于a,ba,bb,ab,a，所以所以ababbaba。由对偶原理，由对偶原理，ababbaba得证。得证。( (2)2)由最小上界的定义有由最小
10、上界的定义有( (a ab)b)cca abba a (13.1)(13.1)(a(ab)b)cca abbb b (13.2)(13.2)(a(ab)b)ccc c (13.3)(13.3)由式由式13.213.2和和13.313.3有有( (a ab)b)ccb bc c(13.4)(13.4)再由式再由式13.113.1和和13.413.4有有( (a ab)b)cca a(b(bc)c)同理可证同理可证( (a ab)b)cca a(b(bc)c)根据偏序关系的反对称性有根据偏序关系的反对称性有( (a ab)b)c ca a(b(bc)c)由对偶原理，由对偶原理，( (a ab)b)
11、c ca a(b(bc)c)得证。得证。定理定理定理定理13.113.113.113.1(3)(3)显然然aaa,aaa,又由又由aaaa可得可得 aaaaaa。根据反根据反对称性有称性有 aaaaa a，由由对偶原理，偶原理，aaaaa a 得得证。( (4)4)显然然a(ab)aa(ab)a(13.5)(13.5)又由又由 aaaa，aba aba 可得可得a(ab)a a(ab)a (13.6)(13.6)由式由式13.513.5和和13.613.6可得可得 a(ab)a(ab)a a，根据根据对偶原理，偶原理，a(ab)a(ab)a a 得得证。定理定理定理定理13.213.213.2
12、13.2定理定理13.213.2 设设S,*, 是具有两个二元运算的代数系统，若对是具有两个二元运算的代数系统，若对于于* *和和 运算适合运算适合交换律交换律、结合律结合律、吸收律吸收律，则可以适当定，则可以适当定义义S S中的偏序中的偏序，使得使得S, 构成一个格，且构成一个格，且a,bSa,bS有有ababa*ba*b，ababa a b b。思路思路 (1)(1)证明证明在在S S中中* *和和 运算都适合幂等律运算都适合幂等律。(2)(2)在在S S上定义二元关系上定义二元关系R R，并证明并证明R R为偏序关系。为偏序关系。(3)(3)证明证明 S,构成格。构成格。说明说明通过规定
13、运算及其基本性质可以给出格的定义。通过规定运算及其基本性质可以给出格的定义。定理定理定理定理13.213.213.213.2 a aSS，由吸收律得由吸收律得(1)(1)证明在证明在S S中中* *和和 运算都适合幂等律运算都适合幂等律。a*aa*a a*a*( (a a (a*a)(a*a) a a同理有同理有 a a a aa a。(2)(2)在在S S上定义二元关系上定义二元关系R R， a,ba,bS S 有有 R R a a b bb b下面证明下面证明R R在在S S上的偏序。上的偏序。根据幂等律，根据幂等律， a aSS都有都有a a a aa a，即即 Ra,aR，所以所以R
14、R在在S S上是自反的。上是自反的。 a,bS a,bS 有有aRbaRb且且bRabRa a a b bb b且且b b a aa a a ab b a aa a b bb (b (由于由于a a b=bb=b a)a)所以所以R R在在S S上是反对称的。上是反对称的。定理定理定理定理13.213.213.213.2 a,b,ca,b,cSS 有有aRbaRb且且bRc bRc a a b bb b 且且 b b c cc c a a c ca a (b(b c)c) a a c c(a(a b)b) c c a a c cb b c cc c aRcaRc这就证明了这就证明了R R在在S
15、 S上是传递的。上是传递的。综上所述，综上所述，R R为为S S上的偏序。上的偏序。以下把以下把R R记作记作。定理定理定理定理13.213.213.213.2(3) (3) 证明证明 构成格。构成格。 即证明即证明ababa a b b，ababa*b a*b 。 a,ba,bSS 有有a a (a(a b)b)(a(a a)a) b ba a b bb b (a(a b)b)a a (b(b b)b)a a b b根据根据的定义有的定义有 aaaa b b和和baba b b，所以所以a a b b是是 a,ba,b的上界。的上界。假设假设 c c为为 a,ba,b的上界，的上界， 则有则
16、有a a c cc c和和b b c cc c，从而有从而有(a(a b)b) c c a a (b(b c)c) a a c c c c这就证明了这就证明了a a bcbc，所以所以a a b b是是 a,ba,b的最小上界，即的最小上界，即 a ab ba a b b为证为证a*ba*b是是 a,ba,b的最大下界，的最大下界， 先证先证首先由首先由a a b bb b 可知可知 a*b a*b a*(aa*(a b)b) a a反之由反之由a*ba*ba a 可知可知a a b b(a*b)(a*b) b b b b (b*a)(b*a)b b再由式再由式(13.7)(13.7)和和的定
17、义有的定义有 ab ab a*b a*ba a，依照前边的证明依照前边的证明, ,类似地可证类似地可证 a*ba*b是是 a,ba,b的最大下界，的最大下界， 即即 a ab ba*ba*b。a a b bb b a*b a*ba a(13.7)(13.7)格的等价定义格的等价定义格的等价定义格的等价定义根据定理根据定理13.213.2，可以给出格的另一个等价定义。，可以给出格的另一个等价定义。定义定义13.313.3 设设S,*, 是代数系统，是代数系统，* *和和 是二元运算，如果是二元运算，如果* *和和 满满足交换律，结合律和吸收律，则足交换律，结合律和吸收律，则S,*, 构成一个构成
18、一个格格( (lattice) )。说明说明格中的幂等律可以由吸收律推出。格中的幂等律可以由吸收律推出。以后我们不再区别是偏序集定义的格，以后我们不再区别是偏序集定义的格，还是代数系统定义的格，而统称为格还是代数系统定义的格，而统称为格L L。格格格格的性质的性质的性质的性质定理定理13.13.3 3 设设L L是是格，则格，则 a,ba,bL L 有有aab b a ab ba a a ab bb b证明证明 先证先证 aab b a ab ba a由由aaa a和和aab b可知，可知，a a是是a,ba,b的下界，的下界，故故aaa ab b。显然又有显然又有a abba a。由反对称性
19、得由反对称性得a ab ba a。再证再证 a ab ba a a ab bb b。根据吸收律有根据吸收律有 b bb b(b(ba)a)由由a ab ba a得得 b bb ba, a, 即即a ab bb b。最后证最后证a ab bb b a ab b。由由aaa ab b得得 aaa ab bb b。 格的性质格的性质格的性质格的性质定理定理11.411.4 设设L L是格，是格， a,b,c,da,b,c,dL L，若若aab b且且ccd d，则则a accb bd d，a accb bd d证明证明 a accaab ba accccd d因此，因此， a accb bd d。同
20、理可证同理可证 a accb bd d。例例例例13.413.413.413.4例例13.413.4 设设L L是格，证明是格，证明 a,b,cL a,b,cL 有有a(bc)a(bc)(ab)(ac)(ab)(ac)证明证明由由 aaa a，bcbcb b 得得a(bc)a(bc)abab由由 aaa a，bcbcc c 得得a(bc)a(bc)acac从而得到从而得到 a(bc)a(bc)(ab)(ac)(ab)(ac)说明说明在格中分配不等式成立。在格中分配不等式成立。一般说来，格中的一般说来，格中的和和运算并不是满足分配律的。运算并不是满足分配律的。本节小结本节小结本节小结本节小结q偏
21、偏序序集集构构成成格格的的条条件件：任任意意二二元元子子集集都都有有最最大大下下界界和和最最小小上界。上界。q格的实例：正整数的因子格，幂集格，子群格。格的实例：正整数的因子格，幂集格，子群格。q格格的的性性质质：对对偶偶原原理理，格格中中算算律律（交交换换、结结合合、幂幂等等、吸吸收），保序性，分配不等式。收），保序性，分配不等式。q格作为代数系统的定义。格作为代数系统的定义。q格的证明方法格的证明方法13131313.2 .2 .2 .2 子格与格同态子格与格同态子格与格同态子格与格同态定义定义13.413.4 设设L, 是格，是格，S S是是L L的非空子集，若的非空子集，若S S关于关
22、于L L中中的运算的运算和和仍构成格，则仍构成格，则称称S S是是L L的的子格子格。例例13.513.5 设格设格L L如右图所示。令如右图所示。令S S1 1a,e,f,ga,e,f,gS S2 2a,b,e,ga,b,e,g则则S S1 1不是不是L L的子格，的子格，S S2 2是是L L的子格。的子格。因为对于因为对于e e和和f,f,有有efefc c，但但c c S S1 1。格同态格同态格同态格同态定义定义13.513.5 设设L L1 1和和L L2 2是是格，格， : L: L1 1L L2 2，若若 a,ba,bL L1 1 有有 (a(ab)b) (a)(a) (b),
23、(b), (a(ab)b) (a)(a)f(b)f(b)成立，则称成立，则称 为格为格L L1 1到到L L2 2的的同态映射同态映射，简称简称格同态格同态。例例13.613.6 (1) (1)设设 L L1 12n|nZ+2n|nZ+， L L2 22n+1|nN2n+1|nN则则L L1 1和和L L2 2关于通常数的小于或等于关系构成格。关于通常数的小于或等于关系构成格。令令 : L: L1 1LL2 2， (x)(x)x-1x-1不难验证不难验证 是是L L1 1到到L L2 2的同态映射，因为对任意的的同态映射，因为对任意的x,yLx,yL1 1有有 (xy)(xy) ( (max(
24、x,y)max(x,y)max(x,y)-1max(x,y)-1 (x)(x) (y)(y)(x-1)(y-1)(x-1)(y-1)max(x-1,y-1)max(x-1,y-1)max(x,y)-1max(x,y)-1 (xy)(xy) ( (min(x,y)min(x,y)min(x,y)-1min(x,y)-1 (x)(x) (y)(y)(x-1)(y-1)(x-1)(y-1)min(x-1,y-1)min(x-1,y-1)min(x,y)-1min(x,y)-1即即 ( (x xyy) ) (x)(x) (y),(y), (x(xyy) ) (x)(x) (y)(y)例例例例13.61
25、3.613.613.6(2)(2)如图中的格如图中的格L L1 1，L L2 2和和L L3 3，若定义若定义 1 1:L:L1 1LL2 2 1 1(a)(a) 1 1(b)(b) 1 1(c)(c)a a1 1， 1 1(d)(d)d d1 1 2 2:L:L1 1LL3 3 2 2(a)(a)a a2 2， 2 2(b)(b)b b2 2, , 2 2(c)(c)c c2 2， 2 2(d)(d)d d2 2则则 1 1和和 2 2都不是格同态，因为都不是格同态，因为 1 1( (b bc)c) 1 1(d)(d)d d1 1 1 1(b)(b) 1 1(c)(c)a a1 1a a1
26、1a a1 1 2 2(b(bc)c) 2 2(d)(d)d d2 2 2 2(b)(b) 2 2(c)(c)b b2 2c c2 2c c2 2从而从而 1 1( (b bc)c) 1 1(b)(b) 1 1(c)(c) 2 2(b(bc)c) 2 2(b)(b) 2 2(c)(c)格同态的性质格同态的性质格同态的性质格同态的性质定理定理13.513.5 设设 是格是格L L1 1到到L L2 2的映射，的映射，( (1)1)若若 是格同态映射，则是格同态映射，则 是保序映射，即是保序映射，即 x,yx,yL L1 1，有有xy xy (x)(x) (y)(y)(2)(2)若若 是双射，则是
27、双射，则 是格同构映射当且仅当是格同构映射当且仅当 x,yx,yL L1 1，有有xy xy (x)(x) (y)(y)证明证明 (1) (1) 任取任取x,yx,yL L1 1，xyxy，由格的性质知由格的性质知 x xy yy y。又由于又由于 是格同态映射，必有是格同态映射，必有 (y)(y) (x(xy)y) (x)(x) (y)(y)从而得到从而得到 (x)(x) (y)(y)。定理定理定理定理13.13.13.13.5(2)5(2)5(2)5(2)的证明的证明的证明的证明充分性。充分性。(2)(2)若若 是双射，则是双射，则 是格同构映射当且仅当是格同构映射当且仅当 x,yx,yL
28、 L1 1，有有xy xy (x)(x) (y)(y)只须证明只须证明 是是L L1 1到到L L2 2的同态映射即可。的同态映射即可。任取任取x,yx,yL L1 1，令令x xy yz z，由由 xzxz和和yz yz 知知 (x)(x) (z)(z)， (y)(y) (z)(z)从而有从而有 ( (x)x) (y)(y) (z)(z) (x(xy) y) 另一方面，由另一方面，由 ( (x)x) (y)(y)L L2 2和和 的满射性可知，的满射性可知，必存在必存在u uL L1 1使得使得 ( (u)u) (x)(x) (y)(y)因此有因此有 ( (x)x) (u)(u)， (y)(
29、y) (u)(u)。由已知条件可得由已知条件可得 xuxu，yuyu。 从而推出从而推出 x xyuyu。再次使用已知条件得再次使用已知条件得 ( (x xy)y) (u)(u) (x)(x) (y)(y)。综合上述有综合上述有 ( (x xy)y) (x)(x) (y)(y)。 同理可证同理可证 ( (x xy)y) (x)(x) (y)(y)。定理定理定理定理13.13.13.13.5(2)5(2)5(2)5(2)的证明的证明的证明的证明必要性。必要性。由由(1)(1)的结论必有的结论必有xy xy (x)(x) (y)(y)反之，若反之，若 (x)(x) (y)(y)，由于由于 是同构映
30、射，则是同构映射，则 (x(xy)y) (x)(x) (y)(y) (y)(y)又由于又由于 是双射，必有是双射，必有x xy yy y。从而证明了从而证明了 xyxy。(2)(2)若若 是双射，则是双射，则 是格同构映射当且仅当是格同构映射当且仅当 x,yx,yL L1 1，有有xy xy (x)(x) (y)(y)例例例例13.713.713.713.7例例13.713.7 设设L L1 1S, L,D, L2 2S 是是格，其中格，其中S S1212是是1212的所的所有正因子构成的集合，有正因子构成的集合，D D为整除关系，为整除关系，为通常数的小于为通常数的小于或等于关系。令或等于关
31、系。令 : S: S1212S S1212， ( (x) )x则则 是双射，但是双射，但 不是格不是格L L1 1到到L L2 2的同构映射。的同构映射。因为因为 (2)(2) (3)(3)，但但2 2不整除不整除3 3。根据根据定理定理13.513.5可知，可知， 不是同构映射。不是同构映射。格的直积格的直积格的直积格的直积类似于半群类似于半群, ,群和环群和环, ,也可以定义格的直积。也可以定义格的直积。定义定义13.613.6 设设L L1 1和和L L2 2是是格，定义格，定义L L1 1L L2 2上的运算上的运算, ,：即即 a, L L1 1L L2 2 有有a a a a a
32、a 称称L 为格为格L L1 1和和L L2 2的的直积直积。可以证明可以证明L 仍是格。仍是格。格的直积格的直积格的直积格的直积 ，a ，a L L1 1L L2 2，有有交换律交换律 a a a a a 结合律结合律 ( ( a)a a a (a a 同样同样 (a( a)a 同理可证同理可证运算也满足交换律和结合律。运算也满足交换律和结合律。格的直积格的直积格的直积格的直积吸收律吸收律 (a( a)a a a)a 同理有同理有 (a( a)a 这就证明了这就证明了和和运算满足吸收律。运算满足吸收律。从而证明从而证明 L L1 1L L2 2仍是格仍是格格的直积举例格的直积举例格的直积举例
33、格的直积举例格格L L0,1, ，为通常的小于或等于关系。则为通常的小于或等于关系。则L LL L，其中其中是最小元，是最小元， 1,1是最大元，且是最大元，且 0,01,1 ， 0,01,1 ，而而与与是不可比的。是不可比的。易见易见L LL L与与图图13.413.4的的L L1 1同构。同构。本节小结本节小结本节小结本节小结q格格L L的非空子集的非空子集S S构成构成L L的子格的条件：的子格的条件：S S对对L L的两个运算封闭。的两个运算封闭。q函数函数 构成格同态的条件：构成格同态的条件： (ab)(ab) (a)(a) (b)(b) (ab)(ab) (a)(a) (b)(b)
34、q格同态的保序性。格同态的保序性。13131313.3 .3 .3 .3 分配格与有补格分配格与有补格分配格与有补格分配格与有补格q一般说来，格中运算一般说来，格中运算对对满足分配不等式，满足分配不等式，即即 a,b,ca,b,cL L，有有a a(b(bc)(ac)(ab)b)(a(ac)c)但是不一定满足分配律。满足分配律的格称为但是不一定满足分配律。满足分配律的格称为分配格分配格。定义定义13.713.7 设设 是格，若是格，若 a,b,ca,b,cL L，有有a a(b(bc)c)(a(ab)b)(a(ac)c)a a(b(bc)c)(a(ab)b)(a(ac)c)则称则称L L为为分
35、配格分配格。说明说明上面两个等式互为对偶式。上面两个等式互为对偶式。在证明在证明L L为分配格时，只须证明其中的一个等式即可。为分配格时，只须证明其中的一个等式即可。例例例例13.813.813.813.8L L1 1和和L L2 2是分配格，是分配格，L L3 3和和L L4 4不是分配格。不是分配格。在在L L3 3中，中，b(cd)b(cd) bebeb b(bc)(bd)(bc)(bd)aaaaa a在在L L4 4中中, ,c(bd)c(bd) cacac c(cb)(cd)(cb)(cd)ededd d钻石格钻石格五角格五角格分配格的判别分配格的判别分配格的判别分配格的判别定理定理
36、13.613.6 设设L L是格，则是格，则L L是分配格当且仅当是分配格当且仅当L L中不含有与钻石中不含有与钻石格或五角格同构的子格。格或五角格同构的子格。证明证明略。略。推论推论( (1 1) ) 小于五元的格都是分配格。小于五元的格都是分配格。( (2 2) ) 任何一条链都是分配格。任何一条链都是分配格。例例例例13.913.913.913.9说明下图中的格是否为分配格，为什么？说明下图中的格是否为分配格，为什么？L L1 1, L, L2 2和和L L3 3都不是分配格。都不是分配格。 a,b,c,d,ea,b,c,d,e是是L L1 1的子格，并且同构于钻石格。的子格，并且同构于
37、钻石格。 a,b,c,e,fa,b,c,e,f是是L L2 2的子格，并且同构于五角格。的子格，并且同构于五角格。 a,c,b,e,fa,c,b,e,f是是L L3 3的子格，也同构于钻石格。的子格，也同构于钻石格。 定理定理定理定理13.713.713.713.7定理定理13.713.7 格格L L是分配格是分配格 当且仅当当且仅当 a,b,ca,b,cL L，a ab ba ac c且且a ab ba ac c b bc c。证明证明 必要性必要性。 a,b,ca,b,cL L，有有b b b b( (a ab b) )( (吸收律吸收律, ,交换交换律律) ) b b(a(ac)c)(
38、(已知条件代入已知条件代入) ) ( (b ba a) )(b(bc) c) ( (分配律分配律) ) ( (a ac c) )(b(bc c) )( (已知条件代入已知条件代入, ,交换律交换律) ) ( (a ab b) )c c ( (分配律分配律) ) ( (a ac)c)c c ( (已知条件代入已知条件代入) ) c c ( (交换律交换律, ,吸收律吸收律) )定理定理定理定理13.713.713.713.7充分性。充分性。假若假若 a,b,ca,b,cL L，有有a ab ba ac c且且a ab ba ac c b bc c成立，而成立，而L L不是分配格。不是分配格。根据
39、根据定理定理13.613.6，L L中必含有与钻石格或五角格同构的子格。中必含有与钻石格或五角格同构的子格。假设假设L L中含有与钻石格同构的子格，且该子格为中含有与钻石格同构的子格，且该子格为u,v,x,y,zu,v,x,y,z，其中其中u u为它的最小元，为它的最小元，v v为它的最大元。为它的最大元。从而推出从而推出x xy yx xz zu u，x xy yx xz zv v但但y yz z，与已知矛盾。与已知矛盾。对五角格的情况同理可证。对五角格的情况同理可证。v vu ux xz zy y定理定理定理定理13.713.713.713.7的应用的应用的应用的应用使用定理使用定理13.
40、713.7也可以判别一个格是否为分配格。也可以判别一个格是否为分配格。例如下例如下图图中的三个格都不是分配格。中的三个格都不是分配格。在在L L1 1中有中有 bcbcbdbd，bcbcbdbd，但但cdcd。在在L L2 2中有中有 bcbcbebe，bcbcbebe，但但cece。在在L L3 3中有中有 cbcbcdcd，cbcbcdcd，但但bdbd。格的全下界和全上界格的全下界和全上界格的全下界和全上界格的全下界和全上界定义定义13.813.8 设设L L是格，是格，若存在若存在a aL L使得使得 x xL L有有axax，则称则称a a为为L L的的全下界全下界；若存在若存在b
41、bL L使得使得 x xL L有有xbxb，则称则称b b为为L L的的全上界全上界。 命题命题格格L L若存在全下界或全上界，一定是唯一的。若存在全下界或全上界，一定是唯一的。证明证明以全下界为例，假若以全下界为例，假若a a1 1和和a a2 2都是格都是格L L的全下界的全下界, ,则有则有a a1 1aa2 2和和a a2 2aa1 1。根据偏序关系的反对称性必有根据偏序关系的反对称性必有a a1 1a a2 2。记法记法将格将格L L的的全下界记全下界记为为0 0，全上界记为全上界记为1 1。有有有有界格界格界格界格定义定义13.913.9 设设L L是格，是格，若若L L存在全下界
42、和全上界，则称存在全下界和全上界，则称L L为为有界格有界格，并将并将L L记为记为L,0,1。说明说明有限格有限格L L一定是有界格。一定是有界格。举例举例q设设L L是是n n元格元格，且，且L Laa1 1,a,a2 2, ,a,an n ，那么那么a a1 1a a2 2a an n是是L L的全的全下界，而下界，而a a1 1a a2 2a an n是是L L的全上界。因此的全上界。因此L L是有界格。是有界格。q对于对于无限格无限格L L来说，有的是有界格，有的不是有界格。来说，有的是有界格，有的不是有界格。q如集合如集合B B的的幂集幂集格格P(B), ，不管不管B B是有穷集还
43、是无穷集，是有穷集还是无穷集，它都是有界格。它的全下界是空集它都是有界格。它的全下界是空集，全上界是全上界是B B。q整数集整数集Z Z关于通常数的小于或等于关系构成的格不是有界格，因关于通常数的小于或等于关系构成的格不是有界格，因为不存在最小和最大的整数。为不存在最小和最大的整数。有界格的性质有界格的性质有界格的性质有界格的性质定理定理13.813.8 设设L,0,1是有界格，则是有界格，则 a aL L有有a a0 00 0a a0 0a aa a1 1a aa a1 11 1证明证明由由 a a00 00 和和 00a a0 0 可知可知 a a0 00 0。说明说明 在有界格中，在有界
44、格中，全下界全下界0 0是关于是关于运算的零元，运算的零元，运算的单位元。运算的单位元。全上界全上界1 1是关于是关于运算的零元，运算的零元，运算的单位元。运算的单位元。对偶原理对偶原理 对于涉及到有界格的命题，如果其中含有全下界对于涉及到有界格的命题，如果其中含有全下界0 0或或全上界全上界1 1，在求该命题的对偶命题时，必须将在求该命题的对偶命题时，必须将0 0替换替换成成1 1，而将而将1 1替换替换成成0 0。例如例如a a0 00 0 和和 a a1 11 1 互为对偶命题，互为对偶命题， a a0 0a a 和和 a a1 1a a 互为对偶命题。互为对偶命题。有界格中的补元有界格
45、中的补元有界格中的补元有界格中的补元定义定义13.1013.10 设设L,0,1是有界格，是有界格，a aL L，若存在若存在b bL L 使得使得a ab b0 0 和和 a ab b1 1成立，则成立，则称称b b是是a a的的补元补元。说明说明若若b b是是a a的补元，那么的补元，那么a a也是也是b b的补元。的补元。换句话说，换句话说，a a和和b b互为补元。互为补元。例例例例13.1013.1013.1013.10考虑下图中的四个格。考虑下图中的四个格。L L1 1中的中的a a与与c c互为补元，其中互为补元，其中a a为全下界，为全下界，c c为全上界，为全上界，b b没有
46、补元。没有补元。L L2 2中的中的a a与与d d互为补元，其中互为补元，其中a a为全下界，为全下界，d d为全上界，为全上界，b b与与c c也互为也互为补元。补元。L L3 3中的中的a a与与e e互为补元，其中互为补元，其中a a为全下界，为全下界，e e为全上界，为全上界，b b的补元是的补元是c c和和d d，c c的补元是的补元是b b和和d d，d d的补元是的补元是b b和和c c。b,c,db,c,d每个元素都有两每个元素都有两个补元。个补元。L L4 4中的中的a a与与e e互为补元。其中互为补元。其中a a为全下界。为全下界。e e为全上界。为全上界。b b的补元
47、是的补元是c c和和d d，c c的补元是的补元是b b，d d的补元是的补元是b b。有界格中补元的说明有界格中补元的说明有界格中补元的说明有界格中补元的说明在任何有界格中，在任何有界格中，q全下全下界界0 0与全上界与全上界1 1互补。互补。 q对于其他元素，可能存在补元，也可能不存在补元。对于其他元素，可能存在补元，也可能不存在补元。q如果存在，可能是唯一的，也可能是多个补元。如果存在，可能是唯一的，也可能是多个补元。q对于有界分配格，如果它的元素存在补元，一定是唯一的。对于有界分配格，如果它的元素存在补元，一定是唯一的。 有界分配格中补元的唯一性有界分配格中补元的唯一性有界分配格中补元
48、的唯一性有界分配格中补元的唯一性定理定理13.913.9 设设L,0,1是有界分配格。是有界分配格。若若aaL L，且对于且对于a a存在补元存在补元b b，则，则b b是是a a的唯一补元。的唯一补元。证明证明假设假设cLcL也也是是a a的补元，则有的补元，则有a ac c1 1，a ac c0 0又知又知b b是是a a的补元，故的补元，故a ab b1 1，a ab b0 0 从而得到从而得到a ac ca ab b，a ac ca ab b 由于由于L L是分配格，根据是分配格，根据定理定理13.713.7，b bc c。 有补格的定义有补格的定义有补格的定义有补格的定义定义定义13
49、.1113.11 设设L,0,1是有界格，若是有界格，若L L中所有元素都有中所有元素都有补元存在，则称补元存在，则称L L为为有补格有补格。L L2 2,L,L3 3和和L L4 4是有补是有补格，格，L L1 1不是有补格。不是有补格。L L2 2和和L L3 3是有补格，是有补格，L L1 1不是有补格。不是有补格。本节小结本节小结本节小结本节小结q如如果果格格中中一一个个运运算算对对另另一一个个运运算算是是可可分分配配的的，称称这这个个格格是是分分配格。配格。q分配格的两种判别法：分配格的两种判别法：不存在与钻石格或五角格同构的子格；不存在与钻石格或五角格同构的子格；对于任意元素对于任
50、意元素a,b,c,a,b,c,有有 ababacac且且ababacacb bc c。q有界格的定义及其实例。有界格的定义及其实例。q格中元素的补元及其性质（分配格中补元的唯一性）。格中元素的补元及其性质（分配格中补元的唯一性）。q有补格的定义。有补格的定义。13131313.4 .4 .4 .4 布尔代数布尔代数布尔代数布尔代数定义定义13.1213.12 如果一个格是如果一个格是有补分配格有补分配格，则称它为，则称它为布尔格布尔格或或布尔布尔代数代数。说明说明在布尔代数中，每个元素都存在着唯一的补元。在布尔代数中，每个元素都存在着唯一的补元。可以把求补元的运算看作是布尔代数中的一元运算。可
51、以把求补元的运算看作是布尔代数中的一元运算。可以把一个布尔代数标记为可以把一个布尔代数标记为B,0,1，为求补运算为求补运算, , a aB B，a a是是a a的补元。的补元。例例例例13.1113.1113.1113.11例例13.1113.11 设设S S1101101,2,5,10,11,22,55,1101,2,5,10,11,22,55,110是是110110的正因子集合。的正因子集合。令令gcdgcd,lcm,lcm分别表示求最大公约数和最小公倍数的运算。问分别表示求最大公约数和最小公倍数的运算。问S,gcd,lcm是否构成布尔代数？为什么？是否构成布尔代数？为什么？解答解答 证
52、明证明 ,lcm构成格。构成格。容易验证容易验证 x,y,zx,y,zS S110110，有有gcdgcd(x,y)(x,y)S S110110lcm(x,y)lcm(x,y)S S110110gcdgcd(x,y)(x,y)gcdgcd(y,x) (y,x) lcm(x,y)lcm(x,y)lcm(y,x)lcm(y,x)gcdgcd( (gcdgcd(x,y),z)(x,y),z)gcdgcd(x,(x,gcdgcd(y,z)(y,z)lcm(lcm(x,y),z)lcm(lcm(x,y),z)lcm(x,lcm(y,z)lcm(x,lcm(y,z)gcdgcd(x,lcm(x,y)(x,
53、lcm(x,y)x xlcm(x,lcm(x,gcdgcd(x,y)(x,y)x x二元运算二元运算交换律交换律结合律结合律吸收律吸收律例例例例13.1113.1113.1113.11证明证明 ,gcd,lcm是分配格。是分配格。易验证易验证 x,y,zx,y,zS S110110 有有gcdgcd(x,lcm(y,z)(x,lcm(y,z)lcm(lcm(gcdgcd(x,y),(x,y),gcdgcd(x,z)(x,z)证明证明 ,lcm是有补格。是有补格。1 1 为为S S110110中的全下界中的全下界110110为为S S110110中的全上界中的全上界1 1和和110110互为补元
54、，互为补元，2 2和和5555互为补元，互为补元，5 5和和2222互为补元，互为补元，1010和和1111互为互为补补元。元。综上所述，综上所述， ,gcd,lcm为布尔代数。为布尔代数。例例例例13.1213.1213.1213.12例例13.1213.12 设设B B为任意集合为任意集合, ,证明证明B B的的幂集格幂集格P(B),B构成布尔代数，称为构成布尔代数，称为集合代数集合代数。证明证明P(B)P(B)关于关于和和构成格，因为构成格，因为和和运算满足交换律、结合律和吸收律。运算满足交换律、结合律和吸收律。由于由于和和互相可分配，因此互相可分配，因此P(B)P(B)是分配格，是分配
55、格，且全下界是空集且全下界是空集, ,全上界是全上界是B B。根据绝对补的定义，取全集为根据绝对补的定义，取全集为B B， x xP(B)P(B)，x x是是x x的补元。的补元。从而证明从而证明P(B)P(B)是有补分配格，即布尔代数。是有补分配格，即布尔代数。 布尔代数的性质布尔代数的性质布尔代数的性质布尔代数的性质定理定理13.1013.10 设设B,0,1是布尔代数，则是布尔代数，则 ( (1) 1) a aB B，(a(a) )a a (2) (2) a,ba,bB B，(a(ab)b)a ab b,(a,(ab)b)a ab b说明说明(1)(1)称为称为双重否定律双重否定律。(2
56、)(2)称为称为德摩根律德摩根律。命题代数与集合代数的双重否定律与德摩根律实际上命题代数与集合代数的双重否定律与德摩根律实际上是这个定理的特例。是这个定理的特例。可以证明德摩根律对有限个元素也是正确的。可以证明德摩根律对有限个元素也是正确的。证明证明(1) (1) (a a) )是是a a的补元，的补元，a a也是也是a a的补元。的补元。由补元的唯一性得由补元的唯一性得( (a a) )a a。定理定理定理定理13.13.13.13.10(2)10(2)10(2)10(2)的证明的证明的证明的证明(2) (2) a,ba,bB B，(a(ab)b)a ab b,(a,(ab)b)a ab b
57、(a(ab)b)(a(ab b) ) ( (a aa ab b) )( (b ba ab b) ) (1(1b b) )( a( a1)1) 1 11 1 1 1(a(ab)b)(a(ab b) ) ( (a ab ba a) )(a(ab bb b) ) (0(0b)b)(a(a0)0) 0 00 00 0所以所以a ab b是是a ab b的补的补元元，根据补元的唯一性有根据补元的唯一性有( (a ab)b)a ab b同理可证同理可证(a(ab)b)= a= ab b。 布尔代数作为代数系统的定义布尔代数作为代数系统的定义布尔代数作为代数系统的定义布尔代数作为代数系统的定义定义定义13.
58、1313.13 设设B,*, 是代数系统，是代数系统，* *和和 是二元运算。是二元运算。若若* *和和运算满足：运算满足：( (1 1) ) 交换律交换律，即，即 a,ba,bB B 有有a*ba*bb*ab*a，a a b bb b a a (2)(2) 分配律分配律，即，即 a,b,ca,b,cB B有有a*(ba*(b c)c)(a*b)(a*b) (a*c)(a*c)a a (b*c)(b*c)(a(a b)*(ab)*(a c)c) (3)(3) 同一律同一律，即存在，即存在0,10,1B B，使得使得 a aB B 有有a*1a*1a a，a a 0 0a a (4)(4) 补元
59、补元律律，即，即 a aB,B,存在存在a aB B，使得使得a*aa*a0 0，a a a a1 1 则称则称B,*, 是一个是一个布尔代数布尔代数。 关于布尔代数定义的说明关于布尔代数定义的说明关于布尔代数定义的说明关于布尔代数定义的说明所谓所谓同一律就是指运算含有单位元的性质同一律就是指运算含有单位元的性质，这里，这里的的1 1是是* *运算的运算的单位元，单位元，0 0是运算是运算 的单位元。的单位元。可以证明可以证明1 1和和0 0分别也是分别也是 和和* *运算运算的零元。的零元。 a aB B有有 a a 1 1 ( (a a 1)1)*1*1 （同一律）同一律） 1 1* *(
60、 (a a 1) 1) （交换律）交换律） ( (a a a a) )* *( (a a 1) 1) （补元律）补元律） a a ( (a a* *1 1) ) （分配律）分配律） a a a a （同一律）同一律） 1 1 （补元律）（补元律）同理可同理可证证 a a* *0 00 0。关于布尔代数定义的说明关于布尔代数定义的说明关于布尔代数定义的说明关于布尔代数定义的说明为证明以上定义为证明以上定义的的B,*, 是布尔代数，只需证明它是一是布尔代数，只需证明它是一个格，即个格，即证明证明* *和和运算满足结合律和吸收律。运算满足结合律和吸收律。证明吸收律证明吸收律， a,ba,bB B有有
61、 a a (a(a* *b)b) ( (a a* *1)1) ( (a a* *b)b)（同一律）同一律） a a*(*(1 1 b b) )（分配律）分配律） a a*1*1 （1 1是是 运算的零元运算的零元) ) a a （同一律）同一律）同同理理有有 a a* *(a(a b)b)a a。关于布尔代数定义的说明关于布尔代数定义的说明关于布尔代数定义的说明关于布尔代数定义的说明为证结合律，先证以下命题：为证结合律，先证以下命题： a,b,ca,b,cB B，a a b ba a c c 且且 a a b ba a c c b bc c由由 a a b ba a c c 且且 a a b
62、ba a c c 可得可得( (a a b)b)* *(a(a b)b)(a(a c)c)* *(a(a c) c) 由分配律和交换律得由分配律和交换律得( (a a* *a a ) ) b b(a(a* *a a ) ) c c由补元律得由补元律得 0 0 b b0 0 c c由同一律和交换律得由同一律和交换律得b bc c关于布尔代数定义的说明关于布尔代数定义的说明关于布尔代数定义的说明关于布尔代数定义的说明使用这个命题，为证明使用这个命题，为证明 ( (a a* *b)b)*c*ca a*(*(b b*c*c) )，只需证明以下只需证明以下两个等式：两个等式：( (1 1) ) a a
63、(a(a* *b)b)*c)*c)a a (a(a*(*(b b*c*c)(2) a(2) a (a(a* *b)b)*c)*c)a a (a(a*(*(b b*c*c)先证明第一个等式，由吸收先证明第一个等式，由吸收律律有有 a a (a(a*(*(b b*c)*c)a a a a (a(a* *b)b)*c)*c) ( (a a (a(a* *b)b)* *(a(a c)c)( (分配律分配律) ) a a* *(a(a c)c)( (吸收吸收律律) ) a a所以所以(1)(1)式成立。式成立。关于布尔代数定义的说明关于布尔代数定义的说明关于布尔代数定义的说明关于布尔代数定义的说明下面证
64、明下面证明(2)(2)式：式： a a (a(a* *b)b)*c)*c)a a (a(a*(*(b b*c*c) a a (a(a*(*(b b*c*c) ( (a a a a) )*(*(a a ( (b b*c*c) ) ( (分配律分配律) ) 1*1*( (a a ( (b b*c*c) ) ( (交换交换律律, ,补元律补元律) ) a a ( (b b*c*c) ) ( (交换交换律律, ,同一律同一律) ) a a (a(a* *b)b)*c)*c) ( (a a (a(a* *b)*(ab)*(a c) (c) (分配律分配律) ) ( ( (a a a a) )* *(a(
65、a b)b)* *(a(a c)c) ( (分配律分配律) ) ( (1 1* *( (a a b)b)* *(a(a c) c) ( (交换律交换律, ,补元补元律律) ) ( (a a b)b)* *( (a a c) (c) (交换律交换律, ,同一律同一律) ) a a ( (b b*c*c) )( (分配律分配律) )所以（所以（2 2）式成立。）式成立。布尔代数的子代数布尔代数的子代数布尔代数的子代数布尔代数的子代数定义定义13.1413.14 设设B,0,1是布尔代数是布尔代数，S S是是B B的非空子的非空子集，若集，若0,10,1S S，且且S S对对, ,和和 运算都是封闭
66、的，则运算都是封闭的，则称称S S是是B B的的子布尔代数子布尔代数。例例例例13.1313.1313.1313.13例例13.1313.13 设设B,0,1是布尔代数，是布尔代数，a,ba,bB B，且且a ab b。令令S Sx|xx|xB B，且且axbaxb称称S S为为B B中的中的区间区间，可简记可简记为为a,ba,b。可以证明可以证明a,ba,b是一个布尔代数。是一个布尔代数。显然显然S S是是B B的非空子的非空子集，且集，且a a和和b b分别为分别为S S的全下界和全上界。的全下界和全上界。对任意的对任意的x,ySx,yS都有都有 axbaxb，aybayb从而有从而有 a
67、xaxyb, axyb, axybybS S关于关于和和运算是封闭的。运算是封闭的。易见易见和和运算在运算在S S上适合交换律和分配律。上适合交换律和分配律。例例例例13.1313.1313.1313.13对任意的对任意的 xSxS， 令令 y y(a(ax x ) )b (b (下面证明下面证明y y为为x x得补元。得补元。) )由于由于 aaaax x ，abab，故故 aa(a(ax x ) )b b。同时同时( (a ax x ) )bbbb，因此因此 y yS S。 又又x xy y x x(a(ax x ) )b b) ) x x( (a ab b)()(x x b b) ) )
68、( (分配律分配律) ) x xa a(x x b b) ) (a(ab)b) x x( (x x b b) ) (ax)(ax) ( (x xx x )(x)(xb b) ) ( (分配律分配律) ) 1 1(xxb b) ) ( (补元律补元律) ) xxb b ( (交换律，同一律交换律，同一律) ) b b(xb)(xb)例例例例13.1313.1313.1313.13 x xy y x x(a(ax x ) )b b) ) x x( (a ax x ) ) (xb,(xb,交换律交换律) ) (x(xa)a)( (x xx x ) ) ( (分配律分配律) ) (x(xa)a)0 0
69、 ( (补元律补元律) ) x xa a ( (同一律同一律) ) a a (ax)(ax)根据定义根据定义13.1313.13，S, 构成布尔代数。构成布尔代数。其全上界是其全上界是a a，全下界是全下界是b b。 x xa,ba,b，x x关于这个全上界和全下界的补元是关于这个全上界和全下界的补元是( (a ax x ) )b b。当当a a0 0且且b b1 1时，时， a,ba,b是是B B的子布尔代数。的子布尔代数。但当但当a a00或或b b1 1时，时， a,ba,b不是不是B B的子布尔代数。的子布尔代数。 例例例例13.1413.1413.1413.14考虑考虑110110的
70、正因子集合的正因子集合S S110110关于关于gcdgcd,lcm,lcm运算构成的布尔代数。运算构成的布尔代数。它有以下的子布尔代数：它有以下的子布尔代数： 1,1101,110 1,2,55,1101,2,55,110 1,5,22,1101,5,22,110 1,10,11,1101,10,11,110 1,2,5,10,11,22,55,1101,2,5,10,11,22,55,110布尔代数的同态映射布尔代数的同态映射布尔代数的同态映射布尔代数的同态映射定义定义13.1513.15 设设B,0,1和和B,E是两个布是两个布尔代数。这里尔代数。这里的的, ,-,-泛指布尔代数泛指布尔
71、代数B B2 2中的求最大中的求最大下下界、最界、最小上界和补元的运算小上界和补元的运算。和和E E分别分别是是B B2 2的全下界和全上界。的全下界和全上界。 : B: B1 1B B2 2。如果对于任意的如果对于任意的a,ba,bB B1 1 有有 (a(ab) b) (a)(a) (b)(b) (a(ab) b) (a)(a) (b)(b) (a(a ) ) - - (a)(a)则称则称 是布尔代数是布尔代数B B1 1到到B B2 2的的同态映射同态映射，简称，简称布尔代数的布尔代数的同态同态。说明说明类似于其它代数系统，也可以定义布尔代数的单同态、类似于其它代数系统，也可以定义布尔代
72、数的单同态、满同态和同构。满同态和同构。例例例例13.1513.1513.1513.15例例13.1513.15 设设B,0,1和和B,E是布尔代数。是布尔代数。 : B: B1 1B B2 2。若若 a,ba,bB B1 1有有 (a(ab) b) (a)(a) (b)(b) (a(a ) ) - - (a)(a)证明证明 是是B B1 1到到B B2 2的同态。的同态。证明证明只须证明只须证明 a,ba,bB B1 1 有有 (a(ab)b) (a)(a) (b)(b)成立即可。成立即可。 (a(ab)b) (a(ab)b) ) ) ) )( (双重否定律双重否定律) ) - - (a(a
73、b)b) ) ) ( (已知已知) ) - - (a(a b b ) )( (德摩根律德摩根律) ) -(-( (a(a ) ) (b(b ) ) ( (已知已知) ) -(-(- (a)(a)- - (b)(b) ( (已知已知) ) -(-(- (a)(a)-(-(- (b) (b) ( (德摩根律德摩根律) ) (a)(a) (b)(b)( (双重否定律双重否定律) )有限布尔代数的结构有限布尔代数的结构有限布尔代数的结构有限布尔代数的结构定义定义13.1613.16 设设L L是格，是格，0 0L L，a aL L，若若 b bL L 有有0 0ba ba b ba a则称则称a a是
74、是L L中的中的原子原子。 考虑右图中的几个格。考虑右图中的几个格。L L1 1的原子的原子是是a a。L L2 2的原子是的原子是a,b,ca,b,c。L L3 3的原子的原子是是a a和和b b。若若L L是正整数是正整数n n的全体正因子关于整除关系构成的格，则的全体正因子关于整除关系构成的格，则L L的原子恰的原子恰为为n n的全体质因子。的全体质因子。若若L L是集合是集合B B的幂集合，则的幂集合，则L L的原子就是由的原子就是由B B中元素构成的单元集。中元素构成的单元集。引理引理引理引理引理引理1 1 设是格，设是格，a,ba,b是中的原子是中的原子，若，若abab，则，则a
75、ab b0 0。证明证明假设假设a abb0 0，则有则有0 0a aba ba 和和 0 0a abbbb由于由于a,ba,b是原子，则有是原子，则有 a abba a 和和 a abbb b，从而有从而有a ab b，与已知矛盾。与已知矛盾。引理引理引理引理引理引理设设B B是有限的布尔代数，是有限的布尔代数， xBxB，x x0 0，令令T(x)T(x)aa1 1,a,a2 2,a,an n 是是B B中所有小于或等于中所有小于或等于x x的原子构成的集合，则的原子构成的集合，则x xa a1 1aa2 2aan n称这个表示式为称这个表示式为x x的原子表示，且是唯一的表示。的原子表示
76、，且是唯一的表示。这里的唯一性是指：若这里的唯一性是指：若x xa a1 1aa2 2aan n，x xb b1 1bb2 2b bn n都是都是x x的原子表示，则有的原子表示，则有 a a1 1,a,a2 2,a,an n bb1 1,b,b2 2,b bn n 引理引理引理引理2 2 2 2的证明的证明的证明的证明令令y ya a1 1aa2 2aan n。 由于由于a ai ixx，i i1,2,n1,2,n，所以必所以必有有yxyx。由此可知由此可知t t1 1是原子，且是原子，且t t1 1xx和和t t1 1yy 。假如假如xyxy 00，则存在则存在B B中中元素元素t t1
77、1,t,t2 2,t ts s，现证明现证明xyxy 0 0。使得使得t t1 1覆盖覆盖0 0，t t2 2覆盖覆盖t t1 1，t ts s覆盖覆盖t ts s-1-1，且且t ts sxyxy 。由由t t1 1xx可知可知t t1 1T(x)T(x)。 即存在即存在a ai iT(x)T(x)，使得使得t t1 1a ai i。又由又由t t1 1yy 可知可知t t1 1yy t t1 1，从而从而有有t t1 1t t1 1yy a ai iy y a ai i(a(a1 1aa2 2aan n) ) a ai i(a(a 1 1aa 2 2a a i i a an n) )( (
78、a ai iaa i i)(a)(a 1 1aa i-i-1 1aa i+1i+1aa n n) )0 0a a 1 1aa i-1i-1aa i+1i+1aa n n0 0这与这与t t1 1覆盖覆盖0 0矛盾。矛盾。从而证明了从而证明了xyxy 0 0。引理引理引理引理由由 y yyy0 0(yx)(yx)(yyyy ) )yy(xy(xy ) )( (yx)1yx)1yxyx可知可知 xyxy。 综合上述得综合上述得x xy y， 即即x xa a1 1aa2 2aan n。设设x xb b1 1bb2 2b bm m是是x x的另一个原子表示，的另一个原子表示，任取任取a ai iaa
79、1 1,a,a2 2,a,an n ，假若假若a ai i bb1 1,b,b2 2,b bm m 。由引理由引理1 1 必有必有a ai ib bj j0 0，j j1,2,m1,2,m。 又由于又由于a ai ixx，于是于是a ai ia ai ix xa ai i(b(b1 1bb2 2b bn n) )( (a ai ibb1 1)()(a ai ibb2 2)()(a ai ib bm m) )0000000 0这与这与a ai i是原子矛盾。是原子矛盾。从而证明了从而证明了a ai ib1,b2,b1,b2,bmbm 。同理可证，同理可证， b bj jbb1 1,b,b2 2,
80、b bm m ，必有必有b bj jaa1 1,a,a2 2,a,an n ，于是于是 a a1 1,a,a2 2,a,an n bb1 1,b,b2 2,b bm m 。有限布尔代数的表示定理有限布尔代数的表示定理有限布尔代数的表示定理有限布尔代数的表示定理定理定理13.11 (13.11 (有限布尔代数的表示定理有限布尔代数的表示定理) ) 设设B B是有限布尔代数，是有限布尔代数，A A是是B B的全体原子构成的集合的全体原子构成的集合，则，则B B同构于同构于A A的幂集代数的幂集代数P(A)P(A)。证明证明任任取取xBxB，令，令T(x)T(x)a|aB,aa|aB,a是原子是原子
81、且且aax x 则则T(x)T(x) A A，定义函数定义函数 ：BBP(A)P(A)， (x)(x)T(x)T(x)， xBxB下面证明下面证明 是是B B到到P(A)P(A)的同构映射。的同构映射。任任取取x,yx,yB B， b b 有有 bbT(xT(xy y) ) bA bA 且且 bbxxy y (bA (bA且且bbx) x) 且且 ( (bAbA且且by)by) b bT(x)T(x)且且bbT(T(y y) ) b bT(x)T(y)T(x)T(y)从而有从而有 T(xT(xy y) )T(x)T(y)T(x)T(y)，即即 x,yx,y B B 有有 (x(xy y) )
82、(x)(x) (y)(y)。定理定理定理定理13.1113.1113.1113.11证明证明证明证明任取任取x,yx,yB B，设设x xa a1 1a a2 2a an n，y yb b1 1b b2 2b bm m是是x,yx,y的原子表示，则的原子表示，则x xy ya a1 1a a2 2a an nb b1 1b b2 2b bm m由引理由引理2 2可知可知T(xT(xy)y)aa1 1,a,a2 2, ,a,an n,b,b1 1,b,b2 2, , , ,b bm m 又由于又由于T(x)T(x)aa1 1,a,a2 2, , ,a ,an n ，T(y)T(y)bb1 1,b
83、,b2 2, , , ,b bm m 所以所以 T(xT(xy)y)T(x)T(y)T(x)T(y)即即 (x(xy)y) (x)(x) (y)(y)定理定理定理定理13.1113.1113.1113.11证明证明证明证明任取任取xxB B，存在存在x x B B 使得使得xxxx 1 1， xxxx 0 0因此有因此有 (x)(x) (x(x ) ) (xx(xx ) ) (1)(1)A A (x)(x) (x(x ) ) (xx(xx ) ) (0)(0)而而和和A A分别分别为为P(P(A A) )的全下界和全上界，的全下界和全上界，因此因此 (x(x ) )是是 (x)(x)在在P(P
84、(A A) )中的补元，即中的补元，即 (x(x ) ) (x)(x)综上所述，综上所述， 是是B B到到P(A)P(A)的同态映射。的同态映射。定理定理定理定理13.1113.1113.1113.11证明证明证明证明下面证明下面证明 为双射。为双射。假设假设 (x)(x) (y)(y)，则，则有有T(x)T(x)T(y)T(y)aa1 1,a,a2 2, , ,a ,an n 由引理由引理2 2可知可知 x xa a1 1a a2 2a an ny y于是于是 为单射为单射。任取任取bb1 1,b,b2 2, , , ,b bm mP(A)P(A)，令令x xb b1 1b b2 2b bm
85、 m ，则则 (x)(x)T(x)T(x)bb1 1,b,b2 2, , , ,b bm m 于是于是 为满射。为满射。定理得证。定理得证。例子例子例子例子考虑考虑110110的正因子的集合的正因子的集合S S110110关于关于gcdgcd, lcm, lcm运算构成的布尔代数。运算构成的布尔代数。它的原子是它的原子是2 2、5 5和和1111，因此原子的集合因此原子的集合A A2,5,112,5,11。幂集幂集P(A)P(A) ,2,5,11,2,5,2,11,5,11,2,5,11,2,5,11,2,5,2,11,5,11,2,5,11。幂集代数幂集代数是是P(A),A。只要令只要令 :
86、 S: S110110P(A)P(A)， (1)(1)， (2)(2)22， (5)(5)55， (11)(11)1111， (10)(10)2,52,5， (22)(22)2,112,11， (55)(55)5,11,5,11, (110)(110)A A， 那么那么f f就是定理就是定理13.1113.11中从中从S S110110到幂到幂集集P(A)P(A)的同构映射。的同构映射。 推论推论推论推论1 1 1 1推论推论1 1 任何有限布尔代数的基数任何有限布尔代数的基数为为2 2n，nN N。证明证明 设设B B是有限布尔代数，是有限布尔代数，A A是是B B的所有原子构成的集合，的所
87、有原子构成的集合，且且|A|A|n，nN N。由定理由定理13.13.11 11 得得B BP(A)P(A)，而而|P(A)|P(A)|2 2n，所以所以|B|B|2 2n。推论推论推论推论2 2 2 2推论推论2 2 任何等势的有限布尔代数都是同构的。任何等势的有限布尔代数都是同构的。证明证明 设设B B1 1和和B B2 2是有限布尔代数，且是有限布尔代数，且| |B B1 1|=|B|=|B2 2| |。则则B B1 1P(AP(A1 1) )，B B2 2P(AP(A2 2) )，其中其中A A1 1和和A A2 2分别为分别为B B1 1和和B B2 2的原子集合。的原子集合。易见易
88、见| |A A1 1| |A|A2 2| |，存在存在双射双射f f：A A1 1A A2 2。令令 ：P(AP(A1 1)P(A)P(A2 2) )， (x)(x)f(x)f(x)， x x A A1 1下面证明下面证明 是是P(AP(A1 1) )到到P(AP(A2 2) )的同构映射。的同构映射。任取任取x,yP(Ax,yP(A1 1) )，由定理由定理7.57.5有有 f(xy)f(xy)f(x)f(y)f(x)f(y)f(xy)f(xy) f(x)f(y)f(x)f(y) 又由于又由于f f的单射性，必有的单射性，必有f(xy)f(xy)f(x)f(y)f(x)f(y) 由于由于f(
89、x)f(f(x)f(x x) )f(xf(xx x) )f(f() ) f(x)f(f(x)f(x x) )f(xf(xx x) )f(Af(A1 1) )A A2 2得得 f(f(x x) )f(x)f(x)，这就证明了这就证明了 是是P(AP(A1 1) )到到P(AP(A2 2) )的的同态映射。同态映射。综上所述综上所述, ,有有P(AP(A1 1) )P(AP(A2 2),),根据习题十三章第根据习题十三章第1919题，题，B B1 1B B2 2得证。得证。有限布尔代数的说明有限布尔代数的说明有限布尔代数的说明有限布尔代数的说明q有限布尔代数的基数都是有限布尔代数的基数都是2 2的
90、幂。的幂。q在同构意义上，对于任何在同构意义上，对于任何2 2n，n为自然数，为自然数，仅存在一个仅存在一个2 2n元元的布尔代数的布尔代数。q下图给出了下图给出了1 1元元,2,2元元,4,4元和元和8 8元的布尔代数。元的布尔代数。主要内容主要内容主要内容主要内容q布尔代数的两个等价定义：布尔代数的两个等价定义：有补分配格；有补分配格；有有两两个个二二元元运运算算并并满满足足交交换换律律、分分配配律律、同同一一律律和和补补元元律的代数系统。律的代数系统。q布尔代数的特殊性质：双重否定律和德摩根律。布尔代数的特殊性质：双重否定律和德摩根律。q子布尔代数的定义及其判别。子布尔代数的定义及其判别
91、。q布尔代数同态的判定：布尔代数同态的判定：f(ab)f(ab)f(a)f(b)(f(a)f(b)(或或f(ab)f(ab)f(a)f(b),f(a)f(b),f(af(a ) )-f(a) -f(a) q对对于于任任意意自自然然数数n n，只只有有一一个个2 2n n元元的的有有限限布布尔尔代代数数，就就是是幂幂集代数。集代数。学习要求学习要求学习要求学习要求q能够判断给定偏序集或者代数系统是否构成格。能够判断给定偏序集或者代数系统是否构成格。q能够确定一个命题的对偶命题。能够确定一个命题的对偶命题。q能够证明格中的等式和不等式。能够证明格中的等式和不等式。q能够判别格能够判别格L L的子集
92、的子集S S是否构成格。是否构成格。q了解格的同态及其性质。了解格的同态及其性质。q能够判别给定的格是否为分配格。能够判别给定的格是否为分配格。q能够判别布尔代数并证明布尔代数的等式。能够判别布尔代数并证明布尔代数的等式。作业作业作业作业习题十三习题十三1 1，2 2，3 3，6 6，8 8，1212，1616，1717，1919格的证明方法格的证明方法格的证明方法格的证明方法q格中等式的证明方法格中等式的证明方法证明等式的左边证明等式的左边“小于等于小于等于”右边，右边右边，右边“小于等于小于等于”左边。左边。根据偏序关系的反对称性，得到需要的等式。根据偏序关系的反对称性，得到需要的等式。q格中不等式的证明方法格中不等式的证明方法aaaa( (偏序关系的自反性偏序关系的自反性) )abab且且bc bc ac ac ( (偏序关系的传递性偏序关系的传递性) )abaaba，abbabb，aabaab，aab aab ( (下界定义与上界的定义下界定义与上界的定义) )abab且且ac ac abc abc，baba且且ca ca bca bca( (最大下界定义与最小上界的定义最大下界定义与最小上界的定义) )abab且且cd cd acbd acbd，acbdacbd( (保序性保序性) )
