11格与布尔代数

,*,Click to edit Master text styles,Second level,Third level,Fourth level,Click to edit Master title style,第11章 格与布尔代数,离 散 数 学,本章内容,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)gcd(x,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,