邱婉玲耿素云离散数学ch

《邱婉玲耿素云离散数学ch》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

第十一章格与布尔代数主要内容格的定义及性质子格分配格、有补格布尔代数1 11.1格的定义与性质定义11.1设是偏序集，如果x,yS，{x,y}都有最小上界和最大下界，则称S关于偏序≼作成一个格.求{x,y}最小上界和最大下界看成x与y的二元运算∨和∧，例1设n是正整数，Sn是n的正因子的集合.D为整除关系，则偏序集构成格.x,y∈Sn，x∨y是lcm(x,y)，即x与y的最小公倍数.x∧y是gcd(x,y)，即x与y的最大公约数.2 图2例2判断下列偏序集是否构成格，并说明理由.(1)，其中P(B)是集合B的幂集.(2)，其中Z是整数集，≤为小于或等于关系.(3)偏序集的哈斯图分别在下图给出.实例(1)幂集格.x,y∈P(B)，x∨y就是x∪y，x∧y就是x∩y.(2)是格.x,y∈Z，x∨y=max(x,y)，x∧y=min(x,y)，(3)都不是格.可以找到两个结点缺少最大下界或最小上界3 实例：子群格例3设G是群，L(G)是G的所有子群的集合.即L(G)={H|H≤G}，对任意的H1,H2∈L(G)，H1∩H2是G的子群，是由H1∪H2生成的子群（即包含着H1∪H2的最小子群）.在L(G)上定义包含关系，则L(G)关于包含关系构成一个格，称为G的子群格.在L(G)中，H1∧H2就是H1∩H2H1∨H2就是4 格的性质：对偶原理定义11.2设f是含有格中元素以及符号=,≼,≽,∨和∧的命题.令f*是将f中的≼替换成≽,≽替换成≼,∨替换成∧,∧替换成∨所得到的命题.称f*为f的对偶命题.例如,在格中令f是(a∨b)∧c≼c,f*是(a∧b)∨c≽c.格的对偶原理设f是含有格中元素以及符号=,≼,≽,∨和∧等的命题.若f对一切格为真,则f的对偶命题f*也对一切格为真.例如,如果对一切格L都有a,b∈L,a∧b≼a，那么对一切格L都有a,b∈L,a∨b≽a注意：对偶是相互的，即(f*)*=f5 格的性质：算律定理11.1设是格,则运算∨和∧适合交换律、结合律、幂等律和吸收律,即(1)a,b∈L有a∨b=b∨a,a∧b=b∧a(2)a,b,c∈L有(a∨b)∨c=a∨(b∨c),(a∧b)∧c=a∧(b∧c)(3)a∈L有a∨a=a,a∧a=a(4)a,b∈L有a∨(a∧b)=a,a∧(a∨b)=a6 证明(1)a∨b是{a,b}的最小上界,b∨a是{b,a}的最小上界.由于{a,b}={b,a},所以a∨b=b∨a.由对偶原理,a∧b=b∧a.(2)由最小上界的定义有(a∨b)∨c≽a∨b≽a(1)(a∨b)∨c≽a∨b≽b(2)(a∨b)∨c≽c(3)由式(2)和(3)有(a∨b)∨c≽b∨c(4)由式(1)和(4)有(a∨b)∨c≽a∨(b∨c)同理可证(a∨b)∨c≼a∨(b∨c)根据反对称性(a∨b)∨c=a∨(b∨c)由对偶原理,(a∧b)∧c=a∧(b∧c)7 证明(3)显然a≼a∨a,又由a≼a可得a∨a≼a.根据反对称性有a∨a=a.由对偶原理,a∧a=a得证.(4)显然a∨(a∧b)≽a(5)由a≼a,a∧b≼a可得a∨(a∧b)≼a(6)由式(5)和(6)可得a∨(a∧b)=a,根据对偶原理,a∧(a∨b)=a8 格的性质：序与运算的关系定理11.2设L是格,则a,b∈L有a≼ba∧b=aa∨b=b证(1)先证a≼ba∧b=a由a≼a和a≼b可知a是{a,b}的下界,故a≼a∧b.显然有a∧b≼a.由反对称性得a∧b=a.(2)再证a∧b=aa∨b=b根据吸收律有b=b∨(b∧a)由a∧b=a和上面的等式得b=b∨a,即a∨b=b.(3)最后证a∨b=ba≼b由a≼a∨b得a≼a∨b=b9 格的性质：保序定理11.3设L是格,a,b,c,d∈L，若a≼b且c≼d,则a∧c≼b∧d,a∨c≼b∨d例4设L是格,证明a,b,c∈L有a∨(b∧c)≼(a∨b)∧(a∨c).证a∧c≼a≼b,a∧c≼c≼d因此a∧c≼b∧d.同理可证a∨c≼b∨d证由a≼a,b∧c≼b得a∨(b∧c)≼a∨b由a≼a,b∧c≼c得a∨(b∧c)≼a∨c从而得到a∨(b∧c)≼(a∨b)∧(a∨c)注意：一般说来,格中的∨和∧运算不满足分配律.10 格作为代数系统的定义定理11.4设是具有两个二元运算的代数系统,若对于∗和◦运算适合交换律、结合律、吸收律,则可以适当定义S中的偏序≼,使得构成格,且a,b∈S有a∧b=a∗b,a∨b=a◦b.证明省略.根据定理11.4,可以给出格的另一个等价定义.定义11.3设是代数系统,∗和◦是二元运算,如果∗和◦满足交换律、结合律和吸收律,则构成格.11 子格及其判别法定义11.4设是格,S是L的非空子集,若S关于L中的运算∧和∨仍构成格,则称S是L的子格.例5设格L如图所示.令S1={a,e,f,g},S2={a,b,e,g}S1不是L的子格,因为e,fS1但e∧f=cS1.S2是L的子格.12 11.2分配格、有补格与布尔代数定义11.5设是格,若a,b,c∈L,有a∧(b∨c)=(a∧b)∨(a∧c)a∨(b∧c)=(a∨b)∧(a∨c)则称L为分配格.注意：可以证明以上两个条件互为充分必要条件L1和L2是分配格,L3和L4不是分配格.称L3为钻石格,L4为五角格.实例13 分配格的判别及性质定理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的子格同构于钻石格.14 有界格的定义定义11.6设L是格,(1)若存在a∈L使得x∈L有a≼x,则称a为L的全下界(2)若存在b∈L使得x∈L有x≼b,则称b为L的全上界说明：格L若存在全下界或全上界,一定是惟一的.一般将格L的全下界记为0,全上界记为1.定义11.7设L是格,若L存在全下界和全上界,则称L为有界格,一般将有界格L记为.15 定理11.6设是有界格,则a∈L有a∧0=0,a∨0=a,a∧1=a,a∨1=1注意：有限格L={a1,a2,…,an}是有界格,a1∧a2∧…∧an是L的全下界,a1∨a2∨…∨an是L的全上界.0是关于∧运算的零元,∨运算的单位元；1是关于∨运算的零元,∧运算的单位元.对于涉及到有界格的命题,如果其中含有全下界0或全上界1,在求该命题的对偶命题时,必须将0替换成1,而将1替换成0.有界格的性质16 有界格中的补元及实例定义11.8设是有界格,a∈L,若存在b∈L使得a∧b=0和a∨b=1成立,则称b是a的补元.注意：若b是a的补元,那么a也是b的补元.a和b互为补元.例7考虑下图中的格.针对不同的元素，求出所有的补元.17 解答(1)L1中a与c互为补元,其中a为全下界,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的补元是b.18 有界分配格的补元惟一性定理11.7设是有界分配格.若L中元素a存在补元,则存在惟一的补元.证假设c是a的补元,则有a∨c=1,a∧c=0,又知b是a的补元,故a∨b=1,a∧b=0从而得到a∨c=a∨b,a∧c=a∧b,由于L是分配格,b=c.注意：在任何有界格中,全下界0与全上界1互补.对于一般元素,可能存在补元,也可能不存在补元.如果存在补元,可能是惟一的,也可能是多个补元.对于有界分配格,如果元素存在补元,一定是惟一的.19 图9有补格的定义定义11.9设是有界格,若L中所有元素都有补元存在,则称L为有补格.例如,图中的L2,L3和L4是有补格,L1不是有补格.20 布尔代数的定义与实例定义11.10如果一个格是有补分配格,则称它为布尔格或布尔代数.布尔代数标记为,为求补运算.例8设S110={1,2,5,10,11,22,55,110}是110的正因子集合，gcd表示求最大公约数的运算，lcm表示求最小公倍数的运算，问是否构成布尔代数？为什么？解(1)不难验证S110关于gcd和lcm运算构成格.(略)(2)验证分配律x,y,z∈S110有gcd(x,lcm(y,z))=lcm(gcd(x,y),gcd(x,z))(3)验证它是有补格,1作为S110中的全下界,110为全上界,1和110互为补元,2和55互为补元,5和22互为补元,10和11互为补元,从而证明了为布尔代数.21 实例例9设B为任意集合,证明B的幂集格构成布尔代数,称为集合代数.证(1)P(B)关于∩和∪构成格,因为∩和∪运算满足交换律,结合律和吸收律.(2)由于∩和∪互相可分配,因此P(B)是分配格.(3)全下界是空集,全上界是B.(4)根据绝对补的定义,取全集为B,x∈P(B),~x是x的补元.从而证明P(B)是有补分配格,即布尔代数.22 布尔代数的性质定理11.8设是布尔代数,则(1)a∈B,(a)=a.(2)a,b∈B,(a∧b)=a∨b,(a∨b)=a∧b（德摩根律）证(1)(a)是a的补元,a也是a的补元.由补元惟一性得(a)=a.(2)对任意a,b∈B有(a∧b)∨(a∨b)=(a∨a∨b)∧(b∨a∨b)=(1∨b)∧(a∨1)=1∧1=1,(a∧b)∧(a∨b)=(a∧b∧a)∨(a∧b∧b)=(0∧b)∨(a∧0)=0∨0=0a∨b是a∧b的补元,根据补元惟一性有(a∧b)=a∨b,同理可证(a∨b)=a∧b.注意：德摩根律对有限个元素也是正确的.23 布尔代数作为代数系统的定义定义11.11设是代数系统,∗和◦是二元运算.若∗和◦运算满足：(1)交换律,即a,b∈B有a∗b=b∗a,a◦b=b◦a(2)分配律,即a,b,c∈B有a∗(b◦c)=(a∗b)◦(a∗c),a◦(b∗c)=(a◦b)∗(a◦c)(3)同一律,即存在0,1∈B,使得a∈B有a∗1=a,a◦0=a(4)补元律,即a∈B,存在a∈B使得a∗a=0,a◦a=1则称是一个布尔代数.可以证明，布尔代数的两种定义是等价的.24 有限布尔代数的结构定义11.12设L是格,0∈L,若b∈L有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和b25 有限布尔代数的表示定理定理11.9(有限布尔代数的表示定理)设B是有限布尔代数,A是B的全体原子构成的集合,则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:S110→P(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,n∈N.证设B是有限布尔代数,A是B的所有原子构成的集合,且|A|=n,n∈N.由定理得BP(A),而|P(A)|=2n,所以|B|=2n.推论2任何等势的有限布尔代数都是同构的.(证明省略)结论：有限布尔代数的基数都是2的幂,对于任何自然数n,仅存在一个2n元的布尔代数.27 图11实例下图给出了1元,2元,4元和8元的布尔代数.28 第十一章习题课主要内容格的两个等价定义格的性质子格特殊格：分配格、有界格、有补格、布尔代数基本要求能够判别给定偏序集或者代数系统是否构成格能够确定一个命题的对偶命题能够证明格中的等式和不等式能判别格L的子集S是否构成子格能够判别给定的格是否为分配格、有补格能够判别布尔代数并证明布尔代数中的等式29 练习11．(1)证明格中的命题,即(a∧b)∨b=b(2)证明(a∧b)∨(c∧d)≼(a∨c)∧(b∨d)(1)(a∧b)∨b是a∧b与b的最小上界,根据最小上界的定义有(a∧b)∨b≽b.b是a∧b与b的上界,故有(a∧b)∨b≼b.由于偏序的反对称性,等式得证.(2)a∧b≼a≼a∨c,a∧b≼b≼b∨d,所以(a∧b)≼(a∨c)∧(b∨d),同理(c∧d)≼(a∨c)∧(b∨d).从而得到(a∧b)∨(c∧d)≼(a∨c)∧(b∨d)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元子格：{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不是分配格,因为它们含有与五角格同构的子格.L1L2L3练习332 L1L2L3图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是有补格.练习433 5．对于以下各题给定的集合和运算判断它们是哪一类代数系统（半群、独异点、群、环、域、格、布尔代数）,并说明理由.(1)S1={1,1/2,2,1/3,3,1/4,4},∗为普通乘法.(2)S2={a1,a2,...,an},ai,aj∈S2,ai∘aj=ai,这里的n为给定正整数,n>1.(3)S3={0,1},∗为普通乘法.(4)S4={1,2,3,6},x,y∈S4,x∘y与x∗y分别表示x与y的最小公倍数和最大公约数.(5)S5={0,1},∗为模2加法,∘为模2乘法.练习534 解：解答(1)不是代数系统,因为乘法不封闭,例如4∗4=16.(2)是半群但不是独异点,因为∗运算满足结合律,但是没有单位元.(3)是独异点但不是群.因为∗运算满足结合律,单位元是1,可是0没有乘法逆元.(4)是格,也是布尔代数.因为这两个运算满足交换律和分配律；求最小公倍数运算的单位元是1,求最大公约数运算的单位元是6,满足同一律；两个运算满足补元律.(5)是域.对于模n的环Zn,当n为素数时构成域.35 证(2)由反之也对.下面证明它们都等价于a≤b.由得即a≤b,又由a≤b得6．设是布尔代数,证明对于B中任意元素a,b练习636 练习77.判断下述代数系统是否为格？是不是布尔代数？(1)S={1,3,4,12};任给x,y∈S,x∘y=lcm(x,y),x∗y=gcd(x,y),其中lcm是求最小公倍数,gcd是求最大公约数.(2)S={0,1,2};∘是模3加法,∗是模3乘法(3)S={0,...,n},其中n≥2;任给x,y∈S,x∘y=max(x,y),x∗y=min(x,y)(1)是布尔代数.(2)不是格.(3)是格,但不是布尔代数.37