离散数学第十三章格与布尔代数.ppt

《离散数学第十三章格与布尔代数.ppt》由会员分享，可在线阅读，更多相关《离散数学第十三章格与布尔代数.ppt（81页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学课件第十三章格与布离散数学课件第十三章格与布尔代数尔代数现在学习的是第1页，共81页本章内容本章内容13.1 13.1 格的定义与性质格的定义与性质13.2 13.2 子格与格同态子格与格同态13.3 13.3 分配格与有补格分配格与有补格13.4 13.4 布尔代数布尔代数本章总结本章总结作业作业现在学习的是第2页，共81页13.1 13.1 格的定义与性质格的定义与性质 定义定义13.113.1 设设是偏序集，是偏序集，如果如果 x,ySS，x,y 都有最小都有最小上界和最大下界上界和最大下界，则称，则称S S关于偏序关于偏序作成一个作成一个格格(lattice)。说明：说明：由于

2、最小上界和最大下界的唯一性，可以把求由于最小上界和最大下界的唯一性，可以把求 x,y 的最的最小上界和最大下界看成小上界和最大下界看成x x与与y y的二元运算的二元运算和和。xy：表示：表示x x与与y y的最小上界的最小上界xy：表示：表示x x和和y y的最大下界。的最大下界。本章出现的本章出现的和和符号只代表格中的运算，而不再有其它的符号只代表格中的运算，而不再有其它的含义。含义。现在学习的是第3页，共81页格的格的实实例例例例13.113.1 设设n n是正整数，是正整数，S Sn n是是n n的正因子的集合。的正因子的集合。D D为为整除关系，整除关系，则则偏序集偏序集S,D构成格

3、。构成格。x,ySx,ySn n，xyxy是是lcm(x,y)lcm(x,y)，即，即x x与与y y的最小公倍数。的最小公倍数。xyxy是是gcd(x,y)gcd(x,y)，即，即x x与与y y的最大公的最大公约约数。数。下下图给图给出了格出了格S,D，S,D和和S,D。现在学习的是第4页，共81页例例13.213.2例例13.213.2 判断下列偏序集是否构成格判断下列偏序集是否构成格,并说明理由。并说明理由。(1)P(B),(1)，其中，其中P(B)P(B)是集合是集合B B的幂集。的幂集。(2)(2)，其中，其中Z Z是整数集是整数集,为小于或等于关系。为小于或等于关系。(3)(3)

4、偏序集的哈斯图分别在下图给出。偏序集的哈斯图分别在下图给出。现在学习的是第5页，共81页例例13.213.2解答解答 (1)(1)是格。是格。x,yP(B)x,yP(B)，xyxy就是就是xyxy，xyxy就是就是xyxy。由于由于和和运算在运算在P(B)P(B)上是封闭的，所以上是封闭的，所以xyxy，xyP(B)xyP(B)。称称P(B),为为B B的的幂集格幂集格。(2)(2)是格。是格。x,yZ,xyx,yZ,xymax(x,y)max(x,y)，xyxymin(x,y)min(x,y)，它们都是整数。，它们都是整数。(3)(3)都不是格。都不是格。(a)(a)中的中的a,ba,b没有

