离散数学电子教材3b(共29页).doc

《离散数学电子教材3b(共29页).doc》由会员分享，可在线阅读，更多相关《离散数学电子教材3b(共29页).doc（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上3.8 关系的闭包运算关系作为集合, 在其上已经定义了并、交、差、补、复合及逆运算。现在再来考虑一种新的关系运算关系的闭包运算，它是由已知关系，通过增加最少的序偶生成满足某种指定性质的关系的运算。 例如, 设，上的二元关系，则上含且最小的自反关系是：；上含且最小的对称关系是： ；上含且最小的传递关系是： 。定义3.8.1 设是上的二元关系，如果有另一个上的关系满足：（1）是自反的（对称的，传递的）；（2）；（3）对于任何上的自反的（对称的，传递的）关系，若，就有。则称关系为的自反（对称，传递） 闭包(Reflexive (Symmetric，Transitive) C

2、losure)，记作。显然，自反（对称，传递）闭包是包含的最小自反（对称，传递）关系。定理3.8.1 设是上的二元关系，那么（1）是自反的，当且仅当（2）是对称的，当且仅当（3）是传递的，当且仅当证明 （1）若是自反的，对任何包含的自反关系，有，故；若，根据闭包定义，必是自反的。（2）、（3）的证明完全类似。 下面讨论由给定关系，求取的方法。定理3.8.2 设是集合上的二元关系，则（1）；（2）（3），通常也记作。证明 （1）令，因为，故，于是在上是自反的。又即。若有自反关系且，显然有，于是 ，所以 。 （2）令，因为 所以是对称的。若是对称的且，则。当时，；当时，。因此 ，故 。（3）令，先

3、证是传递的。 ，则存在自然数，有 ，因此 ，所以，是传递的。显然，。若有传递关系且，则存在自然数，有 ，则 ，使得 ，因此，由于是传递关系，则，所以。故。例3.8.1 设，是上的二元关系，求。解 为了求得，先写出即继续这个运算有： 从以上例题中看到，若有限，譬如含有个元素，那么求取上二元关系的传递闭包不必计算到对的无限大次复合，而最多不超过次复合。定理3.8.3 设是含有个元素的集合，是上的二元关系，则存在一个正整数，使得证明 设，记。若，则存在整数，使得成立，既存在序列，有。设满足上述条件的最小大于，不妨，则序列中必有，使得或。不妨，此时序列就成为，这表明存在，其中，这与是最小的假设矛盾，所

4、以，不成立，即。所以 （）一般地，取，式中的给出了复合次数的上限。 例3.8.2 设，给定上的关系，求。解 所以 即 为计算元素较多的有限集合上二元关系的传递闭包， Warshall在1962年提出了一个有效的算法（假定集合含有个元素）：（） 置新矩阵：；（） 置：；（） 对，若（），则置：，；（） ：；（） 如果，则转到步骤（3），否则停止。例3.8.3 已知，求。 解 按照Warshall算法，从出发，只要遵循“置行查列遍寻真，见真行上析当今，行推列移下右再，行穷列尽闭包成”便可直接求得。 对集合上关系，首先将其关系矩阵赋予：而后的每后一次循环重复操作， 均在前一次操作结果的矩阵上进行。置

5、当今行为第1行，查看第1列中1，对有1的行进行改写，改写方法是：将当今行的元素与列中有1的行的元素分别做析取。对本例，时，第1列中只有，将第一行与第一行各对应元素进行逻辑加，仍记于第一行：；置当今行为第2行， 查看第2列中1， 对有1的行进行改写。对本例，时，第二列中，将第二行与第一行各对应元素进行逻辑加，仍记于第一行：；置当今行为第3行，重复上述操作并结束。对本例，时，第三列中，将第三行分别与第一行、第二行、第三行各对应元素进行逻辑加，仍分别记于第一行、第二行、第三行：得 。结果与例3.8.2一致。传递闭包在语法分析中有很多应用，先以下列说明/例3.8.4 设有一字母表并给定下面六条规则：为

