翻译的高等离散结构课件.ppt

1、第六章 序关系与序结构,6.1 偏序集,偏序集：在某个集合A上的关系R如果是自反的、反对称的和传递的，那么称R是一个偏序。集合A与偏序R一起称作偏序集，用(A，R)表示。如果不会产生混淆的话，那么可以把偏序集简单地记成A而非(A，R)。 例1 设A是集合S的子集的集合，集合的包含关系 是A上的一个偏序，所以(A， )是一个偏序集。 例2 设Z+是正整数集合，通常的关系(小于或等于)是Z+上的一个偏序。同样(大于或等于)也是Z+上的一个偏序。 例3 整除关系(a R b当且仅当a|b)是Z+上的一个偏序。,2,例4 设是集合A上所有等价关系的集合，因为是由A A的子集所组成的，所以在集合的包含偏

2、序下是一个偏序集。如果R和S是A上的等价关系，那么某些性质可以用关系符号表示如下： RS当且仅当x R y推出对A中所有x, y有x S y，于是(， )是一个偏序集。 例5 Z+上的关系不是一个偏序，因为它不是自反的。 例6 设R是集合A上一个偏序，R1是R的逆关系，那么R1也是一个偏序。为了看清这一点，回顾4.4节给出的自反性、反对称性和传递性的特征。如果R有这三种性质，那么R，RR1，R2R，通过取逆有 = 1R1，R1 (R1)1 = R1R，(R1)2R1，所以，由4.4节可知，R1是自反的、反对称的和传递的。因此，R1也是一个偏序。偏序集(A，R1)称为偏序集(A，R)的对偶，偏序

3、R1称为偏序R的对偶。,3,最熟悉的偏序是Z和R上的关系和。由于这个原因，当一般谈到集合A上的偏序R时，常常对R使用符号或，这使得R的性质更熟悉和更容易记忆。因此，读者可以把符号用来当作不同集合上许多不同的偏序。但不要误认为这些关系都是相同的或者它们是熟知的Z或R上的关系。如果需要同另一个偏序区别开来，也可以使用如1，1，等符号来表示偏序。 本书将遵守下面的约定，当(A，)是一个偏序集时，总是使用符号代替偏序1，因此，(A，)将是对偶偏序集。类似地，偏序集(A，1)的对偶将用(A，1)表示，偏序集(B，)的对偶用(B，)表示。这种约定再一次使人想起熟悉的对偶偏序集(Z，)和(Z，)以及偏序集(

4、R，)和(R，)。,4,如果(A，)是一个偏序集，对A的元素a和b，如果ab或ba，那么说a和b是可比的。注意，在偏序集中每一对元素不必都是可比的。例如，考虑例3中的偏序集，元素2和7不是可比的，因为2 7且7 2。因此，在偏序集中的“偏”字意味着某些元素可能不是可比的。如果在一个偏序集A中每一对元素都是可比的，则称A是一个全序集，偏序称为全序，也称A是一个链。 例7 例2中的偏序集是全序集。,5,定理1 如果(A，)和(B，)是偏序集，那么(A B，)是一个偏序集，它的偏序由下述定义：如果在A中aa和在B中bb，那么(a, b)(a, b)。 注意，上面使用的符号表示三种不同的偏序。 证明

5、如果(a, b)A B，因为在A中有aa和在B中有bb，所以(a,b)(a,b)，从而在A B中满足自反性质。 现在假设(a,b)(a，b)和(a, b)(a,b)，其中a, aA，b, bB。于是在A中有 aa，aa 且在B中有 bb, bb, 因为A和B是偏序集，所以在A和B中，由偏序的反对称性推出a = a和b= b，因此，在AB中满足反对称性。 最后，假设(a,b)(a，b)和(a，b)(a, b)，其中a, a, aA且b, b, bB，那么aa且aa，所以，由A中偏序的传递性推出aa。类似地，bb且bb，所以由B中偏序的传递性推出bb。因此，(a,b)(a，b)，由此推出在AB中偏

6、序的传递性成立，从而得到AB是一个偏序集。,6,在如上笛卡儿积AB上定义的偏序称作积偏序。 设(A，)是一个偏序集，如果ab，但ab，则称ab。现在假设(A，)和(B，)是偏序集，在定理1中已经在AB上定义了积偏序。现在在AB上定义另一个有用的偏序，用表示，它的定义如下：如果a a, 或者a = a且bb, 那么(a, b)(a, b)，这种排序称为字典序。除第一个坐标“相等”的情况外，第一个坐标元素的排序起决定性作用而可以忽略第二个坐标的排序。 如果(A，)和(B，)是全序集，那么在AB上的字典序也是一个全序。,7,例8 设A =R，用通常的排序，那么平面R2 = RR给出了字典序，如图6.

7、1所示。可以看到平面是由字典序所产生的全序，每条垂直线有通常的序，并且在该直线上的点比它右边的垂直线上的点小。因此，在图6.1中, p2p3 , p1p2, p1p3。,8,图6.1,字典序很容易扩展到笛卡儿积A1A2An： 当且仅当 或 和 或 ， 和 或 ， 和 因此，第一个坐标完全决定了排序（除非它相等），在第一个坐标相等的情况下，考虑第二个坐标。如果再次相等，考虑第三个坐标，等等。,9,例9 设S = a，b，z是通常的字母表，采用通常的全序方法(ab，bc，yz)。于是Sn = SSS (n个因子)能与长度为n的所有字集合等同。在Sn上的字典序具有性质：如果w1w2(w1，w2Sn)