5、最大下界。没有最大下界。(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没有最大下界。没有最大下界。现在学习的是第6页，共81页例例13.313.3例例13.3 13.3 设设G G是群，是群，L(G)L(G)是是G G的所有子群的集合。即的所有子群的集合。即L(G)L(G)H|HG H|HG 对任意的对任意的H H1 1,H,H2 2L(G)L(G)，H H1 1HH2 2也是也是G G的子群，而的子

6、群，而H 是由是由H H1 1HH2 2生成的子群（即包含着生成的子群（即包含着H H1 1HH2 2的最小的子群）。的最小的子群）。在在L(G)L(G)上定义包含关系上定义包含关系，则，则L(G)L(G)关于包含关系构成一个格，关于包含关系构成一个格，称为称为G G的的子群格子群格。易见在易见在L(G)L(G)中，中，H H1 1HH2 2就是就是H H1 1HH2 2，H H1 1HH2 2就是就是H。现在学习的是第7页，共81页对对偶原理偶原理定定义义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

8、L都有都有 a,bLa,bL，abaaba说说明明许许多格的性多格的性质质都是互都是互为对为对偶命偶命题题的。的。有了格的有了格的对对偶原理，在偶原理，在证证明格的性明格的性质时质时，只只须证须证明其中的一个命明其中的一个命题题即可。即可。现在学习的是第8页，共81页格的运算性质格的运算性质定理定理13.113.1 设设是格，则运算是格，则运算和和适合适合交换律交换律、结合结合律律、幂等律幂等律和和吸收律吸收律，即，即(1)(1)交换律交换律 a,bL a,bL 有有ababbabaababbaba(2)(2)结合律结合律 a,b,cL a,b,cL 有有(ab)c(ab)ca(bc)a(bc

9、)(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现在学习的是第9页，共81页定理定理13.113.1(1)ab(1)ab和和baba分别是分别是a,ba,b和和b,ab,a的最小上界。的最小上界。由于由于a,ba,bb,ab,a，所以，所以ababbaba。由对偶原理，由对偶原理，ababbaba得证。得证。(2)(2)由最小上界的定义有由最小上界的定义有(ab)caba(ab)caba(13.1)(13.1)(ab)cabb(a

10、b)cabb(13.2)(13.2)(ab)cc(ab)cc(13.3)(13.3)由式由式13.213.2和和13.313.3有有(ab)cbc(ab)cbc(13.4)(13.4)再由式再由式13.113.1和和13.413.4有有(ab)ca(bc)(ab)ca(bc)同理可证同理可证(ab)ca(bc)(ab)ca(bc)根据偏序关系的反对称性有根据偏序关系的反对称性有(ab)c(ab)ca(bc)a(bc)由对偶原理，由对偶原理，(ab)c(ab)ca(bc)a(bc)得证。得证。现在学习的是第10页，共81页定理定理13.113.1(3)(3)显显然然aaa,aaa,又由又由aaa

11、a可得可得 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 得得证证。现在学习的是第11页，共81页定理定理13.213.2定理定理13.213.2 设设S,*,是具有两个二元运算的代数系统，若对是具有两个二元运算的代数系统，若对于于*和

12、和 运算适合运算适合交换律交换律、结合律结合律、吸收律吸收律，则可以适当定，则可以适当定义义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)证明证明构成格。构成格。说明说明通过规定运算及其基本性质可以给出格的定义。通过规定运算及其基本性质可以给出格的定义。现在学习的是第12页，共81页定理定理13.213.2 a aS

13、S，由吸收律得，由吸收律得(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，即即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

14、 a b bb (b (由于由于a a b=b b=b a)a)所以所以R R在在S S上是反对称的。上是反对称的。现在学习的是第13页，共81页定理定理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记作记作。现在学习的是第14页，共81页定理定理13.

15、213.2(3)(3)证明证明S 构成格。构成格。即证明即证明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的上界，的上界，则有则有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，所

16、以所以a a b b是是a,ba,b的最小上界，即的最小上界，即ababa a b b为证为证a*ba*b是是a,ba,b的最大下界，的最大下界，先证先证首先由首先由a a b bb b 可知可知 a*b a*ba*(aa*(a b)b)a a反之由反之由a*ba*ba a 可知可知a a b b(a*b)(a*b)b bb b(b*a)(b*a)b b再由式再由式(13.7)(13.7)和和的定义有的定义有 ab ab a*b a*ba a，依照前边的证明依照前边的证明,类似地可证类似地可证 a*ba*b是是a,ba,b的最大下界，的最大下界，即即 ababa*ba*b。a a b bb b

17、 a*b a*ba a(13.7)(13.7)现在学习的是第15页，共81页格的等价定义格的等价定义根据定理根据定理13.213.2，可以给出格的另一个等价定义。，可以给出格的另一个等价定义。定义定义13.313.3 设设S,*,是代数系统，是代数系统，*和和 是二元运算，如果是二元运算，如果*和和 满满足交换律，结合律和吸收律，则足交换律，结合律和吸收律，则S,*,构成一个构成一个格格(lattice)。说明说明格中的幂等律可以由吸收律推出。格中的幂等律可以由吸收律推出。以后我们不再区别是偏序集定义的格，以后我们不再区别是偏序集定义的格，还是代数系统定义的格，而统称为格还是代数系统定义的格，

18、而统称为格L L。现在学习的是第16页，共81页格的性质格的性质定理定理13.313.3 设设L L是格，则是格，则 a,bL a,bL 有有ab ab ababa a ab abb b证明证明 先证先证 ab ab ab aba a由由aaaa和和abab可知，可知，a a是是a,ba,b的下界，的下界，故故aabaab。显然又有。显然又有abaaba。由反对称性得由反对称性得ababa a。再证再证 ababa a ab abb b。根据吸收律有根据吸收律有 b bb(ba)b(ba)由由ababa a得得 b bba,ba,即即ababb b。最后证最后证ababb b ab ab。由由

19、aabaab得得 aabaabb b。现在学习的是第17页，共81页格的性质格的性质定理定理11.411.4 设设L L是格，是格，a,b,c,dLa,b,c,dL，若，若abab且且cdcd，则，则acbdacbd，acbdacbd证明证明 acabacabaccdaccd因此，因此，acbdacbd。同理可证同理可证 acbdacbd。现在学习的是第18页，共81页例例13.413.4例例13.413.4 设设L L是格，证明是格，证明 a,b,cL a,b,cL 有有a(bc)(ab)(ac)a(bc)(ab)(ac)证明证明由由 aaaa，bcb bcb 得得a(bc)aba(bc)a

20、b由由 aaaa，bcc bcc 得得a(bc)aca(bc)ac从而得到从而得到 a(bc)(ab)(ac)a(bc)(ab)(ac)说明说明在格中分配不等式成立。在格中分配不等式成立。一般说来，格中的一般说来，格中的和和运算并不是满足分配律的。运算并不是满足分配律的。现在学习的是第19页，共81页本节小结本节小结q偏偏序序集集构构成成格格的的条条件件：任任意意二二元元子子集集都都有有最最大大下下界界和和最最小小上界。上界。q格的实例：正整数的因子格，幂集格，子群格。格的实例：正整数的因子格，幂集格，子群格。q格格的的性性质质：对对偶偶原原理理，格格中中算算律律（交交换换、结结合合、幂幂等等

21、、吸吸收），保序性，分配不等式。收），保序性，分配不等式。q格作为代数系统的定义。格作为代数系统的定义。q格的证明方法格的证明方法现在学习的是第20页，共81页13.2 13.2 子格与格同态子格与格同态定义定义13.413.4 设设是格，是格，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

22、的子格。的子格。因为对于因为对于e e和和f,f,有有efefc c，但但c c S S1 1。现在学习的是第21页，共81页格同态格同态定义定义13.513.5 设设L L1 1和和L L2 2是格，是格，:L:L1 1LL2 2，若，若 a,bLa,bL1 1 有有(ab)(ab)(a)(a)(b),(b),(ab)(ab)(a)f(b)(a)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

23、 L2 2关于通常数的小于或等于关系构成格。关于通常数的小于或等于关系构成格。令令 :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)

24、(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即即 (xy)(xy)(x)(x)(y),(y),(xy)(xy)(x)(x)(y)(y)现在学习的是第22页，共81页例例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

25、 2,2 2(c)(c)c c2 2，2 2(d)(d)d d2 2则则 1 1和和 2 2都不是格同态，因为都不是格同态，因为 1 1(bc)(bc)1 1(d)(d)d d1 1 1 1(b)(b)1 1(c)(c)a a1 1aa1 1a a1 1 2 2(bc)(bc)2 2(d)(d)d d2 2 2 2(b)(b)2 2(c)(c)b b2 2cc2 2c c2 2从而从而 1 1(bc)(bc)1 1(b)(b)1 1(c)(c)2 2(bc)(bc)2 2(b)(b)2 2(c)(c)现在学习的是第23页，共81页格同态的性质格同态的性质定理定理13.513.5 设设 是格是格

26、L L1 1到到L L2 2的映射，的映射，(1)(1)若若 是格同态映射，则是格同态映射，则 是保序映射，即是保序映射，即 x,yLx,yL1 1，有，有xy xy (x)(x)(y)(y)(2)(2)若若 是双射，则是双射，则 是格同构映射当且仅当是格同构映射当且仅当 x,yLx,yL1 1，有，有xy xy (x)(x)(y)(y)证明证明 (1)(1)任取任取x,yLx,yL1 1，xyxy，由格的性质知由格的性质知 xyxyy y。又由于又由于 是格同态映射，必有是格同态映射，必有(y)(y)(xy)(xy)(x)(x)(y)(y)从而得到从而得到(x)(x)(y)(y)。现在学习的

27、是第24页，共81页定理定理13.5(2)13.5(2)的证明的证明充分性。充分性。(2)(2)若若 是双射，则是双射，则 是格同构映射当且仅当是格同构映射当且仅当 x,yLx,yL1 1，有，有xy xy (x)(x)(y)(y)只须证明只须证明 是是L L1 1到到L L2 2的同态映射即可。的同态映射即可。任取任取x,yLx,yL1 1，令令xyxyz z，由，由 xzxz和和yz yz 知知(x)(x)(z)(z)，(y)(y)(z)(z)从而有从而有 (x)(x)(y)(y)(z)(z)(xy)(xy)另一方面，由另一方面，由(x)(x)(y)L(y)L2 2和和 的满射性可知，的满

28、射性可知，必存在必存在uLuL1 1使得使得(u)(u)(x)(x)(y)(y)因此有因此有 (x)(x)(u)(u)，(y)(y)(u)(u)。由已知条件可得由已知条件可得 xuxu，yuyu。从而推出从而推出 xyuxyu。再次使用已知条件得再次使用已知条件得(xy)(xy)(u)(u)(x)(x)(y)(y)。综合上述有综合上述有 (xy)(xy)(x)(x)(y)(y)。同理可证同理可证 (xy)(xy)(x)(x)(y)(y)。现在学习的是第25页，共81页定理定理13.5(2)13.5(2)的证明的证明必要性。必要性。由由(1)(1)的结论必有的结论必有xy xy (x)(x)(y

29、)(y)反之，若反之，若(x)(x)(y)(y)，由于，由于 是同构映射，则是同构映射，则(xy)(xy)(x)(x)(y)(y)(y)(y)又由于又由于 是双射，必有是双射，必有xyxyy y。从而证明了从而证明了 xyxy。(2)(2)若若 是双射，则是双射，则 是格同构映射当且仅当是格同构映射当且仅当 x,yLx,yL1 1，有，有xy xy (x)(x)(y)(y)现在学习的是第26页，共81页例例13.713.7例例13.713.7 设设L L1 1S,L,D,L2 2S,是格，其中是格，其中S S1212是是1212的的所有正因子构成的集合，所有正因子构成的集合，D D为整除关系，

30、为整除关系，为通常数的小为通常数的小于或等于关系。令于或等于关系。令:S:S1212SS1212，(x)x则则 是双射，但是双射，但 不是格不是格L L1 1到到L L2 2的同构映射。的同构映射。因为因为(2)(2)(3)(3)，但，但2 2不整除不整除3 3。根据定理根据定理13.513.5可知，可知，不是同构映射。不是同构映射。现在学习的是第27页，共81页格的直积格的直积类似于半群类似于半群,群和环群和环,也可以定义格的直积。也可以定义格的直积。定义定义13.613.6 设设L L1 1和和L L2 2是格，定义是格，定义L L1 1L L2 2上的运算上的运算,：即即 a,L L1

31、1LL2 2 有有a a a a 称称L,为格为格L L1 1和和L L2 2的的直积直积。可以证明可以证明L,仍是格。仍是格。现在学习的是第28页，共81页格的直积格的直积 a，a，aLL1 1LL2 2，有，有交换律交换律 a a a a 结合律结合律 (a()a(a a 同样同样a()a 同理可证同理可证运算也满足交换律和结合律。运算也满足交换律和结合律。现在学习的是第29页，共81页格的直积格的直积吸收律吸收律 a()a a)a 同理有同理有a()a 这就证明了这就证明了和和运算满足吸收律。运算满足吸收律。从而证明从而证明 L L1 1LL2 2仍是格仍是格现在学习的是第30页，共81

32、页格的直积举例格的直积举例格格L L，为通常的小于或等于关系。则为通常的小于或等于关系。则LLLL，其中其中是最小元，是最小元，是最大元，且是最大元，且，而而与与是不可比的。是不可比的。易见易见LLLL与图与图13.413.4的的L L1 1同构。同构。现在学习的是第31页，共81页本节小结本节小结q格格L L的非空子集的非空子集S S构成构成L L的子格的条件：的子格的条件：S S对对L L的两个运算封闭。的两个运算封闭。q函数函数 构成格同态的条件：构成格同态的条件：(ab)(ab)(a)(a)(b)(b)(ab)(ab)(a)(a)(b)(b)q格同态的保序性。格同态的保序性。现在学习的

33、是第32页，共81页13.3 13.3 分配格与有补格分配格与有补格q一般说来，格中运算一般说来，格中运算对对满足分配不等式，满足分配不等式，即即 a,b,cLa,b,cL，有，有a(bc)(ab)(ac)a(bc)(ab)(ac)但是不一定满足分配律。满足分配律的格称为但是不一定满足分配律。满足分配律的格称为分配格分配格。定义定义13.713.7 设设是格，若是格，若 a,b,cLa,b,cL，有，有a(bc)a(bc)(ab)(ac)(ab)(ac)a(bc)a(bc)(ab)(ac)(ab)(ac)则称则称L L为为分配格分配格。说明说明上面两个等式互为对偶式。上面两个等式互为对偶式。在

34、证明在证明L L为分配格时，只须证明其中的一个等式即可。为分配格时，只须证明其中的一个等式即可。现在学习的是第33页，共81页例例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钻石格钻石格五角格五角格现在学习的是第34页，共81页分配格的判别分配格的判别定理定理13.613.6 设设L L是格，则是格，则L L是分配格当且

35、仅当是分配格当且仅当L L中不含有与钻石中不含有与钻石格或五角格同构的子格。格或五角格同构的子格。证明证明略。略。推论推论(1)(1)小于五元的格都是分配格。小于五元的格都是分配格。(2)(2)任何一条链都是分配格。任何一条链都是分配格。现在学习的是第35页，共81页例例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是是L L2 2的子格，并且同

36、构于五角格。的子格，并且同构于五角格。a,c,b,e,fa,c,b,e,f是是L L3 3的子格，也同构于钻石格。的子格，也同构于钻石格。现在学习的是第36页，共81页定理定理13.713.7定理定理13.713.7 格格L L是分配格是分配格 当且仅当当且仅当 a,b,cLa,b,cL，ababacac且且ababac ac b bc c。证明证明 必要性必要性。a,b,cLa,b,cL，有，有b b b(b(abab)(吸收律吸收律,交换律交换律)bb(ac)(ac)(已知条件代入已知条件代入)(baba)(bc)(bc)(分配律分配律)(a acc)(b)(bcc)(已知条件代入已知条件

37、代入,交换律交换律)(abab)c)c(分配律分配律)(ac)c(ac)c (已知条件代入已知条件代入)c c(交换律交换律,吸收律吸收律)现在学习的是第37页，共81页定理定理13.713.7充分性。充分性。假若假若 a,b,cLa,b,cL，有，有ababacac且且ababaac c b bc c成立，而成立，而L L不是分配格。不是分配格。根据定理根据定理13.613.6，L L中必含有与钻石格或五角格同构的子格。中必含有与钻石格或五角格同构的子格。假设假设L L中含有与钻石格同构的子格，且该子格为中含有与钻石格同构的子格，且该子格为u,v,x,y,zu,v,x,y,z，其中其中u u

38、为它的最小元，为它的最小元，v v为它的最大元。为它的最大元。从而推出从而推出xyxyxzxzu u，xyxyxzxzv v但但yzyz，与已知矛盾。，与已知矛盾。对五角格的情况同理可证。对五角格的情况同理可证。v vu ux xz zy y现在学习的是第38页，共81页定理定理13.713.7的应用的应用使用定理使用定理13.713.7也可以判别一个格是否为分配格。也可以判别一个格是否为分配格。例如下图中的三个格都不是分配格。例如下图中的三个格都不是分配格。在在L L1 1中有中有 bcbcbdbd，bcbcbdbd，但，但cdcd。在在L L2 2中有中有 bcbcbebe，bcbcbeb

39、e，但，但cece。在在L L3 3中有中有 cbcbcdcd，cbcbcdcd，但，但bdbd。现在学习的是第39页，共81页格的全下界和全上界格的全下界和全上界定义定义13.813.8 设设L L是格，是格，若存在若存在aLaL使得使得 xLxL有有axax，则称，则称a a为为L L的的全下界全下界；若存在若存在bLbL使得使得 xLxL有有xbxb，则称，则称b b为为L L的的全上界全上界。命题命题格格L L若存在全下界或全上界，一定是唯一的。若存在全下界或全上界，一定是唯一的。证明证明以全下界为例，假若以全下界为例，假若a a1 1和和a a2 2都是格都是格L L的全下界的全下界

40、,则有则有a a1 1aa2 2和和a a2 2aa1 1。根据偏序关系的反对称性必有根据偏序关系的反对称性必有a a1 1a a2 2。记法记法将格将格L L的的全下界记为全下界记为0 0，全上界记为全上界记为1 1。现在学习的是第40页，共81页有界格有界格定义定义13.913.9 设设L L是格，若是格，若L L存在全下界和全上界，则称存在全下界和全上界，则称L L为为有界格有界格，并将并将L L记为记为。说明说明有限格有限格L L一定是有界格。一定是有界格。举例举例q设设L L是是n n元格元格，且，且L Laa1 1,a,a2 2,a,an n，那么，那么a a1 1aa2 2aan

41、 n是是L L的全的全下界，而下界，而a a1 1aa2 2aan n是是L L的全上界。因此的全上界。因此L L是有界格。是有界格。q对于对于无限格无限格L L来说，有的是有界格，有的不是有界格。来说，有的是有界格，有的不是有界格。q如集合如集合B B的的幂集格幂集格，不管，不管B B是有穷集还是无穷集，是有穷集还是无穷集，它都是有界格。它的全下界是空集它都是有界格。它的全下界是空集，全上界是全上界是B B。q整数集整数集Z Z关于通常数的小于或等于关系构成的格不是有界格，因关于通常数的小于或等于关系构成的格不是有界格，因为不存在最小和最大的整数。为不存在最小和最大的整数。现在学习的是第41

42、页，共81页有界格的性质有界格的性质定理定理13.813.8 设设是有界格，则是有界格，则 aLaL有有a0a00 0a0a0a aa1a1a aa1a11 1证明证明由由 a00 a00 和和 0a0 0a0 可知可知 a0a00 0。说明说明 在有界格中，在有界格中，全下界全下界0 0是关于是关于运算的零元，运算的零元，运算的单位元。运算的单位元。全上界全上界1 1是关于是关于运算的零元，运算的零元，运算的单位元。运算的单位元。对偶原理对偶原理 对于涉及到有界格的命题，如果其中含有全下界对于涉及到有界格的命题，如果其中含有全下界0 0或或全上界全上界1 1，在求该命题的对偶命题时，必须将，

43、在求该命题的对偶命题时，必须将0 0替换成替换成1 1，而，而将将1 1替换成替换成0 0。例如例如a0a00 0 和和 a1a11 1 互为对偶命题，互为对偶命题，a0a0a a 和和 a1a1a a 互为对偶命题。互为对偶命题。现在学习的是第42页，共81页有界格中的补元有界格中的补元定义定义13.1013.10 设设是有界格，是有界格，aLaL，若存在若存在bL bL 使得使得abab0 0 和和 abab1 1成立，则称成立，则称b b是是a a的的补元补元。说明说明若若b b是是a a的补元，那么的补元，那么a a也是也是b b的补元。的补元。换句话说，换句话说，a a和和b b互为

44、补元。互为补元。现在学习的是第43页，共81页例例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中的中的a a与与e e互为补元，其中互为补元，其中a a为全下界，为全下界，e e为全上界，为全上界，b b的补元是的补元是c c和和d d，c c的的补元是补元是b b和和d

45、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。现在学习的是第44页，共81页有界格中补元的说明有界格中补元的说明在任何有界格中，在任何有界格中，q全下界全下界0 0与全上界与全上界1 1互补。互补。q对于其他元素，可能存在补元，也可能不存在补元。对于其他元素，可能存在补元，也可能不存在补元。q如果存在，可能是唯一的，也可

46、能是多个补元。如果存在，可能是唯一的，也可能是多个补元。q对于有界分配格，如果它的元素存在补元，一定是唯一的。对于有界分配格，如果它的元素存在补元，一定是唯一的。现在学习的是第45页，共81页有界分配格中补元的唯一性有界分配格中补元的唯一性定理定理13.913.9 设设是有界分配格。是有界分配格。若若aLaL，且对于，且对于a a存在补元存在补元b b，则，则b b是是a a的唯一补元。的唯一补元。证明证明假设假设cLcL也是也是a a的补元，则有的补元，则有acac1 1，acac0 0又知又知b b是是a a的补元，故的补元，故abab1 1，abab0 0 从而得到从而得到acacaba

47、b，acacab ab 由于由于L L是分配格，根据定理是分配格，根据定理13.713.7，b bc c。现在学习的是第46页，共81页有补格的定义有补格的定义定义定义13.1113.11 设设是有界格，若是有界格，若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不是有补格。不是有补格。现在学习的是第47页，共81页本节小结本节小结q如如果果格格中中一一个个运运算算对对另另一一个个运运算算是是可可分

48、分配配的的，称称这这个个格格是是分分配格。配格。q分配格的两种判别法：分配格的两种判别法：不存在与钻石格或五角格同构的子格；不存在与钻石格或五角格同构的子格；对于任意元素对于任意元素a,b,c,a,b,c,有有 ababacac且且ababacacb bc c。q有界格的定义及其实例。有界格的定义及其实例。q格中元素的补元及其性质（分配格中补元的唯一性）。格中元素的补元及其性质（分配格中补元的唯一性）。q有补格的定义。有补格的定义。现在学习的是第48页，共81页13.4 13.4 布尔代数布尔代数定义定义13.1213.12 如果一个格是如果一个格是有补分配格有补分配格，则称它为，则称它为布尔

49、格布尔格或或布尔布尔代数代数。说明说明在布尔代数中，每个元素都存在着唯一的补元。在布尔代数中，每个元素都存在着唯一的补元。可以把求补元的运算看作是布尔代数中的一元运算。可以把求补元的运算看作是布尔代数中的一元运算。可以把一个布尔代数标记为可以把一个布尔代数标记为B,0,1，为求补运算为求补运算,aBaB，a a是是a a的补元。的补元。现在学习的是第49页，共81页例例13.1113.11例例13.1113.11 设设S S1101101,2,5,10,11,22,55,1101,2,5,10,11,22,55,110是是110110的正因子集合。的正因子集合。令令gcd,lcmgcd,lcm

50、分别表示求最大公约数和最小公倍数的运算。问分别表示求最大公约数和最小公倍数的运算。问S,gcd,lcm是否构成布尔代数？为什么？是否构成布尔代数？为什么？解答解答 证明证明S,gcd,lcm构成格。构成格。容易验证容易验证 x,y,zSx,y,zS110110，有，有gcd(x,y)Sgcd(x,y)S110110lcm(x,y)Slcm(x,y)S110110gcd(x,y)gcd(x,y)gcd(y,x)gcd(y,x)lcm(x,y)lcm(x,y)lcm(y,x)lcm(y,x)gcd(gcd(x,y),z)gcd(gcd(x,y),z)gcd(x,gcd(y,z)gcd(x,gcd(