罗平翻译的高等离散结构课件

第六章序关系与序结构6.1偏序集偏序集：在某个集合A上的关系R如果是自反的、反对称的和传递的，那么称R是一个偏序。集合A与偏序R一起称作偏序集，用(A，R)表示。如果不会产生混淆的话，那么可以把偏序集简单地记成A而非(A，R)。例1设A是集合S的子集的集合，集合的包含关系

是A上的一个偏序，所以(A，)是一个偏序集。例2

设Z+是正整数集合，通常的关系≤(小于或等于)是Z+上的一个偏序。同样≥(大于或等于)也是Z+上的一个偏序。例3

整除关系(aRb当且仅当a | b)是Z+上的一个偏序。2例4

设是集合A上所有等价关系的集合，因为是由A

A的子集所组成的，所以在集合的包含偏序下是一个偏序集。如果R和S是A上的等价关系，那么某些性质可以用关系符号表示如下：RS当且仅当xRy推出对A中所有x,y有xSy，于是(，)是一个偏序集。例5

Z+上的关系<不是一个偏序，因为它不是自反的。例6

设R是集合A上一个偏序，R–1是R的逆关系，那么R–1也是一个偏序。为了看清这一点，回顾4.4节给出的自反性、反对称性和传递性的特征。如果R有这三种性质，那么∆R，R∩R–1∆，R2R，通过取逆有∆=∆–1R–1，R–1∩(R–1)–1=R–1∩R∆，(R–1)2R–1，所以，由4.4节可知，R–1是自反的、反对称的和传递的。因此，R–1也是一个偏序。偏序集(A，R–1)称为偏序集(A，R)的对偶，偏序R–1称为偏序R的对偶。3最熟悉的偏序是Z和R上的关系≤和≥。由于这个原因，当一般谈到集合A上的偏序R时，常常对R使用符号≤或≥，这使得R的性质更熟悉和更容易记忆。因此，读者可以把符号≤用来当作不同集合上许多不同的偏序。但不要误认为这些关系都是相同的或者它们是熟知的Z或R上的关系≤。如果需要同另一个偏序区别开来，也可以使用如≤1，≤，≥1，≥等符号来表示偏序。本书将遵守下面的约定，当(A，≤)是一个偏序集时，总是使用符号≥代替偏序≤–1，因此，(A，≥)将是对偶偏序集。类似地，偏序集(A，≤1)的对偶将用(A，≥1)表示，偏序集(B，≤)的对偶用(B，≥)表示。这种约定再一次使人想起熟悉的对偶偏序集(Z，≤)和(Z，≥)以及偏序集(R，≤)和(R，≥)。4如果(A，≤)是一个偏序集，对A的元素a和b，如果a≤b或b≤a，那么说a和b是可比的。注意，在偏序集中每一对元素不必都是可比的。例如，考虑例3中的偏序集，元素2和7不是可比的，因为27且72。因此，在偏序集中的“偏”字意味着某些元素可能不是可比的。如果在一个偏序集A中每一对元素都是可比的，则称A是一个全序集，偏序称为全序，也称A是一个链。例7

例2中的偏序集是全序集。5定理1

如果(A，≤)和(B，≤)是偏序集，那么(A

B，≤)是一个偏序集，它的偏序≤由下述定义：如果在A中a≤a和在B中b≤b，那么(a,b)≤(a,b)。注意，上面使用的符号≤表示三种不同的偏序。证明

如果(a,b)∈A

B，因为在A中有a≤a和在B中有b≤b，所以(a,b)≤(a,b)，从而≤在A

B中满足自反性质。现在假设(a,b)≤(a，b)和(a,b)≤(a,b)，其中a,a∈A，b,b∈B。于是在A中有

a≤a，a≤a且在B中有

b≤b,b≤b,因为A和B是偏序集，所以在A和B中，由偏序的反对称性推出a=a

和b=b，因此，≤在AB中满足反对称性。最后，假设(a,b)≤(a，b)和(a，b)≤(a,b)，其中a,a,a∈A且b,b,b∈B，那么a≤a且a≤a，所以，由A中偏序的传递性推出a≤a。类似地，b≤b且b≤b，所以由B中偏序的传递性推出b≤b。因此，(a,b)≤(a，b)，由此推出在AB中偏序的传递性成立，从而得到AB是一个偏序集。

