离散数学格与布尔代数.ppt

第11章格与布尔代数 离散数学 中国地质大学本科生课程 本章内容 11 1格的定义与性质11 2分配格 有补格与布尔代数本章总结作业 11 1格的定义与性质 定义11 1设是偏序集 如果 x y S x y 都有最小上界和最大下界 则称S关于偏序 作成一个格 lattice 说明 由于最小上界和最大下界的唯一性 可以把求 x y 的最小上界和最大下界看成x与y的二元运算 和 x y 表示x与y的最小上界x y 表示x和y的最大下界 本章出现的 和 符号只代表格中的运算 而不再有其它的含义 格的实例 例11 1设n是正整数 Sn是n的正因子的集合 D为整除关系 则偏序集构成格 x y Sn x y是lcm x y 即x与y的最小公倍数 x y是gcd x y 即x与y的最大公约数 下图给出了格 和 例11 2 例11 2判断下列偏序集是否构成格 并说明理由 1 其中P B 是集合B的幂集 2 其中Z是整数集 为小于或等于关系 3 偏序集的哈斯图分别在下图给出 例11 2 解答 1 是格 x y P B x y就是x y x y就是x y 由于 和 运算在P B 上是封闭的 所以x y x y P B 称 为B的幂集格 2 是格 x y Z x y max x y x y min x y 它们都是整数 3 都不是格 a 中的 a b 没有最大下界 b 中的 b d 有两个上界c和e 但没有最小上界 c 中的 b c 有三个上界d e f 但没有最小上界 d 中的 a g 没有最大下界 例11 3 例11 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就是 对偶原理 定义11 2设f是含有格中元素以及符号 和 的命题 令f 是将f中的 替换成 替换成 替换成 替换成 所得到的命题 称f 为f的对偶命题 例如在格中令f是 a b c c 则f 是 a b c c 格的对偶原理设f是含有格中元素以及符号 和 的命题 若f对一切格为真 则f的对偶命题f 也对一切格为真 例如对一切格L都有 a b L a b a 因为a和b的交是a的一个下界 那么对一切格L都有 a b L a b a说明许多格的性质都是互为对偶命题的 有了格的对偶原理 在证明格的性质时 只须证明其中的一个命题即可 格的运算性质 定理11 1设是格 则运算 和 适合交换律 结合律 幂等律和吸收律 即 1 交换律 a b L有a b b aa b b a 2 结合律 a b c L有 a b c a b c a b c a b c 3 幂等律 a L有a a aa a a 4 吸收律 a b L有a a b aa a b a 定理11 1 1 a b和b a分别是 a b 和 b a 的最小上界 由于 a b b a 所以a b b a 由对偶原理 a b b a得证 2 由最小上界的定义有 a b c a b a 13 1 a b c a b b 13 2 a b c c 13 3 由式13 2和13 3有 a b c b c 13 4 再由式13 1和13 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 得证 定理11 1 3 显然a a a 又由a a可得a a a 根据反对称性有a a a 由对偶原理 a a a得证 4 显然a a b a 13 5 又由a a a b a可得a a b a 13 6 由式13 5和13 6可得a a b a 根据对偶原理 a a b a得证 定理11 2 定理11 2设是具有两个二元运算的代数系统 若对于 和 运算适合交换律 结合律 吸收律 则可以适当定义S中的偏序 使得构成一个格 且a b S有a b a b a b a b 思路 1 证明在S中 和 运算都适合幂等律 2 在S上定义二元关系R 并证明R为偏序关系 3 证明构成格 说明通过规定运算及其基本性质可以给出格的定义 定理11 2 a S 由吸收律得 1 证明在S中 和 运算都适合幂等律 a a a a a a a 同理有a a a 2 在S上定义二元关系R a b S有 R a b b 下面证明R在S上的偏序 根据幂等律 a S都有a a a 即 R 所以R在S上是自反的 a b S有 aRb且bRa a b b且b a a a b a a b b 由于a b b a 所以R在S上是反对称的 定理11 2 a b c S有aRb且bRc a b b且b c c a c a b c a c a b c a c b c c aRc这就证明了R在S上是传递的 综上所述 R为S上的偏序 以下把R记作 定理11 2 3 证明构成格 即证明a b a b a b a b a b S有 a a b a a b a b b a b a b b a b 根据 的定义有a a b和b a b 所以a b是 a b 的上界 假设c为 a b 的上界 则有a c c和b c c 从而有 a b c a b c a c c 这就证明了a b c 所以a b是 a b 的最小上界 即 a b a b 为证a b是 a b 的最大下界 先证 首先由a b b可知 a b a a b a 反之由a b a可知 a b a b b b b a b 再由式 13 7 和 的定义有a b a b a 依照前边的证明 类似地可证a b是 a b 的最大下界 即a b a b a b b a b a 13 7 格的等价定义 根据定理11 2 可以给出格的另一个等价定义 定义11 3设是代数系统 和 是二元运算 如果 和 满足交换律 结合律和吸收律 则构成一个格 lattice 说明格中的幂等律可以由吸收律推出 以后我们不再区别是偏序集定义的格 还是代数系统定义的格 而统称为格L 格的性质 定理11 3设L是格 则 a b L有a b a b a a b b证明先证a b a b a由a a和a b可知 a是 a b 的下界 故a a b 显然又有a b a 由反对称性得a b a 再证a b a a b b 根据吸收律有b b b a 由a b a得b b a 即a b b 最后证a b b a b 由a a b得a a b b 格的性质 定理11 4设L是格 a b c d L 若a b且c d 则a c b d a c b d证明a c a ba c c d因此 a c b d 同理可证a c b d 例11 5 例11 5设L是格 证明 a b c L有a b c a b a c 证明由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 说明在格中分配不等式成立 一般说来 格中的 和 运算并不是满足分配律的 本节小结 偏序集构成格的条件 任意二元子集都有最大下界和最小上界 格的实例 正整数的因子格 幂集格 子群格 格的性质 对偶原理 格中算律 交换 结合 幂等 吸收 保序性 分配不等式 格作为代数系统的定义 格的证明方法 子格 定义11 4设是格 S是L的非空子集 若S关于L中的运算 和 仍构成格 则称S是L的子格 例11 6设格L如右图所示 令 S1 a e f g S2 a b e g 则S1不是L的子格 S2是L的子格 因为对于e和f 有e f c 但c S1 11 2分配格 有补格与布尔代数 一般说来 格中运算 对 满足分配不等式 即 a b c L 有a b c a b a c 但是不一定满足分配律 满足分配律的格称为分配格 定义11 5设是格 若 a b c L 有a b c a b a c a b c a b a c 则称L为分配格 说明上面两个等式互为对偶式 在证明L为分配格时 只须证明其中的一个等式即可 例11 7 L1和L2是分配格 L3和L4不是分配格 在L3中 b c d b e b b c b d a a a 在L4中 c b d c a c c b c d e d d 钻石格 五角格 分配格的判别 定理11 5设L是格 则L是分配格当且仅当L中不含有与钻石格或五角格同构的子格 证明略 推论 1 小于五元的格都是分配格 2 任何一条链都是分配格 例11 8 说明下图中的格是否为分配格 为什么 L1 L2和L3都不是分配格 a b c d e 是L1的子格 并且同构于钻石格 a b c e f 是L2的子格 并且同构于五角格 a c b e f 是L3的子格 也同构于钻石格 格的全下界和全上界 定义11 6设L是格 若存在a L使得 x L有a x 则称a为L的全下界 若存在b L使得 x L有x b 则称b为L的全上界 命题格L若存在全下界或全上界 一定是唯一的 证明以全下界为例 假若a1和a2都是格L的全下界 则有a1 a2和a2 a1 根据偏序关系的反对称性必有a1 a2 记法将格L的全下界记为0 全上界记为1 有界格 定义11 7设L是格 若L存在全下界和全上界 则称L为有界格 并将L记为 说明有限格L一定是有界格 举例设L是n元格 且L a1 a2 an 那么a1 a2 an是L的全下界 而a1 a2 an是L的全上界 因此L是有界格 对于无限格L来说 有的是有界格 有的不是有界格 如集合B的幂集格 不管B是有穷集还是无穷集 它都是有界格 它的全下界是空集 全上界是B 整数集Z关于通常数的小于或等于关系构成的格不是有界格 因为不存在最小和最大的整数 有界格的性质 定理 补充 设是有界格 则 a L有a 0 0a 0 aa 1 aa 1 1证明由a 0 0和0 a 0可知a 0 0 说明在有界格中 全下界0是关于 运算的零元 运算的单位元 全上界1是关于 运算的零元 运算的单位元 对偶原理对于涉及到有界格的命题 如果其中含有全下界0或全上界1 在求该命题的对偶命题时 必须将0替换成1 而将1替换成0 例如a 0 0和a 1 1互为对偶命题 a 0 a和a 1 a互为对偶命题 有界格中的补元 定义11 8设是有界格 a L 若存在b L使得a b 0和a b 1成立 则称b是a的补元 说明若b是a的补元 那么a也是b的补元 换句话说 a和b互为补元 例11 9 考虑下图中的四个格 L1中的a与c互为补元 其中a为全下界 c为全上界 b没有补元 L2中的a与d互为补元 其中a为全下界 d为全上界 b与c也互为补元 L3中的a与e互为补元 其中a为全下界 e为全上界 b的补元是c和d c的补元是b和d d的补元是b和c b c d每个元素都有两个补元 L4中的a与e互为补元 其中a为全下界 e为全上界 b的补元是c和d c的补元是b d的补元是b 有界格中补元的说明 在任何有界格中 全下界0与全上界1互补 对于其他元素 可能存在补元 也可能不存在补元 如果存在 可能是唯一的 也可能是多个补元 对于有界分配格 如果它的元素存在补元 一定是唯一的 有界分配格中补元的唯一性 定理11 6设是有界分配格 若a L 且对于a存在补元b 则b是a的唯一补元 证明假设c L也是a的补元 则有a c 1 a c 0又知b是a的补元 故a b 1 a b 0 从而得到a c a b a c a b由于L是分配格 根据定理13 7 b c 有补格的定义 定义11 9设是有界格 若L中所有元素都有补元存在 则称L为有补格 L2 L3和L4是有补格 L1不是有补格 L2和L3是有补格 L1不是有补格 本节小结 如果格中一个运算对另一个运算是可分配的 称这个格是分配格 分配格的两种判别法 不存在与钻石格或五角格同构的子格 对于任意元素a b c 有a b a c且a b a c b c 有界格的定义及其实例 格中元素的补元及其性质 分配格中补元的唯一性 有补格的定义 布尔代数 定义11 10如果一个格是有补分配格 则称它为布尔格或布尔代数 说明在布尔代数中 每个元素都存在着唯一的补元 可以把求补元的运算看作是布尔代数中的一元运算 可以把一个布尔代数标记为 为求补运算 a B a 是a的补元 例11 10 例11 10设S110 1 2 5 10 11 22 55 110 是110的正因子集合 令gcd lcm分别表示求最大公约数和最小公倍数的运算 问是否构成布尔代数 为什么 解答证明构成格 容易验证 x y z S110 有gcd x y S110lcm x y S110gcd x y gcd y x lcm x y lcm y x gcd gcd x y z gcd x gcd y z lcm lcm x y z lcm x lcm y z gcd x lcm x y xlcm x gcd x y x 二元运算 交换律 结合律 吸收律 例11 10 证明是分配格 易验证 x y z S110有gcd x lcm y z lcm gcd x y gcd x z 证明是有补格 1为S110中的全下界110为S110中的全上界1和110互为补元 2和55互为补元 5和22互为补元 10和11互为补元 综上所述 为布尔代数 例11 10 2 例11 10 2 设B为任意集合 证明B的幂集格构成布尔代数 称为集合代数 证明P B 关于 和 构成格 因为 和 运算满足交换律 结合律和吸收律 由于 和 互相可分配 因此P B 是分配格 且全下界是空集 全上界是B 根据绝对补的定义 取全集为B x P B x是x的补元 从而证明P B 是有补分配格 即布尔代数 布尔代数的性质 定理11 7设是布尔代数 则 1 a B a a 2 a b B a b a b a b a b 说明 1 称为双重否定律 2 称为德摩根律 命题代数与集合代数的双重否定律与德摩根律实际上是这个定理的特例 可以证明德摩根律对有限个元素也是正确的 证明 1 a 是a 的补元 a也是a 的补元 由补元的唯一性得 a a 定理11 7 2 的证明 2 a b B a b a b a b a 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 布尔代数作为代数系统的定义 定义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则称是一个布尔代数 关于布尔代数定义的说明 所谓同一律就是指运算含有单位元的性质 这里的1是 运算的单位元 0是运算 的单位元 可以证明1和0分别也是 和 运算的零元 a B有a 1 a 1 1 同一律 1 a 1 交换律 a a a 1 补元律 a a 1 分配律 a a 同一律 1 补元律 同理可证a 0 0 关于布尔代数定义的说明 为证明以上定义的是布尔代数 只需证明它是一个格 即证明 和 运算满足结合律和吸收律 证明吸收律 a b B有a a b a 1 a b 同一律 a 1 b 分配律 a 1 1是 运算的零元 a 同一律 同理有a a b a 关于布尔代数定义的说明 为证结合律 先证以下命题 a b c B a b a c且a b a c b c由a b a c且a b a c可得 a b a b a c a c 由分配律和交换律得 a a b a a c由补元律得0 b 0 c由同一律和交换律得b c 关于布尔代数定义的说明 使用这个命题 为证明 a b c a b c 只需证明以下两个等式 1 a a b c a a b c 2 a a b c a a b c 先证明第一个等式 由吸收律有a a b c aa a b c a a b a c 分配律 a a c 吸收律 a所以 1 式成立 关于布尔代数定义的说明 下面证明 2 式 a a b c a a b c a a b c a a a b c 分配律 1 a b c 交换律 补元律 a b c 交换律 同一律 a a b c a a b a c 分配律 a a a b a c 分配律 1 a b a c 交换律 补元律 a b a c 交换律 同一律 a b c 分配律 所以 2 式成立 有限布尔代数的结构 定义11 12设L是格 0 L a L 若 b L有0 b a b a则称a是L中的原子 考虑右图中的几个格 L1的原子是a L2的原子是a b c L3的原子是a和b 若L是正整数n的全体正因子关于整除关系构成的格 则L的原子恰为n的全体质因子 若L是集合B的幂集合 则L的原子就是由B中元素构成的单元集 有限布尔代数的表示定理 定理11 8 有限布尔代数的表示定理 设B是有限布尔代数 A是B的全体原子构成的集合 则B同构于A的幂集代数P A 证明任取x B 令T x a a B a是原子且a x 则T x A 定义函数 B P A x T x x B下面证明 是B到P A 的同构映射 任取x y B b有b T x y b A且b x y b A且b x 且 b A且b y b T x 且b T y b T x T y 从而有T x y T x T y 即 x y B有 x y x y 定理11 8证明 任取x y B 设x a1 a2 an y b1 b2 bm是x y的原子表示 则x y a1 a2 an b1 b2 bm由引理2可知T x y a1 a2 an b1 b2 bm 又由于T x a1 a2 an T y b1 b2 bm 所以T x y T x T y 即 x y x y 定理11 8证明 任取x B 存在x B使得x x 1 x x 0因此有 x x x x 1 A x x x x 0 而 和A分别为P A 的全下界和全上界 因此 x 是 x 在P A 中的补元 即 x x 综上所述 是B到P A 的同态映射 定理11 8证明 下面证明 为双射 假设 x y 则有T x T y a1 a2 an 由引理2可知x a1 a2 an y于是 为单射 任取 b1 b2 bm P A 令x b1 b2 bm 则 x T x b1 b2 bm 于是 为满射 定理得证 例子 考虑110的正因子的集合S110关于gcd lcm运算构成的布尔代数 它的原子是2 5和11 因此原子的集合A 2 5 11 幂集P A 2 5 11 2 5 2 11 5 11 2 5 11 幂集代数是 只要令 S110 P A 1 2 2 5 5 11 11 10 2 5 22 2 11 55 5 11 110 A 那么f就是定理13 11中从S110到幂集P A 的同构映射 推论1 推论1任何有限布尔代数的基数为2n n N 证明设B是有限布尔代数 A是B的所有原子构成的集合 且 A n n N