6、定义在上的二元关系且，即是从出发用一条规则推出一串字符，使其第一个字符恰为。说明每个字母连续应用上述规则可能推出的头字符。解 则表示从出发，经过多次连续推导而得的字符串，其第一个字符恰为的关系，此关系即是。按照Warshall算法计算的过程中，时，由于第五行的元素都等于零，的赋值不变。时，由于第3、6、7列各元素均为零，的赋值不变。经计算得 因此。 这说明应用给定的六条规则，从出发推导的头字符有三种可能，而从出发推导的头字符有两种可能，而从推出的头字符有两种可能，从出发推导的头字符只可能为。从一种性质的闭包关系出发，求取另一种性质的闭包关系，具有以下运算律： 定理3.8.4 设是集合上的二元关

7、系，则（1）（2）（3）证明 （1） 这里，。（2）这里，（）。（3）留作练习请读者自证。习题3.81设是上的二元关系，证明或反驳下列命题：（1）若，则； (2) 若，则；(3) 若，则； (4) ；（5）)； (6) ；(7) ； (8) ，其中；(9) ； (10) 对称关系的传递闭包是对称的；（11）反对称关系的传递闭包是反对称的。2试找出个元素的集合和上的关系，使都是不相交的，以表明定理3.8.3给出的界限是不可改善的。3试找出个元素的集合X和X上的二元关系，使都是有区别的，并说明这个现象并不与定理3.8.3矛盾。3.9 等价关系与相容关系 本节讨论两类特殊关系等价关系与相容关系。在讨

8、论之前，我们先引进两个概念集合的划分与覆盖。3.9.1 集合的划分和覆盖 设是某一所综合性大学本科学生全体组成的集合，是对的某种分类的集合（）。若按文理科分类，则有，其中表示理科学生全体的集合、表示文科学生全体的集合；若按年级分类，则有，其中表示该大学年级学生全体的集合；若按系分类，则有，这说明这所大学有六个系。分类法尽管给出了三种，但是它们有个共同的特点：(1) 的元素都是的非空子集；(2) 的元素求交是空集、求并就是。 此时，我们就说是集合的一个划分。 定义3.9.1 设是非空集合，的子集的集合，如果满足： （1）都是非空集合； （2）则称集合是集合的覆盖(Cover)，称是覆盖的分块。如

9、果除以上条件外，另有（），则称是的划分（或分划）(Partition)。显然，若是划分则必是覆盖，其逆不真。若，则有两个简单的划分：一是，称为的最大划分(分块最多)；二是，称为的最小划分(分块最少)。 例如，考虑下列子集：，则是的覆盖；是的划分，其中是最小划分，是最大划分；既不是划分也不是覆盖。 定义3.9.2 若与是同一集合的两种划分，则其中所有组成的集合，称为和的交叉划分，即 注意：和的交叉划分一般不是，而是以与元素之间的所有非空交集作元素的集合。 例如，所有生物的集合，可分割成，其中表示所有植物的集合，表示所有动物的集合；又也可分割成，其中表示史前生物，表示史后生物。则其交叉划分为，其中

10、表示史前植物，表示史后植物，表示史前动物，表示史后动物。 定理3.9.1 设与是同一集合的两种划分，则其交叉划分也是原集合的一种划分。 证明 和的交叉划分是： 在交叉划分中，任取两元素和，（），因为 ，所以 ；其次，交叉划分中所有元素的并为 所以，和的交叉划分也是的一种划分。定义3.9.3 给定的任意两个划分与，若对于每一个均有，使（），则称为的加细。若还有，则称为的真加细。定理3.9.2 任何两种划分的交叉划分，都是原来各划分的一种加细。证明 设与的交叉划分为，对中任意元素必有和，则分别是和的加细。3.9.2 等价关系与等价类1. 等价关系 定义3.9.4 设为定义在集合上的一个关系，若是自

