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

1、1,离散数学（二）,特殊格:分配格,有界格与有补格,主要内容:,重点和难点:,一、分配格,分配格的定义： 设是一个格, 若对于任何a,b,cL,有 a*(bc) = (a*b)(a*c) 保交对保联可分配 (1) a(b*c) = (ab)*(ac) 保联对保交可分配 (2) 则称是一个分配格。 Note: 上述定义中(1)和(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) 在此格中不存在与钻石格同构的子格; (ii) 且不存在与五角格同构的子格。 推论:设是格，|L|是分配格。 定理2 每个链都是分配格。 证明: 设是链，则必是格.任取a,b,cL,讨论以下两种情况: (1) ab或ac; (2) ab和ac。 对于情况(1)有: a*(bc)=a; (a*b)(a*c)

3、=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(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

4、*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,二、有界格和有补格,全上/下界定义: 设是一个格, 若aL, 对所有xL均有xa,称a为格的全上界； 若bL, 对所有xL均有bx,称b为格的全下界。 通常将全上界记为“1”，而将全下界记为“0”。 定理5 对于一个格,若全上界存在,那么

5、它是唯一的(若全下界存在,则唯一). Note: 1 有限格必有全上界(全下界) 2 无限格不一定有全上界(全下界) 如无全上界. 有界格的定义: 具有全上界和全下界的格称为有界格,记作.,二、有界格和有补格,例2 (1) S=a,b,c, 偏序格是 ， 全上界 S A(S),有AS 全下界 A(S), 有A (2) X=A|A是由变元p1,p2,pn, , 构成的合式公 式集。诱导的偏序格是 . 全上界 T PX,有PT 全下界 F PX, 有FP.,二、有界格和有补格,定理6 设是一个有界格，则对于aA,都有 a1=1 a1=a (1是运算的零元,运算的幺元) a0=a a0=0 (0是运

6、算的幺元,运算的零元) 证明: (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都不存在补元,0与1互为补元. (2)中a,b,c中任意两个都互为补元, 0与1互为补元. (3)中a的补元都是b和c,而c的补元是a,0与1互为补元.,Note: 在格中有的元素无补元,有的元素有补元,有的元素有多个补元.,二、有

7、界格和有补格,有补格定义: 如果在一个有界格中，每个元素都至少有一个补元,则称这个格为有补格.上图中(2)和(3)是有补格,而(1)不是有补格.,证明: 01=0，01=1，0、1互为补元。设c也是0的补元， 0c =1， 必有c=1，故0的补元唯一。 同理可证1的补元也唯一。,定理7 在有界格中, 0 和 1互为补元, 且是唯一的.,证明: 设 b,c都是a的补元, 则ab=0=ac, ab=1=ac,分配格 满足消去律,可知b=c. 消去律: (即对于任意a,b,cL有(ab=ac) (ab=ac)b=c),定理8 在分配格中，如果元素aL有一个补元a ，则此补元a是唯一的.,三、布尔格(

8、布尔代数),布尔格的定义 如果格,既是有补格,又是分配格,则称此格为布尔格(或有补分配格),也叫做布尔代数.,例3 设S是非空有限集合, 为代数格 A,B(S)，ABAB=AAB 由诱导的偏序格是. 说明是布尔格.,证明 (1)是格; (2)是有界格, 因为 全上界 S A(S),有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)(