6在如上笛卡儿积A×B上定义的偏序≤称作积偏序。设(A，≤)是一个偏序集，如果a≤b，但a≠b，则称a<b。现在假设(A，≤)和(B，≤)是偏序集，在定理1中已经在A×B上定义了积偏序。现在在A×B上定义另一个有用的偏序，用≺表示，它的定义如下：如果a<a,或者a=a且b≤b,那么(a,b)≺(a,b)，这种排序称为字典序。除第一个坐标“相等”的情况外，第一个坐标元素的排序起决定性作用而可以忽略第二个坐标的排序。如果(A，≤)和(B，≤)是全序集，那么在A×B上的字典序≺也是一个全序。7例8

设A= R，用通常的排序≤，那么平面R2=R×R给出了字典序，如图6.1所示。可以看到平面是由字典序所产生的全序，每条垂直线有通常的序，并且在该直线上的点比它右边的垂直线上的点小。因此，在图6.1中,p2≺p3,p1≺p2,p1≺p3。8图6.1字典序很容易扩展到笛卡儿积A1×A2×…×An：

当且仅当

或

和

或

，

和

或…

，

和

因此，第一个坐标完全决定了排序（除非它相等），在第一个坐标相等的情况下，考虑第二个坐标。如果再次相等，考虑第三个坐标，等等。9例9设S={a，b，…，z}是通常的字母表，采用通常的全序方法(a≤b，b≤c，…，y≤z)。于是S n=S×S×…×S(n个因子)能与长度为n的所有字集合等同。在S n上的字典序具有性质：如果w1≺w2(w1，w2∈S n)，那么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=a1a2…an和y=b1b2…bk属于S*并且n≤k，那么如果在Sn的字典序下有(a1，…，an)≺(b1，…，bk)，则称Sn中x≺y。10在上一自然段，使用了n个数组(a1,a2,…，an)∈S n，它实际上与字符串a1a2…an∈S*是长度为n的同一序列，只不过用不同的符号表示罢了。这种符号的不同是出于历史原因，在使用它们时依赖于上下文环境而转换。例10设S是{a，b，…，z}，按通常的次序，那么S*是任意长度的所有可能的“词”的集合，无论这些“词”是否有意义。因此，在S*中有help≺helping，因为在S4中，help≺help。类似地，因为在S6中helper≺helping，所以helper≺helping。正如例子help≺helping所示，排序包括了词头排序，即：任意一个词比它的所有词头(开始部分)大，这也是字典中词的出现方法。11因为一个偏序是一种关系，所以可考虑在有限集合上任意偏序的有向图。将看到偏序的有向图表示方法比那些一般的关系有向图表示方法更简单。下面的定理提供了该方向的第一个结果。定理2偏序的有向图中没有长度比1大的环。证明

假设在集合A上偏序≤的有向图包含一个长度为n≥2的环，那么存在互不相同的元素a1，a2，…，an∈A，使得a1≤a2,a2≤a3,…,an–1≤an,an≤a1由偏序的传递性，使用n–1次得到a1≤an。由反对称性有an≤a1和a1≤an，从而推出an=a1，这与假设a1，a2，…，an互不相同是矛盾的。12哈塞图设A是一个有限集合，定理2表明A上偏序的有向图只有长度为1的环。事实上，因为偏序是自反的，所以在偏序的有向图中每个顶点被包含在长度为1的环中。为了简化这件事情，将去掉有向图中所有这种环。因此，在图6.2(a)中表示的有向图将画成如图6.2(b)所示的图。13图6.2我们也去掉由传递性推出的所有边。因此，如果a≤b且b≤c，那么得到a≤c。在这种情况下，省略从a到c的边，但要画从a到b和从b到c的边。例如，图6.3(a)所示的有向图将画成图6.3(b)所示的图。还约定用所有朝上的边来画偏序的有向图，以致箭头可以从边上省略。最后，用点取代圆圈来表示顶点。因此，图6.4所示的图给出了图6.2(a)所示有向图的最终形式。这样的偏序图比它的有向图简单得多，称作偏序集上偏序的哈塞图。因为哈塞图完全描述了有关的偏序，所以它是一种非常有用的工具。14图6.3图6.4例11设A={1，2，3，4，12}，考虑A上的整除性偏序，即：如果a,bA，a≤b当且仅当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，≤)是一个偏序集，(A，≥)是对偶偏序集,那么(A,≥)的哈塞图恰好是把(A，≤)的哈塞图颠倒过来。例13

图6.9(a)给出了偏序集(A，≤)的哈塞图，其中A={a，b，c，d，e，f }。图6.9(b)给出了对偶偏序集(A，≥)的哈塞图。注意，像刚才提到的那样，这些图能够通过把另一个图颠倒过来而得到。17图6.9拓扑排序如果A是具有偏序≤的一个偏序集，有时需要对集合A找一个全序

