离散数学-课件-ch11汇编

1、 2 图2 例例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) 都不是格都不是格. 可以找到两个结点缺少最大下界或最小上界可以找到两个结点缺少最大下界或最小上界 3 实例：子群格实

2、例：子群格 例例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 就是就是 4 格的性质：对偶原理格的性质：对偶原理 定义定义11.2 设设 f 是含有格中元素以及符号是含

3、有格中元素以及符号 =, , ,和和的命的命 题题. 令令 f*是将是将 f 中的中的 替换成替换成 , 替换成替换成 ,替换成替换成,替换替换 成成 所得到的命题所得到的命题. 称称 f* 为为 f 的的对偶命题对偶命题. 例如例如, 在格中令在格中令 f 是是 (ab)c c, f*是是 (ab)c c . 格的格的对偶原理对偶原理 设设 f 是含有格中元素以及符号是含有格中元素以及符号=, , ,和和等的命题等的命题. 若若 f 对对 一切格为真一切格为真, 则则 f 的对偶命题的对偶命题 f*也对一切格为真也对一切格为真. 例如例如, 如果对一切格如果对一切格L都有都有 a,bL, a

4、b a，那么对一切格那么对一切格 L 都有都有 a,bL, ab a l 注意：对偶是相互的，即注意：对偶是相互的，即 ( f*)*= f 5 格的性质：算律格的性质：算律 定理定理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(ab) = a, a(ab) = a 6 证明证明 (1) ab是是 a,

5、 b 的最小上界的最小上界, ba是是 b, a 的最小上界的最小上界. 由于由于 a, b = b, a , 所以所以 ab = ba. 由对偶原理由对偶原理, ab = ba. (2) 由最小上界的定义有由最小上界的定义有 (ab)c ab a (1) (ab)c ab b (2) (ab)c c (3) 由式由式(2)和和(3)有有 (ab)c bc (4) 由式由式(1)和和(4)有有 (ab)c a(bc) 同理可证同理可证 (ab)c a(bc) 根据反对称性根据反对称性 (ab)c = a(bc) 由对偶原理由对偶原理, (ab)c = a(bc) 7 证明证明 (3) 显然显然

6、 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 8 格的性质：序与运算的关系格的性质：序与运算的关系 定理定理11.2 设设L是格是格, 则则 a,bL有有 a b ab = a ab = b 证证 (1) 先证先证 a b ab = a 由由 a a 和和 a b 可知可知 a 是是

7、a,b 的下界的下界, 故故 a ab. 显然有显然有ab a. 由反对称性得由反对称性得 ab = a. (2) 再证再证 ab = a ab = b 根据吸收律有根据吸收律有 b = b(ba) 由由 ab = a 和上面的等式得和上面的等式得 b = ba, 即即 ab = b. (3) 最后证最后证 ab = b a b 由由 a ab 得得 a ab = b 9 格的性质：保序格的性质：保序 定理定理11.3 设设L是格是格, a,b,c,dL，若若a b 且且 c d, 则则 ac bd, ac bd 例例4 设设L是格是格, 证明证明 a,b,cL有有 a(bc) (ab)(ac

8、). 证证 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) 注意：一般说来注意：一般说来, 格中的格中的和和运算不满足分配律运算不满足分配律. 10 格作为代数系统的定义格作为代数系统的定义 定理定理11.4 设设是具有两个二元运算的代数系统是具有两个二元运算的代数系统, 若对若对 于于 和和 运算适合交换律、结合律、吸收律运算适合交换律、结合律、吸收律, 则可以适当定义则可以适当定义S 中中 的偏序的偏序

9、,使得使得 构成格构成格, 且且 a,bS 有有 ab = a b, ab = a b. 证明省略证明省略. 根据定理根据定理11.4, 可以给出格的另一个等价定义可以给出格的另一个等价定义. 定义定义11.3 设设是代数系统是代数系统, 和和 是二元运算是二元运算, 如如 果果 和和 满足交换律、结合律和吸收律满足交换律、结合律和吸收律, 则则构成格构成格. 11 子格及其判别法子格及其判别法 定义定义11.4 设设是格是格, S是是L的非空子集的非空子集, 若若S关于关于L中中 的运算的运算和和仍构成格仍构成格, 则称则称S是是L的的子格子格. 例例5 设格设格L如图所示如图所示. 令令