8、，那么w1在字典列表中将先于w2。这一事实说明了字典序名称的由来。 因此，park part，help hind，jump mump。因为j m，所以第三个为真。因为h = h, e i,所以第二个为真。因为p = p，a = a，r = r，k t，所以第一个为真。 如果S是一个偏序集，那么可以用下面的方法把字典序扩展到S*(见1.3节)。 如果x = a1a2an和y = b1b2bk属于S*并且nk，那么如果在Sn的字典序下有(a1，an) (b1，bk)，则称Sn中x y。,10,在上一自然段，使用了n个数组(a1, a2,，an)Sn，它实际上与字符串a1a2anS*是长度为n的同一

9、序列，只不过用不同的符号表示罢了。这种符号的不同是出于历史原因，在使用它们时依赖于上下文环境而转换。 例10 设S是a，b，z，按通常的次序，那么S*是任意长度的所有可能的“词”的集合，无论这些“词”是否有意义。 因此，在S*中有help helping，因为在S4中，help help。类似地，因为在S6中helper helping，所以helper helping。正如例子help helping所示，排序包括了词头排序，即：任意一个词比它的所有词头(开始部分)大，这也是字典中词的出现方法。,11,因为一个偏序是一种关系，所以可考虑在有限集合上任意偏序的有向图。将看到偏序的有向图表示方法

10、比那些一般的关系有向图表示方法更简单。下面的定理提供了该方向的第一个结果。 定理2 偏序的有向图中没有长度比1大的环。 证明 假设在集合A上偏序的有向图包含一个长度为n2的环，那么存在互不相同的元素a1，a2，anA，使得 a1a2, a2a3, , an1an, ana1 由偏序的传递性，使用n1次得到a1an。由反对称性有ana1和a1an，从而推出an = a1，这与假设a1，a2，an互不相同是矛盾的。,12,哈塞图,设A是一个有限集合，定理2表明A上偏序的有向图只有长度为1的环。事实上，因为偏序是自反的，所以在偏序的有向图中每个顶点被包含在长度为1的环中。为了简化这件事情，将去掉有向

11、图中所有这种环。因此，在图6.2(a)中表示的有向图将画成如图6.2(b)所示的图。,13,图 6.2,我们也去掉由传递性推出的所有边。因此，如果ab且bc，那么得到ac。在这种情况下，省略从a到c的边，但要画从a到b和从b到c的边。例如，图6.3(a)所示的有向图将画成图6.3(b)所示的图。还约定用所有朝上的边来画偏序的有向图，以致箭头可以从边上省略。最后，用点取代圆圈来表示顶点。因此，图6.4所示的图给出了图6.2(a)所示有向图的最终形式。这样的偏序图比它的有向图简单得多，称作偏序集上偏序的哈塞图。因为哈塞图完全描述了有关的偏序，所以它是一种非常有用的工具。,14,图 6.3,图 6.

12、4,例11 设A=1，2，3，4，12，考虑A上的整除性偏序，即：如果a, b A，ab当且仅当a|b。画出偏序集(A，)的哈塞图。 解 在图6.5中给出了图6.5的偏序集的有向图。哈塞图如图6.6所示，由此可以看出哈塞图的简单性 。,15,图6.5,图6.6,例12 设S=a，b，c和A = P(S)，画出具有偏序 (集合包含)关系的偏序集A的哈塞图。 解 首先确定A，得到 A = , a, b, c, a，b, a，c, b，c, a，b，c 于是哈塞图如图6.7所示。 注意, 一个有限全序集的哈塞图总是具有图6.8所示的形式。,16,图 6.7,图 6.8,容易看到如果(A，)是一个偏序

13、集，(A，)是对偶偏序集,那么(A, )的哈塞图恰好是把(A，)的哈塞图颠倒过来。 例13 图6.9(a)给出了偏序集(A，)的哈塞图，其中A=a，b，c，d，e，f。图6.9(b)给出了对偶偏序集(A，)的哈塞图。注意，像刚才提到的那样，这些图能够通过把另一个图颠倒过来而得到。,17,图6.9,拓扑排序,如果A是具有偏序的一个偏序集，有时需要对集合A找一个全序 ，使得该全序只不过是已知偏序在如下意义的一个扩展：如果ab，那么ab。构造如的一个全序的过程称作拓扑排序。该问题产生于当人们必须把有限偏序集A输入计算机时。A中的元素必须以某种次序被输入，并且也许要求它们输入后保持偏序，即：如果ab，

14、那么a是在b之前被输入。拓扑排序将给出遇到这种情况时元素输入的次序。,18,例14 对于哈塞图如图6.10所示的偏序集，给出一个拓扑排序。 解 显然如图6.11(a)所示的哈塞图的偏序是一个全序。容易看到每一对元素用排序也就是用排序，所以是偏序的拓扑排序。图6.11(b)和(c)给出了此问题的另外两种解答。,19,图6.10,图6.11,同构,设(A，)和(A，)是偏序集，f：AA是A与A之间的一一对应。如果对于A中任意的a和b，ab当且仅当 f (a) f(b)，那么称函数 f 是从(A，)到(A，)的一个同构。如果 f：AA是一个同构，那么称(A，)和(A，)是同构的偏序集。 例15 设A