，使得该全序只不过是已知偏序在如下意义的一个扩展：如果a≤b，那么a≺b。构造如≺的一个全序的过程称作拓扑排序。该问题产生于当人们必须把有限偏序集A输入计算机时。A中的元素必须以某种次序被输入，并且也许要求它们输入后保持偏序，即：如果a≤b，那么a是在b之前被输入。拓扑排序≺将给出遇到这种情况时元素输入的次序。18例14

对于哈塞图如图6.10所示的偏序集，给出一个拓扑排序。解

显然如图6.11(a)所示的哈塞图的偏序≺是一个全序。容易看到每一对元素用≤排序也就是用≺排序，所以≺是偏序≤的拓扑排序。图6.11(b)和(c)给出了此问题的另外两种解答。

19图6.10图6.11同构设(A，≤)和(A，≤)是偏序集，f ：A→A是A与A之间的一一对应。如果对于A中任意的a和b，a≤b当且仅当

f(a)≤f (b)，那么称函数

f是从(A，≤)到(A，≤)的一个同构。如果

f：A→A是一个同构，那么称(A，≤)和(A，≤)是同构的偏序集。例15

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

20假设f：A→A是从偏序集(A，≤)到偏序集(A，≤)的一个同构。还假设B是A的一个子集，B=f (B)是对应的A的子集。那么从同构的定义可以看到下面的原理必定成立。定理3(对应原理)如果B的元素相互间或者与A的其他元素间有某种性质，并且这种性质可完全根据关系≤定义，那么B的元素一定具有由≤定义的完全相同的性质。21例16

设(A，≤)是偏序集，它的哈塞图如图6.12所示。假设f是从(A，≤)到某个其他偏序集(A，≤)的一个同构。首先注意对A中任意x有d≤x(稍后将d这样的元称为A的“最小元”)，那么在A中对应元f (d)一定满足性质：对A中的所有y有f (d)≤y。作为另一个例子，注意ab和b

a，这种元素对称为在A中是不可比的。于是从对应原理得到f(a)和f(b)在A中一定也是不可比的。

22图6.12确切地说，设(A，≤)和(A，≤)是有限偏序集，f：A→A是一一对应，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：A→A定义如下f(1)=，f(2)={a}，f(3)={b}，f(6)={a，b}那么容易看到f是一一对应。如果哈塞图的每个符号a∈A用f (a)代替，结果如图6.13(b)所示。因为很显然这是(A，≤)的一个哈塞图，所以函数

f是一个同构。24图6.136.2偏序集的极值元在一个偏序集中，某些元素对于偏序集的许多性质和应用具有特殊的重要性。在这一节讨论这些元素，在稍后几节可以看到它们所起的重要作用。本节考虑一个偏序集(A，≤)。一个元素a∈A，如果在A中不存在任何元素c使得a<c，则称a是A的一个极大元。一个元素b∈A，如果在A中不存在任何元素c使得c<b，则称b是A的一个极小元。由此立即得到：如果(A，≤)是一个偏序集，那么(A，≥)是它的对偶偏序集。元素a∈A是(A，≥)的一个极大元当且仅当a是(A，≤)的一个极小元。同样，a是(A，≥)的一个极小元当且仅当它是(A，≤)的一个极大元。25例1

考虑偏序集A，它的哈塞图如图6.22所示。元素a1,a2和a3是A的极大元，元素b1,b2和b3是极小元。注意，因为在b2与b3之间不存在任何直线，所以可以断定既没有b3≤b2也没有b2≤b3。

图6.2226例2

设A是有通常偏序≤的非负实数偏序集，那么0是A的极小元，A不存在极大元。例3

偏序集Z具有通常的偏序≤，它没有极大元也没有极小元。

定理1

设A是有偏序≤的有限非空偏序集，那么A至少有一个极大元和一个极小元。证明

设a是A的任意一个元素，如果a不是极大元，那么能够找到一个元a1∈A，使得a<a1；如果a1不是极大元，那么能够找到一个元a2∈A，使得a1<a2。因为A是有限集，所以这种推理不能无限次继续下去。因此，最终获得有限链：a<a1<a2<…<ak–1<ak，它不能再扩充了。因此，对任意b∈A，不能有ak<b，所以ak是(A，≤)的一个极大元。同理可得对偶偏序集(A，≥)有一个极大元，所以(A，≤)有一个极小元。27用极小元的概念，能够为已知有限偏序集(A,≤)给出一种求拓扑排序的算法。首先注意如果a∈A且B=A–{a}，那么B也是≤在B×B限制下的一个偏序集(见4.2节)。于是得到如下的算法，该算法产生一个名为SORT的线性数组。假设SORT是按递增下标排序，即：SORT[1]SORT[2]…，那么用这种方式定义A上的关系

