离散数学二元关系

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=,jump,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)若|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,则记作xRy实例：R=,S=,a,b.R是二元关系,当a,b不是有序对时，S不是二元关系根据上面的记法，可以写1R2,aRb,aSb等.,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个不同的二元关系.,jump,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,xm，B=y1,y2,yn，R是从A到B的关系，R的关系矩阵是布尔矩阵MR=rijmn,其中rij=1R.2.关系图若A=x1,x2,xm，R是从A上的关系，R的关系图是GR=,其中A为结点集，R为边集.如果属于关系R，在图中就有一条从xi到xj的有向边.注意：关系矩阵适合表示从A到B的关系或A上的关系（A,B为有穷集）关系图适合表示有穷集A上的关系,12,实例,例4A=1,2,3,4,R=,R的关系矩阵MR和关系图GR如下：,jump,jump1,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关系的合成运算RS=|y(RS),例6R=,S=,R1=,RS=,SR=,jump,15,合成的图示法,利用图示（不是关系图）方法求合成:R=,S=,则：RS=,SR=,16,关系运算(限制与像),定义7.9设R为二元关系,A是集合(1)R在A上的限制记作RA,其中RA=|xRyxA(2)A在R下的像记作RA,其中RA=ran(RA)例7设R=,则R1=,R=R2,3=,R1=2,3R=R3=2,说明：R在A上的限制RA是R的子关系，即RARA在R下的像RA是ranR的子集，即RAranR,17,关系运算的性质,定理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.,18,定理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),19,证明,(2)任取,(FG)1FGt(FG)t(G1F1)G1F1所以(FG)1=G1F1,20,关系运算的性质,定理7.3设R为A上的关系,则RIA=IAR=R,证:任取RIAt(RIA)t(Rt=yyA)R,21,关系运算的性质,定理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,22,推广,定理7.4的结论可以推广到有限多个关系R(R1R2Rn)=RR1RR2RRn(R1R2Rn)R=R1RR2RRnRR(R1R2Rn)RR1RR2RRn(R1R2Rn)RR1RR2RRnR,23,关系运算的性质,定理7.5设F为关系,A,B为集合,则(1)F(AB)=FAFB(2)FAB=FAFB(3)F(AB)=FAFB(4)FABFAFB请将教材P109定理7.5(2)的RAB改为FAB！,24,证明,(1)F(AB)=FAFB证(1)任取F(AB)FxABF(xAxB)(FxA)(FxB)FAFBFAFB所以有F(AB)=FAFB.,25,证明,(4)FABFAFB证：任取yFABx(FxAB)x(FxAxB)x(FxA)(FxB)x(FxA)x(FxB)yFAyFByFAFB所以有FABFAFB.,26,关系的幂运算,定义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,27,例8设A=a,b,c,d,R=,求R的各次幂,分别用矩阵和关系图表示.,解R与R2的关系矩阵分别是：,幂的求法,28,R3和R4的矩阵是：因此M4=M2,即R4=R2.因此可以得到R2=R4=R6=，R3=R5=R7=R0的关系矩阵是,幂的求法,29,关系图,R0,R1,R2,R3,的关系图如下图所示.,R0,R1,R2=R4=,R3=R5=,30,幂运算的性质,定理7.6设A为n元集,R是A上的关系,则存在自然数s和t,使得Rs=Rt.,证R为A上的关系,由于|A|=n,A上的不同关系只有个.列出R的各次幂R0,R1,R2,必存在自然数s和t，使得Rs=Rt.该定理说明有穷集上只有有穷多个不同的二元关系。当t足够大时Rt必与某个Rs（st）相等。,31,定理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.,32,证明,(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.,33,定理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由归纳法命题得证.,34,证明,(3)任取qN,若qRx+y=u+v，求R导出的划分.,AA=,根据中的x+y=2,3,4,5,6,7,8将A划分成等价类：A/R=,79,3设R是Z上的模n等价关系,即xyxy(modn),试给出由R确定的Z的划分.,练习3,解设除以n余数为r的整数构成等价类r，则r=kn+r|kZ,r=0,1,n1=r|r=0,1,n1,80,图11,练习4,4设偏序集的哈斯图如图所示.(1)写出A和R的集合表达式(2)求该偏序集中的极大元、极小元、最大元、最小元,解(1)A=a,b,c,d,eR=,IA(2)极大元和最大元是a,极小元是d,e；没有最小元.,81,练习5,5设R是A上的二元关系，设S=|c(RR).证明如果R是等价关系，则S也是等价关系。,证R是A上的等价关系.(1)证自反任取x,xARx(RR)S(2)证对称任取,Sc(RR)c(RR)S(3)证传递任取,SSc(RR)d(RR)RRS,82,6设偏序集和，定义AB上二元关系T:TxRuySv证明T为偏序关系.,练习6,证(1)自反性任取,ABxAyBxRxySyT(2)反对称性任取,TTxRuySvuRxvSy(xRuuRx)(ySvvSy)x=uy=v=(3)传递性任取,TTxRuySvuRwvSt(xRuuRw)(ySvvSt)x