1、第十一章 格与布尔代数主要内容l 格的定义及性质 l 子格l 分配格、有补格l 布尔代数111.1 格的定义与性质 定义 11.1 设 是偏序集，如果 x,yS， x,y都有最小上界和最大下界，则称 S关于偏序 作成一个 格 . （偏序关系P126）求 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
2、) ，其中 P(B)是集合 B的幂集 .(2) ，其中 Z是整数集， 为小于或等于关系 .(3) 偏序集的哈斯图分别在下图给出 . 实例 (1) 幂集格 . x,y P(B)， x y就是 x y， x y就是 xy. (2) 是格 . x,y Z， x y = max(x,y)， x y = min(x,y)，(3) 都不是格 . 可以找到两个结点缺少最大下界或最小上界 3格的性质：算律定理 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
3、), (a b) c = a (b c)(3) a L 有 a a = a, a a = a(4) a,b L 有 a (a b) = a, a (a b) = a 4格的性质：序与运算的关系定理 11.3 设 L是格 , 则 a,b L有 a b a b = a a b = b可以用集合的例子来验证 幂集格，其中 P(B)是集合 B的幂集 .幂集格 . x,y P(B)， x y就是 x y， x y就是 xy.5格的性质：保序定理 11.4 设 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
4、 (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) （注意最大下界）注意：一般说来 , 格中的 和 运算不满足分配律 . 6格作为代数系统的定义定理 11.4 设 是具有两个二元运算的代数系统 , 若对于和 运算适合交换律、结合律、吸收律 , 则可以适当定义 S中的偏序 ,使得 构成格 , 且 a,b S 有a b = ab, a b = ab.证明省略 . 根据定
5、理 11.4, 可以给出格的另一个等价定义 . 定义 11.3 设 是代数系统 , 和 是二元运算 , 如果和 满足交换律、结合律和吸收律 , 则 构成格 .711.2 分配格、有补格与布尔代数 定义 11.5 设 是格 , 若 a,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为 五角格 .实例8有界格的定义定义 11.6 设 L是格 ,(1) 若存在 a L使得 x L有 a x
6、, 则称 a为 L的 全下界(2) 若存在 b L使得 x L有 x b, 则称 b为 L的 全上界 说明：l 格 L若存在全下界或全上界 , 一定是惟一的 . l 一般将格 L的全下界记为 0, 全上界记为 1.定义 11.7 设 L是格 ,若 L存在全下界和全上界 , 则称 L 为 有界格 , 一般将有界格 L记为 .9定理 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
