第六章 格与布尔代数这一章将介绍另一类代数系统，这就是格。格论大体上是在1935年左右形成的，它不仅是代数学的一个分支，而且在近代解析几何，半序空间等方面也都有重要的作用。我们在这里只介绍格的一些基本知识以及几个具有特别性质的格分配格、有补格。学习格与布尔代数 这一章的要求一、学习目的与要求本章在已经学过的群、环和域几个代数系统的 基础上，进一步学习格这个新的代数系统，并且 学习在计算机科学中有重要应用的布尔代数。通 过本章的学习，使学生进一步了解格的基本概念 ，掌握布尔代数的运算规律，为学习数字逻辑、 计算机硬件设计等课程打下数学基础。 二、知识点1格的概念，偏序集上的并运算、 偏序集上的交运算。2分配格、有补格；3布尔代数、Stone表示定理及其推 论，布尔表达式、布尔函数、开关代数的概 念。三、要求1识记根据哈斯图识别是否是格，分配格、有补格，模格，布尔格、布尔代数。2领会格同构的概念，分配格与模格的关系，格的 全上界的唯一性证明，Stone表示定理、布尔表达式、析取范式和合取范式。3简单应用开关代数。一、自反性和反自反性 1、自反性：设R是集合X上的二元关系，如果对 于每一个xX，有R，则称R是自反的。R在X上自反(x)(xXR)2、反自反性：设R是集合X上的二元关系，如果 对于每一个xX，有R，则称R是反自反的。R在X上反自反(x)(xXR)复习二、对称性和反对称性 1、对称性：设R是集合X上的二元关系，如果对于 每一个x，yX，每当R，就有R ，则称R是对称的。 R在X上对称(x)(y)(xXyXRR) 2、反对称性：设R是集合X上的二元关系，如果对 于每一个x，yX，每当R和R必 有x=y，则称R是反对称的。 R在X上反对称 (x)(y)(xXyXRRx=y)三、传递性 1、定义：设R是集合X上的二元关系，如果对 于任意x，y，zX，每当R，R时就有R，则称R是传递的。 R在X上传递 (x)(y)(z)(xXyXzXRRR)1.偏序集定义3-12.1：设A是一个集合，如果A上的一个关系R满足 自反性、反对称性和传递性，则称R是A上的一个偏序关系 ，记作 。称作偏序集。2. 最大元、最小元定义3-12.6：设是一个偏序集，且B是A的子集，若有某个元素bB，对于B中的每一个元素x，有xb，则称b为的最大元；同理，若有某个元素bB，对于B中的每一个元素x，有bx，则称b为的最小元。3.哈斯图 定义3-12.2：在偏序集中，如果x、yA，xy， xy，且没有其他元素z，使xz，zy，则称元素y盖住元 素x。记COVA=|x、yA，y盖住x。 对于给定偏序集，它的盖住关系是唯一的，所以可用盖住的性质画出偏序集合图，或称哈斯图，其作图规则为：(1)小圆圈代表元素。(2)如果xy且xy，将代表y的小圆圈画在代表x的小圆圈之上。(3)如果COVA，则在x与y之间用直线连结。4. 上界、下界定义3-12.7：设是一偏序集，对于BA，如有aA，且对任意元素xB，都有xa，则称a为B的上界。同理，对任意元素xB，都有ax，则称a为B的下界。 5. 上确界、下确界定义3-12.8：设是一偏序集且BA，a是B的任一上界，若对B的所有上界y均有ay，则称a是B的最小上界(上确界)，记作LUBB。同理，b是B的任一下界，若对B的所有下界z均有zb，则称b是B的最大下界(下确界)，记作GLBB。 6-1 格的概念在第三章中，我们介绍了偏序集的概念，偏序集就是由 一个集合A以及A上的一个偏序关系“”所组成的一个代数系 统。我们知道，对于偏序集来说，它的任一个子集 不是必定存在最小上界或最大下界的。例如，在由图6-1.1所示的偏序集中，a，b的最小上 界是c，但没有最大下界；e，f的最大下界是d，但没有最 小上界。今后，我们把a，b的最小上界（最大下界）称为元素a，b的最小上界（最大下界）。由图6-1.2所示的偏序集都有这样一个共同的特性，那就是在这些偏序集中，任何两个元素都有最小上界和最大下界。我们把具有这种性质的偏序集称作格。一、格的定义称为正整数格定义6-1.1 设是一个偏序集，如果A中任意两个元素 都有最小上界和最大下界，则称为格（lattice）。例1 设I+是所有正整数的结合，在I+上定义一个二元关系|， 对于a,bI+，a|b当且仅当a整除b。容易验证|是I+上的一个 偏序关系，故是偏序集。由于该偏序集中任意两 个元素的最小公倍数、最大公约数就是这两个元素的最小 上界和最大下界，因此是格。例2 设(S)是给定集合S的幂集，是一个偏序 集。由于(S)中的任意两个元素S1，S2，它们的最大下界 为S1S2 ，最小上界为S1S2 ，所以是格。例3 给定S=a，b，(S)=,a,b,a,b，那么，格如图6-1.3所示。二、由格所诱导的代数系统定义6-1.2 设是一个格,如果在A上定义两个二元运 算和 ,使得对于任意的a,b A ， ab等于 a和b的最小上 界, ab等于a和b的最大下界,那么,就称为由格所诱导的代数系统。二元运算和分别称为并运算和交运算。通常用ab 表示a,b的上确界,用ab 表示a，b的下 确界,和分别称为保联(join)和保交(meet)运算。由于对任 何a，b，ab及ab都是A 中确定的成员，因此 ,均为 A上的运算。设S=a,b ， (S) =, a,b,a,b由格诱 导的代数系统为 。其中为集合的并运算和 为集合的交运算。如表6-1.1所示。三、子格定义6-1.3 设是一个格, 由格所诱导 的代数系统为 。设BA 且B ，如果A中 的两个运算和 关于B是封闭的，则称 是 的子格。例4 例1给出了一个具体的格 ，由它诱 导的代数系统为 ，其中ab就是a，b的 最小公倍数，ab就是a，b的最大公约数。因为任何两个偶数的最大公约数和最小公倍数都是偶数，所以 ，如果取E+是正偶整数的全体，那么和关于E+ 是封闭的，因此称 是的子格。必须指出，对于格，设B是A的非空子集，尽 管必定是一个偏序集，然而不一定是格 ，而且即使是格，也不一定是的子格。例题1 设是一个格，任取aS，构造S的子集T为：T=x|xS且xa则是 的一个子格。解 对于任意的x,yT，必有xa 和ya，所以xya，xya故xyT，xyT 因此是 的一个子格。同样地，可以证明，如果取Q=x|xS且ax，则也是 的一个子格。四、格所诱导的代数系统的一些性质1. 对偶原理在讨论格以及格所诱导的代数系统的一些性质之前，先介绍格的对偶原理。对偶这个概念在日常生活中也是屡见不鲜的，譬如，在不同国家的交通规则可能不同，但基本上是两种，一种是以左为准，另一种是以右为准，那么，在以左为准的交通规则中，如果将左换成右，右换成左就可得到另一种以右为准的交通规则，这里，左和右就是一种对偶的概念。格对偶原理：设是一个偏序集,在A上定义 一 个二元关系R,使得对于A中任意两个元素a,b都有 关系a Rb当且仅当b a,于是也是一个偏序集。把和称为相互对偶的(哈斯图相互颠倒)。可以证明，若是格，则也是格。称R是的逆关系。记为。格对偶原理可以叙述为：设P是对任意格都真的 命题，如果在命题P中把换成 ，换成，换成 ，就得到另一个命题P，我们把P称为P的对偶命 题，则P对任意格也是真的命题。2. 格所诱导的代数系统的一些性质定理6-1.1 在一个格中，对任意两个元素 a,bA都有a ab b ab ab a ab b 证明思路： 因为a和b的并是a的一个上界，所以a ab同理 b ab 由对偶原理，即得 ab a ab b 定理6-1.2 在一个格中，对于任意元素a,b,c,dA, 如果 a b 和 c d 则 ac bdac bd证明 因为b bd，d bd，所以，由传递性可得a bd和 c bd 这就表明bd是a和c的一个上界，而ac是a和c的最小上界 ，所以，必有ac bd 类似地可以证明 ac bd推论 在一个格中，对于任意元素a,b,cA,如果b c,则 ab ac, ab ac(保序性)。证明 只要在定理6-1.2中将a代替b，b代替c，c代替d，即可得证。定理6-1.3 在一个格中,由格所诱导的 代数系统为,则对于任意元素a,b,c,dA,有(1) ab= baab= ba(2) a(bc)=(ab)ca(bc)=(ab)c(3) aa=aaa=a(4) a(ab)=aa(ab)=a（交换律）（结合律）（幂等律）（吸收律）（2）第一式：先证(ab)c a(bc) 根据定理1（x xy,y xy）b bc a(bc ) , a a(bc ) 根据定理2（x1 x2且y1 y2 x1y1 x2y2）ab a(bc ) 又因为c (bc ) a(bc ) 再根据定理2(ab)c a(bc )再证a(bc) (ab)cb ab, c c bc (ab)c a (ab) a(bc ) a(bc) a(bc ) 证明思路：（1）格中任何两个元素 a，b的最小上界 （最大下界）当然等于b，a的最小上界（最大下界）， 故 ab=ba（ab=ba）（3）由定理6-1.1可得 a a a由自反性可知 a a 由此可得 aa a因此 aa= a利用对偶原理，即得aa=a（4）由定理6-1.1可得 a a （ab）因为 a a和 ab a 所以 a （ab） a因此 a(ab)=a利用对偶原理，即得a(ab)=a例6 设是一个偏序集，这里N是自然数集， 是普通 的数与数之间的“小于等于”关系，定义ab =maxa,b （取大运算）ab =min a,b （取小运算） 则是一个格。由此格诱导的代数系统为 可以证明，该代数系统的两个运算满足定理6-1.3的4个运算律。在此代数系统中，任意两个数a和b的最大值（最小值）与b 和a的最大值（最小值）是相等的，因此，并运算和交运算都是 可交换的；又因为max(max(a,b),c)和max(a,max(b,c) 都是三 个数a,b,c中的最大值，所以在中并运算是可结合的， 同理， min(min(a,b),c)=min(a, min(b,c) ，说明交运算的结合 性；由于max(a,a)=min(a,a)=a，所以幂等性成立；又由于 max(a,min(a,b) =a和min(a, max(a,b)=a，因此，吸收性也成 立。 五、由代数系统确定的格引理6-1.1 设是一个