第十一章格与布尔代数

1、1 11.1 格的定义及其性质格的定义及其性质 11.2 分配格分配格有补格与布尔代数有补格与布尔代数第十一章第十一章 格与布尔代数格与布尔代数2211.1 格的定义与性质 定义11.1 设是偏序集，如果x,yS，x,y都有最小上界和最大下界，则称S关于偏序 作成一个格. 求x,y 最小上界和最大下界看成 x 与 y 的二元运算和，例例11.1 设设n是正整数，是正整数，Sn是是n的正因子的集合的正因子的集合. D为整除关系，为整除关系，则偏序集则偏序集构成格构成格. x,ySn，xy是是lcm(x,y)，即，即x与与y的最小公倍数的最小公倍数. xy是是gcd(x,y)，即，即x与与y的最大

2、公约数的最大公约数. 33图2例例11.2 判断下列偏序集是否构成格，并说明理由判断下列偏序集是否构成格，并说明理由.(1) ，其中，其中P(B)是集合是集合B的幂集的幂集.(2) ，其中，其中Z是整数集，是整数集，为小于或等于关系为小于或等于关系.(3) 偏序集的哈斯图分别在下图给出偏序集的哈斯图分别在下图给出. (1) 幂集格幂集格. x,yP(B)，xy就是就是xy，xy就是就是xy. (2) 是格是格. x,yZ，xy = max(x,y)，xy = min(x,y)，(3) 都不是格都不是格. 可以找到两个结点缺少最大下界或最小上界可以找到两个结点缺少最大下界或最小上界44例11.3

3、 设G是群，L(G)是G 的所有子群的集合. 即L(G) = H | HG ，对任意的H1, H2L(G)，H1H2是G 的子群，是由H1H2生成的子群（即包含着H1H2的最小子群）.在L(G)上定义包含关系，则L(G)关于包含关系构成一个格，称为G的子群格. 在 L(G)中， H1H2 就是 H1H2 H1H2 就是 55定义11.2 设 f 是含有格中元素以及符号 =, , ,和的命题. 令 f*是将 f 中的 替换成 , 替换成 ,替换成,替换成所得到的命题. 称 f* 为 f 的对偶命题. 例如, 在格中令 f 是 (ab)cc, f*是 (ab)c c .格的格的对偶原理对偶原理 设

4、设 f f 是含有格中元素以及符号是含有格中元素以及符号=,=, , , ,和和等的命题等的命题. . 若若 f f 对对一切格为真一切格为真, , 则则 f f 的对偶命题的对偶命题 f f* *也对一切格为真也对一切格为真. . 例如例如, , 如果对一切格如果对一切格L L都有都有 a a, ,b bL L, , a ab b a a，那么对一切格那么对一切格L L都有都有 a a, ,b bL L, , a ab b a a l 注意：对偶是相互的，即注意：对偶是相互的，即 ( ( f f* *) )* *= = f f66定理11.1 设是格, 则运算和适合交换律、结合律、幂等律和吸

5、收律, 即(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(ab) = a, a(ab) = a 77证明(1) ab是 a, b 的最小上界, ba是 b, a 的最小上界. 由于 a, b = b, a , 所以 ab = ba. 由对偶原理, ab = ba. (2) 由最小上界的定义有 (ab)caba (1) (ab)cabb (2) (ab)cc (3)由式(2)和(3)有 (ab)cbc (4)由式(1)和(4)有 (ab)c

6、a(bc)同理可证 (ab)ca(bc) 根据反对称性 (ab)c = a(bc)由对偶原理, (ab)c = a(bc)88证明(3) 显然 a aa, 又由 a a 可得 aa a. 根据反对称性有aa = a . 由对偶原理, aa = a 得证. (4) 显然 a(ab) a (5) 由 a a, ab a 可得 a(ab) a (6) 由式(5)和(6) 可得 a(ab) = a, 根据对偶原理, a(ab) = a 99定理11.2 设是具有两个二元运算的代数系统, 若对于 和运算适合交换律、结合律、吸收律, 则可以适当定义S中的偏序 ,使得 构成格, 且a,bS 有 ab = a

7、b, ab = ab.证明省略. 根据定理11.4, 可以给出格的另一个等价定义.定义11.3 设是代数系统, 和是二元运算, 如果 和满足交换律、结合律和吸收律, 则构成格.1010定理11.3 设L是格, 则a,bL有a b ab = a ab = b证证 (1) (1) 先证先证 a a b b a ab b = = a a由由 a a a a 和和 a a b b 可知可知 a a 是是 a a, ,b b 的下界的下界, , 故故 a a a ab b. .显然有显然有a ab b a a. . 由反对称性得由反对称性得 a ab b = = a a. .(2) (2) 再证再证 a

8、 ab b = = a a a ab b = = b b根据吸收律有根据吸收律有 b b = = b b(b ba a) ) 由由 a ab b = = a a 和上面的等式得和上面的等式得 b b = = b ba a, , 即即 a ab b = = b b. .(3) (3) 最后证最后证 a ab b = = b b a a b b由由 a a a ab b 得得 a a a ab b = = b b 1111定理11.4 设L是格, a,b,c,dL，若a b 且 c d, 则 ac bd, ac bd例例11.5 设设L是格是格, 证明证明 a,b,cL有有 a(bc) (ab)(

9、ac).证证 ac a b, ac c d 因此因此 ac bd. 同理可证同理可证 ac bd 证证 由由 a a, bc b 得得 a(bc) ab由由 a a, bc c 得得 a(bc) ac从而得到从而得到a(bc) (ab)(ac)注意：一般说来注意：一般说来, 格中的格中的和和运算不满足分配律运算不满足分配律. 1212子格及其判别法定义定义11.411.4 设设 ,是格是格, , S S是是L L的非空子集的非空子集, , 若若S S关于关于L L中中的运算的运算和和仍构成格仍构成格, , 则称则称S S是是L L的的子格子格. . 例例11.611.6 设格设格L L如图所示