是(A，≤)的一种拓扑排序。算法找有限偏序集(A，≤)的拓扑排序。步骤1：选择A的一个极小元a。步骤2：使a成为SORT的下一项并且用A–{a}代替A。步骤3：重复步骤1和步骤2直到A={}。28例4

设A={a,b,c,d,e}，A上偏序≤的哈塞图如图6.23(a)所示，该偏序集的一个极小元是标号为d的顶点(也可选e)。把d放入SORT[1]中，并且在图6.23(b)中给出A–{d}的哈塞图。新A的一个极小元是e，所以e成为SORT[2]，A–{e}如图6.23(c)所示。这个过程继续下去，直至用完A中元素为止，并且填充SORT。图6.23(f)给出了全部数组SORT和对应于SORT的偏序集的哈塞图。这就是(A，≤)的一个拓扑排序。29图6.23一个元素a∈A，如果对所有x∈A有x≤a，则称a是A的最大元。一个元素a∈A，如果对所有x∈A有a≤x，则称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

一个偏序集至多有一个最大元也至多有一个最小元。证明

假设a和b是偏序集A的最大元，那么，由于b是一个最大元，所以有a≤b。类似地，由于a是一个最大元，所以有b≤a。因此，由反对称性质得到a=b，故如果偏序集有一个最大元，那么它只有一个这样的元。因为对所有偏序集这一事实都为真，所以对偶偏序集(A，≥)至多有一个最大元，故(A，≤)也至多有一个最小元。

一个偏序集的最大元，如果存在的话，用I表示，它常称作单位元。类似地，一个偏序集的最小元，如果存在的话，用0表示，它常称作零元。考虑某个偏序集A和A的子集B，一个元素a∈A，如果对所有b∈B有b≤a，则称a是B的一个上界。如果对所有b∈B有a≤b，则称a是B的一个下界。31例8

考虑偏序集A={a，b，c，d，e，f，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的一个子集。如果一个元a∈A是B的上界并且当a是B的一个上界时，有a≤a，则称a是B的最小上界(LUB(B))。因此，如果对所有b∈B，有b≤a并且如果当a∈A也是B的一个上界时，那么a≤a，则a=LUB(B)。类似地，如果一个元a∈A是B的一个下界，并且当a是B的一个下界时，a≤a，则称a是B的最大下界(GLB(B))。因此，如果对所有b∈B有a≤b，并且当a∈A也是B的一个下界时，有a≤a，那么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和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存在的话，求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：A→A下的同构偏序集。(a)如果a是(A,≤)的一个极大(极小)元，那么f (a)是(A，≤)的一个极大(极小)元。(b)如果a是(A，≤)的最大(最小)元，那么f (a)是(A，≤)的最大(最小)元。(c)如果a是A的子集B的一个上界(下界，最小上界，最大下界)，那么f (a)是A的子集

f (B)的一个上界(下界，最小上界，最大下界)。(d)如果(A，≤)的每个子集有一个LUB(GLB)，那么(A，≤)的每个子集有一个LUB(GLB)。36例11

验证偏序集(A，≤)与(A，≤)不同构，它们的哈塞图分别如图6.26(a)和(b)所示。解

因为(A，≤)有一个最大元a，而(A,≤)没有最大元，所以两个偏序集不是同构的。因为(A，≤)没有一个最小元，而(A,≤)有一个最小元，所以也能推出它们不是同构的。37图6.266.3格格是任意两个元素所组成的子集{a，b}都有最小上界和最大下界的一个偏序集(L,≤)。用

ab表示LUB({a，b})并且称它为a和b的并。类似地，用ab表示GLB({a，b})并且称它为a和b的交。格结构经常出现在计算和数学应用中。注意，格是如1.6节所描述的具有二元运算“并”与“交”的一种数学结构。例1

设S是一个集合，L=P(S)，已看到包含

是L上的一个偏序。设A和B属于偏序集(L，)，那么AB是集合A∪B。为了看清这一点，注意AA∪B,BA∪B，如果AC和BC，那么得到A∪BC。类似地，可证明在(L，)中元素AB是集合A∩B。所以，L是一个格。38例2

考虑偏序集(Z+，≤)，对于Z+中的a和b，a≤b当且仅当a | b，于是L是一个格。在这个格中，a与b的并和交分别是它们的最小公倍数和最大公约数(见1.4节)，即ab=LCM(a，b)，ab=GCD(a，b) 例3

设n是一个正整数，Dn是n的所有正因子的集合。那么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)不表示一个格，因为fg不存在。图(f)不表示一个格，因为de和bc都不存在。图(g)不表示一个格，因为cd不存在。40例5