11、反的、对称的和传递的，则称为等价关系(Equivalence Relation)。例 3 . 9. 1 （1） 平面上三角形集合中，三角形的相似关系是等价关系。（） 数的相等关系是任何数集上的等价关系。（3）一群人的集合中姓氏相同的关系也是等价关系。（4）设是任意非空集合，则上的恒等关系和全域关系均是上的等价关系。例3.9.2 设集合， 验证是上的等价关系。证明 的关系矩阵：关系图如图3-17所示。图3-17关系矩阵中，对角线上的所有元素都是1，关系图上每个结点都有自环，说明是自反的。关系矩阵是对称的，关系图上任意两结点间或没有弧线连接，或有成对弧出现，故是对称的。从的序偶表示式中，可以看出是

12、传递的。故是上的等价关系。例3.9.3 设为整数集，其中当且仅当，使得，证明是等价关系。证明 设任意（1），所以，是自反的；（2）若，(为整数)，则 ，所以，是对称的；（3）若，则， (为整数)，所以，是传递的。因此，是等价关系。我们称之为整数集上的模同余关系(Congruence Modulo )。2等价类定义3.9.5 设是集合上的等价关系，对任何，若，则称与等价。对任何，集合中等价于的所有元素组成的集合称为以为代表元的（关于等价关系的）等价类(Equivalence Class)，记作。即由等价类的定义可知是非空的，因为，。因此，任给集合及其上的等价关系，必可写出上各个元素的等价类。例如

13、，在例3.9.2中，的各个元素的等价类为：；可见，上的等价关系的不同的等价类有两个。例3.9.4 设是整数集合，是模同余关系，即，确定由的元素所产生的等价类。解 例3.9.3已证明整数集合上的模同余的关系是等价关系，故本例中由的元素所产生的等价类是从本例可以看到，在集合上模3同余等价关系所构成的等价类有：定理3.9.3 设给定集合上的等价关系，对于有当且仅当。证明 若 ，因为 ，故，即 ，则。若 ，则，即 ；，即 。所以，。定义3.9.6 集合上的等价关系，其所有等价类的集合称作关于的商集(Quotient Set )，记作，即例如，例3.9.2中，商集： 例3.9.4中商集： 。我们注意到商

14、集中，且任意两个等价类的交为，于是我们有下述重要定理。定理3.9.4 集合上的等价关系，决定了的一个划分，该划分就是商集。为证定理，我们需要证明非空集合在其上的等价关系下形成的等价类的全体的集合商集满足：(1) 每一等价类都是的子集， 中任一元素均属于某一等价类， 即等价类全体的并集是；(2) 不同的等价类之间交是空集。 证明 ，因为 ，所以，从而；因为自反，即，所以，则 ；故 。(1) 得证。为证明（2），用反证法：设，且 则 ，使成立，由对称性得 ，再由传递性得 ，据定理3.9.3，必有 ，这与题设矛盾，（2）得证。所以，是的对应于的一个划分。定理3.9.5设是集合的一个划分，则存在上的一

15、个等价关系，使得是关于的商集。证明 在集合上定义关系，对任意，当且仅当在同一分块中。可以证明这样定义的关系是一个等价关系。因为：（1）与在同一分块中，故必有，即是自反的。（2）若与在同一分块中，与也必在同一分块中，即 ，故是对称的。（3）若与在同一分块中，与在同一分块中，因为 ，即属于且仅属于一个分块，故与必在同一分块中，即 ，故是传递的。所以，是等价关系。由的定义可知： 。由定理3.9.5可知：由集合的划分所确定的上的等价关系为：定理3.9.4和定理3.9.5说明：非空集合上的等价关系与的划分一一对应。例3.9.5 设的划分，试由划分确定上的一个等价关系。解 显然，。定理3.9.6 设和为非