10、如图所示. . 令令 S S1 1=a a, , e e, , f f, , g g, , S S2 2=a a, , b b, , e e, , g g S S1 1不是不是L L的子格的子格, , 因为因为e e, , f f S S1 1 但但 e ef f = = c c S S1 1. .S S2 2是是L L的子格的子格. . 131311.2 11.2 分配格、有补格与布尔代数分配格、有补格与布尔代数 定义11.5 设是格, 若a,b,cL,有 a(bc) = (ab)(ac) a(bc) = (ab)(ac) 则称L为分配格.注意：可以证明以上两个条件互为充分必要条件L1 和和

11、 L2 是分配格是分配格, L3 和和 L4不是分配格不是分配格. 称称 L3为为钻石格钻石格, L4为为五角格五角格.例例11.71414分配格的判别及性质定理11.5 设L是格, 则L是分配格当且仅当L不含有与钻石格或五角格同构的子格.证明省略.推论 (1) 小于五元的格都是分配格.(2) 任何一条链都是分配格. 例11.8 说明图中的格是否为分配格, 为什么？解解 都不是分配格都不是分配格. a,b,c,d,e 是是L1的子格的子格, 同构于钻石格同构于钻石格 a,b,c,e,f 是是L2的子格的子格, 同构于五角格；同构于五角格； a,c,b,e,f 是是L3的子格的子格 同构于钻石格

12、同构于钻石格. 1515有界格定义11.6 设L是格,(1) 若存在aL使得xL有 a x, 则称a为L的全下界(2) 若存在bL使得xL有 x b, 则称b为L的全上界说明：格L若存在全下界或全上界, 一定是惟一的. 一般将格L的全下界记为0, 全上界记为1.定义11.7 设L是格,若L存在全下界和全上界, 则称L 为有界格, 一般将有界格L记为.1616有界格中的补元及实例定义11.8 设是有界格, aL, 若存在bL 使得 ab = 0 和 ab = 1 成立, 则称b是a的补元.注意：若b是a的补元, 那么a也是b的补元. a和b互为补元. 例例11.9 考虑下图中的格考虑下图中的格.

13、 针对不同的元素，求出所有的补元针对不同的元素，求出所有的补元.1717解答(1) L1中 a 与 c 互为补元, 其中 a 为全下界, c为全上界, b 没有 补元.(2) L2中 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

14、 ; d 的补元是 b . 1818有界分配格的补元惟一性定理11.6 设是有界分配格. 若L中元素 a 存在补元, 则存在惟一的补元.证 假设 c 是 a 的补元, 则有 ac = 1, ac = 0, 又知 b 是 a 的补元, 故 ab = 1, ab = 0 从而得到 ac = ab, ac = ab, 由于L是分配格, b = c. 注意：注意：l 在任何有界格中在任何有界格中, 全下界全下界0与全上界与全上界1互补互补.l 对于一般元素对于一般元素, 可能存在补元可能存在补元, 也可能不存在补元也可能不存在补元. 如果存在补元如果存在补元, 可能是惟可能是惟一的一的, 也可能是多个

