1、1离散数学（二）特殊格 :分配格 ,有界格与有补格分配格11有界格和有补格2主要内容 :分配格 ,有界格与有补格重点 : 重点和难点:布尔格 (布尔代数 )3有补格 的定义难点 : 一、分配格分配格的定义：设 是一个格 , 若对于任何 a,b,c L,有a*(bc) = (a*b)(a*c) 保交对保联可分配 (1)a(b*c) = (ab)*(ac) 保联对保交可分配 (2)则称 是一个 分配格 。Note: 上述定义中 (1)和 (2)是等价的 ,只要一个成立 ,应用吸收律可推出另外一个。因此 ,判断一个格是否是分配格只需判断(1)或 (2)其中之一 .例 1:S=a,b,c, 为分配格
2、, 因为任取 A,B,C (S),(a) A (BC)=(A B)(A C) (b) A(B C)=(AB) (AC)一、分配格例 2: 图中钻石格与五角格是分配格吗？(a) b*(cd) b*a b (b*c)(b*d) ee e所以 b*(cd) (b*c)(b*d)(b) c*(bd) c*a c (c*b)(c*d) ed=d所以 c*(bd) (c*b)(c*d)一、分配格定理 1 设 是偏序格，则 是分配格当且仅当(i) 在此格中不存在与钻石格同构的子格 ;(ii) 且不存在与五角格同构的子格。推论 :设 是格， |L|是分配格 。定理 2 每个链都是分配格。证明 : 设 是链，则
3、 必是格 .任取 a,b,c L,讨论以下两种情况 : (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,c L,满足a*(bc) = (a*b)(a*c),现要证 a(b*c) = (ab)*(ac).(ab)*(ac) = (ab)
4、* 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,c L,若有 a*b=a*c和 ab=ac，则必有 b=c。证明 : c = (a*c) c = (a*b) c = (a c) *(b c) = (a b)*(b c) = (a b)*b) (a b) * c) = b (a*c) (b*c)= b (a*b) (b*c)= b (a*c)= b (a*b)= b二、有界格和有补格全上 /下界定义
5、:设 是一个格 ,若 a L, 对所有 x L均有 xa,称 a为格 的 全上界 ；若 b L, 对所有 x L均有 bx,称 b为格 的 全下界 。通常将全上界记为 “1”，而将全下界记为 “0”。定理 5 对于一个格 ,若全上界存在 ,那么它是唯一的 (若全下界存在 ,则唯一 ).Note: 1 有限格必有全上界 (全下界 )2 无限格不一定有全上界 (全下界 ) 如 无全上界 .有界格的定义 :具有全上界和全下界的格称为 有界格 ,记作 .二、有界格和有补格例 2 (1) S=a,b,c, 偏序格是 ，全上界 S A (S),有 A S全下界 A (S), 有 A(2) X=A|A是由变元 p1,p2, pn, , , , , 构成的合式公式集 。 诱导的偏序格是 .全上界 T P X,有 PT全下界 F P X, 有 FP.二、有界格和有补格定理 6 设 是一个有界格，则对于 aA,都有a 1=1 a 1=a (1是 运算的零元 , 运算的幺元 )a 0=a a 0=0 (0是 运算的幺元 , 运算的零元 ) 证明 : (1) 证 a 1=1 因为 a 1 L且 1是全上界，所以 a 11;又因为 1 a 1，所以 a 1=1.(2) 证 a 1=a 因为 a a， a 1, 所以 a a 1;又因为 a 1 a，所以 a 1=a.(3)(4)类似可证 .
