离散数学第11章格与布尔代数.ppt

《离散数学第11章格与布尔代数.ppt》由会员分享，可在线阅读，更多相关《离散数学第11章格与布尔代数.ppt（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第十一章第十一章 格与布尔代数格与布尔代数主要内容主要内容l格的定义及性质格的定义及性质 l子格子格l分配格、有补格分配格、有补格l布尔代数布尔代数111.1 格的定义与性质格的定义与性质 定义定义11.1设设是偏序集，如果是偏序集，如果 x,y S，x,y都有最小上都有最小上界和最大下界，则称界和最大下界，则称S关于偏序关于偏序 作成一个作成一个格格.（偏序关系（偏序关系P126）求求x,y最小上界和最大下界看成最小上界和最大下界看成x 与与y 的二元运算的二元运算和和，例例1设设n是正整数，是正整数，Sn是是n的正因子的集合的正因子的集合.D为整除关系，为整除关系，则则偏序集偏序集构成格构

2、成格.x,ySn，xy是是lcm(x,y)，即，即x与与y的的最小公倍数最小公倍数.xy是是gcd(x,y)，即，即x与与y的最大公约数的最大公约数.2图2例例2判断下列偏序集是否构成格，并说明理由判断下列偏序集是否构成格，并说明理由.(1)，其中，其中P(B)是集合是集合B的幂集的幂集.(2)，其中，其中Z是整数集，是整数集，为小于或等于关系为小于或等于关系.(3)偏序集的哈斯图分别在下图给出偏序集的哈斯图分别在下图给出.实例实例(1)幂集格幂集格.x,yP(B)，xy就是就是xy，xy就是就是xy.(2)是格是格.x,yZ，xy=max(x,y)，xy=min(x,y)，(3)都不是格都不

3、是格.可以找到两个结点缺少最大下界或最小上界可以找到两个结点缺少最大下界或最小上界3格的性质：算律格的性质：算律定理定理11.1设设是格是格,则运算则运算和和适合交换律、结合律、适合交换律、结合律、幂等律和吸收律幂等律和吸收律,即即(1)a,bL有有 ab=ba,ab=ba(2)a,b,cL有有(ab)c=a(bc),(ab)c=a(bc)(3)aL有有aa=a,aa=a(4)a,bL有有a(ab)=a,a(ab)=a4格的性质：序与运算的关系格的性质：序与运算的关系定理定理11.3设设L是格是格,则则 a,bL有有a bab=aab=b 可以用集合的例子来验证可以用集合的例子来验证 幂集格幂

4、集格，其中，其中P(B)是集合是集合B的幂集的幂集.幂集格幂集格.x,yP(B)，xy就是就是xy，xy就是就是xy.5格的性质：保序格的性质：保序定理定理11.4设设L是格是格,a,b,c,dL，若若a b 且且c d,则则ac bd,ac bd例例4设设L是格是格,证明证明 a,b,cL有有 a(bc)(ab)(ac).证证ac a b,ac c d 因此因此ac bd.同理可证同理可证ac bd 证证由由a a,bc b得得a(bc)ab由由a a,bc c得得a(bc)ac从而得到从而得到a(bc)(ab)(ac)（注意最大下界）（注意最大下界）注意：一般说来注意：一般说来,格中的格中

5、的和和运算不满足分配律运算不满足分配律.6格作为代数系统的定义格作为代数系统的定义定理定理11.4设设是具有两个二元运算的代数系统是具有两个二元运算的代数系统,若对于若对于 和和运算适合交换律、结合律、吸收律运算适合交换律、结合律、吸收律,则可以适当定义则可以适当定义S中中的偏序的偏序,使得使得构成格构成格,且且 a,bS 有有ab=a b,ab=ab.证明省略证明省略.根据定理根据定理11.4,可以给出格的另一个等价定义可以给出格的另一个等价定义.定义定义11.3设设是代数系统是代数系统,和和是二元运算是二元运算,如果如果 和和满足交换律、结合律和吸收律满足交换律、结合律和吸收律,则则构成格

