《离散数学课件ch11》由会员分享，可在线阅读，更多相关《离散数学课件ch11（34页珍藏版）》请在金锄头文库上搜索。
1、离散数学离散数学- -课件件-ch11-ch11图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)都不是格都不是格.可以找到两个结点缺少最大下界或最小上界可以找到两个结点缺少最大下界或最小上界2实例：子群格实
2、例：子群格例例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就是就是3格的性质：对偶原理格的性质：对偶原理定义定义11.2设设f 是含有格中元素以及符号是含有格中元素以及符号=, , ,和和的命题的命题
3、.令令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 注意：对偶是相互的，即注意：对偶是相互的
4、，即(f*)*=f4格的性质：算律格的性质：算律定理定理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)=a5证明证明(1)ab是是a,b 的最小上界的最小上界,ba是是b,a 的最小上界的最小上界.由于由于a,b =b,a ,所以所以ab =ba.由对偶原理由对偶原理,ab =ba.(2)由最小上界的定义有由最小上界的定义有(
5、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)6证明证明(3)显然显然a aa,又由又由a a 可得可得aa a.根据反对称性有根据反对称性有aa =a . 由对偶原理由对偶原理,aa =a 得证得证.(4)显然显然a(ab) a(5)由由a a,ab a 可得可得a(ab) a(6)由式由式(5)和和(6)可得可得a(ab)=a,根据对偶原
6、理根据对偶原理,a(ab)=a7格的性质：序与运算的关系格的性质：序与运算的关系定理定理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 8格的性质：保序格的性质：保序定理定理11.3设设L是格是格,
7、 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)注意：一般说来注意：一般说来,格中的格中的和和运算不满足分配律运算不满足分配律. 9格作为代数系统的定义格作为代数系统的定义定理定理11.4设设是具有两个二元运算的代数系统是具有两个二元运算的代数系统,若对于若对于 和和运算适合交换律、结合律
8、、吸收律运算适合交换律、结合律、吸收律,则可以适当定义则可以适当定义S中中的偏序的偏序 ,使得使得构成格构成格,且且 a,bS 有有ab =a b,ab =ab.证明省略证明省略.根据定理根据定理11.4,可以给出格的另一个等价定义可以给出格的另一个等价定义.定义定义11.3设设是代数系统是代数系统, 和和是二元运算是二元运算,如果如果 和和满足交换律、结合律和吸收律满足交换律、结合律和吸收律,则则构成格构成格.10子格及其判别法子格及其判别法定义定义11.4设设是格是格,S是是L的非空子集的非空子集,若若S关于关于L中中的运算的运算和和仍构成格仍构成格,则称则称S是是L的的子格子格.例例5设
9、格设格L如图所示如图所示.令令 S1=a,e,f,g, S2=a,b,e,gS1不是不是L的子格的子格,因为因为e,f S1但但ef =c S1.S2是是L的子格的子格. 1111.2分配格、有补格与布尔代数分配格、有补格与布尔代数 定义定义11.5设设是格是格,若若 a,b,cL,有有a(bc)=(ab)(ac)a(bc)=(ab)(ac)则称则称L为为分配格分配格.注意：可以证明以上两个条件互为充分必要条件注意：可以证明以上两个条件互为充分必要条件L1和和L2是分配格是分配格,L3和和L4不是分配格不是分配格.称称L3为为钻石格钻石格,L4为为五角格五角格.实例实例12分配格的判别及性质分
10、配格的判别及性质定理定理11.5设设L是格是格,则则L是分配格当且仅当是分配格当且仅当L不含有与钻石格不含有与钻石格或五角格同构的子格或五角格同构的子格.证明省略证明省略.推论推论(1)小于五元的格都是分配格小于五元的格都是分配格.(2)任何一条链都是分配格任何一条链都是分配格.例例6 说明图中的格是否为分配格说明图中的格是否为分配格, 为什么？为什么？解解都不是分配格都不是分配格.a,b,c,d,e 是是L1的子格的子格,同构于钻石格同构于钻石格a,b,c,e,f 是是L2的子格的子格,同构于五角格；同构于五角格；a,c,b,e,f 是是L3的子格的子格同构于钻石格同构于钻石格. 13有界格
11、的定义有界格的定义定义定义11.6设设L是格是格,(1)若存在若存在aL使得使得 xL有有a x,则称则称a为为L的的全下界全下界(2)若存在若存在bL使得使得 xL有有x b,则称则称b为为L的的全上界全上界说明：说明：格格L若存在全下界或全上界若存在全下界或全上界,一定是惟一的一定是惟一的.一般将格一般将格L的全下界记为的全下界记为0,全上界记为全上界记为1.定义定义11.7设设L是格是格,若若L存在全下界和全上界存在全下界和全上界,则称则称L 为为有界有界格格,一般将有界格一般将有界格L记为记为.14 定理定理11.6设设是有界格是有界格,则则 aL有有a0=0,a0=a,a1=a,a1
12、=1注意：注意：有限格有限格L=a1,a2,an是有界格是有界格,a1a2an是是L的全下的全下界界,a1a2an是是L的全上界的全上界.0是关于是关于运算的零元运算的零元,运算的单位元；运算的单位元；1是关于是关于运算的运算的零元零元,运算的单位元运算的单位元.对于涉及到有界格的命题对于涉及到有界格的命题,如果其中含有全下界如果其中含有全下界0或全上界或全上界1,在求该命题的对偶命题时在求该命题的对偶命题时,必须将必须将0替换成替换成1,而将而将1替换替换成成0.有界格的性质有界格的性质15有界格中的补元及实例有界格中的补元及实例定义定义11.8设设是有界格是有界格,aL,若存在若存在bL使
13、得使得ab =0和和ab =1成立成立,则称则称b是是a的的补元补元.注意：若注意：若b是是a的补元的补元,那么那么a也是也是b的补元的补元.a和和b互为补元互为补元.例例7考虑下图中的格考虑下图中的格. 针对不同的元素，求出所有的补元针对不同的元素，求出所有的补元.16解答解答(1) L1中中a 与与c 互为补元互为补元,其中其中a 为全下界为全下界,c为全上界为全上界,b 没有没有补元补元.(2)L2中中a 与与d 互为补元互为补元,其中其中a 为全下界为全下界,d 为全上界为全上界,b与与c也互为补元也互为补元.(3)L3中中a 与与e 互为补元互为补元,其中其中a 为全下界为全下界,e
14、 为全上界为全上界,b 的补的补元是元是c 和和d ;c 的补元是的补元是b 和和d ;d 的补元是的补元是b 和和c ;b,c,d 每个元素都有两个补元每个元素都有两个补元.(4)L4中中a 与与e 互为补元互为补元,其中其中a 为全下界为全下界,e 为全上界为全上界,b 的补的补元是元是c 和和d ;c 的补元是的补元是b ;d 的补元是的补元是b .17有界分配格的补元惟一性有界分配格的补元惟一性定理定理11.7设设是有界分配格是有界分配格.若若L中元素中元素a 存在存在补元补元,则存在惟一的补元则存在惟一的补元.证证假设假设c 是是a 的补元的补元,则有则有ac =1,ac =0,又知
15、又知b 是是a 的补元的补元,故故ab =1,ab =0从而得到从而得到ac =ab,ac =ab,由于由于L是分配格是分配格,b =c.注意：注意：在任何有界格中在任何有界格中, 全下界全下界0与全上界与全上界1互补互补.对于一般元素对于一般元素, 可能存在补元可能存在补元, 也可能不存在补元也可能不存在补元. 如果存如果存在补元在补元, 可能是惟一的可能是惟一的, 也可能是多个补元也可能是多个补元. 对于有界分配对于有界分配格格, 如果元素存在补元如果元素存在补元, 一定是惟一的一定是惟一的.18图9有补格的定义有补格的定义定义定义11.9设设是有界格是有界格,若若L中所有元素都有补中所有
16、元素都有补元存在元存在,则称则称L为为有补格有补格.例如例如,图中的图中的L2,L3和和L4是有补格是有补格,L1不是有补格不是有补格.19布尔代数的定义与实例布尔代数的定义与实例定义定义11.10 如果一个格是有补分配格如果一个格是有补分配格, 则称它为布尔格或布则称它为布尔格或布尔代数尔代数. 布尔代数标记为布尔代数标记为, 为求补运算为求补运算. 例例8设设S110=1,2,5,10,11,22,55,110是是110的正因子集合，的正因子集合，gcd表示求最大公约数的运算，表示求最大公约数的运算，lcm表示求最小公倍数的运算，表示求最小公倍数的运算，问问是否构成布尔代数？为什么？是否构
17、成布尔代数？为什么？解解(1) 不难验证不难验证S110关于关于gcd和和lcm运算构成格运算构成格.(略略)(2)验证分配律验证分配律 x,y,zS110有有gcd(x,lcm(y,z)=lcm(gcd(x,y),gcd(x,z)(3)验证它是有补格验证它是有补格,1作为作为S110中的全下界中的全下界,110为全上界为全上界,1和和110互为补元互为补元,2和和55互为补元互为补元,5和和22互为补元互为补元,10和和11互为补元互为补元,从而证明了从而证明了为布尔代数为布尔代数. 20实例实例例例9设设B为任意集合为任意集合,证明证明B的幂集格的幂集格构成布尔代数构成布尔代数,称为集合代
18、数称为集合代数.证证(1)P(B)关于关于和和构成格构成格,因为因为和和运算满足交换律运算满足交换律,结合律和吸收律结合律和吸收律.(2)由于由于和和互相可分配互相可分配,因此因此P(B)是分配格是分配格.(3)全下界是空集全下界是空集,全上界是全上界是B.(4)根据绝对补的定义根据绝对补的定义,取全集为取全集为B, xP(B),x是是x的补元的补元.从而证明从而证明P(B)是有补分配格是有补分配格,即布尔代数即布尔代数.21布尔代数的性质布尔代数的性质定理定理11.8设设是布尔代数是布尔代数,则则(1) aB,(a ) =a.(2) a,bB,(ab) =a b ,(ab) =a b （德摩
19、（德摩根律）根律）证证(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 )=(0b)(a0)=00=0a b 是是ab的补元的补元,根据补元惟一性有根据补元惟一性有(ab) =a b ,同理同理可证可证(ab) =a b .注意：德摩根律对有限个元素也是正确的注意：德摩根律对有限个元素也是正确的.22布尔代数作为代数系统的定义布尔代数作为代数系统的定义定义定义11.11设设是代数
20、系统是代数系统, 和和是二元运算是二元运算.若若 和和运运算满足：算满足：(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)同一律同一律,即存在即存在0,1B,使得使得 aB有有a 1=a,a0=a(4)补元律补元律,即即 aB,存在存在a B 使得使得a a =0,aa =1则称则称是一个布尔代数是一个布尔代数.可以证明，布尔代数的两种定义是等价的可以证明，布尔代数的两种定义是等价的.23有限布尔代数的结构有限布尔代数的结构定义定义11.12设设L 是格是格,
21、0L,若若 bL有有0 b a b =a, 则则称称a 是是L 中的中的原子原子.实例：实例：(1) L是正整数是正整数n 的全体正因子关于整除关系构成的的全体正因子关于整除关系构成的格格,则则L的原子恰为的原子恰为n的全体素因子的全体素因子.(2)若若L是是B的幂集的幂集,则则L的原子就是的原子就是B中元素构成的单元集中元素构成的单元集(3)图中图中L1的原子是的原子是a,L2的原子是的原子是a,b,c,L3的原子是的原子是a 和和b24有限布尔代数的表示定理有限布尔代数的表示定理定理定理11.9(有限布尔代数的表示定理有限布尔代数的表示定理)设设B是有限布尔代数是有限布尔代数,A是是B的全
22、体原子构成的集合的全体原子构成的集合,则则B同构同构于于A的幂集代数的幂集代数P(A).实例实例:(1)S110关于关于gcd,lcm运算构成的布尔代数运算构成的布尔代数.它的原子是它的原子是2,5和和11,因此原子的集合因此原子的集合A =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)的同构映射的同构
23、映射.25推论推论推论推论1任何有限布尔代数的基数为任何有限布尔代数的基数为2n,nN.证证设设B是有限布尔代数是有限布尔代数,A是是B的所有原子构成的集合的所有原子构成的集合,且且|A|=n,nN.由定理得由定理得B P(A),而而|P(A)|=2n,所以所以|B|=2n.推论推论2任何等势的有限布尔代数都是同构的任何等势的有限布尔代数都是同构的.(证明省略证明省略)结论结论：有限布尔代数的基数都是有限布尔代数的基数都是2的幂的幂,对于任何自然数对于任何自然数n,仅存在一个仅存在一个2n元的布尔代数元的布尔代数.26图11实例实例下图给出了下图给出了 1元元,2元元,4元和元和8元的布尔代数
24、元的布尔代数.27第十一章第十一章 习题课习题课主要内容主要内容格的两个等价定义格的两个等价定义格的性质格的性质子格子格特殊格：分配格、有界格、有补格、布尔代数特殊格：分配格、有界格、有补格、布尔代数基本要求基本要求能够判别给定偏序集或者代数系统是否构成格能够判别给定偏序集或者代数系统是否构成格能够确定一个命题的对偶命题能够确定一个命题的对偶命题能够证明格中的等式和不等式能够证明格中的等式和不等式能判别格能判别格L的子集的子集S是否构成子格是否构成子格能够判别给定的格是否为分配格、有补格能够判别给定的格是否为分配格、有补格能够判别布尔代数并证明布尔代数中的等式能够判别布尔代数并证明布尔代数中的
25、等式 28练习练习11(1)证明格中的命题证明格中的命题,即即(ab)b =b(2)证明证明(ab)(cd) (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)29解2求图中格的所有子格求图中格的所有子格.1元子格：元子格：a ,b ,c ,d ,e ；
26、2元子格：元子格：a,b ,a,c ,a,d ,a,e ,b,c ,b,d ,b,e ,c,e ,d,e ；3元子格：元子格：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 练习练习2eabcd30图133判别下述格判别下述格L是否为分配格是否为分配格. L1不是分配格不是分配格,因为它含有与钻石格同构的子格因为它含有与钻石格同构的子格.L2和和L3不是分配格不是分配格,因为它们含有与五角格同构的子格因为它们含有与五角格同构的子格.L1
27、L2 L3练习练习331L1L2 L3图124针对下图，求出每个格的补元并说明它们是否为有补格针对下图，求出每个格的补元并说明它们是否为有补格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是有补格是有补格.练习练习4325对于以下各题给定的集合和
28、运算判断它们是哪一类代数对于以下各题给定的集合和运算判断它们是哪一类代数系统（半群、独异点、群、环、域、格、布尔代数）系统（半群、独异点、群、环、域、格、布尔代数）,并说并说明理由明理由.(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乘法乘法.练习练习533谢谢观赏谢谢观赏
