离散数学第11章-格与布尔代数省名师优质课赛课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,第十一章 格与布尔代数,主要内容,格定义及性质,子格,分配格、有补格,布尔代数,1/20,1,11.1,格定义与性质,定义11.1,设是偏序集，假如,x,y,S,，,x,y,都有最小上,界和最大下界，则称,S,关于偏序作成一个,格,.（偏序关系P126）,求,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,最大条约数.,2/20,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/20,3,格性质：算律,定理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,)=,a,4/20,4,格性质：序与运算关系,定理11.3,设,L,是格,则,a,b,L,有,a,b,a,b,=,a,a,b,=,b,能够用集合例子来验证 幂集格,，其中,P,(,B,)是集合,B,幂集.,幂集格.,x,y,P,(,B,)，,x,y,就是,x,y,，,x,y,就是,x,y,.5/20,5,格性质：保序,定理11.4,设,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,)（注意最大下界）,注意：普通说来,格中和运算不满足分配律.,6/20,6,格作为代数系统定义,定理11.4设是含有两个二元运算代数系统,若对于,和,运算适合交换律、结合律、吸收律,则能够适当定义,S,中,偏序,使得 组成格,且,a,b,S,有,a,b,=,a,b,a,b,=,a,b,.,证实省略.依据定理11.4,能够给出格另一个等价定义.,定义11.3,设是代数系统,和,是二元运算,假如,和,满足交换律、结合律和吸收律,则组成格.,7/20,7,11.2,分配格、有补格与布尔代数,定义11.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,为,五角格,.,实例,8/20,8,有界格定义,定义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,记为.,9/20,9,定理11.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是关于运算零元,运算单位元.,有界格性质,10/20,10,有界格中补元及实例,定义11.8,设是有界格,a,L,若存在,b,L,使得 ,a,b,=0 和,a,b,=1,成立,则称,b,是,a,补元,.,注意：若,b,是,a,补元,那么,a,也是,b,补元.,a,和,b,互为补元.,例7,考虑下列图中格.针对不一样元素，求出全部补元.,11/20,11,解答,(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,.,12/20,12,有界分配格补元惟一性,定理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=b,(b,a),=,b,(,c,a,)=(,b,c),(,b,a,)=(,a,c),c=c,注意：,在任何有界格中,全下界0与全上界1互补.,对于普通元素,可能存在补元,也可能不存在补元.假如存在补元,可能是惟一,也可能是多个补元.对于有界分配格,假如元素存在补元,一定是惟一.,13/20,13,图9,有补格定义,定义11.9,设是有界格,若,L,中全部元素都有补,元存在,则称L,为,有补格,.,比如,图中,L,2,L,3,和,L,4,是有补格,L,1,不是有补格.,14/20,14,布尔代数定义与实例,定义11.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互为补元,从而证实了为布尔代数.,15/20,15,布尔代数性质,定理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)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,.,注意：德摩根律对有限个元素也是正确.,16/20,16,图11,实例,下列图给出了,1 元,2 元,4 元和 8 元布尔代数.,17/20,17,第十一章 习题课,主要内容,格两个等价定义,格性质,子格,特殊格：分配格、有界格、有补格、布尔代数,基本要求,能够判别给定偏序集或者代数系统是否组成格,能够确定一个命题对偶命题,能够证实格中等式和不等式,能判别格,L,子集,S是否组成子格,能够判别给定格是否为分配格、有补格,能够判别布尔代数并证实布尔代数中等式,18/20,18,解,1求图中格全部子格.,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,练习,1,e,a,b,c,d,19/20,19,L,1,L,2,L,3,图12,2,针对下列图，求出每个格补元并说明它们是否为有补格,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,是有补格.,练习,2,20/20,20,