离散数学屈婉玲第十四章研究报告.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * 格作为代数系统的定义 设S,?,?是具有两个二元运算的代数系统, 若对于?和?运算 适合交换律、结合律、吸收律, 则可以适当定义S中的偏序 ?, 使得 S,? 构成格, 且?a,b∈S 有 a∧b = a?b, a∨b = a?b. 格的等价定义：设S, ?, ? 是代数系统, ?和?是二元运算, 如 果?和?满足交换律、结合律和吸收律, 则S, ?,?构成格. * 分配格、有补格与布尔代数 定义14.18 设L,∧,∨是格, 若?a,b,c∈L,有 a∧(b∨c) = (a∧b)∨(a∧c)   a∨(b∧c) = (a∨b)∧(a∨c) 则称L为分配格. 注意：可以证明以上两个条件互为充分必要条件 L1 和 L2 是分配格, L3 和 L4不是分配格. 称 L3为钻石格, L4为五角格. 实例 * 分配格的判别 分配格的判别：设 L 是格, 则 L 是分配格当且仅当 L 不含有 与钻石格或五角格同构的子格. 小于五元的格都是分配格. 任何一条链都是分配格.? 例6 说明图中的格是否为分配格, 为什么？ 解 都不是分配格. { a,b,c,d,e }是L1的子格, 同构于钻石格 { a,b,c,e,f }是L2的子格, 同构于五角格； { a,c,b,e,f } 是L3的子格 同构于钻石格. * 有补格的定义 定义14.19 设L是格, (1) 若存在a∈L使得?x∈L有 a ? x, 则称a为L的全下界， 记 为0；若存在b∈L使得?x∈L有 x ? b, 则称b为L的全上界 ，记为1. ? (2) 若L存在全下界和全上界, 则称L 为有界格, 一般将有界 格L记为L,∧,∨,0,1. 定义14.20 设L,∧,∨,0,1是有界格, a∈L, 若存在b∈L 使得 a∧b = 0 和 a∨b = 1 成立, 则称b是a的补元. 定义14.21 设L,∧,∨,0,1是有界格, 若L中所有元素都有补 元存在, 则称L为有补格. * 补元的性质 注意： 在任何有界格中, 全下界0与全上界1互补. 对于一般元素, 可能存在补元, 也可能不存在补元. 如果存在补元, 可能是惟一的, 也可能是多个补元. 对于有界分配格, 如果元素存在补元, 一定是惟一的. * 有界格中的补元及实例 例7 L1：a 与 c 互补, a 为全下界, c为全上界, b 没有补元. L2：a 与 d 互补, a 为全下界, d 为全上界, b与 c互补. L3：a 与 e 互补, a 为全下界, e 为全上界, b 的补元是 c 和 d ; c 的补元是 b 和 d ; d 的补元是 b 和 c .? L4：a 与 e 互补, a 为全下界, e 为全上界, b 的补元是 c 和 d ; c 的补元是 b ; d 的补元是 b . L2, L3和L4是有补格, L1不是有补格. * 布尔代数的定义与实例 定义14.22 如果一个格是有补分配格, 则称它为布尔格或布 尔代数. 布尔代数标记为B,∧,∨,?, 0, 1, ?为求补运算. 例8 设 S110 = {1, 2, 5, 10, 11, 22, 55, 110}是110的正因子集合，gcd表示求最大公约数的运算，lcm表示求最小公倍数的运算，问S110, gcd, lcm是否构成布尔代数？为什么？ 解 (1) 不难验证S110关于gcd 和 lcm 运算构成格. (略) (2) 验证分配律 ?x, y, z∈S110 有 gcd(x, lcm(y, z)) = lcm(gcd(x, y), gcd(x, z)) (3) 验证它是有补格, 1作为S110中的全下界, 110为全上界,  1和110互为补元, 2和55互为补元, 5和22互为补元, 10和 11互为补元, 从而证明了S110, gcd, lcm为布尔代数. * 实例 例9 设B为任意集合, 证明B的幂集格P(B), ∩,∪, ~, ? , B 构成布尔代数, 称为集合代数. 证 (1) P(B)关于∩和∪构成格, 因为∩和∪运算满足交换律, 结合律和吸收律. (2) 由于∩和∪互相可分配, 因此P(B)是分配格. (3) 全下界是空集?, 全上界是B. (4) 根据绝对补的定义, 取全集为B, ? x