离散数学ppt课件第十三章格与布尔代数.ppt

《离散数学ppt课件第十三章格与布尔代数.ppt》由会员分享，可在线阅读，更多相关《离散数学ppt课件第十三章格与布尔代数.ppt（84页珍藏版）》请在三一办公上搜索。

1、第13章 格与布尔代数,本章内容,13.1 格的定义与性质13.2 子格与格同态13.3 分配格与有补格13.4 布尔代数本章总结作业,13.1 格的定义与性质,定义13.1 设是偏序集，如果x,yS，x,y都有最小上界和最大下界，则称S关于偏序作成一个格(lattice)。说明：由于最小上界和最大下界的唯一性，可以把求x,y的最小上界和最大下界看成x与y的二元运算和。xy：表示x与y的最小上界xy：表示x和y的最大下界。本章出现的和符号只代表格中的运算，而不再有其它的含义。,格的实例,例13.1 设n是正整数，Sn是n的正因子的集合。D为整除关系，则偏序集构成格。x,ySn，xy是lcm(x

2、,y)，即x与y的最小公倍数。xy是gcd(x,y)，即x与y的最大公约数。下图给出了格，和。,例13.2,例13.2 判断下列偏序集是否构成格,并说明理由。(1)，其中P(B)是集合B的幂集。(2)，其中Z是整数集,为小于或等于关系。(3)偏序集的哈斯图分别在下图给出。,例13.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

3、)中的b,c有三个上界d,e,f,但没有最小上界。(d)中的a,g没有最大下界。,例13.3,例13.3 设G是群，L(G)是G的所有子群的集合。即L(G)H|HG 对任意的H1,H2L(G)，H1H2也是G的子群，而是由H1H2生成的子群（即包含着H1H2的最小的子群）。在L(G)上定义包含关系，则L(G)关于包含关系构成一个格，称为G的子群格。易见在L(G)中，H1H2就是H1H2，H1H2就是。,对偶原理,定义13.2 设f是含有格中元素以及符号、和的命题。令f*是将f中的替换成，替换成，替换成，替换成所得到的命题。称f*为f的对偶命题。例如 在格中令f是(ab)cc，则f*是(ab)c

4、c。格的对偶原理 设f是含有格中元素以及符号、和的命题。若f对一切格为真，则f的对偶命题f*也对一切格为真。例如 对一切格L都有 a,bL，aba(因为a和b的交是a的一个下界)那么对一切格L都有 a,bL，aba说明许多格的性质都是互为对偶命题的。有了格的对偶原理，在证明格的性质时，只须证明其中的一个命题即可。,格的运算性质,定理13.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,定理

5、13.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)得证。,定理13.1,(3)显然aaa,又由aa可得 aaa。根据反对称性有 aaa，由对偶原理，aaa 得证。(4)显然a(ab)a(13.5)又由 aa，aba 可得a(ab)