15、是正整数集合Z+，是A上通常的偏序(见例2)。A是正偶数集合，是A上通常的偏序。函数f：AA由f (a) = 2a给出，它是从(A，)到(A，)的一个同构。 首先，因为如果f (a) = f (b)，那么2a = 2b，即a = b，所以f是单射。其次，Dom(f) = A，所以f是处处有定义的。最后，如果cA，那么有某个aZ+使得c = 2a，所以c = f (a)。这就证明了f是满射。因此，f是一一对应。最后，如果a和b是A中的元素，则显然ab当且仅当2a2b。因此f是一个同构。,20,假设f：AA是从偏序集(A，)到偏序集(A，)的一个同构。还假设B是A的一个子集，B= f(B)是对应的

16、A的子集。那么从同构的定义可以看到下面的原理必定成立。 定理3 (对应原理) 如果B的元素相互间或者与A的其他元素间有某种性质，并且这种性质可完全根据关系定义，那么B的元素一定具有由定义的完全相同的性质。,21,例16 设(A，)是偏序集，它的哈塞图如图6.12所示。假设f是从(A，)到某个其他偏序集(A，)的一个同构。首先注意对A中任意x有dx(稍后将d这样的元称为A的“最小元”)，那么在A中对应元f(d)一定满足性质：对A中的所有y有f(d)y。作为另一个例子，注意a b和b a，这种元素对称为在A中是不可比的。于是从对应原理得到f (a)和f(b)在A中一定也是不可比的。,22,图6.1

17、2,确切地说，设(A，)和(A，)是有限偏序集，f：AA是一一对应，H是(A，)的任意哈塞图。那么 1如果f是一个同构，H的每个符号a用f(a)取代，那么H将变为(A，)的一个哈塞图。 反之 2如果H是(A，)的一个哈塞图，当每个符号a由f(a)代替时，那么f是一个同构。 这就说明了名字“同构”的合理性，因为同构偏序集用哈塞图描述有相同的“形状”。,23,例17 设A = 1，2，3，6，是关系 |(整除)，图6.13(a)表示(A，)的哈塞图。设A = P(a，b)=，a，b，a，b，是集合包含 ，如果f：AA定义如下 f (1) = ，f (2) = a，f (3) = b，f (6) =

18、 a，b 那么容易看到f是一一对应。如果哈塞图的每个符号aA用f(a)代替，结果如图6.13(b)所示。因为很显然这是(A，)的一个哈塞图，所以函数 f 是一个同构。,24,图6.13,6.2 偏序集的极值元,在一个偏序集中，某些元素对于偏序集的许多性质和应用具有特殊的重要性。在这一节讨论这些元素，在稍后几节可以看到它们所起的重要作用。本节考虑一个偏序集(A，)。 一个元素aA，如果在A中不存在任何元素c使得ac，则称a是A的一个极大元。一个元素bA，如果在A中不存在任何元素c使得cb，则称b是A的一个极小元。 由此立即得到：如果(A，)是一个偏序集，那么(A，)是它的对偶偏序集。元素aA是(

19、A，)的一个极大元当且仅当a是(A，)的一个极小元。同样，a是(A，)的一个极小元当且仅当它是(A，)的一个极大元。,25,例1 考虑偏序集A，它的哈塞图如图6.22所示。元素a1, a2和a3是A的极大元，元素b1, b2和b3是极小元。注意，因为在b2与b3之间不存在任何直线，所以可以断定既没有b3b2也没有b2b3。 图6.22,26,例2 设A是有通常偏序的非负实数偏序集，那么0是A的极小元，A不存在极大元。 例3 偏序集Z具有通常的偏序，它没有极大元也没有极小元。 定理1 设A是有偏序的有限非空偏序集，那么A至少有一个极大元和一个极小元。 证明 设a是A的任意一个元素，如果a不是极大

20、元，那么能够找到一个元a1A，使得aa1；如果a1不是极大元，那么能够找到一个元a2A，使得a1a2。因为A是有限集，所以这种推理不能无限次继续下去。因此，最终获得有限链：aa1a2ak1ak，它不能再扩充了。因此，对任意bA，不能有akb，所以ak是(A，)的一个极大元。 同理可得对偶偏序集(A，)有一个极大元，所以(A，)有一个极小元。,27,用极小元的概念，能够为已知有限偏序集(A, )给出一种求拓扑排序的算法。首先注意如果aA且B=Aa，那么B也是在BB限制下的一个偏序集(见4.2节)。于是得到如下的算法，该算法产生一个名为SORT的线性数组。假设SORT是按递增下标排序，即：SORT

21、1 SORT2 ，那么用这种方式定义A上的关系 是(A，)的一种拓扑排序。 算法 找有限偏序集(A，)的拓扑排序。 步骤1：选择A的一个极小元a。 步骤2：使a成为SORT的下一项并且用Aa代替A。 步骤3：重复步骤1和步骤2直到A= 。,28,例4 设A=a,b,c,d,e，A上偏序的哈塞图如图6.23(a)所示，该偏序集的一个极小元是标号为d的顶点(也可选e)。把d放入SORT1中，并且在图6.23(b)中给出Ad的哈塞图。新A的一个极小元是e，所以e成为SORT2，Ae如图6.23(c)所示。这个过程继续下去，直至用完A中元素为止，并且填充SORT。图6.23(f)给出了全部数组SORT

22、和对应于SORT的偏序集的哈塞图。这就是(A，)的一个拓扑排序。,29,图 6.23,一个元素aA，如果对所有xA有xa，则称a是A的最大元。一个元素aA，如果对所有xA有ax，则称a是A的最小元。 同前面一样，(A，)的一个元a是最大元(最小元)当且仅当它是(A，)的最小元(最大元)。 例5 考虑例2中定义的偏序集，那么0是一个最小元，不存在最大元。 例6 设S=a, b, c，考虑6.1节的例12定义的偏序集A=P(S)，空集是A的一个最小元，集合S是A的一个最大元。 例7 有通常偏序的偏序集Z既无最小元也无最大元。,30,定理2 一个偏序集至多有一个最大元也至多有一个最小元。 证明 假设

