第6章 格与布尔代数

Chapter6格与布尔代数 格论 1935 是一种重要的代数结构 它是计算机语言的指称语义的理论基础 在计算机应用逻辑研究中有着重要作用 布尔代数是英国数学家GeorgeBoole在1847年左右在对逻辑思维法则进行研究时提出的 后来很多数学家特别是E V Hungtington和E H Stone对布尔代数的进行了一般化研究 在1938年C E Shannon发表的ASymbolicAnalysisofRelayandSwitchingCircuits论文 为布尔代数在工艺技术 中的应用开创了先河 自此以后布尔代数在自动推理和逻辑电路设计的分析和优化等问题的讨论中都有着最直接的应用 作为计算机设计基础的 数字逻辑 就是布尔代数 本章先介绍格 在此基础上引入分配格和有补格 而把布尔代数作为一种特殊的格加以讨论 6 1用偏序集定义的格 1 格的第一种定义偏序集 L Remark偏序集 L 中不是任意两个元素均存在上确界及下确界的 c b a d Def设 L 是偏序集 若L中任意两个元素都存在上确界以及下确界 则称 L 是格 lattice 为了方便 这样的格可称为偏序格 Figure6 3 钻石格与五角格 课堂练习习题6 11 例6 1 P170 证明 P X 是格 其中P X 是集合X的幂集 Proof cf Chapter1 A B P X 1 sup A B A B 2 inf A B A B 例6 2 P170 证明 Dn 是格 其中Dn是自然数n的正因数组成的集合 是其上的整除关系 Proof cf Chapter2 例6 3 P170 令F是所有合式公式 WFF 组成的集合 是公式间的逻辑蕴涵关系 则 F 是格 Proof cf Chapter3 A B F 1 sup A B A B 2 inf A B A B 2 格的性质Def设 L 是格 x y sup x y x y inf x y 格中的 是求上确界运算 可以看作是格的加法运算 读作 加 同样 格中的 是求下确界运算 可以看作是格的乘法运算 读作 乘 与环中的 加 和 乘 以及数的 加 和 乘 不同 与布尔代数的运算一致 由于 上确界 上界 以及 下界 下确界 根据定义易知Theorem6 1设 L 是格 则对于任意x y L 有 1 x x y y x y 2 x y x x y y L 与 L Def对于任意关于格 L 的命题 将命题前提和结论中的 1 改为 2 改为 3 改为 4 0改为1 5 1改为0所得到的命题称为原命题的对偶命题 Theorem6 2对于任意关于格 L 的真命题 其对偶命题亦为真 如 1 x x y y x y 2 x y x x y y 在格的性质中 有很多都是成对 dual 出现的 Theorem6 3 保序性 设 L 是格 对于任意xi yi L i 1 2 Proof 1 x1 x2是 x1 x2 的上确界 2 y1 y2是 x1 x2 的上界 Theorem6 4 幂等性 设 L 是格 x L x x x x x x 格的特征性质 Theorem6 5格 L 满足 1 交换性 2 结合性 3 吸收性 Proof 3 x x x y x x x y x 显然 x x x y 所以x x y x x x y x 仿上 对偶 Theorem6 6设 L 是格 则对于任意x y L 下列三个命题等价 1 x y 2 x y y 2 x y x Proof 1 2 x y y y x y y 显然 y x y x y y 2 3 x x y x y x y x 3 1 x x y y 3 格的保序映射Def设 L1 1 和 L2 2 是格 偏序集即可 若存在 L1 L2 则称 为 L1 1 到 L2 2 的保序映射 例6 4 P173 作业习题6 13 6 7 6 2用代数结构定义的格 1 格的第二种定义Def设 L 是代数结构 和 是L上的两个2元运算 同时满足 1 交换性 2 结合性 3 吸收性 则称 L 为格 称这样定义的格为代数格 由定义知 格是具有两个2元运算的代数结构 为了下面的应用 首先证明两个命题 命题1设 L 是代数结构 和 是L上的两个2元运算 若 和 相互可吸收 则 和 具有幂等性 Hint命题2设 L 是代数结构 和 是L上的两个2元运算 若 和 相互可吸收 则 x y L x y x x y y 2 格的两种定义的等价性格的这两种定义是否是一回事 Theorem6 7偏序格 L 与代数格 L 是等价的 Proof 1 是偏序 自反 命题1 反对称 传递 2 对于任意x y L x y是 x y 的下确界 3 对于任意x y L x y是 x y 的上确界 x y L x y x y x x y y 命题2 3 子格设 L 是格 M L 在M上的限制仍记为 有例子表明 M 不一定是格 例6 5X a b M a b P X P X M 不是格 例6 6X a b c M P X c P X M 是格 借助于子代数给子格下的定义 Def设 L 是格 M L 若 M 是格 则称 M 为 L 的子格 sublattice 显然 M 为 L 的子格 M关于 和 封闭 Remark设 L 是格 M L M 是格与 M 是子格存在差异 正因为这样 才借助于子代数对子格定义 4 格的同态与同构可以类似地定义格的同态与同构 Def设 L1 和 L2 是格 若存在 L1 L2 分 别保持格的求上确界运算和求下确界运算 则称 为 L1 到 L2 的格同态映射 格同构的直观意义 Theorem6 8格同态映射是保序映射 Remark格的保序映射不一定是格同态映射 习题 可以考虑格同构映射与格保序映射之间的关系 作业习题6 21 4 6 8 6 3分配格 1 分配格 distributivelattice 的定义有例子表明 格不满足分配性 例6 9举例说明在格 L 中 格的乘法运算 和格加法运算 相互不一定可分配 Solution 钻石格 五角格 Theorem6 9 分配不等式 设 L 是格 对于任意x y z L 有 1 x y z x y x z 2 dual Proof 1 x y z x y x y z x z Theorem6 10设 L 是格 则格的乘法运算 对格的加法运算 可分配 格的加法运算 对格的乘法运算 可分配 Proof x y z L Def设 L 是格 若格的乘法运算 对格的加法运算 可分配 或格的加法运算 对格的乘法运算 可分配 则称 L 是分配格 例6 10证明 P X 是分配格 其他例子 钻石格和五角格是两个非常重要的非分配格的例子 我们只给出Theorem6 11设 L 是格 则L是分配格的充要条件是L中不含有同构于钻石格和五角格的子格 根据上述定理有以下两个推论 Corollary1小于5个元素的格为分配格 Corollary2任意链是分配格 可直接证 2 分配格的性质Theorem6 12设 L 是格 则L是分配格的充要条件是对于任意x y z L 由x y x z和x y x z可以推出y z Remark由x y x z可以推出y z x y x z Proof y y x z y x y z z x y z x y z x z z z 判断一个格是否分配格 作业习题6 32 5 7 9 6 4有补格 1 有界格一般来说 格L不一定存在最大元与最小元 例如 实数集R关于数的小于等于关系 所作成的格 R Def设 L 是格 若L存在最大元素1以及最小元素0 则称 L 为有界格 boundedlattice 例6 12证明 对任意集合X P X 是有界格 Hint最大元素 X 最小元素 显然 任意有限格是有界格 2 补元 有补格Def设 L 是有界格 a L 若存在b L 使得a b 1且a b 0 则称b为a的补元 complement 显然 在任意有界格中 若b为a的补元 则a为b的补元 0与1互为补元 但对于有界格 不是每个元素均有补元 同时一个元素的补元未必唯一 因此 不能定义1元运算 Def设 L 是有界格 若L中每个元素都有补元 则称 L 为有补格 latticecomplemented 例6 14证明 对任意集合X P X 是有补格 Hint A P X X A P X A X A X A X A 右图是有补格 不是分配格 几个重要结论 Theorem6 13在分配格中 若一个元素存在补元 则补元是唯一的 Clearly 根据定理6 13知 在有补分配格中 每个元素都有唯一的补元 正因为如此 在有补分配格中可以定义一个元素的补运算 它是其上的1元代数运算 下述定理是有补分配格的重要性质 Theorem6 14设 L 是有补分配格 则DeMorgan律成立 即对于任意x y L 有 1 2 Proof 1 2 Theorem6 15设 L 是有补分配格 则对于任意x y L 有Proof显然 1 x y 2 作业习题6 4 4 5 6 7 6 5布尔代数 1 布尔代数的格定义Def元素个数 2的有补分配格 B 称为布尔代数 Booleanalgebra 或布尔格 偏序集与各种格之间的相互关系 仅1个元素的有补分配格是布尔代数的退化情形 一般不作为布尔代数考虑 可参见布尔代数的公理化定义 显然 在任何布尔代数或布尔格中有两个特殊元素 一个是其最小元0 一个是其最大元1 当然0 1 在任意布尔代数 B 中可以定义3种代数运算 对于任意x y B a 布尔加 x y sup x y b 布尔乘 x y inf x y c 布尔补 x的补元 例6 16设 X 1 证明 P X 是布尔代数 称为集合代数 X 例6 17证明 F 是布尔代数 其中F是所有合式公式组成的集合 是公式间的逻辑蕴涵关系 称为逻辑代数 F中的元素是逻辑表达式 特别地 令G是所有命题公式组成的集合 则称 G 为命题代数 令H是仅含命题变元p1 p2 pn的所有命题公式组成的集合 则 H 是布尔代数 这时由于集合代数和逻辑代数都是布尔代数 因此它们有完全相似的性质 2 布尔代数的性质Theorem6 16设 B 是布尔代数 I B 是格 II B 是分配格 III B 是有补格 IV B 是有补分配格 以下是布尔代数的特征性质 参见下面的布尔代数的公理化定义 交换律 分配律 幺元律 有补律 3 布尔代数的公理化定义Def E V Hungtington 设B是集合 B 2 和 是B上的两个2元代数运算 是B上的1元代数运算 且满足 1 交换律 2 分配律 3 幺元律 4 有补律 则称是布尔代数 Remark按这种定义需强调两个0元运算 Theorem6 17布尔代数的两种定义是等价的 Proof只需证明 满足定义6 13条件的代数结构是格且0和1分别是其最小元素和最大元素即可 因为根据 2 分配律和 4 有补律知是B有补分配格 首先注意 由于定义中的条件是对偶出现的 所以在该代数结构中 对偶原理成立 其次 x B x 1 1 再其次 B 是格 1 交换性 2 吸收性 3 结合性 B上定义 4 子布尔代数由于布尔代数中有两个0元运算 0和1 有必要对子布尔代数给出定义 Def设是布尔代数 C B 若是布尔代数 则称是的子布尔代数 显然 对于布尔代数 C B 则C是B的子布尔代数 0 1 C且C关于运算 封闭 5 布尔代数的同态与同构定义两个布尔代数的同态与同构时 同样要注意布尔代数中的两个0元运算 0和1 Def设和是布尔代数 若存在映射 B1 B2且 保持所有布尔代数中的运算 1 2 3 4 5 布尔代数之间的同态 构 又称为布尔同态 构 它要求 1 5 都要成立 但实际上 其中的一些条件可以从别的条件推导出来 见本节习题8 9 10 由布尔代数的同构定义容易知道 2个元素的布尔代数是最简单的布尔代数 任意布尔代数都有同构于2个元素的布尔代数的子布尔代数 作业习题6 51 6 8 9 10 6 6有限布尔代数的结构 有限布尔代数与无限布尔代数 对于集合代数 P X 当 X n 1有限时P X 有限 P X 是有限布尔代数 Theorem M H Stone 设是有限布尔代数 则存在有限集合X使得与集合代数 X 同构 实际上 集合X是由有限布尔代数的所有原子组成的集合 先定义一般格上的原子的概念 Def设 L 是格 其最小元素为0 对于a L 若a盖住0 则a称为格的原子 atom 例子 图6 16 Property1 P187 Property2 P188 Property3 P188 Property4 P188 Property5 P188 Property6 P188 ProofoftheStonetheorem 令集合X是由有限布尔代数的所有原子组成的集合 0 单射 满射 保持运算 由Stone定理有Corollary1任意有限布尔代数的元素个数为2n 其中n为正整数 Corollary2在同构意义下 2n个元素的有限布尔代数是唯一的 其中n为正整数 作业习题6 61 4 6 7布尔表达式 布尔表达式的化简及其主范式表示在理论研究和实际应用中都有十分重要的意义 1布尔表达式的定义Def设是布尔代数 则B上的布尔表达式 Booleanexpression 递归定义如下 1 B中的元素a b c等是布尔表达式 2 取值于B的变元x1 x2 等是布尔表达式 3 若e1和e2是布尔表达式 则 e1 e2 e1 e2布尔表达式 4 有限次使用 1 2 3 得到的字符串是仅有的布尔表达式 例设B 0 a b 1 是布尔代数 则等是B上的布尔表达式 含n个变元x1 x2 xn的布尔表达式记为E x1 x2 xn 因此 上例中的两个布尔表达式分别记为逻辑代数上的布尔表达式常称为逻辑表达式 设B 0 1 是布尔代数 它是最简单的逻辑代数 在计算机逻辑电路设计中 B中元素的0和1称为逻辑常量 B上的变元称为逻辑变量 B上的布尔表达式称为逻辑表达式 它就是命题公式 例如等是B上的布尔表达式 2 布尔表达式的化简大家知道 在逻辑电路设计时 会用一个最简单的逻