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

,*,Click to edit Master text styles,Second level,Third level,Fourth level,Click to edit Master title style,第,11,章 格与布尔代数,离 散 数 学,中国地质大学本科生课程,本章内容,11.1,格的定义与性质,11.2,分配格、有补格,与,布尔代数,本章总结,作业,11.1,格的定义与性质,定义,11.1,设,是偏序集，如果,x,y,S,，,x,y,都有最小上界和最大下界，则称,S,关于偏序,作成一个格,(,lattice,),。,说明：由于最小上界和最大下界的唯一性，可以把求,x,y,的最小上界和最大下界看成,x,与,y,的二元运算,和,。,x,y,：表示,x,与,y,的最小上界,x,y,：表示,x,和,y,的最大下界。,本章出现的,和,符号只代表格中的运算，而不再有其它的含义。,格的实例,例,11.1,设,n,是正整数，,S,n,是,n,的正因子的集合。,D,为整除关系，则偏序集,构成格。,x,y,S,n,，,x,y,是,lcm(x,y),，,即,x,与,y,的最小公倍数。,x,y,是,gcd(x,y,),，,即,x,与,y,的最大公约数。,下图给出了格,，,和,。,例,11.2,例,11.2,判断下列偏序集是否构成格,并说明理由。,(1),，,其中,P(B),是集合,B,的幂集。,(2),，,其中,Z,是整数集,为小于或等于关系。,(3),偏序集的哈斯图分别在下图给出。,例,11.2,解答,(1),是格。,x,y,P(B),，,x,y,就是,x,y,，,x,y,就是,x,y,。,由于,和,运算在,P(B),上是封闭的，所以,x,y,，,x,y,P(B),。,称,为,B,的幂集格。,(2),是格。,x,y,Z,x,y,max(x,y),，,x,y,min(x,y),，,它们都是整数。,(3),都不是格。,(a),中的,a,b,没有最大下界。,(b),中的,b,d,有两个上界,c,和,e,但没有最小上界。,(c),中的,b,c,有三个上界,d,e,f,但没有最小上界。,(d),中的,a,g,没有最大下界。,例,11.3,例,11.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,就是,。,对偶原理,定义,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,说明许多格的性质都是互为对偶命题的。,有了格的对偶原理，在证明格的性质时，只须证明其中的一个命题即可。,格的运算性质,定理,11.1,设,是格，则运算,和,适合交换律、结合律、幂等律和吸收律，即,(1),交换律,a,bL,有,ab,baab,ba,(2),结合律,a,b,cL,有,(ab)c,a(bc)(ab)c,a(bc),(3),幂等律,aL,有,aa,aaa,a,(4),吸收律,a,bL,有,a(ab),aa(ab),a,定理,11.1,(1)ab,和,ba,分别是,a,b,和,b,a,的最小上界。,由于,a,b,b,a,，所以,ab,ba,。,由对偶原理，,ab,ba,得证。,(2),由最小上界的定义有,(a,b),ca,ba,(13.1),(a,b),ca,bb,(13.2),(a,b),cc,(13.3),由式,13.2,和,13.3,有,(a,b),cb,c(13.4),再由式,13.1,和,13.4,有,(a,b),ca,(b,c),同理可证,(a,b),ca,(b,c),根据偏序关系的反对称性有,(a,b),c,a,(b,c),由对偶原理，,(a,b),c,a,(b,c),得证。,定理,11.1,(3),显然,aaa,又由,aa,可得,aaa,。,根据反对称性有,aa,a,，,由对偶原理，,aa,a,得证。,(4),显然,a(ab)a(13.5),又由,aa,，,aba,可得,a(ab)a(13.6),由式,13.5,和,13.6,可得,a(ab),a,，,根据对偶原理，,a(ab),a,得证。,定理,11.2,定理,11.2,设,是具有两个二元运算的代数系统，若对于,*,和,运算适合交换律、结合律、吸收律，则可以适当定义,S,中的偏序,，使得,构成一个格，且,a,bS,有,ab,a*b,，,ab,a,b,。,思路,(1),证明在,S,中,*,和,运算都适合幂等律。,(2),在,S,上定义二元关系,R,，并证明,R,为偏序关系。,(3),证明,构成格。,说明通过规定运算及其基本性质可以给出格的定义。,定理,11.2,a,S,，由吸收律得,(1),证明在,S,中,*,和,运算都适合幂等律。,a*a,a*(a,(a*a),a,同理有,a,a,a,。,(2),在,S,上定义二元关系,R,，,a,b,S,有,R,ab,b,下面证明,R,在,S,上的偏序。,根据幂等律，,a,S,都有,a,a,a,，,即,R,，,所以,R,在,S,上是自反的。,a,bS,有,aRb,且,bRa,a,b,b,且,b,a,a,a,ba,a,b,b (,由于,a b=ba),所以,R,在,S,上是反对称的。,定理,11.2,a,b,c,S,有,aRb,且,bRc a,b,b,且,bc,c,ac,a(bc),ac,(ab)c,ac,bc,c,aRc,这就证明了,R,在,S,上是传递的。,综上所述，,R,为,S,上的偏序。,以下把,R,记作,。,定理,11.2,(3),证明,构成格。即证明,ab,a,b,，,ab,a*b,。,a,b,S,有,a(ab),(aa)b,ab,b(ab),a(bb),ab,根据,的定义有,aab,和,bab,，,所以,a,b,是,a,b,的上界。,假设,c,为,a,b,的上界，,则有,ac,c,和,bc,c,，,从而有,(ab)c,a(bc),ac,c,这就证明了,abc,，,所以,ab,是,a,b,的最小上界，即,ab,ab,为证,a*b,是,a,b,的最大下界，,先证,首先由,ab,b,可知,a*b,a*(ab),a,反之由,a*b,a,可知,ab,(a*b)b,b(b*a),b,再由式,(13.7),和,的定义有,ab a*b,a,，,依照前边的证明,类似地可证,a*b,是,a,b,的最大下界，,即,ab,a*b,。,a,b,b a*b,a(13.7),格的等价定义,根据定理,11.2,，可以给出格的另一个等价定义。,定义,11.3,设,是代数系统，,*,和,是二元运算，如果,*,和,满足交换律，结合律和吸收律，则,构成一个格,(,lattice,),。,说明格中的幂等律可以由吸收律推出。,以后我们不再区别是偏序集定义的格，还是代数系统定义的格，而统称为格,L,。,格的性质,定理,11.3,设,L,是格，则,a,b,L,有,ab,a,b,a,a,b,b,证明,先证,ab,a,b,a,由,aa,和,ab,可知，,a,是,a,b,的下界，,故,aa,b,。,显然又有,a,ba,。,由反对称性得,a,b,a,。,再证,a,b,a,a,b,b,。,根据吸收律有,b,b,(b,a),由,a,b,a,得,b,b,a,即,a,b,b,。,最后证,a,b,b,ab,。,由,aa,b,得,aa,b,b,。,格的性质,定理,11.4,设,L,是格，,a,b,c,d,L,，,若,ab,且,cd,，,则,a,cb,d,，,a,cb,d,证明,a,cab,a,ccd,因此，,a,cb,d,。,同理可证,a,cb,d,。,例,11.5,例,11.5,设,L,是格，证明,a,b,cL,有,a(bc)(ab)(ac),证明由,aa,，,bc,b,得,a(bc)ab,由,aa,，,bc,c,得,a(bc)ac,从而得到,a(bc)(ab)(ac),说明在格中分配不等式成立。,一般说来，格中的,和,运算并不是满足分配律的。,本节小结,偏序集构成格的条件：任意二元子集都有最大下界和最小上界。,格的实例：正整数的因子格，幂集格，子群格。,格的性质：对偶原理，格中算律（交换、结合、幂等、吸收），保序性，分配不等式。,格作为代数系统的定义。,格的证明方法,子格,定义,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,有,ef,c,，,但,c,S,1,。,11.2,分配格、有补格与布尔代数,一般说来，格中运算,对,满足分配不等式，,即,a,b,c,L,，,有,a,(b,c)(a,b),(a,c),但是不一定满足分配律。满足分配律的格称为分配格。,定义,11.5,设,是格，若,a,b,c,L,，,有,a,(b,c),(a,b),(a,c),a,(b,c),(a,b),(a,c),则称,L,为分配格。,说明上面两个等式互为对偶式。,在证明,L,为分配格时，只须证明其中的一个等式即可。,例,11.7,L,1,和,L,2,是分配格，,L,3,和,L,4,不是分配格。,在,L,3,中，,b(cd),be,b,(bc)(bd),aa,a,在,L,4,中,c(bd),ca,c,(cb)(cd),ed,d,钻石格,五角格,分配格的判别,定理,11.5,设,L,是格，则,L,是分配格当且仅当,L,中不含有与钻石格或五角格同构的子格。,证明略。,推论,(1),小于五元的格都是分配格。,(2),任何一条链都是分配格。,例,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,的子格，也同构于钻石格。,格的全下界和全上界,定义,11.6,设,L,是格，,若存在,a,L,使得,x,L,有,ax,，,则称,a,为,L,的,全下界,；,若存在,b,L,使得,x,L,有,xb,，,则称,b,为,L,的,全上界,。,命题格,L,若存在全下界或全上界，一定是唯一的。,证明以全下界为例，假若,a,1,和,a,2,都是格,L,的全下界,则有,a,1,a,2,和,a,2,a,1,。,根据偏序关系的反对称性必有,a,1,a,2,。,记法,将格,L,的全下界记,为,0,，,全上界记为,1,。,有界格,定义,11.7,设,L,是格，,若,L,存在全下界和全上界，则称,L,为,有界格，,并将,L,记为,。,说明有限格,L,一定是有界格。,举例,设,L,是,n,元格，且,L,a,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,关于通常数的小于或等于关系构成的格不是有界格，因为不存在最小和最大的整数。,有界格的性质,定理,（补充）,设,是有界格，则,a,L,有,a,0,0a,0,a,a,1,aa,1,1,证明由,a,00,和,0a,0,可知,a,0,0,。,说明,在有界格中，,全下界,0,是关于,运算的零元，,运算的单位元。,全上界,1,是关于,运算的零元，,运算的单位元。,对偶原理 对于涉及到有界格的命题，如果其中含有全下界,0,或全上界,1,，,在求该命题的对偶命题时，必须将,0,替换,成,1,，,而将,1,替换,成,0,。,例如,a,0,0,和,a,1,1,互为对偶命题，,a,0,a,和,a,1,a,互为对偶命题。,有界格中的补元,定义,11.8,设,是有界格，,a,L,，,若存在,b,L,使得,a,b,0,和,a,b,1,成立，则,称,b,是,a,的,补元,。,说明若,b,是,a,的补元，那么,a,也是,b,的补元。,换句话说，,a,和,b,互为补元。,例,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,。,有界格中补元的说明,在任何有界格中，,全下,界,0,与全上界,1,互补。,对于其他元素，可能存在补元，也可能不存在补元。,如果存在，可能是唯一的，也可能是多个补元。,对于有界分配格，如果它的元素存在补元，一定是唯一的。,有界分配格中补元的唯一性,定理,11.6,设,是有界分配格。,若,a,L,，且对于,a,存在补元,b,，则,b,是,a,的唯一补元。,证明假设,cL,也,是,a,的补元，则有,a,c,1,，,a,c,0,又知,b,是,a,的补元，故,a,b,1,，,a,b,0,从而得到,a,c,a,b,，,a,c,a,b,由于,L,是分配格，根据定理,13.7,，,b,c,。,有补格的定义,定义,11.9,设,是有界格，若,L,中所有元素都有补元存在，则称,L,为有补格。,L,2,L,3,和,L,4,是有补格，,L,1,不是有补格。,L,2,和,L,3,是有补格，,L,1,不是有补格。,本节小结,如果格中一个运算对另一个运算是可分配的，称这个格是分配格。,分配格的两种判别法：,不存在与钻石格或五角格同构的子格；,对于任意元素,a,b,c,有,ab,ac,且,ab,ac,b,c,。,有界格的定义及其实例。,格中元素的补元及其性质（分配格中补元的唯一性）。,有补格的定义。,布尔代数,定义,11.10,如果一个格是有补分配格，则称它为布尔格或布尔代数。,说明在布尔代数中，每个元素都存在着唯一的补元。,可以把求补元的运算看作是布尔代数中的一元运算。,可以把一个布尔代数标记为,，,为求补运算,a,B,，,a,是,a,的补元。,例,11.10,例,11.10,设,S,110,1,2,5,10,11,22,55,110,是,110,的正因子集合。,令,gcd,lcm,分别表示求最大公约数和最小公倍数的运算。问,是否构成布尔代数？为什么？,解答,证明,构成格。,容易验证,x,y,z,S,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,二元运算,交换律,结合律,吸收律,例,11.10,证明,是分配格。,易验证,x,y,z,S,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,互为补元。,综上所述，,为布尔代数。,例,11.10,（,2,）,例,11.10,（,2,）,设,B,为任意集合,证明,B,的幂集格,构成布尔代数，称为,集合代数,。,证明,P(B),关于,和,构成格，因为,和,运算满足交换律、结合律和吸收律。,由于,和,互相可分配，因此,P(B),是分配格，,且全下界是空集,全上界是,B,。,根据绝对补的定义，取全集为,B,，,x,P(B),，,x,是,x,的补元。,从而证明,P(B),是有补分配格，即布尔代数。,布尔代数的性质,定理,11.7,设,是布尔代数，则,(1),a,B,，,(a,),a,(2),a,b,B,，,(a,b),a,b,(a,b),a,b,说明,(1),称为双重否定律,。,(2),称为德摩根律。,命题代数与集合代数的双重否定律与德摩根律实际上是这个定理的特例。,可以证明德摩根律对有限个元素也是正确的。,证明,(1)(a,),是,a,的补元，,a,也是,a,的补元。,由补元的唯一性得,(a,),a,。,定理,11.7(2),的证明,(2),a,b,B,，,(a,b),a,b,(a,b),a,b,(a,b),(a,b,),(a,a,b,),(b,a,b,),(1,b,),(a,1),1,1,1,(a,b),(a,b,),(a,b,a,),(a,b,b,),(0,b),(a,0),0,0,0,所以,a,b,是,a,b,的补元,，,根据补元的唯一性有,(a,b),a,b,同理可证,(a,b),=a,b,。,布尔代数作为代数系统的定义,定义,11.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,则称,是一个布尔代数,。,关于布尔代数定义的说明,所谓同一律就是指运算含有单位元的性质，这里,的,1,是,*,运算的单位元，,0,是运算,的单位元。,可以证明,1,和,0,分别也是,和,*,运算,的零元。,a,B,有,a,1,(,a,1),*1,（同一律）,1*,(,a,1),（交换律）,(,a,a,),*,(,a,1),（补元律）,a,(,a,*,1,),（分配律）,a,a,（同一律）,1,（补元律）,同理可,证,a,*,0,0,。,关于布尔代数定义的说明,为证明以上定义,的,是布尔代数，只需证明它是一个格，即证明,*,和,运算满足结合律和吸收律。,证明吸收律,，,a,b,B,有,a,(a,*,b),(,a,*1),(a,*,b),（同一律）,a,*(1,b,),（分配律）,a,*1,（,1,是,运算的零元,),a,（同一律）,同理有,a,*,(ab),a,。,关于布尔代数定义的说明,为证结合律，先证以下命题：,a,b,c,B,，,ab,ac,且,ab,ac b,c,由,ab,ac,且,ab,ac,可得,(ab),*,(ab),(ac),*,(ac),由分配律和交换律得,(a,*,a)b,(a,*,a)c,由补元律得,0b,0c,由同一律和交换律得,b,c,关于布尔代数定义的说明,使用这个命题，为证明,(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),式成立。,关于布尔代数定义的说明,下面证明,(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)(,交换律,补元,律,),(ab),*,(a,c)(,交换律,同一律,),a,(,b,*c,),(,分配律,),所以（,2,）式成立。,有限布尔代数的结构,定义,11.12,设,L,是格，,0,L,，,a,L,，,若,b,L,有,0,ba,b,a,则称,a,是,L,中的原子,。,考虑右图中的几个格。,L,1,的原子,是,a,。,L,2,的原子是,a,b,c,。,L,3,的原子,是,a,和,b,。,若,L,是正整数,n,的全体正因子关于整除关系构成的格，则,L,的原子恰为,n,的全体质因子。,若,L,是集合,B,的幂集合，则,L,的原子就是由,B,中元素构成的单元集。,有限布尔代数的表示定理,定理,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,y,B,，,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),。,定理,11.8,证明,任取,x,y,B,，设,x,a,1,a,2,a,n,，,y,b,1,b,2,b,m,是,x,y,的原子表示，则,x,y,a,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),定理,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),的同态映射。,定理,11.8,证明,下面证明,为双射。,假设,(x),(y),，则有,T(x),T(y),a,1,a,2,a,n,由引理,2,可知,x,a,1,a,2,a,n,y,于是,为单射。,任取,b,1,b,2,b,m,P(A,),，,令,x,b,1,b,2,b,m,，则,(x),T(x),b,1,b,2,b,m,于是,为满射。,定理得证。,例子,考虑,110,的正因子的集合,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,。,幂集代数,是,。,只要令,: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),的同构映射。,推论,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,。,推论,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,得证。,有限布尔代数的说明,有限布尔代数的基数都是,2,的幂。,在同构意义上，对于任何,2,n,，,n,为自然数，仅存在一个,2,n,元的布尔代数。,下图给出了,1,元,2,元,4,元和,8,元的布尔代数。,主要内容,布尔代数的两个等价定义：,有补分配格；,有两个二元运算并满足交换律、分配律、同一律和补元律的代数系统。,布尔代数的特殊性质：双重否定律和德摩根律。,对于任意自然数,n,，只有一个,2,n,元的有限布尔代数，就是幂集代数。,学习要求,能够判断给定偏序集或者代数系统是否构成格。,能够确定一个命题的对偶命题。,能够证明格中的等式和不等式。,能够判别格,L,的子集,S,是否构成格。,能够判别给定的格是否为分配格。,能够判别布尔代数并证明布尔代数的等式。,作业,习题十三,1,，,2,，,3,，,6,，,8,，,12,，,16,，,17,，,19,格的证明方法,格中等式的证明方法,证明等式的左边“小于等于”右边，右边“小于等于”左边。,根据偏序关系的反对称性，得到需要的等式。,格中不等式的证明方法,aa(,偏序关系的自反性,),ab,且,bc,ac(,偏序关系的传递性,),aba,，,abb,，,aab,，,b,ab,(,下界定义与上界的定义,),ab,且,ac,abc,，,ba,且,ca bca,(,最大下界定义与最小上界的定义,),ab,且,cd acbd,，,acbd(,保序性,),