离散数学-格的定义与性质

《离散数学-格的定义与性质》由会员分享，可在线阅读，更多相关《离散数学-格的定义与性质（33页珍藏版）》请在金锄头文库上搜索。

1、1 11 1 格的定义与性质 定义11 1 设是偏序集 如果 x y S x y 都有最小上 界和最大下界 则称S关于偏序 作成一个格 求 x y 最小上界和最大下界看成 x 与 y 的二元运算 和 例1 设n是正整数 Sn是n的正因子的集合 D为整除关系 则 偏序集构成格 x y Sn x y是lcm x y 即x与y的 最小公倍数 x y是gcd x y 即x与y的最大公约数 2 图2 例2 判断下列偏序集是否构成格 并说明理由 1 其中P B 是集合B的幂集 2 其中Z是整数集 为小于或等于关系 3 偏序集的哈斯图分别在下图给出 实例 1 幂集格 x y P B x y就是x y x y

2、就是x y 2 是格 x y Z x y max x y x y min x y 3 都不是格 可以找到两个结点缺少最大下界或最小上界 3 实例 子群格 例3 设G是群 L G 是G 的所有子群的集合 即 L G H H G 对任意的H1 H2 L G H1 H2是G 的子群 是由 H1 H2生成的子群 即包含着H1 H2的最小子群 在L G 上定义包含关系 则L G 关于包含关系构成一个 格 称为G的子群格 在 L G 中 H1 H2 就是 H1 H2 H1 H2 就是 4 格的性质 对偶原理 定义11 2 设 f 是含有格中元素以及符号 和 的命题 令 f 是将 f 中的 替换成 替换成

3、替换成 替换成 所得到的命题 称 f 为 f 的对偶命题 例如 在格中令 f 是 a b c c f 是 a b c c 格的对偶原理 设 f 是含有格中元素以及符号 和 等的命题 若 f 对 一切格为真 则 f 的对偶命题 f 也对一切格为真 例如 如果对一切格L都有 a b L a b a 那么对一切格L 都有 a b L a b a l 注意 对偶是相互的 即 f f 5 格的性质 算律 定理11 1 设是格 则运算 和 适合交换律 结合律 幂等律和吸收律 即 1 a b L 有 a b b a a b b a 2 a b c L 有 a b c a b c a b c a b c 3

4、a L 有 a a a a a a 4 a b L 有 a a b a a a b a 6 证明 1 a b是 a b 的最小上界 b a是 b a 的最小上界 由于 a b b a 所以 a b b a 由对偶原理 a b b a 2 由最小上界的定义有 a b c a b a 1 a b c a b b 2 a b c c 3 由式 2 和 3 有 a b c b c 4 由式 1 和 4 有 a b c a b c 同理可证 a b c a b c 根据反对称性 a b c a b c 由对偶原理 a b c a b c 7 证明 3 显然 a a a 又由 a a 可得 a a a 根

5、据反对称性有 a a a 由对偶原理 a a a 得证 4 显然 a a b a 5 由 a a a b a 可得 a a b a 6 由式 5 和 6 可得 a a b a 根据对偶原理 a a b a 8 格的性质 序与运算的关系 定理11 2 设L是格 则 a b L有 a b a b a a b b 证 1 先证 a b a b a 由 a a 和 a b 可知 a 是 a b 的下界 故 a a b 显然有a b a 由反对称性得 a b a 2 再证 a b a a b b 根据吸收律有 b b b a 由 a b a 和上面的等式得 b b a 即 a b b 3 最后证 a b

6、 b a b 由 a a b 得 a a b b 9 格的性质 保序 定理11 3 设L是格 a b c d L 若a b 且 c d 则 a c b d a c b d 例4 设L是格 证明 a b c L有 a b c a b a c 证 a c a b a c c d 因此 a c b d 同理可证 a c b d 证 由 a a b c b 得 a b c a b 由 a a b c c 得 a b c a c 从而得到 a b c a b a c 注意 一般说来 格中的 和 运算不满足分配律 10 格作为代数系统的定义 定理11 4 设是具有两个二元运算的代数系统 若对于 和 运算适

7、合交换律 结合律 吸收律 则可以适当定义S中 的偏序 使得 构成格 且 a b S 有 a b a b a b a b 证明省略 根据定理11 4 可以给出格的另一个等价定义 定义11 3 设是代数系统 和 是二元运算 如果 和 满足交换律 结合律和吸收律 则构成格 11 子格及其判别法 定义11 4 设是格 S是L的非空子集 若S关于L中 的运算 和 仍构成格 则称S是L的子格 例5 设格L如图所示 令 S1 a e f g S2 a b e g S1不是L的子格 因为e f S1 但 e f c S1 S2是L的子格 12 11 2 分配格 有补格与布尔代数 定义11 5 设是格 若 a

8、b c L 有 a b c a b a c a b c a b a c 则称L为分配格 l 注意 可以证明以上两个条件互为充分必要条件 L1 和 L2 是分配格 L3 和 L4不是分配格 称 L3为钻石格 L4为五角格 实例 13 分配格的判别及性质 定理11 5 设L是格 则L是分配格当且仅当L不含有与钻石格 或五角格同构的子格 证明省略 推论 1 小于五元的格都是分配格 2 任何一条链都是分配格 例6 说明图中的格是否为分配格 为什么 解 都不是分配格 a b c d e 是L1的子格 同构于钻石格 a b c e f 是L2的子格 同构于五角格 a c b e f 是L3的子格 同构于钻