6、a(13.6)由式13.5和13.6可得 a(ab)a，根据对偶原理，a(ab)a 得证。,定理13.2,定理13.2 设是具有两个二元运算的代数系统，若对于*和运算适合交换律、结合律、吸收律，则可以适当定义S中的偏序，使得构成一个格，且a,bS有aba*b，abab。思路(1)证明在S中*和运算都适合幂等律。(2)在S上定义二元关系R，并证明R为偏序关系。(3)证明构成格。说明通过规定运算及其基本性质可以给出格的定义。,定理13.2,aS，由吸收律得,(1)证明在S中*和运算都适合幂等律。,a*a,a*(a(a*a),a,同理有 aaa。,(2)在S上定义二元关系R，,a,bS 有,R ab

7、b,下面证明R在S上的偏序。,根据幂等律，,aS都有aaa，,即R，,所以R在S上是自反的。,a,bS 有,aRb且bRa,abb且baa,abaabb(由于a b=ba),所以R在S上是反对称的。,定理13.2,a,b,cS 有aRb且bRc abb 且 bcc aca(bc)ac(ab)c acbcc aRc这就证明了R在S上是传递的。综上所述，R为S上的偏序。以下把R记作。,定理13.2,(3)证明构成格。即证明abab，aba*b。,a,bS 有,a(ab)(aa)bab,b(ab)a(bb)ab,根据的定义有 aab和bab，,所以ab是a,b的上界。,假设 c为a,b的上界，,则有

8、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。,abb a*ba(13.7),格的等价定义,根据定理13.2，可以给出格的另一个等价定义。定义13.3 设是代数系统，*和是二元运算，如果*和满足交换律，结合律和吸收律，则构成一个格(lattice)。说明格中的

9、幂等律可以由吸收律推出。以后我们不再区别是偏序集定义的格，还是代数系统定义的格，而统称为格L。,格的性质,定理13.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。,格的性质,定理11.4 设L是格，a,b,c,dL，若ab且cd，则acbd，acbd证明 acabaccd因此，acbd。同理可证 acbd。,例13.4,例13.4 设L是格，证明 a,b,cL 有a(b

10、c)(ab)(ac)证明由 aa，bcb 得a(bc)ab由 aa，bcc 得a(bc)ac从而得到 a(bc)(ab)(ac)说明在格中分配不等式成立。一般说来，格中的和运算并不是满足分配律的。,本节小结,偏序集构成格的条件：任意二元子集都有最大下界和最小上界。格的实例：正整数的因子格，幂集格，子群格。格的性质：对偶原理，格中算律（交换、结合、幂等、吸收），保序性，分配不等式。格作为代数系统的定义。格的证明方法,13.2 子格与格同态,定义13.4 设是格，S是L的非空子集，若S关于L中的运算和仍构成格，则称S是L的子格。,例13.5 设格L如右图所示。令,S1a,e,f,gS2a,b,e,

11、g,则S1不是L的子格，S2是L的子格。因为对于e和f,有efc，但cS1。,格同态,定义13.5 设L1和L2是格，:L1L2，若a,bL1 有(ab)(a)(b),(ab)(a)f(b)成立，则称为格L1到L2的同态映射，简称格同态。例13.6(1)设 L12n|nZ+，L22n+1|nN则L1和L2关于通常数的小于或等于关系构成格。令:L1L2，(x)x-1不难验证是L1到L2的同态映射，因为对任意的x,yL1有,(xy),(max(x,y),max(x,y)-1,(x)(y),(x-1)(y-1),max(x-1,y-1),max(x,y)-1,(xy),(min(x,y),min(x

12、,y)-1,(x)(y),(x-1)(y-1),min(x-1,y-1),min(x,y)-1,即(xy)(x)(y),(xy)(x)(y),例13.6,(2)如图中的格L1，L2和L3，若定义,1:L1L2 1(a)1(b)1(c)a1，1(d)d12:L1L3 2(a)a2，2(b)b2,2(c)c2，2(d)d2,则1和2都不是格同态，因为1(bc)1(d)d11(b)1(c)a1a1a12(bc)2(d)d22(b)2(c)b2c2c2从而1(bc)1(b)1(c)2(bc)2(b)2(c),格同态的性质,定理13.5 设是格L1到L2的映射，(1)若是格同态映射，则是保序映射，即x,

13、yL1，有xy(x)(y)(2)若是双射，则是格同构映射当且仅当x,yL1，有xy(x)(y)证明(1)任取x,yL1，xy，由格的性质知 xyy。又由于是格同态映射，必有(y)(xy)(x)(y)从而得到(x)(y)。,定理13.5(2)的证明,充分性。,(2)若是双射，则是格同构映射当且仅当x,yL1，有xy(x)(y),只须证明是L1到L2的同态映射即可。,任取x,yL1，,令xyz，由 xz和yz 知,(x)(z)，(y)(z),从而有(x)(y)(z)(xy),另一方面，由(x)(y)L2和的满射性可知，必存在uL1使得(u)(x)(y)因此有(x)(u)，(y)(u)。,由已知条件

14、可得 xu，yu。,从而推出 xyu。,再次使用已知条件得(xy)(u)(x)(y)。综合上述有(xy)(x)(y)。同理可证(xy)(x)(y)。,定理13.5(2)的证明,必要性。由(1)的结论必有xy(x)(y)反之，若(x)(y)，由于是同构映射，则(xy)(x)(y)(y)又由于是双射，必有xyy。从而证明了 xy。,(2)若是双射，则是格同构映射当且仅当x,yL1，有xy(x)(y),例13.7,例13.7 设L1,L2是格，其中S12是12的所有正因子构成的集合，D为整除关系，为通常数的小于或等于关系。令:S12S12，(x)x则是双射，但不是格L1到L2的同构映射。因为(2)(

15、3)，但2不整除3。根据定理13.5可知，不是同构映射。,格的直积,类似于半群,群和环,也可以定义格的直积。定义13.6 设L1和L2是格，定义L1L2上的运算,：即,L1L2 有称为格L1和L2的直积。可以证明仍是格。,格的直积,，L1L2，有,交换律,结合律(),同样()同理可证运算也满足交换律和结合律。,格的直积,吸收律()同理有()这就证明了和运算满足吸收律。从而证明 L1L2仍是格,格的直积举例,格L，为通常的小于或等于关系。则LL，其中是最小元，是最大元，且，而与是不可比的。易见LL与图13.4的L1同构。,本节小结,格L的非空子集S构成L的子格的条件：S对L的两个运算封闭。函数构

16、成格同态的条件：(ab)(a)(b)(ab)(a)(b)格同态的保序性。,13.3 分配格与有补格,一般说来，格中运算对满足分配不等式，即a,b,cL，有a(bc)(ab)(ac)但是不一定满足分配律。满足分配律的格称为分配格。定义13.7 设是格，若a,b,cL，有a(bc)(ab)(ac)a(bc)(ab)(ac)则称L为分配格。说明上面两个等式互为对偶式。在证明L为分配格时，只须证明其中的一个等式即可。,例13.8,L1和L2是分配格，L3和L4不是分配格。,在L3中，b(cd),beb,(bc)(bd),aaa,在L4中,c(bd),cac,(cb)(cd),edd,钻石格,五角格,分

17、配格的判别,定理13.6 设L是格，则L是分配格当且仅当L中不含有与钻石格或五角格同构的子格。证明略。推论(1)小于五元的格都是分配格。(2)任何一条链都是分配格。,例13.9,说明下图中的格是否为分配格，为什么？,L1,L2和L3都不是分配格。a,b,c,d,e是L1的子格，并且同构于钻石格。a,b,c,e,f是L2的子格，并且同构于五角格。a,c,b,e,f是L3的子格，也同构于钻石格。,定理13.7,定理13.7 格L是分配格 当且仅当 a,b,cL，abac且abac bc。证明 必要性。a,b,cL，有b b(ab)(吸收律,交换律)b(ac)(已知条件代入)(ba)(bc)(分配律

18、)(ac)(bc)(已知条件代入,交换律)(ab)c(分配律)(ac)c(已知条件代入)c(交换律,吸收律),定理13.7,充分性。假若a,b,cL，有abac且abac bc成立，而L不是分配格。根据定理13.6，L中必含有与钻石格或五角格同构的子格。假设L中含有与钻石格同构的子格，且该子格为u,v,x,y,z，其中u为它的最小元，v为它的最大元。,从而推出xyxzu，xyxzv但yz，与已知矛盾。对五角格的情况同理可证。,定理13.7的应用,使用定理13.7也可以判别一个格是否为分配格。例如下图中的三个格都不是分配格。,在L1中有 bcbd，bcbd，但cd。在L2中有 bcbe，bcbe

19、，但ce。在L3中有 cbcd，cbcd，但bd。,格的全下界和全上界,定义13.8 设L是格，若存在aL使得xL有ax，则称a为L的全下界；若存在bL使得xL有xb，则称b为L的全上界。命题格L若存在全下界或全上界，一定是唯一的。证明以全下界为例，假若a1和a2都是格L的全下界,则有a1a2和a2a1。根据偏序关系的反对称性必有a1a2。记法将格L的全下界记为0，全上界记为1。,有界格,定义13.9 设L是格，若L存在全下界和全上界，则称L为有界格，并将L记为。说明有限格L一定是有界格。举例设L是n元格，且La1,a2,an，那么a1a2an是L的全下界，而a1a2an是L的全上界。因此L是

20、有界格。对于无限格L来说，有的是有界格，有的不是有界格。如集合B的幂集格，不管B是有穷集还是无穷集，它都是有界格。它的全下界是空集，全上界是B。整数集Z关于通常数的小于或等于关系构成的格不是有界格，因为不存在最小和最大的整数。,有界格的性质,定理13.8 设是有界格，则aL有a00a0aa1aa11证明由 a00 和 0a0 可知 a00。说明 在有界格中，全下界0是关于运算的零元，运算的单位元。全上界1是关于运算的零元，运算的单位元。对偶原理 对于涉及到有界格的命题，如果其中含有全下界0或全上界1，在求该命题的对偶命题时，必须将0替换成1，而将1替换成0。例如a00 和 a11 互为对偶命题

21、，a0a 和 a1a 互为对偶命题。,有界格中的补元,定义13.10 设是有界格，aL，若存在bL 使得ab0 和 ab1成立，则称b是a的补元。说明若b是a的补元，那么a也是b的补元。换句话说，a和b互为补元。,例13.10,考虑下图中的四个格。,L1中的a与c互为补元，其中a为全下界，c为全上界，b没有补元。L2中的a与d互为补元，其中a为全下界，d为全上界，b与c也互为补元。L3中的a与e互为补元，其中a为全下界，e为全上界，b的补元是c和d，c的补元是b和d，d的补元是b和c。b,c,d每个元素都有两个补元。L4中的a与e互为补元。其中a为全下界。e为全上界。b的补元是c和d，c的补元

22、是b，d的补元是b。,有界格中补元的说明,在任何有界格中，全下界0与全上界1互补。对于其他元素，可能存在补元，也可能不存在补元。如果存在，可能是唯一的，也可能是多个补元。对于有界分配格，如果它的元素存在补元，一定是唯一的。,有界分配格中补元的唯一性,定理13.9 设是有界分配格。若aL，且对于a存在补元b，则b是a的唯一补元。证明假设cL也是a的补元，则有ac1，ac0又知b是a的补元，故ab1，ab0 从而得到acab，acab 由于L是分配格，根据定理13.7，bc。,有补格的定义,定义13.11 设是有界格，若L中所有元素都有补元存在，则称L为有补格。,L2,L3和L4是有补格，L1不是

23、有补格。,L2和L3是有补格，L1不是有补格。,本节小结,如果格中一个运算对另一个运算是可分配的，称这个格是分配格。分配格的两种判别法：不存在与钻石格或五角格同构的子格；对于任意元素a,b,c,有 abac且abacbc。有界格的定义及其实例。格中元素的补元及其性质（分配格中补元的唯一性）。有补格的定义。,13.4 布尔代数,定义13.12 如果一个格是有补分配格，则称它为布尔格或布尔代数。说明在布尔代数中，每个元素都存在着唯一的补元。可以把求补元的运算看作是布尔代数中的一元运算。可以把一个布尔代数标记为，为求补运算,aB，a是a的补元。,例13.11,例13.11 设S1101,2,5,10

24、,11,22,55,110是110的正因子集合。令gcd,lcm分别表示求最大公约数和最小公倍数的运算。问是否构成布尔代数？为什么？解答 证明构成格。,容易验证x,y,zS110，有gcd(x,y)S110lcm(x,y)S110gcd(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)xlcm(x,gcd(x,y)x,二元运算,交换律,结合律,吸收律,例13.11,证明 是分配格。易验证 x,y,zS110 有gcd(x,lcm(y,z)lcm

25、(gcd(x,y),gcd(x,z)证明 是有补格。1 为S110中的全下界110为S110中的全上界1和110互为补元，2和55互为补元，5和22互为补元，10和11互为补元。综上所述，为布尔代数。,例13.12,例13.12 设B为任意集合,证明B的幂集格构成布尔代数，称为集合代数。证明P(B)关于和构成格，因为和运算满足交换律、结合律和吸收律。由于和互相可分配，因此P(B)是分配格，且全下界是空集,全上界是B。根据绝对补的定义，取全集为B，xP(B)，x是x的补元。从而证明P(B)是有补分配格，即布尔代数。,布尔代数的性质,定理13.10 设是布尔代数，则(1)aB，(a)a(2)a,b

26、B，(ab)ab,(ab)ab说明(1)称为双重否定律。(2)称为德摩根律。命题代数与集合代数的双重否定律与德摩根律实际上是这个定理的特例。可以证明德摩根律对有限个元素也是正确的。证明(1)(a)是a的补元，a也是a的补元。由补元的唯一性得(a)a。,定理13.10(2)的证明,(2)a,bB，(ab)ab,(ab)ab(ab)(ab)(aab)(bab)(1b)(a1)11 1(ab)(ab)(aba)(abb)(0b)(a0)000所以ab是ab的补元，根据补元的唯一性有(ab)ab同理可证(ab)=ab。,布尔代数作为代数系统的定义,定义13.13 设是代数系统，*和是二元运算。若*和运

27、算满足：(1)交换律，即a,bB 有a*bb*a，abba(2)分配律，即a,b,cB有a*(bc)(a*b)(a*c)a(b*c)(ab)*(ac)(3)同一律，即存在0,1B，使得aB 有a*1a，a0a(4)补元律，即aB,存在aB，使得a*a0，aa1 则称是一个布尔代数。,关于布尔代数定义的说明,所谓同一律就是指运算含有单位元的性质，这里的1是*运算的单位元，0是运算的单位元。可以证明1和0分别也是和*运算的零元。aB有 a1(a1)*1（同一律）1*(a1)（交换律）(aa)*(a1)（补元律）a(a*1)（分配律）aa（同一律）1（补元律）同理可证 a*00。,关于布尔代数定义的

28、说明,为证明以上定义的是布尔代数，只需证明它是一个格，即证明*和运算满足结合律和吸收律。证明吸收律，a,bB有 a(a*b)(a*1)(a*b)（同一律）a*(1b)（分配律）a*1（1是运算的零元)a（同一律）同理有 a*(ab)a。,关于布尔代数定义的说明,为证结合律，先证以下命题：a,b,cB，abac 且 abac bc由 abac 且 abac 可得(ab)*(ab)(ac)*(ac)由分配律和交换律得(a*a)b(a*a)c由补元律得 0b0c由同一律和交换律得bc,关于布尔代数定义的说明,使用这个命题，为证明(a*b)*ca*(b*c)，只需证明以下两个等式：(1)a(a*b)*

29、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)*(ac)(分配律)a*(ac)(吸收律)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)*(ac)(分配律)(aa)*(ab)*(ac)(分配律)(1*(ab)*(ac)(交换律,补元律)(ab)*(ac)(交换律,同一律)a(b*c)(分配律)所

30、以（2）式成立。,布尔代数的子代数,定义13.14 设是布尔代数，S是B的非空子集，若0,1S，且S对,和运算都是封闭的，则称S是B的子布尔代数。,例13.13,例13.13 设是布尔代数，a,bB，且ab。令Sx|xB，且axb称S为B中的区间，可简记为a,b。可以证明a,b是一个布尔代数。显然S是B的非空子集，且a和b分别为S的全下界和全上界。对任意的x,yS都有 axb，ayb从而有 axyb,axybS关于和运算是封闭的。易见和运算在S上适合交换律和分配律。,例13.13,对任意的 xS，,令 y(ax)b(下面证明y为x得补元。),由于 aax，ab，,故 a(ax)b。,同时(ax

31、)bb，,因此 yS。,又,xy x(ax)b)x(ab)(xb)(分配律)xa(xb)(ab)x(xb)(ax)(xx)(xb)(分配律)1(xb)(补元律)xb(交换律，同一律)b(xb),例13.13,xy x(ax)b)x(ax)(xb,交换律)(xa)(xx)(分配律)(xa)0(补元律)xa(同一律)a(ax)根据定义13.13，构成布尔代数。其全上界是a，全下界是b。xa,b，x关于这个全上界和全下界的补元是(ax)b。当a0且b1时，a,b是B的子布尔代数。但当a0或b1时，a,b不是B的子布尔代数。,例13.14,考虑110的正因子集合S110关于gcd,lcm运算构成的布尔

32、代数。它有以下的子布尔代数：1,1101,2,55,1101,5,22,1101,10,11,1101,2,5,10,11,22,55,110,布尔代数的同态映射,定义13.15 设和是两个布尔代数。这里的,-泛指布尔代数B2中的求最大下界、最小上界和补元的运算。和E分别是B2的全下界和全上界。:B1B2。如果对于任意的a,bB1 有(ab)(a)(b)(ab)(a)(b)(a)-(a)则称是布尔代数B1到B2的同态映射，简称布尔代数的同态。说明类似于其它代数系统，也可以定义布尔代数的单同态、满同态和同构。,例13.15,例13.15 设和是布尔代数。:B1B2。若a,bB1有(ab)(a)(

33、b)(a)-(a)证明是B1到B2的同态。证明只须证明a,bB1 有(ab)(a)(b)成立即可。(ab)(ab)(双重否定律)-(ab)(已知)-(ab)(德摩根律)-(a)(b)(已知)-(-(a)-(b)(已知)-(-(a)-(-(b)(德摩根律)(a)(b)(双重否定律),有限布尔代数的结构,定义13.16 设L是格，0L，aL，若 bL 有0ba ba则称a是L中的原子。,考虑右图中的几个格。L1的原子是a。L2的原子是a,b,c。L3的原子是a和b。,若L是正整数n的全体正因子关于整除关系构成的格，则L的原子恰为n的全体质因子。若L是集合B的幂集合，则L的原子就是由B中元素构成的单

34、元集。,引理,引理1设是格，a,b是中的原子，若ab，则ab0。证明假设ab0，则有0aba 和 0abb由于a,b是原子，则有 aba 和 abb，从而有ab，与已知矛盾。,引理,引理设B是有限的布尔代数，xB，x0，令T(x)a1,a2,an是B中所有小于或等于x的原子构成的集合，则xa1a2an称这个表示式为x的原子表示，且是唯一的表示。这里的唯一性是指：若xa1a2an，xb1b2bn都是x的原子表示，则有a1,a2,anb1,b2,bn,引理2的证明,令ya1a2an。,由于aix，i1,2,n，,所以必有yx。,由此可知t1是原子，且t1x和t1y。,假如xy0，,则存在B中元素t

35、1,t2,ts，,现证明xy0。,使得t1覆盖0，t2覆盖t1，ts覆盖ts-1，且tsxy。,由t1x可知t1T(x)。,即存在aiT(x)，使得t1ai。,又由t1y可知t1yt1，从而有,t1t1y,aiy,ai(a1a2an),ai(a1a2aian),(aiai)(a1ai-1ai+1an),0a1ai-1ai+1an0,这与t1覆盖0矛盾。,从而证明了xy0。,引理,由 yy0,(yx)(yy),y(xy),(yx)1,yx,可知 xy。,综合上述得xy，,即xa1a2an。,设xb1b2bm是x的另一个原子表示，,任取aia1,a2,an，,假若aib1,b2,bm。,由引理1

36、必有aibj0，j1,2,m。,又由于aix，于是,aiaix,ai(b1b2bn),(aib1)(aib2)(aibm),0000,这与ai是原子矛盾。,从而证明了aib1,b2,bm。,同理可证，bjb1,b2,bm，必有bja1,a2,an，于是a1,a2,anb1,b2,bm。,有限布尔代数的表示定理,定理13.11(有限布尔代数的表示定理)设B是有限布尔代数，A是B的全体原子构成的集合，则B同构于A的幂集代数P(A)。证明任取xB，令T(x)a|aB,a是原子且ax则T(x)A，定义函数：BP(A)，(x)T(x)，xB下面证明是B到P(A)的同构映射。任取x,yB，b 有 bT(x

37、y)bA 且 bxy(bA且bx)且(bA且by)bT(x)且bT(y)bT(x)T(y)从而有 T(xy)T(x)T(y)，即x,yB 有(xy)(x)(y)。,定理13.11证明,任取x,yB，设xa1a2an，yb1b2bm是x,y的原子表示，则xya1a2anb1b2bm由引理2可知T(xy)a1,a2,an,b1,b2,bm又由于T(x)a1,a2,an，T(y)b1,b2,bm所以 T(xy)T(x)T(y)即(xy)(x)(y),定理13.11证明,任取xB，存在xB 使得xx1，xx0因此有(x)(x)(xx)(1)A(x)(x)(xx)(0)而和A分别为P(A)的全下界和全上

38、界，因此(x)是(x)在P(A)中的补元，即(x)(x)综上所述，是B到P(A)的同态映射。,定理13.11证明,下面证明为双射。假设(x)(y)，则有T(x)T(y)a1,a2,an由引理2可知 xa1a2any于是为单射。任取b1,b2,bmP(A)，令xb1b2bm，则(x)T(x)b1,b2,bm于是为满射。定理得证。,例子,考虑110的正因子的集合S110关于gcd,lcm运算构成的布尔代数。它的原子是2、5和11，因此原子的集合A2,5,11。幂集P(A),2,5,11,2,5,2,11,5,11,2,5,11。幂集代数是。只要令:S110P(A)，(1)，(2)2，(5)5，(1

39、1)11，(10)2,5，(22)2,11，(55)5,11,(110)A，那么f就是定理13.11中从S110到幂集P(A)的同构映射。,推论1,推论1任何有限布尔代数的基数为2n，nN。证明 设B是有限布尔代数，A是B的所有原子构成的集合，且|A|n，nN。由定理13.11 得BP(A)，而|P(A)|2n，所以|B|2n。,推论2,推论2 任何等势的有限布尔代数都是同构的。证明 设B1和B2是有限布尔代数，且|B1|=|B2|。则B1P(A1)，B2P(A2)，其中A1和A2分别为B1和B2的原子集合。易见|A1|A2|，存在双射f：A1A2。令：P(A1)P(A2)，(x)f(x)，x

40、A1下面证明是P(A1)到P(A2)的同构映射。任取x,yP(A1)，由定理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(xx)f()f(x)f(x)f(xx)f(A1)A2得 f(x)f(x)，这就证明了是P(A1)到P(A2)的同态映射。综上所述,有P(A1)P(A2),根据习题十三章第19题，B1B2得证。,有限布尔代数的说明,有限布尔代数的基数都是2的幂。在同构意义上，对于任何2n，n为自然数，仅存在一个2n元的布尔代数。下图给出了1元,2元,4元和8元的布尔代数。,主要内容,布尔代数的两个等价定义

41、：有补分配格；有两个二元运算并满足交换律、分配律、同一律和补元律的代数系统。布尔代数的特殊性质：双重否定律和德摩根律。子布尔代数的定义及其判别。布尔代数同态的判定：f(ab)f(a)f(b)(或f(ab)f(a)f(b),f(a)-f(a)对于任意自然数n，只有一个2n元的有限布尔代数，就是幂集代数。,学习要求,能够判断给定偏序集或者代数系统是否构成格。能够确定一个命题的对偶命题。能够证明格中的等式和不等式。能够判别格L的子集S是否构成格。了解格的同态及其性质。能够判别给定的格是否为分配格。能够判别布尔代数并证明布尔代数的等式。,作业,习题十三1，2，3，6，8，12，16，17，19,格的证明方法,格中等式的证明方法证明等式的左边“小于等于”右边，右边“小于等于”左边。根据偏序关系的反对称性，得到需要的等式。格中不等式的证明方法aa(偏序关系的自反性)ab且bc ac(偏序关系的传递性)aba，abb，aab，aab(下界定义与上界的定义)ab且ac abc，ba且ca bca(最大下界定义与最小上界的定义)ab且cd acbd，acbd(保序性),