第11章格与布尔代数精选文档.ppt

《第11章格与布尔代数精选文档.ppt》由会员分享，可在线阅读，更多相关《第11章格与布尔代数精选文档.ppt（37页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第11章格与布尔代数章格与布尔代数1本讲稿第一页，共三十七页11.1 格的定义与性质格的定义与性质 定义定义11.1设设是偏序集，如果是偏序集，如果 x,y S，x,y都有最小上都有最小上界和最大下界，则称界和最大下界，则称S关于偏序关于偏序 作成一个作成一个格格.求求x,y最小上界和最大下界看成最小上界和最大下界看成x 与与y 的二元运算的二元运算和和，例例1设设n是正整数，是正整数，Sn是是n的正因子的集合的正因子的集合.D为整除关系，则为整除关系，则偏序集偏序集构成格构成格.x,ySn，xy是是lcm(x,y)，即，即x与与y的的最小公倍数最小公倍数.xy是是gcd(x,y)，即，即x

2、与与y的最大公约数的最大公约数.2本讲稿第二页，共三十七页图2例例2判断下列偏序集是否构成格，并说明理由判断下列偏序集是否构成格，并说明理由.(1)，其中，其中P(B)是集合是集合B的幂集的幂集.(2)，其中，其中Z是整数集，是整数集，为小于或等于关系为小于或等于关系.(3)偏序集的哈斯图分别在下图给出偏序集的哈斯图分别在下图给出.实例实例(1)幂集格幂集格.x,yP(B)，xy就是就是xy，xy就是就是xy.(2)是格是格.x,yZ，xy=max(x,y)，xy=min(x,y)，(3)都不是格都不是格.可以找到两个结点缺少最大下界或最小上界可以找到两个结点缺少最大下界或最小上界3本讲稿第三

3、页，共三十七页实例：子群格实例：子群格例例3设设G是群，是群，L(G)是是G 的所有子群的集合的所有子群的集合.即即L(G)=H|HG，对任意的对任意的H1,H2L(G)，H1H2是是G 的子群，的子群，是由是由H1H2生成的子群（即包含着生成的子群（即包含着H1H2的最小子群）的最小子群）.在在L(G)上定义包含关系上定义包含关系，则，则L(G)关于包含关系构成一个关于包含关系构成一个格，称为格，称为G的子群格的子群格.在在L(G)中，中，H1H2就是就是H1H2 H1H2就是就是4本讲稿第四页，共三十七页格的性质：对偶原理格的性质：对偶原理定义定义11.2设设f 是含有格中元素以及符号是含

4、有格中元素以及符号=,和和的命题的命题.令令f*是将是将f 中的中的 替换成替换成,替换成替换成,替换成替换成,替换成替换成所得到的命题所得到的命题.称称f*为为f 的的对偶命题对偶命题.例如例如,在格中令在格中令f 是是(ab)c c,f*是是(ab)c c.格的格的对偶原理对偶原理 设设f 是含有格中元素以及符号是含有格中元素以及符号=,和和等的命题等的命题.若若f 对对一切格为真一切格为真,则则f 的对偶命题的对偶命题f*也对一切格为真也对一切格为真.例如例如,如果对一切格如果对一切格L都有都有 a,bL,ab a，那么对一切格那么对一切格L都有都有 a,bL,ab a l注意：对偶是相

5、互的，即注意：对偶是相互的，即(f*)*=f5本讲稿第五页，共三十七页格的性质：算律格的性质：算律定理定理11.1设设是格是格,则运算则运算和和适合交换律、结合律、适合交换律、结合律、幂等律和吸收律幂等律和吸收律,即即(1)a,bL有有 ab=ba,ab=ba(2)a,b,cL有有(ab)c=a(bc),(ab)c=a(bc)(3)aL有有aa=a,aa=a(4)a,bL有有a(ab)=a,a(ab)=a6本讲稿第六页，共三十七页证明证明(1)ab是是a,b 的最小上界的最小上界,ba是是b,a 的最小上界的最小上界.由于由于a,b=b,a,所以所以ab=ba.由对偶原理由对偶原理,ab=ba

