离散数学屈婉玲第七章ppt课件

.,1,主要内容有序对与笛卡儿积二元关系的定义与表示法关系的运算关系的性质关系的闭包等价关系与划分偏序关系,第七章二元关系,.,2,7.1有序对与笛卡儿积,定义7.1由两个元素x和y，按照一定的顺序组成的二元组称为有序对，记作.有序对性质:(1)有序性（当xy时）(2)与相等的充分必要条件是=x=uy=v.,.,3,笛卡儿积,定义7.2设A,B为集合，A与B的笛卡儿积记作AB，且AB=|xAyB.,例1A=1,2,3,B=a,b,cAB=,BA=,A=,B=P(A)A=,P(A)B=,.,4,笛卡儿积的性质,(1)不适合交换律ABBA(AB,A,B)(2)不适合结合律(AB)CA(BC)(A,B,C)(3)对于并或交运算满足分配律A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB)(AC)(BC)A=(BA)(CA)(4)若A或B中有一个为空集，则AB就是空集.A=B=(5)ACBDABCD.(6)若|A|=m,|B|=n,则|AB|=mn,.,5,性质证明,证明A(BC)=(AB)(AC),证任取A(BC)xAyBCxA(yByC)(xAyB)(xAyC)ABAC(AB)(AC)所以有A(BC)=(AB)(AC).,.,6,实例,例2(1)证明A=B,C=DAC=BD(2)AC=BD是否推出A=B,C=D?为什么？,解(1)任取ACxAyCxByDBD(2)不一定.反例如下：A=1，B=2,C=D=,则AC=BD但是AB.,.,7,7.2二元关系,定义7.3如果一个集合满足以下条件之一：(1)集合非空,且它的元素都是有序对(2)集合是空集则称该集合为一个二元关系,简称为关系，记作R.如果R,可记作xRy；如果R,则记作xy实例：R=,S=,a,b.R是二元关系,当a,b不是有序对时，S不是二元关系根据上面的记法，可以写1R2,aRb,ac等.,.,8,A到B的关系与A上的关系,定义7.4设A,B为集合,AB的任何子集所定义的二元关系叫做从A到B的二元关系,当A=B时则叫做A上的二元关系.,例3A=0,1,B=1,2,3,那么R1=,R2=AB,R3=,R4=R1,R2,R3,R4是从A到B的二元关系,R3和R4也是A上的二元关系.计数:|A|=n,|AA|=n2,AA的子集有个.所以A上有个不同的二元关系.例如|A|=3,则A上有=512个不同的二元关系.,.,9,A上重要关系的实例,定义7.5设A为集合,(1)是A上的关系，称为空关系(2)全域关系EA=|xAyA=AA恒等关系IA=|xA小于等于关系LA=|x,yAxy,A为实数子集整除关系DB=|x,yBx整除y,A为非0整数子集包含关系R=|x,yAxy,A是集合族.,.,10,实例,例如,A=1,2,则EA=,IA=,例如A=1,2,3,B=a,b,则LA=,DA=,例如A=P(B)=,a,b,a,b,则A上的包含关系是R=,类似的还可以定义：大于等于关系,小于关系,大于关系,真包含关系等.,.,11,关系的表示,1.关系矩阵若A=x1,x2,xn，R是A上的关系，R的关系矩阵是布尔矩阵MR=(rij)nn,其中rij=1R2.关系图若A=x1,x2,xm，R是从A上的关系，R的关系图是GR=,其中A为结点集，R为边集.如果属于关系R，在图中就有一条从xi到xj的有向边.注意：关系矩阵适合表示有穷集A上的关系（可推广为从A到B的关系）关系图适合表示有穷集A上的关系,.,12,实例,例4A=1,2,3,4,R=,R的关系矩阵MR和关系图GR如下：,.,13,7.3关系的运算,关系的基本运算定义7.6关系的定义域、值域与域分别定义为domR=x|y(R)ranR=y|x(R)fldR=domRranR,例5R=,则domR=1,2,4ranR=2,3,4fldR=1,2,3,4,.,14,关系运算(逆与合成),定义7.7关系的逆运算R1=|R定义7.8关系的合成运算FG=|t(FG),例6R=,S=,R1=,RS=,SR=,.,15,合成的图示法,利用图示（不是关系图）方法求合成RS=,SR=,.,16,关系运算(限制与像),定义7.9设R为二元关系,A是集合(1)R在A上的限制记作RA,其中RA=|xRyxA(2)A在R下的像记作RA,其中RA=ran(RA)说明：R在A上的限制RA是R的子关系，即RARA在R下的像RA是ranR的子集，即RAranR,.,17,实例,例7设R=,则R1=,R=R2,3=,R1=2,3R=R3=2,.,18,关系运算的性质,定理7.1设F是任意的关系,则(1)(F1)1=F(2)domF1=ranF,ranF1=domF,证(1)任取,由逆的定义有(F1)1F1F.所以有(F1)1=F.,(2)任取x,xdomF1y(F1)y(F)xranF所以有domF1=ranF.同理可证ranF1=domF.,.,19,定理7.2设F,G,H是任意的关系,则(1)(FG)H=F(GH)(2)(FG)1=G1F1,关系运算的性质,证(1)任取,(FG)Ht(FGH)t(s(FG)H)ts(FGH)s(Ft(GH)s(FGH)F(GH)所以(FG)H=F(GH),.,20,证明,(2)任取,(FG)1FGt(FG)t(G1F1)G1F1所以(FG)1=G1F1,.,21,关系运算的性质,定理7.3设R为A上的关系,则RIA=IAR=R,证任取RIAt(RIA)t(Rt=yyA)R,.,22,关系运算的性质,定理7.4(1)F(GH)=FGFH(2)(GH)F=GFHF(3)F(GH)FGFH(4)(GH)FGFHF,只证(3)任取,F(GH)t(FGH)t(FGH)t(FG)(FH)t(FG)t(FH)FGFHFGFH所以有F(GH)=FGFH,.,23,推广,定理7.4的结论可以推广到有限多个关系R(R1R2Rn)=RR1RR2RRn(R1R2Rn)R=R1RR2RRnRR(R1R2Rn)RR1RR2RRn(R1R2Rn)RR1RR2RRnR,.,24,关系运算的性质,定理7.5设F为关系,A,B为集合,则(1)F(AB)=FAFB(2)FAB=FAFB(3)F(AB)=FAFB(4)FABFAFB,.,25,证明,证只证(1)和(4).(1)任取F(AB)FxABF(xAxB)(FxA)(FxB)FAFBFAFB所以有F(AB)=FAFB.,.,26,证明,(4)任取y,yFABx(FxAB)x(FxAxB)x(FxA)(FxB)x(FxA)x(FxB)yFAyFByFAFB所以有FAB=FAFB.,.,27,关系的幂运算,定义7.10设R为A上的关系,n为自然数,则R的n次幂定义为：(1)R0=|xA=IA(2)Rn+1=RnR注意：对于A上的任何关系R1和R2都有R10=R20=IA对于A上的任何关系R都有R1=R,.,28,例8设A=a,b,c,d,R=,求R的各次幂,分别用矩阵和关系图表示.,解R与R2的关系矩阵分别是：,幂的求法,.,29,R3和R4的矩阵是：因此M4=M2,即R4=R2.因此可以得到R2=R4=R6=，R3=R5=R7=R0的关系矩阵是,幂的求法,.,30,关系图,R0,R1,R2,R3,的关系图如下图所示.,R0,R1,R2=R4=,R3=R5=,.,31,幂运算的性质,定理7.6设A为n元集,R是A上的关系,则存在自然数s和t,使得Rs=Rt.,证R为A上的关系,由于|A|=n,A上的不同关系只有个.列出R的各次幂R0,R1,R2,必存在自然数s和t使得Rs=Rt,.,32,定理7.7设R是A上的关系,m,nN,则(1)RmRn=Rm+n(2)(Rm)n=Rmn,幂运算的性质,证用归纳法(1)对于任意给定的mN,施归纳于n.若n=0,则有RmR0=RmIA=Rm=Rm+0假设RmRn=Rm+n,则有RmRn+1=Rm(RnR)=(RmRn)R=Rm+n+1,所以对一切m,nN有RmRn=Rm+n.,.,33,证明,(2)对于任意给定的mN,施归纳于n.若n=0,则有(Rm)0=IA=R0=Rm0假设(Rm)n=Rmn,则有(Rm)n+1=(Rm)nRm=(Rmn)Rn=Rmn+m=Rm(n+1)所以对一切m,nN有(Rm)n=Rmn.,.,34,定理7.8设R是A上的关系,若存在自然数s,t(st)使得Rs=Rt,则(1)对任何kN有Rs+k=Rt+k(2)对任何k,iN有Rs+kp+i=Rs+i,其中p=ts(3)令S=R0,R1,Rt1,则对于任意的qN有RqS,幂运算的性质,证(1)Rs+k=RsRk=RtRk=Rt+k(2)对k归纳.若k=0,则有Rs+0p+i=Rs+i假设Rs+kp+i=Rs+i,其中p=ts,则Rs+(k+1)p+i=Rs+kp+i+p=Rs+kp+iRp=Rs+iRp=Rs+p+i=Rs+ts+i=Rt+i=Rs+i由归纳法命题得证.,.,35,证明,(3)任取qN,若qt,显然有RqS,若qt,则存在自然数k和i使得q=s+kp+i,其中0ip1.于是Rq=Rs+kp+i=Rs+i而s+is+p1=s+ts1=t1从而证明了RqS.,.,36,7.4关系的性质,定义7.11设R为A上的关系,(1)若x(xAR),则称R在A上是自反的.(2)若x(xAR),则称R在A上是反自反的.,实例：自反：全域关系EA,恒等关系IA,小于等于关系LA,整除关系DA反自反：实数集上的小于关系、幂集上的真包含关系.A=1,2,3,R1,R2,R3是A上的关系,其中R1,R2,R3R2自反，R3反自反，R1既不是自反的也不是反自反的.,.,37,对称性与反对称性,定义7.12设R为A上的关系,(1)若xy(x,yARR),则称R为A上对称的关系.(2)若xy(x,yARRx=y),则称R为A上的反对称关系.,实例：对称关系：A上的全域关系EA,恒等关系IA和空关系反对称关系：恒等关系IA和空关系也是A上的反对称关系.设A1,2,3,R1,R2,R3和R4都是A上的关系,其中R1,，R2,R3,，R4,R1：对称和反对称；R2：只有对称；R3：只有反对称；R4：不对称、不反对称,.,38,传递性,定义7.13设R为A上的关系,若xyz(x,y,zARRR),则称R是A上的传递关系.,实例：A上的全域关系EA,恒等关系IA和空关系，小于等于和小于关系，整除关系，包含与真包含关系设A1,2,3,R1,R2,R3是A上的关系,其中R1,R2,R3R1和R3是A上的传递关系,R2不是A上的传递关系.,.,39,关系性质成立的充要条件,定理7.9设R为A上的关系,则(1)R在A上自反当且仅当IAR(2)R在A上反自反当且仅当RIA=(3)R在A上对称当且仅当R=R1(4)R在A上反对称当且仅当RR1IA(5)R在A上传递当且仅当RRR,.,40,证明,证明只证(1)、(3)、(4)、(5)(1)必要性任取,由于R在A上自反必有IAx,yAx=yR从而证明了IAR充分性.任取x,有xAIAR因此R在A上是自反的.,.,41,证明,(3)必要性.任取,RRR1所以R=R1充分性.任取,由R=R1得RR1R所以R在A上是对称的,.,42,证明,(4)必要性.任取,有RR1RR1RRx=yx,yAIA这就证明了RR1IA充分性.任取,RRRR1RR1IAx=y从而证明了R在A上是反对称的.,.,43,证明,(5)必要性.任取有RRt(RR)R所以RRR充分性.任取,R,则RRRRR所以R在A上是传递的,.,44,关系性质的三种等价条件,.,45,关系性质的判别,例9判断下列各图的性质(a)(b)(c),解：(a)对称(b)反自反、反对称、传递(c)自反、反对称,.,46,关系的性质和运算之间的联系,.,47,7.5关系的闭包,主要内容闭包定义闭包的构造方法集合表示矩阵表示图表示闭包的性质,.,48,闭包定义,定义7.14设R是非空集合A上的关系,R的自反(对称或传递)闭包是A上的关系R,使得R满足以下条件：(1)R是自反的(对称的或传递的)(2)RR(3)对A上任何包含R的自反(对称或传递)关系R有RRR的自反闭包记作r(R),对称闭包记作s(R),传递闭包记作t(R).,定理7.10设R为A上的关系,则有(1)r(R)=RR0(2)s(R)=RR1(3)t(R)=RR2R3说明：对有穷集A(|A|=n)上的关系,(3)中的并最多不超过Rn,.,49,证明,证只证(1)和(3).(1)由IA=R0RR0知RR0是自反的,且满足RRR0设R是A上包含R的自反关系,则有RR和IAR.从而有RR0R.RR0满足闭包定义,所以r(R)=RR0.,(1)先证RR2t(R)成立.用归纳法证明对任意正整数n有Rnt(R).n=1时有R1=Rt(R).假设Rnt(R)成立,那么对任意的Rn+1=RnRt(RnR)t(t(R)t(R)t(R)这就证明了Rn+1t(R).由归纳法命题得证.,.,50,证明,再证t(R)RR2成立,为此只须证明RR2传递.任取,则RR2RR2t(Rt)s(Rs)ts(RtRs)ts(Rt+s)RR2从而证明了RR2是传递的.,.,51,闭包的矩阵表示和图表示,设关系R,r(R),s(R),t(R)的关系矩阵分别为M,Mr,Ms和Mt则Mr=M+EMs=M+MMt=M+M2+M3+E是单位矩阵,M是转置矩阵，相加时使用逻辑加.,设关系R,r(R),s(R),t(R)的关系图分别记为G,Gr,Gs,Gt,则Gr,Gs,Gt的顶点集与G的顶点集相等.除了G的边以外,以下述方法添加新的边：(1)考察G的每个顶点,若没环就加一个环，得到Gr(2)考察G的每条边,若有一条xi到xj的单向边,ij,则在G中加一条xj到xi的反向边,得到Gs(3)考察G的每个顶点xi,找xi可达的所有顶点xj(允许i=j)，如果没有从xi到xj的边,就加上这条边,得到图Gt,.,52,实例,例9设A=a,b,c,d,R=,R和r(R),s(R),t(R)的关系图如下图所示.,.,53,求传递闭包的算法,算法Warshall输人：M（R的关系矩阵）输出：MT（t(R)的关系矩阵）1MTM2fork1tondo3fori1tondo4forj1tondo5MTi,jMTi,j+MTi,kMTk,j,.,54,实例,设A=a,b,c,d,R=,R的传递闭包的矩阵如下：,.,55,闭包的性质,定理7.11设R是非空集合A上的关系,则(1)R是自反的当且仅当r(R)=R.(2)R是对称的当且仅当s(R)=R.(3)R是传递的当且仅当t(R)=R.,定理7.12设R1和R2是非空集合A上的关系,且R1R2,则(1)r(R1)r(R2)(2)s(R1)s(R2)(3)t(R1)t(R2),证明略,.,56,定理7.13设R是非空集合A上的关系,(1)若R是自反的,则s(R)与t(R)也是自反的(2)若R是对称的,则r(R)与t(R)也是对称的(3)若R是传递的,则r(R)是传递的.说明：如果需要进行多个闭包运算，比如求R的自反、对称、传递的闭包tsr(R)，运算顺序如下：tsr(R)=rts(R)=trs(R),闭包的性质,证明略,.,57,7.6等价关系与划分,主要内容等价关系的定义与实例等价类及其性质商集与集合的划分等价关系与划分的一一对应,.,58,7.6等价关系与划分,定义7.15设R为非空集合上的关系.如果R是自反的、对称的和传递的,则称R为A上的等价关系.设R是一个等价关系,若R,称x等价于y,记做xy.,实例设A=1,2,8,如下定义A上的关系R：R=|x,yAxy(mod3)其中xy(mod3)叫做x与y模3相等,即x除以3的余数与y除以3的余数相等.不难验证R为A上的等价关系,因为(1)xA,有xx(mod3)(2)x,yA,若xy(mod3),则有yx(mod3)(3)x,y,zA,若xy(mod3),yz(mod3),则有xz(mod3),.,59,模3等价关系的关系图,等价关系的实例,.,60,等价类定义,定义7.16设R为非空集合A上的等价关系,xA，令xR=y|yAxRy称xR为x关于R的等价类,简称为x的等价类,简记为x或实例A=1,2,8上模3等价关系的等价类：1=4=7=1,4,72=5=8=2,5,83=6=3,6,.,61,等价类的性质,定理7.14设R是非空集合A上的等价关系,则(1)xA,x是A的非空子集(2)x,yA,如果xRy,则x=y(3)x,yA,如果xy,则x与y不交(4)x|xA=A,证(1)由定义,xA有xA.又xx,即x非空.(2)任取z,则有zxRRRRRR从而证明了zy.综上所述必有xy.同理可证yx.这就得到了x=y.,.,62,证明,(3)假设xy,则存在zxy,从而有zxzy,即RR成立.根据R的对称性和传递性必有R,与xy矛盾,(4)先证x|xAA.任取y,yx|xAx(xAyx)yxxAyA从而有x|xAA再证Ax|xA.任取y,yAyyyAyx|xA从而有x|xAA成立.综上所述得x|xA=A.,.,63,商集与划分,定义7.17设R为非空集合A上的等价关系,以R的所有等价类作为元素的集合称为A关于R的商集,记做A/R,A/R=xR|xA实例设A=1,2,8，A关于模3等价关系R的商集为A/R=1,4,7,2,5,8,3,6A关于恒等关系和全域关系的商集为：A/IA=1,2,8，A/EA=1,2,8,定义7.18设A为非空集合,若A的子集族(P(A)满足:(1)(2)xy(x,yxyxy=)(3)=A则称是A的一个划分,称中的元素为A的划分块.,.,64,划分实例,例10设Aa,b,c,d,给定1,2,3,4,5,6如下：1=a,b,c,d2=a,b,c,d3=a,a,b,c,d4=a,b,c5=,a,b,c,d6=a,a,b,c,d则1和2是A的划分,其他都不是A的划分.,.,65,例11给出A1,2,3上所有的等价关系,实例,1对应EA,5对应IA,2,3和4分别对应R2,R3和R4.R2=,IAR3=,IAR4=,IA,解先做出A的划分,从左到右分别记作1,2,3,4,5.,.,66,7.7偏序关系,主要内容偏序关系偏序关系的定义偏序关系的实例偏序集与哈斯图偏序集中的特殊元素及其性质极大元、极小元、最大元、最小元上界、下界、最小上界、最大下界,.,67,定义与实例,定义7.19偏序关系：非空集合A上的自反、反对称和传递的关系，记作.设为偏序关系,如果,则记作xy,读作x“小于或等于”y.实例集合A上的恒等关系IA是A上的偏序关系.小于或等于关系,整除关系和包含关系也是相应集合上的偏序关系.,.,68,相关概念,定义7.20设R为非空集合A上的偏序关系,(1)x,yA,x与y可比xyyx(2)任取元素x和y,可能有下述几种情况发生：xy(或yx),xy,x与y不是可比的,定义7.21R为非空集合A上的偏序关系,(1)x,yA,x与y都是可比的，则称R为全序（或线序）实例：数集上的小于或等于关系是全序关系,整除关系不是正整数集合上的全序关系,定义7.22x,yA,如果xy且不存在zA使得xzy,则称y覆盖x.例如1,2,4,6集合上整除关系,2覆盖1,4和6覆盖2,4不覆盖1.,.,69,偏序集与哈斯图,定义7.23集合A和A上的偏序关系一起叫做偏序集,记作.实例:,哈斯图:利用偏序关系的自反、反对称、传递性进行简化的关系图特点：(1)每个结点没有环(2)两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前(3)具有覆盖关系的两个结点之间连边,.,70,实例,例12偏序集和的哈斯图.,.,71,例13已知偏序集的哈斯图如下图所示,试求出集合A和关系R的表达式.,解A=a,b,c,d,e,f,g,hR=,IA,实例,.,72,偏序集中的特殊元素,定义7.24设为偏序集,BA,yB(1)若x(xByx)成立,则称y为B的最小元(2)若x(xBxy)成立,则称y为B的最大元(3)若x(xBxyx=y)成立,则称y为B的极小元(4)若x(xByxx=y)成立,则称y为B的极大元,性质：(1)对于有穷集，极小元和极大元一定存在，可能存在多个.(2)最小元和最大元不一定存在，如果存在一定惟一.(3)最小元一定是极小元；最大元一定是极大元.(4)孤立结点既是极小元，也是极大元.,.,73,定义7.25设为偏序集,BA,yA(1)若x(xBxy)成立,则称y为B的上界(2)若x(xByx)成立,则称y为B的下界(3)令Cy|y为B的上界,C的最小元为B的最小上界或上确界(4)令Dy|y为B的下界,D的最大元为B的最大下界或下确界,偏序集中的特殊元素,性质：(1)下界、上界、下确界、上确界不一定存在(2)下界、上界存在不一定惟一(3)下确界、上确界如果存在，则惟一(4)集合的最小元是其下确界，最大元是其上确界；反之不对.,.,74,实例,例14设偏序集，求A的极小元、最小元、极大元、最大元，设Bb,c,d,求B的下界、上界、下确界、上确界.,解极小元：a,b,c,g；极大元：a,f,h；没有最小元与最大元.B的下界和最大下界都不存在；上界有d和f,最小上界为d.,.,75,实例,例15设X为集合,AP(X)X,且A.若|X|=n,n2.问：(1)偏序集是否存在最大元？(2)偏序集是否存在最小元？(3)偏序集中极大元和极小元的一般形式是什么？并说明理由.,解(1)不存在最小元和最大元,因为n2.(2)的极小元就是X的所有单元集,即x,xX.(3)的极大元恰好比X少一个元素,即Xx,xX.,.,76,调度问题,有穷任务集T，m台相同的机器，T上存在偏序，若t1t2,任务t1完成后t2才能开始tT,l(t)是t需要的时间，d(t)是t的截止时间，l(t),d(t)Z+开始时间为0，:T0,1,表示对