10、S1=a, e, f, g, S2=a, b, e, g S1不是不是L的子格的子格, 因为因为e, f S1 但但 ef = c S1. S2是是L的子格的子格. 12 11.2 分配格、有补格与布尔代数分配格、有补格与布尔代数 定义定义11.5 设设是格是格, 若若 a,b,cL,有有 a(bc) = (ab)(ac) a(bc) = (ab)(ac) 则称则称L为为分配格分配格. l 注意：可以证明以上两个条件互为充分必要条件注意：可以证明以上两个条件互为充分必要条件 L1 和和 L2 是分配格是分配格, L3 和和 L4不是分配格不是分配格. 称称 L3为为钻石格钻石格, L4为为五角

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

12、格； a,c,b,e,f 是是L3的子格的子格 同构于钻石格同构于钻石格. 14 有界格的定义有界格的定义 定义定义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 为为有界有界

13、格格, 一般将有界格一般将有界格L记为记为. 15 定理定理11.6 设设是有界格是有界格, 则则 aL有有 a0 = 0, a0 = a, a1 = a, a1 = 1 注意：注意： l 有限格有限格L=a1,a2,an是有界格是有界格, a1a2an是是L的全下的全下 界界, a1a2an是是L的全上界的全上界. l 0是关于是关于运算的零元运算的零元,运算的单位元；运算的单位元；1是关于是关于运算的运算的 零元零元,运算的单位元运算的单位元. l 对于涉及到有界格的命题对于涉及到有界格的命题, 如果其中含有全下界如果其中含有全下界0或全上界或全上界 1, 在求该命题的对偶命题时在求该命题

14、的对偶命题时, 必须将必须将0替换成替换成1, 而将而将1替换替换 成成0. 有界格的性质有界格的性质 16 有界格中的补元及实例有界格中的补元及实例 定义定义11.8 设设是有界格是有界格, aL, 若存在若存在bL 使得使得 ab = 0 和和 ab = 1 成立成立, 则称则称b是是a的的补元补元. l 注意：若注意：若b是是a的补元的补元, 那么那么a也是也是b的补元的补元. a和和b互为补元互为补元. 例例7 考虑下图中的格考虑下图中的格. 针对不同的元素，求出所有的补元针对不同的元素，求出所有的补元. 17 解答解答 (1) L1中中 a 与与 c 互为补元互为补元, 其中其中 a

15、 为全下界为全下界, 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 为全

16、上界为全上界, b 的补的补 元是元是 c 和和 d ; c 的补元是的补元是 b ; d 的补元是的补元是 b . 18 有界分配格的补元惟一性有界分配格的补元惟一性 定理定理11.7 设设是有界分配格是有界分配格. 若若L中元素中元素 a 存在存在 补元补元, 则存在惟一的补元则存在惟一的补元. 证证 假设假设 c 是是 a 的补元的补元, 则有则有 ac = 1, ac = 0, 又知又知 b 是是 a 的补元的补元, 故故 ab = 1, ab = 0 从而得到从而得到 ac = ab, ac = ab, 由于由于L是分配格是分配格, b = c. 注意：注意： l 在任何有界格中在任

17、何有界格中, 全下界全下界0与全上界与全上界1互补互补. l 对于一般元素对于一般元素, 可能存在补元可能存在补元, 也可能不存在补元也可能不存在补元. 如果如果 存在补元存在补元, 可能是惟一的可能是惟一的, 也可能是多个补元也可能是多个补元. 对于有界对于有界 分配格分配格, 如果元素存在补元如果元素存在补元, 一定是惟一的一定是惟一的. 19 图9 有补格的定义有补格的定义 定义定义11.9 设设是有界格是有界格, 若若L中所有元素都有补中所有元素都有补 元存在元存在, 则称则称L为为有补格有补格. 例如例如, 图中的图中的L2, L3和和L4是有补格是有补格, L1不是有补格不是有补格

18、. 20 布尔代数的定义与实例布尔代数的定义与实例 定义定义11.10 如果一个格是有补分配格如果一个格是有补分配格, 则称它为布尔格或布则称它为布尔格或布 尔代数尔代数. 布尔代数标记为布尔代数标记为, 为求补运算为求补运算. 例例8 设设 S110 = 1, 2, 5, 10, 11, 22, 55, 110是是110的正因子集合，的正因子集合， gcd表示求最大公约数的运算，表示求最大公约数的运算，lcm表示求最小公倍数的运表示求最小公倍数的运 算，问算，问是否构成布尔代数？为什么？是否构成布尔代数？为什么？ 解解 (1) 不难验证不难验证S110关于关于gcd 和和 lcm 运算构成格