9、石格 14 有界格的定义 定义11 6 设L是格 1 若存在a L使得 x L有 a x 则称a为L的全下界 2 若存在b L使得 x L有 x b 则称b为L的全上界 说明 l 格L若存在全下界或全上界 一定是惟一的 l 一般将格L的全下界记为0 全上界记为1 定义11 7 设L是格 若L存在全下界和全上界 则称L 为有界 格 一般将有界格L记为 15 定理11 6 设是有界格 则 a L有 a 0 0 a 0 a a 1 a a 1 1 注意 l 有限格L a1 a2 an 是有界格 a1 a2 an是L的全下 界 a1 a2 an是L的全上界 l 0是关于 运算的零元 运算的单位元 1是

10、关于 运算的 零元 运算的单位元 l 对于涉及到有界格的命题 如果其中含有全下界0或全上界 1 在求该命题的对偶命题时 必须将0替换成1 而将1替换 成0 有界格的性质 16 有界格中的补元及实例 定义11 8 设是有界格 a L 若存在b L 使得 a b 0 和 a b 1 成立 则称b是a的补元 l 注意 若b是a的补元 那么a也是b的补元 a和b互为补元 例7 考虑下图中的格 针对不同的元素 求出所有的补元 17 解答 1 L1中 a 与 c 互为补元 其中 a 为全下界 c为全上界 b 没有 补元 2 L2中 a 与 d 互为补元 其中 a 为全下界 d 为全上界 b与 c 也互为补

11、元 3 L3中a 与 e 互为补元 其中 a 为全下界 e 为全上界 b 的补 元是 c 和 d c 的补元是 b 和 d d 的补元是 b 和 c b c d 每个元素都有两个补元 4 L4中 a 与 e 互为补元 其中 a 为全下界 e 为全上界 b 的补 元是 c 和 d c 的补元是 b d 的补元是 b 18 有界分配格的补元惟一性 定理11 7 设是有界分配格 若L中元素 a 存在 补元 则存在惟一的补元 证 假设 c 是 a 的补元 则有 a c 1 a c 0 又知 b 是 a 的补元 故 a b 1 a b 0 从而得到 a c a b a c a b 由于L是分配格 b c

12、 注意 l 在任何有界格中 全下界0与全上界1互补 l 对于一般元素 可能存在补元 也可能不存在补元 如果存 在补元 可能是惟一的 也可能是多个补元 对于有界分配 格 如果元素存在补元 一定是惟一的 19 图9 有补格的定义 定义11 9 设是有界格 若L中所有元素都有补 元存在 则称L为有补格 例如 图中的L2 L3和L4是有补格 L1不是有补格 20 布尔代数的定义与实例 定义11 10 如果一个格是有补分配格 则称它为布尔格或布 尔代数 布尔代数标记为 为求补运算 例8 设 S110 1 2 5 10 11 22 55 110 是110的正因子集合 gcd表示求最大公约数的运算 lcm表

13、示求最小公倍数的运 算 问是否构成布尔代数 为什么 解 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互为补元 从而证明了为布尔代数 21 实例 例9 设B为任意集合 证明B的幂集格 构成布尔代数 称为集合代数 证 1 P B 关于 和 构成格 因为 和 运算满足交换律 结合律和吸收律 2 由于 和 互相可分配 因此P B 是分配格 3 全下界

14、是空集 全上界是B 4 根据绝对补的定义 取全集为B x P B x是x的补元 从而证明P B 是有补分配格 即布尔代数 22 布尔代数的性质 定理11 8 设是布尔代数 则 1 a B a a 2 a b B a b a b a b a b 德摩根律 证 1 a 是a 的补元 a也是a 的补元 由补元惟一性得 a a 2 对任意a b B有 a b a b a a b b a b 1 b a 1 1 1 1 a b a b a b a a b b 0 b a 0 0 0 0 a b 是a b的补元 根据补元惟一性有 a b a b 同理 可证 a b a b l 注意 德摩根律对有限个元素也

15、是正确的 23 布尔代数作为代数系统的定义 定义11 11 设是代数系统 和 是二元运算 若 和 运 算满足 1 交换律 即 a b B有 a b b a a b b a 2 分配律 即 a b c B有 a b c a b a c a b c a b a c 3 同一律 即存在0 1 B 使得 a B有a 1 a a 0 a 4 补元律 即 a B 存在 a B 使得 a a 0 a a 1 则称 是一个布尔代数 可以证明 布尔代数的两种定义是等价的 24 有限布尔代数的结构 定义11 12 设 L 是格 0 L 若 b L有 0 b a b a 则 称 a 是 L 中的原子 实例 1 L是

16、正整数 n 的全体正因子关于整除关系构成的 格 则L的原子恰为n的全体素因子 2 若L是B的幂集 则L的原子就是B中元素构成的单元集 3 图中L1的原子是a L2的原子是a b c L3的原子是a 和 b 25 有限布尔代数的表示定理 定理11 9 有限布尔代数的表示定理 设B是有限布尔代数 A是B的全体原子构成的集合 则B同构 于A的幂集代数P A 实例 1 S110关于gcd lcm运算构成的布尔代数 它的原子是 2 5和11 因此原子的集合A 2 5 11 幂集 P A 2 5 11 2 5 2 11 5 11 2 5 11 幂集代数是 只要令 f S110 P A f 1 f 2 2 f 5 5 f 11 11 f 10 2 5 f 22 2 11 f 55 5 11 f 110 A 那么 f 就是从S110到幂集P A 的同构映射 26 推论 推论1 任何有限布尔代数的基数为2n n N 证 设B是有限布尔代数 A是B的所有原子构成的集合 且 A n n N 由定理得 B P A 而 P A 2n 所以 B 2n 推论2 任何等势的有限布尔代数都是同构的 证明省略 结论 l