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

* 离散数学（二） 特殊格:分配格,有界格与有补格 分配格 11 有界格和有补格 2 主要内容: 分配格,有界格与有补格 重点: 重点和难点: 布尔格(布尔代数) 3 有补格的定义 难点: 一、分配格 分配格的定义： 设L,*,⊕是一个格, 若对于任何a,b,c∈L,有 a*(b⊕c) = (a*b)⊕(a*c) 保交对保联可分配 (1) a⊕(b*c) = (a⊕b)*(a⊕c) 保联对保交可分配 (2) 则称L,*,⊕是一个分配格。 Note: 上述定义中(1)和(2)是等价的,只要一个成立,应用吸收律可推出另外一个。因此,判断一个格是否是分配格只需判断(1)或(2)其中之一. 例1:S={a,b,c}, ρ(S),∩,∪为分配格, 因为任取A,B,C∈ρ(S), (a) A∪(B∩C)=(A∪B)∩(A∪C) (b) A∩(B∪C)=(A∩B)∪(A∩C) 一、分配格 例2: 图中钻石格与五角格是分配格吗？ (a) b*(c⊕d)＝b*a＝b (b*c)⊕(b*d)＝e⊕e＝e 所以b*(c⊕d) ≠ (b*c)⊕(b*d) (b) c*(b⊕d)＝c*a＝c (c*b)⊕(c*d)＝e⊕d=d 所以c*(b⊕d) ≠ (c*b)⊕(c*d) 一、分配格 定理1 设L, ≤ 是偏序格，则L, ≤ 是分配格当且仅当 (i) 在此格中不存在与钻石格同构的子格; (ii) 且不存在与五角格同构的子格。 推论:设L, ≤ 是格，|L|5, 则L, ≤ 是分配格。 定理2 每个链都是分配格。 证明: 设L,≤是链，则L,≤必是格.任取a,b,c∈L,讨论以下两种情况: (1) a≤b或a≤c; (2) a≥b和a≥c。 对于情况(1)有: a*(b⊕c)=a; (a*b)⊕(a*c)=a⊕a=a. 对于情况(2)有: a*(b⊕c)=b⊕c; (a*b)⊕(a*c)=b⊕c. 因此有a*(b⊕c)=(a*b)⊕(a*c). 所以,每个链都是分配格. 一、分配格 定理3 设L,*,⊕是一个格，若*运算对⊕运算可分配，则⊕对*也可分配，反之亦然。 证明: 设*运算对⊕运算可分配，即任取a,b,c∈L,满足 a*(b⊕c) = (a*b)⊕(a*c), 现要证 a⊕(b*c) = (a⊕b)*(a⊕c). (a⊕b)*(a⊕c) = ((a⊕b) * a)⊕((a⊕b) *c) = a ⊕ [(a*c)⊕(b*c)] = [a⊕(a*c)]⊕(b*c) = a⊕(b*c) 同理可由a⊕(b*c) = (a⊕b)*(a⊕c)推出a*(b⊕c) = (a*b)⊕(a*c). 一、分配格 定理4 设L,*,⊕是一个分配格，那么对于任意a,b,c∈L,若有a*b= a*c和a⊕b=a⊕c，则必有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 二、有界格和有补格 全上/下界定义: 设L, ≤是一个格, 若?a∈L, 对所有x∈L均有x≤a,称a为格L, ≤的全上界； 若?b∈L, 对所有x∈L均有b≤x,称b为格L, ≤的全下界。 通常将全上界记为“1”，而将全下界记为“0”。 定理5 对于一个格L, ≤,若全上界存在,那么它是唯一的(若全下界存在,则唯一). Note: 1 有限格必有全上界(全下界) 2 无限格不一定有全上界(全下界) 如I, ≤ 无全上界. 有界格的定义: 具有全上界和全下界的格称为有界格,记作L,∧,∨,0,1. 二、有界格和有补格 例2 (1) S={a,b,c}, 偏序格是 ρ(S), ?， 全上界 S ?A∈ρ(S),有A?S 全下界 ? ?A∈ρ(S), 有??A (2) X={A|A是由变元p1,p2,…,pn, ﹁,∧,∨,→, ?