第八章 格与布尔代数.ppt

单击此处编辑母版标题样式,*,1,第八章 格与布尔代数,主要内容,格的定义及性质,子格,分配格、有补格,布尔代数,2,8.1,格的定义与性质,定义,8.1,设,是偏序集，如果,x,y,S,，,x,y,都有最小上,界和最大下界，则称,S,关于偏序作成一个,格,.,求,x,y,最小上界和最大下界看成,x,与,y,的二元运算和，,例,1,设,n,是正整数，,S,n,是,n,的正因子的集合,.,D,为整除关系，则,偏序集,构成格,.,x,y,S,n,，,x,y,是,lcm(,x,y,),，即,x,与,y,的,最小公倍数,.,x,y,是,gcd(,x,y,),，即,x,与,y,的最大公约数,.,3,图,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),都不是格,.,可以找到两个结点缺少最大下界或最小上界,4,实例：子群格,例,3,设,G,是群，,L,(,G,),是,G,的所有子群的集合,.,即,L,(,G,)=,H,|,H,G,，,对任意的,H,1,H,2,L,(,G,),，,H,1,H,2,是,G,的子群，,是由,H,1,H,2,生成的子群（即包含着,H,1,H,2,的最小子群）,.,在,L,(,G,),上定义包含关系,，则,L,(,G,),关于包含关系构成一个,格，称为,G,的子群格,.,在,L,(,G,),中，,H,1,H,2,就是,H,1,H,2,H,1,H,2,就是,5,格的性质：对偶原理,定义,8.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,*)*=,f,6,格的性质：算律,定理,8.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,)=,a,7,证明,(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,),8,证明,(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,)=,a,9,格的性质：序与运算的关系,定理,8.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,=,b,10,格的性质：保序,定理,8.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,),注意：一般说来,格中的和运算不满足分配律,.,11,格作为代数系统的定义,定理,8.4,设,是具有两个二元运算的代数系统,若对于,和,运算适合交换律、结合律、吸收律,则可以适当定义,S,中,的偏序,使得,构成格,且,a,b,S,有,a,b,=,a,b,a,b,=,a,b,.,证明省略,.,根据定理,8.4,可以给出格的另一个等价定义,.,定义,8.3,设,是代数系统,和,是二元运算,如果,和,满足交换律、结合律和吸收律,则,构成格,.,12,子格及其判别法,定义,8.4,设,是格,S,是,L,的非空子集,若,S,关于,L,中的运算和仍构成格,则称,S,是,L,的,子格,.,例,5,设格,L,如图所示,.,令,S,1,=,a,e,f,g,S,2,=,a,b,e,g,S,1,不是,L,的子格,因为,e,f,S,1,但,e,f,=,c,S,1,.,S,2,是,L,的子格,.,13,8.2,分配格、有补格与布尔代数,定义,8.5,设,是格,若,a,b,c,L,有,a,(,b,c,)=(,a,b,)(,a,c,),a,(,b,c,)=(,a,b,)(,a,c,),则称,L,为,分配格,.,注意：可以证明以上两个条件互为充分必要条件,L,1,和,L,2,是分配格,L,3,和,L,4,不是分配格,.,称,L,3,为,钻石格,L,4,为,五角格,.,实例,14,分配格的判别及性质,定理,8.5,设,L,是格,则,L,是分配格当且仅当,L,不含有与钻石格,或五角格同构的子格,.,证明省略,.,推论,(1),小于五元的格都是分配格,.,(2),任何一条链都是分配格,.,例,6,说明图中的格是否为分配格,为什么？,解 都不是分配格,.,a,b,c,d,e,是,L,1,的子格,同构于钻石格,a,b,c,e,f,是,L,2,的子格,同构于五角格；,a,c,b,e,f,是,L,3,的子格,同构于钻石格,.,15,有界格的定义,定义,8.6,设,L,是格,(1),若存在,a,L,使得,x,L,有,a,x,则称,a,为,L,的,全下界,(2),若存在,b,L,使得,x,L,有,x,b,则称,b,为,L,的,全上界,说明：,格,L,若存在全下界或全上界,一定是惟一的,.,一般将格,L,的全下界记为,0,全上界记为,1.,定义,8.7,设,L,是格,若,L,的每个非空子集均有上下确界，则称其为,完全格,；若,L,存在全下界和全上界,则称其为,有界,格,一般将有界格,L,记为,.,16,定理,8.6,设,是有界格,则,a,L,有,a,0=0,a,0=,a,a,1=,a,a,1=1,注意：,有限格,L,=,a,1,a,2,a,n,是有界格,a,1,a,2,a,n,是,L,的全下界,a,1,a,2,a,n,是,L,的全上界,.,0,是关于运算的零元,运算的单位元；,1,是关于运算的零元,运算的单位元,.,对于涉及到有界格的命题,如果其中含有全下界,0,或全上界,1,在求该命题的对偶命题时,必须将,0,替换成,1,而将,1,替换成,0.,有界格的性质,17,有界格中的补元及实例,定义,8.8,设,是有界格,a,L,若存在,b,L,使得,a,b,=0,和,a,b,=1,成立,则称,b,是,a,的,补元,.,注意：若,b,是,a,的补元,那么,a,也是,b,的补元,.,a,和,b,互为补元,.,例,7,考虑下图中的格,.,针对不同的元素，求出所有的补元,.,18,解答,(1),L,1,中,a,与,c,互为补元,其中,a,为全下界,c,为全上界,b,没有,补元,.,(2),L,2,中,a,与,d,互为补元,其中,a,为全下界,d,为全上界,b,与,c,也互为补元,.,(3),L,3,中,a,与,e,互为补元,其中,a,为全下界,e,为全上界,b,的补,元是,c,和,d,;,c,的补元是,b,和,d,;,d,的补元是,b,和,c,;,b,c,d,每个元素都有两个补元,.,(4),L,4,中,a,与,e,互为补元,其中,a,为全下界,e,为全上界,b,的补,元是,c,和,d,;,c,的补元是,b,;,d,的补元是,b,.,19,有界分配格的补元惟一性,定理,8.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,互补,.,对于一般元素,可能存在补元,也可能不存在补元,.,如果存在补元,可能是惟一的,也可能是多个补元,.,对于有界分配格,如果元素存在补元,一定是惟一的,.,20,图,9,有补格的定义,定义,8.9,设,是有界格,若,L,中所有元素都有补,元存在,则称,L,为,有补格,.,例如,图中的,L,2,L,3,和,L,4,是有补格,L,1,不是有补格,.,21,布尔代数的定义与实例,定义,8.10,如果一个格是有补分配格,则称它为布尔格或布,尔代数,.,布尔代数标记为,为求补运算,.,例,8,设,S,110,=1,2,5,10,11,22,55,110,是,110,的正因子集合，,gcd,表示求最大公约数的运算，,lcm,表示求最小公倍数的运算，问,是否构成布尔代数？为什么？,解,(1),不难验证,S,110,关于,gcd,和,lcm,运算构成格,.(,略,),(2),验证分配律,x,y,z,S,110,有,gcd(,x,lcm(,y,z,)=lcm(gcd(,x,y,),gcd(,x,z,)(3),验证它是有补格,1,作为,S,110,中的全下界,110,为全上界,1,和,110,互为补元,2,和,55,互为补元,5,和,22,互为补元,10,和,11,互为补元,从而证明了,为布尔代数,.,22,实例,例,9,设,B,为任意集合,证明,B,的幂集格,构成布尔代数,称为集合代数,.,证,(1),P,(,B,),关于和构成格,因为和运算满足交换律,结合律和吸收律,.,(2),由于和互相可分配,因此,P,(,B,),是分配格,.,(3),全下界是空集,全上界是,B,.,(4),根据绝对补的定义,取全集为,B,x,P,(,B,),x,是,x,的补元,.,从而证明,P,(,B,),是有补分配格,即布尔代数,.,23,布尔代数的性质,定理,8.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)=11=1,(,a,b,)(,a,b,)=(,a,b,a,)(,a,b,b,)=(0,b,)(,a,0)=00=0,a,b,是,a,b,的补元,根据补元惟一性有,(,a,b,),=,a,b,同理,可证,(,a,b,),=,a,b,.,注意：德摩根律对有限个元素也是正确的,.,24,布尔代数作为代数系统的定义,定义,8.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,则称,是一个布尔代数,.,可以证明，布尔代数的两种定义是等价的,.,25,有限布尔代数的结构,定义,8.12,设,L,是格,0,L,若,b,L,有,0,b,a,b,=,a,则,称,a,是,L,中的,原子,.,实例：,(1),L,是正整数,n,的全体正因子关于整除关系构成的,格,则,L,的原子恰为,n,的全体素因子,.,(2),若,L,是,B,的幂集,则,L,的原子就是,B,中元素构成的单元集,(3),图中,L,1,的原子是,b,c,d,L,2,的原子是,b,c,L,3,的原子是,c,b,e,26,有限布尔代数的表示定理,定理,8.9,(,有限布尔代数的表示定理,),设,B,是有限布尔代数,A,是,B,的全体原子构成的集合,则,B,同构,于,A,的幂集代数,P,(,A,).,实例,:(1),S,110,关于,gcd,lcm,运算构成的布尔代数,.,它的原子是,2,5,和,11,因此原子的集合,A,=2,5,11.,幂集,P,(,A,)=,2,5,11,2,5,2,11,5,11,2,5,11.,幂集代数是,.,只要令,f,:,S,110,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,就是从,S,110,到幂集,P,(,A,),的同构映射,.,27,推论,推论,1,任何有限布尔代数的基数为,2,n,n,N.,证 设,B,是有限布尔代数,A,是,B,的所有原子构成的集合,且,|,A,|=,n,n,N,.,由定理得,B,P,(,A,),而,|,P,(,A,)|=2,n,所以,|,B,|=2,n,.,推论,2,任何等势的有限布尔代数都是同构的,.(,证明省略,),结论：,有限布尔代数的基数都是,2,的幂,对于任何自然数,n,仅存在一个,2,n,元的布尔代数,.,28,图,11,实例,下图给出了,1,元,2,元,4,元和,8,元的布尔代数,.,29,第六章,3,习题课,主要内容,格的两个等价定义,格的性质,子格,特殊格：分配格、有界格、有补格、布尔代数,基本要求,能够判别给定偏序集或者代数系统是否构成格,能够确定一个命题的对偶命题,能够证明格中的等式和不等式,能判别格,L,的子集,S,是否构成子格,能够判别给定的格是否为分配格、有补格,能够判别布尔代数并证明布尔代数中的等式,30,练习,1,1,(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,),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,e,a,b,c,d,32,图,13,3,判别下述格,L,是否为分配格,.,L,1,不是分配格,因为它含有与钻石格同构的子格,.,L,2,和,L,3,不是分配格,因为它们含有与五角格同构的子格,.,L,1,L,2,L,3,练习,3,33,L,1,L,2,L,3,图,12,4,针对下图，求出每个格的补元并说明它们是否为有补格,L,1,中,a,与,h,互为补元,其他元素没补元,.,L,2,中,a,与,g,互为补元,.,b,的补元为,c,d,f,；,c,的补元为,b,d,e,f,；,d,的补元为,b,c,e,；,e,的补元为,c,d,f,；,f,的补元为,b,c,e,.,L,3,中,a,与,h,互为补元,b,的补元为,d,；,c,的补元为,d,；,d,的补元为,b,c,g,；,g,的补元为,d,.,L,2,与,L,3,是有补格,.,练习,4,34,5,对于以下各题给定的集合和运算判断它们是哪一类代数,系统（半群、独异点、群、环、域、格、布尔代数）,并说,明理由,.,(1),S,1,=1,1/2,2,1/3,3,1/4,4,为普通乘法,.,(2),S,2,=,a,1,a,2,.,a,n,a,i,a,j,S,2,a,i,a,j,=,a,i,这里的,n,为给定,正整数,n,1.,(3),S,3,=0,1,为普通乘法,.,(4),S,4,=1,2,3,6,x,y,S,4,x,y,与,x,y,分别表示,x,与,y,的最小公倍数和最大公约数,.,(5),S,5,=0,1,为模,2,加法,为模,2,乘法,.,练习,5,35,解：,解答,(1),不是代数系统,因为乘法不封闭,例如,44=16.,(2),是半群但不是独异点,因为运算满足结合律,但是没有单,位元,.,(3),是独异点但不是群,.,因为运算满足结合律,单位元是,1,可,是,0,没有乘法逆元,.,(4),是格,也是布尔代数,.,因为这两个运算满足交换律和分配,律；求最小公倍数运算的单位元是,1,求最大公约数运算,的单位元是,6,满足同一律；两个运算满足补元律,.,(5),是域,.,对于模,n,的环,Z,n,当,n,为素数时构成域,.,36,证,(2),由 反之也对,.,下面证,明它们都等价于,a,b.,由 得,即,a,b,又由,a,b,得,6,设,是布尔代数,证明对于,B,中任意元素,a,b,练习,6,37,练习,7,7.,判断下述代数系统是否为格？是不是布尔代数？,(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),是格,但不是布尔代数,.,38,作业,P151:3,6,7,