离散数学课件 第三章 集合与关系-2.ppt

主标题,主文本标题,二级标题,三级标题,四级标题,五级标题,3-7,复合关系和逆关系,二元关系是以序偶为元素的集合，所以可以对它进行集合运算。,此外还有一种新的运算：,关系的复合,定义,3-7.1,设,R,是从集合,A,到集合,B,上的二元关系，,S,是从集合,B,到集合,C,上的二元关系，则,RS,称为,R,和,S,的,复合关系,，表示为,RS=,xAzC,y(yB,RS),复合关系举例,例：,A=1,，,2,，,3,，,4,，,B=3,，,5,，,7,，,C=1,，,2,，,3,R=,，,，,，,S=,，,则,RS=,，,如图所示：,复合关系的结合律,定理：,设,R,1,A,1,A,2,R,2,A,2,A,3,R,3,A,3,A,4,则,(R,1,R,2,)R,3,=R,1,(R,2,R,3,),。,例：,设,A=1,2,3,4,5,A,上的二元关系,R=,S=,则,R,S=,S,R=,R,S,(R,S),R=,R,(S,R)=,复合关系的矩阵表示（自学）,两个关系的复合可通过相应矩阵相乘获得。,复合关系练习,练习：,R,是,A,上的二元关系，试证,R,是传递的充要条件是,RR,R,证：,：,R,R,必,y,使得,R,，,R,R,是传递的,R,R,R,R,：,R,R,必有,R,R,R,R,R ,R,由,x,y,z,任意性知,x,y,z,(,R,R,R),R,是传递的,逆关系,定义,3-7.2,设,R,是,A,到,B,的二元关系，则,R,的逆,是,B,到,A,的二元关系，记为,R,c,，其中,R,c,=|,R,。,注：,（,1,）,xRy,yR,c,x,（,2,）,互换,R,的关系矩阵的行和列，即得,R,c,的关系矩阵。,即,M,R,c,M,R,T,（,3,）颠倒,R,的关系图中每条弧线的箭头方向，即得,R,c,的关系图。,逆关系举例,例,1,整数集上的,关系,集合族上的,关系的逆是,空关系的逆是空关系,A,B,的全域关系的逆是,B,A,的全域关系,例,2,A=0,1,2,3,，,R=,则,R,c,=,定理,定理：,设,R,R2,R1,是,A,到,B,的关系，则,a,）,(,R,c,),c,=R,b,）,(R1R2),c,=R1,c,R2,c,c,）,(R1R2),c,=R1,c,R2,d,）,(,R),c,=(,R,c,),R=A,B-R,即,R,的补的逆等于逆的补,e,）,(R1-R2),c,=R1,c,-R2,c,f),(,A,B),c,=BA,定理,定理,3-7.2,设,R,、,S,分别是,A,到,B,、,B,到,C,的关系，,则,(,RS),c,=S,c,R,c,证：设,是,(,RS),c,的任一元素，,则,(,RS),c,RS,b(,R,S),b(c,b,S,c,R,c,),S,c,R,c,定理,定理,3-7.3,R,是,A,上的二元关系,(a)R,是对称的,R=,R,c,(b)R,是反对称的,RR,c,I,A,证：,(a),：,任取,R,，,因为,R,是对称的，,所以,R,R,R,c,：,任取,R,，,则,R,c,R=,R,c,R,R,是对称的,(b),略,3-8,关系的闭包运算,设,R,是,A,上的关系，我们希望,R,具有某些有用的性质，比如说自反性。如果,R,不具有自反性，我们通过在,R,中添加一部分有序对来改造,R,，得到新的关系,R,，使得,R,具有自反性。但又不希望,R,与,R,相差太多，换句话说，添加的有序对要尽可能的少。满足这些要求的,R,就称为,R,的自反闭包。,通过添加有序对来构造,的,闭包,除自反闭包外还有对称闭包和传递闭包。,各种闭包的定义,定义,3-8.1,设,R,是非空集合,A,上的关系，,R,的自反（对称或传递）闭包是,A,上的关系,R,，使得,R,满足以下条件：,（,1,）,R,是,自反,的（,对称,的或,传递,的）,（,2,）,R,R,（,3,）,对,A,上任何包含,R,的自反（对称或传递）关系,R”,，有,R,R”,。一般将,R,的,自反闭包记作,r(R,),，,对称闭包记作,s(R,),，,传递闭包记作,t(R,),。,注：,R,的自反闭包记为,r(R,),若,R,是自反的，则,R=,r(R,),反之也成立。,R,的对称闭包记为,s(R,),若,R,是对称的，则,R=,s(R,),反之也成立。,R,的传递闭包记为,t(R,),若,R,是传递的，则,R=,t(R,),反之也成立。,构造闭包的方法,下面的定理给出了,构造闭包的方法,：,自反闭包,r(R,)=RI,A,对称闭包,s(R,)=,RR,c,传递闭包,t(R,)=RR,2,R,3,证明,r(R,)=RI,A,证：设,R=RI,A,x,A,R,R,具有自反性,R,R,设,R”,是自反的，且,R,R”,R,是自反的，,I,A,R”,又,R,R”,R=I,A,R,R”,综上所述，,R,满足自反闭包定义的三个条件,，,r(R,)=R=RI,A,证明,s(R,)=,RR,c,证明：设,R=,RR,c,R,c,=,(,RR,c,),c,=,R,c,(R,c,),c,=,R,c,R,=R,，,所以,R,是对称的,R=,RR,c,R,设,R”,是对称的，且,R,R”,，要证,R,R”,任取,RR,c,R,R,c,R”R,R”R”,R”R”,R”,R,=,RR,c,R,”,综上所述，由定义知道，,R,即,RR,c,为,R,的对称闭包。,证,t(R,)=RR,2,R,3,(R,为,A,上的二元关系）,证：,(1),证,t(R,),：,先用归纳法证，对,n0,R,n,t(R,),a),由定义,R,t(R,),b),设,R,n,t(R,),成立，要证,R,n+1,t(R,),任取,R,n+1,=,R,n,R,，,存在,cA,使,R,n,R,由归纳假设和基础步骤知,t(R,),，,t(R,）,t(R,),是传递的，,t(R,),即,R,n+1,t(R,),对一切,n,，,R,n,t,(R,),根据的结论，证,t(R,),：,任取,存在一个,n,，,使,R,n,t(R,),t(R,),t(R,),(2),证,t(R,),设,是 的任意元素,必,s,t,使得,R,s,R,t,R,t,R,s,=,R,t+s,是传递的,t(R,),是包含,R,的最小传递关系,t(R,),由（,1,），（,2,）得,t(R,),=,闭包运算举例,题：,设,A=,a,b,c,R,是,A,上的二元关系，且给定,R=,求,r(R),s(R),t(R,),。,解：,r(R,),=R I,A,=,s(R,),=R,R,c,=,t(R,),=RR,2,R,3,=RR,2,R,3,（因为,R,4,=R,R,5,=R,2,R,6,=R,3,),=,定理,3-8.5,设,R,为,X,上二元关系，,X,=n,，,那么，存在一个正整数,kn,，,使得,t(,)=R R,2,R,3,.,R,k,例：,P123,例题,2,求,R,+,的算法,Warshall,算法,AM i=1,对,i,列中出现,1,的各行，分别被,或,上,i,行,i=i+1,in,结束,Y,例：,P124,例题,3,P125,例题,4,设有一字母表,V=,A,B,C,D,e,d,f,并给定下面六条规则：,A-,Af,B-,Dde,C-e,A-B,B-De,D-Bf,R,为定义在,V,上的二元关系且,x,i,Rx,j,，即是从,x,i,出发用一条规则推出一串字符，使其第一个字符恰为,x,j,。说明每个字母连续应用上述规则可能推出的头字符。,闭包运算的性质,设,R,为集合,X,上的任一二元关系，那么,a)rs(R,)=,sr(R,),自反对称闭包等于对称自反闭包,b)tr(R,)=,rt(R,),传递自反闭包等于自反传递闭包,c)ts(R),st(R,),传递对称闭包包含对称传递闭包,证明,rs(R,)=,sr(R,),证：,rs(R,)=,r(s(R,),=,r(RR,c,),=,I,x,RR,c,=,I,x,RR,c,I,x,=(,I,x,R)(R,c,I,x,c,),=(,I,x,R),(RI,x,),c,=,s(I,x,R,),=,sr(R,),证明,rt(R,)=,tr(R,),证：,rt(R,)=,r(RR,2,),=I,X,RR,2,tr(R,)=,t(RI,X,),=I,X,R(I,X,R),2,(,I,X,R),n,=I,X,RR,2,R,n,rt(R,)=,tr(R,),注：以上证明引用了公式：（证明略）,(,RI,X,),n,=I,X,RR,2,R,n,证明,st(R,),ts(R,),证：先证,R,对称,t(R),对称,t,(R),-1,=(,RR,2,R,3,),-1,=,R,-1,(R,2,),-1,(R,3,),-1,=,R,-1,(R,-1,),2,(R,-1,),3,(,(F,G),-1,=G,-1,F,-1,，,定理,3-7.2,),=R R,2,R,3,=t,(R),t(R),对称,.,因为,R,s(R,),故,st,(R),st(s,(R),而,st(s,(R)=,sts(R,)=,s(,t,s,(R),)=,ts,(R),st,(R),ts,(R).,注：,st(R),ts(R,),未必成立。,反例：设,R=,则,s(R,)=,t(s(R,)=,s(t(R,)=s,=,t(s(R,),注意：先做传递，再做对称，有可能破坏传递性。,3-9,集合的划分和覆盖,除了把两个集合相互比较外，还常把一个集合分成若干子集讨论。,定义,3-9.1,设,A,为非空集，,S=S,1,S,m,S,i,A,，,S,i,(i=1m),且,S,1,S,2,.,S,m,=A,，,称,S,是,A,的覆盖,.,若再加,S,i,S,j,=,(,i,j,=1,m,i,j),则称,S,是,A,的划分,m,称为,划分的秩,。,集合的划分和覆盖举例,例,1,设,A=1,2,3,4,5,，,下面哪些是覆盖，哪些是划分：,(1)X=1,2,3,4,5,(2)Y=1,2,2,3,4,5,(3)Z=1,2,3,4,(4)U=1,2,3,4,5,(5)V=1,2,3,4,5,U,称为,A,的,最小划分,，,V,称为,A,的,最大划分,。,交叉划分,定义,3-9.2,若,S,1,=A,1,A,m,S,2,=B,1,B,n,是,A,的二个划分,则,S=A,i,B,j,|A,i,S,1,B,j,S,2,称为,A,的交叉划分,。,定理,3-9.1,设,A,1,A,2,A,m,与,B,1,B,2,B,n,为同一集合,A,的两个划分。则其交叉划分,A,i,B,j,亦是原集合的一种划分。,交叉划分举例,例：,设,B,是所有生物的集合,可划分成,A,P,其中,A,表示所有动物,Animal,的集合,P,表示所有植物,Plant,的集合。,B,也可划分成,F,L,其中,F,表示史前,First,生物,L,表示史后,Last,生物。,它们的交叉划分为,:,D=AF,AL,PF,PL,其中,AF,是史前动物,AL,是史后动物,PF,是史前植物,PL,是史后植物。,加细,定义,3-9.3,设,S,S,是集合,A,的二个划分，若,S,的每一块均是,S,中某块的子集，,S,是,S,的,加细。,例,:,A=,正整数集,S=1,3,5,7,2,4,6,S=1,5,9,3,7,，,11,2,4,6,则,S,是,S,的细分,定理,3-9.2,任何两种划分的交叉划分，都是原来各划分的一种加细。,练习：,3-9,（,2,）,证明：,1.,aA,，,a,与,a,在同一分块中，故必有,aRa,。故,R,是自反的。,2.,若,a,与,b,在同一分块中，,b,与,a,也必在同一分块中，即,aRb,bRa,，故,R,是对称的。,3.,若,a,与,b,在同一分块中，,b,与,c,在同一分块中，根据划分的定义，,b,属于且仅属于一个分块，故,a,与,c,必在同一分块中。,即,aRb,bRc,aRc,，故,R,是传递的。,3-10,等价关系与等价类,等价关系是一类重要的二元关系。,定义,3-10.1,若集合,A,上的二元关系,R,是,自反的,，,对称的,和,传递的,，称,R,是,等价关系,。若,R,是等价关系，,aRb,，,可读为“,a,等价于,b”,。,例如，,数中的相等关系，是等价关系,集合中的相等关系，是等价关系,命题演算中,关系，是等价关系,全域关系是等价关系，空集上任何关系是等价关系。,等价关系举例,例：,设,A=1,2,8,，如下定义,A,上的关系,R,：,R=|x,，,yAxy(mod,3),其中,xy(mod,3),叫做,模,3,同余,，即,x,除以,3,的余数与,y,除以,3,的余数相等。不难验证,R,为,A,上的等价关系，因为,xA,，有,xx(mod,3),，,x,，,yA,，若,xy(mod,3),，则有,yx(mod,3),，,x,，,y,，,zA,，若,xy(mod,3),，,yz(mod,3),，则有,xz(mod,3),。该关系的关系图如下：,等价关系举例（续）,不难看出，上述关系图被分为三个互不相连通的部分。每部分中的数两两都有关系，不同部分中的数则没有关系。,每一部分中的所有的顶点构成一个等价类。,等价类,定义,3-10.2,设,R,是,A,上的等价关系，,对,a,A,，集合,a,R,=,x|xRa,称为,a,关于,R,的等价类,，简记为,a,，,a,称为等价类,a,R,的,表示元素,。,从以上定义可以知道，,a,的等价类是,A,中所有与,a,等价的元素构成的集合。,上例中的等价类是：,1=4=7=1,4,7,2=5=8=2,5,8,3=6=3,6,例：,设,I,是整数集，,R,是模,3,同余关系，,即,R=|x,Iy,Ix,y(mod3),不难验证,R,是等价关系，其等价类为,0,R,=-6,-3,0,3,6,1,R,=-2,1,4,2,R,=-4,-1,2,5,等价类的每一元素均可作本等价类的表示元素。,定理,3-10.1,设给定集合,A,上的等价关系,R,，,对于,a,b,A,有,aRb,iff,a,R,=,b,R,证：,aa,R,=,b,R,根据等价类定义,aRb,aRb,xa,R,xRa,xRb,xb,R,由,x,的任意性知，,a,R,=,b,R,商集,定义,3-10.3,集合,A,上的等价关系,R,，,其,等价类集合,a,R,|a,A,，,称为,A,关于,R,的商集,，,记为,A/R,。,例,1,：,A=1,2,8,，,R=|x,，,yAxy(mod,3),则,A/R=,1,4,7,2,5,8,3,6,例,2,：,A,为正整数集合，,R,是模,3,同余关系，,则,A/R=,0,R,1,R,2,R,，,其中,0,R,=-6,-3,0,3,6,1,R,=-2,1,4,2,R,=-4,-1,2,5,显然：,商集是集合的集合。,商集的每个元素是等价关系的一个等价类。,等价类中的每个元素都是集合,A,上的元素。,同一等价类中的任意两个元素都具有关系,R,。,商集举例,例：设集合,S=a,b,c,d,e,f,g,，,S,上的等价关系,R,如下表所示，求商集,S/R,。,a,b,c,d,e,f,g,a,b,c,d,e,f,g,S/R,=a,b,c,d,e,f,g,思考：,R=?,根据等价类对集合进行划分,定理,3-10.2,集合,A,上的等价关系,R,决定了,A,的一个划分，即为商集,A/R,。,证明,A/R=,a,R,|a,A,（,1,）,根据等价类定义，,a,A,，,a,R,A,a,R,A,a,A,，,aRa,a,a,R,A,a,R,a,R,=A,A/R,是一个覆盖,根据等价类对集合进行划分,（,2,）,证：需证,a,b,A,，若,a,R,b,R,，,则,a,R,b,R,=,。,反证法：若,a,R,b,R,则,c,a,R,b,R,cRa,且,cRb,R,是对称、传递的,aRb,则,a,R,=,b,R,，这与前提矛盾。,由（,1,），（,2,）得,A/R,是一个划分。,定理,3-10.3,集合,A,的任一,划分,S,确定,了,A,的一个,等价关系,R,。,证明,设,S=S,1,，,S,2,，,S,m,（,构造性证明）,定义关系,R:,aRb,当且仅当,a,b,在,S,的同一块中，,现证,R,是等价关系。,(1),a,A,，,a,与,a,在同一块中,aRa,，,自反性成立,。,(2),a,b,A,，,若,aRb,，则,a,与,b,在同一块中，则,b,与,a,也在同一块,bRa,，,即,aRb,bRa,对称性成立,(3),a,b,c,A,，,若,aRb,，,bRc,，,则,a,与,b,在同一块，,b,与,c,在同一块,S,i,S,j,=,(,i,j,),a,与,c,在同一块，即,aRbbRc,aRc,传递性成立,综上所述，,R,是,A,的一个等价关系，且,A/R=S,定理,3-10.3,举例,例：,A=,a,b,c,d,e,，,S=,a,b,c,d,e,，,求由,S,确定的等价关系。,解：,设,R1=,a,b,a,b,=,R2=,c,c,=R3=,d,e,d,e,=,则,R=R1R2R3,是由,S,确定的等价关系。,若,S=,a,b,c,d,e,，,则由,S,确定的等价关系是什么？,定理,3-10.4,设,R1,，,R2,是非空集合,A,上的等价关系，则,R1=R2,A/R1=A/R2,。,证明,：若,R1=R2,A/R1=a,R1,|a,A,，,A/R2=a,R2,|a,A,则,x,a,R1,R1,R2,x,a,R2,，,a,R1,a,R2,同理可证，,a,R2,a,R1,a,R1,=a,R2,A/R1=A/R2,：,a,A,，,a,R1,A/R1,A/R1=A/R2,必,c,R2,A/R2,，使,a,R1,=c,R2,a,b,A,R1,a,a,R1,b,a,R1,a,c,R2,b,c,R2,R2,R1,R2,同理可证：,R2,R1,R1=R2,综上所述，,R1=R2,A/R1=A/R2,例：,设,和,是非空集,A,的划分,R,、,R,是分别由,、,确定的等价关系，试证,细分,R,R,证：,：,R,则,a,、,b,在,的同一块中，,细分,a,、,b,在,的同一块,R,R,R,：设,S,i,a,S,i,，,则,S,i,=,a,R,=,x|xRa,x,S,i,xRa,xRa,x,a,R,a,R,a,R,由,S,i,的任意性，知,细分,细分,R,R,加细（细分）图解,3-11,相容关系,定义,3-11.1,设,R,是集合,A,上的二元关系，若,R,是自反的和对称的，称,R,是,相容关系,。,例：,所有等价关系是相容关系；,在一群人的集合中,朋友关系也是相容关系。,相容关系的表示方法,因为相容关系是自反和对称的,其关系矩阵是对称的且主对角线元素全为,1,因此我们可仅用下三角矩阵,T,来表示和存储就够了,即关系矩阵可以简化为“,阶梯形,”。,相容关系的关系图可简记为：用无向边代替二有向边 自回路省略,相容关系的表示方法,(P135,例题,),1,1,1,0,0,0,1,1,1,1,1,0,1,1,1,1,0,0,0,1,1,1,1,0,0,1,0,1,1,0,0,0,0,0,0,1,x,1,x,6,x,4,x,3,x,2,x,5,相容关系,r,的矩阵及图形表示,定义,3-11.2,设,R,是集合,A,上的相容关系,若,C,A,若任意,a,b,C,有,aRb,则称,C,是由,R,产生的,相容类。,例：上例相容关系,r,产生的相容类。,最大相容类,定义,3-11.3,设,R,为定义在集合,A,上的相容关系，如果不能真包含在任何其他相容类中的相容类，称作,最大相容类,，,记为,C,R,。,例：,P137,例题,1,a,3,a,4,a,2,a,5,a,7,a,6,a,1,相容关系的确定,利用相容关系的关系图来确定相容类和最大相容类是方便的。,极大完全子图的顶点集合就是最大相容类。,所谓极大完全子图是指每对顶点都有边相连的多边形,而最大相容类外的任何顶点不可能与类内的所有顶点相连。,另外,孤立顶点,以及不在极大完全子图,两个顶点及其连线,也是最大相容类。,例,设给定的相容关系图表示成下图,写出所有的最大相容类。,解,最大相容类：,h,a,b,d,e,f,b,c,d,f,g,。,完全覆盖,定义,3-11.4,设,R,为定义在集合,A,上的相容关系，其最大相容类的集合称作集合,A,的,完全覆盖,，,记为,C,R,(A),。,例,1,：,1,2,3,4,5,6,A,的完全覆盖是：,1,，,2,，,3,，,4,，,5,，,6,，,5,，,2,，,6,，,3,3-12,序关系,定义,3-12.1,若集合,A,上的二元关系,R,是,自反,的、,反对称,的和,传递,的，则称,R,是,A,的,偏序关系,，,记作 。设 为偏序关系，如果,，则记作,x y,，读作“小于或等于”。,序偶,称为,偏序集合,。,注意这里的“小于或等于”不是指数的大小，而是在偏序关系中的顺序性。,x“,小于或等于”,y,的含义是：依照这个序，,x,排在,y,的前边或者,x,就是,y,。,根据不同偏序的定义，对序有着不同的解释。,例如整除关系是偏序关系，,3 6,的含义是,3,整除,6,。大于或等于关系也是偏序关系，针对这个关系写,5 4,是说大于或等于,4,关系中,5,排在,4,的前边，也就是,5,比,4,大。,盖住,定义,3-12.2,在偏序集,中，如果,x,y,A,，,x,y,，,x,y,，,且没有其他元素,z,满足,x,z,、,z,y,，,则称元素,y,盖住,元素,x,。,并且把所有具备盖住性质的续偶集合记作,COV A,，,COV A=|,y,盖住,x,例：,A,为正整数,m,12,的因子的集合，并设,为整除关系，求,COV A,。,(P140),哈斯图（偏序集合图）,对于给定的偏序集,，,它的盖住关系是唯一的，所以,可以用哈斯图表示偏序集合图,。,哈斯图作图规则：,用小圆圈代表元素。,如果,x y,，,且,x,y,，,则将代表,y,的小圆圈画在代表,x,的小圆圈之上。,如果,COV A,则在,x,与,y,之间用直线连接。,哈斯图举例,例：画出偏序集,的哈斯图。,哈斯图举例（续）,例：,A=,a,b,c,，,画出,的哈斯图。,a,b,c,a,b,a,c,b,c,a,b,c,哈斯图举例（续）,例：已知偏序集,的哈斯图如图所示，试求出集合,A,和关系,R,的表达式。,解：,A=,a,b,c,d,e,f,g,h,R=,I,A,a,b,c,d,e,f,h,g,偏序集中的特殊元素,定义,3-12.5,3-12.6,设,为偏序集，,B,是,A,的子集，,yB,。,若,x(xBy,x),成立，则称,y,为,B,的最小元,。,若,x(xBx,y),成立，则称,y,为,B,的最大元。,若,b,B,且,B,中不存在任何元素,x,使,b,x,且,b x,称,b,是,B,的极大元,。,若,b,B,且,B,中不存在任何元素,x,使,b,x,且,x b,称,b,是,B,的极小元,。,例：设偏序集,如图所示，求,A,的极小元，最小元，极大元，最大元。,a,b,c,d,e,f,h,g,解,:,极小元：,a,b,c,g,。,极大元：,a,f,h,。没有最小元与最大元。由这个例子可以知道，,哈斯图中的孤立顶点既是极小元也是极大元,。,b,a,e,d,c,解：,A,不存在最大、最小元；极大元素为,d,e,极小元素为,a,b,；,B,的最大元素为,c,，,没有最小元素；极大元素为,c,极小元素为,a,b,。,例：设,A=,a,b,c,d,e,、,B=,a,b,c,，则各自的最大最小元素、极大极小元素是哪些？,最小元是,B,中最小的元素,，它与,B,中其它元素都可比；而极小元不一定与,B,中元素可比，,只要没有比它小的元素，它就是极小元,。对于有穷集,B,，,极小元一定存在，但最小元不一定存在,。最小元如果存在，一定是唯一的，但极小元可能有多个。如果,B,中只有一个极小元，则它一定是,B,的最小元。如果,B,中存在最小元，则它一定是,B,的唯一极小元。类似的，极大元与最大元也有这种区别。,定理,3-12.1,设,是一偏序集合，且,B,A,，若,B,有最大（最小）元，则是唯一的。,证：设,a,b,都是,B,的最大元素，,那么,a,b,b,a,，,从偏序关系的反对称性，得,a=b,。,最小元证明情况与此类似。,上界、下界,定义,3-12.7,，,3-12.8,设,为偏序集，,B,A,，,yA,。（,1,）若,x(xBx,y),成立，则称,y,为,B,的上界,。（,2,）若,x(xBy,x),成立，则称,y,为,B,的下界,。（,3,）令,C,y|y,为,B,的上界,，则称,C,的最小元为,B,的最小上界或上确界,。（,4,）令,D,y|y,为,B,的下界,，则称,D,的最大元为,B,的最大下界或下确界,。,设,为有序集，,B,A,。,的哈斯图如下所示。,A=a,，,b,，,c,，,d,，,e,，,f,，,g,，,h,，,i,，,j,，,k,B,=a,，,b,，,c,，,d,，,e,，,f,，,g,B,=h,，,i,，,j,，,k,j,k,h,i,f,g,e,d,c,b,a,j,k,h,i,f,g,e,d,c,b,a,B,B,的上界,B,的,下,界,B,由定义可知，,B,的最小元一定是,B,的下界，同时也是,B,的最大下界,。同样的，,B,的最大元一定是,B,的上界，同时也是,B,的最小上界,。但,反过来不一定正确,，,B,的下界不一定是,B,的最小元，因为它可能不是,B,中的元素。同样的，,B,的上界也不一定是,B,的最大元。,序关系（注意）,（,1,）,B,的最大（小）元素和极大（小）元素必须是子集,B,的元素，而,B,的上界（下界）和最小上界（最大下界）可以是也可以不是,B,的元素。,（,2,）,上界和下界可以存在也可以不存在，可以唯一也可以不唯一。,（,3,）,极大元素和极小元素可以唯一也可以不唯一。,（,4,）,最大元素、最小元素可以存在也可以不存在，但若存在则唯一。,（,5,）,对于非空有限偏序集合，其极大元素和极小元素总是存在。,序关系（说明）,1,、设,是偏序集合，,B,是,A,的子集，,（,a,）,如果,b,是,B,的最大元素，那么,b,是,B,的极大元素，且极大元素唯一。,（,b,）,如果,b,是,B,的最大元素，那么,b,是,B,的最小上界。,（,c,）,如果,b,是,B,的上界且,b,B,则,b,是,B,的最大元素。,（对最小元素、极小元素和最大下界也存在类似的关系）,2,、对,来说，它的逆,也是一个偏序集合，偏序 的,P,中的最大元素、极大元素、上界、最小上界，是,P,中的最小元素、极小元素、下界、最大下界，反之亦然。,拟序,定义：,若集合,A,上的二元关系,R,是反自反的、传递的，则称,R,是,A,的,拟序关系,，序偶,称为拟序集合。,全序关系,在偏序集合,中，,B,A,，若每一,a,、,b,B,，,都有,a b,或,b a,称,B,为,链（即,B,中任意两元素都有关系）,；若,B,中任意两元素都是无关的，则称,是,反链。,定义,3-12.4,在偏序集,中,，若是链，则称,为,全序,(,线序,),集合,，称为,全序,(,线序,),关系。,全序（线序）举例,例：,是一全序集合；,不是一个全序集合；,P=,a,a,b,a,b,c,上的包含关系,，,是全序集。其哈斯图如下：,注：,全序集合的哈斯图是一竖立的结点序列，每相邻的结点用一条弧连接。,a,a,b,c,a,b,良序,定义,3-12.9,任一,偏序集合,，假如它的每个非空子集，都有最小元素，则这种偏序集合是,良序集合。,例：,n=1,2,3,n,对于小于等于关系来说是良序集合。但,不是良序集合。,定理,3-12.2,每一个良序集合，一定是全序集合。,证明：,设,是良序集，那么对任意两个元素,x,y,A,可构成子集,x,y,，,必存在最小元素，这个最小元素不是,x,就是,y,，,因此一定有,x,y,或,y,x,。,定理,3-12.3,每一个有限的全序集合，一定是良序集合。,证明：,设,A=a,1,a,2,a,n,，,令,是全序集，现假定,不是良序集合，那么必存在一个非空集合,B,A,，,在,B,中不存在最小元素，由于,B,是一个有限集合，故一定可以找到两个元素,x,与,y,是无关的，由于,是全序集，,x,yA,，,所以,x,y,必有关系，得出矛盾。故,是良序集合。,上述结论对于无限的全序集合不一定成立。,