离散数学格与布尔代数.pptx

Click to edit Master text styles,Second level,Third level,Fourth level,Click to edit Master title style,第11章 格与布尔代数,离 散 数 学,中国地质大学本科生课程,第1页,本章内容,11.1,格定义与性质,11.2,分配格、有补格,与,布尔代数,本章总结,作业,第2页,11.1 格定义与性质,定义11.1,设是偏序集，,假如,x,y,S，,x,y,都有最小上界和最大下界,，则称S关于偏序作成一个,格,(,lattice,),。,说明：,因为最小上界和最大下界唯一性，能够把求,x,y最小上界和最大下界看成x与y二元运算和。,x,y,：表示x与y最小上界,x,y,：表示x和y最大下界。,本章出现和符号只代表格中运算，而不再有其它含义。,第3页,格实例,例11.1,设n是正整数，S,n,是n正因子集合。D为整除关系，则偏序集组成格。,x,yS,n,，,xy是lcm(x,y)，即x与y最小公倍数。,xy是gcd(x,y)，即x与y最大条约数。,下列图给出了格，和。,第4页,例11.2,例11.2,判断以下偏序集是否组成格,并说明理由。,(1)，其中P(B)是集合B幂集。,(2)，其中Z是整数集,为小于或等于关系。,(3)偏序集哈斯图分别在下列图给出。,第5页,例11.2,解答1)是格。,x,yP(B)，xy就是xy，xy就是xy。,因为和运算在P(B)上是封闭，所以xy，xyP(B)。,称,为B,幂集格,。,(2)是格。,x,yZ,xymax(x,y)，xymin(x,y)，它们都是整数。,(3)都不是格。,(a)中a,b没有最大下界。,(b)中b,d有两个上界c和e,但没有最小上界。,(c)中b,c有三个上界d,e,f,但没有最小上界。,(d)中a,g没有最大下界。,第6页,例11.3,例11.3,设G是群，L(G)是G全部子群集合。即,L(G)H|HG,对任意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,就是。,第7页,对偶原理,定义11.2,设f是含有格中元素以及符号、和命题。令f,*,是将f中替换成，替换成，替换成，替换成所得到命题。称f,*,为f,对偶命题,。,比如,在格中令f是(ab)cc，则f,*,是(ab)cc。,格对偶原理,设f是含有格中元素以及符号、和命题。若f对一切格为真，则f对偶命题f,*,也对一切格为真。,比如,对一切格L都有,a,bL，aba,(因为a和b交是a一个下界),那么,对一切格L都有a,bL，aba,说明,许多格性质都是互为对偶命题。,有了格对偶原理，在证实格性质时，只须证实其中一个命题即可。,第8页,格运算性质,定理11.1,设是格，则运算和适合,交换律,、,结合律,、,幂等律,和,吸收律,，即,(1)交换律,a,bL 有,abbaabba,(2)结合律,a,b,cL 有,(ab)ca(bc)(ab)ca(bc),(3)幂等律,aL 有,aaaaaa,(4)吸收律,a,bL 有,a(ab)aa(ab)a,第9页,定理11.1,(1)ab和ba分别是a,b和b,a最小上界。,因为a,bb,a，所以abba。,由对偶原理，abba得证。,(2)由最小上界定义有,(ab)caba(13.1),(ab)cabb(13.2),(ab)cc(13.3),由式13.2和13.3有(ab)cbc(13.4),再由式13.1和13.4有(ab)ca(bc),同理可证(ab)ca(bc),依据偏序关系反对称性有(ab)ca(bc),由对偶原理，(ab)ca(bc)得证。,第10页,定理11.1,(3)显然aaa,又由aa可得 aaa。,依据反对称性有 aaa，,由对偶原理，aaa 得证。,(4)显然a(ab)a(13.5),又由 aa，aba 可得,a(ab)a(13.6),由式13.5和13.6可得 a(ab)a，,依据对偶原理，a(ab)a 得证。,第11页,定理11.2定理11.2,设是含有两个二元运算代数系统，若对于*和,运算适合,交换律,、,结合律,、,吸收律,，则能够适当定义S中偏序，使得组成一个格，且a,bS有aba*b，aba,b。,思绪,(1)证实,在S中*和,运算都适合幂等律,。,(2)在S上定义二元关系R，并证实R为偏序关系。,(3)证实组成格。,说明,经过要求运算及其基本性质能够给出格定义。,第12页,定理11.2,a,S，由吸收律得,(1)证实在S中*和,运算都适合幂等律,。,a*a,a*,(,a,(a*a),a,同理有 a,aa。,(2)在S上定义二元关系R，,a,b,S 有,R,abb,下面证实R在S上偏序。,依据幂等律，,a,S都有a,aa，,即R，,所以R在S上是自反。,a,bS 有,aRb且bRa,a,bb且b,aa,abaabb (因为a b=ba),所以R在S上是反对称。,第13页,定理11.2,a,b,c,S,有,aRb且bRc abb 且 bcc,aca(bc),ac(ab)c,acbcc,aRc,这就证实了R在S上是传递。,总而言之，R为S上偏序。,以下把R记作。,第14页,定理11.2,(3)证实组成格。即证实aba,b，aba*b。,a,b,S,有,a(ab)(aa)bab,b(ab)a(bb)ab,依据定义有 aab和bab，,所以ab是a,b上界。,假设 c为a,b上界，,则有acc和bcc，,从而有,(ab)c,a(bc),ac,c,这就证实了abc，,所以ab是a,b最小上界，即,abab,为证a*b是a,b最大下界，,先证,首先由abb 可知,a*b,a*(ab),a,反之由a*ba 可知,ab,(a*b)b,b(b*a),b,再由式(13.7)和定义有 ab a*ba，,依照前边证实,类似地可证 a*b是a,b最大下界，,即 aba*b。,a,bb a*ba(13.7),第15页,格等价定义,依据定理11.2，能够给出格另一个等价定义。,定义11.3,设是代数系统，*和,是二元运算，假如*和,满足交换律，结合律和吸收律，则组成一个,格,(,lattice,),。,说明,格中幂等律能够由吸收律推出。,以后我们不再区分是偏序集定义格，还是代数系统定义格，而统称为格L。,第16页,格性质,定理11.3,设L是格，则,a,bL 有,ab,aba,abb,证实,先证 ab,aba,由aa和ab可知，a是a,b下界，,故aab。显然又有aba。,由反对称性得aba。,再证 aba,abb。,依据吸收律有 bb(ba),由aba得 bba,即abb。,最终证abb,ab。,由aab得 aabb。,第17页,格性质,定理11.4,设L是格，,a,b,c,dL，若ab且cd，则,acbd，acbd,证实,acab,accd,所以，acbd。,同理可证 acbd。,第18页,例11.5例11.5,设L是格，证实,a,b,cL 有,a(bc)(ab)(ac),证实,由 aa，bcb 得,a(bc)ab,由 aa，bcc 得,a(bc)ac,从而得到 a(bc)(ab)(ac),说明,在格中分配不等式成立。,普通说来，格中和运算并不是满足分配律。,第19页,本节小结,偏序集组成格条件：任意二元子集都有最大下界和最小上界。,格实例：正整数因子格，幂集格，子群格。,格性质：对偶原理，格中算律（交换、结合、幂等、吸收），保序性，分配不等式。,格作为代数系统定义。,格证实方法,第20页,子格,定义11.4,设是格，S是L非空子集，若S关于L中运算和仍组成格，则称S是L,子格,。,例11.6,设格L如右图所表示。令,S,1,a,e,f,g,S,2,a,b,e,g,则S,1,不是L子格，S,2,是L子格。,因为对于e和f,有efc，,但c,S,1,。,第21页,11.2 分配格、有补格与布尔代数,普通说来，格中运算对满足分配不等式，,即,a,b,cL，有,a(bc)(ab)(ac),不过不一定满足分配律。满足分配律格称为,分配格,。,定义11.5,设是格，若,a,b,cL，有,a(bc)(ab)(ac),a(bc)(ab)(ac),则称L为,分配格,。,说明,上面两个等式互为对偶式。,在证实L为分配格时，只须证实其中一个等式即可。,第22页,例11.7,L,1,和L,2,是分配格，L,3,和L,4,不是分配格。,在L,3,中，b(cd),beb,(bc)(bd),aaa,在L,4,中,c(bd),cac,(cb)(cd),edd,钻石格,五角格,第23页,分配格判别,定理11.5,设L是格，则L是分配格当且仅当L中不含有与钻石格或五角格同构子格。,证实,略。,推论,(1)小于五元格都是分配格。,(2)任何一条链都是分配格。,第24页,例11.8,说明下列图中格是否为分配格，为何？,L,1,L,2,和L,3,都不是分配格。,a,b,c,d,e是L,1,子格，而且同构于钻石格。,a,b,c,e,f是L,2,子格，而且同构于五角格。,a,c,b,e,f是L,3,子格，也同构于钻石格。,第25页,格全下界和全上界,定义11.6,设L是格，,若存在aL使得,xL有,ax,，则称a为L,全下界,；,若存在bL使得,xL有,xb,，则称b为L,全上界,。,命题,格L若存在全下界或全上界，一定是唯一。,证实,以全下界为例，假若a,1,和a,2,都是格L全下界,则有a,1,a,2,和a,2,a,1,。,依据偏序关系反对称性必有a,1,a,2,。,记法,将格L,全下界记为0,，,全上界记为1,。,第26页,有界格,定义11.7,设L是格，若L存在全下界和全上界，则称L为,有界格,，并将,L记为,。,说明,有限格L一定是有界格。,举例,设L是,n元格,，且La,1,a,2,a,n,，那么a,1,a,2,a,n,是L全下界，而a,1,a,2,a,n,是L全上界。所以L是有界格。,对于,无限格L,来说，有是有界格，有不是有界格。,如集合B,幂集格,，不论B是有穷集还是无穷集，它都是有界格。它全下界是空集,，,全上界是B。,整数集Z,关于通常数小于或等于关系组成格不是有界格，因为不存在最小和最大整数。,第27页,有界格性质,定理（补充）,设是有界格，则,aL有,a00a0a,a1aa11,证实,由 a00 和 0a0 可知 a00。,说明,在有界格中，,全下界0是关于运算零元，运算单位元。,全上界1是关于运算零元，运算单位元。,对偶原理,对于包括到有界格命题，假如其中含有全下界0或全上界1，在求该命题对偶命题时，必须将0替换成1，而将1替换成0。,比如,a00 和 a11 互为对偶命题，,a0a 和 a1a 互为对偶命题。,第28页,有界格中补元,定义11.8,设是有界格，aL，,若存在bL 使得,ab0,和,ab1,成立，则称b是a,补元,。,说明,若b是a补元，那么a也是b补元。,换句话说，a和b互为补元。,第29页,例11.9,考虑下列图中四个格。,L,1,中a与c互为补元，其中a为全下界，c为全上界，b没有补元。,L,2,中a与d互为补元，其中a为全下界，d为全上界，b与c也互为补元。,L,3,中a与e互为补元，其中a为全下界，e为全上界，b补元是c和d，c补元是b和d，d补元是b和c。b,c,d每个元素都有两个补元。,L,4,中a与e互为补元。其中a为全下界。e为全上界。b补元是c和d，c补元是b，d补元是b。,第30页,有界格中补元说明,在任何有界格中，,全下界0与全上界1互补。,对于其它元素，可能存在补元，也可能不存在补元。,假如存在，可能是唯一，也可能是多个补元。,对于有界分配格，假如它元素存在补元，一定是唯一。,第31页,有界分配格中补元唯一性,定理11.6,设是有界分配格。,若aL，且对于a存在补元b，则b是a唯一补元。,证实,假设cL也是a补元，则有,ac1，ac0,又知b是a补元，故,ab1，ab0,从而得到,acab，acab,因为L是分配格，依据定理13.7，bc。,第32页,有补格定义,定义11.9,设是有界格，若L中全部元素都有补元存在，则称L为,有补格,。,L,2,L,3,和L,4,是有补格，,L,1,不是有补格。,L,2,和L,3,是有补格，,L,1,不是有补格。,第33页,本节小结,假如格中一个运算对另一个运算是可分配，称这个格是分配格。,分配格两种判别法：,不存在与钻石格或五角格同构子格；,对于任意元素a,b,c,有 abac且abac,bc。,有界格定义及其实例。,格中元素补元及其性质（分配格中补元唯一性）。,有补格定义。,第34页,布尔代数,定义11.10,假如一个格是,有补分配格,，则称它为,布尔格,或,布尔代数,。,说明,在布尔代数中，每个元素都存在着唯一补元。,能够把求补元运算看作是布尔代数中一元运算。,能够把一个布尔代数标识为,，,为求补运算,aB，a是a补元。,第35页,例11.10,例11.10,设S,110,1,2,5,10,11,22,55,110是110正因子集合。令gcd,lcm分别表示求最大条约数和最小公倍数运算。问是否组成布尔代数？为何？,解答,证实组成格。,轻易验证,x,y,zS,110,，有,gcd(x,y)S,110,lcm(x,y)S,110,gcd(x,y)gcd(y,x),lcm(x,y)lcm(y,x),gcd(gcd(x,y),z)gcdx,gcd(y,z),lcm(lcm(x,y),z)lcm(x,lcm(y,z),gcd(x,lcm(x,y)x,lcm(x,gcd(x,y)x,二元运算,交换律,结合律,吸收律,第36页,例11.10,证实 是分配格。,易验证,x,y,zS,110,有,gcd(x,lcm(y,z)lcm(gcd(x,y),gcd(x,z),证实 是有补格。,1 为S,110,中全下界,110为S,110,中全上界,1和110互为补元，2和55互为补元，,5和22互为补元，10和11互为补元。,总而言之，为布尔代数。,第37页,例11.10（2）,例11.10（2）,设B为任意集合,证实B,幂集格,组成布尔代数，称为,集合代数,。,证实,P(B)关于和组成格，因为,和运算满足交换律、结合律和吸收律。,因为和相互可分配，所以P(B)是分配格，,且全下界是空集,全上界是B。,依据绝对补定义，取全集为B，,xP(B)，x是x补元。,从而证实P(B)是有补分配格，即布尔代数。,第38页,布尔代数性质,定理11.7,设是布尔代数，则,(1),aB，(a)a,(2),a,bB，(ab)ab,(ab)ab,说明,(1)称为,双重否定律,。,(2)称为,德摩根律,。,命题代数与集合代数双重否定律与德摩根律实际上是这个定理特例。,能够证实德摩根律对有限个元素也是正确。,证实,(1)(a,),是a,补元，a也是a,补元。,由补元唯一性得(a,),a。,第39页,定理11.7(2)证实,(2),a,bB，(ab)ab,(ab)ab,(ab),(ab),(,aa,b)(,b,a,b,),(1b)(a1),11,1,(ab),(ab),(,a,b,a,)(a,bb,),(0b)(a0),000,所以ab是ab补元，依据补元唯一性有,(ab)ab,同理可证(ab)=ab。,第40页,布尔代数作为代数系统定义,定义11.11,设是代数系统，*和,是二元运算。,若*和运算满足：,(1),交换律,，即,a,bB 有,a*bb*a，a,bb,a,(2),分配律,，即,a,b,cB有,a*(b,c)(a*b),(a*c)a,(b*c)(a,b)*(a,c),(3),同一律,，即存在0,1B，使得,aB 有,a*1a，a,0a,(4),补元律,，即,aB,存在a,B，使得,a*a,0，a,a,1,则称是一个,布尔代数,。,第41页,关于布尔代数定义说明,所谓,同一律就是指运算含有单位元性质,，这里1是*运算单位元，0是运算,单位元。,能够证实1和0分别也是,和*运算零元。,aB,有,a,1(,a,1),*1,（同一律）,1,*,(,a,1)（交换律）,(,a,a,),*,(,a,1)（补元律）,a,(,a*,1,)（分配律）,a,a,（同一律）,1 （补元律）,同理可证 a*,00。,第42页,关于布尔代数定义说明,为证实以上定义,是布尔代数，只需证实它是一个格，即,证实*和运算满足结合律和吸收律。,证实吸收律,，,a,bB有,a,(a,*,b),(,a*,1),(,a,*,b),（同一律）,a*(,1,b,)（分配律）,a*1,（,1是运算零元),a,（同一律）,同理有,a*,(ab),a。,第43页,关于布尔代数定义说明,为证结合律，先证以下命题：,a,b,cB，,abac 且 abac bc,由 abac 且 abac 可得,(ab),*,(ab)(ac),*,(ac),由分配律和交换律得,(a,*,a)b(a,*,a)c,由补元律得,0b0c,由同一律和交换律得,bc,第44页,关于布尔代数定义说明,使用这个命题，为证实,(a,*,b),*c,a,*(,b,*c,),，只需证实以下两个等式：,(1)a(a,*,b),*c),a(a,*(,b,*c,),(2)a(a,*,b),*c),a(a,*(,b,*c,),先证实第一个等式，由吸收律有,a(a,*(,b,*c),a,a(a,*,b),*c),(,a(a,*,b),*,(a,c)(,分配律,),a,*,(a,c)(,吸收律,),a,所以(1)式成立。,第45页,关于布尔代数定义说明,下面证实(2)式：a(a,*,b),*c),a(a,*(,b,*c,),a,(a,*(,b,*c,),(,aa,),*(,a,(,b,*c,),(分配律,),1*,(,a,(,b,*c,)(交换律,补元律),a,(,b,*c,)(交换律,同一律),a,(a,*,b),*c),(,a,(a,*,b)*(a,c)(,分配律,),(,aa,),*,(ab),*,(a,c)(,分配律,),(,1*,(ab),*,(a,c)(,交换律,补元律,),(,a,b),*,(,a,c)(,交换律,同一律,),a,(,b,*c,),(,分配律,),所以（2）式成立。,第46页,有限布尔代数结构,定义11.12,设L是格，0L，aL，若,bL 有,0ba,ba,则称a是L中,原子,。,考虑右图中几个格。,L,1,原子是a。,L,2,原子是a,b,c。,L,3,原子是a和b。,若L是正整数n全体正因子关于整除关系组成格，则L原子恰为n全体质因子。,若L是集合B幂集合，则L原子就是由B中元素组成单元集。,第47页,有限布尔代数表示定理,定理11.8(有限布尔代数表示定理),设B是有限布尔代数，,A是B全体原子组成集合,，则B同构于A幂集代数P(A)。,证实,任取xB，令T(x)a|aB,a是原子且a,x,则T(x),A，定义函数,：B,P(A)，,(x)T(x)，,xB,下面证实,是,B到,P(A)同构映射。,任取x,yB，,b 有,b,T(x,y,),bA 且 b,x,y,(bA且b,x),且(bA且by),b,T(x),且b,T(,y,),b,T(x)T(y),从而有 T(x,y,)T(x)T(y)，,即,x,y,B 有,(x,y,),(x),(y)。,第48页,定理11.8证实,任取x,y,B，设,xa,1,a,2,a,n,，,yb,1,b,2,b,m,是x,y原子表示，则,x,ya,1,a,2,a,n,b,1,b,2,b,m,由引理2可知,T(x,y)a,1,a,2,a,n,b,1,b,2,b,m,又因为,T(x)a,1,a,2,a,n,，,T(y)b,1,b,2,b,m,所以 T(x,y)T(x)T(y),即,(x,y),(x),(y),第49页,定理11.8证实,任取x,B，存在,x,B 使得,xx,1，,xx,0,所以有,x),(x,),(xx,),(1)A,(x),(x,),(xx,),(0),而和,A,分别为P(,A,)全下界和全上界，,所以,(x,),是,(x),在P(,A,)中补元，即,(x,),(x),总而言之，,是B到P(A)同态映射。,第50页,定理11.8证实,下面证实,为双射。,假设,(x),(y)，则有,T(x)T(y)a,1,a,2,a,n,由引理2可知,xa,1,a,2,a,n,y,于是,为单射。,任取b,1,b,2,b,m,P(A)，,令,xb,1,b,2,b,m,，则,(x)T(x)b,1,b,2,b,m,于是,为满射。,定理得证。,第51页,例子,考虑110正因子集合S,110,关于gcd,lcm运算组成布尔代数。,它原子是2、5和11，所以原子集合A2,5,11。,幂集P(A),2,5,11,2,5,2,11,5,11,2,5,11。,幂集代数是。,只要令,:S,110,P(A)，,(1),，,(2)2，,(5)5，,(11)11，,(10)2,5，,(22)2,11，,(55)5,11,(110)A，,那么f就是定理13.11中从S,110,到幂集P(A)同构映射。,第52页,推论1,推论1,任何有限布尔代数基数为2,n,，,n,N。,证实,设B是有限布尔代数，A是B全部原子组成集合，,且|A|,n,，,n,N。,由定理13.11 得,B,P(A)，而|P(A)|2,n,，所以|B|2,n,。,第53页,推论2,推论2,任何等势有限布尔代数都是同构。,证实,设B,1,和B,2,是有限布尔代数，且|B,1,|=|B,2,|。,则B,1,P(A,1,)，B,2,P(A,2,)，其中A,1,和A,2,分别为B,1,和B,2,原子集合。,易见|A,1,|A,2,|，存在双射f：A,1,A,2,。令,：,P(A,1,)P(A,2,)，,(x)f(x)，x,A,1,下面证实,是,P(A,1,),到,P(A,2,)同构映射。,任取x,yP(A,1,)，由定理7.5有,f(xy)f(x)f(y)f(xy),f(x)f(y),又因为f单射性，必有,f(xy)f(x)f(y),因为,f(x)f(,x,)f(x,x,)f(,),f(x)f(,x,)f(x,x,)f(A,1,)A,2,得 f(,x,),f(x)，这就证实了,是,P(A,1,),到,P(A,2,)同态映射。,总而言之,有P(A,1,),P(A,2,),依据习题十三章第19题，B,1,B,2,得证。,第54页,有限布尔代数说明,有限布尔代数基数都是2幂。,在同构意义上，对于任何,2,n,，,n,为自然数，,仅存在一个2,n,元布尔代数,。,下列图给出了1元,2元,4元和8元布尔代数。,第55页,主要内容,布尔代数两个等价定义：,有补分配格；,有两个二元运算并满足交换律、分配律、同一律和补元律代数系统。布尔代数特殊性质：双重否定律和德摩根律。,对于任意自然数n，只有一个2,n,元有限布尔代数，就是幂集代数。,第56页,学习要求,能够判断给定偏序集或者代数系统是否组成格。,能够确定一个命题对偶命题。,能够证实格中等式和不等式。,能够判别格L子集S是否组成格。,能够判别给定格是否为分配格。,能够判别布尔代数并证实布尔代数等式。,第57页,作业,习题十三,1，2，3，6，8，12，16，17，19,第58页,格证实方法,格中等式证实方法,证实等式左边“小于等于”右边，右边“小于等于”左边。,依据偏序关系反对称性，得到需要等式。,格中不等式证实方法,aa(偏序关系自反性),ab且bc,ac(偏序关系传递性),aba，abb，aab，bab,(下界定义与上界定义),ab且ac,abc，ba且ca bca,(最大下界定义与最小上界定义),ab且cd acbd，acbd(保序性),第59页,