1、第13章 格与布尔代数q 2本章内容本章内容13.1 13.1 格的定义与性质格的定义与性质13.2 13.2 子格与格同态子格与格同态13.3 13.3 分配格与有补格分配格与有补格13.4 13.4 布尔代数布尔代数本章总结本章总结作业作业q 313.1 13.1 格的定义与性质格的定义与性质 定义定义13.113.1 设设S, 是偏序集，是偏序集，如果如果 x, ,ySS， x, ,y 都有最小都有最小上界和最大下界上界和最大下界，则称，则称S S关于偏序关于偏序作成一个作成一个格格( (lattice) )。说明：说明：由于最小上界和最大下界的唯一性，可以把求由于最小上界和最大下界的唯
2、一性，可以把求 x, ,y 的最的最小上界和最大下界看成小上界和最大下界看成x x与与y y的二元运算的二元运算和和。xy：表示：表示x x与与y y的最小上界的最小上界xy：表示：表示x x和和y y的最大下界。的最大下界。 本章出现的本章出现的和和符号只代表格中的运算，而不再有其它的符号只代表格中的运算，而不再有其它的含义。含义。q 4格的实例格的实例例例13.113.1 设设n n是正整数，是正整数，S Sn n是是n n的正因子的集合。的正因子的集合。D D为整除关系，为整除关系，则偏序集则偏序集S 构成格。构成格。 x,yx,yS Sn n，x xy y是是lcm(x,y)lcm(x
3、,y)，即即x x与与y y的最小公倍数。的最小公倍数。x xy y是是gcd(x,ygcd(x,y) )，即即x x与与y y的最大公约数。的最大公约数。下图给出了格下图给出了格S,D，S,D和和S,D。q 5例例13.213.2例例13.213.2 判断下列偏序集是否构成格判断下列偏序集是否构成格, ,并说明理由。并说明理由。(1) P(B),(1) ，其中其中P(B)P(B)是集合是集合B B的幂集。的幂集。(2) Z,(2) ，其中其中Z Z是整数集是整数集, ,为小于或等于关系。为小于或等于关系。(3) (3) 偏序集的哈斯图分别在下图给出。偏序集的哈斯图分别在下图给出。q 6例例1
4、3.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(x,y)min(x,y)，它们都是整数。它们都是整数。(3)(3)都不是格。都不是格。(a)(a)中的中的a,ba,b没有最大下界。没有最大下界。(b)(b)中的中的b,db,d有
5、两个上界有两个上界c c和和e,e,但没有最小上界。但没有最小上界。(c)(c)中的中的b,cb,c有三个上界有三个上界d,e,f,d,e,f,但没有最小上界。但没有最小上界。(d)(d)中的中的a,ga,g没有最大下界。没有最大下界。q 7例例13.313.3例例13.3 13.3 设设G G是群，是群，L(G)L(G)是是G G的所有子群的集合。即的所有子群的集合。即L(G)L(G) H|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生成的子群（即包含着生成的子群（
6、即包含着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 。 q 8对偶原理对偶原理定义定义13.213.2 设设f f是含有格中元素以及符号、是含有格中元素以及符号、和和的的命题。令命题。令f f* *是将是将f f中的中的替换成替换成，替换成替换成，替换成替换成，替换成替换成所得到的命题。称所得到的命题。
7、称f f* *为为f f的的对偶命题对偶命题。例如例如 在格中令在格中令f f是是(ab)cc(ab)cc，则，则f f* *是是(ab)cc(ab)cc。格的对偶原理格的对偶原理 设设f f是含有格中元素以及符号、是含有格中元素以及符号、和和的命题。若的命题。若f f对一切格为真，则对一切格为真，则f f的对偶命题的对偶命题f f* *也对一切格也对一切格为真。为真。例如例如 对一切格对一切格L L都有都有 a,bLa,bL，abaaba( (因为因为a a和和b b的交是的交是a a的一个下界的一个下界) )那么那么对一切格对一切格L L都有都有 a,bLa,bL，abaaba说明说明许多
8、格的性质都是互为对偶命题的。许多格的性质都是互为对偶命题的。有了格的对偶原理，在证明格的性质时，有了格的对偶原理，在证明格的性质时，只须证明其中的一个命题即可。只须证明其中的一个命题即可。q 9格的运算性质格的运算性质定理定理13.113.1 设设L, 是格，则运算是格，则运算和和适合适合交换律交换律、结合结合律律、幂等律幂等律和和吸收律吸收律，即，即(1)(1)交换律交换律 a,bL a,bL 有有ababbabaababbaba(2)(2)结合律结合律 a,b,cL a,b,cL 有有(ab)c(ab)ca(bc)a(bc)(ab)c(ab)ca(bc)a(bc)(3)(3)幂等律幂等律
9、aL aL 有有aaaaa aaaaaa a(4)(4)吸收律吸收律 a,bL a,bL 有有a(ab)a(ab)a aa(ab)a(ab)a aq 10定理定理13.113.1(1)ab(1)ab和和baba分别是分别是a,ba,b和和b,ab,a的最小上界。的最小上界。由于由于a,ba,bb,ab,a，所以，所以ababbaba。由对偶原理，由对偶原理，ababbaba得证。得证。(2)(2)由最小上界的定义有由最小上界的定义有(a(ab)b)cacaba ba (13.1)(13.1)(a(ab)b)cacabb bb (13.2)(13.2)(a(ab)b)cc cc (13.3)(1
10、3.3)由式由式13.213.2和和13.313.3有有(a(ab)b)cbcbc c(13.4)(13.4)再由式再由式13.113.1和和13.413.4有有(a(ab)b)caca(b(bc)c)同理可证同理可证(a(ab)b)caca(b(bc)c)根据偏序关系的反对称性有根据偏序关系的反对称性有(a(ab)b)c ca a(b(bc)c)由对偶原理，由对偶原理，(a(ab)b)c ca a(b(bc)c)得证。得证。q 11定理定理13.113.1(3)(3)显然显然aaa,aaa,又由又由aaaa可得可得 aaaaaa。根据反对称性有根据反对称性有 aaaaa a，由对偶原理，由对
11、偶原理，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 得证。得证。q 12定理定理13.213.2定理定理13.213.2 设设S, 是具有两个二元运算的代数系统，若对是具有两个二元运算的代数系统，若对于于* *和和 运算适合运算适合交换律交换律、结合律结合律、吸收律吸收律，则可以适当定，则可以适当定义义S S中的
12、偏序中的偏序，使得，使得S, 构成一个格，且构成一个格，且a,bSa,bS有有ababa a* *b b，ababa a b b。思路思路 (1)(1)证明证明在在S S中中* *和和 运算都适合幂等律运算都适合幂等律。(2)(2)在在S S上定义二元关系上定义二元关系R R，并证明，并证明R R为偏序关系。为偏序关系。(3)(3)证明证明构成格。构成格。说明说明通过规定运算及其基本性质可以给出格的定义。通过规定运算及其基本性质可以给出格的定义。q 13定理定理13.213.2 a aSS，由吸收律得，由吸收律得(1)(1)证明在证明在S S中中* *和和 运算都适合幂等律运算都适合幂等律。a
13、 a* *a 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，即即RR，所以所以R 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=b b=b a)a)所以所以R
14、R在在S S上是反对称的。上是反对称的。q 14定理定理13.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 aRc aRc这就证明了这就证明了R R在在S S上是传递的。上是传递的。综上所述，综上所述，R R为为S S上的偏序。上的偏序。以下把以下把R R记作记作。q 15定理定理13.213.2(3) (3) 证明证明S构成格。构成格。 即证明即证明ababa a b b，ababa a* *b
15、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的上界，的上界，则有则有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的最小上界，即的最小上界，即 ababa a b b
16、为证为证a a* *b b是是a,ba,b的最大下界，的最大下界， 先证先证首先由首先由a a b bb b 可知可知 a a* *b b a a* *(a(a b)b) a a反之由反之由a a* *b ba a 可知可知a a b b (a(a* *b)b) b b b b (b(b* *a)a)b b再由式再由式(13.7)(13.7)和和的定义有的定义有 ab ab a a* *b ba a， 依照前边的证明依照前边的证明, ,类似地可证类似地可证 a a* *b b是是a,ba,b的最大下界，的最大下界， 即即 ababa a* *b b。a a b bb b a a* *b ba
17、a(13.7)(13.7)q 16格的等价定义格的等价定义根据定理根据定理13.213.2，可以给出格的另一个等价定义。，可以给出格的另一个等价定义。定义定义13.313.3 设设S, 是代数系统，是代数系统，* *和和 是二元运算，如果是二元运算，如果* *和和 满满足交换律，结合律和吸收律，则足交换律，结合律和吸收律，则S, 构成一个构成一个格格( (lattice) )。说明说明格中的幂等律可以由吸收律推出。格中的幂等律可以由吸收律推出。以后我们不再区别是偏序集定义的格，以后我们不再区别是偏序集定义的格，还是代数系统定义的格，而统称为格还是代数系统定义的格，而统称为格L L。q 17格的
18、性质格的性质定理定理13.313.3 设设L L是格，则是格，则 a,ba,bL L 有有ab ab a ab ba a a ab bb b证明证明 先证先证 ab ab a ab ba a由由aaaa和和abab可知，可知，a a是是a,ba,b的下界，的下界，故故aaaab b。显然又有显然又有a ababa。由反对称性得由反对称性得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 ab ab。由由aaaab
19、b得得 aaaab bb b。 q 18格的性质格的性质定理定理11.411.4 设设L L是格，是格， a,b,c,da,b,c,dL L，若若abab且且cdcd，则则a acbcbd d，a acbcbd d证明证明 a acabcaba accdccd因此，因此， a acbcbd d。同理可证同理可证 a acbcbd d。q 19例例13.413.4 例例13.413.4 设设L L是格，证明是格，证明 a,b,cL a,b,cL 有有a(bc)(ab)(ac)a(bc)(ab)(ac)证明证明由由 aaaa，bcbcb b 得得a(bc)aba(bc)ab由由 aaaa，bcbc
20、c c 得得a(bc)aca(bc)ac从而得到从而得到 a(bc)(ab)(ac)a(bc)(ab)(ac)说明说明在格中分配不等式成立。在格中分配不等式成立。一般说来，格中的一般说来，格中的和和运算并不是满足分配律的。运算并不是满足分配律的。q 20本节小结本节小结q 偏序集构成格的条件：任意二元子集都有最大下界和最偏序集构成格的条件：任意二元子集都有最大下界和最小上界。小上界。q 格的实例：正整数的因子格，幂集格，子群格。格的实例：正整数的因子格，幂集格，子群格。q 格的性质：对偶原理，格中算律（交换、结合、幂等、格的性质：对偶原理，格中算律（交换、结合、幂等、吸收），保序性，分配不等式
21、。吸收），保序性，分配不等式。q 格作为代数系统的定义。格作为代数系统的定义。q 格的证明方法格的证明方法q 2113.2 13.2 子格与格同态子格与格同态定义定义13.413.4 设设L, 是格，是格，S S是是L L的非空子集，若的非空子集，若S S关于关于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和
22、和f,f,有有efefc c，但但c c S S1 1。q 22格同态格同态定义定义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),(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关于通常数的小于或等于关系构成
23、格。关于通常数的小于或等于关系构成格。令令 : L: L1 1LL2 2， (x)(x)x-1x-1不难验证不难验证 是是L L1 1到到L L2 2的同态映射，因为对任意的的同态映射，因为对任意的x,yLx,yL1 1有有 (xy)(xy) (max(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)
24、(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)q 23例例13.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
25、(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 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)q 24格同态的性质格同态的性质定理定理13.513.5 设设 是格是格L L1
26、1到到L L2 2的映射，的映射，(1)(1)若若 是格同态映射，则是格同态映射，则 是保序映射，即是保序映射，即 x,yx,yL L1 1，有有xy xy (x)(x) (y)(y)(2)(2)若若 是双射，则是双射，则 是格同构映射当且仅当是格同构映射当且仅当 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)(
27、y)。q 25定理定理13.5(2)13.5(2)的证明的证明充分性。充分性。(2)(2)若若 是双射，则是双射，则 是格同构映射当且仅当是格同构映射当且仅当 x,yx,yL 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
28、和和 的满射性可知，的满射性可知，必存在必存在u uL L1 1使得使得 (u)(u) (x)(x) (y)(y)因此有因此有 (x)(x) (u)(u)， (y)(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)。q 26定理定理13.5(2)13.5(2)的证明的证明必要性。必要性。由由(1)(1)的结论必
29、有的结论必有xy xy (x)(x) (y)(y)反之，若反之，若 (x)(x) (y)(y)，由于由于 是同构映射，则是同构映射，则 (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)q 27例例13.713.7例例13.713.7 设设L L1 1S, L,D, L2 2S 是格，其中是格，其中S S1212是是1212的的所有正因子构成的集合，
30、所有正因子构成的集合，D D为整除关系，为整除关系，为通常数的小为通常数的小于或等于关系。令于或等于关系。令 : S: S1212S S1212， ( (x) )x则则 是双射，但是双射，但 不是格不是格L L1 1到到L L2 2的同构映射。的同构映射。因为因为 (2)(2) (3)(3)，但但2 2不整除不整除3 3。根据定理根据定理13.513.5可知，可知， 不是同构映射。不是同构映射。q 28格的直积格的直积类似于半群类似于半群, ,群和环群和环, ,也可以定义格的直积。也可以定义格的直积。定义定义13.613.6 设设L L1 1和和L L2 2是格，定义是格，定义L L1 1L
31、L2 2上的运算上的运算, ,：即即 a, L L1 1L L2 2 有有a a a a a a 称称L 为格为格L L1 1和和L L2 2的的直积直积。可以证明可以证明L 仍是格。仍是格。q 29格的直积格的直积 a ，a ，a L L1 1L L2 2，有有交换律交换律 a a a a a a 结合律结合律 (a( a)a a a (a a 同样同样 a (a( a)a 同理可证同理可证运算也满足交换律和结合律。运算也满足交换律和结合律。q 30格的直积格的直积吸收律吸收律 a (a( a)a a a)a 同理有同理有 a (a( a)a 这就证明了这就证明了和和运算满足吸收律。运算满足
32、吸收律。从而证明从而证明 L L1 1L L2 2仍是格仍是格q 31格的直积举例格的直积举例格格L L0,1, ，为通常的小于或等于关系。则为通常的小于或等于关系。则L LL L，其中其中是最小元，是最小元，是最大元，且是最大元，且，而而与与是不可比的。是不可比的。易见易见L LL L与图与图13.413.4的的L L1 1同构。同构。q 32本节小结本节小结q 格格L L的非空子集的非空子集S S构成构成L L的子格的条件：的子格的条件：S S对对L L的两个运算封闭。的两个运算封闭。 q 函数函数 构成格同态的条件：构成格同态的条件： (ab)(ab) (a)(a) (b)(b) (ab
33、)(ab) (a)(a) (b)(b)q 格同态的保序性。格同态的保序性。q 3313.3 13.3 分配格与有补格分配格与有补格q 一般说来，格中运算一般说来，格中运算对对满足分配不等式，满足分配不等式，即即 a,b,ca,b,cL L，有有a a(b(bc)(ac)(ab)b)(a(ac)c)但是不一定满足分配律。满足分配律的格称为但是不一定满足分配律。满足分配律的格称为分配格分配格。定义定义13.713.7 设设L, 是格，若是格，若 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
34、为为分配格分配格。说明说明上面两个等式互为对偶式。上面两个等式互为对偶式。在证明在证明L L为分配格时，只须证明其中的一个等式即可。为分配格时，只须证明其中的一个等式即可。q 34例例13.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钻石格钻石格五角格五角格q 35分配格的判别分配格的判别定理定理13.613.6 设设
35、L L是格，则是格，则L L是分配格当且仅当是分配格当且仅当L L中不含有与钻石中不含有与钻石格或五角格同构的子格。格或五角格同构的子格。证明证明略。略。推论推论(1) (1) 小于五元的格都是分配格。小于五元的格都是分配格。(2) (2) 任何一条链都是分配格。任何一条链都是分配格。q 36例例13.913.9说明下图中的格是否为分配格，为什么？说明下图中的格是否为分配格，为什么？L L1 1, L, L2 2和和L L3 3都不是分配格。都不是分配格。a,b,c,d,ea,b,c,d,e是是L L1 1的子格，并且同构于钻石格。的子格，并且同构于钻石格。a,b,c,e,fa,b,c,e,f
36、是是L L2 2的子格，并且同构于五角格。的子格，并且同构于五角格。a,c,b,e,fa,c,b,e,f是是L L3 3的子格，也同构于钻石格。的子格，也同构于钻石格。 q 37定理定理13.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)( (已知条件代入已知条件代入) ) ( (b ba a) )(b(
37、bc) c) ( (分配律分配律) ) ( (a ac c) )(b(bc c) )( (已知条件代入已知条件代入, ,交换律交换律) ) ( (a ab b) )c c ( (分配律分配律) ) (a(ac)c)c c ( (已知条件代入已知条件代入) ) c c ( (交换律交换律, ,吸收律吸收律) )q 38定理定理13.713.7充分性。充分性。假若假若 a,b,ca,b,cL L，有有a ab ba ac c且且a ab ba ac c b bc c成立，而成立，而L L不是分配格。不是分配格。根据定理根据定理13.613.6，L L中必含有与钻石格或五角格同构的子格。中必含有与钻
38、石格或五角格同构的子格。假设假设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 yq 39定理定理13.713.7的应用的应用使用定理使用定理13.713.7也可以判别一个格是否为分配格。也可以判别一个格是否为分配格。例如下图中的三个格都不是分配格。例如下图中
39、的三个格都不是分配格。在在L L1 1中有中有 bcbcbdbd，bcbcbdbd，但，但cdcd。在在L L2 2中有中有 bcbcbebe，bcbcbebe，但，但cece。在在L L3 3中有中有 cbcbcdcd，cbcbcdcd，但，但bdbd。q 40格的全下界和全上界格的全下界和全上界定义定义13.813.8 设设L L是格，是格，若存在若存在a aL L使得使得 x xL L有有axax，则称则称a a为为L L的的全下界全下界；若存在若存在b bL L使得使得 x xL L有有xbxb，则称则称b b为为L L的的全上界全上界。 命题命题格格L L若存在全下界或全上界，一定是
40、唯一的。若存在全下界或全上界，一定是唯一的。证明证明以全下界为例，假若以全下界为例，假若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。q 41有界格有界格定义定义13.913.9 设设L L是格，是格，若若L L存在全下界和全上界，则称存在全下界和全上界，则称L L为为有界格有界格，并将并将L L记为记为L,0,1。说明说明有限格有限格L L一定是有界格。一
41、定是有界格。举例举例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是有穷集还是无穷集，是有穷集还是无穷集，它都是有界格。它的全下界是空集它都是有界格。它的全下界是空集，全上界是全上界是B B。q 整数集整数集
42、Z Z关于通常数的小于或等于关系构成的格不是有界格，关于通常数的小于或等于关系构成的格不是有界格，因为不存在最小和最大的整数。因为不存在最小和最大的整数。q 42有界格的性质有界格的性质定理定理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 和和 0a0a0 0 可知可知 a a0 00 0。说明说明 在有界格中，在有界格中，全下界全下界0 0是关于是关于运算的零元，运算的零元，运算的单位元。运算的单位元。全上界全上界1 1是关于是关于运算的零元，运算的零元，运算的
43、单位元。运算的单位元。对偶原理对偶原理 对于涉及到有界格的命题，如果其中含有全下界对于涉及到有界格的命题，如果其中含有全下界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 互为对偶命题。互为对偶命题。q 43有界格中的补元有界格中的补元定义定义13.1013.10 设设L,0,1是有界格，是有界格，a aL L，若存在若存在b bL L 使得使得a ab b0 0
44、和和 a ab b1 1成立，则成立，则称称b b是是a a的的补元补元。说明说明若若b b是是a a的补元，那么的补元，那么a a也是也是b b的补元。的补元。换句话说，换句话说，a a和和b b互为补元。互为补元。q 44例例13.1013.10考虑下图中的四个格。考虑下图中的四个格。L L1 1中的中的a a与与c c互为补元，其中互为补元，其中a a为全下界，为全下界，c c为全上界，为全上界，b b没有补元。没有补元。L L2 2中的中的a a与与d d互为补元，其中互为补元，其中a a为全下界，为全下界，d d为全上界，为全上界，b b与与c c也互为也互为补元。补元。L L3 3
45、中的中的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的补元是的补元是c c和和d d，c c的补元是的补元是b b，d d的补元是的补元是b b。q 45有界格中补元的说明有界格中补元的说明在任何有界格中，在任何有界格中，q 全下全下界界0
46、0与全上界与全上界1 1互补。互补。 q 对于其他元素，可能存在补元，也可能不存在补元。对于其他元素，可能存在补元，也可能不存在补元。q 如果存在，可能是唯一的，也可能是多个补元。如果存在，可能是唯一的，也可能是多个补元。q 对于有界分配格，如果它的元素存在补元，一定是唯一的。对于有界分配格，如果它的元素存在补元，一定是唯一的。 q 46有界分配格中补元的唯一性有界分配格中补元的唯一性定理定理13.913.9 设设L,0,1是有界分配格。是有界分配格。若若aaL L，且对于，且对于a a存在补元存在补元b b，则，则b b是是a a的唯一补元。的唯一补元。证明证明假设假设cLcL也也是是a a
47、的补元，则有的补元，则有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。 q 47有补格的定义有补格的定义定义定义13.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
48、 L3 3是有补格，是有补格，L L1 1不是有补格。不是有补格。q 48本节小结本节小结q 如果格中一个运算对另一个运算是可分配的，称这个格是分如果格中一个运算对另一个运算是可分配的，称这个格是分配格。配格。 q 分配格的两种判别法：分配格的两种判别法：不存在与钻石格或五角格同构的子格；不存在与钻石格或五角格同构的子格；对于任意元素对于任意元素a,b,c,a,b,c,有有 ababacac且且ababacacb bc c。 q 有界格的定义及其实例。有界格的定义及其实例。 q 格中元素的补元及其性质（分配格中补元的唯一性）。格中元素的补元及其性质（分配格中补元的唯一性）。 q 有补格的定义。
49、有补格的定义。q 4913.4 13.4 布尔代数布尔代数定义定义13.1213.12 如果一个格是如果一个格是有补分配格有补分配格，则称它为，则称它为布尔格布尔格或或布尔布尔代数代数。说明说明在布尔代数中，每个元素都存在着唯一的补元。在布尔代数中，每个元素都存在着唯一的补元。可以把求补元的运算看作是布尔代数中的一元运算。可以把求补元的运算看作是布尔代数中的一元运算。可以把一个布尔代数标记为可以把一个布尔代数标记为B,0,1，为求补运算为求补运算, , a aB B，a a是是a a的补元。的补元。q 50例例13.1113.11例例13.1113.11 设设S S1101101,2,5,10
50、,11,22,55,1101,2,5,10,11,22,55,110是是110110的正因子集合。的正因子集合。令令gcd,lcmgcd,lcm分别表示求最大公约数和最小公倍数的运算。问分别表示求最大公约数和最小公倍数的运算。问S,gcd,lcm是否构成布尔代数？为什么？是否构成布尔代数？为什么？解答解答 证明证明S,gcd,lcm构成格。构成格。容易验证容易验证 x,y,zx,y,zS S110110，有，有gcd(x,y)gcd(x,y)S S110110lcm(x,y)lcm(x,y)S S110110gcd(x,y)gcd(x,y)gcd(y,xgcd(y,x) ) lcm(x,y)l