16、空集合上的等价关系，则。证明 ，。若 ，故 ，即；若，即，则对，必有，使得，故 所以， ；类似地有 ，因此，。在实际应用中常常比较集合的不同等价关系和不同划分的大小。大划分含有更多的块， 小等价关系序对较少。大划分对应小等价关系，大等价关系对应小划分。如集合的最大划分对应上最小的等价关系，最大的等价关系对应最小划分。划分的大小一般不能由相对应的等价关系的大小确定，但下面的定理指出：若划分加细划分，则由生成的等价关系包含在由生成的等价关系中。 定理3.9.7 设和是非空集合的划分，和是分别与和对应的等价关系，则加细当且仅当。证明 ， 设加细。，由生成，则存在分块，使，而且 ，因此， 并且是中的序

17、对， 即， 可见， 。设。，非空，有且于是，加细。所以，加细当且仅当。 在以非空集合的划分为元素的集合上可以定义二元运算“和”与“积”。划分与的和是和加细的最大划分，与的积是加细和的最小划分。 定义3.9.7 设，是非空集合的划分， 称是与的和，如果：(1) ，都加细；(2) 若还有划分能被和加细，那么加细；称是与的积，如果： 加细和； 若还有划分加细和，那么加细。例3.9.6 假定在一片圆形纸上画了红线和绿线，这些曲线它们各自或与圆周线一起形成的都是闭合区域。当沿红线剪开时产生划分，当沿绿线剪开时产生划分，那么既沿红线又沿绿线剪开时产生“积划分”；而沿共涂两色的线剪开时，就产生“和划分”。定

18、理3.9.8 设，是由非空集合的划分，分别生成的等价关系，则生成与的积，并且划分与的积划分唯一。 证明 (1) 显然，是上的等价关系；(2) 设生成的划分是，则由及定理3.9.7知，加细且加细；(3) 若还有划分既加细也加细，则生成的等价关系满足：且，从而，于是加细。综上所述，生成。 划分与的积划分唯一。因为如果与还有积划分，则由定义3.9.7的知，加细且加细，于是与含有相同的元素，即。 定理3.9.9 设，是由非空集合的划分，分别生成的等价关系，则生成与的和，并且划分与的和划分唯一。 证明：(1) 显然自反、对称且是包含的最小的等价关系；(2) 因为，所以，都加细生成的划分；(3) 如若还有

19、划分，由上等价关系生成，都加细，则且，于是，进而，因此加细。综上所述，生成。划分与的和划分唯一。 因为若与还有和划分， 则由定义3.9.7的(2)知，加细且加细，于是的分块都是的分块的子集，的分块也都是的分块的子集，互为子集的块只能发生在和的同一分块上，可见和含有相同的元素， 即。 给定个元素的集合，如何求出的全部划分(全部等价关系)呢? 我们记的一个划分的分块数为这个划分的秩，为求的全部划分，须首先求得的秩为的不同的划分个数。此问题有如下数学模型：将个不同的球放入只相同的盒中，求使无空盒的相异放法数(记为)。 此模型的计算公式即组合数学中的第二类Stirling数公式，亦称第二类Stirli

20、ng数，该公式为：且有性质：。例3.9.7 求4元集合上的不同的等价关系个数。解 设集合的不同划分数为，则3.9.3 相容关系定义3.9.8 给定集合上的关系，若是自反的、对称的，则称是上的相容关系Cconsistent Relation)。相容关系只要求满足自反性与对称性，因此，等价关系必定是相容关系但反之不真。 例3.9.8 设是由下列英文单词组成的集合，定义关系：，且和有相同的字母显然，是一个相容关系。令的关系图如图3-18所示。 图3-18的关系矩阵为。由于相容关系是自反和对称的，因此，其关系矩阵的对角线元素都是，且矩阵是对称的。为此我们可将矩阵用梯形表示。同理，在相容关系的关系图中，

21、每个结点处都有自环且每两个相关联的结点间的弧线都是成对出现的，为了简化图形，我们今后对相容关系图，不画自环，并用单线代替双向弧线，因此，上例的关系矩阵和关系图可简化为表3-1和图3-19。表3-1 例3.9.8的简化关系矩阵 图3-19定义3.9.9 设是集合上的相容关系， ，如果对于中任意两个元素 有，就称是由相容关系产生的相容类(Consistent Class)。例如，上例中相容关系可产生相容类等等。对于前三个相容类，都能加进新的元素组成新的相容类，而后两个相容类，加入任一新元素，就不再组成相容类，称它们为最大相容类(Maximal Consistent Class)。定义3.9.10

