《离散数学第11章格与布尔代数.ppt》由会员分享，可在线阅读，更多相关《离散数学第11章格与布尔代数.ppt（20页珍藏版）》请在三一办公上搜索。
1、1,第十一章 格与布尔代数,主要内容格的定义及性质 子格分配格、有补格布尔代数,2,11.1 格的定义与性质,定义11.1 设是偏序集，如果x,yS，x,y都有最小上界和最大下界，则称S关于偏序作成一个格.（偏序关系P126）求x,y 最小上界和最大下界看成 x 与 y 的二元运算和，,例1 设n是正整数，Sn是n的正因子的集合.D为整除关系，则偏序集构成格.x,ySn，xy是lcm(x,y)，即x与y的最小公倍数.xy是gcd(x,y)，即x与y的最大公约数.,3,图2,例2 判断下列偏序集是否构成格，并说明理由.(1)，其中P(B)是集合B的幂集.(2)，其中Z是整数集，为小于或等于关系.
2、(3)偏序集的哈斯图分别在下图给出.,实例,(1)幂集格.x,yP(B)，xy就是xy，xy就是xy.(2)是格.x,yZ，xy=max(x,y)，xy=min(x,y)，(3)都不是格.可以找到两个结点缺少最大下界或最小上界,4,格的性质：算律,定理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)=a,5,格的性质：序与运算的关系,定理11.3 设L是格,则a,bL有a b ab=a ab
3、=b 可以用集合的例子来验证 幂集格，其中P(B)是集合B的幂集.幂集格.x,yP(B)，xy就是xy，xy就是xy.,6,格的性质：保序,定理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)（注意最大下界）注意：一般说来,格中的和运算不满足分配律.,7,格作为代数系统的定义,定理11.4 设是具有两个
4、二元运算的代数系统,若对于和运算适合交换律、结合律、吸收律,则可以适当定义S中的偏序,使得 构成格,且a,bS 有 ab=ab,ab=ab.证明省略.根据定理11.4,可以给出格的另一个等价定义.,定义11.3 设是代数系统,和是二元运算,如果和满足交换律、结合律和吸收律,则构成格.,8,11.2 分配格、有补格与布尔代数,定义11.5 设是格,若a,b,cL,有 a(bc)=(ab)(ac)a(bc)=(ab)(ac)则称L为分配格.注意：可以证明以上两个条件互为充分必要条件,L1 和 L2 是分配格,L3 和 L4不是分配格.称 L3为钻石格,L4为五角格.,实例,9,有界格的定义,定义1
5、1.6 设L是格,(1)若存在aL使得xL有 a x,则称a为L的全下界(2)若存在bL使得xL有 x b,则称b为L的全上界说明：格L若存在全下界或全上界,一定是惟一的.一般将格L的全下界记为0,全上界记为1.定义11.7 设L是格,若L存在全下界和全上界,则称L 为有界格,一般将有界格L记为.,10,定理11.6 设是有界格,则aL有a0=0,a0=a,a1=a,a1=1,注意：有限格L=a1,a2,an是有界格,a1a2an是L的全下界,a1a2an是L的全上界.0是关于运算的零元,运算的单位元；1是关于运算的零元,运算的单位元.,有界格的性质,11,有界格中的补元及实例,定义11.8
6、设是有界格,aL,若存在bL 使得 ab=0 和 ab=1 成立,则称b是a的补元.注意：若b是a的补元,那么a也是b的补元.a和b互为补元.,例7 考虑下图中的格.针对不同的元素，求出所有的补元.,12,解答,(1)L1中 a 与 c 互为补元,其中 a 为全下界,c为全上界,b 没有 补元.(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 互为
7、补元,其中 a 为全下界,e 为全上界,b 的补 元是 c 和 d;c 的补元是 b;d 的补元是 b.,13,有界分配格的补元惟一性,定理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)=(b c)(b a)=(ac)c=c,注意：在任何有界格中,全下界0与全上界1互补.对于一般元素,可能存在补元,也可能不存在补元.如果存在补元,可能是惟一的,也可能是多个补元.对于有界分配格,如果元素存在补
8、元,一定是惟一的.,14,图9,有补格的定义,定义11.9 设是有界格,若L中所有元素都有补元存在,则称L为有补格.例如,图中的L2,L3和L4是有补格,L1不是有补格.,15,布尔代数的定义与实例,定义11.10 如果一个格是有补分配格,则称它为布尔格或布尔代数.布尔代数标记为,为求补运算.,例8 设 S110=1,2,5,10,11,22,55,110是110的正因子集合，gcd表示求最大公约数的运算，lcm表示求最小公倍数的运算，问是否构成布尔代数？为什么？,解 画出哈斯图？(1)不难验证S110关于gcd 和 lcm 运算构成格.(略)(2)验证分配律 x,y,zS110 有 gcd(
9、x,lcm(y,z)=lcm(gcd(x,y),gcd(x,z)(3)验证它是有补格,1作为S110中的全下界,110为全上界,1和110互为补元,2和55互为补元,5和22互为补元,10和 11互为补元,从而证明了为布尔代数.,16,布尔代数的性质,定理11.8 设是布尔代数,则(1)aB,(a)=a.(2)a,bB,(ab)=ab,(ab)=ab（德摩根律）,证(1)(a)是a的补元,a也是a的补元.由补元惟一性得(a)=a.(2)对任意a,bB有(ab)(ab)=(aab)(bab)=(1b)(a1)=11=1,(ab)(ab)=(aba)(abb)=(0b)(a0)=00=0ab是ab
10、的补元,根据补元惟一性有(ab)=ab,同理可证(ab)=ab.注意：德摩根律对有限个元素也是正确的.,17,图11,实例,下图给出了 1 元,2 元,4 元和 8 元的布尔代数.,18,第十一章 习题课,主要内容格的两个等价定义格的性质子格特殊格：分配格、有界格、有补格、布尔代数基本要求能够判别给定偏序集或者代数系统是否构成格能够确定一个命题的对偶命题能够证明格中的等式和不等式能判别格L的子集S是否构成子格能够判别给定的格是否为分配格、有补格能够判别布尔代数并证明布尔代数中的等式,19,解,1求图中格的所有子格.,1元子格：a,b,c,d,e；2元子格：a,b,a,c,a,d,a,e,b,c
11、,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,d,e,b,c,d,e；5元子格：a,b,c,d,e,练习1,20,L1 L2 L3,图12,2针对下图，求出每个格的补元并说明它们是否为有补格,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是有补格.,练习2,