19、运算构成格. (略略) (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互为补元互为补元, 从而证明了从而证明了为布尔代数为布尔代数. 21 实例实例 例例9 设设B为任意集合为任意集合, 证明证明B的幂集格的幂集格 构成布尔代数构成布尔代数, 称为集合代数称为集合代数. 证证 (1)

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

21、, (ab) = a b （德摩根律）（德摩根律） 证证 (1) (a ) 是是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 = 0 a b 是是ab的补元的补元, 根据补元惟一性有根据补元惟一性有(ab) = a b , 同理同理 可证可证 (ab) = a b . l 注意：德摩根律对有限个元素也是正确的注意：德摩根律对有

22、限个元素也是正确的. 23 布尔代数作为代数系统的定义布尔代数作为代数系统的定义 定义定义11.11 设设是代数系统是代数系统, 和和 是二元运算是二元运算. 若若 和和 运运 算满足：算满足： (1) 交换律交换律, 即即 a,bB有有a b = b a, a b = b a (2) 分配律分配律, 即即 a,b,cB有有 a (b c) = (a b) (a c), a (b c) = (a b) (a c) (3) 同一律同一律, 即存在即存在0,1B, 使得使得 aB有有a 1 = a, a 0 = a (4) 补元律补元律, 即即 aB, 存在存在 a B 使得使得 a a = 0,

23、 a a = 1 则称则称 是一个布尔代数是一个布尔代数. 可以证明，布尔代数的两种定义是等价的可以证明，布尔代数的两种定义是等价的. 24 有限布尔代数的结构有限布尔代数的结构 定义定义11.12 设设 L 是格是格, 0L, 若若 bL有有 0 b a b = a, 则则 称称 a 是是 L 中的中的原子原子. 实例：实例：(1) L是正整数是正整数 n 的全体正因子关于整除关系构成的的全体正因子关于整除关系构成的 格格, 则则L的原子恰为的原子恰为n的全体素因子的全体素因子. (2) 若若L是是B的幂集的幂集, 则则L的原子就是的原子就是B中元素构成的单元集中元素构成的单元集 (3) 图

24、中图中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

25、,2,11,5,11,2,5,11. 幂集代数是幂集代数是. 只要令只要令 f: S110P(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, nN. 证证 设设B是有限布尔代数是有限布尔代数, A是是B的所有原子构成的集合的所有原子构成的集合, 且且 |A| = n, nN. 由定理得

26、由定理得 B P(A), 而而 |P(A)| = 2n, 所以所以 |B| = 2n. 推论推论2 任何等势的有限布尔代数都是同构的任何等势的有限布尔代数都是同构的. (证明省略证明省略) 结论结论 ： l 有限布尔代数的基数都是有限布尔代数的基数都是2的幂的幂, l 对于任何自然数对于任何自然数n, 仅存在一个仅存在一个2n元的布尔代数元的布尔代数. 27 图11 实例实例 下图给出了下图给出了 1 元元, 2 元元, 4 元和元和 8 元的布尔代数元的布尔代数. 28 第十一章第十一章 习题课习题课 主要内容主要内容 l 格的两个等价定义格的两个等价定义 l 格的性质格的性质 l 子格子格

27、 l 特殊格：分配格、有界格、有补格、布尔代数特殊格：分配格、有界格、有补格、布尔代数 基本要求基本要求 l 能够判别给定偏序集或者代数系统是否构成格能够判别给定偏序集或者代数系统是否构成格 l 能够确定一个命题的对偶命题能够确定一个命题的对偶命题 l 能够证明格中的等式和不等式能够证明格中的等式和不等式 l 能判别格能判别格L的子集的子集S是否构成子格是否构成子格 l 能够判别给定的格是否为分配格、有补格能够判别给定的格是否为分配格、有补格 l 能够判别布尔代数并证明布尔代数中的等式能够判别布尔代数并证明布尔代数中的等式 29 练习练习1 1(1) 证明格中的命题证明格中的命题, 即即 (a

28、b)b = b (2) 证明证明 (ab)(cd) (ac)(bd) (1) (ab)b是是ab与与b的最小上界的最小上界, 根据最小上界的定义根据最小上界的定义 有有(ab)b b . b是是ab与与b的上界的上界, 故有故有(ab)b b. 由由 于于 偏序的反对称性偏序的反对称性, 等式得证等式得证. (2) ab a ac, ab b bd, 所以所以 (ab) (ac)(bd), 同理同理 (cd) (ac)(bd). 从而得到从而得到 (ab)(cd) (ac)(bd) 30 解 2求图中格的所有子格求图中格的所有子格. 1元子格：元子格： 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,