离散数学-第10讲-分配格、有界格与有补格ppt课件.ppt

《离散数学-第10讲-分配格、有界格与有补格ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学-第10讲-分配格、有界格与有补格ppt课件.ppt（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1离散数学（二）离散数学（二）特殊格特殊格:分配格分配格,有界格与有补格有界格与有补格分配格分配格1 11 1有界格和有补格有界格和有补格2 2主要内容主要内容:分配格分配格,有界格与有补格有界格与有补格重点重点:重点和难点重点和难点:布尔格布尔格(布尔代数布尔代数)3 3有补格有补格的定义的定义难点难点:一、分配格一、分配格分配格的定义：分配格的定义：设是一个格,若对于任何a,b,cL,有a*(bc)=(a*b)(a*c)保交对保联可分配保交对保联可分配 (1)a(b*c)=(ab)*(ac)保联对保交可分配保联对保交可分配 (2)则称是一个分配格分配格。Note:上述定义中(1)和(2)是

2、等价的,只要一个成立,应用吸收律可推出另外一个。因此,判断一个格是否是分配格只需判断(1)或(2)其中之一其中之一.例例1:S=a,b,c,为分配格,因为任取A,B,C(S),(a)A(BC)=(AB)(AC)(b)A(BC)=(AB)(AC)一、分配格一、分配格例例2:2:图中钻石格与五角格是分配格吗？(a)b*(cd)b*ab (b*c)(b*d)eee 所以b*(cd)(b*c)(b*d)(b)c*(bd)c*ac (c*b)(c*d)ed=d 所以c*(bd)(c*b)(c*d)一、分配格一、分配格定理定理1 设是偏序格，则是分配格当且仅当 (i)在此格中不存在与钻石格同构的子格;(i

3、i)且不存在与五角格同构的子格。推论推论:设是格，|L|5,则是分配格。定理定理2 每个链都是分配格。证证明明:设是链，则必是格.任取a,b,cL,讨论以下两种情况:(1)ab或ac;(2)ab和ac。对于情况(1)有:a*(bc)=a;(a*b)(a*c)=aa=a.对于情况(2)有:a*(bc)=bc;(a*b)(a*c)=bc.因此有a*(bc)=(a*b)(a*c).所以,每个链都是分配格.一、分配格一、分配格定理定理3 设是一个格，若*运算对运算可分配，则对*也可分配，反之亦然。证明证明:设*运算对运算可分配，即任取a,b,cL,满足 a*(bc)=(a*b)(a*c),现要证 a(

4、b*c)=(ab)*(ac).(ab)*(ac)=(ab)*a)(ab)*c)=a (a*c)(b*c)=a(a*c)(b*c)=a(b*c)同理可由a(b*c)=(ab)*(ac)推出a*(bc)=(a*b)(a*c).一、分配格一、分配格定理定理4 设是一个分配格，那么对于任意a,b,cL,若有a*b=a*c和ab=ac，则必有b=c。证明证明:c=(a*c)c=(a*b)c =(ac)*(bc)=(ab)*(bc)=(ab)*b)(ab)*c)=b(a*c)(b*c)=b(a*b)(b*c)=b(a*c)=b(a*b)=b二、有界格和有补格二、有界格和有补格全上全上/下界定义下界定义:设

5、是一个格,若aL,对所有xL均有xa,称a为格的全上界全上界；若bL,对所有xL均有bx,称b为格的全下界全下界。通常将全上界记为“1”，而将全下界记为“0”。定理定理5 对于一个格,若全上界存在,那么它是唯一的(若全下界存在,则唯一).Note:1 有限格必有全上界(全下界)2 无限格不一定有全上界(全下界)如无全上界.有界格的定义有界格的定义:具有全上界和全下界的格称为有界格有界格,记作.二、有界格和有补格二、有界格和有补格例例2 (1)S=a,b,c,偏序格是，全上界 S A(S),有AS全下界 A(S),有A (2)X=A|A是由变元p1,p2,pn,构成的合式公式集。诱导的偏序格是.

