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

第11章 格与布尔代数,离 散 数 学,中国地质大学本科生课程,本章内容,11.1 格的定义与性质 11.2 分配格、有补格与布尔代数 本章总结 作业,11.1 格的定义与性质,定义11.1 设是偏序集，如果x,yS，x,y都有最小上界和最大下界，则称S关于偏序作成一个格(lattice)。 说明：由于最小上界和最大下界的唯一性，可以把求x,y的最小上界和最大下界看成x与y的二元运算和。 xy：表示x与y的最小上界 xy：表示x和y的最大下界。 本章出现的和符号只代表格中的运算，而不再有其它的含义。,格的实例,例11.1 设n是正整数，Sn是n的正因子的集合。D为整除关系，则偏序集构成格。x,ySn， xy是lcm(x,y)，即x与y的最小公倍数。 xy是gcd(x,y)，即x与y的最大公约数。 下图给出了格，和。,例11.2,例11.2 判断下列偏序集是否构成格,并说明理由。 (1) ，其中P(B)是集合B的幂集。 (2) ，其中Z是整数集,为小于或等于关系。 (3) 偏序集的哈斯图分别在下图给出。,例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没有最大下界。,例11.3,例11.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就是。,对偶原理,定义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 有 abbaabba (2)结合律 a,b,cL 有 (ab)ca(bc)(ab)ca(bc) (3)幂等律 aL 有 aaaaaa (4)吸收律 a,bL 有 a(ab)aa(ab)a,定理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)得证。,定理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.2,定理11.2 设是具有两个二元运算的代数系统，若对于*和运算适合交换律、结合律、吸收律，则可以适当定义S中的偏序，使得构成一个格，且a,bS有aba*b，abab。 思路 (1)证明在S中*和运算都适合幂等律。 (2)在S上定义二元关系R，并证明R为偏序关系。 (3)证明构成格。 说明通过规定运算及其基本性质可以给出格的定义。,定理11.2,aS，由吸收律得,(1)证明在S中*和运算都适合幂等律。,a*a, a*(a(a*a), a,同理有 aaa。,(2)在S上定义二元关系R，,a,bS 有,R abb,下面证明R在S上的偏序。,根据幂等律，,aS都有aaa，,即R，,所以R在S上是自反的。,a,bS 有,aRb且bRa, abb且baa, abaabb (由于a b=ba),所以R在S上是反对称的。,定理11.2,a,b,cS 有 aRb且bRc abb 且 bcc aca(bc) ac(ab)c acbcc aRc 这就证明了R在S上是传递的。 综上所述，R为S上的偏序。 以下把R记作。,定理11.2,(3) 证明构成格。 即证明abab，aba*b 。,a,bS 有,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。,abb a*ba(13.7),格的等价定义,根据定理11.2，可以给出格的另一个等价定义。 定义11.3 设是代数系统，*和是二元运算，如果*和满足交换律，结合律和吸收律，则构成一个格(lattice)。 说明格中的幂等律可以由吸收律推出。 以后我们不再区别是偏序集定义的格，还是代数系统定义的格，而统称为格L。,格的性质,定理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。,格的性质,定理11.4 设L是格，a,b,c,dL，若ab且cd，则 acbd，acbd 证明 acab accd 因此， acbd。 同理可证 acbd。,例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) 说明在格中分配不等式成立。 一般说来，格中的和运算并不是满足分配律的。,本节小结,偏序集构成格的条件：任意二元子集都有最大下界和最小上界。 格的实例：正整数的因子格，幂集格，子群格。 格的性质：对偶原理，格中算律（交换、结合、幂等、吸收），保序性，分配不等式。 格作为代数系统的定义。 格的证明方法,子格,定义11.4 设是格，S是L的非空子集，若S关于L中的运算和仍构成格，则称S是L的子格。,例11.6 设格L如右图所示。令,S1a,e,f,g S2a,b,e,g,则S1不是L的子格，S2是L的子格。 因为对于e和f,有efc， 但cS1。,11.2 分配格、有补格与布尔代数,一般说来，格中运算对满足分配不等式， 即a,b,cL，有 a(bc)(ab)(ac) 但是不一定满足分配律。满足分配律的格称为分配格。 定义11.5 设是格，若a,b,cL，有 a(bc)(ab)(ac) a(bc)(ab)(ac) 则称L为分配格。 说明上面两个等式互为对偶式。 在证明L为分配格时，只须证明其中的一个等式即可。,例11.7,L1和L2是分配格，L3和L4不是分配格。,在L3中，b(cd),beb,(bc)(bd),aaa,在L4中,c(bd),cac,(cb)(cd),edd,钻石格,五角格,分配格的判别,定理11.5 设L是格，则L是分配格当且仅当L中不含有与钻石格或五角格同构的子格。 证明略。 推论(1) 小于五元的格都是分配格。 (2) 任何一条链都是分配格。,例11.8,说明下图中的格是否为分配格，为什么？,L1, L2和L3都不是分配格。 a,b,c,d,e是L1的子格，并且同构于钻石格。 a,b,c,e,f是L2的子格，并且同构于五角格。 a,c,b,e,f是L3的子格，也同构于钻石格。,格的全下界和全上界,定义11.6 设L是格， 若存在aL使得xL有ax，则称a为L的全下界； 若存在bL使得xL有xb，则称b为L的全上界。 命题格L若存在全下界或全上界，一定是唯一的。 证明以全下界为例，假若a1和a2都是格L的全下界, 则有a1a2和a2a1。 根据偏序关系的反对称性必有a1a2。 记法将格L的全下界记为0，全上界记为1。,有界格,定义11.7 设L是格，若L存在全下界和全上界，则称L为有界格，并将L记为。 说明有限格L一定是有界格。 举例 设L是n元格，且La1,a2,an，那么a1a2an是L的全下界，而a1a2an是L的全上界。因此L是有界格。 对于无限格L来说，有的是有界格，有的不是有界格。 如集合B的幂集格，不管B是有穷集还是无穷集，它都是有界格。它的全下界是空集，全上界是B。 整数集Z关于通常数的小于或等于关系构成的格不是有界格，因为不存在最小和最大的整数。,有界格的性质,定理（补充） 设是有界格，则aL有 a00a0a a1aa11 证明由 a00 和 0a0 可知 a00。 说明 在有界格中， 全下界0是关于运算的零元，运算的单位元。 全上界1是关于运算的零元，运算的单位元。 对偶原理 对于涉及到有界格的命题，如果其中含有全下界0或全上界1，在求该命题的对偶命题时，必须将0替换成1，而将1替换成0。 例如a00 和 a11 互为对偶命题， a0a 和 a1a 互为对偶命题。,有界格中的补元,定义11.8 设是有界格，aL， 若存在bL 使得 ab0 和 ab1 成立，则称b是a的补元。 说明若b是a的补元，那么a也是b的补元。 换句话说，a和b互为补元。,例11.9,考虑下图中的四个格。,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的补元是b，d的补元是b。,有界格中补元的说明,在任何有界格中， 全下界0与全上界1互补。 对于其他元素，可能存在补元，也可能不存在补元。 如果存在，可能是唯一的，也可能是多个补元。 对于有界分配格，如果它的元素存在补元，一定是唯一的。,有界分配格中补元的唯一性,定理11.6 设是有界分配格。 若aL，且对于a存在补元b，则b是a的唯一补元。 证明假设cL也是a的补元，则有 ac1，ac0 又知b是a的补元，故 ab1，ab0 从而得到 acab，acab 由于L是分配格，根据定理13.7，bc。,有补格的定义,定义11.9 设是有界格，若L中所有元素都有补元存在，则称L为有补格。,L2,L3和L4是有补格， L1不是有补格。,L2和L3是有补格， L1不是有补格。,本节小结,如果格中一个运算对另一个运算是可分配的，称这个格是分配格。 分配格的两种判别法： 不存在与钻石格或五角格同构的子格； 对于任意元素a,b,c,有 abac且abacbc。 有界格的定义及其实例。 格中元素的补元及其性质（分配格中补元的唯一性）。 有补格的定义。,布尔代数,定义11.10 如果一个格是有补分配格，则称它为布尔格或布尔代数。 说明在布尔代数中，每个元素都存在着唯一的补元。 可以把求补元的运算看作是布尔代数中的一元运算。 可以把一个布尔代数标记为， 为求补运算, aB，a是a的补元。,例11.10,例11.10 设S1101,2,5,10,11,22,55,110是110的正因子集合。令gcd,lcm分别表示求最大公约数和最小公倍数的运算。问是否构成布尔代数？为什么？ 解答 证明构成格。,容易验证x,y,zS110，有 gcd(x,y)S110 lcm(x,y)S110 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,zS110 有 gcd(x,lcm(y,z)lcm(gcd(x,y),gcd(x,z) 证明 是有补格。 1 为S110中的全下界 110为S110中的全上界 1和110互为补元，2和55互为补元， 5和22互为补元，10和11互为补元。 综上所述，为布尔代数。,例11.10（2）,例11.10（2） 设B为任意集合,证明B的幂集格构成布尔代数，称为集合代数。 证明P(B)关于和构成格，因为 和运算满足交换律、结合律和吸收律。 由于和互相可分配，因此P(B)是分配格， 且全下界是空集,全上界是B。 根据绝对补的定义，取全集为B， xP(B)，x是x的补元。 从而证明P(B)是有补分配格，即布尔代数。,布尔代数的性质,定理11.7 设是布尔代数，则 (1) aB，(a)a (2) a,bB，(ab)ab,(ab)ab 说明(1)称为双重否定律。 (2)称为德摩根律。 命题代数与集合代数的双重否定律与德摩根律实际上是这个定理的特例。 可以证明德摩根律对有限个元素也是正确的。 证明(1) (a)是a的补元，a也是a的补元。 由补元的唯一性得(a)a。,定理11.7(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。,布尔代数作为代数系统的定义,定义11.11 设是代数系统，*和是二元运算。 若*和运算满足： (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。,关于布尔代数定义的说明,为证明以上定义的是布尔代数，只需证明它是一个格，即证明*和运算满足结合律和吸收律。 证明吸收律，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)*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)(分配律) 所以（2）式成立。,有限布尔代数的结构,定义11.12 设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中元素构成的单元集。,有限布尔代数的表示定理,定理11.8 (有限布尔代数的表示定理) 设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(xy) 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)。,定理11.8证明,任取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),定理11.8证明,任取xB，存在xB 使得 xx1， xx0 因此有 (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)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， (11)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)，xA1 下面证明是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元的布尔代数。,主要内容,布尔代数的两个等价定义： 有补分配格； 有两个二元运算并满足交换律、分配律、同一律和补元律的代数系统。 布尔代数的特殊性质：双重否定律和德摩根律。 对于任意自然数n，只有一个2n元的有限布尔代数，就是幂集代数。,学习要求,能够判断给定偏序集或者代数系统是否构成格。 能够确定一个命题的对偶命题。 能够证明格中的等式和不等式。 能够判别格L的子集S是否构成格。 能够判别给定的格是否为分配格。 能够判别布尔代数并证明布尔代数的等式。,作业,习题十三 1，2，3，6，8，12，16，17，19,格的证明方法,格中等式的证明方法 证明等式的左边“小于等于”右边，右边“小于等于”左边。 根据偏序关系的反对称性，得到需要的等式。 格中不等式的证明方法 aa(偏序关系的自反性) ab且bc ac (偏序关系的传递性) aba，abb，aab，bab (下界定义与上界的定义) ab且ac abc，ba且ca bca (最大下界定义与最小上界的定义) ab且cd acbd，acbd(保序性),