在6.1节的例4中已经看到，在集合A上所有等价关系所组成的集合

在集合包含偏序下是一个偏序集。现在能够推出

是一个格。等价关系R和S的交是它们的交集R∩S，并且它们的并是它们的并集的传递闭包(R∪S)

(见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，)中的并A∨B是集合A∩B，交A∧B是集合A∪B。

定理1

如果(L1，≤)和(L2，≤)是格，那么(L，≤)是一个格，其中L=L1×L2，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)=(a1∨1a2,b1∨2b2)(a1,b1)∧(a2,b2)=(a1∧1a2,b1∧2b2)于是L是一个格。42例7

设L1和L2分别是由图6.41(a)和(b)给出的格，那么L=L1×L2是如图6.41(c)所示的格。设(L，≤)是一个格，S是L的一个非空子集，如果当a∈S且b∈S时，有a∨b∈S和a∧b∈S，则称S是L的子格。

43例8

n的所有正因子格Dn (见例3)是整除关系下(见例2)格Z+的一个子格。

例9

考虑如图6.42(a)所示的格L，则图6.42(b)所示的偏序子集Sb不是L的一个子格，因为a∧b

Sb。图6.42(c)中的偏序子集Sc不是L的一个子格，因为a∨b

Sc。然而，当把Sc自身视为一个偏序集时，它是一个格。如图6.42(d)所示的偏序子集Sd是L的一个子格。44同构的格如果f：L1→L2是从偏序集(L1，≤1)到偏序集(L2，≤2)的一个同构，那么6.2节的定理4表明L1是一个格当且仅当L2是一个格。事实上，如果a和b是L1的元素，那么f (a∧b)=f (a)∧f (b)和f (a∨b)=f (a)∨f (b)。如果两个格作为偏序集是同构的，则称它们是同构的格。例10

设L是格D6，L是在包含关系下的格P(S)，S={a，b}，这些偏序集在6.1节的例16中已经讨论过，并且已证明它们是同构的。因此，由于两者都是格，所以它们是同构的格。

45如果f：A→B是从格(A，≤)到集合B的一一对应，那么可用函数f在B上定义偏序≤。如果b1和b2是在B中，那么有A的惟一元a1和惟一元a2使得b1=f (a1)和b2=f (a2)。定义b1≤b2(在B中)当且仅当a1≤a2(在A中)。如果A和B是有限的，那么能够从几何上描述这个过程如下。对(A，≤)构造哈塞图，于是每个符号a用B中的对应元f (a)取代，结果得到B上偏序≤的哈塞图。当给出B上的偏序≤时，f将是从偏序集(A，≤)到偏序集(B，≤)的一个同构。为了看清这一点，注意到f已经被假设是一一对应。≤的定义说明对于A中任意的a1和a2，a1≤a2当且仅当f (a1)≤f (a2)。因此，f是一个同构。因为(A，≤)是一个格，所以(B，≤)也是格，且它们是同构的格。46例11

如果A是一个集合，设

是A上所有等价关系所组成的集合，∏是A上所有划分的集合。在5.1节的例13中，已构造了从

到∏的一一对应f。在6.1节的例4中，考虑了在

上的偏序

。从这个偏序可用上面解释的f构造∏上的偏序≤。由构造可知，如果P 1和P 2是A的划分，R1和R2分别是对应于这些划分的等价关系，那么P 1≤P 2将意味着R1R2。因为在例5中已证明(，)是一个格，并且知道f是一个同构，所以得到(∏，≤)也是一个格。在第35题中可直接根据它们本身的划分描述偏序≤。47格的性质在证明格的许多性质之前，回顾a∨b和a∧b的意义。1．a≤a∨b且b≤a∨b；a∨b是a和b的上界。2．若a≤c且b≤c，则a∨b≤c；a∨b是a和b的最小上界。1．a∧b≤a且a∧b≤b；a∧b是a和b的下界。2．若c≤a且c≤b，则c≤a∧b；a∧b是a和b的最大下界。48定理2

设L是一个格，那么对L中每个a和b，有(a)a∨b=b

当且仅当a≤b。(b)a∧b=a

当且仅当a≤b。(c)a∧b=a

当且仅当a∨b=b。证明(a)假设a∨b=b，因为a≤a∨b=b，所以有a≤b。反之，如果a≤b，那么因b≤b，则b是a和b的一个上界；因此，由最小上界的定义得到a∨b≤b。因为a∨b是一个上界，b≤a∨b，所以a∨b=b。(b)类似于(a)的证明，留给读者作为练习。(c)从(a)和(b)的证明即得证。49例12