6、.(2)由最小上界的定义有由最小上界的定义有(ab)c ab a(1)(ab)c ab b(2)(ab)c c(3)由式由式(2)和和(3)有有(ab)c bc(4)由式由式(1)和和(4)有有(ab)c a(bc)同理可证同理可证(ab)c a(bc)根据反对称性根据反对称性(ab)c=a(bc)由对偶原理由对偶原理,(ab)c=a(bc)7本讲稿第七页，共三十七页证明证明(3)显然显然a aa,又由又由a a 可得可得aa a.根据反对称性有根据反对称性有aa=a.由对偶原理由对偶原理,aa=a 得证得证.(4)显然显然a(ab)a(5)由由a a,ab a 可得可得a(ab)a(6)由式

7、由式(5)和和(6)可得可得a(ab)=a,根据对偶原理根据对偶原理,a(ab)=a8本讲稿第八页，共三十七页格的性质：序与运算的关系格的性质：序与运算的关系定理定理11.2设设L是格是格,则则 a,bL有有a bab=aab=b证证(1)先证先证a bab=a由由a a 和和a b 可知可知a 是是a,b 的下界的下界,故故a ab.显然有显然有ab a.由反对称性得由反对称性得ab=a.(2)再证再证ab=aab=b根据吸收律有根据吸收律有b=b(ba)由由ab=a 和上面的等式得和上面的等式得b=ba,即即ab=b.(3)最后证最后证ab=ba b由由a ab 得得a ab=b 9本讲稿

8、第九页，共三十七页格的性质：保序格的性质：保序定理定理11.3设设L是格是格,a,b,c,dL，若若a b 且且c d,则则ac bd,ac bd例例4设设L是格是格,证明证明 a,b,cL有有 a(bc)(ab)(ac).证证ac a b,ac c d 因此因此ac bd.同理可证同理可证ac bd 证证由由a a,bc b得得a(bc)ab由由a a,bc c得得a(bc)ac从而得到从而得到a(bc)(ab)(ac)注意：一般说来注意：一般说来,格中的格中的和和运算不满足分配律运算不满足分配律.10本讲稿第十页，共三十七页格作为代数系统的定义格作为代数系统的定义定理定理11.4设设是具有

9、两个二元运算的代数系统是具有两个二元运算的代数系统,若对于若对于 和和运算适合交换律、结合律、吸收律运算适合交换律、结合律、吸收律,则可以适当定义则可以适当定义S中中的偏序的偏序,使得使得构成格构成格,且且 a,bS 有有ab=a b,ab=ab.证明省略证明省略.根据定理根据定理11.4,可以给出格的另一个等价定义可以给出格的另一个等价定义.定义定义11.3设设是代数系统是代数系统,和和是二元运算是二元运算,如果如果 和和满足交换律、结合律和吸收律满足交换律、结合律和吸收律,则则构成格构成格.11本讲稿第十一页，共三十七页子格及其判别法子格及其判别法定义定义11.4设设是格是格,S是是L的非

10、空子集的非空子集,若若S关于关于L中的运中的运算算和和仍构成格仍构成格,则称则称S是是L的的子格子格.例例5设格设格L如图所示如图所示.令令 S1=a,e,f,g,S2=a,b,e,gS1不是不是L的子格的子格,因为因为e,f S1但但ef=c S1.S2是是L的子格的子格.12本讲稿第十二页，共三十七页11.2分配格、有补格与布尔代数分配格、有补格与布尔代数 定义定义11.5设设是格是格,若若 a,b,cL,有有a(bc)=(ab)(ac)a(bc)=(ab)(ac)则称则称L为为分配格分配格.l注意：可以证明以上两个条件互为充分必要条件注意：可以证明以上两个条件互为充分必要条件L1和和L2