6、构成格.711.2分配格、有补格与布尔代数分配格、有补格与布尔代数 定义定义11.5设设是格是格,若若 a,b,cL,有有a(bc)=(ab)(ac)a(bc)=(ab)(ac)则称则称L为为分配格分配格.l注意：可以证明以上两个条件互为充分必要条件注意：可以证明以上两个条件互为充分必要条件L1和和L2是分配格是分配格,L3和和L4不是分配格不是分配格.称称L3为为钻石格钻石格,L4为为五角格五角格.实例实例8有界格的定义有界格的定义定义定义11.6设设L是格是格,(1)若存在若存在aL使得使得 xL有有a x,则称则称a为为L的的全下界全下界(2)若存在若存在bL使得使得 xL有有x b,则

7、称则称b为为L的的全上界全上界说明：说明：l格格L若存在全下界或全上界若存在全下界或全上界,一定是惟一的一定是惟一的.l一般将格一般将格L的全下界记为的全下界记为0,全上界记为全上界记为1.定义定义11.7设设L是格是格,若若L存在全下界和全上界存在全下界和全上界,则称则称L 为为有界有界格格,一般将有界格一般将有界格L记为记为.9 定理定理11.6设设是有界格是有界格,则则 aL有有a0=0,a0=a,a1=a,a1=1注意：注意：l有限格有限格L=a1,a2,an是有界格是有界格,a1a2an是是L的全的全下界下界,a1a2an是是L的全上界的全上界.l0是关于是关于运算的零元运算的零元,

8、运算的单位元；运算的单位元；1是关于是关于运算运算的零元的零元,运算的单位元运算的单位元.有界格的性质有界格的性质10有界格中的补元及实例有界格中的补元及实例定义定义11.8设设是有界格是有界格,aL,若存在若存在bL使得使得ab=0和和ab=1成立成立,则称则称b是是a的的补元补元.l注意：若注意：若b是是a的补元的补元,那么那么a也是也是b的补元的补元.a和和b互为补元互为补元.例例7考虑下图中的格考虑下图中的格.针对不同的元素，求出所有的补元针对不同的元素，求出所有的补元.11解答解答(1)L1中中a 与与c 互为补元互为补元,其中其中a 为全下界为全下界,c为全上界为全上界,b 没没有

9、有补元补元.(2)L2中中a 与与d 互为补元互为补元,其中其中a 为全下界为全下界,d 为全上界为全上界,b与与c也互为补元也互为补元.(3)L3中中a 与与e 互为补元互为补元,其中其中a 为全下界为全下界,e 为全上界为全上界,b 的的补补元是元是c 和和d;c 的补元是的补元是b 和和d;d 的补元是的补元是b 和和c;b,c,d 每个元素都有两个补元每个元素都有两个补元.(4)L4中中a 与与e 互为补元互为补元,其中其中a 为全下界为全下界,e 为全上界为全上界,b 的的补补元是元是c 和和d;c 的补元是的补元是b;d 的补元是的补元是b.12有界分配格的补元惟一性有界分配格的补

10、元惟一性定理定理11.7设设是有界分配格是有界分配格.若若L中元素中元素a 存在存在补元补元,则存在惟一的补元则存在惟一的补元.证证假设假设c 是是a 的补元的补元,则有则有ac=1,ac=0,又知又知b 是是a 的补元的补元,故故ab=1,ab=0从而得到从而得到ac=ab,ac=ab,由于由于L是分配格是分配格.b=b (ba)=b(ca)=(bc)(ba)=(ac)c=c注意：注意：l在任何有界格中在任何有界格中,全下界全下界0与全上界与全上界1互补互补.l对于一般元素对于一般元素,可能存在补元可能存在补元,也可能不存在补元也可能不存在补元.如果如果存在补元存在补元,可能是惟一的可能是惟

11、一的,也可能是多个补元也可能是多个补元.对于有界对于有界分配格分配格,如果元素存在补元如果元素存在补元,一定是惟一的一定是惟一的.13图9有补格的定义有补格的定义定义定义11.9设设是有界格是有界格,若若L中所有元素都有补中所有元素都有补元存在元存在,则称则称L为为有补格有补格.例如例如,图中的图中的L2,L3和和L4是有补格是有补格,L1不是有补格不是有补格.14布尔代数的定义与实例布尔代数的定义与实例定义定义11.10 如果一个格是有补分配格如果一个格是有补分配格,则称它为布尔格或布则称它为布尔格或布尔代数尔代数.布尔代数标记为布尔代数标记为,为求补运算为求补运算.例例8设设S110=1,