22、设是集合上的相容关系，不能真包含在任何其它相容类中的相容类，称作最大相容类，记作。若为最大相容类，显然它是的子集，对于任意，必与中的所有元素有相容关系。而在中没有任何元素与所有元素有相容关系。根据最大相容类的定义，它可以从相容关系的简化关系图求得，具体方法是：（1）在相容关系的简化关系图中，每一个最大完全多边形的顶点集合，就是一个最大相容类。所谓完全多边形(Complete Polygon)，就是其每个顶点都与其它顶点连接的多边形。例如一个三角形是完全多边形，一个四边形加上两条对角线就是完全多边形。（2）在的简化关系图中，每一个孤立结点的单点集合，是一个最大相容类。（3）在的简化关系图中，不在

23、完全多边形中的边的两个端点的集合，是一个最大相容类。例3.9.9 由例3.9.8中相容关系的简化关系图3-19可得其全部最大相容类为：定理3.9.10 设是集合上的相容关系，是一个相容类，那么必存在一个最大相容类，使得。证明 设，构造相容类序列，其中，且，其中是满足而 与中各元素都有相容关系的最小下标。由于的元素个数， 所以至多经过步，就使这个过程终止，而此序列的最后一个相容类，就是所要找的最大相容类。从定理3.9.10中可以看到，的任一元素，它可以组成相容类，因此必包含在一个最大相容类中，因此，如由所有最大相容类作出一个集合，则中每一个元素至少属于该集合的一个成员之中，所以最大相容类集合必覆

24、盖集合。定义3.9.11 在集合上给定相容关系，其最大相容类的集合称作集合的完全覆盖(Complete Cover)，记作。例3.9.10 设集合，上二元关系求的完全覆盖。 解 是上的相容关系(自反，对称)。 的简化关系图如图3-20所示：图3-20的最大相容类是确定的，即。因此，集合是的完全覆盖。定理3.9.11 给定集合的覆盖，由它确定的关系是上的相容关系。证明 因为 ，对于任意，必存在某个， 使得 ，所以， ，即 ， 因此，是自反的。其次，若有任意，且，则必存在某个，使 ，故必有 ，即，所以是对称的。因此，是上的相容关系。从上述定理可以看到，给定集合上的任意一个覆盖，必可在上构造对应于此

25、覆盖的一个相容关系，但是不同的覆盖却能构造相同的相容关系。例如，设，集合和都是的覆盖，但它们可以产生相同的相容关系：因此，相容关系与覆盖之间不是一一对应的。但是我们有：定理3.9.12 集合上相容关系与完全覆盖一一对应。习题3.91设是集合的划分，试证明是集合的划分。其中。2把个元素的集合划分成两个分块，共有多少种不同的方法？3已知及其关系如下，试说明是等价关系，并指出其等价类。（1）：自然数集， 能表示成形式，为任意整数；（2）：正整数的序偶，； （3）：实数部分非零的复数全体，；（4）：实数集，其中表示小于或等于的最大整数。4设，试根据以下的划分求上相应的等价关系，并画出关系图。（1）；

26、（2）；（3）； （4）.5证明：（1）设是上的关系。对于而言，如且蕴含，则关系称为循环的。证明是自反的和循环的，当且仅当它是一等价关系。（2）设和是上的等价关系，分别是相应于的划分。证明：当且仅当中每一个等价类包含于的一些等价类中。（3）设和是上的等价关系，其对应等价类的数目（称为等价关系的秩）分别为。试证是秩至多为的上的等价关系，但不一定是上的等价关系。6（1）试叙述根据上的相容关系来定义一个覆盖的方法，此方法所定义的覆盖是否唯一？（2）给定集合的覆盖，能否确定此覆盖对应的相容关系？（3）若和是上的相容关系，问，是不是相容关系？3.10 偏序关系3.10.1偏序关系的定义在一个集合上，我们

