《离散格与布尔代数》由会员分享，可在线阅读，更多相关《离散格与布尔代数（20页珍藏版）》请在金锄头文库上搜索。
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,ySn，xy是lcm(x,y)，即x与y 的 最小公倍数. xy是gcd(x,y)，即x与y的最大公约数. 2图2例2 判断下列偏序集是否构成格，并说明理由. (1) ，其中P(B)是集合B的幂集. (2)
2、，其中Z是整数集，为小于或等于关系. (3) 偏序集的哈斯图分别在下图给出. 实例 (1) 幂集格. x,yP(B)，xy就是xy，xy就是xy. (2) 是格. x,yZ，xy = max(x,y)，xy = min(x,y)， (3) 都不是格. 可以找到两个结点缺少最大下界或最小上界3格的性质：算律定理11.1 设是格, 则运算和适合交换律、结合律 、 幂等律和吸收律, 即 (1) a,bL 有 ab = ba, ab = ba (2) a,b,cL 有 (ab)c = a(bc), (ab)c = a(bc) (3) aL 有 aa = a, aa = a (4) a,bL 有 a(a
3、b) = a, a(ab) = a 4格的性质：序与运算的关系定理11.3 设L是格, 则a,bL有 a b ab = a ab = b可以用集合的例子来验证 幂集格 ，其中P(B)是集合B的幂集.幂集格. x,yP(B)，xy就是xy，xy就是xy.5格的性质：保序定理11.4 设L是格, a,b,c,dL，若a b 且 c d, 则 ac bd, ac bd例4 设L是格, 证明a,b,cL有 a(bc) (ab)(ac).证 ac a b, ac c d 因此 ac bd. 同理可证 ac bd 证 由 a a, bc b 得 a(bc) ab 由 a a, bc c 得 a(bc) a
4、c 从而得到 a(bc) (ab)(ac) （注意最大下界）注意：一般说来, 格中的和运算不满足分配律. 6格作为代数系统的定义定理11.4 设是具有两个二元运算的代数系统, 若对于 和运算适合交换律、结合律、吸收律, 则可以适当定义S中 的偏序 ,使得 构成格, 且a,bS 有ab = ab, ab = ab.证明省略. 根据定理11.4, 可以给出格的另一个等价定义. 定义11.3 设是代数系统, 和是二元运算, 如果 和满足交换律、结合律和吸收律, 则构成格.711.2 分配格、有补格与布尔代数 定义11.5 设是格, 若a,b,cL,有 a(bc) = (ab)(ac) a(bc) =
5、 (ab)(ac) 则称L为分配格.l 注意：可以证明以上两个条件互为充分必要条件L1 和 L2 是分配格, L3 和 L4不是分配格. 称 L3为钻石格, L4为五角格.实例8有界格的定义定义11.6 设L是格, (1) 若存在aL使得xL有 a x, 则称a为L的全下界 (2) 若存在bL使得xL有 x b, 则称b为L的全上界 说明： l 格L若存在全下界或全上界, 一定是惟一的. l 一般将格L的全下界记为0, 全上界记为1.定义11.7 设L是格,若L存在全下界和全上界, 则称L 为有界 格, 一般将有界格L记为.9定理11.6 设是有界格, 则aL有 a0 = 0, a0 = a,
6、 a1 = a, a1 = 1注意： l 有限格L=a1,a2,an是有界格, a1a2an是L的全下 界, a1a2an是L的全上界. l 0是关于运算的零元,运算的单位元；1是关于运算 的零元,运算的单位元. 有界格的性质10有界格中的补元及实例定义11.8 设是有界格, aL, 若存在bL 使得 ab = 0 和 ab = 1 成立, 则称b是a的补元.l 注意：若b是a的补元, 那么a也是b的补元. a和b互为补元. 例7 考虑下图中的格. 针对不同的元素，求出所有的补元.11解答(1) L1中 a 与 c 互为补元, 其中 a 为全下界, c为全上界, b 没 有补元. (2) L2
7、中 a 与 d 互为补元, 其中 a 为全下界, d 为全上界, b与 c 也互为补元. (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 . 12有界分配格的补元惟一性定理11.7 设是有界分配格. 若L中元素 a 存在 补元, 则存在惟一的补元. 证 假设 c 是 a 的补元, 则有 a
8、c = 1, ac = 0, 又知 b 是 a 的补元, 故 ab = 1, ab = 0 从而得到 ac = ab, ac = ab, 由于L是分配格. b=b (ba) = b (ca )= (b c) (b a )= (ac ) c=c 注意： l 在任何有界格中, 全下界0与全上界1互补. l 对于一般元素, 可能存在补元, 也可能不存在补元. 如果 存在补元, 可能是惟一的, 也可能是多个补元. 对于有界 分配格, 如果元素存在补元, 一定是惟一的.13图9有补格的定义定义11.9 设是有界格, 若L中所有元素都有补 元存在, 则称L为有补格. 例如, 图中的L2, L3和L4是有补
9、格, L1不是有补格. 14布尔代数的定义与实例定义11.10 如果一个格是有补分配格, 则称它为布尔格或布 尔代数. 布尔代数标记为, 为求补运算. 例8 设 S110 = 1, 2, 5, 10, 11, 22, 55, 110是110的正因子集合 ，gcd表示求最大公约数的运算，lcm表示求最小公倍数的运 算，问是否构成布尔代数？为什么？解 画出哈斯图？(1) 不难验证S110关于gcd 和 lcm 运算构成格. (略) (2) 验证分配律 x, y, zS110 有 gcd(x, lcm(y, z) = lcm(gcd(x, y), gcd(x, z) (3) 验证它是有补格, 1作为
10、S110中的全下界, 110为全上界, 1和110互为补元, 2和55互为补元, 5和22互为补元, 10和 11互为补元, 从而证明了为布尔代数. 15布尔代数的性质定理11.8 设是布尔代数, 则 (1) aB, (a) = a . (2) a,bB, (ab) = ab, (ab) = ab （德摩根律）证 (1) (a)是a的补元, a也是a的补元. 由补元惟一性得 (a)=a. (2) 对任意a, bB有 (ab)(ab) = (aab)(bab) = (1b)(a1) = 11 = 1, (ab)(ab) = (aba)(abb) = (0b)(a0) = 00 = 0 ab是ab
11、的补元, 根据补元惟一性有(ab) = ab, 同理 可证 (ab) = ab. l 注意：德摩根律对有限个元素也是正确的. 16图11实例下图给出了 1 元, 2 元, 4 元和 8 元的布尔代数. 17第十一章 习题课主要内容 l 格的两个等价定义 l 格的性质 l 子格 l 特殊格：分配格、有界格、有补格、布尔代数基本要求 l 能够判别给定偏序集或者代数系统是否构成格 l 能够确定一个命题的对偶命题 l 能够证明格中的等式和不等式 l 能判别格L的子集S是否构成子格 l 能够判别给定的格是否为分配格、有补格 l 能够判别布尔代数并证明布尔代数中的等式 18解1求图中格的所有子格.1元子格
12、： a , b , c , d , e ； 2元子格： a, b , a, c , a, d , a, e , b, c , b, d , b, e , c, e , d, e ； 3元子格： a, b, c , a, b, d , a, b, e , a, c, e , a, d, e , b, c, e , b, d, e ； 4元子格： a, b, c, e , a, b, d, e , b, c, d, e ； 5元子格： a, b, c, d, e 练习1eabcd19L1 L2 L3图122针对下图，求出每个格的补元并说明它们是否为有补格L1中, a与h互为补元, 其他元素没补元. L2中, a与g互为补元. b的补元为c, d, f；c的补元为b, d, e, f；d 的补元为b, c, e；e的补元为c, d, f；f的补元为b, c, e. L3中, a与h互为补元, b的补元为d；c的补元为d；d的补元为b, c, g；g的补元为d. L2与L3是有补格.练习220