12、2,5,10,11,22,55,110是是110的正因子集合，的正因子集合，gcd表示求最大公约数的运算，表示求最大公约数的运算，lcm表示求最小公倍数的运算，表示求最小公倍数的运算，问问是否构成布尔代数？为什么？是否构成布尔代数？为什么？解解画出哈斯图？画出哈斯图？(1)不难验证不难验证S110关于关于gcd和和lcm运算构成格运算构成格.(略略)(2)验证分配律验证分配律 x,y,zS110有有gcd(x,lcm(y,z)=lcm(gcd(x,y),gcd(x,z)(3)验证它是有补格验证它是有补格,1作为作为S110中的全下界中的全下界,110为全上界为全上界,1和和110互为补元互为补

13、元,2和和55互为补元互为补元,5和和22互为补元互为补元,10和和11互为补元互为补元,从而证明了从而证明了为布尔代数为布尔代数.15布尔代数的性质布尔代数的性质定理定理11.8设设是布尔代数是布尔代数,则则(1)aB,(a)=a.(2)a,bB,(ab)=a b,(ab)=a b（德（德摩根律）摩根律）证证(1)(a)是是a 的补元的补元,a也是也是a 的补元的补元.由补元惟一性由补元惟一性得得(a)=a.(2)对任意对任意a,bB有有(ab)(a b)=(aa b)(ba b)=(1b)(a 1)=11=1,(ab)(a b)=(aba)(abb)=(0b)(a0)=00=0a b 是是

14、ab的补元的补元,根据补元惟一性有根据补元惟一性有(ab)=a b,同理同理可证可证(ab)=a b.l注意：德摩根律对有限个元素也是正确的注意：德摩根律对有限个元素也是正确的.16图11实例实例下图给出了下图给出了 1元元,2元元,4元和元和8元的布尔代数元的布尔代数.17第十一章第十一章 习题课习题课主要内容主要内容l格的两个等价定义格的两个等价定义l格的性质格的性质l子格子格l特殊格：分配格、有界格、有补格、布尔代数特殊格：分配格、有界格、有补格、布尔代数基本要求基本要求l能够判别给定偏序集或者代数系统是否构成格能够判别给定偏序集或者代数系统是否构成格l能够确定一个命题的对偶命题能够确定

15、一个命题的对偶命题l能够证明格中的等式和不等式能够证明格中的等式和不等式l能判别格能判别格L的子集的子集S是否构成子格是否构成子格l能够判别给定的格是否为分配格、有补格能够判别给定的格是否为分配格、有补格l能够判别布尔代数并证明布尔代数中的等式能够判别布尔代数并证明布尔代数中的等式 18解1求图中格的所有子格求图中格的所有子格.1元子格：元子格：a,b,c,d,e；2元子格：元子格：a,b,a,c,a,d,a,e,b,c,b,d,b,e,c,e,d,e；3元子格：元子格：a,b,c,a,b,d,a,b,e,a,c,e,a,d,e,b,c,e,b,d,e；4元子格：元子格：a,b,c,e,a,b

16、,d,e,b,c,d,e；5元子格：元子格：a,b,c,d,e 练习练习1eabcd19L1L2 L3图122针对下图，求出每个格的补元并说明它们是否为有补格针对下图，求出每个格的补元并说明它们是否为有补格L1中中,a与与h互为补元互为补元,其他元素没补元其他元素没补元.L2中中,a与与g互为补元互为补元.b的补元为的补元为c,d,f；c的补元为的补元为b,d,e,f；d的补元为的补元为b,c,e；e的补元为的补元为c,d,f；f的补元为的补元为b,c,e.L3中中,a与与h互为补元互为补元,b的补元为的补元为d；c的补元为的补元为d；d的补元为的补元为b,c,g；g的补元为的补元为d.L2与与L3是有补格是有补格.练习练习220