27、常常要考虑元素的次序关系，其中很重要的一类关系称作偏序关系。定义3.10.1 设是一个集合，如果上的一个关系，满足自反性、反对称性和传递性，则称是上的一个偏序关系(Partially Ordered Relation)，并把它记为“”。序偶称作偏序集(Partially Ordered Set Or Poset)。例3.10.1 在实数集上，小于等于关系“”是偏序关系。因为：（1）对于任何实数，有成立，故是自反的；（2）对任何实数，如果且，则必有，故是反对称的；（3）对任何实数，如果，那么必有，故是传递的。例3.10.2 设为任意非空集合，上的包含关系是偏序关系。因为：（1）对于任意，有，所以

28、“”是自反的； （2）对任意，若且，则所以“”是反对称的； （3）对任意，若且，则，所以“”是可传递的。 例3.10.3 正整数集上的整除关系是偏序关系。因为： （1）对于任何正整数，有成立，故“”是自反的；（2）对任何正整数，如果且，则必有，故“”是反对称的；（3）对任何正整数，如果且，那么必有，故“”是传递的。例3.10.4 （1）实数集上的小于关系“”不是偏序关系。（2）任意非空集合的幂集上的真包含关系“”不是偏序关系。3.10.2 偏序关系的哈斯图为了更清楚地描述偏序集合中元素间的层次关系，我们先介绍“盖住”的概念。定义3.10.2 在偏序集合中，如果，且没有其它元素满足，则称元素盖住

29、元素。并且记COV盖住。称为偏序集中的盖住关系。显然。例3.10.5 设，并设“”为整除关系，求COV。解 “”COV对于给定偏序集，它的盖住关系是唯一的，所以哈斯(Hasse)根据盖住的概念给出了偏序关系图的一种画法，这种画法画出的图称为哈斯图(Hasse Diagram)，其作图规则如下： （1） 用小圆圈代表元素。（2） 如果且，则将代表的小圆圈画在代表的小圆圈之上。（3） 如果COV，则在与之间用直线连接。根据这个作图规则，例3.10.5中偏序集的一般关系图和哈斯图如图3-21所示。 图3-21例3.10.6 设，则“”关系是上的偏序关系，它们的哈斯图分别如图3-22的所示。 图3-2

30、2 例3.10.7 设，上的整除关系“”是一偏序关系，其哈斯图如图3-23所示。图3-233.10.3 偏序集中特殊位置的元素从偏序集的哈斯图可以看到偏序集中各个元素之间具有分明的层次关系，则其中必有一些处于特殊位置的元素。下面讨论偏序集中具有特殊位置的元素。定义3.10.3 设是一个偏序集合，且是的子集，若有某个元素，使得（1）不存在，满足且，则称为的极大元(Maximal Element)；（2）不存在，满足且，则称为的极小元(Minimal Element)；（3）对每一个有，则称为的最大元(Largest Element)；（4）对每一个有，则称为的最小元(Smallest Eleme

31、nt)。例3.10.8 设，其偏序关系求的极大元、极小元、最大元和最小元。解 COV ，的哈斯图如图3-24所示。 14 21 152 7 3 5图3-24故的极小元集合是，的极大元集合为，无最大元，也无最小元。例3.10.9 在例3.10.7中取分别为，和，则 集合极大元极小元最大元最小元无无无例3.10.10 在例3.10.6中的图3-22所示的偏序集中，取分别为，和，则集合极大元极小元最大元最小元无无从上面的3个例子可以看出，最大（小）元和极大（小）元有如下性质：定理3.10.1设为一偏序集且，则（1）的最大（小）元必是的极大（小）元，反之不然。（2）的最大（小）元不一定存在，若有最大（

