第五章格与布尔代数.ppt

第五章格与布尔代数 在上一章中介绍了几种代数系统 如半群 群 环 域等 在本章中将再介绍两种代数系统 格和布尔代数 关于格和布尔代数在计算机科学中的应用是众所周知的 第一节格1 1格的定义1 2格中的性质1 3分配格1 4有界格和有补格第二节布尔代数 1格1 1格的定义 在介绍格之前 先介绍两个代数系统中关于运算的性质 定义1 设是代数系统 是上的二元运算 1 任取x Z 若有x x x 则称x是幂等元 2 若 x Z x是幂等元 则称运算x满足幂等律 定义2 设是代数系统 和 是Z上的两个二元运算 若x y Z 有x x y xx x y x则称运算 和运算 满足吸收律 例1 设Z是非零集合 2Z是Z的幂集 和 是2Z上的交和运算 已知是代数系统 1 任取A 2Z 由集合一章知有A A AA A A故由定义1知 和 运算均满足幂等律 2 任取A B 2Z 由集合一章知有A A B AA A B A故由定义2知 和 运算均满足吸收律 例2 设I是整数集合 a b I 定义运算 和 如下 a b min a b a b max a b 则是代数系统 1 由于 a I a a min a a aa a max a a a故由定义1知 和 运算均满足幂等律 2 任取a b I 由于有a a b min a max a b aa a b max a min a b a故由定义2知 和 运算均满足吸收律 定义3 设是代数系统 和 是L上的二元运算 若1 运算和 运算满足结合律2 运算和 运算满足交换律3 运算和 运算满足幂等律4 运算和 运算满足吸收律则称是格 从格的定义可知 格是一个代数系统 这个代数系统有两个二元运算 这两个二元运算满足4条性质 从格的定义可以看到格这种代数系统和环 域这些代数系统有着很大的不同 格中的两个运算满足幂等律和吸收律 这在环和域中是没有的 而环中的么元和逆元的概念在格中也是没有的 因此环和格是两种不同的代数系统 从格的定义还看到 格中的两个二元运算的性质具有对称性 即一个运算所具有的性质 另一个也有 反之亦然 这正是格这种代数系统的特点 格中的许多性质均与此特点有关 例3 已知是代数系统 由集合一章和前面的例子知 和 运算分别满足结合律 交换律 幂等律和吸收律 由格的定义知是格 例4 设I是整数集合 a b Ia b min a b a b max a b 则是代数系统 1 由于 a b c I 有 a b c min min a b c min a b c a b c min a min b c min a b c a b c max max a b c max a b c a b c max a max b c max a b c 故 运算和 运算满足结合律 2 由于 a b I 有a b min a b min b a b aa b max a b max b a b a故 运算和 运算满足交换律 3 由前面的例2知 运算和 运算满足幂等律 4 由前面的例2知 运算和 运算满足吸收律 由格的定义知是格 下面介绍格中的一些性质 从这些性质出发 可以产生格的另一种等价的定义 定理1设是格 a b L a b a的充分必要条件是a b b 由定理1知 在格中 a b a和a b b这两个式子是等价的 当一个式子成立时 另一个式子也成立 反之亦然 在以后的使用中 哪个方便就用哪个 定理2设是格 那么在L中存在半序关系R 由定理2知 可以通过格中 运算构造出格上的一个半序关系 那么是否也可以由格中的 运算构造出格上的一个半序关系呢 由于 运算和运算 的对称性 不但可以用 运算构造出一个半序关系 而且还可以构造出同一个半序关系 由定义1知 a b a和a b b两式是等价的 因此定理2中的R可用 运算定义为 R a b a b L且a b b 同理可以证明R也是L上的半序关系 而且由定理1知这个半序关系与定理2中的半序关系是同一个半序关系 今后将这样定义的半序关系R记为 即 a b La b a b a a b b 定理3设是格 a b a b L且a b a 则有GLB a b a b 其中 GLB a b 是a b的下确界 GLB是GreatestLowerBound的缩写 定理4设是格 a b a b L且a b b 且 则有LUB a b a b 其中 LUB a b 是a b的上确界 LUB是LeastUpperBound的缩写 由定理1 定理2 定理3 定理4知 如果是格 那么就可以在L上利用 和 定义出一个半序关系 在这个半序关系的作用下 L为半序集 且L中的任意两个元素都有上 下确界 并且任意两个元素的上 下确界可以用 或 运算来表示 格中的这种性质是格这种代数系统所独有的 现在反过来问 如果有一个半序集 这个半序集上的任意两个元素都有上 下确界存在 那么这个半序集是否有可能构成一个格呢 下面的定理回答了这个问题 定理5设是半序集 是L上的半序关系 若L中的任意两个元素在 的作用下都有上 下确界存在 则是格 由此定理可知 一个半序集 若其中任两元素都有上 下确界存在 就可以根据此定理给出的方法构成一格 若在此格中再根据定理2的方法定义一个半序关系 则这个半序关系就是半序集上原来的那个半序关系 理由如下 设有半序集 且在半序关系 的作用下 L中的任意两元素都有上确界和下确界 由定理5知可得一格 其中 a b GLB a b a b LUB a b 在此格上根据定理2的方式定义一个半序关系 a b a b L且a b a 由定理2 定理3和定理4知在 的作用下 有a b glb a b a b lub a b 由于这里的 和 就是上面格中的 运算和 运算 故有a b glb a b GLB a b a b lub a b LUB a b 下面证明半序关系 等于半序关系 1 若a b 则有GLB a b a 又因为a b GLB a b 故有a b a 即a b 由 a b 的任意性知 2 若a b 则有a b a 又因为a b GLB a b 故有a GLB a b 由下确界的定义知有a b 由 a b 的任意性知 由集合相等的定义知 即 和 是同一个半序关系 由此可知 格与任意两个元素有上 下确界的半序集是等价的 即格就是任意两个元素有上 下确界的半序集 而任意两个元素有上 下确界的半序集就是格 于是得到格的另一种等价的定义 定义3 设是半序集 若L中的任意两个元素有上 下确界存在 则称是格 由于定义3和定义3 的等价性 以后关于格 既可以用表示 也可以用表示 当用表示时 半序关系是用a b a或a b b定义的 当用表示时 两个运算是用a b GLB a b a b LUB a b 定义的 更多的时候则用表示 即将格中的代数性质和序性质都表示出来 这样就将格的性质描述的比较全面了 例如是格 也是格 且是同一个格 因此通常用表示这个格 下面给出两个例子 这两个例子建立了同一个格 一个是从定义3的角度建立的 一个是从定义3 的角度建立的 例5设N为自然数集 和 定义如下 a b N a b GLD a b a b LCM a b 由于两个自然数的最大公约数和最小公倍数是唯一的 且为自然数 故 和 是N上的两个二元运算 下证这两个二元运算分别满足结合律 交换律 幂等律 吸收律 1 a b c N 由于有 a b c GCD a b c a b c a b c LCM a b c a b c 故 运算和 运算满足结合律 2 a b N 由于有a b GCD a b GCD b a b aa b LCM a b LCM b a b a故 运算和 运算满足交换律 3 a N 由于有a a GCD a a aa a LCM a a a故 运算和 运算满足幂等律 4 a b N 由于有a a b GCD a LCM a b aa a b LCM a GCD a b a故 运算和 运算满足吸收律 由格的定义知是格 由定理2可知 在此格上有半序关系R如下 R a b a b N且a b a a b a b N且a b b 由于a b a等价于GCD a b a a b b等价于LCM a b b 故当且仅当a整除b时 a b有关系R 因此 半序关系R就是N上的整除关系 且在此半序关系的作用下 有GLB a b a b GCD a b LUB a b a b LCM a b 例6 设N是自然数集合 R a b a b N且a b 则是格 要证是格 必须证两点 一是证明R为N上的半序关系 二是证明在R的作用下N中任意两元素都有上 下确界 证 先证R是N上的半序关系 1 a N 由整除的性质知有a a 故a N有 a a R 即R是自反的 2 若有 a b R且 b a R 则有a b且b a 由整除的性质知有a b 即R是反对称的 3 若有 a b R且 b c R 则有a b且b c 由整除的性质知有a c 即R是传递的 由半序关系的定义知R是N上的半序关系 下证N中任意两元素在R的作用下都有上 下确界存在 a b N 设 是a b的最大公约数 即 GCD a b 于是有 a且 b 即 是a b的下界 若另有下界 则有 a 且 b 故 是a b的公约数 由最大公约数的定义知有 即 是a b的最大下界 即有 GLB a b GCD a b a b N 设 是a b的最小公倍数 即 LCM a b 于是有a 且b 即 是a b的上界 若另有上界 则有a 且b 故 是a b的公倍数 由最小公倍数的定义知有 即 是a b的最小上界 即有LUB a b LCM a b 由格的定义知是格 由定理5的证明知 在此格上可产生两个二元运算 和 其中 a b N a b GLB a b GCD a b a b LUB a b LCM a b 且 运算和 运算满足结合律 交换律 幂等律 吸收律 由例3和例4可知 如果将求最大公约数和求最小公倍数作为N上的两个二元运算 则半序关系就是N上的整除关系 且任两元素的上确界就是它们的最小公倍数 任两个元素的下确界就是它们的最大公约数 反之 若在N上定义一个整除关系 则此关系是一个半序关系 且任两元素的上确界就是它们的最小公倍数 任两个元素的下确界就是它们的最大公约数 由此而引出的两个二元运算就是求最大公约数和求最小公倍数 且这两个二元运算满足结合律 交换律 幂等律 吸收律 这两个例子验证了定义3和定义3 的等价性 通常将此格记为 1 2格中的性质1 对偶原理 设是格 是 的逆关系 若T是格中某个已证明的定理 那么在定理的条件和结论中实行1 将 换成 2 将 换成 3 将 换成 由此所得到的新的定理仍然成立 这就是格中的对偶原理 格中的对偶原理实质上来源于两个二元运算 和 所具有的结合律 交换律 幂等律 吸收律的对称性以及半序关系 和其逆关系 的对称性 2 运算的保序性定理6设是格 a b c L 若a b 则a c b ca c b c3 分配不等式定理7设是格 a b c L 有1 a b c a b a c 2 a b a c a b c 1 3分配格 定义6设是格 若 a b c L 有a b c a b a c a b c a b a c 则称是分配格 所谓分配格就是在格中 运算对 运算满足分配律 且 运算对 运算也满足分配律 例1 已知是格 由集合一章知 A B C 2Z 有 A B C A B A C A B C A B A C 由分配格的定义知是分配格 例2 已知是格 由GCD和LCM的性质可知 A B C N有GCD a LCM b c LCM GCD a b GCD a c LCM a GCD b c GCD LCM a b LCM a c 由分配格的定义知是分配格 例3 下面两个格均不是分配格 由于在图3中a2 a3 a4 a2 a1 a2 a2 a3 a2 a4 a5 a5 a5故a2 a3 a4 a2 a3 a2 a4 由于在图4中b2 b3 b4 b2 b1 b2 b2 b3 b2 b4 b3 b5 b3故b2 b3 b4 b2 b3 b2 b4 由分配格的定义知图4中的格不是分配格 关于分配格有一个充分必要条件 即一个格不是分配格的充分必要条件是格中有一子格与例3中的某个格同构 定理11设是分配格 a b c L 若a b a c且a b a c 则b c 定理11说明分配格中有格的消去律 这里说明一点 即格中的消去律 没有提到零元的问题 这是因为在格中 关于 的零元 若有的话只能是最小元 而关于 的零元 若有的话只能是最大元 在格中 当 L 2时 最小元和最大元就不会是同一个元素 因此若a是关于 的零元就不是关于 的零元 若a是关于 的零元就不是关于 的零元 由于在定理11中要求a b a c和a b a c同时成立 因此对a就没有任何要求 故这里的消去律和前面提过的消去律有所不同 这是格中的消去律 定理12设是格 若 是L上的全序关系 则是分配格 例4 设Z为实数闭区间 0 1 为实数间的小于或等于关系 由于a b L 有GLB a b min a b LUB a b max a b 故是格 且a b min a b a b max a b 由于任意两个实数均能比较大小 故此格中的半序关系为全序关系 由定理12知是分配格 有时记为 1 4有界格和有补格 定义7设是格 1 若存在L0 L a L有L0 a 则称L0是格中的最小元 通常记为0 2 若存在L1 L a L有a L1 则称L1是格中的最大元 通常记为1 3 若格中有最大元和最小元 则称此格为有界格 今后若一个格是有界格 往往将最大元1和最小元0也写在格的表示中 即表示有界格 由于格是半序集 且格中任意两元素都有上 下确界 因此有限格中必有最大元和最小元 即有限格一定是有界格 但在无限格中就不一定有最大元和最小元 即无限格不一定是有界格 例1 已知是格 当 Z n时 这是有限格 因此是有界格 由于 A 2Z 有 A 故是此格的最小元 由于 A 2Z 有A Z 故Z是此格的最大元 例2 已知是格 这是一个无限格 这也是一个有界格 最大元是1 最小元是0 例3 已知是格 这是一个无限格 这不是一个有界格 因为在此格中无最大元 定义8设是有界格 1 任取a L 若存在b L 使得a b 0a b 1则称b是a的补元 将b记为a 2 若格中的每个元素均有补元 则称此格为有补格 在定义中可以看到补元的概念是建立在有界格的基础上的 即补元的先决条件是 此格必须是有界格 补元是对某个元素而言 有补格则是对所有的元素而言 一个元素可能有补元 也可能没有补元 但在有补格中 则要求每个元素有补元 另外由 和 的交换律知 当b