15、补元也可能是多个补元. 对于有界分配格对于有界分配格, 如果元素存在补元如果元素存在补元, 一定是惟一一定是惟一的的.1919图9有补格的定义定义11.9 设是有界格, 若L中所有元素都有补元存在, 则称L为有补格. 例如, 图中的L2, L3和L4是有补格, L1不是有补格. 2020布尔代数的定义与实例定义11.10 如果一个格是有补分配格, 则称它为布尔格或布尔代数. 布尔代数标记为, 为求补运算. 例例11.10 (1)设设 S110 = 1, 2, 5, 10, 11, 22, 55, 110是是110的正因的正因子集合，子集合，gcd表示求最大公约数的运算，表示求最大公约数的运算，

16、lcm表示求最小公表示求最小公倍数的运算，问倍数的运算，问是否构成布尔代数？为什是否构成布尔代数？为什么？么？解解 (1) 不难验证不难验证S110关于关于gcd 和和 lcm 运算构成格运算构成格. (略略)(2) 验证分配律验证分配律 x, y, zS110 有有 gcd(x, lcm(y, z) = lcm(gcd(x, y), gcd(x, z) (3) 验证它是有补格验证它是有补格, 1作为作为S110中的全下界中的全下界, 110为全上界为全上界, 1和和110互为补元互为补元, 2和和55互为补元互为补元, 5和和22互为补元互为补元, 10和和 11互为补元互为补元, 从而证明

17、了从而证明了为布尔代数为布尔代数. 2121例11.10 (2) 设B为任意集合, 证明B的幂集格构成布尔代数, 称为集合代数.证 (1) P(B)关于和构成格, 因为和运算满足交换律, 结合律和吸收律. (2) 由于和互相可分配, 因此P(B)是分配格.(3) 全下界是空集, 全上界是B. (4) 根据绝对补的定义, 取全集为B, xP(B), x是x的补元. 从而证明P(B)是有补分配格, 即布尔代数. 2222布尔代数的性质定理11.7 设是布尔代数, 则(1) aB, (a) = a .(2) a,bB, (ab) = ab, (ab) = ab （德摩根律）证证 (1) (a ) 是

18、是a 的补元的补元, a也是也是a 的补元的补元. 由补元惟一性得由补元惟一性得(a ) =a. (2) 对任意对任意a, bB有有 (ab)(a b ) = (aa b )(ba b ) = (1b )(a 1) = 11 = 1, (ab)(a b ) = (aba )(abb ) = (0b)(a0) = 00 = 0a b 是是ab的补元的补元, 根据补元惟一性有根据补元惟一性有(ab) = a b , 同理同理可证可证 (ab) = a b . l 注意：德摩根律对有限个元素也是正确的注意：德摩根律对有限个元素也是正确的. 2323布尔代数作为代数系统的定义定义11.11 设是代数系

19、统, 和是二元运算. 若 和运算满足： (1) 交换律, 即a,bB有ab = ba, ab = ba (2) 分配律, 即a,b,cB有 a (bc) = (ab)(ac), a(bc) = (ab) (ac) (3) 同一律, 即存在0,1B, 使得aB有a 1 = a, a0 = a (4) 补元律, 即aB, 存在 aB 使得 a a = 0, aa = 1 则称 是一个布尔代数.可以证明，布尔代数的两种定义是等价的. 2424有限布尔代数的结构定义11.12 设 L 是格, 0L, 若bL有 0 b a b = a, 则称 a 是 L 中的原子. 实例：实例：(1)(1) L L是正

20、整数是正整数 n n 的全体正因子关于整除关系构成的的全体正因子关于整除关系构成的格格, , 则则L L的原子恰为的原子恰为n n的全体素因子的全体素因子. .(2) (2) 若若L L是是B B的幂集的幂集, , 则则L L的原子就是的原子就是B B中元素构成的单元集中元素构成的单元集 (3) (3) 图中图中L L1 1的原子是的原子是a a, , L L2 2的原子是的原子是a a, , b b, , c c, , L L3 3的原子是的原子是a a 和和 b b2525有限布尔代数的表示定理定理11.9 (有限布尔代数的表示定理) 设B是有限布尔代数, A是B的全体原子构成的集合, 则B同构于A的幂集代数P(A).实例实例: (1) : (1) S S110110关于关于gcd, lcmgcd, lcm运算构成的布尔代数运算构成的布尔代数. . 它的原子是它的原子