离散数学第十一章.ppt

1,第十一章 格与布尔代数,主要内容格的定义及性质 子格分配格、有补格布尔代数,2,11.1 格的定义与性质,定义11.1 设是偏序集，如果x,yS，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与y的最大公约数.,3,图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)都不是格.可以找到两个结点缺少最大下界或最小上界,4,实例：子群格,例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 就是,5,格的性质：对偶原理,定义11.2 设 f 是含有格中元素以及符号=,和的命题.令 f*是将 f 中的替换成,替换成,替换成,替换成所得到的命题.称 f*为 f 的对偶命题.例如,在格中令 f 是(ab)cc,f*是(ab)cc.,格的对偶原理 设 f 是含有格中元素以及符号=,和等的命题.若 f 对一切格为真,则 f 的对偶命题 f*也对一切格为真.例如,如果对一切格L都有 a,bL,aba，那么对一切格L都有 a,bL,aba 注意：对偶是相互的，即(f*)*=f,6,格的性质：算律,定理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)=a,7,证明,(1)ab是 a,b 的最小上界,ba是 b,a 的最小上界.由于 a,b=b,a,所以 ab=ba.由对偶原理,ab=ba.,(2)由最小上界的定义有(ab)caba(1)(ab)cabb(2)(ab)cc(3)由式(2)和(3)有(ab)cbc(4)由式(1)和(4)有(ab)ca(bc)同理可证(ab)ca(bc)根据反对称性(ab)c=a(bc)由对偶原理,(ab)c=a(bc),8,证明,(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,根据对偶原理,a(ab)=a,9,格的性质：序与运算的关系,定理11.2 设L是格,则a,bL有a b ab=a ab=b,证(1)先证 a b ab=a由 a a 和 a b 可知 a 是 a,b 的下界,故 a ab.显然有ab a.由反对称性得 ab=a.(2)再证 ab=a ab=b根据吸收律有 b=b(ba)由 ab=a 和上面的等式得 b=ba,即 ab=b.(3)最后证 ab=b ab由 a ab 得 a ab=b,10,格的性质：保序,定理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)注意：一般说来,格中的和运算不满足分配律.,11,格作为代数系统的定义,定理11.4 设是具有两个二元运算的代数系统,若对于和运算适合交换律、结合律、吸收律,则可以适当定义S中的偏序,使得 构成格,且a,bS 有 ab=ab,ab=ab.证明省略.根据定理11.4,可以给出格的另一个等价定义.,定义11.3 设是代数系统,和是二元运算,如果和满足交换律、结合律和吸收律,则构成格.,12,子格及其判别法,定义11.4 设是格,S是L的非空子集,若S关于L中的运算和仍构成格,则称S是L的子格.,例5 设格L如图所示.令 S1=a,e,f,g,S2=a,b,e,gS1不是L的子格,因为e,fS1 但 ef=cS1.S2是L的子格.,13,11.2 分配格、有补格与布尔代数,定义11.5 设是格,若a,b,cL,有 a(bc)=(ab)(ac)a(bc)=(ab)(ac)则称L为分配格.注意：可以证明以上两个条件互为充分必要条件,L1 和 L2 是分配格,L3 和 L4不是分配格.称 L3为钻石格,L4为五角格.,实例,14,分配格的判别及性质,定理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的子格 同构于钻石格.,15,有界格的定义,定义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记为.,16,定理11.6 设是有界格,则aL有a0=0,a0=a,a1=a,a1=1,注意：有限格L=a1,a2,an是有界格,a1a2an是L的全下界,a1a2an是L的全上界.0是关于运算的零元,运算的单位元；1是关于运算的零元,运算的单位元.对于涉及到有界格的命题,如果其中含有全下界0或全上界1,在求该命题的对偶命题时,必须将0替换成1,而将1替换成0.,有界格的性质,17,有界格中的补元及实例,定义11.8 设是有界格,aL,若存在bL 使得 ab=0 和 ab=1 成立,则称b是a的补元.注意：若b是a的补元,那么a也是b的补元.a和b互为补元.,例7 考虑下图中的格.针对不同的元素，求出所有的补元.,18,解答,(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.,19,有界分配格的补元惟一性,定理11.7 设是有界分配格.若L中元素 a 存在补元,则存在惟一的补元.证 假设 c 是 a 的补元,则有 ac=1,ac=0,又知 b 是 a 的补元,故 ab=1,ab=0 从而得到 ac=ab,ac=ab,由于L是分配格,b=c.,注意：在任何有界格中,全下界0与全上界1互补.对于一般元素,可能存在补元,也可能不存在补元.如果存在补元,可能是惟一的,也可能是多个补元.对于有界分配格,如果元素存在补元,一定是惟一的.,20,图9,有补格的定义,定义11.9 设是有界格,若L中所有元素都有补元存在,则称L为有补格.例如,图中的L2,L3和L4是有补格,L1不是有补格.,21,布尔代数的定义与实例,定义11.10 如果一个格是有补分配格,则称它为布尔格或布尔代数.布尔代数标记为,为求补运算.,例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中的全下界,110为全上界,1和110互为补元,2和55互为补元,5和22互为补元,10和 11互为补元,从而证明了为布尔代数.,22,实例,例9 设B为任意集合,证明B的幂集格构成布尔代数,称为集合代数.证(1)P(B)关于和构成格,因为和运算满足交换律,结合律和吸收律.(2)由于和互相可分配,因此P(B)是分配格.(3)全下界是空集,全上界是B.(4)根据绝对补的定义,取全集为B,xP(B),x是x的补元.从而证明P(B)是有补分配格,即布尔代数.,23,布尔代数的性质,定理11.8 设是布尔代数,则(1)aB,(a)=a.(2)a,bB,(ab)=ab,(ab)=ab（德摩根律）,证(1)(a)是a的补元,a也是a的补元.由补元惟一性得(a)=a.(2)对任意a,bB有(ab)(ab)=(aab)(bab)=(1b)(a1)=11=1,(ab)(ab)=(aba)(abb)=(0b)(a0)=00=0ab是ab的补元,根据补元惟一性有(ab)=ab,同理可证(ab)=ab.注意：德摩根律对有限个元素也是正确的.,24,布尔代数作为代数系统的定义,定义11.11 设是代数系统,和是二元运算.若和运算满足：(1)交换律,即a,bB有ab=ba,ab=ba(2)分配律,即a,b,cB有 a(bc)=(ab)(ac),a(bc)=(ab)(ac)(3)同一律,即存在0,1B,使得aB有a 1=a,a0=a(4)补元律,即aB,存在 aB 使得 a a=0,aa=1 则称 是一个布尔代数.可以证明，布尔代数的两种定义是等价的.,25,有限布尔代数的结构,定义11.12 设 L 是格,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 和 b,26,有限布尔代数的表示定理,定理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: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)的同构映射.,27,推论,推论1 任何有限布尔代数的基数为2n,nN.证 设B是有限布尔代数,A是B的所有原子构成的集合,且|A|=n,nN.由定理得 B P(A),而|P(A)|=2n,所以|B|=2n.推论2 任何等势的有限布尔代数都是同构的.(证明省略)结论：有限布尔代数的基数都是2的幂,对于任何自然数n,仅存在一个2n元的布尔代数.,28,图11,实例,下图给出了 1 元,2 元,4 元和 8 元的布尔代数.,29,第十一章 习题课,主要内容格的两个等价定义格的性质子格特殊格：分配格、有界格、有补格、布尔代数基本要求能够判别给定偏序集或者代数系统是否构成格能够确定一个命题的对偶命题能够证明格中的等式和不等式能判别格L的子集S是否构成子格能够判别给定的格是否为分配格、有补格能够判别布尔代数并证明布尔代数中的等式,30,练习1,1(1)证明格中的命题,即(ab)b=b(2)证明(ab)(cd)(ac)(bd),(1)(ab)b是ab与b的最小上界,根据最小上界的定义有(ab)bb.b是ab与b的上界,故有(ab)bb.由于偏序的反对称性,等式得证.,(2)abaac,abbbd,所以(ab)(ac)(bd),同理(cd)(ac)(bd).从而得到(ab)(cd)(ac)(bd),31,解,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,练习2,32,图13,3判别下述格L是否为分配格.,L1不是分配格,因为它含有与钻石格同构的子格.L2和L3不是分配格,因为它们含有与五角格同构的子格.,L1 L2 L3,练习3,33,L1 L2 L3,图12,4针对下图，求出每个格的补元并说明它们是否为有补格,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是有补格.,练习4,34,5对于以下各题给定的集合和运算判断它们是哪一类代数系统（半群、独异点、群、环、域、格、布尔代数）,并说明理由.(1)S1=1,1/2,2,1/3,3,1/4,4,为普通乘法.(2)S2=a1,a2,.,an,ai,ajS2,aiaj=ai,这里的 n 为给定 正整数,n1.(3)S3=0,1,为普通乘法.(4)S4=1,2,3,6,x,yS4,xy与xy分别表示 x 与 y 的最小公倍数和最大公约数.(5)S5=0,1,为模2加法,为模2乘法.,练习5,35,解：,解答,(1)不是代数系统,因为乘法不封闭,例如44=16.(2)是半群但不是独异点,因为运算满足结合律,但是没有单 位元.(3)是独异点但不是群.因为运算满足结合律,单位元是1,可 是0没有乘法逆元.(4)是格,也是布尔代数.因为这两个运算满足交换律和分配 律；求最小公倍数运算的单位元是1,求最大公约数运算 的单位元是6,满足同一律；两个运算满足补元律.(5)是域.对于模 n 的环Zn,当n为素数时构成域.,36,证(2)由 反之也对.下面证明它们都等价于ab.由 得即 ab,又由 ab 得,6设是布尔代数,证明对于B中任意元素 a,b,练习6,37,练习7,7.判断下述代数系统是否为格？是不是布尔代数？(1)S=1,3,4,12;任给 x,yS,xy=lcm(x,y),xy=gcd(x,y),其中 lcm 是求最小公倍数,gcd 是求最大公约数.(2)S=0,1,2;是模3加法,是模3乘法(3)S=0,.,n,其中n2;任给 x,yS,xy=max(x,y),xy=min(x,y),(1)是布尔代数.(2)不是格.(3)是格,但不是布尔代数.,