离散数学格与布尔代数ppt课件

第11章 格与布尔代数离离 散散 数数 学学中国地质大学本科生课程中国地质大学本科生课程本章内容本章内容11.1 11.1 格的定义与性质格的定义与性质11.2 11.2 分配格、有补格与布尔代数分配格、有补格与布尔代数本章总结本章总结作业作业11.1 11.1 格的定义与性质格的定义与性质 定义定义11.111.1 设设是偏序集，是偏序集，如果如果 x,ySS，x,y 都有最小都有最小上界和最大下界上界和最大下界，则称，则称S S关于偏序关于偏序作成一个作成一个格格(lattice)。说明：说明：由于最小上界和最大下界的唯一性，可以把求由于最小上界和最大下界的唯一性，可以把求 x,y 的最的最小上界和最大下界看成小上界和最大下界看成x x与与y y的二元运算的二元运算和和。xy：表示：表示x x与与y y的最小上界的最小上界xy：表示：表示x x和和y y的最大下界。的最大下界。本章出现的本章出现的和和符号只代表格中的运算，而不再有其它的符号只代表格中的运算，而不再有其它的含义。含义。格的实例格的实例例例11.111.1 设设n n是正整数，是正整数，S Sn n是是n n的正因子的集合。的正因子的集合。D D为整除关系，为整除关系，则偏序集则偏序集S,D构成格。构成格。x,ySx,ySn n，xyxy是是lcm(x,y)lcm(x,y)，即，即x x与与y y的最小公倍数。的最小公倍数。xyxy是是gcd(x,y)gcd(x,y)，即，即x x与与y y的最大公约数。的最大公约数。下图给出了格下图给出了格S,D，S,D和和S,D。例例11.211.2例例11.211.2 判断下列偏序集是否构成格判断下列偏序集是否构成格,并说明理由。并说明理由。(1)P(B),(1)，其中，其中P(B)P(B)是集合是集合B B的幂集。的幂集。(2)(2)，其中，其中Z Z是整数集是整数集,为小于或等于关系。为小于或等于关系。(3)(3)偏序集的哈斯图分别在下图给出。偏序集的哈斯图分别在下图给出。例例11.211.2解答解答 (1)(1)是格。是格。x,yP(B)x,yP(B)，xyxy就是就是xyxy，xyxy就是就是xyxy。由于由于和和运算在运算在P(B)P(B)上是封闭的，所以上是封闭的，所以xyxy，xyP(B)xyP(B)。称称P(B),为为B B的的幂集格幂集格。(2)(2)是格。是格。x,yZ,xyx,yZ,xymax(x,y)max(x,y)，xyxymin(x,y)min(x,y)，它们都是整数。，它们都是整数。(3)(3)都不是格。都不是格。(a)(a)中的中的a,ba,b没有最大下界。没有最大下界。(b)(b)中的中的b,db,d有两个上界有两个上界c c和和e,e,但没有最小上界。但没有最小上界。(c)(c)中的中的b,cb,c有三个上界有三个上界d,e,f,d,e,f,但没有最小上界。但没有最小上界。(d)(d)中的中的a,ga,g没有最大下界。没有最大下界。例例11.311.3例例11.3 11.3 设设G G是群，是群，L(G)L(G)是是G G的所有子群的集合。即的所有子群的集合。即L(G)L(G)H|HG H|HG 对任意的对任意的H H1 1,H,H2 2L(G)L(G)，H H1 1HH2 2也是也是G G的子群，而的子群，而H 是由是由H H1 1HH2 2生成的子群（即包含着生成的子群（即包含着H H1 1HH2 2的最小的子群）。的最小的子群）。在在L(G)L(G)上定义包含关系上定义包含关系，则，则L(G)L(G)关于包含关系构成一个格，关于包含关系构成一个格，称为称为G G的的子群格子群格。易见在易见在L(G)L(G)中，中，H H1 1HH2 2就是就是H H1 1HH2 2，H H1 1HH2 2就是就是H。对偶原理对偶原理定义定义11.211.2 设设f f是含有格中元素以及符号、是含有格中元素以及符号、和和的的命题。令命题。令f f*是将是将f f中的中的替换成替换成，替换成替换成，替换成替换成，替换成替换成所得到的命题。称所得到的命题。称f f*为为f f的的对偶命题对偶命题。例如例如 在格中令在格中令f f是是(ab)cc(ab)cc，则，则f f*是是(ab)cc(ab)cc。格的对偶原理格的对偶原理 设设f f是含有格中元素以及符号、是含有格中元素以及符号、和和的命题。若的命题。若f f对一切格为真，则对一切格为真，则f f的对偶命题的对偶命题f f*也对一切格也对一切格为真。为真。例如例如 对一切格对一切格L L都有都有 a,bLa,bL，abaaba(因为因为a a和和b b的交是的交是a a的一个下界的一个下界)那么那么对一切格对一切格L L都有都有 a,bLa,bL，abaaba说明说明许多格的性质都是互为对偶命题的。许多格的性质都是互为对偶命题的。有了格的对偶原理，在证明格的性质时，有了格的对偶原理，在证明格的性质时，只须证明其中的一个命题即可。只须证明其中的一个命题即可。格的运算性质格的运算性质定理定理11.111.1 设设是格，则运算是格，则运算和和适合适合交换律交换律、结合结合律律、幂等律幂等律和和吸收律吸收律，即，即(1)(1)交换律交换律 a,bL a,bL 有有ababbabaababbaba(2)(2)结合律结合律 a,b,cL a,b,cL 有有(ab)c(ab)ca(bc)a(bc)(ab)c(ab)ca(bc)a(bc)(3)(3)幂等律幂等律 aL aL 有有aaaaa aaaaaa a(4)(4)吸收律吸收律 a,bL a,bL 有有a(ab)a(ab)a aa(ab)a(ab)a a定理定理11.111.1(1)ab(1)ab和和baba分别是分别是a,ba,b和和b,ab,a的最小上界。的最小上界。由于由于a,ba,bb,ab,a，所以，所以ababbaba。由对偶原理，由对偶原理，ababbaba得证。得证。(2)(2)由最小上界的定义有由最小上界的定义有(ab)caba(ab)caba(13.1)(13.1)(ab)cabb(ab)cabb(13.2)(13.2)(ab)cc(ab)cc(13.3)(13.3)由式由式13.213.2和和13.313.3有有(ab)cbc(ab)cbc(13.4)(13.4)再由式再由式13.113.1和和13.413.4有有(ab)ca(bc)(ab)ca(bc)同理可证同理可证(ab)ca(bc)(ab)ca(bc)根据偏序关系的反对称性有根据偏序关系的反对称性有(ab)c(ab)ca(bc)a(bc)由对偶原理，由对偶原理，(ab)c(ab)ca(bc)a(bc)得证。得证。定理定理11.111.1(3)(3)显然显然aaa,aaa,又由又由aaaa可得可得 aaaaaa。根据反对称性有根据反对称性有 aaaaa a，由对偶原理，由对偶原理，aaaaa a 得证。得证。(4)(4)显然显然a(ab)aa(ab)a(13.5)(13.5)又由又由 aaaa，aba aba 可得可得a(ab)a a(ab)a(13.6)(13.6)由式由式13.513.5和和13.613.6可得可得 a(ab)a(ab)a a，根据对偶原理，根据对偶原理，a(ab)a(ab)a a 得证。得证。定理定理11.211.2定理定理11.211.2 设设S,是具有两个二元运算的代数系统，若对是具有两个二元运算的代数系统，若对于于*和和 运算适合运算适合交换律交换律、结合律结合律、吸收律吸收律，则可以适当定，则可以适当定义义S S中的偏序中的偏序，使得，使得构成一个格，且构成一个格，且a,bSa,bS有有ababa a*b b，ababa a b b。思路思路 (1)(1)证明证明在在S S中中*和和 运算都适合幂等律运算都适合幂等律。(2)(2)在在S S上定义二元关系上定义二元关系R R，并证明，并证明R R为偏序关系。为偏序关系。(3)(3)证明证明构成格。构成格。说明说明通过规定运算及其基本性质可以给出格的定义。通过规定运算及其基本性质可以给出格的定义。定理定理11.211.2 a aSS，由吸收律得，由吸收律得(1)(1)证明在证明在S S中中*和和 运算都适合幂等律运算都适合幂等律。a a*a a a a*(a a(a(a*a)a)a a同理有同理有 a a a aa a。(2)(2)在在S S上定义二元关系上定义二元关系R R，a,ba,bS S 有有 R R a a b bb b下面证明下面证明R R在在S S上的偏序。上的偏序。根据幂等律，根据幂等律，a aSS都有都有a a a aa a，即即RR，所以所以R R在在S S上是自反的。上是自反的。a,bS a,bS 有有aRbaRb且且bRabRa a a b bb b且且b b a aa a a ab b a aa a b bb (b (由于由于a a b=b b=b a)a)所以所以R R在在S S上是反对称的。上是反对称的。定理定理11.211.2 a,b,ca,b,cSS 有有aRbaRb且且bRc bRc a a b bb b 且且 b b c cc c a a c ca a(b(b c)c)a a c c(a(a b)b)c c a a c cb b c cc c aRc aRc这就证明了这就证明了R R在在S S上是传递的。上是传递的。综上所述，综上所述，R R为为S S上的偏序。上的偏序。以下把以下把R R记作记作。定理定理11.211.2(3)(3)证明证明S构成格。构成格。即证明即证明ababa a b b，ababa a*b b。a,ba,bSS 有有a a(a(a b)b)(a(a a)a)b ba a b bb b(a(a b)b)a a(b(b b)b)a a b b根据根据的定义有的定义有 aaaa b b和和baba b b，所以所以a a b b是是a,ba,b的上界。的上界。假设假设 c c为为a,ba,b的上界，的上界，则有则有a a c cc c和和b b c cc c，从而有从而有(a(a b)b)c c a a(b(b c)c)a a c c c c这就证明了这就证明了a a bcbc，所以所以a a b b是是a,ba,b的最小上界，即的最小上界，即 ababa a b b为证为证a a*b b是是a,ba,b的最大下界，的最大下界，先证先证首先由首先由a a b bb b 可知可知 a a*b b a a*(a(a b)b)a a反之由反之由a a*b ba a 可知可知a a b b(a(a*b)b)b b b b(b(b*a)a)b b再由式再由式(13.7)(13.7)和和的定义有的定义有 ab ab a a*b ba a，依照前边的证明依照前边的证明,类似地可证类似地可证 a a*b b是是a,ba,b的最大下界，的最大下界，即即 ababa a*b b。a a b bb b a a*b ba a(13.7)(13.7)格的等价定义格的等价定义根据定理根据定理11.211.2，可以给出格的另一个等价定义。，可以给出格的另一个等价定义。定义定义11.311.3 设设S,是代数系统，是代数系统，*和和 是二元运算，如果是二元运算，如果*和和 满满足交换律，结合律和吸收律，则足交换律，结合律和吸收律，则S,构成一个构成一个格格(lattice)。说明说明格中的幂等律可以由吸收律推出。格中的幂等律可以由吸收律推出。以后我们不再区别是偏序集定义的格，以后我们不再区别是偏序集定义的格，还是代数系统定义的格，而统称为格还是代数系统定义的格，而统称为格L L。格的性质格的性质定理定理11.311.3 设设L L是格，则是格，则 a,bL a,bL 有有ab ab ababa a ab abb b证明证明 先证先证 ab ab ab aba a由由aaaa和和abab可知，可知，a a是是a,ba,b的下界，的下界，故故aabaab。显然又有。显然又有abaaba。由反对称性得由反对称性得ababa a。再证再证 ababa a ab abb b。根据吸收律有根据吸收律有 b bb(ba)b(ba)由由ababa a得得 b bba,ba,即即ababb b。最后证最后证ababb b ab ab。由由aabaab得得 aabaabb b。格的性质格的性质定理定理11.411.4 设设L L是格，是格，a,b,c,dLa,b,c,dL，若，若abab且且cdcd，则，则acbdacbd，acbdacbd证明证明 acabacabaccdaccd因此，因此，acbdacbd。同理可证同理可证 acbdacbd。例例11.511.5 例例11.511.5 设设L L是格，证明是格，证明 a,b,cL a,b,cL 有有a(bc)(ab)(ac)a(bc)(ab)(ac)证明证明由由 aaaa，bcb bcb 得得a(bc)aba(bc)ab由由 aaaa，bcc bcc 得得a(bc)aca(bc)ac从而得到从而得到 a(bc)(ab)(ac)a(bc)(ab)(ac)说明说明在格中分配不等式成立。在格中分配不等式成立。一般说来，格中的一般说来，格中的和和运算并不是满足分配律的。运算并不是满足分配律的。本节小结本节小结q 偏序集构成格的条件：任意二元子集都有最大下界和最偏序集构成格的条件：任意二元子集都有最大下界和最小上界。小上界。q 格的实例：正整数的因子格，幂集格，子群格。格的实例：正整数的因子格，幂集格，子群格。q 格的性质：对偶原理，格中算律（交换、结合、幂等、格的性质：对偶原理，格中算律（交换、结合、幂等、吸收），保序性，分配不等式。吸收），保序性，分配不等式。q 格作为代数系统的定义。格作为代数系统的定义。q 格的证明方法格的证明方法子格子格定义定义11.411.4 设设是格，是格，S S是是L L的非空子集，若的非空子集，若S S关于关于L L中中的运算的运算和和仍构成格，则称仍构成格，则称S S是是L L的的子格子格。例例11.611.6 设格设格L L如右图所示。令如右图所示。令S S1 1a,e,f,ga,e,f,gS S2 2a,b,e,ga,b,e,g则则S S1 1不是不是L L的子格，的子格，S S2 2是是L L的子格。的子格。因为对于因为对于e e和和f,f,有有efefc c，但但c c S S1 1。11.2 11.2 分配格、有补格与布尔代数分配格、有补格与布尔代数q 一般说来，格中运算一般说来，格中运算对对满足分配不等式，满足分配不等式，即即 a,b,cLa,b,cL，有，有a(bc)(ab)(ac)a(bc)(ab)(ac)但是不一定满足分配律。满足分配律的格称为但是不一定满足分配律。满足分配律的格称为分配格分配格。定义定义11.511.5 设设是格，若是格，若 a,b,cLa,b,cL，有，有a(bc)a(bc)(ab)(ac)(ab)(ac)a(bc)a(bc)(ab)(ac)(ab)(ac)则称则称L L为为分配格分配格。说明说明上面两个等式互为对偶式。上面两个等式互为对偶式。在证明在证明L L为分配格时，只须证明其中的一个等式即可。为分配格时，只须证明其中的一个等式即可。例例11.711.7L L1 1和和L L2 2是分配格，是分配格，L L3 3和和L L4 4不是分配格。不是分配格。在在L L3 3中，中，b(cd)b(cd)bebeb b(bc)(bd)(bc)(bd)aaaaa a在在L L4 4中中,c(bd)c(bd)cacac c(cb)(cd)(cb)(cd)ededd d钻石格钻石格五角格五角格分配格的判别分配格的判别定理定理11.511.5 设设L L是格，则是格，则L L是分配格当且仅当是分配格当且仅当L L中不含有与钻石中不含有与钻石格或五角格同构的子格。格或五角格同构的子格。证明证明略。略。推论推论(1)(1)小于五元的格都是分配格。小于五元的格都是分配格。(2)(2)任何一条链都是分配格。任何一条链都是分配格。例例11.811.8说明下图中的格是否为分配格，为什么？说明下图中的格是否为分配格，为什么？L L1 1,L,L2 2和和L L3 3都不是分配格。都不是分配格。a,b,c,d,ea,b,c,d,e是是L L1 1的子格，并且同构于钻石格。的子格，并且同构于钻石格。a,b,c,e,fa,b,c,e,f是是L L2 2的子格，并且同构于五角格。的子格，并且同构于五角格。a,c,b,e,fa,c,b,e,f是是L L3 3的子格，也同构于钻石格。的子格，也同构于钻石格。格的全下界和全上界格的全下界和全上界定义定义11.611.6 设设L L是格，是格，若存在若存在aLaL使得使得 xLxL有有axax，则称，则称a a为为L L的的全下界全下界；若存在若存在bLbL使得使得 xLxL有有xbxb，则称，则称b b为为L L的的全上界全上界。命题命题格格L L若存在全下界或全上界，一定是唯一的。若存在全下界或全上界，一定是唯一的。证明证明以全下界为例，假若以全下界为例，假若a a1 1和和a a2 2都是格都是格L L的全下界的全下界,则有则有a a1 1aa2 2和和a a2 2aa1 1。根据偏序关系的反对称性必有根据偏序关系的反对称性必有a a1 1a a2 2。记法记法将格将格L L的的全下界记为全下界记为0 0，全上界记为全上界记为1 1。有界格有界格定义定义11.711.7 设设L L是格，若是格，若L L存在全下界和全上界，则称存在全下界和全上界，则称L L为为有界格有界格，并将并将L L记为记为。说明说明有限格有限格L L一定是有界格。一定是有界格。举例举例q 设设L L是是n n元格元格，且，且L Laa1 1,a,a2 2,a,an n，那么，那么a a1 1aa2 2aan n是是L L的的全下界，而全下界，而a a1 1aa2 2aan n是是L L的全上界。因此的全上界。因此L L是有界格。是有界格。q 对于对于无限格无限格L L来说，有的是有界格，有的不是有界格。来说，有的是有界格，有的不是有界格。q 如集合如集合B B的的幂集格幂集格，不管，不管B B是有穷集还是无穷集，是有穷集还是无穷集，它都是有界格。它的全下界是空集它都是有界格。它的全下界是空集，全上界是全上界是B B。q 整数集整数集Z Z关于通常数的小于或等于关系构成的格不是有界格，关于通常数的小于或等于关系构成的格不是有界格，因为不存在最小和最大的整数。因为不存在最小和最大的整数。有界格的性质有界格的性质定理（补充）定理（补充）设设是有界格，则是有界格，则 aLaL有有a0a00 0a0a0a aa1a1a aa1a11 1证明证明由由 a00 a00 和和 0a0 0a0 可知可知 a0a00 0。说明说明 在有界格中，在有界格中，全下界全下界0 0是关于是关于运算的零元，运算的零元，运算的单位元。运算的单位元。全上界全上界1 1是关于是关于运算的零元，运算的零元，运算的单位元。运算的单位元。对偶原理对偶原理 对于涉及到有界格的命题，如果其中含有全下界对于涉及到有界格的命题，如果其中含有全下界0 0或或全上界全上界1 1，在求该命题的对偶命题时，必须将，在求该命题的对偶命题时，必须将0 0替换成替换成1 1，而，而将将1 1替换成替换成0 0。例如例如a0a00 0 和和 a1a11 1 互为对偶命题，互为对偶命题，a0a0a a 和和 a1a1a a 互为对偶命题。互为对偶命题。有界格中的补元有界格中的补元定义定义11.811.8 设设是有界格，是有界格，aLaL，若存在若存在bL bL 使得使得abab0 0 和和 abab1 1成立，则称成立，则称b b是是a a的的补元补元。说明说明若若b b是是a a的补元，那么的补元，那么a a也是也是b b的补元。的补元。换句话说，换句话说，a a和和b b互为补元。互为补元。例例11.911.9考虑下图中的四个格。考虑下图中的四个格。L L1 1中的中的a a与与c c互为补元，其中互为补元，其中a a为全下界，为全下界，c c为全上界，为全上界，b b没有补元。没有补元。L L2 2中的中的a a与与d d互为补元，其中互为补元，其中a a为全下界，为全下界，d d为全上界，为全上界，b b与与c c也互为也互为补元。补元。L L3 3中的中的a a与与e e互为补元，其中互为补元，其中a a为全下界，为全下界，e e为全上界，为全上界，b b的补元是的补元是c c和和d d，c c的补元是的补元是b b和和d d，d d的补元是的补元是b b和和c c。b,c,db,c,d每个元素都有两每个元素都有两个补元。个补元。L L4 4中的中的a a与与e e互为补元。其中互为补元。其中a a为全下界。为全下界。e e为全上界。为全上界。b b的补元是的补元是c c和和d d，c c的补元是的补元是b b，d d的补元是的补元是b b。有界格中补元的说明有界格中补元的说明在任何有界格中，在任何有界格中，q 全下界全下界0 0与全上界与全上界1 1互补。互补。q 对于其他元素，可能存在补元，也可能不存在补元。对于其他元素，可能存在补元，也可能不存在补元。q 如果存在，可能是唯一的，也可能是多个补元。如果存在，可能是唯一的，也可能是多个补元。q 对于有界分配格，如果它的元素存在补元，一定是唯一的。对于有界分配格，如果它的元素存在补元，一定是唯一的。有界分配格中补元的唯一性有界分配格中补元的唯一性定理定理11.611.6 设设是有界分配格。是有界分配格。若若aLaL，且对于，且对于a a存在补元存在补元b b，则，则b b是是a a的唯一补元。的唯一补元。证明证明假设假设cLcL也是也是a a的补元，则有的补元，则有acac1 1，acac0 0又知又知b b是是a a的补元，故的补元，故abab1 1，abab0 0 从而得到从而得到acacabab，acacab ab 由于由于L L是分配格，根据定理是分配格，根据定理13.713.7，b bc c。有补格的定义有补格的定义定义定义11.911.9 设设是有界格，若是有界格，若L L中所有元素都有补中所有元素都有补元存在，则称元存在，则称L L为为有补格有补格。L L2 2,L,L3 3和和L L4 4是有补是有补格，格，L L1 1不是有补格。不是有补格。L L2 2和和L L3 3是有补格，是有补格，L L1 1不是有补格。不是有补格。本节小结本节小结q 如果格中一个运算对另一个运算是可分配的，称这个格是分如果格中一个运算对另一个运算是可分配的，称这个格是分配格。配格。q 分配格的两种判别法：分配格的两种判别法：不存在与钻石格或五角格同构的子格；不存在与钻石格或五角格同构的子格；对于任意元素对于任意元素a,b,c,a,b,c,有有 ababacac且且ababacacb bc c。q 有界格的定义及其实例。有界格的定义及其实例。q 格中元素的补元及其性质（分配格中补元的唯一性）。格中元素的补元及其性质（分配格中补元的唯一性）。q 有补格的定义。有补格的定义。布尔代数布尔代数定义定义11.1011.10 如果一个格是如果一个格是有补分配格有补分配格，则称它为，则称它为布尔格布尔格或或布尔布尔代数代数。说明说明在布尔代数中，每个元素都存在着唯一的补元。在布尔代数中，每个元素都存在着唯一的补元。可以把求补元的运算看作是布尔代数中的一元运算。可以把求补元的运算看作是布尔代数中的一元运算。可以把一个布尔代数标记为可以把一个布尔代数标记为B,0,1，为求补运算为求补运算,aBaB，a a是是a a的补元。的补元。例例11.1011.10例例11.1011.10 设设S S1101101,2,5,10,11,22,55,1101,2,5,10,11,22,55,110是是110110的正因子集合。的正因子集合。令令gcd,lcmgcd,lcm分别表示求最大公约数和最小公倍数的运算。问分别表示求最大公约数和最小公倍数的运算。问S,gcd,lcm是否构成布尔代数？为什么？是否构成布尔代数？为什么？解答解答 证明证明S,gcd,lcm构成格。构成格。容易验证容易验证 x,y,zSx,y,zS110110，有，有gcd(x,y)Sgcd(x,y)S110110lcm(x,y)Slcm(x,y)S110110gcd(x,y)gcd(x,y)gcd(y,x)gcd(y,x)lcm(x,y)lcm(x,y)lcm(y,x)lcm(y,x)gcd(gcd(x,y),z)gcd(gcd(x,y),z)gcd(x,gcd(y,z)gcd(x,gcd(y,z)lcm(lcm(x,y),z)lcm(lcm(x,y),z)lcm(x,lcm(y,z)lcm(x,lcm(y,z)gcd(x,lcm(x,y)gcd(x,lcm(x,y)x xlcm(x,gcd(x,y)lcm(x,gcd(x,y)x x二元运算二元运算交换律交换律结合律结合律吸收律吸收律例例11.1011.10证明证明 S,gcd,lcm是分配格。是分配格。易验证易验证 x,y,zS x,y,zS110110 有有gcd(x,lcm(y,z)gcd(x,lcm(y,z)lcm(gcd(x,y),gcd(x,z)lcm(gcd(x,y),gcd(x,z)证明证明 S,gcd,lcm是有补格。是有补格。1 1 为为S S110110中的全下界中的全下界110110为为S S110110中的全上界中的全上界1 1和和110110互为补元，互为补元，2 2和和5555互为补元，互为补元，5 5和和2222互为补元，互为补元，1010和和1111互为补元。互为补元。综上所述，综上所述，S,gcd,lcm为布尔代数。为布尔代数。例例11.1011.10（2 2）例例11.1011.10（2 2）设设B B为任意集合为任意集合,证明证明B B的的幂集格幂集格P(B),B构成布尔代数，称为构成布尔代数，称为集合代数集合代数。证明证明P(B)P(B)关于关于和和构成格，因为构成格，因为和和运算满足交换律、结合律和吸收律。运算满足交换律、结合律和吸收律。由于由于和和互相可分配，因此互相可分配，因此P(B)P(B)是分配格，是分配格，且全下界是空集且全下界是空集,全上界是全上界是B B。根据绝对补的定义，取全集为根据绝对补的定义，取全集为B B，xP(B)xP(B)，x x是是x x的补元。的补元。从而证明从而证明P(B)P(B)是有补分配格，即布尔代数。是有补分配格，即布尔代数。布尔代数的性质布尔代数的性质定理定理11.711.7 设设B,0,1是布尔代数，则是布尔代数，则 (1)(1)aBaB，(a(a)a a(2)(2)a,bBa,bB，(ab)(ab)a abb,(ab),(ab)a abb说明说明(1)(1)称为称为双重否定律双重否定律。(2)(2)称为称为德摩根律德摩根律。命题代数与集合代数的双重否定律与德摩根律实际上命题代数与集合代数的双重否定律与德摩根律实际上是这个定理的特例。是这个定理的特例。可以证明德摩根律对有限个元素也是正确的。可以证明德摩根律对有限个元素也是正确的。证明证明(1)(a(1)(a)是是a a的补元，的补元，a a也是也是a a的补元。的补元。由补元的唯一性得由补元的唯一性得(a(a)a a。定理定理11.7(2)11.7(2)的证明的证明(2)(2)a,bBa,bB，(ab)(ab)a abb,(ab),(ab)a abb(ab)(ab)(a(abb)(aaaabb)()(b baabb)(1b(1b)(a)(a1)1)1111 1 1(ab)(ab)(a(abb)(a abbaa)(a)(abbbb)(0b)(a0)(0b)(a0)00000 0所以所以a abb是是abab的补元，根据补元的唯一性有的补元，根据补元的唯一性有(ab)(ab)a abb同理可证同理可证(ab)(ab)=a=abb。布尔代数作为代数系统的定义布尔代数作为代数系统的定义定义定义11.1111.11 设设B,是代数系统，是代数系统，*和和 是二元运算。是二元运算。若若*和和运算满足：运算满足：(1)(1)交换律交换律，即，即 a,bB a,bB 有有a a*b bb b*a a，a a b bb b a a(2)(2)分配律分配律，即，即 a,b,cBa,b,cB有有a a*(b(b c)c)(a(a*b)b)(a(a*c)c)a a(b(b*c)c)(a(a b)b)*(a(a c)c)(3)(3)同一律同一律，即存在，即存在0,1B0,1B，使得，使得 aB aB 有有a a*1 1a a，a a 0 0a a (4)(4)补元律补元律，即，即 aB,aB,存在存在a aBB，使得，使得a a*a a0 0，a a a a1 1 则称则称B,是一个是一个布尔代数布尔代数。关于布尔代数定义的说明关于布尔代数定义的说明所谓所谓同一律就是指运算含有单位元的性质同一律就是指运算含有单位元的性质，这里的，这里的1 1是是*运算的运算的单位元，单位元，0 0是运算是运算 的单位元。的单位元。可以证明可以证明1 1和和0 0分别也是分别也是 和和*运算的零元。运算的零元。aBaB有有 a a 1 1 (a a 1)1)*1 1 （同一律）（同一律）1 1*(a a 1)1)（交换律）（交换律）(a a a a)*(a a 1)1)（补元律）（补元律）a a(aa*1 1)（分配律）（分配律）a a aa （同一律）（同一律）1 1 （补元律）（补元律）同理可证同理可证 a a*0 00 0。关于布尔代数定义的说明关于布尔代数定义的说明为证明以上定义的为证明以上定义的B,是布尔代数，只需证明它是一是布尔代数，只需证明它是一个格，即个格，即证明证明*和和运算满足结合律和吸收律。运算满足结合律和吸收律。证明吸收律证明吸收律，a,bBa,bB有有 a a(a(a*b)b)(a a*1)1)(a a*b)b)（同一律）（同一律）a a*(1 1 b b)（分配律）（分配律）a a*1 1 （1 1是是 运算的零元运算的零元)a a （同一律）（同一律）同理有同理有 a a*(a(a b)b)a a。关于布尔代数定义的说明关于布尔代数定义的说明为证结合律，先证以下命题：为证结合律，先证以下命题：a,b,cBa,b,cB，a a b ba a c c 且且 a a b ba a c c b bc c由由 a a b ba a c c 且且 a a b ba a c c 可得可得(a(a b)b)*(a(a b)b)(a(a c)c)*(a(a c)c)由分配律和交换律得由分配律和交换律得(a(a*a a)b b(a(a*a a)c c由补元律得由补元律得 0 0 b b0 0 c c由同一律和交换律得由同一律和交换律得b bc c关于布尔代数定义的说明关于布尔代数定义的说明使用这个命题，为证明使用这个命题，为证明 (a(a*b)b)*c ca a*(b b*c c)，只需证明以下，只需证明以下两个等式：两个等式：(1)a(1)a(a(a*b)b)*c)c)a a(a(a*(b b*c c)(2)a(2)a(a(a*b)b)*c)c)a a(a(a*(b b*c c)先证明第一个等式，由吸收律有先证明第一个等式，由吸收律有 a a(a(a*(b b*c)c)a a a a(a(a*b)b)*c)c)(a a(a(a*b)b)*(a(a c)c)(分配律分配律)a a*(a(a c)c)(吸收律吸收律)a a所以所以(1)(1)式成立。式成立。关于布尔代数定义的说明关于布尔代数定义的说明下面证明下面证明(2)(2)式：式：a a(a(a*b)b)*c)c)a a(a(a*(b b*c c)a a(a(a*(b b*c c)(a a a a)*(a a(b b*c c)(分配律分配律)1 1*(a a(b b*c c)(交换律交换律,补元律补元律)a a(b b*c c)(交换律交换律,同一律同一律)a a(a(a*b)b)*c)c)(a a(a(a*b)b)*(a(a c)(c)(分配律分配律)(a a a a)*(a(a b)b)*(a(a c)c)(分配律分配律)(1 1*(a(a b)b)*(a(a c)c)(交换律交换律,补元律补元律)(a a b)b)*(a a c)(c)(交换律交换律,同一律同一律)a a(b b*c c)(分配律分配律)所以（所以（2 2）式成立。）式成立。有限布尔代数的结构有限布尔代数的结构定义定义11.1211.12 设设L L是格，是格，0L0L，aLaL，若，若 bL bL 有有0 0ba ba b ba a则称则称a a是是L L中的中的原子原子。考虑右图中的几个格。考虑右图中的几个格。L L1 1的原子是的原子是a a。L L2 2的原子是的原子是a,b,ca,b,c。L L3 3的原子是的原子是a a和和b b。若若L L是正整数是正整数n n的全体正因子关于整除关系构成的格，则的全体正因子关于整除关系构成的格，则L L的原子恰的原子恰为为n n的全体质因子。的全体质因子。若若L L是集合是集合B B的幂集合，则的幂集合，则L L的原子就是由的原子就是由B B中元素构成的单元集。中元素构成的单元集。有限布尔代数的表示定理有限布尔代数的表示定理定理定理11.8(11.8(有限布尔代数的表示定理有限布尔代数的表示定理)设设B B是有限布尔代数，是有限布尔代数，A A是是B B的全体原子构成的集合的全体原子构成的集合，则，则B B同构于同构于A A的幂集代数的幂集代数P(A)P(A)。证明证明任取任取xBxB，令，令T(x)T(x)a|aB,aa|aB,a是原子且是原子且aax x 则则T(x)T(x)A A，定义函数，定义函数：BBP(A)P(A)，(x)(x)T(x)T(x)，xBxB下面证明下面证明 是是B B到到P(A)P(A)的同构映射。的同构映射。任取任取x,yBx,yB，b b 有有 bbT(xT(xy y)bA bA 且且 bbxxy y (bA(bA且且bbx)x)且且 (bA(bA且且by)by)b bT(x)T(x)且且bbT(T(y y)b bT(x)T(y)T(x)T(y)从而有从而有 T(xT(xy y)T(x)T(y)T(x)T(y)，即即 x,yx,y B B 有有 (x(xy y)(x)(x)(y)(y)。定理定理11.811.8证明证明任取任取x,yx,yB B，设，设x xa a1 1a a2 2a an n，y yb b1 1b b2 2b bm m是是x,yx,y的原子表示，则的原子表示，则x xy ya a1 1a a2 2a an nb b1 1b b2 2b bm m由引理由引理2 2可知可知T(xT(xy)y)aa1 1,a,a2 2,a,an n,b,b1 1,b,b2 2,b bm m 又由于又由于T(x)T(x)aa1 1,a,a2 2,a,an n，T(y)T(y)bb1 1,b,b2 2,b bm m 所以所以 T(xT(xy)y)T(x)T(y)T(x)T(y)即即(x(xy)y)(x)(x)(y)(y)定理定理11.811.8证明证明任取任取xxB B，存在，存在x x B B 使得使得xxxx 1 1，xxxx 0 0因此有因此有(x)(x)(x(x)(xx(xx)(1)(1)A A(x)(x)(x(x)(xx(xx)(0)(0)而而和和A A分别为分别为P(P(A A)的全下界和全上界，的全下界和全上界，因此因此(x(x)是是(x)(x)在在P(P(A A)中的补元，即中的补元，即(x(x)(x)(x)综上所述，综上所述，是是B B到到P(A)P(A)的同态映射。的同态映射。定理定理11.811.8证明证明下面证明下面证明 为双射。为双射。假设假设(x)(x)(y)(y)，则有，则有T(x)T(x)T(y)T(y)aa1 1,a,a2 2,a,an n 由引理由引理2 2可知可知 x xa a1 1a a2 2a an ny y于是于是 为单射。为单射。任取任取bb1 1,b,b2 2,b bm mP(A)P(A)，令令x xb b1 1b b2 2b bm m，则，则(x)(x)T(x)T(x)bb1 1,b,b2 2,b bm m 于是于是 为满射。为满射。定理得证。定理得证。例子例子考虑考虑110110的正因子的集合的正因子的集合S S110110关于关于gcd,lcmgcd,lcm运算构成的布尔代数。运算构成的布尔代数。它的原子是它的原子是2 2、5 5和和1111，因此原子的集合，因此原子的集合A A2,5,112,5,11。幂集幂集P(A)P(A),2,5,11,2,5,2,11,5,11,2,5,11,2,5,11,2,5,2,11,5,11,2,5,11。幂集代数是幂集代数是P(A),A。只要令只要令 :S:S110110P(A)P(A)，(1)(1)，(2)(2)22，(5)(5)55，(11)(11)1111，(10)(10)2,52,5，(22)(22)2,112,11，(55)(55)5,11,5,11,(110)(110)A A，那么那么f f就是定理就是定理13.1113.11中从中从S S110110到幂集到幂集P(A)P(A)的同构映射。的同构映射。推论推论1 1推论推论1 1 任何有限布尔代数的基数为任何有限布尔代数的基数为2 2n，nNN。证明证明 设设B B是有限布尔代数，是有限布尔代数，A A是是B B的所有原子构成的集合，的所有原子构成的集合，且且|A|A|n，nNN。由定理由定理13.11 13.11 得得B BP(A)P(A)，而，而|P(A)|P(A)|2 2n，所以，所以|B|B|2 2n。推论推论2 2推论推论2 2 任何等势的有限布尔代数都是同构的。任何等势的有限布尔代数都是同构的。证明证明 设设B B1 1和和B B2 2是有限布尔代数，且是有限布尔代数，且|B|B1 1|=|B|=|B2 2|。则则B B1 1P(AP(A1 1)，B B2 2P(AP(A2 2)，其中，其中A A1 1和和A A2 2分别为分别为B B1 1和和B B2 2的原子集合。的原子集合。易见易见|A|A1 1|A|A2 2|，存在双射，存在双射f f：A A1 1A A2 2。令。令：P(AP(A1 1)P(A)P(A2 2)，(x)(x)f(x)f(x)，x x A A1 1下面证明下面证明 是是P(AP(A1 1)到到P(AP(A2 2)的同构映射。的同构映射。任取任取x,yP(Ax,yP(A1 1)，由定理，由定理7.57.5有有 f(xy)f(xy)f(x)f(y)f(x)f(y)f(xy)f(xy)f(x)f(y)f(x)f(y)又由于又由于f f的单射性，必有的单射性，必有f(xy)f(xy)f(x)f(y)f(x)f(y)由于由于f(x)f(f(x)f(x x)f(xf(xx x)f(f()f(x)f(f(x)f(x x)f(xf(xx x)f(Af(A1 1)A A2 2得得 f(f(x x)f(x)f(x)，这就证明了，这就证明了 是是P(AP(A1 1)到到P(AP(A2 2)的同态映射。的同态映射。综上所述综上所述,有有P(AP(A1 1)P(AP(A2 2),),根据习题十三章第根据习题十三章第1919题，题，B B1 1B B2 2得证。得证。有限布尔代数的说明有限布尔代数的说明q 有限布尔代数的基数都是有限布尔代数的基数都是2 2的幂。的幂。q 在同构意义上，对于任何在同构意义上，对于任何2 2n，n为自然数，为自然数，仅存在一个仅存在一个2 2n元元的布尔代数的布尔代数。q 下图给出了下图给出了1 1元元,2,2元元,4,4元和元和8 8元的布尔代数。元的布尔代数。主要内容主要内容q 布尔代数的两个等价定义：布尔代数的两个等价定义：有补分配格；有补分配格；有两个二元运算并满足交换律、分配律、同一律和补元有两个二元运算并满足交换律、分配律、同一律和补元律的代数系统。律的代数系统。q 布尔代数的特殊性质：双重否定律和德摩根律。布尔代数的特殊性质：双重否定律和德摩根律。q 对于任意自然数对于任意自然数n n，只有一个，只有一个2 2n n元的有限布尔代数，就是幂元的有限布尔代数，就是幂集代数。集代数。学习要求学习要求q 能够判断给定偏序集或者代数系统是否构成格。能够判断给定偏序集或者代数系统是否构成格。q 能够确定一个命题的对偶命题。能够确定一个命题的对偶命题。q 能够证明格中的等式和不等式。能够证明格中的等式和不等式。q 能够判别格能够判别格L L的子集的子集S S是否构成格。是否构成格。q 能够判别给定的格是否为分配格。能够判别给定的格是否为分配格。q 能够判别布尔代数并证明布尔代数的等式。能够判别布尔代数并证明布尔代数的等式。作业作业习题十三习题十三1 1，2 2，3 3，6 6，8 8，1212，1616，1717，1919