6、全上界 T PX,有PT 全下界 F PX,有FP.二、有界格和有补格二、有界格和有补格定理定理6 设是一个有界格，则对于aA,都有 a1=1 a1=a (1是运算的零元,运算的幺元)a0=a a0=0 (0是运算的幺元,运算的零元)证明证明:(1)证 a1=1 因为a1 L且1是全上界，所以 a11;又因为 1 a1，所以 a1=1.(2)证 a1=a 因为a a，a 1,所以a a1;又因为 a1 a，所以a1=a.(3)(4)类似可证.二、有界格和有补格二、有界格和有补格补元的定义补元的定义:设是有界格aL,若存在bL使得ab=1和ab=0,则称b为a的补元补元。(1)中a,b,c都不存

7、在补元,0与1互为补元.(2)中a,b,c中任意两个都互为补元,0与1互为补元.(3)中a的补元都是b和c,而c的补元是a,0与1互为补元.Note:在格中有的元素无补元在格中有的元素无补元,有的元素有补元有的元素有补元,有的元素有多个补元有的元素有多个补元.二、有界格和有补格二、有界格和有补格有补格定义有补格定义:如果在一个有界格中，每个元素都至少有一个补元,则称这个格为有补格有补格.上图中(2)和(3)是有补格,而(1)不是有补格.证明证明:01=0，01=1，0、1互为补元。设c也是0的补元，0c=1，必有c=1，故0的补元唯一。同理可证1的补元也唯一。定理定理7 在有界格中,0 和 1

8、互为补元,且是唯一的.证明证明:设 b,c都是a的补元,则ab=0=ac,ab=1=ac,分配格满足消去律,可知b=c.消去律:(即对于任意a,b,cL有(ab=ac)(ab=ac)b=c)定理定理8 在分配格中，如果元素aL有一个补元a，则此补元a是唯一的.三、布尔格三、布尔格(布尔代数布尔代数)布尔格的定义布尔格的定义 如果格,既是有补格,又是分配格,则称此格为布尔格布尔格(或有有补分配格补分配格),也叫做布尔代数布尔代数.例例3 设S是非空有限集合,为代数格 A,B(S)，ABAB=AAB由诱导的偏序格是.说明是布尔格.证明证明(1)是格;(2)是有界格有界格,因为 全上界 S A(S)

9、,有AS 全下界 A(S),有A;(3)是有补格有补格,因任取 A(S),A的补元是S-A;(4)是分配格分配格,因和运算满足相互分配律.综上可知,是一个布尔格布尔格。三、布尔格三、布尔格(布尔代数布尔代数)例例4 X=A|A是由变元p1,p2,pn,构成的合式公式集。诱导的偏序格是.说明是布尔格.证明证明(1)是格，(2)是有界格,因为 全上界 T PX,有PT 全下界 F PX,有FP.(3)是有补格，因任取 PX,P的补元是P (4)是分配格,因和运算满足相互分配律，综上可知,是一个布尔格。三、布尔格三、布尔格(布尔代数布尔代数)由于布尔代数L中的每个元都有唯一的补元.求一个元素的补元素可以求一个元素的补元素可以看作一元运算看作一元运算,称为补运算称为补运算.因此,布尔代数L可记为,其中表示求补运算.证明证明(1)由于aa=1,aa=0;根据交换律有,aa=1,aa=0;所以(a)=a;(2)(ab)(ab)=(aab)(bab)=0 (ab)(ab)=(aab)(bab)=1 根据补元的唯一性,可得(ab)=ab定理定理8 设是布尔格()，对于所有a,bL,有 (1)(a)=a (2)(ab)=ab (3)(ab)=ab (4)abab=0ab=1作业：P239习题7.39、1317谢谢同学们谢谢同学们!