32、最小）元，则必是唯一的。（3）的极大（小）元不一定是唯一的。当时，则偏序集的极大元即是哈斯图中最顶层的元素，其极小元是哈斯图中最底层的元素，不同的极小元或不同的极大元之间是不可比较的。证明 我们证明最大（小）元的唯一性。假定和都是的最大元，则且，由的反对称性，得到。的最小元情况与此类似。定义3.10.4 设为一偏序集，对于，如有，对的任意元素，都满足（1），则称为的上界(Upper Bound)；（2），则称为的下界(Lower Bound)；（3）为的上界，且对的任一上界均有，则称为的最小上界（上确界）(Least Upper Bound)，记作LUB；（4）为的下界，且对的任一下界，均有，

33、则称为的最大下界（下确界）(Greatest Lower Bound)，记为GLB。例3.10.11 在例3.10.7中取分别为，和，和，则 集合上界下界上确界下确界无无无无无无无无无无例3.10.12 在例3.10.6中的图3-22所示的偏序集中，取分别为，和，则集合上界下界上确界下确界，从上面的两个例子可以看出，上(下)界和上(下)确界有如下性质：定理3.10.2 设为一偏序集且，则（1）的上（下）界不一定存在，若存在，则不一定唯一，并且它们可能在中，也可能在外；（2）的上（下）确界不一定存在，若存在，必定是唯一的，并且若有最大（小）元，则它必是的上（下）确界。3.10.4 两种特殊的偏序

34、集1全序定义3.10.5 设为一个偏序集，若对于任意，必有或，则称为全序集合或线序集合（有时也称为链），二元关系称为全序关系或线序关系(Total Order Or Linear Order)。例3.10.13 （1）定义在自然数集合上的小于等于关系“”是偏序关系，且对任意，必有：或成立，故“”是全序关系。（2）实数集上的小于等于关系“”也是上的一个全序关系。（3）设，则上的整除关系是一个全序关系，其哈斯图如图3-25所示。图3-25 例3.10.13中（3）的哈斯图（4）自然数集合上的整除关系就仅是一个偏序而不是全序。 2.良序定义3.10.6 设为一个偏序集，若的任意非空子集均有最小元素，

35、则称为上的一个良序(Well-ordered)，称为良序集(Well-ordered Set)。例如，（1）正整数集上的小于等于关系是良序，即是良序集。（2）上的小于等于关系是良序，即是良序集。（3）整数集和实数集上的小于等于关系“”不是良序关系（因为或本身无最小元）。定理3.10.3 每一个良序集合，一定是全序集合。证明 设为良序集合，则对任意两个元素可构成子集，必存在最小元素，这个最小元素不是就是，因此一定有或。所以为全序集。注意：定理3.10.3的逆不成立 。 例如，整数集和实数集上的小于等于关系“”是全序，但不是良序。但是我们有定理3.10.4 每一个有限的全序集合，一定是良序集合。证

36、明 设，且是全序集合，现在假定不是良序集合，那么必存在一个非空子集，在B中不存在最小元素，由于是一个有限集合，故一定可以找出两个元素与是无关的，由于是全序集，所以必有关系，得出矛盾，故必是良序集合。习题3.101 对于下列集合上的“整除”关系，画出其哈斯图。（1）； （2）。2证明或反驳下列命题：(1) 如是拟序（反自反且可传递）关系，则亦然。(2) 如是偏序关系，则亦然。(3) 如是全序关系，则亦然。(4) 和当且仅当是拟序关系。(5) 和当且仅当是偏序关系。(6) 若是上的偏序关系，且，则是上的偏序关系。(7) 若是拟序关系，则是偏序关系。(8) 若是偏序关系，则是拟序关系。(9) 存在集合和其上关系使是良序集，但不是良序集。3（1）给出集合能使是全序集。 （2）给出关系，它既是给定集合上的偏序关系又是等价关系。4设，偏序集的哈斯图如图3-26所示。 图3-26（） 中哪些为真？（） 求的最小元与最大元，如果它们存在的话。（） 求的极小元与极大元。（） 求和的上界与下界，并指出它们的上确界与下确界（如果存在的话）。（） 把哈斯图改为有向图。5下列集合中哪些是拟序集合、偏序集合、全序集合、良序集合？ （1）， （2） （3） （4）专心-专注-专业