离散数学(第11讲)二元关系.ppt

C CS S|S SWWU US ST TXDCXDC1 1设设R R，S S都是集合都是集合A A到到B B的两个关系，则：的两个关系，则：RSRS|(xRy)(xSy)|(xRy)(xSy)RSRS|(xRy)(xSy)|(xRy)(xSy)R R|A A B B RR R-S R-S|(xRy)(xS|(xRy)(xSy)y)4.24.2关系的运算关系的运算一、关系的交、并、补、差运算（补充）一、关系的交、并、补、差运算（补充）根根据据定定义义，由由于于A AB B是是相相对对于于R R的的全全集集，所所以以 R RA AB-R,B-R,且且R RR RA AB,RRB,RR。C CS S|S SWWU US ST TXDCXDC2 2设设A Aa,b,c,Ba,b,c,B1,21,2，R R,，S S,，则：则：RSRSRSRSR-SR-S例例,，；,；,A AB-RB-R。C CS S|S SWWU US ST TXDCXDC3 3结论结论q 如果如果R是是A上的关系，则有上的关系，则有（1）R是是自反的自反的充要要条件是充要要条件是IA R（2）R是是反自反的反自反的充要条件是充要条件是RIA=。例例 设设R，S是是A上的自反关系，上的自反关系，试证明试证明R-1，RS，RS，也是，也是A上的自反关系。上的自反关系。C CS S|S SWWU US ST TXDCXDC4 4定义定义设设R R是一个从集合是一个从集合A A到集合到集合B B的二元关系，则的二元关系，则R R的的逆关系逆关系R R-1-1是从是从B B到到A A的关系，的关系，R R-1-1|RR,运算运算“-1-1”称为逆运算称为逆运算。二、关系的逆运算二、关系的逆运算逆关系逆关系 注意：关系是一种集合，逆关系也是一种集注意：关系是一种集合，逆关系也是一种集合，因此，如果合，因此，如果R R是一个关系，则是一个关系，则R R-1-1和都是关和都是关系，但系，但R R-1-1和是完全不同的两种关系，千万不要和是完全不同的两种关系，千万不要混淆。混淆。C CS S|S SWWU US ST TXDCXDC5 5设设A Aa,b,ca,b,c,d,d,B,B1,2,3,R1,2,3,R是从是从A A到到B B的一个关系，的一个关系，R R,，则：则：R R-1-1 A AB-RB-R例例,3。,C CS S|S SWWU US ST TXDCXDC6 6R R、R R-1-1、关系矩阵如下：关系矩阵如下：例例(续续)如用关系图表示逆关系，则仅将关系图中的如用关系图表示逆关系，则仅将关系图中的有向边的方向改变成相反方向。有向边的方向改变成相反方向。如用关系矩阵表示逆关系，则如用关系矩阵表示逆关系，则M MR R-1-1M MR RT T。C CS S|S SWWU US ST TXDCXDC7 7设设R R，S S是从集合是从集合A A到集合到集合B B的二元关系，则有：的二元关系，则有：1)1)；(双重否定律双重否定律)定理（补充）定理（补充）2)2)(R R-1-1)-1-1R R；3)3)()-1-1 ；(可换性可换性)4)4)(RS)(RS)-1-1R R-1-1SS-1-1；(分配性分配性)5)5)(RS)(RS)-1-1R R-1-1SS-1-1；6)6)(R-S)(R-S)-1-1R R-1-1-S-S-1-1；7)7)-1-1；8)8)(A(AB)B)-1-1(B(BA)A)；9)9)S S R R S S-1-1 R R-1-1；(单调性单调性)10)10)；C CS S|S SWWU US ST TXDCXDC8 8证明证明（3 3）()-1-1()-1-1 ；（RS)RS)-1-1R R-1-1SS-1-1 R R R R-1-1 证证 明明（4 4）(R R S S)-1-1 R R S S R R S S R R-1-1 S S-1-1(R R-1-1 S S-1-1)C CS S|S SWWU US ST TXDCXDC9 9（6）若（若（3）、（）、（5）成立，则有）成立，则有 (R-S)-1=(RS)-1=R-1(S)-1 =R-1S-1=R-1-S-1证明：证明：（5）(RS)-1，则，则RS,R S R-1 S-1 R-1S-1 (RS)-1=R-1S-1C CS S|S SWWU US ST TXDCXDC1010设设R R是是A A上的二元关系，那么上的二元关系，那么R R是对称的当且仅是对称的当且仅当当R RR R-1-1证明：证明：充分性充分性 a,bA，如，如R，则，则R1，由于由于R1R，故，故R，R是对称的。是对称的。必要性必要性 R1，则，则R，又因为又因为R是对称的，故是对称的，故R，R1 R，R，因，因R是对称的，是对称的，R，R1，R R1，从而有从而有 RR1。C CS S|S SWWU US ST TXDCXDC40-40-1111结论结论R是是A上反对称关系的充要条件是上反对称关系的充要条件是R R1A。设设R和和S是是A上的反对称关系，则上的反对称关系，则R1、R S、也是、也是A的反对称关系。的反对称关系。R、S均是均是反对称的反对称的，未必能得出，未必能得出R S也也是反对称是反对称的。的。C CS S|S SWWU US ST TXDCXDC1212三、三、关系关系的的合成运算合成运算 设设 R R是是 一一 个个 从从 集集 合合A A到到 集集 合合B B的的 二二 元元 关关系系，S S是是 从从 集集 合合B B到到 集集 合合C C的的 二二 元元 关关 系系(也也 可可简简 单单 地地 描描 述述 为为R R：A A B B，S S：B BC C)，则则R R与与S S的的合合成成关关系系（合合成成关关系系）R R S S是是从从A A到到C C的的关关系系，并并且：且：R R S S|(xA)(zC)|(xA)(zC)(y)y)(yB)(xRy)(ySz)(yB)(xRy)(ySz)运算运算“”称为称为合成运算合成运算。C CS S|S SWWU US ST TXDCXDC1313注意，在合成关系中，注意，在合成关系中，R R的后域的后域B B一定是一定是S S的的前域前域B B，否则，否则R R和和S S是不可合成的。合成的结果是不可合成的。合成的结果R R S S的前域就是的前域就是R R的前域的前域A A，后域就是，后域就是S S的后域的后域C C。如果。如果对任意的对任意的xAxA和和zCzC，不存在，不存在yByB，使得，使得xRyxRy和和ySzySz同时成立，则同时成立，则R R S S为空，否则为非空。并且，为空，否则为非空。并且，R=RR=R =。例：例：1)1)某人某人a a与与c c有外祖父的关系，则一定存在一个有外祖父的关系，则一定存在一个b b，使得使得a a与与b b有父女关系而有父女关系而b b与与c c有母子关系。有母子关系。2)2)某人某人a a与与b b有有“兄妹兄妹”关系，关系，b b和和c c有有“母子母子”关系，关系，则则a a与与c c有有“舅甥舅甥”关系。关系。C CS S|S SWWU US ST TXDCXDC1414例例设设 A AB BC C11,2 2,3 3,44，定义定义 R R为为ABAB的关系的关系 R R,S S为为BCBC的关系的关系 S S,。1 1).用集合方法求用集合方法求 R R S S，S S R R，R R R R，S S S S。则：则：R R S S,；S S R R,；R R R R,；S S S S,。C CS S|S SWWU US ST TXDCXDC1515 R RS SR R。S SA AB BC CA AC C1 1。1 1。1 11 1。1 12 2。2 2。2 22 2。2 23 3。3 3。3 33 3。3 34 4。4 4。4 44 4。4 42)2).用用关关系系图图求求R RS S。例例 R R,，S S,，3 3).用关系矩阵求用关系矩阵求R R S S。M MR R S S M MR R M MS SC CS S|S SWWU US ST TXDCXDC1616定定理理1 1 ：设设R R是是从从集集合合A A到到集集合合B B的的关关系系，S S1 1,S,S2 2是是从从集集合合B B到到集集合合C C的的关关系系，T T是是从从集集合合C C到到集集合合D D的的关系，则：关系，则：1)1)R R (S(S1 1SS2 2)(R(R S S1 1)(R)(R S S2 2)（左分配）（左分配）2)2)(S(S1 1SS2 2)T T(S(S1 1 T)(ST)(S2 2 T)T)（右分配）（右分配）3)3)R R (S(S1 1SS2 2)(R(R S S1 1)(R)(R S S2 2)4)4)(S(S1 1SS2 2)T T(S(S1 1 T)(ST)(S2 2 T)T)C CS S|S SWWU US ST TXDCXDC1717证明：证明：(1)R (S1 1 S2 2)yB，使得，使得R S1 1 S2 2 y(R(S1 1 S2 2)y(R S1 1)y(R S2 2)R S1 1 R S2 2)R S1 1 R S2 2从而有：从而有：R S1 1 R S2 2=R (S1 1 S2 2)C CS S|S SWWU US ST TXDCXDC1818证证明明对对任任意意RR(S(S1 1SS2 2)，则则由由合合成成运运算算知，知，至至少少存存在在ccB,B,使使得得：RR，(S(S1 1SS2 2)。即：即：S S1 1,且且S S2 2。因因 此此，由由 R,R,且且 S S1 1，则则 有有：(R(R S S1 1),),由由R,R,且且S S2 2，则有：，则有：(R(R S S2 2)。所以，所以，(R(R S S1 1)(R(R S S2 2)。即，即，R R(S S1 1SS2 2)(R(R S S1 1)(R)(R S S2 2)。3 3）R R (S(S1 1SS2 2)(R(R S S1 1)(R)(R S S2 2)C CS S|S SWWU US ST TXDCXDC1919定理定理2 2 设设R,S,TR,S,T分别是从集合分别是从集合A A到集合到集合B B，集合，集合B B到到集合集合C C，集合，集合C C到集合到集合D D的二元关系，则的二元关系，则1)1)(R(R S)S)T TR R (S(S T)T)（结合律）（结合律）2)2)(R(R S)S)-1-1S S-1-1 R R-1-1(补充补充)证证明明 1)1)设设(R(R S)S)T T，cC,cC,使得：使得：RR S S，T T。则由合成运算知则由合成运算知,至少存在至少存在R R(S(S T)T),又对于又对于R R S S，则至少存一个，则至少存一个bBbB，使得，使得R R，S S。因此因此,由由S,S,T T,有有S S T T，又由，又由R R和和S S T T，知：，知：所以所以(R(R S)S)T T R R(S(S T)T)。同理可证：同理可证：R(ST)(R(R S)S)T T。由集合性质知：由集合性质知：(R(R S)S)T TR R(S(S T)T)。C CS S|S SWWU US ST TXDCXDC20202)2).任取任取(R(R S)S)-1-1，则，则R R S S由由“”的定义知：则至少存一个的定义知：则至少存一个bB,bB,使得：使得：R R，S S，即：即：R R-1-1,S S-1-1。由由S S-1-1和和R R-1-1,有：有：S S-1-1 R R-1-1，所以，所以，(R(R S)S)-1-1 S S-1-1 R R-1-1。反反之之，任任取取S S-1-1 R R-1-1，由由“”的的定定义义知知：则则至至少少存一个存一个bB,bB,使得：使得：S S-1-1和和R R-1-1，所以：所以：R R，S S。由由“”知：知：R R S S。即有：。即有：(R(R S)S)-1-1。所以，所以，S S-1-1 R R-1-1(R(R S)S)-1-1。由集合的定义知：由集合的定义知：(R(R S)S)-1-1S S-1-1 R R-1-1。定理定理 (续续)2)2)(R(R S)S)-1-1S S-1-1 R R-1-1 C CS S|S SWWU US ST TXDCXDC2121结论结论R是传递关系的充要条件是是传递关系的充要条件是R R R 设设R、S是是A上的传递关系，则上的传递关系，则R1，R S也是也是A上的传递关系。上的传递关系。R，S是传递的，但是传递的，但R S未必是传递的未必是传递的。C CS S|S SWWU US ST TXDCXDC2222定义定义设设R R是集合是集合A A上的二元关系，则可上的二元关系，则可定义定义R R的的n n次幂次幂R Rn n,该该R Rn n也是也是A A上的二元关系，定义上的二元关系，定义如下：如下：1.R1.R0 0I IA A|a|aAA；2.R2.R1 1；3 3.R R2 2 R R R R3.3.R Rn+1n+1R Rn n R RR R R Rn n。四、关系的四、关系的幂幂 显然，显然，R Rm+nm+nR Rm m R Rn n,(R,(Rm m)n nR Rmnmn。C CS S|S SWWU US ST TXDCXDC2323例：设例：设A Aa,b,c,d,e,f,a,b,c,d,e,f,定义在定义在A A上的关系上的关系R R,，求求R Rn n。解解 R R0 0 I IA A,.R R1 1R R，R R2 2R R R R,，R R3 3R R R R R RR R2 2 R R,，R R4 4R R3 3 R R,，R R5 5R R4 4 R R,，R R6 6R R5 5 R R,R R5 5，R R7 7R R6 6 R RR R5 5，R Rn nR R5 5(n(n5)5)。C CS S|S SWWU US ST TXDCXDC2424例例 (续续)S S1 1S,S,S S2 2S S S S,，S S3 3S S S S S SS S2 2 S S,，S S4 4S S3 3 S S,，S S5 5S S4 4 S S，S S6 6S S5 5 S S，S S7 7，S Sn n(n(n5)5)。设设A Aa,b,c,d,e,f,a,b,c,d,e,f,定义在定义在A A上的关系上的关系S S,求求S Sn n。C CS S|S SWWU US ST TXDCXDC2525定定理理3.2.4 令令R A A，且且|A|=n，则则存存在在i和和j，使得使得Ri=Rj，其中，其中0ij2n2。定定理理3.2.5 令令R A A，若若存存在在i和和j，ij，使使得得Ri=Rj。且。且d=j-i，则，则(1)对任意对任意k0,Ri+k=Rj+k。(2)对任意对任意k,m0，Ri+md+k=Ri+k。(3)设设S=R0,R1,R2,Rj+1，对，对 n N，有，有Rn S。C CS S|S SWWU US ST TXDCXDC2626习题习题100100页页1 1 2 2 8 8 10 10 11 11