离散数学(第5章)陈瑜.ppt

陈瑜,Email：yu2023/6/30,离散数学,计算机学院,2023/6/30,计算机科学与工程学院,2,主要内容,1.等价关系2.偏序关系3.全序关系4.良序关系5.有限偏序集到全(良)序集,2023/6/30,计算机科学与工程学院,3,5.1 等价关系,一个事物常常可以有很多种表现形式，如1/2可以写成2/4，3/6，5/10等等，一个命题公式也可以表示成很多不同然而等价的形式。当我们以某种尺度来看待这些表面不同而具有相同特征的事物时，归类分析的想法就产生了，这就是等价关系的核心思想。,2023/6/30,计算机科学与工程学院,4,5.1 等价关系,例5.1：1）在全体中国人所组成的集合上定义的“同姓”关系，就是具备自反的、对称的、传递的性质，因此，就是一个等价关系；2）对任何集合A,考虑RAA,则R是A上的等价关系；3）三角形的“相似关系”、“全等关系”等都是等价关系；4）直线的“平行关系”不是等价关系，因为它们不是自反的。5）幂集上定义的“”，整数集上定义的“”都不是等价关系，因为它们不是对称的。6）“朋友”关系，则不是等价关系，因它不是传递的。,定义5-1.1设R是定义在非空集合A上的一个二元关系，当R同时具有自反、对称和传递性质时，称R是A上的一个等价关系。,2023/6/30,计算机科学与工程学院,5,5.1 等价关系,例5.1：1）在全体中国人所组成的集合上定义的“同姓”关系，就是具备自反的、对称的、传递的性质，因此，就是一个等价关系；2）对任何集合A,考虑RAA,则R是A上的等价关系；3）三角形的“相似关系”、“全等关系”等都是等价关系；4）直线的“平行关系”不是等价关系，因为它们不是自反的。5）幂集上定义的“”，整数集上定义的“”都不是等价关系，因为它们不是对称的。6）“朋友”关系，则不是等价关系，因它不是传递的。,定义5-1.1设R是定义在非空集合A上的一个二元关系，当R同时具有自反、对称和传递性质时，称R是A上的一个等价关系。,2023/6/30,计算机科学与工程学院,6,5.1 等价关系,例5.1：1）在全体中国人所组成的集合上定义的“同姓”关系，就是具备自反的、对称的、传递的性质，因此，就是一个等价关系；2）对任何集合A,考虑RAA,则R是A上的等价关系；3）三角形的“相似关系”、“全等关系”等都是等价关系；4）直线的“平行关系”不是等价关系，因为它们不是自反的。5）幂集上定义的“”，整数集上定义的“”都不是等价关系，因为它们不是对称的。6）“朋友”关系，则不是等价关系，因它不是传递的。,定义5-1.1设R是定义在非空集合A上的一个二元关系，当R同时具有自反、对称和传递性质时，称R是A上的一个等价关系。,2023/6/30,计算机科学与工程学院,7,5.1 等价关系,例5.1：1）在全体中国人所组成的集合上定义的“同姓”关系，就是具备自反的、对称的、传递的性质，因此，就是一个等价关系；2）对任何集合A,考虑RAA,则R是A上的等价关系；3）三角形的“相似关系”、“全等关系”等都是等价关系；4）直线的“平行关系”不是等价关系，因为它们不是自反的。5）幂集上定义的“”，整数集上定义的“”都不是等价关系，因为它们不是对称的。6）“朋友”关系，则不是等价关系，因它不是传递的。,定义5-1.1设R是定义在非空集合A上的一个二元关系，当R同时具有自反、对称和传递性质时，称R是A上的一个等价关系。,2023/6/30,计算机科学与工程学院,8,5.1 等价关系,例5.1：1）在全体中国人所组成的集合上定义的“同姓”关系，就是具备自反的、对称的、传递的性质，因此，就是一个等价关系；2）对任何集合A,考虑RAA,则R是A上的等价关系；3）三角形的“相似关系”、“全等关系”等都是等价关系；4）直线的“平行关系”不是等价关系，因为它们不是自反的。5）幂集上定义的“”，整数集上定义的“”都不是等价关系，因为它们不是对称的。6）“朋友”关系，则不是等价关系，因它不是传递的。,定义5-1.1设R是定义在非空集合A上的一个二元关系，当R同时具有自反、对称和传递性质时，称R是A上的一个等价关系。,2023/6/30,计算机科学与工程学院,9,5.1 等价关系,例5.1：1）在全体中国人所组成的集合上定义的“同姓”关系，就是具备自反的、对称的、传递的性质，因此，就是一个等价关系；2）对任何集合A,考虑RAA,则R是A上的等价关系；3）三角形的“相似关系”、“全等关系”等都是等价关系；4）直线的“平行关系”不是等价关系，因为它们不是自反的。5）幂集上定义的“”，整数集上定义的“”都不是等价关系，因为它们不是对称的。6）“朋友”关系，则不是等价关系，因它不是传递的。,定义5-1.1设R是定义在非空集合A上的一个二元关系，当R同时具有自反、对称和传递性质时，称R是A上的一个等价关系。,2023/6/30,计算机科学与工程学院,10,5.1 等价关系,例5.1：1）在全体中国人所组成的集合上定义的“同姓”关系，就是具备自反的、对称的、传递的性质，因此，就是一个等价关系；2）对任何集合A,考虑RAA,则R是A上的等价关系；3）三角形的“相似关系”、“全等关系”等都是等价关系；4）直线的“平行关系”不是等价关系，因为它们不是自反的。5）幂集上定义的“”，整数集上定义的“”都不是等价关系，因为它们不是对称的。6）“朋友”关系，则不是等价关系，因它不是传递的。,定义5-1.1设R是定义在非空集合A上的一个二元关系，当R同时具有自反、对称和传递性质时，称R是A上的一个等价关系。,2023/6/30,计算机科学与工程学院,11,证明：1)对任意xZ，有m|(x-x)，所以R，即R是自反的。2)对任意x,yZ，若R，即m|(x-y)，所以 m|(y-x)，因此，R，即R是对称的。3)对任意x,y,zZ，若R且R，有m|(x-y)且m|(y-z)，所以由(x-z)=(x-y)+(y-z)得m|(x-z)，所以，R，即R是传递的。由(1)、(2)、(3)知，R是Z上的等价关系。,例5.2：设m为正整数，考虑整数集合Z上的关系如下：R=|x,yZ(m|(x-y)证明R是一个等价关系。,m整除(x-y)，即：(x-y)是m的倍数。,2023/6/30,计算机科学与工程学院,12,证明：1)对任意xZ，有m|(x-x)，所以R，即R是自反的。2)对任意x,yZ，若R，即m|(x-y)，所以 m|(y-x)，因此，R，即R是对称的。3)对任意x,y,zZ，若R且R，有m|(x-y)且m|(y-z)，所以由(x-z)=(x-y)+(y-z)得m|(x-z)，所以，R，即R是传递的。由(1)、(2)、(3)知，R是Z上的等价关系。,例5.2：设m为正整数，考虑整数集合Z上的关系如下：R=|x,yZ(m|(x-y)证明R是一个等价关系。,2023/6/30,计算机科学与工程学院,13,证明：1)对任意xZ，有m|(x-x)，所以R，即R是自反的。2)对任意x,yZ，若R，即m|(x-y)，所以 m|(y-x)，因此，R，即R是对称的。3)对任意x,y,zZ，若R且R，有m|(x-y)且m|(y-z)，所以由(x-z)=(x-y)+(y-z)得m|(x-z)，所以，R，即R是传递的。由(1)、(2)、(3)知，R是Z上的等价关系。,例5.2：设m为正整数，考虑整数集合Z上的关系如下：R=|x,yZ(m|(x-y)证明R是一个等价关系。,2023/6/30,计算机科学与工程学院,14,证明：1)对任意xZ，有m|(x-x)，所以R，即R是自反的。2)对任意x,yZ，若R，即m|(x-y)，所以 m|(y-x)，因此，R，即R是对称的。3)对任意x,y,zZ，若R且R，有m|(x-y)且m|(y-z)，所以由(x-z)=(x-y)+(y-z)得m|(x-z)，所以，R，即R是传递的。由(1)、(2)、(3)知，R是Z上的等价关系。,例5.2：设m为正整数，考虑整数集合Z上的关系如下：R=|x,yZ(m|(x-y)证明R是一个等价关系。,2023/6/30,计算机科学与工程学院,15,证明：1)对任意xZ，有m|(x-x)，所以R，即R是自反的。2)对任意x,yZ，若R，即m|(x-y)，所以 m|(y-x)，因此，R，即R是对称的。3)对任意x,y,zZ，若R且R，有m|(x-y)且m|(y-z)，所以由(x-z)=(x-y)+(y-z)得m|(x-z)，所以，R，即R是传递的。由(1)、(2)、(3)知，R是Z上的等价关系。,例5.2：设m为正整数，考虑整数集合Z上的关系如下：R=|x,yZ(m|(x-y)证明R是一个等价关系。,2023/6/30,计算机科学与工程学院,16,以m为模的同余关系,上例中R称为Z上以m为模的同余关系，一般记xRy为：xy(mod m)称为同余式。,此时，R将Z分成了如下m个子集：,-3m,-2m,-m,0,m,2m,3m,-3m+1,-2m+1,-m+1,1,m+1,2m+1,3m+1,-3m+2,-2m+2,-m+2,2,m+2,2m+2,3m+2,-2m-1,-m-1,-1,m-1,2m-1,3m-1,4m-1,2023/6/30,计算机科学与工程学院,17,以m为模的同余关系,上例中R称为Z上以m为模的同余关系，一般记xRy为：xy(mod m)称为同余式。,此时，R将Z分成了如下m个子集：,-3m,-2m,-m,0,m,2m,3m,-3m+1,-2m+1,-m+1,1,m+1,2m+1,3m+1,-3m+2,-2m+2,-m+2,2,m+2,2m+2,3m+2,-2m-1,-m-1,-1,m-1,2m-1,3m-1,4m-1,2023/6/30,计算机科学与工程学院,18,这m个Z的子集具有的特点：在同一个子集中的元素之间都有关系R，而不同子集的元素之间无关系R。也就是说，通过等价关系，将集合分成若干子集，使这些子集构成的集合就是Z的一个划分。,事实上，对任意正整数m，Z的任意非空子集A，关系R=|(x,yA)(m|(x-y)都是A上的等价关系。,2023/6/30,计算机科学与工程学院,19,这m个Z的子集具有的特点：在同一个子集中的元素之间都有关系R，而不同子集的元素之间无关系R。也就是说，通过等价关系，将集合分成若干子集，使这些子集构成的集合就是Z的一个划分。,事实上，对任意正整数m，Z的任意非空子集A，关系R=|(x,yA)(m|(x-y)都是A上的等价关系。,2023/6/30,计算机科学与工程学院,20,例5.3,我们常见的时钟上的时针重复关系即为m=12，A=0,1,2,3,23。此等价关系R的关系图如下图所示，A被分成了12个子集0,12、1,13、2,14、11,23。,2023/6/30,计算机科学与工程学院,21,等价类,定义5-1.2 设R是集合A上的等价关系,对任意 aA,记aRx|(xA)(R)，称A的子集合aR为关系R的一个等价类,或叫作由a生成的一个R等价类。其中a称为aR的生成元(或叫代表元，或典型元)。在不会引起混淆时，简记为a。,2023/6/30,计算机科学与工程学院,22,例5.4,设A1,2,3,4,5,8，考虑R是A上的以3为模的同余关系，求其等价类。,解：从例5.2易知，该R是一个等价关系，为此可求xR(xA)。1R1,44R；2R2,5,85R8R；3R3。,2023/6/30,计算机科学与工程学院,23,例5.4,设A1,2,3,4,5,8，考虑R是A上的以3为模的同余关系，求其等价类。,解：从例5.2易知，该R是一个等价关系，为此可求xR(xA)。1R1,44R；2R2,5,85R8R；3R3。,2023/6/30,计算机科学与工程学院,24,例5.4,设A1,2,3,4,5,8，考虑R是A上的以3为模的同余关系，求其等价类。,解：从例5.2易知，该R是一个等价关系，为此可求xR(xA)。1R1,44R；2R2,5,85R8R；3R3。,2023/6/30,计算机科学与工程学院,25,例5.4,设A1,2,3,4,5,8，考虑R是A上的以3为模的同余关系，求其等价类。,解：从例5.2易知，该R是一个等价关系，为此可求xR(xA)。1R1,44R；2R2,5,85R8R；3R3。,2023/6/30,计算机科学与工程学院,26,例5.4,设A1,2,3,4,5,8，考虑R是A上的以3为模的同余关系，求其等价类。,解：从例5.2易知，该R是一个等价关系，为此可求xR(xA)。1R1,44R；2R2,5,85R8R；3R3。,2023/6/30,计算机科学与工程学院,27,等价类的性质,定理5-1.1设R是非空集合A上的等价关系,则 对任意a、bA,或者a=b或者ab=；,证明:任意给定a、bA。若ab=，则已得证。若ab，则存在A的元素xab。于是xa且xb，故有xRa且xRb；又由于R是对称的，于是aRx且xRb；又R是传递的，故aRb。因此，对任意ya必有yRa，而aRb，故yRb，即yb，因此得到a b。同理可证a b，故a=b。显然成立。,2023/6/30,计算机科学与工程学院,28,等价类的性质,定理5-1.1设R是非空集合A上的等价关系,则 对任意a、bA,或者a=b或者ab=；,证明:任意给定a、bA。若ab=，则已得证。若ab，则存在A的元素xab。于是xa且xb，故有xRa且xRb；又由于R是对称的，于是aRx且xRb；又R是传递的，故aRb。因此，对任意ya必有yRa，而aRb，故yRb，即yb，因此得到a b。同理可证a b，故a=b。显然成立。,2023/6/30,计算机科学与工程学院,29,等价类的性质,定理5-1.1设R是非空集合A上的等价关系,则 对任意a、bA,或者a=b或者ab=；,证明:任意给定a、bA。若ab=，则已得证。若ab，则存在A的元素xab。于是xa且xb，故有xRa且xRb；又由于R是对称的，于是aRx且xRb；又R是传递的，故aRb。因此，对任意ya必有yRa，而aRb，故yRb，即yb，因此得到a b。同理可证a b，故a=b。显然成立。,2023/6/30,计算机科学与工程学院,30,等价类的性质,定理5-1.1设R是非空集合A上的等价关系,则 对任意a、bA,或者a=b或者ab=；,证明:任意给定a、bA。若ab=，则已得证。若ab，则存在A的元素xab。于是xa且xb，故有xRa且xRb；又由于R是对称的，于是aRx且xRb；又R是传递的，故aRb。因此，对任意ya必有yRa，而aRb，故yRb，即yb，因此得到a b。同理可证a b，故a=b。显然成立。,这个定理告诉我们,集合A上一个等价关系决定了集合元素的一种聚类方式,即分割集合的方式。,2023/6/30,计算机科学与工程学院,31,集合的划分,定义5-1.3设A是一个非空集合，A1,A2,A3.Am都是A的非空子集，SA1,A2,A3,.,Am。如果：1）对一切的ij(i,j1,2,3,.,m)，都有 AiAj。2）则称集合S为集合A的一个分划,而A1,A2,A3,.Am叫做这个划分的块。,2023/6/30,计算机科学与工程学院,32,例：设集合A=a,b,c，则：S1=a，b，c，S2=a,b,c，S3=a,b,c，S4=b,a,c,S5=c，a,b 都是A的分划，并且由A只能产生这5个不同的分划。,2023/6/30,计算机科学与工程学院,33,定理5-1.2建立了集合上等价关系与分划的紧密联系。定理5-1.2 设非空集合A的每个等价关系都能决定A的一个分划，而A的每个分划都能导出A上的一个等价关系。（p108）,2023/6/30,计算机科学与工程学院,34,证明：（定理5-1.2）,证明:定理的第一部分结论由定理5-5.1就可以得到。对于第二部分，设SA1,A2,A3,.,Am是A上的任意一个分划。现在定义关系R如下:即是说,(a,b)R当且仅当a和b同属某个Ai。我们证明这样定义的关系R是一个等价关系。由于S是A的分划,因此对任何aA,皆有aRa,即R是自反的。如果aRb,那么存在Ai，使(a,b)Ai,从而又有bRa,这说明R是对称的。如果同时有aRb和bRc,且(a,b)Ai，(a,b)Aj。由于当ij时AiAj,所以必然Ai=Aj，即(a,c)Ai，也就是aRc成立。这说明R是传递的。因此，R是由分划S导出的一个等价关系。,2023/6/30,计算机科学与工程学院,35,证明：（定理5-1.2）,证明:定理的第一部分结论由定理5-5.1就可以得到。对于第二部分，设SA1,A2,A3,.,Am是A上的任意一个分划。现在定义关系R如下:即是说,(a,b)R当且仅当a和b同属某个Ai。我们证明这样定义的关系R是一个等价关系。由于S是A的分划,因此对任何aA,皆有aRa,即R是自反的。如果aRb,那么存在Ai，使(a,b)Ai,从而又有bRa,这说明R是对称的。如果同时有aRb和bRc,且(a,b)Ai，(a,b)Aj。由于当ij时AiAj,所以必然Ai=Aj，即(a,c)Ai，也就是aRc成立。这说明R是传递的。因此，R是由分划S导出的一个等价关系。,2023/6/30,计算机科学与工程学院,36,证明：（定理5-1.2）,证明:定理的第一部分结论由定理5-5.1就可以得到。对于第二部分，设SA1,A2,A3,.,Am是A上的任意一个分划。现在定义关系R如下:即是说,(a,b)R当且仅当a和b同属某个Ai。我们证明这样定义的关系R是一个等价关系。由于S是A的分划,因此对任何aA,皆有aRa,即R是自反的。如果aRb,那么存在Ai，使(a,b)Ai,从而又有bRa,这说明R是对称的。如果同时有aRb和bRc,且(a,b)Ai，(a,b)Aj。由于当ij时AiAj,所以必然Ai=Aj，即(a,c)Ai，也就是aRc成立。这说明R是传递的。因此，R是由分划S导出的一个等价关系。,2023/6/30,计算机科学与工程学院,37,证明：（定理5-1.2）,证明:定理的第一部分结论由定理5-5.1就可以得到。对于第二部分，设SA1,A2,A3,.,Am是A上的任意一个分划。现在定义关系R如下:即是说,(a,b)R当且仅当a和b同属某个Ai。我们证明这样定义的关系R是一个等价关系。由于S是A的分划,因此对任何aA,皆有aRa,即R是自反的。如果aRb,那么存在Ai，使(a,b)Ai,从而又有bRa,这说明R是对称的。如果同时有aRb和bRc,且(a,b)Ai，(a,b)Aj。由于当ij时AiAj,所以必然Ai=Aj，即(a,c)Ai，也就是aRc成立。这说明R是传递的。因此，R是由分划S导出的一个等价关系。,2023/6/30,计算机科学与工程学院,38,证明：（定理5-1.2）,证明:定理的第一部分结论由定理5-5.1就可以得到。对于第二部分，设SA1,A2,A3,.,Am是A上的任意一个分划。现在定义关系R如下:即是说,(a,b)R当且仅当a和b同属某个Ai。我们证明这样定义的关系R是一个等价关系。由于S是A的分划,因此对任何aA,皆有aRa,即R是自反的。如果aRb,那么存在Ai，使(a,b)Ai,从而又有bRa,这说明R是对称的。如果同时有aRb和bRc,且(a,b)Ai，(a,b)Aj。由于当ij时AiAj,所以必然Ai=Aj，即(a,c)Ai，也就是aRc成立。这说明R是传递的。因此，R是由分划S导出的一个等价关系。,2023/6/30,计算机科学与工程学院,39,证明：（定理5-1.2）,证明:定理的第一部分结论由定理5-5.1就可以得到。对于第二部分，设SA1,A2,A3,.,Am是A上的任意一个分划。现在定义关系R如下:即是说,(a,b)R当且仅当a和b同属某个Ai。我们证明这样定义的关系R是一个等价关系。由于S是A的分划,因此对任何aA,皆有aRa,即R是自反的。如果aRb,那么存在Ai，使(a,b)Ai,从而又有bRa,这说明R是对称的。如果同时有aRb和bRc,且(a,b)Ai，(a,b)Aj。由于当ij时AiAj,所以必然Ai=Aj，即(a,c)Ai，也就是aRc成立。这说明R是传递的。因此，R是由分划S导出的一个等价关系。,2023/6/30,计算机科学与工程学院,40,5.2 次(偏)序关系,事物之间的顺序关系,如家族的祖,父,子,孙等上下辈关系,世界杯足球赛队间的胜负关系，数之间的大小关系等等。从这些关系中抽出具有典型意义的特征，就构成了有广泛的理论和实际应用意义的偏序关系。偏（次）序关系是集合上的自反的、可传递、反对称关系,它提供比较集合的工具;也提供了事物之间的顺序关系。,2023/6/30,计算机科学与工程学院,41,5.2 次(偏)序关系,定义5-2.1：设R是集合A上的自反的、反对称的、传递的关系，则称R是A上的偏序关系(记为“”,读作“小于等于”)。序偶称为偏序集。容易证明：偏序 的逆关系 也是一个偏序，我们用“”表示，读作“大于等于”。,2023/6/30,计算机科学与工程学院,42,5.2 次(偏)序关系,定义5-2.1：设R是集合A上的自反的、反对称的、传递的关系，则称R是A上的偏序关系(记为“”,读作“小于等于”)。序偶称为偏序集。容易证明：偏序 的逆关系 也是一个偏序，我们用“”表示，读作“大于等于”。,2023/6/30,计算机科学与工程学院,43,例5.5,集合A的幂集2A上定义的“”是偏序关系。是偏序集。,实数集合R上定义的“”是偏序关系，是偏序集。大于零的自然数集合N上定义的“整除”关系“|”也是一个偏序关系,是偏序集。,2023/6/30,计算机科学与工程学院,44,例5.5,集合A的幂集2A上定义的“”是偏序关系。是偏序集。,实数集合R上定义的“”是偏序关系，是偏序集。大于零的自然数集合N上定义的“整除”关系“|”也是一个偏序关系,是偏序集。,2023/6/30,计算机科学与工程学院,45,例5.5,集合A的幂集2A上定义的“”是偏序关系。是偏序集。,实数集合R上定义的“”是偏序关系，是偏序集。大于零的自然数集合N上定义的“整除”关系“|”也是一个偏序关系,是偏序集。,2023/6/30,计算机科学与工程学院,46,偏序集的哈斯图,用小圆圈或点表示A中的元素，省掉关系图中所有的环。(因自反性)对任意x,yA，若x y，则将x画在y的下方，可去掉关系图中所有边的箭头。(因反对称性)去掉有向边，即当（i，j）和（j，k）都是有向边时，去掉有向边（i，k）。(因传递性)按1),2),3)所作成的图称为哈斯图(Hasse图)。,2023/6/30,计算机科学与工程学院,47,偏序集的哈斯图,用小圆圈或点表示A中的元素，省掉关系图中所有的环。(因自反性)对任意x,yA，若x y，则将x画在y的下方，可去掉关系图中所有边的箭头。(因反对称性)去掉有向边，即当（i，j）和（j，k）都是有向边时，去掉有向边（i，k）。(因传递性)按1),2),3)所作成的图称为哈斯图(Hasse图)。,2023/6/30,计算机科学与工程学院,48,偏序集的哈斯图,用小圆圈或点表示A中的元素，省掉关系图中所有的环。(因自反性)对任意x,yA，若x y，则将x画在y的下方，可去掉关系图中所有边的箭头。(因反对称性)去掉有向边，即当（i，j）和（j，k）都是有向边时，去掉有向边（i，k）。(因传递性)按1),2),3)所作成的图称为哈斯图(Hasse图)。,2023/6/30,计算机科学与工程学院,49,偏序集的哈斯图,用小圆圈或点表示A中的元素，省掉关系图中所有的环。(因自反性)对任意x,yA，若x y，则将x画在y的下方，可去掉关系图中所有边的箭头。(因反对称性)去掉有向边，即当（i，j）和（j，k）都是有向边时，去掉有向边（i，k）。(因传递性)按1),2),3)所作成的图称为哈斯图(Hasse图)。,2023/6/30,计算机科学与工程学院,50,偏序集的哈斯图,偏序关系R的Hasse图是由R的一个真子集cover(R)的关系图构成的。这个cover(R)又称为盖住关系，可以用符号表示为:求出了R的cover(R)，作Hasse图就容易了。(参见p111，例5-2.4),2023/6/30,计算机科学与工程学院,51,例5.6,设A2,3,6,12,24,36,“|”是A上的整除关系，画出其一般的关系图和哈斯图。,关系图,哈斯图,2,3,6,12,36,24,2,3,6,12,36,24,2023/6/30,计算机科学与工程学院,52,例5.7,设集合Aa，Ba,b，Ca,b,c。分别画出集合A、B、C、D之幂集 2A、2B、2C 上定义的“”的哈斯图。2A=，a2B=，a,b,a,b2C=，a,b,c,a,b,a,c,b,c,a,b,c,a,a,b,a,b,a,b,c,a,b,a,c,b,c,a,b,c,2023/6/30,计算机科学与工程学院,53,可比较的,定义5-6.2 设是一个偏序集，对任意x,yA，如果x y或y x，则称x与y是可比较的。否则，x与y是不可比较的。,例5.24集合A=a,b,c，偏序集中，a与a,b是可比的，a与b,c不是可比的。偏序集中，对任意x,yA，x与y都是可比的。偏序集中，对任意x,yA，x与y都是可比的。偏序集中，2与3不是可比的；2与6是可比的；2与8是可比的；对任意nN+，0与n是可比的。,2023/6/30,计算机科学与工程学院,54,可比较的,定义5-6.2 设是一个偏序集，对任意x,yA，如果x y或y x，则称x与y是可比较的。否则，x与y是不可比较的。,例5.24集合A=a,b,c，偏序集中，a与a,b是可比的，a与b,c不是可比的。偏序集中，对任意x,yA，x与y都是可比的。偏序集中，对任意x,yA，x与y都是可比的。偏序集中，2与3不是可比的；2与6是可比的；2与8是可比的；对任意nN+，0与n是可比的。,2023/6/30,计算机科学与工程学院,55,可比较的,定义5-6.2 设是一个偏序集，对任意x,yA，如果x y或y x，则称x与y是可比较的。否则，x与y是不可比较的。,例5.24集合A=a,b,c，偏序集中，a与a,b是可比的，a与b,c不是可比的。偏序集中，对任意x,yA，x与y都是可比的。偏序集中，对任意x,yA，x与y都是可比的。偏序集中，2与3不是可比的；2与6是可比的；2与8是可比的；对任意nN+，0与n是可比的。,2023/6/30,计算机科学与工程学院,56,可比较的,定义5-6.2 设是一个偏序集，对任意x,yA，如果x y或y x，则称x与y是可比较的。否则，x与y是不可比较的。,例5.24集合A=a,b,c，偏序集中，a与a,b是可比的，a与b,c不是可比的。偏序集中，对任意x,yA，x与y都是可比的。偏序集中，对任意x,yA，x与y都是可比的。偏序集中，2与3不是可比的；2与6是可比的；2与8是可比的；对任意nN+，0与n是可比的。,2023/6/30,计算机科学与工程学院,57,可比较的,定义5-6.2 设是一个偏序集，对任意x,yA，如果x y或y x，则称x与y是可比较的。否则，x与y是不可比较的。,例5.24集合A=a,b,c，偏序集中，a与a,b是可比的，a与b,c不是可比的。偏序集中，对任意x,yA，x与y都是可比的。偏序集中，对任意x,yA，x与y都是可比的。偏序集中，2与3不是可比的；2与6是可比的；2与8是可比的；对任意nN+，0与n是可比的。,2023/6/30,计算机科学与工程学院,58,5.3全序集与良序集,定义5-3.1如果偏序集中任何两个元素都是可比较的，则称是全序集，称 为A上的一个全序关系。例：实数集合上的“”关系是全序关系。,2023/6/30,计算机科学与工程学院,59,5.3全序集与良序集,定义5-3.2设是一个偏序集，。如果是一个全序子集，则称B为A中的一条链。链中元素数目减1称为该链的长度。例：36，12，6，3是偏序集:的一条长度为3的链。,2023/6/30,计算机科学与工程学院,60,5.3全序集与良序集,定义5-3.3 设是偏序集，a是A的一个元素。,1)若对任意bA,都有ba,则称a为A中的最大元。2)若对任意bA,都有ab,则称a为A中的最小元。3)若对任意bA,或者b a，或者b与a不可比较,则称a为 A中的极大元。4)若对任意bA,或者a b，或者b与a不可比较,则称a为 A中的极小元。注：参见教材p114例子。,2023/6/30,计算机科学与工程学院,61,偏序集中的特殊元素,定义5-3.3 设是偏序集，a是A的一个元素。,1)若对任意bA,都有ba,则称a为A中的最大元。2)若对任意bA,都有ab,则称a为A中的最小元。3)若对任意bA,或者b a，或者b与a不可比较,则称a为 A中的极大元。4)若对任意bA,或者a b，或者b与a不可比较,则称a为 A中的极小元。注：参见教材p114例子。,2023/6/30,计算机科学与工程学院,62,偏序集中的特殊元素,定义5-3.3 设是偏序集，a是A的一个元素。,1)若对任意bA,都有ba,则称a为A中的最大元。2)若对任意bA,都有ab,则称a为A中的最小元。3)若对任意bA,或者b a，或者b与a不可比较,则称a为 A中的极大元。4)若对任意bA,或者a b，或者b与a不可比较,则称a为 A中的极小元。注：参见教材p114例子。,2023/6/30,计算机科学与工程学院,63,偏序集中的特殊元素,定义5-3.3 设是偏序集，a是A的一个元素。,1)若对任意bA,都有ba,则称a为A中的最大元。2)若对任意bA,都有ab,则称a为A中的最小元。3)若对任意bA,或者b a，或者b与a不可比较,则称a为 A中的极大元。4)若对任意bA,或者a b，或者b与a不可比较,则称a为 A中的极小元。注：参见教材p114例子。,2023/6/30,计算机科学与工程学院,64,偏序集中的特殊元素,定义5-3.3 设是偏序集，a是A的一个元素。,1)若对任意bA,都有ba,则称a为A中的最大元。2)若对任意bA,都有ab,则称a为A中的最小元。3)若对任意bA,或者b a，或者b与a不可比较,则称a为 A中的极大元。4)若对任意bA,或者a b，或者b与a不可比较,则称a为 A中的极小元。注：参见教材p114例子。,显然，有限偏序集总存在极大元和极小元。,2023/6/30,计算机科学与工程学院,65,定义5-3.4 设B A，aA若对任意bB,都有b a,则称a为B的上界。若对任意bB,都有a b,则称a为B的下界。若元素cA是B的任何一个上界,若均有a c,则称a为B的 最小上界。若元素cA是B的任何一个下界,若均有c a,则称a为B的 最大下界。注意：上下界均针对于子集而言。,2023/6/30,计算机科学与工程学院,66,定义5-3.4 设B A，aA若对任意bB,都有b a,则称a为B的上界。若对任意bB,都有a b,则称a为B的下界。若元素cA是B的任何一个上界,若均有a c,则称a为B的 最小上界。若元素cA是B的任何一个下界,若均有c a,则称a为B的 最大下界。注意：上下界均针对于子集而言。,2023/6/30,计算机科学与工程学院,67,定义5-3.4 设B A，aA若对任意bB,都有b a,则称a为B的上界。若对任意bB,都有a b,则称a为B的下界。若元素cA是B的任何一个上界,若均有a c,则称a为B的 最小上界。若元素cA是B的任何一个下界,若均有c a,则称a为B的 最大下界。注意：上下界均针对于子集而言。,2023/6/30,计算机科学与工程学院,68,定义5-3.4 设B A，aA若对任意bB,都有b a,则称a为B的上界。若对任意bB,都有a b,则称a为B的下界。若元素cA是B的任何一个上界,若均有a c,则称a为B的 最小上界。若元素cA是B的任何一个下界,若均有c a,则称a为B的 最大下界。注意：上下界均针对于子集而言。（参见教材p114，例5-3.3）,2023/6/30,计算机科学与工程学院,69,例5.25 设集合A1,2,3,4,5,6,7,8，|是A上的整除关系，则是偏序集，考虑A的子集：B11,2,3,6，B22,3,5,7，B3A。求出B1，B2，B3的最大(小)元、极大(小)元、上(下)界、最小上界、最大下界。,6,1,6,1,6,1,6,1,无,无,2,3,5,7,2,3,5,7,无,1,无,1,无,1,5,6,7,8,1,无,1,无,1,2023/6/30,计算机科学与工程学院,70,例5.26 设集合Aa,b,c，考虑P(A)上的关系“”，则是偏序集。求2A的子集：B1a,b,b,c,b,c,，B2a,c,a,c，B32A的最大(小)元、极大(小)元、最小上界、最大下界。,无,a,b,b,c,a,b,c,a,b,c,a,c,无,a,c,a,c,a,c,a,b,c,a,c,a,b,c,a,b,c,a,b,c,a,b,c,2023/6/30,计算机科学与工程学院,71,例5.27 设Ax1,x2,x3,x4,x5,A上定义偏序集的哈斯图如下，求Bx3,x4,x5的最大(小)元、极大(小)元、上(下)界、最小上界、最大下界。,x5,x3,x4,x1,x2,2023/6/30,计算机科学与工程学院,72,解：,例5.27 设Ax1,x2,x3,x4,x5,A上定义偏序集的哈斯图如下，求Bx3,x4,x5的最大(小)元、极大(小)元、上(下)界、最小上界、最大下界。,最大元：无；最小元：x5；极大元：x3,x4；极小元：x5；上界：x1,x2；下界：x5；最小上界：无；最大下界：x5。,x5,x3,x4,x1,x2,2023/6/30,计算机科学与工程学院,73,解：,例5.27 设Ax1,x2,x3,x4,x5,A上定义偏序集的哈斯图如下，求Bx3,x4,x5的最大(小)元、极大(小)元、上(下)界、最小上界、最大下界。,最大元：无；最小元：x5；极大元：x3,x4；极小元：x5；上界：x1,x2；下界：x5；最小上界：无；最大下界：x5。,x5,x3,x4,x1,x2,2023/6/30,计算机科学与工程学院,74,例5.28,1）集合Aa,b,c上定义的关系R,2）实数集合R上定义的“”是全序关系，是全序集。3）集合Aa的幂集2A上定义的“”是全序关系，是全序集。若|A|，则不是全序集。,是一个全序关系，的哈斯图如右图。,2023/6/30,计算机科学与工程学院,75,例5.28,1）集合Aa,b,c上定义的关系R,2）实数集合R上定义的“”是全序关系，是全序集。3）集合Aa的幂集2A上定义的“”是全序关系，是全序集。若|A|，则不是全序集。,是一个全序关系，的哈斯图如右图。,a,b,c,2023/6/30,计算机科学与工程学院,76,例5.28,1）集合Aa,b,c上定义的关系R,2）实数集合R上定义的“”是全序关系，是全序集。3）集合Aa的幂集2A上定义的“”是全序关系，是全序集。若|A|，则不是全序集。,是一个全序关系，的哈斯图如右图。,a,b,c,2023/6/30,计算机科学与工程学院,77,例5.28,1）集合Aa,b,c上定义的关系R,2）实数集合R上定义的“”是全序关系，是全序集。3）集合Aa的幂集2A上定义的“”是全序关系，是全序集。若|A|，则不是全序集。,是一个全序关系，的哈斯图如右图。,a,b,c,2023/6/30,计算机科学与工程学院,78,例5.29：字典次序（自学）,计算机科学中常用的字典排序如下：设是一有限的字母表。上的字母组成的字母串叫上的字；*是包含空字“”的所有字组成的集合，建立*上的字典次序关系L：设 xx1x2x3xn，yy1y2y3ym,其中：x,y*，xi,yj(i1,2,.n；j1,2,.m)。.当x1y1时,若x1y1(x1、y1的大小由它们的ASCII码号进行比较）,则xLy；若y1x1,则yLx；,2023/6/30,计