复合关系和逆关系-集合与关系-离散数学

复合关系和逆关系第1页本节讲述关系的运算二元关系是以序偶为元素的集合，除了可进行集合并、交、补等运算外，还可以进行一些新的运算。知识点：复合运算：定义计算方法证明逆运算定义计算方法证明第2页关系的定义域与值域关系R中所有序偶x,y的第一元素x组成的集合，称为R的定义域，记作domR，即domR={x|(y)(x,yR)}关系R中所有序偶x,y的第二元素y组成的集合，称为R的值域，记作ranR，即ranR={y|(x)(x,yR)}称fldR=domR∪ranR为R的域。显然R是从A到B的关系，有domRA，ranRB，fldRA∪B。A={1,2,3,4}，B={a,b,c}，RA×BR={1,a,1,c,2,c,3,a,3,c}domR={1,2,3}ranR={a,c}fldR={1,2,3,a,c}举例定义域(domain)：值域(range)：域：第3页一、复合关系例如有3个人a,b,c，A={a,b,c}，R是A上母子关系，S是A上父女关系，a,b∈R∧b,c∈S即a是b的母亲,b是a的儿子;b是c的父亲，c是b的女子。则a和c间就是奶奶和孙女的关系,记作R◦S,称它是R和S的复合关系。RabcSacSR第4页（一）定义3-7.1设X、Y、Z是三个集合，R是从X到Y的关系，S是从Y到Z的关系，则R和S的复合关系记作R◦S。R◦S={x,z|xX∧zZ∧(y)(yY∧x,yR∧y,zS)}(俗称过河拆桥)显然，R◦S是一个新的二元关系，是从X到Z的关系。注意，如果对任意的x∈X和z∈Z，不存在y∈Y，使得xRy和ySz同时成立，则R◦S为空，否则为非空。◦R=R◦=。一、复合关系第5页A={1,2,3}B={a,b,c,d}C={x,y,z,s,t}RA×BSB×C，求R◦S（1）枚举法R={1,b,2,c,2,d,3,a}S={a,y,b,x,b,z,c,s,d,y,d,t}（二）复合关系的计算方法则R◦S={1,x,1,z,2,s,2,y,2,t,3,y}R◦SS◦RS◦R=第6页R={1,b,2,c,2,d,3,a}S={a,y,b,x,b,z,c,s,d,y,d,t}（2）有向图法（首尾相连法）RS。。。Cxyz。s1。2。3。A1。2。3。A。。。Babc。d。t。。。Cxyz。sSR。t第7页MRa1,b1a1,b2...al,bna2,b1a2,b2...a2,bn......am,b1am,b2...am,bn(aij)MSb1,c1b1,c2...bl,ctb2,c1b2,c2...b2,ct......bn,c1bn,c2...bn,ct(bij)a1,c1...al,cta2,c1...a2,ct......am,c1...am,ctMSR(cij)（3）矩阵法（矩阵逻辑积）RS11=(R11∧S11)∨(R12∧S21)∨...∨(R1n∧Sn1)=(R1k∧Sk1)(其中∧是逻辑乘,∨是逻辑加)k=1n∨RSij=(Ri1∧S1j)∨(Ri2∧S2j)∨...∨(Rin∧Snj)=(Rik∧Skj)(1≤i≤m,1≤j≤t)k=1n∨第8页010001000001110003×4。101000001001001=4×51010001011010003×5（3）矩阵法（续）R={1,b,2,c,2,d,3,a}S={a,y,b,x,b,z,c,s,d,y,d,t}即R◦S={1,x,1,z,2,s,2,y,2,t,3,y}第9页设I是实数集合，R和S都是I上的关系，定义如下：R={x,y|y=x2+3x}S={x,y|y=2x+3}xx2+3x2(x2+3x)+3=2x2+6x+3RS所以R◦S={x,y|y=2x2+6x+3}（4）谓词公式法第10页（一）复合关系的性质关系复合运算不满足交换律，但是1.满足结合律:RA×BSB×CTC×D则(R◦S)◦T=R◦(S◦T)2.RA×BSB×CTB×C⑴R◦(S∪T)=(R◦S)∪(R◦T)⑵R◦(S∩T)(R◦S)∩(R◦T)3.R是从A到B的关系，则R◦IB=IA◦R=R二、性质第11页证明：a，d∈(R◦S)◦T(c)(c∈C∧a,c∈R◦S∧c,d∈T)(c)(c∈C∧(b)(a,b∈R∧b,c∈S)∧c,d∈T)(c)(b)(c∈C∧a,b∈R∧b,c∈S∧c,d∈T)(c)(b)(a,b∈R∧(c∈C∧b,c∈S∧c,d∈T))(b)(c)(a,b∈R∧(c∈C∧b,c∈S∧c,d∈T))(b)(a,b∈R∧(c)(c∈C∧b,c∈S∧c,d∈T))(b)(a,b∈R∧b,d∈S◦T)a，d∈R◦(S◦T)所以，(R◦S)◦T=R◦(S◦T)1.满足结合律:RA×BSB×CTC×D则(R◦S)◦T=R◦(S◦T)ABCDRST第12页2.RA×BSB×CTB×C⑴R◦(S∪T)=(R◦S)∪(R◦T)⑵R◦(S∩T)(R◦S)∩(R◦T)证明⑴R◦(S∪T)=(R◦S)∪(R◦T)任取a,c∈R◦(S∪T)(b)(b∈B∧a,b∈R∧b,c∈S∪T)(b)(b∈B∧a,b∈R∧(b,c∈S∨b,c∈T))(b)((b∈B∧a,b∈R∧b,c∈S)∨(b∈B∧a,b∈R∧b,c∈T))(b)(b∈B∧a,b∈R∧b,c∈S)∨(b)(b∈B∧a,b∈R∧b,c∈T)a,c∈R◦S∨a,c∈R◦Ta,c∈(R◦S)∪(R◦T)所以R◦(S∪T)=(R◦S)∪(R◦T)所以，R◦(S∪T)=(R◦S)∪(R◦T)ABCDRST第13页证明⑵：R◦(S∩T)(R◦S)∩(R◦T)任取a,c∈R◦(S∩T)(b)(b∈B∧a,b∈R∧b,c∈S∩T)(b)(b∈B∧a,b∈R∧(b,c∈S∧b,c∈T))(b)((b∈B∧a,b∈R∧b,c∈S)∧(b∈B∧a,b∈R∧b,c∈T))(b)(b∈B∧a,b∈R∧b,c∈S)∧(b)(b∈B∧a,b∈R∧b,c∈T)a,c∈R◦S∧a,c∈R◦Ta,c∈(R◦S)∩(R◦T)所以R◦(S∩T)(R◦S)∩(R◦T)第14页由数学归纳法不难证明性质2的结论对于有限多个关系的并和交也是成立的，即有R◦(R1∪R2∪…∪Rn)＝R◦R1∪R◦R2∪…∪R◦Rn(R1∪R2∪…∪Rn)◦R＝R1◦R∪R2◦R∪…∪Rn◦RR◦(R1∩R2∩…∩Rn)R◦R1∩R◦R2∩…∩R◦Rn(R1∩R2∩…∩Rn)◦RR1◦R∩R2◦R∩…∩Rn◦R第15页3.R是从A到B的关系，则R◦IB=IA◦R=R综上所述，有R◦IB＝R同理可证IA◦R＝R(2)RR◦IB任取x,y∈R◦IB(t)(t∈B∧x,t∈R∧(t,y)∈IB)(t)(t∈B∧x,t∈R∧t＝y)x,y∈RR◦IBR任取x,y∈Rx,y∈R∧x∈A∧y∈Bx,y∈R∧y∈Bx,y∈R∧y,y∈IBx,y∈R◦IBRR◦IB证明:(1)R◦IBRABR第16页例如：令A={1,2,3},B={a,b,c,d}1。2。3。AIA。。。Babc。dR1。2。3。ARIB。。。abc。d。。。Babc。d1。2。3。AB从这两个图看出它们的复合都等于R。第17页令R是A上关系，由于复合运算可结合，所以关系的复合可以写成乘幂形式。即R◦R=R2，R2◦R=R◦R2=R3，…Rn+1＝Rn◦RR0＝{x,x|x∈A}＝IARm◦Rn=Rm+n(Rm)n=Rmn说明对于A上的任何关系R1和R2都有R10＝R20＝IA即：A上任何关系的0次幂都相等，都等于A上的恒等关系IA。二、关系的乘幂若|X|=n，则X中的二元关系R的幂次值是有限的，一般不用求超出X的n的次幂。第18页Rn的计算给定A上的关系R和自然数n，怎样计算Rn呢？下面考虑n≥2的情况。若R是用集合表达式给出的，可以通过n-1次复合计算得到Rn。若R是用关系矩阵M给出的，则Rn的关系矩阵是Mn，即n个矩阵M之逻辑积。若R是用关系图G给出的，可以直接由图G得到Rn的关系图G’。G’的结点集与G相同。对G的每个结点xi，找出从xi出发经过n步长的路径能够到达的结点xj，连接xixj得G’的一条边；得到的所有边组成G’的关系图。第19页例如R是A上关系，如图所示,adbcR:adbcR2:adbcR3:第20页例设A＝{a,b,c,d}，R＝{a,b,b,a,b,c,c,d}，求R的0、1、2、3次幂，分别用矩阵和关系图表示。解答第21页因此M4＝M2，即R4＝R2。因此可以得到R2＝R4＝R6＝…R3＝R5＝R7＝…用关系图的方法可以得到R0,R1,R2,R3,…的关系图第22页二、逆关系逆关系(反关系)也是我们经常遇到的概念，例如≤与≥就是互为逆关系。（一）定义3-7.2R是从A到B的关系，如果将R中的所有序偶的两个元素的位置互换，得到一个从B到A的关系，称之为R的逆关系，记作RC，或R-1。RC={y,x|x,yR}y,x∈RCx,yR或者xRyyRCx例如，小于关系的逆关系是大于关系，大于关系的逆关系为小于关系，相等关系的逆关系仍是相等关系。C=ABRBARC第23页A={1,2,3},B={1,2,3,4}，RA×BR={1,2,2,3,3,1,3,3,3,4}1、枚举法求RCRC={2,1,3,2,1,3,3,3,4,3}2.RC的有向图：将R的有向图的所有边的方向颠倒一下即可。3.RC的矩阵MRC=(MR)T即为R矩阵的转置。如（二）逆关系的计算方法101000011011MR=3×4101000101011MR=c4×3第24页令R、S都是从X到Y的关系，则1.(RC)C=R2.(R∪S)C=RC∪SC。3.(R∩S)C=RC∩SC。4.(R－S)C=RC－SC。5.(~R)C=~RC6.RSRCSC7.令R是从X到Y的关系，S是Y到Z的关系，则(R◦S)C=SC◦RC。(注意≠RC◦SC)（三）逆关系的性质第25页证明2：(R∪S)C=RC∪SC任取y,x(R∪S)Cx,yR∪Sx,yR∨x,ySy,xRC∨y,xSCy,xRC∪SC所以(R∪S)C=RC∪SC,其它(1)(3)(4)性质可类似证。证明5:(~R)C=~RC任取y,x∈(~R)Cx,y∈~Rx,yRy,xRCy,x∈~RC所以(~R)C=~RC（三）逆关系的性质第26页6.RSRCSC证明：例如：R={1,2,2,3,3,1,3,3,3,4},S={1,2,2,1,2,2,2,3,3,1,3,3,3,4}RC={2,1,3,2,1,3,3,3,4,3}SC={2,1,1,2,2,2,3,2,