离散数学教程-6-1-关系运算.ppt

.-吴扬扬制-,1,证明：方法1(反证法)：,P754证明:若A,AB=AC，则B=C,若BC，,则b(bBbC或bCbB)。,不妨设bBbC，,A有aA,使得AB,但AC,与AB=AC矛盾,B=C,方法2(直接证法)：若B=，则AB=AC=,AC=,B=C,若B,bB,A有aA,使得AB,AB=AC,AC,bC,BC,同理可证CB,因此，必有B=C,.-吴扬扬制-,2,4.3关系的运算关系交并差关系的逆求逆关系方法逆关系的性质合成关系求合成关系方法合成关系的性质,主要内容：,.-吴扬扬制-,3,4.3关系的运算1.交、并、差、补(1),设A、B是集合，RAB,SAB,则RS,RS,RS和,x(RS)y,(xRy)(xSy),x(RS)y,(xRy)(xSy),x(R-S)y,例1:设A=a,b,c,d,B=1,2,3,R=,S=,则:RS=,(AB)-R=,RS=,R-S=,.-吴扬扬制-,4,有限集合上关系的交、并、差和补可用矩阵运算表达:MRSi,j=(MRMS)i,j=MRi,jMSi,jMRSi,j=(MRMS)i,j=MRi,jMSi,jMR-Si,j=(MR-MS)i,j=MRi,jMSi,j,4.3关系的运算(2),例2:设A=a,b,c,d,R=,IA为A中恒等关系，,.-吴扬扬制-,5,定义:设A、B是集合，RAB,称从B到A的关系,4.3关系的运算2.关系的逆（1）,为R的逆关系。,例2:设A=a,b,c,d,B=1,2,3，R=,例1:整数集合I上的大于关系，其逆关系是：,整数集合I上的小于关系。,R的逆关系的关系矩阵等于R的关系矩阵的转置矩阵。,R的逆关系的关系图为R的关系图的?,.-吴扬扬制-,6,性质:定理4.3.1:设A、B是集合，RiAB(i=1,2),则,4.3关系的运算2.关系的逆（2）,f)若R1R2,则,证明(f):对任意的,.-吴扬扬制-,7,例3:设A为集合，RAA，则R是对称的，当且仅当,4.3关系的运算2.关系的逆（3）,证明:(必要性)对任意的R，R是对称的,R,因此,（充分性）对任意的R，,由逆关系的定义知：必有R。R是对称的。,同理可证,故,.-吴扬扬制-,8,定义:设A、B、C为集合，R1AB，R2BC，则称关系R1oR2=|xAzCy(yBxR1yyR2z)为R1与R2的合成。例4:设A=a,b,c,B=1,2,3,4,C=,，RAB，SBC,R=,S=,求：RoS.解:RoS=,4.3关系的运算3.关系的合成（1）,能否求SoR？,关系的合成可用矩阵的运算来实现,4.3关系的运算3.关系的合成（2）,如例4中A=a,b,c,B=1,2,3,4,C=,，R=,S=,.-吴扬扬制-,10,关系的合成也能用关系图求得,4.3关系的运算3.关系的合成（3）,如例4中A=a,b,c,B=1,2,3,4,C=,，R=,S=,.-吴扬扬制-,11,4.3关系的运算3.合成关系（4）,合成关系的性质定理4.3.2(结合律):设A、B、C、D为集合，R1AB，R2BC，R3CD，则R1(R2R3)=(R1R2)R3证明：R1(R2R3)和(R1R2)R3都是A到D的二元关系，且a,d,R1(R2R3)合成定义b(bBR1(R2R3)合成定义b(bBR1c(cCR2R3)量词辖域扩张bc(bBR1(cCR2R3)量词辖域收缩c(b(bBR1R2)cCR3)合成定义c(R1R2)cCR3)合成定义(R1R2)R3R1(R2R3)=(R1R2)R3,12,4.3关系的运算3.合成关系（2）,定理4.3.3设A、B、C、D为集合，R1AB，R2,R3BC，R4CD，则(1)R1(R2R3)=(R1R2)(R1R3)(2)(R2R3)R4=(R2R4)(R3R4),(3)R1(R2R3)(R1R2)(R1R3)(4)(R2R3)R4(R2R4)(R3R4),例：设A=1,2,3,4，R1=,R2=，R3=R1(R2R3)=,但(R1R2)(R1R3)=证明(3):对任意R1(R2R3),有bB使R1,R2R3有bB使R1,R2且R3R1R2且R1R3，即(R1R2)(R1R3)因此，R1(R2R3)(R1R2)(R1R3),.-吴扬扬制-,13,上机题：1.编一个程序，实现关系的逆运算和合成运算。程序的主要语句和变量必须说明；交上机作业时，除了打印源程序