23、a和b是偏序集A的最大元，那么，由于b是一个最大元，所以有ab。类似地，由于a是一个最大元，所以有ba。因此，由反对称性质得到a=b，故如果偏序集有一个最大元，那么它只有一个这样的元。因为对所有偏序集这一事实都为真，所以对偶偏序集(A，)至多有一个最大元，故(A，)也至多有一个最小元。 一个偏序集的最大元，如果存在的话，用I表示，它常称作单位元。类似地，一个偏序集的最小元，如果存在的话，用0表示，它常称作零元。 考虑某个偏序集A和A的子集B，一个元素aA，如果对所有bB有ba，则称a是B的一个上界。如果对所有bB有ab，则称a是B的一个下界。,31,例8 考虑偏序集A=a，b，c，d，e，f，

24、g，h，它的哈塞图如图6.24所示。求A的下列子集的所有上界和下界。 (a) B1 = a，b (b) B2 = c，d，e 解 (a) B1没有下界，它的上界是c，d，e，f，g，h。 (b) B2的上界是f，g和h，它的下界是c，a和b。,32,例8表明一个偏序集的子集B可以有也可以没有上界或下界(在A中)，而且B的上界或下界可以属于也可以不属于B本身。,图 6.24,设A是一个偏序集，B是A的一个子集。如果一个元aA是B的上界并且当a是B的一个上界时，有aa，则称a是B的最小上界(LUB(B)。因此，如果对所有bB，有ba并且如果当aA也是B的一个上界时，那么aa，则a = LUB(B)

25、。 类似地，如果一个元aA是B的一个下界，并且当a是B的一个下界时，aa，则称a是B的最大下界(GLB(B)。因此，如果对所有bB有ab，并且当aA也是B的一个下界时，有aa，那么a = GLB(B)。 同通常情况一样，(A，)中的上界对应(A，)中的下界(对于同一集合元素)，(A，)中的下界对应(A，)中的上界。对于最大下界和最小上界，类似的命题成立。,33,例9 设A是例8中考虑的偏序集，有例中所定义的子集B1和B2，对于 (a) B1； (b) B2； 求所有最小上界和最大下界。 解 (a) 因为B1没有下界，所以它没有最大下界。然而，LUB(B1)=c。 (b) 因为B2的下界是c，a

26、和b，所以易得GLB(B2)=c, B2的上界是f，g和h。因为f和g不是可比的，所以推出B2没有最小上界。 定理3 设(A，)是一个偏序集，那么A的一个子集B至多有一个LUB和一个GLB。 证明 类似于定理2的证明。,34,用A的哈塞图的观点对有限偏序集A上的LUB和GLB做一些解释。设B=b1，b2，, br，如果a=LUB(B)，那么a是通过向上道路从b1，b2，, br可能到达的第一个顶点。类似地，如果a=GLB(B)，那么a是通过向下道路从b1，b2，br可能到达的第一个顶点。 例10 设A=1，2，3，4，5，11是偏序集，它的哈塞图如图6.25所示，如果LUB和GLB存在的话，求

27、B=6，7，10的LUB和GLB。,35,解 从顶点6，7和10搜索所有向上的道路，可以发现LUB(B)=10。类似地，从6，7和10通过检查所有向下的道路，可以发现GLB(B)=4。,图 6.25,定理4 假设(A，)和(A，)是在同构f：AA下的同构偏序集。 (a) 如果a是(A, )的一个极大(极小)元，那么f(a)是(A，)的一个极大(极小)元。 (b) 如果a是(A，)的最大(最小)元，那么f(a)是(A，)的最大(最小)元。 (c) 如果a是A的子集B的一个上界(下界，最小上界，最大下界)，那么f(a)是A的子集 f(B)的一个上界(下界，最小上界，最大下界)。 (d) 如果(A，

28、)的每个子集有一个LUB(GLB)，那么(A，)的每个子集有一个LUB(GLB)。,36,例11 验证偏序集(A，)与(A，)不同构，它们的哈塞图分别如图6.26(a)和(b)所示。 解 因为(A，)有一个最大元a，而(A, )没有最大元，所以两个偏序集不是同构的。因为(A，)没有一个最小元，而(A, )有一个最小元，所以也能推出它们不是同构的。,37,图 6.26,6.3 格,格是任意两个元素所组成的子集a，b都有最小上界和最大下界的一个偏序集(L,)。用 ab表示LUB(a，b)并且称它为a和b的并。类似地，用ab表示GLB(a，b)并且称它为a和b的交。格结构经常出现在计算和数学应用中。

29、注意，格是如1.6节所描述的具有二元运算“并”与“交”的一种数学结构。 例1 设S是一个集合，L = P(S)，已看到包含 是L上的一个偏序。设A和B属于偏序集(L， )，那么AB是集合AB。为了看清这一点，注意AAB, BAB，如果AC和BC，那么得到ABC。类似地，可证明在(L，)中元素AB是集合AB。所以，L是一个格。,38,例2 考虑偏序集(Z+，)，对于Z+中的a和b，ab当且仅当a|b，于是L是一个格。在这个格中，a与b的并和交分别是它们的最小公倍数和最大公约数(见1.4节)，即 ab=LCM(a，b)，ab=GCD(a，b) 例3 设n是一个正整数，Dn是n的所有正因子的集合。那

30、么Dn在例2所考虑的整除关系下是一个格。因此，如果n=20，则有D20=1，2，4，5，10，20，D20的哈塞图如图6.39(a)所示。如果n=30，则有D30=1,2,3,5,6,10,15,30。D30的哈塞图如图6.39(b)所示。,39,例4 图6.40中的哪些哈塞图表示格？ 解 哈塞图(a)，(b)，(d)和(e)表示格。图(c)不表示一个格，因为f g不存在。图(f)不表示一个格，因为de和bc都不存在。图(g)不表示一个格，因为cd不存在。,40,例5 在6.1节的例4中已经看到，在集合A上所有等价关系所组成的集合 在集合包含偏序下是一个偏序集。现在能够推出 是一个格。等价关系

31、R和S的交是它们的交集RS，并且它们的并是它们的并集的传递闭包(RS) (见4.8节)。设(L，)是一个偏序集，(L，)是对偶偏序集。如果(L，)是一个格，可以证明(L，)也是一个格。事实上，对于L中任意a和b，在(L，)中a和b的最小上界等于(L，)中a和b的最大下界。类似地，在(L，)中a和b的最大下界等于(L，)中a和b的最小上界。如果L是一个有限集合，那么通过检验偏序集的哈塞图和它对偶的哈塞图，就很容易看到这一性质。,41,例6 设S是一个集合，L=P(S)，那么(L， )是一个格，它的对偶格是(L， )，这里 是“包含于”， 是“包含”。于是本例前面的讨论表明在偏序集(L， )中的并

32、AB是集合AB，交AB是集合AB。 定理1 如果(L1，)和(L2，)是格，那么(L，)是一个格，其中L=L1L2，L的偏序是积偏序。 证明 分别用1和1表示L1中的并和交，用2和2表示L2中的并和交。从6.1节的定理1可知，L是一个偏序集。现在需要证明如果(a1,b1), (a2,b2)L，那么(a1,b1)(a2,b2)和(a1,b1)(a2,b2)在L中存在。事实上，可以验证： (a1,b1)(a2,b2) = (a11a2, b12b2) (a1,b1)(a2,b2) = (a11a2, b12b2) 于是L是一个格。,42,例7 设L1和L2分别是由图6.41(a)和(b)给出的格，

33、那么L = L1L2是如图6.41(c)所示的格。 设(L，)是一个格，S是L的一个非空子集，如果当aS且bS时，有abS和abS，则称S是L的子格。,43,例8 n的所有正因子格Dn(见例3)是整除关系下(见例2)格Z+的一个子格。 例9 考虑如图6.42(a)所示的格L，则图6.42(b)所示的偏序子集Sb不是L的一个子格，因为ab Sb。图6.42(c)中的偏序子集Sc不是L的一个子格，因为ab Sc。然而，当把Sc自身视为一个偏序集时，它是一个格。如图6.42(d)所示的偏序子集Sd是L的一个子格。,44,同构的格,如果f：L1L2是从偏序集(L1，1)到偏序集(L2，2)的一个同构，

34、那么6.2节的定理4表明L1是一个格当且仅当L2是一个格。事实上，如果a和b是L1的元素，那么f(ab)=f(a)f(b)和f(ab) = f(a) f(b)。如果两个格作为偏序集是同构的，则称它们是同构的格。 例10 设L是格D6，L是在包含关系下的格P(S)，S=a，b，这些偏序集在6.1节的例16中已经讨论过，并且已证明它们是同构的。因此，由于两者都是格，所以它们是同构的格。,45,如果f：AB是从格(A，)到集合B的一一对应，那么可用函数f在B上定义偏序。如果b1和b2是在B中，那么有A的惟一元a1和惟一元a2使得b1=f(a1)和b2=f(a2)。 定义b1b2 (在B中)当且仅当a

35、1a2 (在A中)。如果A和B是有限的，那么能够从几何上描述这个过程如下。对(A，)构造哈塞图，于是每个符号a用B中的对应元f(a)取代，结果得到B上偏序的哈塞图。 当给出B上的偏序时，f将是从偏序集(A，)到偏序集(B，)的一个同构。为了看清这一点，注意到f已经被假设是一一对应。的定义说明对于A中任意的a1和a2，a1a2当且仅当f(a1)f(a2)。因此，f是一个同构。因为(A，)是一个格，所以(B，)也是格，且它们是同构的格。,46,例11 如果A是一个集合，设 是A上所有等价关系所组成的集合，是A上所有划分的集合。在5.1节的例13中，已构造了从 到的一一对应f。在6.1节的例4中，考

36、虑了在 上的偏序 。从这个偏序可用上面解释的f构造上的偏序。由构造可知，如果P1和P2是A的划分，R1和R2分别是对应于这些划分的等价关系，那么P1P2将意味着R1 R2。因为在例5中已证明( ， )是一个格，并且知道f是一个同构，所以得到(，)也是一个格。在第35题中可直接根据它们本身的划分描述偏序。,47,格的性质,在证明格的许多性质之前，回顾ab和ab的意义。 1aab且bab；ab是a和b的上界。 2若ac且bc，则abc；ab是a和b的最小上界。 1aba且abb；ab是a和b的下界。 2若ca且cb，则cab；ab是a和b的最大下界。,48,定理2 设L是一个格，那么对L中每个a和

37、b，有 (a) ab =b 当且仅当ab。 (b) ab=a 当且仅当ab。 (c) ab=a 当且仅当ab=b。 证明 (a) 假设ab=b，因为aab=b，所以有ab。反之，如果ab，那么因bb，则b是a和b的一个上界；因此，由最小上界的定义得到abb。因为ab是一个上界，bab，所以ab=b。 (b) 类似于(a)的证明，留给读者作为练习。 (c) 从(a)和(b)的证明即得证。,49,例12 设L是一个全序集，如果a,bL，那么或者ab或者ba。从定理2可知L是一个格，因为每对元素有最小上界和最大下界。定理3 设L是一个格，那么 1. 幂等性质 (a) aa = a (b) aa =

38、a 2. 交换性质 (a) ab = ba (b) ab = ba 3. 结合性质 (a) a(bc) = (ab)c (b) a(bc) = (ab)c 4. 吸收性质 (a) a(ab) = a (b) a(ab) = a 证明 1. 命题从LUB和GLB的定义可得到。 2. LUB和GLB的定义对a和b是对称的，所以结论成立。,50,3. (a) 从LUB的定义得到aa(bc)和bca(bc)。而且bbc和cbc，于是由传递性得ba(bc)和ca(bc)。因此，a(bc)是a和b的一个上界，所以由最小上界的定义有 aba(bc) 因为a(bc)是ab和c的一个上界，所以得到(ab)ca(

39、bc) 类似地有：a(bc)(ab)c，由的反对称性可知性质3(a)成立。 (b) 证明类似于第(a)部分，略去不证。 4. (a) 因为aba和aa，于是a是ab和a的一个上界，所以a(ab)a。另一方面，由LUB的定义有aa(ab)，所以a(ab) = a。 (b) 证明类似于第(a)部分，略去不证。,51,从性质3知道，可把a(bc)和(ab)c仅写作abc，类似地有abc，而且可把LUB(a1, a2, an)写作a1a2an，GLB(a1, a2,，an)写作a1a2an，因为可以用归纳法证明这些并和交的各项的分组是独立的。 定理4 设L是一个格，那么对于L中的每个a，b和c，有 1

40、如果ab，那么 (a) acbc(b) acbc 2ac和bc当且仅当abc。 3ca和cb当且仅当cab。 4如果ab和cd，那么 (a) acbd(b) acbd 证明 证明留作练习。,52,几种特殊类型的格,一个格L称为是有界的，如果它有最大元I和最小元0(见6.2节)。 例13 格Z+在整除偏序下(如例2中的定义)不是一个有界的格，因为它有最小元数1，但没有最大元。 例14 格Z在偏序下不是有界的，因为它既无最大元也无最小元。 例15 格P(S)（如例1所定义，它是集合S的所有子集）的集合是有界的。它的最大元是S，最小元是。 如果L是一个有界格，那么对所有aA，有 0aI，a0 = a

41、，a0=0 aI=I，aI=a,53,定理5 设L=a1,a2,an是一个有限格，那么L是有界的。 证明 L的最大元是a1a2an，L的最小元是a1a2an。 注意，定理5的证明是一个构造性证明。证明L有界是通过构造最大元和最小元完成的。 称格L是分配的，如果对L中的任意a, b和c，有下面的分配性质： 1a(bc) = (ab)(ac) 2a(bc) = (ab)(ac) 如果L不是分配的，则称L是非分配的。 当元素a,b或c中任意两个元素是相等的或者元素中任意一个是0或I时，可证明分配性质成立，将它留作一个练习。该结论可减少在证明分配性质成立时所必须检验的情形的数目。然而，分配性质的证明通

42、常是一项冗长乏味的任务。,54,例16 对于集合S，P(S)是分配格，因为并集和交集(分别为并和交)都满足如1.2节所给出的分配性质。 例17 如图6.43所示的格是分配的。因为可以通过从元素a, b, c和d中选出所有有序对来验证分配性质。 例18 证明：图6.44所示的格是非分配的。 证明 (a) 显然有 a(bc) = aI = a 而(ab)(ac) = b0 = b (b) 注意到a(bc) = aI = a 而(ab)(ac) = 00 = 0,55,定理6 格L是非分配的当且仅当它包含一个同构于例18中两个格之一的子格。 可通过检查L的哈塞图使定理6得到十分有效的使用。 设L是有

43、最大元I和最小元0的一个有界格，aL。一个元素aL称作a的补，如果 aa = I，aa = 0 注意：0=I, I=0。 例19 格L = P(S)中的每个元素有一个补，因为如果AL，那么它的补集 有性质A = S和A = ，即集合的补也是格L中的补。 例20 图6.44具有每个格中的每个元素均有补的性质。元素c在两种情况下有两个补a和b。,56,例21 考虑例3中讨论的格D20和D30，如图6.39所示。注意，在D30中每个元素有一个补。例如，如果a = 5，那么a = 6，然而在D20中的元素2和元素10没有补。 例20和21表明一个格中的元素a不一定有补，并且它可能有几个补。然而，对于一

44、个有界分配格，情况大为受限，正如下面定理所表明的那样。,57,定理7 设L是一个有界的分配格，如果一个补存在，那么它是惟一的。 证明 设a和a是元素aL的补，那么 aa=I ，aa=I, aa=0，aa=0 用分配律得到 a= a0= a(aa) = (aa)(aa) = I(aa) = aa 同样 a= a0= a(aa) = (aa)(aa) = I(aa) = aa 因此a = a。,58,定理7的证明是一个直接证明，但是在如何选择a和a的表达方式方面并不是很清楚。在这种证明中，含有某些尝试和错误，但是人们希望使用L是有界的和L是可分配的假设。另外一种证明方法见第36题。 一个格L称作有

45、补的，如果它是有界的并且L中的每个元素有一个补。 例22 格L = P(S)是有补的。注意在这种情况下，L中的每个元素有惟一的补，这一点能够直接看到或者通过定理7看到。 例23 在例20中所讨论的格是有补的(见图6.44)。在这种情况下，补不是惟一的。,59,6.4 有限布尔代数,本节讨论在计算机科学中有着大量应用的一类格。在6.3节的例6中已经看到，如果S是一个集合，L=P(S)， 是通常的包含关系，那么偏序集(L，)是一个格。这些格有许多非一般格所共有的性质。正因如此，它们很容易用来处理许多实际问题，并且在各种应用中起着非常重要的作用。 本节将仅限于考虑格(P(S)，)，其中S是一个有限集

46、合。从寻找所有本质上不同的例子开始。,60,定理1 如果S1=x1, x2, xn和S2=y1, y2,，yn是有n个元素的任意两个有限集合，那么格(P(S1)，)和(P(S2)，)是同构的。特别可以同样地画出它们的哈塞图。 证明 像图6.58所示的那样，把集合的元素排列起来，使得S1在S2上面，S1中的每个元素直接对应于S2中有相同标号的元素。对S1的每个子集A, 设f(A)是S2的子集，该子集是由与A中元素对应的所有元素组成的。图6.59给出了S1的一个特殊子集A和对应的S2的子集f(A)容易看到，刚才描述的函数f是从S1的子集到S2的子集的一一对应。同样显然，如果A和B是S1的任意子集,

47、 那么AB当且仅当f(A) f(B)。有关的细节省略。因此, 格(P(S1), )和 (P (S2), )是同构的。,61,该定理的一个基本要点是格(P(S)， )完全由偏序集的数|S|所决定，在任何情况下它不依赖于S中元素的性质。 例1 图6.60(a)和(b)分别给出了格(P(S)， )和(P(T)， )的哈塞图，其中S=a,b,c，T=2，3，5。从此图很容易看到两个格是同构的。事实上，一种可能的同构f:ST由下述给出：f(a)=2, f(b)=3, f(c)=5, f(a,b)=2,3, f(b,c)=3,5, f(a,c)=2,5, f(a,b,c)=2,3,5, f( )=.,62

48、,因此，对每个n=0,1,2, 只存在形如(P(S)，)的一类格。这种格仅依赖于n而不依赖于S，正如3.1节的例2所表示的那样，它有2n个元素。回顾1.3节，如果一个集合S有n个元素，那么S的所有子集可用长度为n的0和1的序列来表示。所以，可用这种序列给格(P(S)，)的哈塞图标号。这样做的目的就是使图不依赖于特殊集合S，并且强调它只依赖于n的事实。 例2 图6.60(c)给出了图6.60(a)和(b)中出现的图是如何用0和1的序列来标号的。这种标号同样能很好地用于描述图6.60(a)或(b)的格，或者从任意有三个元素的集合S产生的格(P(S)，)。,63,一个有n个元素的集合，如果对应它的格

49、的哈塞图是用长度为n的0和1的序列标号的(如上所述)，那么得到的格取名为Bn。在Bn中的偏序性质能够直接描述如下。如果x=a1a2an和y=b1b2bn是Bn的两个元素，那么 1xy当且仅当对k=1,2,n有akbk(按数0或1)。 2xy=c1c2cn, 这里ck=minak，bk。 3xy=d1d2dn，这里dk=maxak , bk。 4x有一个补x = z1z2zn，其中如果xk = 0，则zk =1，如果xk =1，则zk = 0。,64,这些命题的真实性可通过观察(Bn，)与(P(S), )是同构的这一事实看到，所以在Bn中的每个x和y对应于S中的子集A和B。于是xy，xy, xy

50、和x 分别对应于A B，AB，A B和 (集合补)(请验证)。对于n = 0,1,2,3,图6.61给出了格Bn的哈塞图。 由上可知，每个格(P(S)， )与Bn 同构，其中n=|S|。其他的格也可能与某个Bn 同构，因此它也具有Bn所具有的所有特殊性质。,65,例3 在6.1节的例17中，已考虑在整除偏序下6的所有正整数因子所组成的格D6, 它的哈塞图在该例中也已给出。现在可以看到，D6与B2是同构的。事实上，f：D6B2是一个同构，其中 f(1)=00，f(2)=10，f(3)=01，f(6)=11 所以可以给出以下定义。一个有限格称为一个布尔代数，如果对某个非负整数n它与Bn是同构的。因

51、此，每个Bn是一个布尔代数，所以每个格(P(S)，)也是一个布尔代数，其中S是一个有限集合。例3表明D6也是一个布尔代数。 在本节只讨论有限偏序集。然而，对于这种难以理解的限制，已注意到存在无限偏序集与格(P(S)，)(当然S是无限集合)共享所有相关的性质，但是它不与这些格中任何一个格同构。因此，把布尔代数的定义限制到有限的情况是非常必要的，它对于我们提到的应用也是足够的。,66,例4 考虑格D20和D30，它们分别是在整除偏序下20和30的所有正整数因子所组成的格。这些偏序集在6.3节的例3中已介绍过，它们的哈塞图在图6.39中已给出。因为D20有6个元素，对任意整数n0，62n，所以推出D

52、20不是布尔代数。偏序集D30有8个元素，因为8=23，所以它可能是一个布尔代数。通过图6.39(b)和图6.61的比较，可以看到D30与B3是同构的。事实上，由 f(1)=000, f(2)=100, f(3)=010, f(5)=001, f(6)=110, f(10)=101, f(15)=011, f(30)=111 定义的f：D30B3是一一对应，并且是一个同构。因此，D30是一个布尔代数。,67,对于某个非负整数n，如果一个有限格L不是包含2n个元素，那么L不可能是一个布尔代数。如果|L|=2n，则L可以是也可以不是一个布尔代数。如果L相对来说比较小，那么能够把它的哈塞图与Bn的哈

53、塞图进行比较。用这种方法在例4中已看到D30是一个布尔代数。然而，如果L很大，那么这种技巧是不现实的。在这种情况下，也许能够通过直接构造一个与某个Bn的同构或者等价地与(P(S)，)(S为某个有限集)的同构来证明L是一个布尔代数。例如，假设想要知道格Dn是否是一个布尔代数，就需要一种方法进行判断，无论n是多大。下面的定理给出了该问题的部分回答。,68,定理2 设n=p1p2pk，其中pi 是互不相同的素数，那么Dn 是一个布尔代数。 证明 设S=p1, p2, ，pk，如果TS，aT是T中素数的积，那么aT|n 。对S的某个子集T，n的任何因子一定具有形式aT(设a = 1)。读者可以证明，如

54、果V和T是S的子集，V T当且仅当av|aT。同样，从1.4节定理6的证明得到aVT = aVaT =GCD(aV, aT)和 aVT =aVaT=LCM(aV,aT)。因此，由f(T) =aT 给出的函数 fP(S)Dn是从P(S)到Dn的一个同构。因为P(S)是一个布尔代数，所以Dn是一个布尔代数。 例5 因为210=2357，66=2311，646=21719，所以由定理2得到 D210，D66和D646都是布尔代数。,69,对于其他非常大的格L，可以通过证明L的偏序没有所需要的性质来证明L不是一个布尔代数。一个布尔代数与某个Bn是同构的，所以它与某个格(P(S), )也是同构的。因此，

55、一个布尔代数L一定是一个有界格和补格(见6.3节)。换言之，它有一个与集合S对应的最大元I和与子集对应的最小元0。同样，L的每个元素x有一个补x。根据6.3节的例16，L也一定是分配格。于是对应原理(见6.1节)告诉人们下面的法则成立。 定理3(布尔代数的替换法则) 如果用替代，用替代，那么集合S上任意子集关于包含或成立的任何公式对于布尔代数L的任意元素将继续成立。,70,例6 如果L是任一布尔代数，x,y,zL，那么下面三条性质成立。 1(x ) =x， 对合性质 2(xy) = x y 德摩根定律 3(xy) =xy 由布尔代数的替换法则易知上述命题为真，因为它们对应的公式 1 = A 2

56、 = 3 = 对于集合S的任意子集A和B成立。,71,类似地，用替换法则能够列出任何布尔代数必定成立的其他性质。下面总结了布尔代数 (L，)的所有基本性质，每条性质的右边列出集合S的子集所对应的性质。假设x, y和z是L中的任意元素，A，B和C是S的任意子集。同样，I和0分别表示L的最大元和最小元。 1xy 当且仅当xy = y。 1A B 当且仅当AB = B。 2xy 当且仅当xy=x。 2A B 当且仅当AB=A。 3(a) xx=x。 3(a) AA=A。 (b) xx=x。 (b) AA=A。 4(a) xy =yx。 4(a) AB=BA。 (b) xy=yx。 (b) AB=BA

57、。,72,5.(a) x(yz)=(xy)z。 5.(a) A(BC)=(AB)C。 (b) x(yz)=(xy)z。 (b) A(BC)=(AB)C。 6(a) x(xy)= x。 6(a) A(AB) =A。 (b) x(xy)= x。 (b) A(AB) =A。 7对L中的所有x, 0 xI。 7对所有AP(S), AS。 8(a) x0=x。 8(a) A =A。 (b) x0=0。 (b) A =。 9(a) xI =I。 9(a) AS= S。 (b) xI=x。 (b) AS=A。,73,10(a) x(yz) = (xy)(xz)。 (b) x(yz) =(xy)(xz)。 1

58、0(a) A(BC)=(AB)(AC)。 (b) A(BC)=(AB)(AC)。 11每个元素x有惟一的补x满足： (a) xx =I。 (b) xx = 0。 11每个元素A有惟一的补 满足： (a) A =S。 (b) A =。 12(a) 0 = I。 12(a) =S。 (b) I =0。 (b) =。 13(x ) = x。 13 =A。,74,14(a) (xy) = xy。 14(a) = 。 (b) (xy) = xy。 (b) = 。 因此，要证明一个格L不是一个布尔代数，可以通过证明它不具有上面性质中的一条或更多条来实现。 例7 证明：如图6.62所示的哈塞图的格不是一个布

59、尔代数。 证明 元素a和e都是c的补，即：它们两个关于元素c都满足性质11(a)和11(b)。但是性质11要求这样的元素在布尔代数中是惟一的。因此，所给出的格不可能是一个布尔代数。,75,例8 证明：如果n是一个正整数，p是一个素数并且p2|n，那么Dn不是布尔代数。 解 假设p2|n，所以对某个正整数q，有n = p2q。因为p也是n的一个因子，所以p是Dn的一个元素。因此，由上面给出的评述可知，如果Dn是一个布尔代数，那么p一定有补p。于是GCD(p, p )=1和LCM(p, p) = n。由1.4节的定理6得pp=n，所以p= n /p = pq。从而证明了GCD(p, pq) = 1，这是不可能的，