设L是一个全序集，如果a,b∈L，那么或者a≤b或者b≤a。从定理2可知L是一个格，因为每对元素有最小上界和最大下界。定理3

设L是一个格，那么1.幂等性质(a)a∨a=a(b)a∧a=a2.交换性质(a)a∨b=b∨a(b)a∧b=b∧a3.结合性质(a)a∨(b∨c)=(a∨b)∨c(b)a∧(b∧c)=(a∧b)∧c4.吸收性质(a)a∨(a∧b)=a(b)a∧(a∨b)=a证明1.命题从LUB和GLB的定义可得到。2.LUB和GLB的定义对a和b是对称的，所以结论成立。503.(a)从LUB的定义得到a≤a∨(b∨c)和b∨c≤a∨(b∨c)。而且b≤b∨c和c≤b∨c，于是由传递性得b≤a∨(b∨c)和c≤a∨(b∨c)。因此，a∨(b∨c)是a和b的一个上界，所以由最小上界的定义有

a∨b≤a∨(b∨c)因为a∨(b∨c)是a∨b和c的一个上界，所以得到(a∨b)∨c≤a∨(b∨c)类似地有：a∨(b∨c)≤(a∨b)∨c，由≤的反对称性可知性质3(a)成立。(b)证明类似于第(a)部分，略去不证。

4.(a)因为a∧b≤a和a≤a，于是a是a∧b和a的一个上界，所以a∨(a∧b)≤a。另一方面，由LUB的定义有a≤a∨(a∧b)，所以a∨(a∧b)=a。(b)证明类似于第(a)部分，略去不证。51从性质3知道，可把a∨(b∨c)和(a∨b)∨c仅写作a∨b∨c，类似地有a∧b∧c，而且可把LUB({a1,a2,…,an})写作a1∨a2∨…∨an，GLB({a1,a2,…，an})写作a1∧a2∧…∧an，因为可以用归纳法证明这些并和交的各项的分组是独立的。定理4

设L是一个格，那么对于L中的每个a，b和c，有1．如果a≤b，那么(a)a∨c≤b∨c (b)a∧c≤b∧c2．a≤c和b≤c当且仅当a∨b≤c。3．c≤a和c≤b当且仅当c≤a∧b。4．如果a≤b和c≤d，那么(a)a∨c≤b∨d (b)a∧c≤b∧d证明

证明留作练习。52几种特殊类型的格一个格L称为是有界的，如果它有最大元I和最小元0(见6.2节)。例13

格Z+在整除偏序下(如例2中的定义)不是一个有界的格，因为它有最小元——数1，但没有最大元。

例14

格Z在偏序≤下不是有界的，因为它既无最大元也无最小元。

例15

格P(S)（如例1所定义，它是集合S的所有子集）的集合是有界的。它的最大元是S，最小元是。

如果L是一个有界格，那么对所有a∈A，有0≤a≤I，a∨0=a，a∧0=0a∨I=I，a∧I=a53定理5

设L={a1,a2,…,an}是一个有限格，那么L是有界的。证明

L的最大元是a1∨a2∨…∨an，L的最小元是a1∧a2∧…∧an。

注意，定理5的证明是一个构造性证明。证明L有界是通过构造最大元和最小元完成的。称格L是分配的，如果对L中的任意a,b和c，有下面的分配性质：1．a∧(b∨c)=(a∧b)∨(a∧c)2．a∨(b∧c)=(a∨b)∧(a∨c)如果L不是分配的，则称L是非分配的。当元素a,b或c中任意两个元素是相等的或者元素中任意一个是0或I时，可证明分配性质成立，将它留作一个练习。该结论可减少在证明分配性质成立时所必须检验的情形的数目。然而，分配性质的证明通常是一项冗长乏味的任务。54例16

对于集合S，P(S)是分配格，因为并集和交集(分别为并和交)都满足如1.2节所给出的分配性质。

例17

如图6.43所示的格是分配的。因为可以通过从元素a,b,c和d中选出所有有序对来验证分配性质。

例18

证明：图6.44所示的格是非分配的。证明

(a)显然有

a∧(b∨c)=a∧I=a

而(a∧b)∨(a∧c)=b∨0=b(b)注意到a∧(b∨c)=a∧I=a而(a∧b)∨(a∧c)=0∨0=055定理6

格L是非分配的当且仅当它包含一个同构于例18中两个格之一的子格。可通过检查L的哈塞图使定理6得到十分有效的使用。设L是有最大元I和最小元0的一个有界格，a∈L。一个元素a∈L称作a的补，如果a∨a=I，a∧a=0注意：0=I,I=0。例19

格L=P(S)中的每个元素有一个补，因为如果A∈L，那么它的补集