11、是分配格是分配格,L3和和L4不是分配格不是分配格.称称L3为为钻石格钻石格,L4为为五角格五角格.实例实例13本讲稿第十三页，共三十七页分配格的判别及性质分配格的判别及性质定理定理11.5设设L是格是格,则则L是分配格当且仅当是分配格当且仅当L不含有与钻石格不含有与钻石格或五角格同构的子格或五角格同构的子格.证明省略证明省略.推论推论(1)小于五元的格都是分配格小于五元的格都是分配格.(2)任何一条链都是分配格任何一条链都是分配格.例例6 说明图中的格是否为分配格说明图中的格是否为分配格,为什么？为什么？解解都不是分配格都不是分配格.a,b,c,d,e 是是L1的子格的子格,同构于钻石格同构

12、于钻石格a,b,c,e,f 是是L2的子格的子格,同构于五角格；同构于五角格；a,c,b,e,f 是是L3的子格的子格同构于钻石格同构于钻石格.14本讲稿第十四页，共三十七页有界格的定义有界格的定义定义定义11.6设设L是格是格,(1)若存在若存在aL使得使得 xL有有a x,则称则称a为为L的的全下界全下界(2)若存在若存在bL使得使得 xL有有x b,则称则称b为为L的的全上界全上界说明：说明：l格格L若存在全下界或全上界若存在全下界或全上界,一定是惟一的一定是惟一的.l一般将格一般将格L的全下界记为的全下界记为0,全上界记为全上界记为1.定义定义11.7设设L是格是格,若若L存在全下界和

13、全上界存在全下界和全上界,则称则称L 为为有界有界格格,一般将有界格一般将有界格L记为记为.15本讲稿第十五页，共三十七页 定理定理11.6设设是有界格是有界格,则则 aL有有a0=0,a0=a,a1=a,a1=1注意：注意：l有限格有限格L=a1,a2,an是有界格是有界格,a1a2an是是L的全下界的全下界,a1a2an是是L的全上界的全上界.l0是关于是关于运算的零元运算的零元,运算的单位元；运算的单位元；1是关于是关于运算的零元运算的零元,运算的单位元运算的单位元.l对于涉及到有界格的命题对于涉及到有界格的命题,如果其中含有全下界如果其中含有全下界0或全上界或全上界1,在求在求该命题的

14、对偶命题时该命题的对偶命题时,必须将必须将0替换成替换成1,而将而将1替换成替换成0.有界格的性质有界格的性质16本讲稿第十六页，共三十七页有界格中的补元及实例有界格中的补元及实例定义定义11.8设设是有界格是有界格,aL,若存在若存在bL使得使得ab=0和和ab=1成立成立,则称则称b是是a的的补元补元.l注意：若注意：若b是是a的补元的补元,那么那么a也是也是b的补元的补元.a和和b互为补元互为补元.例例7考虑下图中的格考虑下图中的格.针对不同的元素，求出所有的补元针对不同的元素，求出所有的补元.17本讲稿第十七页，共三十七页解答解答(1)L1中中a 与与c 互为补元互为补元,其中其中a

15、为全下界为全下界,c为全上界为全上界,b 没有没有补元补元.(2)L2中中a 与与d 互为补元互为补元,其中其中a 为全下界为全下界,d 为全上界为全上界,b与与c也互为补元也互为补元.(3)L3中中a 与与e 互为补元互为补元,其中其中a 为全下界为全下界,e 为全上界为全上界,b 的补的补元是元是c 和和d;c 的补元是的补元是b 和和d;d 的补元是的补元是b 和和c;b,c,d 每个元素都有两个补元每个元素都有两个补元.(4)L4中中a 与与e 互为补元互为补元,其中其中a 为全下界为全下界,e 为全上界为全上界,b 的补的补元是元是c 和和d;c 的补元是的补元是b;d 的补元是的补

16、元是b.18本讲稿第十八页，共三十七页有界分配格的补元惟一性有界分配格的补元惟一性定理定理11.7设设是有界分配格是有界分配格.若若L中元素中元素a 存在存在补元补元,则存在惟一的补元则存在惟一的补元.证证假设假设c 是是a 的补元的补元,则有则有ac=1,ac=0,又知又知b 是是a 的补元的补元,故故ab=1,ab=0从而得到从而得到ac=ab,ac=ab,由于由于L是分配格是分配格,b=c.注意：注意：l在任何有界格中在任何有界格中,全下界全下界0与全上界与全上界1互补互补.l对于一般元素对于一般元素,可能存在补元可能存在补元,也可能不存在补元也可能不存在补元.如果存在如果存在补元补元,

