第3章二元关系精选PPT.ppt

第3章二元关系第1页，本讲稿共121页主要内容 3.1 基本概念基本概念3.2 关系的合成关系的合成3.3 关系上的闭包运算关系上的闭包运算3.4 次序关系次序关系3.5 等价关系和划分等价关系和划分第2页，本讲稿共121页3.1基本概念n3.1.1 关系一个非常普遍的概念n数值的大于关系、整除关系，人类的父子关系、师生关系、同学关系例1nA=a,b,c,d是某乒乓球队的男队员集合，B=e,f,g是女队员集合.A和B之间的混双配对关系：AB=|xAyB=,例2n令=1,2,3,4,A中元素间的关系R：R=,AA第3页，本讲稿共121页n定义 3.1-1 关系如果A1,A2,An是集合，R A1A2An，则称R是A1A2An上的n元关系如果 RAn，则称R是A上的n元关系n定义3.1-2 空关系与全域关系设R是A1A2An上的n元关系n若R=，称R为A1A2An上的空关系n若R=A1A2An，称R为A1A2An上的全域关系n恒等关系A上的恒等关系IA定义为：IA AA，且IA=|xA 例A=1,2,3,则IA=,第4页，本讲稿共121页n思考若R和S都是关系，且R=,，S=,，R=S？n错误n定义3.1-3 关系的相等R1是 A1A2An上 的 n元 关 系,R2是B1B2Bm上的m元关系.那么R1=R2,当且仅当n=m,且对一切i,1in,Ai=Bi,并且R1和R2是相等的有序n元组集合第5页，本讲稿共121页3.1.2 二元关系n设A、是集合，如果R AB，则称R是一个从A到B的二元关系，若RA2，则称R是A上的二元关系n二元关系简称为关系关系nR xRy 也称之为x与y有R关系nR xRy 也称之为x与y没有R关系后缀表示法后缀表示法中缀表示法中缀表示法第6页，本讲稿共121页例nR是实数集合，R上的几个关系x2+y2=4=xy第7页，本讲稿共121页3.1.3 关系矩阵和关系图n关系矩阵有限集合之间的关系可以用矩阵表示便于用计算机来处理设A=a1,a2,am，B=b1,b2,bn是有限集，RAB，A到B的二元关系R可用mn阶矩阵表示：MR=(rij)mn，其中rij=1,如果aiRbj 0,如aiRbj 则称矩阵MR=rij是R的关系矩阵第8页，本讲稿共121页n例A=a1,a2,B=b1,b2,b3nR是A到B的关系，R=,b1 b2 b3a1 1 0 1a2 1 1 0MR=1 0 11 1 0nS是B上的关系，S=,b1 b2 b3b1 1 0 1b2 1 1 0b3 0 1 0MS=1 0 1 1 1 0 0 1 0第9页，本讲稿共121页n关系图有向图两种情况nR ABnR AA例：设A=1,2,3,4,B=a,b,cnR AB，R=,nS AA，S=,1。2。3。4。A。B。abcGR:GS:1。4。23第10页，本讲稿共121页关系的定义域与值域n设R AB定义域定义域(domain)：由所有R的第一个分量组成的集合，称为R的定义域，记作dom R，即 dom R=x|y(R)值域值域(range)：由所有R的第二个分量组成的集合，称为R的值域，记作ran R，即 ran R=y|x(R)例：A=1,2,3,4,R AA，R=,ndom R=1,2nran R=1,2,3第11页，本讲稿共121页关系的集合运算n关系就是集合n、-、和补运算对关系也适用n特别的R=(AB)-R第12页，本讲稿共121页思考题n设A和B分别是n元和m元有限集，则共有多少个不同的A到B的关系？n设A(和B)都是非空有限集，则A上的空关系、恒等关系和A上(A到B的)全关系的关系图和关系矩阵有何特点。n怎样通过关系图和关系矩阵求domR和ranR第13页，本讲稿共121页3.1.4 关系的特性n最重要的一节最重要的一节n这里关系都是集合A上的关系n关系的性质主要有自反性反自反性对称性反对称性传递性第14页，本讲稿共121页n设R是A上的二元关系，如果对于xA都有R(xRx)，则称R是A上的自反关系.即 R是A上的自反关系x(xAxRx)例：A=1,2,3nR1=,不是自反关系nR2=,自反关系n空关系不是自反关系n全关系、恒等关系自反关系自反关系第15页，本讲稿共121页自反关系的特征n定理：设R是集合A上的关系，则R具有自反性 iff IAR证明：必要性xA，由R自反知 R，IAR充分性xA，由IA的定义知 IA，R，即R是自反的n自反关系的关系矩阵主对角线上的所有元素均为1n自反关系的关系图每个结点都有自环线第16页，本讲稿共121页n令A=1,2,3，下列哪些关系是自反的1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R7R8第17页，本讲稿共121页反自反关系n设R是集合A上的关系，如果对于xA都有R，则称R为A上的反自反关系。即 R是A上的反自反关系x(xAR)例：A=1,2,3nS1=,不是反自反关系nS2=,反自反关系n空关系反自反关系第18页，本讲稿共121页反自反关系的特征n定理：设R是集合A上的关系，则R具有反自反性 iff IAR=证明：必要性xA，由R反自反知 R，IAR=充分性假设R不是反自反的，即存在xA，R，则 IAR，与IAR=矛盾 n反自反关系的关系矩阵主对角线上的所有元素均为0n反自反关系的关系图每个结点都没有自环线第19页，本讲稿共121页n令A=1,2,3，下列哪些关系是反自反的1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R7R8第20页，本讲稿共121页思考题n设A是n元有限集共有多少个A上的不同的自反关系？共有多少个A上的不同的反自反关系？n是否存在满足下列要求的关系，若有，请给出实例既自反又反自反既不自反又不反自反空集上的空关系空集上的空关系第21页，本讲稿共121页对称关系n设R是集合A上的关系，若对任何x,yA,只要有xRy,就必有yRx,则称R为A上的对称关系，即 R是A上的对称关系xy(xAyAxRy yRx)n例：邻居关系，朋友关系A=1,2,3nR=,nIAn空关系n全关系第22页，本讲稿共121页对称关系的特征n对称关系的关系矩阵根据主对角线对称n对称关系的关系图在两个不同的结点之间，若有边的话，则有方向相反的两条边（平行线）第23页，本讲稿共121页n令A=1,2,3，下列哪些关系是对称的1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R7R8第24页，本讲稿共121页反对称关系n设R是集合A上的关系,若对x,yA,如果有xRy,和yRx,就有x=y,则称R为A上的反对称关系，即R是A上的反对称关系xy(xAyAxRyyRx)x=y)xy(xAyAxyxRy)y x)Rn例：A=1,2,3R1=,R2=,IA空关系第25页，本讲稿共121页反对称关系的特征n反对称关系的关系矩阵以主对角线为对称的两个元素中最多有一个1n反对称关系的关系图两个不同的结点之间最多有一条边第26页，本讲稿共121页n令A=1,2,3，下列哪些关系是反对称的1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R7R8第27页，本讲稿共121页思考题n是否存在满足下列要求的关系，若有，请给出实例既对称又反对称既不对称又不反对称n设A是n元有限集共有多少个A上的不同的对称关系？共有多少个A上的不同的反对称关系？共有多少个A上不同的既对称又反对称的关系？IA第28页，本讲稿共121页传递关系nR是A上的关系，对x,y,zA,如果有xRy,和yRz,就有xRz,则称R为A上的传递关系，即R是A上的传递关系xyz(xAyAzAxRyyRz)xRz)n例，=，A=1,2,3,4nR1=,nR2=,nIAn空关系，全关系第29页，本讲稿共121页传递关系的特征n传递关系的关系矩阵如果aij=1,且ajk=1,则aik=1n传递关系的关系图如果有边,则也有边第30页，本讲稿共121页n令A=1,2,3，下列哪些关系是传递的1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R7R8第31页，本讲稿共121页练习n设R是集合A上的一个自反关系,求证：R是对称和传递的，iff 若,R,则 R证明：必要性:已知R是对称和传递的，设R，R，(要证明 R)因为R对称故R,又R 是传递的，且R得R充分性:已知a,b,cA，若，R,则 R先证先证R对称对称：R，(要证明 R)因为R是自反的,所以R，由R且R，根据已知条件得R，即R是对称的再证再证R传递传递：a,b,cA 设 R，R(要证明R)由R对称,得R，由R且R，根据已知条件得R 所以R是传递的第32页，本讲稿共121页n从下列各题给出的备选答案中选出正确的答案，并将其代号填入题后面的括号内。(1)设A=0,1,2,3，A上的关系R=,，则R是A.自反的 B.对称的 C.反对称的 D.可传递的 ()(2)设R是整数集I上的关系，定义为当且仅当|i1-i2|10时，i1Ri2，则R是A.自反的 B.对称的 C.反对称的 D.可传递的 ()B A B 第33页，本讲稿共121页n下图给出了1,2,3上三个关系的关系图，试对每一个图所表示的关系的性质作出判别，并将选中的性质的代号填入相应的括号内A.自反的 B.对称的 C.反对称的 D.传递的 E.反自反则1是（）则2是（）则3是（）ABAB A A E E第34页，本讲稿共121页思考题n关系的性质对于集合运算是否保持封闭？即自反（反自反、对称、反对称、传递）关系的交、并、差、对称差及补关系是否仍是自反（反自反、对称、反对称、传递）的？反对称传递对称反自反自反 R1R1R2R1-R2R1R2R1R2R1,R2不反对称不反对称反对称不反对称反对称不传递不传递不传递不传递传递对称对称对称对称对称不反自反反自反反自反反自反反自反不自反不自反不自反自反自反第35页，本讲稿共121页3.2 关系的合成（复合）n3.2.1 关系的合成定义定义:设是R1从A到B的关系，R2是从B到C的关系，则R1和R2的复合关系是从A到C的关系，记作R1R2(R1R2)，定义为：R1R2=|xAzCy(yBR1R2)例nR兄妹关系，S母子母子关系，RS舅舅和外甥舅舅和外甥关系nA=1,2,3,4,B=2,3,4,C=1,2,3,R是A到B的关系;S是B到C的关系R=x+y=6=,S=y-z=1=,R S=,第36页，本讲稿共121页练习nA=1,2,3 B=1,2,3.4 C=1,2,3,4,5R AB S BCR=,S=,求 R S=,。C123。41。2。3。A1。2。3。A。B123。4RS5。C123。45第37页，本讲稿共121页n设A=1,2,3,4,5,R和S都是A上二元关系.如果R=,S=,求RS，SR，(RS)R，R(SR)，RR，SSRS=,SR=,(RS)R=R(SR)=RR=,SS=,不满足交换律满足结合律？第38页，本讲稿共121页关系复合运算的性质n设R是A到B的二元关系,IA,IB分别是A和B上的相等关系,则IAR=RIB=Rn例：令A=1,2,3,B=a,b,c,d1。2。3。AIA。Babc。dR1。2。3。ARIB。abc。d。Babc。d1。2。3。AB第39页，本讲稿共121页n定理3.21设R1是从A到B的关系,R2和R3是从B到C的关系,R4是从C到D的关系,则(a)R1(R2R3)=R1R2R1R3(b)R1(R2R3)R1R2R1R3(c)(R2R3)R4=R2R4R3R4(d)(R2R3)R4R2R4R3R4第40页，本讲稿共121页证明(a)任取R1(R2R3)b(bBR1R2R3)b(bBR1(R2R3)b(bBR1R2)(bBR1R3)b(bBR1R2)b(bBR1R3)R1R2R1R3(R1R2)(R1R3)所以R1(R2R3)=(R1R2)(R1R3)第41页，本讲稿共121页证明(b)任取R1(R2R3)b(bBR1R2 R3)b(bBR1(R2 R3)b(bBR1R2)(bBR1 R3)b(bBR1R2)b(bBR1 R3)R1R2 R1 R3(R1R2)(R1R3)所以 R1(R2 R3)(R1R2)(R1R3)第42页，本讲稿共121页n定理3.22 设R1,R2和R3分别是从A到B,B到C和C到D的关系,那么(R1R2)R3=R1(R2R3)(复合运算满足结合律)证明：R1 (R2 R3)b(bB R1 R2 R3)b(bB R1 c(cC R2 R3)bc(bB R1(cC R2 R3)cb(cC(bB R1 R2 R3)c(cCb(bB R1 R2)R3)c(cC R1 R2)R3)(R1 R2)R3第43页，本讲稿共121页3.2.2 关系R的幂n当R是A上的一个关系时,R可与自身合成任意次而形成A上的一个新关系，即 RR=R2，R2R=RR2=R3，n定义3.22 设R是集合A上的二元关系,nN,那么R的n次幂记为Rn,定义如下:(1)R0=IA(2)Rn+1=RnRn定理3.23设R是A上的二元关系,并设m和n是N的元素,那么(1)RmRn=Rm+n (2)(Rm)n=Rmn第44页，本讲稿共121页n定理3.24设A=n,R是集合A上的一个关系,那么i,jZ，使Ri=Rj而 0ij证明：为方便起见，记因为总共只有m个定义在n元有限集A上的不同的关系，所以以下m+1个R的方幂 R0,R1,R2,Rm之中，必有相同者。所以存在i和j，0ijm 使 Ri=Rj鸽巢原理（抽屉原则）第45页，本讲稿共121页n定理3.25设R是集合A上的一个二元关系.若i,jZ,ij,使Ri=Rj.记d=j-i,那么(a)对所有k Z,k0,Ri+k=Rj+k(b)对所有k,m Z,k,m0,Ri+md+k=Ri+k(c)记S=R0,R1,R2,Rj-1,那么对nN,RnS证明(a)：i.k=0时，Ri=Rjii.设k=t时，Ri+t=Rj+t则k=t+1时，Ri+t+1=Ri+tR=Rj+tR=Rj+t+1得证第46页，本讲稿共121页证明(b)：i.k=0时，证明Ri+md=Ri m=0时，Ri=Ri设m=t时，Ri+td=Ri则m=t+1时，Ri+(t+1)d=Ri+tdRd=RiRd=Ri+d=Ri+j-i=Rj=Riii.设k=n时，Ri+md+n=Ri+n则k=n+1时，Ri+md+n+1=Ri+md+nR=Ri+nR=Ri+n+1得证第47页，本讲稿共121页证明(c)：只需证n j时,RnS由n j i,必存在s,tZ使得n=i+sd+t(0td-1)因为 i.n=j时，j=i+1*d+0=i+j-i ii.设n=k时，存在s,t使得k=i+sd+t(0td-1)则n=k+1时,k+1=i+sd+t+1,分两种情况讨论情况1:td-1,则s和t+1就是要求的两个数情况2:t=d-1,则t+1=d，k+1=i+(s+1)d+0,即s+1和0是要求的两个数总之，存在s,tZ使得n=i+sd+t(0td-1)由(b)知Rn=Ri+sd+t=Ri+t 且td-1，则 i+t i+d-1=i+j-i-1=j-1即 Rn=Ri+t S第48页，本讲稿共121页例n设A=a,b,c,d,R=,求R0,R2,R3,R4R0=,R2=,R3=,R4=,nR4=R2,根据定理3.25(c)对nN,RnR0,R1,R2,R3易证R5=R3,R6=R4=R2用归纳法可得R2n+1=R3和R2n=R2(n1)第49页，本讲稿共121页第50页，本讲稿共121页3.2.3 合成关系的矩阵表达n定理3.26 设X=x1,x2,xm,Y=y1,y2,yn,Z=z1,z2,zp,R是X到Y的关系,MR=aij是mn矩阵,S是Y到Z的关系,MS=bij是np矩阵.则MRS=cij=MRMS,这里是逻辑乘,是逻辑加第51页，本讲稿共121页n例3设 X=1,2,Y=a,b,c,Z=,R是X到Y的关系，S是Y到Z的关系，R=,S=,则第52页，本讲稿共121页第53页，本讲稿共121页n定理3.27 关系矩阵的乘法是可结合的nMRS=MRMS cij=aijbijnMRS=MRMS cij=aijbijnMR cij=aijnMR-S=MR MS cij=aij(bij)n定理：设R是集合A上的一个二元关系，R是传递的 iff R2R证明：必要性 R2t,使得xRt 且 tRy又R是传递的，所以xRy，即R2R 充分性 x,y,z A,若xRy 且 yRz，则 R2 R2R，R，即R是传递的第54页，本讲稿共121页补充定理n定理1：设R1是由A到B的关系，R2和R3是由B到C的关系，R4是由C到D的关系，则如果 R2 R3,则R1R2 R1R3,R2R4 R3R4n定理2：设R1和R2是由A到B的关系，S1和S2是由B到C的关系，若 R1 R2,S1 S2,则 R1S1 R2S2证明：1.R1R2则b，b B使得 aR1b 且 bR2c R2 R3 bR3c即 R1R3 R1R2 R1R3 类似可证R2R4 R3R4第55页，本讲稿共121页3.3.1 逆关系n定义3.31设R是从A到B的二元关系,关系R的逆(或叫R的逆关系)记为R-1(Rc),是一从B到A的二元关系,定义如下:R-1=|Rn例I上的关系“”集合族上的关系的逆是关系 空关系的逆是空关系(AB)-1=BAR=,nR-1=,第56页，本讲稿共121页逆关系的关系图和关系矩阵nR-1的关系图将R关系图的所有边的方向颠倒n R-1的矩阵 R矩阵的转置：M=(MR)T第57页，本讲稿共121页n定理3.32 设R,S,R1和R2都是从A到B的二元关系,那么下列各式成立:(a)(R-1)-1=R(b)(RS)-1=R-1 S-1(c)(RS)-1=R-1 S-1(d)(R)-1=(R-1)(e)(RS)-1=R-1 S-1(f)R1 R2 R1-1 R2-1(g)(R1R2)-1=R2-1 R1-1 第58页，本讲稿共121页n定理：R是A上关系，则 R是对称的，当且仅当 R-1=R R是反对称的，当且仅当 RR-1 IA证明：充分性，已知 R-1=R (证明R对称)任取x,yA 设R,则R-1,而R-1=R 即有R，所以R对称必要性，已知R对称，(证明R-1=R)先证R-1R，任取R-1,则R,又R对称所以有R，所以R-1R。再证R R-1，任取R,因R对称，所以有R，则RC,所以RR-1。综上R-1=R第59页，本讲稿共121页证明 充分性，已知RR-1IA，(证明R反对称)任取x,yA 设R 且R，则R 且 R-1，所以RR-1，因为RR-1IA所以 IA ，即x=y 所以R反对称必要性，已知R反对称，(证明RR-1 IA)任取RR-1 则R 且 R-1 即R 且 R因为R反对称，所以x=y 即IA 所以RR-1 IA第60页，本讲稿共121页思考题n关系的性质对于复合运算和逆是否保持封闭？即自反（反自反、对称、反对称、传递）关系的复合关系和逆关系是否仍是自反（反自反、对称、反对称、传递）的？反对称传递对称反自反自反R1-1R1R2R1,R2反对称不反对称传递不传递对称不对称反自反不反自反自反自反第61页，本讲稿共121页3.3 关系上的闭包运算n例1。2。31。2。31。2。31。2。3第62页，本讲稿共121页n定义3.32 设R是A上的二元关系,若有A上的关系R,满足：(i)RR(ii)R是自反的(对称的、传递的)(iii)对于任何A上自反(对称、传递)的关系R”,如果RR”,就有RR”则称R是R的自反(对称、传递)闭包。记作r(R)、(s(R)、t(R)(reflexive、symmetric、transitive)nR的自反(对称,传递)闭包是包含R并且具有自反(对称,传递)性质的最小关系第63页，本讲稿共121页闭包的性质n定理3.34设R是集合A上的二元关系(a)R是自反的当且仅当r(R)=R(b)R是对称的当且仅当s(R)=R(c)R是传递的当且仅当t(R)=R证明(a)：充分性显然必要性：由闭包的定义Rr(R)又RR，且R是自反的根据闭包的极小性，有r(R)R则r(R)=R第64页，本讲稿共121页闭包的计算n定理3.3-53.3-7 设R是非空集A的关系,则(1)r(R)=RIA(2)s(R)=RR-1(3)证明(1):设R=R IA.显然,R是自反的，且R R.假设R是A上的自反关系且R R.因R是自反的,所以R IA,又R R,所以R R IA=R所以,R=r(R).证毕第65页，本讲稿共121页证明(2):设R=R R-1(i)显然R R(ii)又(R R-1)-1=R-1 R=R R-1 R是对称的(iii)假设R是A上的对称关系且R R 则 R-1 R-1 R=R R-1 R 综上，s(R)=R=RR-1第66页，本讲稿共121页证明(3):令R=RR2R3.,（只需证明t(R)R 且 R t(R)）(i)先证t(R)R(利用闭包的极小性)显然 R R(再证明R是传递的)x,y,zA,设有R,R,由R定义得必存在整数i,j使得Ri,Rj,则Ri+jR,所以R,R传递由闭包的极小性可得t(R)R(ii)再证 Rt(R)Rt(R)R2t2(R)t(R)则R3=R2R t2(R)t(R)t2(R)t(R)这个过程可以一直进行下去，即得Rit(R)Rt(R)综合(i)(ii)R=t(R)第67页，本讲稿共121页例(a)整数集合I上的关系的自反闭包是,对称闭包是关系,传递闭包是关系自身(b)整数集合I上的关系的自反闭包是自身,对称闭包是全域关系,传递闭包是自身(c)的自反闭包是全域关系,对称闭包是,的传递闭包是全域关系(d)空关系的自反闭包是恒等关系,对称闭包和传递闭包是自身(e)设R是I上的关系,xRy当且仅当y=x+1,那么t(R)是关系第68页，本讲稿共121页n定理3.38 设R是n元有限集A上的关系,则存在自然数kn，使得证明：显然只需证a,bA,若t(R),则存在自然数p使得Rp,即存在序列x1,x2,xp-1满足aRx1,x1Rx2,xp-1Rb若满足上述条件的最小p值大于n，则由于A是有限集，必存在s,t使得 xs=xt，其中0s tp，因此可得到 aRx1,x1Rx2,xsRxt+1,xp-1Rb即Rp-(t-s),与p是最小的假设矛盾第69页，本讲稿共121页例nA=1,2,3，A上关系R1,R2,R3,如下：(1)R1=,(2)R2=,(3)R3=,求它们的传递闭包解：(1)R12=R13=t(R)=R1 R12 R13=R1 (2)R22=,R23=,=IA R24=R23 t(R)=R2 R22 R23第70页，本讲稿共121页闭包的性质n定理设R和S都是集合A上的关系且RS，则(a)r(R)r(S)(b)s(R)s(S)(c)t(R)t(S)证明(a)：显然r(S)是自反的，且RS r(S)，由闭包的极小性可知r(R)r(S)第71页，本讲稿共121页闭包的应用n例：传递闭包在语法分析中的应用设有一字母表V=A,B,C,D,e,d,f.假设文法G 为(1)A A f;(2)B D d e;(3)C e;(4)A B;(5)B D e;(6)D B fR 为定义在V 上的二元关系,(x i,x j)R 表示从x i 出发用一条规则推出一串字符,使其第一个字母恰好为x jt(R):每个字母连续使用文法可能推出的头字符.第72页，本讲稿共121页n定理3.39(a)如果R是自反的,那么s(R)和t(R)都是自反的(b)如果R是对称的,那么r(R)和t(R)都是对称的(c)如果R是传递的,那么r(R)是传递的证明(c)：证明R是传递的,那么r(R)是传递的 r2(R)=(RIA)2=(RIA)(RIA)=R2R R IA =R IA(R是传递的，R2 R)=r(R)r(R)是传递的第73页，本讲稿共121页n定理3.310 设R是集合A上的二元关系,那么(a)rs(R)=sr(R)(b)rt(R)=tr(R)(c)st(R)ts(R)证明(a)：Rs(R)r(R)rs(R)，sr(R)srs(R)rs(R)是对称的（定理3.39）srs(R)=rs(R)即得sr(R)rs(R)同理可证rs(R)sr(R)sr(R)=rs(R)n通常将t(R)记成R+，tr(R)记成R*，即t(R)=R+=RR2.Rn=tr(R)=rt(R)=R*=R0RR2.Rn=Rii=1Rii=0第74页，本讲稿共121页3.4 次序关系n常遇到的重要关系n例数值的、关系集合的、关系图书馆的图书按书名的字母次序排序词典中的字(词)的排序计算机中文件按文件名排序程序按语句次序执行.第75页，本讲稿共121页3.4.1 偏序关系n定义3.41 如果集合A上的二元关系R是自反的,反对称的和传递的,那么称R为A上的偏偏序关系序关系,或称半序关系称序偶为偏序偏序集集n通常，把偏序关系R记作,如果,则记作ab,读作“a小于等于b”n注意注意：定义中的“”不是指普通中的实数中的大小关系的,而是一般的偏序关系第76页，本讲稿共121页例n设集合Aa,b,c,A上的关系R,判断R是否是偏序关系。n设A是非零自然数集,DA是A上的整除关系,判断DA是否是偏序关系n设A是一个集合，则集合的“包含”关系是否是其幂集上的偏序关系（是）（是）（是）第77页，本讲稿共121页例nA=1,2,4,62。1。64第78页，本讲稿共121页哈斯图(Hasse)n描述偏序集的关系图,可以简化简化为哈斯图哈斯图n简化规则用小圆圈代表元素如果xy,并且xy,则将代表y的小圆圈画在代表x的小圆圈的上方若xy，且在A中不存在任何其它元素z，使得xz,zy(x是y的直接前辈，或y是x的直接后裔)，则有一条由x到y的连线第79页，本讲稿共121页例2。1。642。1。84。6。4。第80页，本讲稿共121页练习1.设A=a,b,c，则“”关系是(A)上的偏序关系，则(A),R)是偏序集,画出其哈斯图2.设A=2,3,6,12,24,36,画出的哈斯图第81页，本讲稿共121页nA=1,2,12,的哈斯图第82页，本讲稿共121页偏序集中的重要元素n极小元与极大元，最小元与最大元设是一偏序集合,B是A的子集若存在元素bB,使得B中没有没有元素x满足xb且xb,则称b为B的一个极小元极小元若存在元素bB,使得B中没有没有元素x满足xb且bx,则称b为B的一个极大元极大元如存在元素bB,使得xB,均有bx,则称b为B的最小元最小元如存在元素bB,使得xB,均有xb,则称b为B的最大元最大元第83页，本讲稿共121页例n设的哈斯图如下所示：讨论当B取相应集合时，其最大元,最小元,极大元,极小元abcdefghia,ba,b无无无无a,bc无无cB极小元极小元极大元极大元最小元最小元最大元最大元a,ba,b,c第84页，本讲稿共121页abcdefghiB极小元极小元极大元极大元最小元最小元最大元最大元a,b,c,db,c,d,fa,c,f,ia,bc,d无无无无bfbfaiai第85页，本讲稿共121页几点说明n极大(小)元总是存在的n最大(小)元可能不存在n极大(小)元未必是最大(小)元n极大(小)元未必是唯一的n如果B存在最大(小)元x,则x就是B的极大(小)元n孤立点则又是极大元,也是极小元第86页，本讲稿共121页n定理3.41 设是一偏序集，且BA,如果B有最大(最小)元，那么它是唯一的证明：假设a和b都是B的最大元,那么ab和ba.则a=b(是反对称性的)类似可证最小元的唯一性第87页，本讲稿共121页n上界与下界，上确界与下确界设是一偏序集合,B是A的子集如存在aA,使得xB,均有xa,则称B有上界，并称a为B的一个上界上界(Upper Bound)如存在aA,使得xB,均有ax,则称B有下界，并称a为B的一个下界下界(Lower Bound)若a是B的上界，并且对B的每一个上界a皆有a a，则称 a是B的最小上界最小上界(上确界，Least Upper Bound)，记作lub若a是B的下界，并且对B的每一个下界a皆有 a a，则称 a是B的最大下界最大下界(下确界，Greatest Lower Bound)，记作glb第88页，本讲稿共121页abcdefghiB上界上界下界下界上确界上确界下确界下确界a,ba,b,cc,d,e,f,g,h,i无无无无无无c,e,f,h,i无无c无无第89页，本讲稿共121页abcdefghiB上界上界下界下界上确界上确界下确界下确界a,b,c,db,c,d,fa,c,f,if,h,i无无f无无f,h,ibfbiaia第90页，本讲稿共121页n定理3.42 如果是非空有限偏序集,则A的极小(大)元素常存在,最大下界和最小上界也可能存在或不存在,但如果它们存在,则是唯一的.n定理3.43设是偏序集合且BA,如果B的最小上界(最大下界)存在,那么是唯一的n定理3.44设是偏序集合,B是A的子集(a)如果b是B的最大(小)元,那么b是B的极大(小)元(b)如果b是B的最大(小)元,那么b是B的lub(glb)(c)如果b是B的一个上(下)界且bB,那么b是B的最大(小)元第91页，本讲稿共121页练习n给定一偏序关系的Hasse图。12。24。36。最大元上界上确界下界A6,12,241,2,32,3下确界最小元极大元极小元B无24无无无246,12,24,366,12,24,36无246611,2,3,6111124,36166246112,311无2,32,3第92页，本讲稿共121页3.4.2 拟序关系n如果集合A上的二元关系R是反自反的和传递的,那么称R为A上的拟序关系拟序关系,称序偶为拟序集拟序集n通常，把拟序关系R记作,如果,则记作ab,读作“a小于b”n例实数集合中的是拟序关系集合的是拟序关系第93页，本讲稿共121页n定理定理 拟序关系是反对称的证明：设R是A上的拟序关系假设R不是反对称的，则x,yA,xy,xRy且yRx，由R的传递性得xRx，与R反自反矛盾 R反对称n定理定理3.45 在集合A上,(a)如果R是一拟序关系,那么r(R)=RIA是偏序关系(b)如果R是一偏序关系,那么R-IA是拟序关系第94页，本讲稿共121页n可比较如果是一偏序,或ab或ba,我们说a和b是可比较的n线序集全序集定义3.46 在偏序集中.如果a,bA,a，b均可比较.那么叫做A上的线序关系(或全序关系),这时的序偶叫做线序集或全序集、链.3.4.3 线序集和良序集2。1。84。第95页，本讲稿共121页n良序集定义3.47如果A上的二元关系R是一偏序偏序关系,且A的每一非空子集都有最小元,那么R叫做A上的良序关系,序偶叫做良序集良序集必是线序集定理3.46是良序集n*3.4.4 词典序和标准序n*3.4.5 数学归纳法的推广第96页，本讲稿共121页思考题n证明或用反例否定下列命题(1)每一个偏序关系的逆都是偏序关系(2)每一个拟序关系的逆都是拟序关系(3)每一个全序关系的逆都是全序关系(4)每一个良序关系的逆都是良序关系第97页，本讲稿共121页3.5 等价关系和划分n3.5.1 等价关系定义3.51如果集合A上的二元关系R是自反的,对称的和传递的,那么称R是等价关系设R是A上的等价关系,a,bA.若aRb,记作ab,读做“a等价于b”.例n空关系n全关系n恒等关系n同学集合A=a,b,c,d,e,f,g,A中的关系R是“住在同一房间”第98页，本讲稿共121页n例集合A=1,2,3,4,5,6,7,R=|x-y可被3整除(或x/3与y/3的余数相同)n定义3.52设k是一正整数而a,bI.如果对某整数m,a-b=mk,那么a和b是模k等价,写成ab(mod k)n定理3.51模k等价是任何集合A上的等价关系第99页，本讲稿共121页等价关系的关系矩阵与关系图n关系矩阵可简化为三角矩阵n关系图每一结点都有一自环线（可省略）如果有从a到b的弧,那么也有从b到a的弧（可画成无向图）如果从a到c有一条路径,则从a到c有一条弧第100页，本讲稿共121页nA=1,2,3,4,5,6,7,R是模3等价关系，画出其简化关系图2。5。1。4。7。3。6。等价关系等价关系R R的有向图可能由若干个独立子图构成的有向图可能由若干个独立子图构成的，每个独立子图都是完全关系图的，每个独立子图都是完全关系图(团团)第101页，本讲稿共121页判断下图中哪些是等价关系A=1,2,31。2。1。2。331。2。1。2。1。2。1。2。3333R2R1R5R61。2。1。2。33R3R4R7R8第102页，本讲稿共121页等价类n定义3.53 R是A上的等价关系，aA,由a确定的集合aR:aR=x|xAR称集合aR为a关于R的等价类,简记为an称a为等价类a的表示元素.n如果等价类个数有限,则R的不同等价类的个数叫做R的秩;n等价类aR,aaR第103页，本讲稿共121页例nR是I上模4等价关系04=-8,-4,0,4,8,14=-7,-3,1,5,9,24=-6,-2,2,6,10,34=-5,-1,3,7,11,nA=a,b,c,d,e,f,R=,a=b=c=a,b,cd=e=d,ef=f秩是3第104页，本讲稿共121页等价关系图求等价类R图中每个独立子图上的结点，构成一个等价类图中每个独立子图上的结点，构成一个等价类第105页，本讲稿共121页n下述三个等价关系各有几个等价类？说出对应的各个等价类。练习1。2。3R21。2。3R1。R3。123第106页，本讲稿共121页等价类的性质n定理3.52 设R是非空集合A上的等价关系,aRb iffa=b证明：充分性 aa=b,即ab,aRb必要性x a,则aRx,R对称,xRa又 aRb，且R传递，xRb，即x b ab，类似可证ba a=b第107页，本讲稿共121页n定理3.53 设R是集合A上的等价关系,则对所有a,bA,或者a=b,或者ab=证明：如果A=,断言无义地真设A.若aRb，根据定理3.52得a=b若R,假设ab,则存在cab，cacb,R,R,由R对称得 R又由R传递得R,矛盾定理得证第108页，本讲稿共121页思考n设R是集合A上的等价关系，a,bA,若ab=,则R证明：假设R,由等价类定义得ba,又bb，所以bab，矛盾第109页，本讲稿共121页n定 理 3.56 设 R是 A上 的 二 元 关 系,设R=tsr(R)是R的自反对称传递闭包,那么(a)R是A上的等价关系,叫做R诱导的等价关系(b)若R是等价关系且RR,那么RR.R是包含R的最小等价关系.n例A=a,b,cRtsr(R)第110页，本讲稿共121页等价类与划分n3.5.2 划分定义3.55给定非空集合A和非空集合族=A1,A2,Am,如果(i)A=A1A2Am(ii)AiAj=或Ai=Aj(i,j=1,2,m)称集合族为集合A的一个划分划分划分的元素Ai称为划分的块块如果划分是有限集合,则不同块的个数叫划分的秩秩第111页，本讲稿共121页关于集合的划分的理解n划分中的每一块是非空的n划分中的任意两块没有公共元素nA的一个划分耗尽了A中的所有元素n例n设S=1,2,3A=1,2,2,3B=1,1,2,1,3C=1,2,3D=1,2,3E=1,2,3F=1,1,2最小（粗）划分最大（细）划分第112页，本讲稿共121页n覆盖定义3.54给定非空集合A和非空集合族=A1,A2,Am,如果A=A1A2Am称集合族为集合A的一个覆盖覆盖n定理3.57 设A是非空集合,R是A上的等价关系.R的等价类集合 aRaA是A的划分证明：令=aRaA，则对a,b 有a=b(aRb)或ab=(R)a A 中所有块的并集也包含于A又xA，x x，A也包含于中所有块的并集第113页，本