有性质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不一定有补，并且它可能有几个补。然而，对于一个有界分配格，情况大为受限，正如下面定理所表明的那样。57定理7

设L是一个有界的分配格，如果一个补存在，那么它是惟一的。证明

设a和a是元素a∈L的补，那么a∨a=I

，a∨a=I,a∧a=0，a∧a=0用分配律得到a=a ∨0=a ∨(a∧a )=(a ∨a)∧(a ∨a )=I∧(a ∨a )=a ∨a 同样a=a∨0=a∨(a∧a )=(a ∨a)∧(a ∨a ) =I∧(a ∨a )=a ∨a 因此a=a 。58定理7的证明是一个直接证明，但是在如何选择a

和a

的表达方式方面并不是很清楚。在这种证明中，含有某些尝试和错误，但是人们希望使用L是有界的和L是可分配的假设。另外一种证明方法见第36题。一个格L称作有补的，如果它是有界的并且L中的每个元素有一个补。例22

格L=P(S)是有补的。注意在这种情况下，L中的每个元素有惟一的补，这一点能够直接看到或者通过定理7看到。

例23

在例20中所讨论的格是有补的(见图6.44)。在这种情况下，补不是惟一的。

596.4有限布尔代数本节讨论在计算机科学中有着大量应用的一类格。在6.3节的例6中已经看到，如果S是一个集合，L=P(S)，

是通常的包含关系，那么偏序集(L，)是一个格。这些格有许多非一般格所共有的性质。正因如此，它们很容易用来处理许多实际问题，并且在各种应用中起着非常重要的作用。本节将仅限于考虑格(P(S)，)，其中S是一个有限集合。从寻找所有本质上不同的例子开始。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的任意子集,那么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 : S→T由下述给出：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因此，对每个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个元素的集合，如果对应它的格的哈塞图是用长度为n的0和1的序列标号的(如上所述)，那么得到的格取名为Bn。在Bn中的偏序性质能够直接描述如下。如果x=a1a2…an和y=b1b2…bn是Bn的两个元素，那么1．x≤y当且仅当对k=1,2,…,n有ak≤bk(按数0或1)。2．x∧y=c1c2…cn,这里ck=min{ak，bk}。3．x∨y=d1d2…dn，这里dk = max{ak,bk}。4．x有一个补x'=z1z2…zn，其中如果xk=0，则zk=1，如果xk=1，则zk=0。64这些命题的真实性可通过观察(Bn，≤)与(P(S),)是同构的这一事实看到，所以在Bn中的每个x和y对应于S中的子集A和B。于是x≤y，x∧y,x∨y和x'

分别对应于AB，A∩B，AB和(集合补)(请验证)。对于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：D6→B2是一个同构，其中

f (1)=00，f (2)=10，f (3)=01，f (6)=11所以可以给出以下定义。一个有限格称为一个布尔代数，如果对某个非负整数n它与Bn是同构的。因此，每个Bn是一个布尔代数，所以每个格(P(S)，)也是一个布尔代数，其中S是一个有限集合。例3表明D6也是一个布尔代数。在本节只讨论有限偏序集。然而，对于这种难以理解的限制，已注意到存在无限偏序集与格(P(S)，)(当然S是无限集合)共享所有相关的性质，但是它不与这些格中任何一个格同构。因此，把布尔代数的定义限制到有限的情况是非常必要的，它对于我们提到的应用也是足够的。66例4考虑格D20和D30，它们分别是在整除偏序下20和30的所有正整数因子所组成的格。这些偏序集在6.3节的例3中已介绍过，它们的哈塞图在图6.39中已给出。因为D20有6个元素，对任意整数n≥0，6≠2n，所以推出D20不是布尔代数。偏序集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：D30→B3是一一对应，并且是一个同构。因此，D30是一个布尔代数。67对于某个非负整数n，如果一个有限格L不是包含2n个元素，那么L不可能是一个布尔代数。如果|L|=2n，则L可以是也可以不是一个布尔代数。如果L相对来说比较小，那么能够把它的哈塞图与Bn的哈塞图进行比较。用这种方法在例4中已看到D30是一个布尔代数。然而，如果L很大，那么这种技巧是不现实的。在这种情况下，也许能够通过直接构造一个与某个Bn的同构或者等价地与(P(S)，)(S为某个有限集)的同构来证明L是一个布尔代数。例如，假设想要知道格Dn是否是一个布尔代数，就需要一种方法进行判断，无论n是多大。下面的定理给出了该问题的部分回答。68定理2

设n=p1p2…pk，其中pi

是互不相同的素数，那么Dn

是一个布尔代数。证明