17、可能是惟一的可能是惟一的,也可能是多个补元也可能是多个补元.对于有界分配格对于有界分配格,如果元素存在补元如果元素存在补元,一定是惟一的一定是惟一的.19本讲稿第十九页，共三十七页图9有补格的定义有补格的定义定义定义11.9设设是有界格是有界格,若若L中所有元素都有补中所有元素都有补元存在元存在,则称则称L为为有补格有补格.例如例如,图中的图中的L2,L3和和L4是有补格是有补格,L1不是有补格不是有补格.20本讲稿第二十页，共三十七页布尔代数的定义与实例布尔代数的定义与实例定义定义11.10 如果一个格是有补分配格如果一个格是有补分配格,则称它为布尔格或布则称它为布尔格或布尔代数尔代数.布尔

18、代数标记为布尔代数标记为,为求补运算为求补运算.例例8设设S110=1,2,5,10,11,22,55,110是是110的正因子集合，的正因子集合，gcd表示求最大公约数的运算，表示求最大公约数的运算，lcm表示求最小公倍数的运算，问表示求最小公倍数的运算，问是否构成布尔代数？为什么？是否构成布尔代数？为什么？解解(1)不难验证不难验证S110关于关于gcd和和lcm运算构成格运算构成格.(略略)(2)验证分配律验证分配律 x,y,zS110有有gcd(x,lcm(y,z)=lcm(gcd(x,y),gcd(x,z)(3)验证它是有补格验证它是有补格,1作为作为S110中的全下界中的全下界,1

19、10为全上界为全上界,1和和110互为补元互为补元,2和和55互为补元互为补元,5和和22互为补元互为补元,10和和11互为补元互为补元,从而证明了从而证明了为布尔代数为布尔代数.21本讲稿第二十一页，共三十七页实例实例例例9设设B为任意集合为任意集合,证明证明B的幂集格的幂集格构成布尔代数构成布尔代数,称为集合代数称为集合代数.证证(1)P(B)关于关于和和构成格构成格,因为因为和和运算满足交换律运算满足交换律,结合律和吸收律结合律和吸收律.(2)由于由于和和互相可分配互相可分配,因此因此P(B)是分配格是分配格.(3)全下界是空集全下界是空集,全上界是全上界是B.(4)根据绝对补的定义根据

20、绝对补的定义,取全集为取全集为B,xP(B),x是是x的补元的补元.从而证明从而证明P(B)是有补分配格是有补分配格,即布尔代数即布尔代数.22本讲稿第二十二页，共三十七页布尔代数的性质布尔代数的性质定理定理11.8设设是布尔代数是布尔代数,则则(1)aB,(a)=a.(2)a,bB,(ab)=a b,(ab)=a b（德摩（德摩根律）根律）证证(1)(a)是是a 的补元的补元,a也是也是a 的补元的补元.由补元惟一性得由补元惟一性得(a)=a.(2)对任意对任意a,bB有有(ab)(a b)=(aa b)(ba b)=(1b)(a 1)=11=1,(ab)(a b)=(aba)(abb)=(

21、0b)(a0)=00=0a b 是是ab的补元的补元,根据补元惟一性有根据补元惟一性有(ab)=a b,同理同理可证可证(ab)=a b.l注意：德摩根律对有限个元素也是正确的注意：德摩根律对有限个元素也是正确的.23本讲稿第二十三页，共三十七页布尔代数作为代数系统的定义布尔代数作为代数系统的定义定义定义11.11设设是代数系统是代数系统,和和是二元运算是二元运算.若若 和和运运算满足：算满足：(1)交换律交换律,即即 a,bB有有a b=b a,ab=ba(2)分配律分配律,即即 a,b,cB有有a(bc)=(a b)(a c),a(b c)=(ab)(ac)(3)同一律同一律,即存在即存在

22、0,1B,使得使得 aB有有a 1=a,a0=a(4)补元律补元律,即即 aB,存在存在a B 使得使得a a=0,aa=1则称则称是一个布尔代数是一个布尔代数.可以证明，布尔代数的两种定义是等价的可以证明，布尔代数的两种定义是等价的.24本讲稿第二十四页，共三十七页有限布尔代数的结构有限布尔代数的结构定义定义11.12设设L 是格是格,0L,若若 bL有有0 b a b=a,则则称称a 是是L 中的中的原子原子.实例：实例：(1)L是正整数是正整数n 的全体正因子关于整除关系构成的的全体正因子关于整除关系构成的格格,则则L的原子恰为的原子恰为n的全体素因子的全体素因子.(2)若若L是是B的幂

23、集的幂集,则则L的原子就是的原子就是B中元素构成的单元集中元素构成的单元集(3)图中图中L1的原子是的原子是a,L2的原子是的原子是a,b,c,L3的原子是的原子是a 和和b25本讲稿第二十五页，共三十七页有限布尔代数的表示定理有限布尔代数的表示定理定理定理11.9(有限布尔代数的表示定理有限布尔代数的表示定理)设设B是有限布尔代数是有限布尔代数,A是是B的全体原子构成的集合的全体原子构成的集合,则则B同构同构于于A的幂集代数的幂集代数P(A).实例实例:(1)S110关于关于gcd,lcm运算构成的布尔代数运算构成的布尔代数.它的原子是它的原子是2,5和和11,因此原子的集合因此原子的集合A

24、=2,5,11.幂集幂集 P(A)=,2,5,11,2,5,2,11,5,11,2,5,11.幂集代数是幂集代数是.只要令只要令f:S110P(A),f(1)=,f(2)=2,f(5)=5,f(11)=11,f(10)=2,5,f(22)=2,11,f(55)=5,11,f(110)=A,那么那么f 就是从就是从S110到幂集到幂集P(A)的同构映射的同构映射.26本讲稿第二十六页，共三十七页推论推论推论推论1任何有限布尔代数的基数为任何有限布尔代数的基数为2n,nN.证证设设B是有限布尔代数是有限布尔代数,A是是B的所有原子构成的集合的所有原子构成的集合,且且|A|=n,nN.由定理得由定理

25、得B P(A),而而|P(A)|=2n,所以所以|B|=2n.推论推论2任何等势的有限布尔代数都是同构的任何等势的有限布尔代数都是同构的.(证明省略证明省略)结论结论：l有限布尔代数的基数都是有限布尔代数的基数都是2的幂的幂,l对于任何自然数对于任何自然数n,仅存在一个仅存在一个2n元的布尔代数元的布尔代数.27本讲稿第二十七页，共三十七页图11实例实例下图给出了下图给出了 1元元,2元元,4元和元和8元的布尔代数元的布尔代数.28本讲稿第二十八页，共三十七页第十一章第十一章 习题课习题课主要内容主要内容l格的两个等价定义格的两个等价定义l格的性质格的性质l子格子格l特殊格：分配格、有界格、有

26、补格、布尔代数特殊格：分配格、有界格、有补格、布尔代数基本要求基本要求l能够判别给定偏序集或者代数系统是否构成格能够判别给定偏序集或者代数系统是否构成格l能够确定一个命题的对偶命题能够确定一个命题的对偶命题l能够证明格中的等式和不等式能够证明格中的等式和不等式l能判别格能判别格L的子集的子集S是否构成子格是否构成子格l能够判别给定的格是否为分配格、有补格能够判别给定的格是否为分配格、有补格l能够判别布尔代数并证明布尔代数中的等式能够判别布尔代数并证明布尔代数中的等式 29本讲稿第二十九页，共三十七页练习练习11(1)证明格中的命题证明格中的命题,即即(ab)b=b(2)证明证明(ab)(cd)

27、(ac)(bd)(1)(ab)b是是ab与与b的最小上界的最小上界,根据最小上界的定义根据最小上界的定义有有(ab)b b.b是是ab与与b的上界的上界,故有故有(ab)b b.由于由于偏序的反对称性偏序的反对称性,等式得证等式得证.(2)ab a ac,ab b bd,所以所以(ab)(ac)(bd),同理同理(cd)(ac)(bd).从而得到从而得到(ab)(cd)(ac)(bd)30本讲稿第三十页，共三十七页解2求图中格的所有子格求图中格的所有子格.1元子格：元子格：a,b,c,d,e；2元子格：元子格：a,b,a,c,a,d,a,e,b,c,b,d,b,e,c,e,d,e；3元子格：元

28、子格：a,b,c,a,b,d,a,b,e,a,c,e,a,d,e,b,c,e,b,d,e；4元子格：元子格：a,b,c,e,a,b,d,e,b,c,d,e；5元子格：元子格：a,b,c,d,e 练习练习2eabcd31本讲稿第三十一页，共三十七页图133判别下述格判别下述格L是否为分配格是否为分配格.L1不是分配格不是分配格,因为它含有与钻石格同构的子格因为它含有与钻石格同构的子格.L2和和L3不是分配格不是分配格,因为它们含有与五角格同构的子格因为它们含有与五角格同构的子格.L1L2 L3练习练习332本讲稿第三十二页，共三十七页L1L2 L3图124针对下图，求出每个格的补元并说明它们是否

29、为有补格针对下图，求出每个格的补元并说明它们是否为有补格L1中中,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与与L3是有补格是有补格.练习练习433本讲稿第三十三页，共三十七页5对于以下各题给定的集合和运算判断它们是哪一类代数对于以下各题给定的集合和运算判断它

30、们是哪一类代数系统（半群、独异点、群、环、域、格、布尔代数）系统（半群、独异点、群、环、域、格、布尔代数）,并说并说明理由明理由.(1)S1=1,1/2,2,1/3,3,1/4,4,为普通乘法为普通乘法.(2)S2=a1,a2,.,an,ai,ajS2,ai aj=ai,这里的这里的n 为给定为给定正整数正整数,n1.(3)S3=0,1,为普通乘法为普通乘法.(4)S4=1,2,3,6,x,yS4,x y与与x y分别表示分别表示x 与与y 的最的最小公倍数和最大公约数小公倍数和最大公约数.(5)S5=0,1,为模为模2加法加法,为模为模2乘法乘法.练习练习534本讲稿第三十四页，共三十七页解

31、：解答解答(1)不是代数系统不是代数系统,因为乘法不封闭因为乘法不封闭,例如例如4 4=16.(2)是半群但不是独异点是半群但不是独异点,因为因为 运算满足结合律运算满足结合律,但是没有单但是没有单位元位元.(3)是独异点但不是群是独异点但不是群.因为因为 运算满足结合律运算满足结合律,单位元是单位元是1,可可是是0没有乘法逆元没有乘法逆元.(4)是格是格,也是布尔代数也是布尔代数.因为这两个运算满足交换律和分配因为这两个运算满足交换律和分配律；求最小公倍数运算的单位元是律；求最小公倍数运算的单位元是1,求最大公约数运算求最大公约数运算的单位元是的单位元是6,满足同一律；两个运算满足补元律满足

32、同一律；两个运算满足补元律.(5)是域是域.对于模对于模n 的环的环Zn,当当n为素数时构成域为素数时构成域.35本讲稿第三十五页，共三十七页证证(2)由由反之也对反之也对.下面证下面证明它们都等价于明它们都等价于ab.由由得得即即ab,又由又由ab 得得 6设设是布尔代数是布尔代数,证明对于证明对于B中任意元素中任意元素a,b练习练习636本讲稿第三十六页，共三十七页练习练习77.判断下述代数系统是否为格？是不是布尔代数？判断下述代数系统是否为格？是不是布尔代数？(1)S=1,3,4,12;任给任给x,yS,x y=lcm(x,y),x y=gcd(x,y),其中其中lcm是求最小公倍数是求最小公倍数,gcd是求最大公约数是求最大公约数.(2)S=0,1,2;是模是模3加法加法,是模是模3乘法乘法(3)S=0,.,n,其中其中n2;任给任给x,yS,x y=max(x,y),x y=min(x,y)(1)是布尔代数是布尔代数.(2)不是格不是格.(3)是格是格,但不是布尔代数但不是布尔代数.37本讲稿第三十七页，共三十七页