离散数学3.11-12

,单击此处编辑母版标题样式,*,3,11,相容关系,一、相容关系,定义,设,R,是定义在集合,A,上的关系，如果,R,是,自反的、对称的,，则称此关系,R,为,A,上的,相容关系,。,1,3,11,相容关系,例如,，设,A,是由下列英文单词组成的集合。,A=cat,teacher,cold,desk,knife,by,定义关系：,R=|x,yA,且,x,和,y,有相同的字母,。,R,是不是相容关系？,令,x,1,=cat,x,2,=teacher,x,3,=cold,x,4,=desk,x,5,=knife,x,6,=by.,R,的关系图可由图表示。,R,的关系矩阵为,由于相容关系是自反和对称的，因此其关系矩阵的对角线元素都是,1,，且矩阵是对称的。,简化：用梯形表示关系矩阵，,关系图,中不画自回路，用单线代替来回弧线。,2,3,11,相容关系,定义,设,r,是集合,A,上的相容关系，如,C,A,，,如果对于,C,中任意两个元素,a,1,和,a,2,有,a,1,ra,2,，称,C,是由相容关系,r,产生的,相容类,。,例 上例中的相容关系,R,，下述集合是否为,R,的相容类？,x,1,x,2,x,1,x,5,x,1,x,2,x,3,x,2,x,4,x,5,第一个相容类，能加进一个新的元素,x,3,组成新的相容类，而最后一个相容类，加入任一新元素，就不再组成相容类，我们称它为,最大相容类,。,3,3,11,相容关系,定义,设,r,是集合,A,上的相容关系，不能真包含在任何其他,相容类中的相容类，称做,最大相容类,。记作,C,r,。,在相容关系图中，最大,完全多边形,的顶点集合，就是最,大相容类。,所谓,完全多边形,，就是其每个顶点都与其他顶点连接的,多边形。例如三个顶点的完全多边形，四个顶点的完全,多边形。,此外，在相容关系图中，一个孤立结点，以及不是完全,多边形的两个结点的连线，也是最大相容类。,4,3,11,相容关系,例,设给定相容关系图如图,3-11,、,3,，写出最大相容类。,解：最大相容类为：,a,1,a,2,a,4,a,6,a,3,a,4,a,6,a,4,a,5,a,7,5,3,11,相容关系,定理,r,是有限集,A,上的相容关系，,C,是一个相容类，那么必存在一个最大相容类,C,r,，,使,C,C,r,。,证明：设,A=a,1,，,a,2,，,，,a,n,，,构成相容类序列,，其中,C,0,=C,且,C,i+1,=,C,i,a,j,，,其中,j,是满足,a,j,不属于,C,i,而,a,j,与,C,i,中各元素都有相容关系的最小足标。,由于,A,的元素个数,|A|=n,，,所以至多经过,n-|C|,步，就使这个过程终止，而此序列的最后一个相容类，就是所要找到的最大相容类。,6,3,11,相容关系,定义,在集合,A,上给定相容关系,r,，,其中,最大相容类的集合,称作集合,A,的,完全覆盖,，记作,C,r,(A),。,注：,A,的覆盖不是唯一的，对于相容关系,r,，可以作成不同相容类的集合，它们都能构成,A,的覆盖；但是给定,A,上相容关系,r,，只对应一个完全覆盖。,定理,给定集合,A,的覆盖,A,1,A,2,A,n,，,由它确定的关系,R=A,1,A,1,A,2,A,2,A,n,A,n,是相容关系。,证明,7,3,11,相容关系,例：集合,A=1,2,3,4,，集合,1,2,3,3,4,和,1,2,2,3,1,3,3,4,都是,A,的覆盖，求它们分别对应的相容关系。,给定集合,A,上的任意一个覆盖，根据定理必可在,A,上构造,一个对应于此覆盖的一个相容关系。但是不同的覆盖却,能构造相同的相容关系。,定理,集合,A,上相容关系,r,与完全覆盖,Cr(A,),存在一一对应。,8,3-12,序关系,定义,偏,序关系,是上的二元关系，如果满足：,(1),自反的,(2,）反对称的,(3),传递的,则称是上,偏序关系,/,半序关系,/,部分序关系,(记为,),定义,集合,A,连同,A,上的偏序关系一起,称为一个,偏序,集,，记为 。,9,例：,整数集,I,上的二元关系,，,I,证明：,R,是个偏序关系。,是偏序集。,例,:,集合,A,的幂集,(,A),上定义的“,”关系,序关系,10,几点说明：,（,1,）同一集合上的两个不同的偏序关系，构成两个不同的偏序集。,如：,1,和,2,都定义在上，但,与,显然不是一样的偏序集。,（,2,）不同集合上分别相同定义的偏序关系，同样构成两个不同的偏序集。,如：,与,是,两个不同的,偏序,集。,序关系,11,哈斯图,二、,哈斯图,定义,设,是偏序集，,x,y,A,，,若有,x,y,，,x,y,，且,不存在其他元素,z,A,，,使得,x,z,z,y,，,则称,y,盖住,x,。,并且,COV A=|,x,y,A,y,盖住,x,例：,A=1,2,3,4,6,12,，定义在,A,上的偏序关系,R,为：,R=,，,求,COV A,12,序关系,根据上述定义，可以简化偏序关系的关系图得到哈斯,图，具体画法如下：,用小圆圈表示,A,中的元素，省掉关系图中所有的环。,(,自反性简化,),对任意,x,yA(xy),，若,xy,，,则将,x,画在,y,的下方，,对任意,COV A,，,则,x,与,y,之间用一条线相连之，否则无线相连,(,传递性简化,),。可省掉关系图中所有边的箭头,(,反对称性简化,),。,上例的哈斯图,13,序关系,例：,设,A,2,3,6,12,24,36,“,”,是,A,上的整除关系，画出其一般的关系图和哈斯图。,关系图,哈斯图,14,序关系,例：,设集合,A,a,，,B,a,b,，,C,a,b,c,。分别画出集合,A,、,B,、,C,之幂集,P,(,A)、,P,(B)、,P,(C),上定义的,“,”,的哈斯图。,15,三、全序关系,定义,设,是偏序集，,，若中每两个元素都有关系,，,则称为,链,。,若中每两个元素都无关，则称为,反链,。约定，若,B,只有单个元素，,B,既是链也是反链。,例题 设集合,A=,a,b,c,d,e,上的二元关系为,R=,验证,为偏序集，画出哈斯图，举例说明链和反链。,通过哈斯图可以看出：在每个链中总可以从,该链,最高结点出发沿着该盖住方向遍历该链中的所有结点。每个反链中任意两个结点间均无连线。,全序关系,16,全序关系,定义,设,为偏序集，若,A,是一个,链，,则称,为,A,上的全序关系或线序关系，,此时称,为全序集。也就是集合,A,中,任意的两个元素都有关系。,例题 给定,P=,a,a,b,a,b,c,上的,包含关系,，证明,是个全序集合。,17,偏序集与特殊元素,四、偏序集与特殊元素,设,是偏序集，且,B,是,A,的子集。对于,B,中的一个,元素,b,如果,B,中没有任何其他不同于,b,的元素,x,满足,bx,则,称,b,为,B,的,极大元素,。,对于,B,中的一个元素,b,如果,B,中没有任何其他不同于,b,的元素,x,满足,xb,则称,b,为,B,的,极小元素,。,当,B=A,时，偏序集,的极大元是哈斯图中最顶层的元,素，极小元是哈斯图中最低层的元素。,18,序关系,例：,设集合,A,1,2,3,4,5,6,7,8,，,D,是,A,上的整除关系，则,是偏序集，考虑,A,的子集：,B,1,1,2,3,6,，,B,2,2,3,5,7,，,B,3,A,。,求出,B,1,，,B,2,，,B,3,极大,(,小,),元。,在非空有限集合中，极大元素与极小元素必定存在，但不一定唯一。,集合,极大元,极小元,B,1,6,1,B,2,2,3,5,7,2,3,5,7,B,3,5,6,7,8,1,19,偏序集与特殊元素,定义,设,是偏序集，,B,是,A,的子集。,若存在元素,bB,使得对任意,xB,都有,xb,则,称,b,为,B,的,最大元素,。,若存在元素,bB,使得对任意,xB,都有,bx,则,称,b,为,B,的,最小元素,。,20,偏序集与特殊元素,定理：设,是偏序集，,B,是,A,的子集。,若,B,有最大,(,最小,),元，则必是唯一的。,21,序关系,例：,设集合,A,1,2,3,4,5,6,7,8,，,D,是,A,上的整除关系，则,是偏序集，考虑,A,的子集：,B,1,1,2,3,6,，,B,2,2,3,5,7,，,B,3,A,。,求出,B,1,，,B,2,，,B,3,的最大,(,小,),元。,最大元素和最小元素不一定存在，如果存在则必唯一。,集合,最大元,最小元,B,1,6,1,B,2,无,无,B,3,无,1,22,序关系,续：,若存在元素,aA,使得对任意,xB,都有,xa,则称,a,为,B,的上界,。,若存在元素,aA,使得对任意,xB,都有,ax,则称,a,为,B,的下界,。,上界和下界不是唯一的。,若元素,a,是,B,的任一上界,若对,B,的所有上界,y,均有,a,y,则称,a,为,B,的,上确界,（最小上界,),，记作,LUB B,。,若元素,b,是,B,的任一下界,若对,B,的所有下界,z,均有,z,b,则称,b,为,B的,下确界（最大下界,),，记作,GLB B,。,23,序关系,例：,设集合,A,1,2,3,4,5,6,7,8,，,D,是,A,上的整除关系，则,是偏序集，考虑,A,的子集：,B,1,1,2,3,6,，,B,2,2,3,5,7,，,B,3,A,。,求出,B,1,，,B,2,，,B,3,的上,(,下,),界、上,(,下,),确界。,集合,上界,下界,上确界,下确界,B,1,6,1,6,1,B,2,无,1,无,1,B,3,无,1,无,1,24,序关系,例：,设集合,A,a,b,c,，,考虑,P,(,A),上的关系,“,”,，则,是偏序集。求,P,(,A),的子集：,B,1,a,b,b,c,b,c,，,B,2,a,c,a,c,，,B,3,(A),的最大(小)元、极大(小)元、上(下)界、上(下)确界。,集合,最大元,最小元,极大元,极小元,上界,下界,上确界,下确界,B,1,无,a,b,b,c,a,b,c,a,b,c,B,2,a,c,无,a,c,a,c,a,c,a,b,c,a,c,B,3,a,b,c,a,b,c,a,b,c,a,b,c,25,序关系,例：,设,A,x,1,x,2,x,3,x,4,x,5,A,上定义偏序集,的哈斯图如下，求,B,x,3,x,4,x,5,的最大,(,小,),元、极大,(,小,),元、上,(,下,),界、上,(,下,),确界。,解,：最大元：无；,极大元：,x,3,x,4,；,上界：,x,1,x,2,；,上确界：无；,最小元：,x,5,；,极小元：,x,5,；,下界：,x,5,；,下确界：,x,5,。,26,一些结论：,设,是一偏序集，,B,是,A,的子集。则：,若,bB,是,B,的最大元,b,是,B,的极大元、上界、上确界；,若,bB,是,B,的最小元,b,是,B,的极小元、下界、下确界；,若,a,是,B,的上确界，且,aB,a,是,B,的最大元；,若,a,是,B,的下确界，且,aB,a,是,B,的最小元；,若“,”,是一个全序关系，则,bB,是,B,的最大元,bB,是,B,的极大元；,若“,”,是一个全序关系，则,bB,是,B,的最小元,bB,是,B,的极小元。,若,bB,是,B,的极大元，且,b,是唯一的,b,是,B,的最大元。,若,bB,是,B,的极小元，且,b,是唯一的,b,是,B,的最小元。,序关系,27,五、良序关系,定义,设,是一偏序集，若,A,的任何一个非空子集都有最小元素，则“,”,称为良序关系，,是良序集。,良序关系,例：,设在集合,A,a,b,c,上定义的偏序关系,“,”,的哈斯图如右图所示，是良序关系吗？,例：,是良序集？,是良序集？下例呢？不是良序集的情况,28,定理,（,1,）良序集是全序集,（,2,）全序集未必是良序的，,例：大于,0,小于,1,的全部实数，按大小次序关系是个全序集合，但由于集合本身就不存在最小元素，所以不是良序集合。,（,3,）有限的全序集是