设S={p1,p2,…，pk}，如果TS，aT是T中素数的积，那么aT|n

。对S的某个子集T，n的任何因子一定具有形式aT(设a=1)。读者可以证明，如果V和T是S的子集，VT当且仅当av|aT。同样，从1.4节定理6的证明得到aV∩T=aV∧aT=GCD(aV,aT)和

aV∪T=aV∨aT=LCM(aV, aT)。因此，由f (T)=aT给出的函数

f∶P(S)→Dn是从P(S)到Dn的一个同构。因为P(S)是一个布尔代数，所以Dn是一个布尔代数。例5

因为210=2×3×5×7，66=2×3×11，646=2×17×19，所以由定理2得到

D210，D66和D646都是布尔代数。

69对于其他非常大的格L，可以通过证明L的偏序没有所需要的性质来证明L不是一个布尔代数。一个布尔代数与某个Bn是同构的，所以它与某个格(P(S),)也是同构的。因此，一个布尔代数L一定是一个有界格和补格(见6.3节)。换言之，它有一个与集合S对应的最大元I和与子集

对应的最小元0。同样，L的每个元素x有一个补x'。根据6.3节的例16，L也一定是分配格。于是对应原理(见6.1节)告诉人们下面的法则成立。定理3(布尔代数的替换法则)如果用∧替代∩，用∨替代∪，那么集合S上任意子集关于包含∪或∩成立的任何公式对于布尔代数L的任意元素将继续成立。70例6

如果L是任一布尔代数，x,y,z∈L，那么下面三条性质成立。1．(x')'=x，

对合性质2．(x∧y)'=x'∨y'

德·摩根定律3．(x∨y)'=x'∧y'由布尔代数的替换法则易知上述命题为真，因为它们对应的公式1'．=A2'．=∪

3'．=∩

对于集合S的任意子集A和B成立。

71类似地，用替换法则能够列出任何布尔代数必定成立的其他性质。下面总结了布尔代数(L，≤)的所有基本性质，每条性质的右边列出集合S的子集所对应的性质。假设x,y和z是L中的任意元素，A，B和C是S的任意子集。同样，I和0分别表示L的最大元和最小元。1．x≤y

当且仅当x∨y=y。1'．AB

当且仅当A∪B=B。2．x≤y

当且仅当x∧y=x。2'．AB

当且仅当A∩B=A。3．(a)x∨x=x。 3'．(a)A∪A=A。(b)x∧x=x。 (b)A∩A=A。4．(a)x∨y=y∨x。 4'．(a)A∪B=B∪A。(b)x∧y=y∧x。 (b)A∩B=B∩A。725.(a)x∨(y∨z)=(x∨y)∨z。5'.(a)A∪(B∪C)=(A∪B)∪C。(b)x∧(y∧z)=(x∧y)∧z。(b)A∩(B∩C)=(A∩B)∩C。6．(a)x∨(x∧y)=x。6'．(a)A∪(A∩B)=A。(b)x∧(x∨y)=x。(b)A∩(A∪B)=A。7．对L中的所有x,0≤x≤I。7'．对所有AP(S),AS。8．(a)x∨0=x。 8'．(a)A∪=A。(b)x∧0=0。 (b)A∩=。9．(a)x∨I=I。 9'．(a)A∪S =S。(b)x∧I=x。(b)A∩S=A。7310．(a)x∧(y∨z)=(x∧y)∨(x∧z)。(b)x∨(y∧z)=(x∨y)∧(x∨z)。

10'．(a)A∩(B∪C)=(A∩B)∪(A∩C)。

(b)A∪(B∩C)=(A∪B)∩(A∪C)。11．每个元素x有惟一的补x' 满足：

(a)x∨x'=I。(b)x∧x'=0。

11'．每个元素A有惟一的补

满足：(a)A∪=S。(b)A∩=。12．(a)0'=I。 12'．(a)=S。(b)I'=0。(b)=。13．(x')'=x。 13'．=A。7414．(a)(x∧y)'=x'∨y'。14'．(a)=∪

。(b)(x∨y)'=x'

∧y'。(b)=∩

。因此，要证明一个格L不是一个布尔代数，可以通过证明它不具有上面性质中的一条或更多条来实现。例7

证明：如图6.62所示的哈塞图的格不是一个布尔代数。证明

元素a和e都是c的补，即：它们两个关于元素c都满足性质11(a)和11(b)。但是性质11要求这样的元素在布尔代数中是惟一的。因此，所给出的格不可能是一个布尔代数。

75例8

证明：如果n是一个正整数，p是一个素数并且p2|n，那么Dn不是布尔代数。

解

假设p2|