《离散数学课件:3-6 复合关系和逆关系》由会员分享,可在线阅读,更多相关《离散数学课件:3-6 复合关系和逆关系(18页珍藏版)》请在金锄头文库上搜索。
1、 六、复合关系和逆关系六、复合关系和逆关系(一一) 复合关系复合关系 设设R1是从是从X到到Y的二元关系,的二元关系, R2是从是从Y到到Z的二元关系,则的二元关系,则R1与与R2的复合关系为从的复合关系为从X到到Z的二元关系,记为的二元关系,记为R1 R2,定义为,定义为 R1 R2=|x X z Z ( y)(y Y R1 R2) 其中其中表示二元关系的表示二元关系的合成运算合成运算.关系合成运算的性质关系合成运算的性质&设设R是从是从X到到Y的二元关系,的二元关系,IX, IY分别是分别是X, Y上上的恒等关系,则的恒等关系,则IX R=R IY=R;&如果二元关系如果二元关系R1的值域
2、与的值域与R2的定义域的交集为空的定义域的交集为空集,则复合关系集,则复合关系R1 R2是空关系;是空关系;&二元关系的合成运算满足二元关系的合成运算满足结合律结合律: 设设R1, R2, R3分别是从分别是从A到到B, B到到C, C到到D的二元关系,则的二元关系,则(R1 R2) R3=R1 (R2 R3).合成运算满足合成运算满足交换律交换律吗?吗? No.六、复合关系和逆关系六、复合关系和逆关系例例例例3.6.13.6.1设二元关系设二元关系R=, , , , S=, , , ,求复合关系,求复合关系R S, S R, R R, R R R. 解:解:R S=, , , ,S R= ,
3、 , , , R R=, , , , ,R R R=, , , , , .(R R) R 用关系图来反映关系的复合,更为直观、可靠用关系图来反映关系的复合,更为直观、可靠. 比如比如R S:123451234123六、复合关系和逆关系六、复合关系和逆关系用关系矩阵求复合关系用关系矩阵求复合关系 设设A B =C,关系矩阵为,关系矩阵为MA=(aij)n n, MB=(bij)n n, MC=(cij)n n, 则则cij=(aik bkj). nk=1上式中,上式中, 代表逻辑加,满足代表逻辑加,满足0 0=0, 0 1=1, 1 0=1, 1 1=1. 代表逻辑乘,满足代表逻辑乘,满足0 0
4、=0, 0 1=0, 1 0=0, 1 1=1.如何理解?如何理解?&公式的理解:要想公式的理解:要想“i ”与与“j ”建立关系,则建立关系,则至少存至少存在一个在一个“k”,使,使“i ”与与“k ”有关系,有关系,且且“k ”与与“j ”有关系有关系.(公式中的(公式中的 和和 分别体现的就是分别体现的就是“至少存在一个至少存在一个”和和“且且”.)&逻辑加逻辑加和和逻辑乘逻辑乘的理解:关系矩阵中的元素的理解:关系矩阵中的元素1和和0,表达,表达的是关系的是关系“有有”和和“无无”,即,即T和和F.(把运算规则中的(把运算规则中的1和和0分别换成分别换成T和和F,易见等式成立,易见等式成
5、立.)六、复合关系和逆关系六、复合关系和逆关系例例例例3.6.23.6.2设设A=1, 2, 3, 4, B=2, 3, 4, C=1, 2, 3,R1是从是从A到到B的的二元二元关系,关系, R2是从是从B到到C的的二元二元关系:关系:R1=|x+y=6分别用列举法、图示法、关系矩阵法表示关系的合分别用列举法、图示法、关系矩阵法表示关系的合成成R1 R2 . =, , ,R2=|y-z=1 =, , ,解:解:(1)列举法列举法R1 R2=, , .(2)图示法图示法1234234123六、复合关系和逆关系六、复合关系和逆关系例例例例3.6.23.6.2设设A=1, 2, 3, 4, B=2
6、, 3, 4, C=1, 2, 3,R1是从是从A到到B的的二元二元关系,关系, R2是从是从B到到C的的二元二元关系:关系:R1=|x+y=6分别用列举法、图示法、关系矩阵法表示关系的合分别用列举法、图示法、关系矩阵法表示关系的合成成R1 R2 . =, , ,R2=|y-z=1 =, , ,(3)关系矩阵法关系矩阵法解:解:六、复合关系和逆关系六、复合关系和逆关系关系的幂关系的幂 设设R是集合是集合A上的二元关系,上的二元关系,n N为任一为任一自然数,则自然数,则R的的n次幂记为次幂记为Rn,定义为:,定义为:(1)R0为为A上的恒等关系,上的恒等关系,R0=|x A.(2)Rn+1=
7、Rn R.从从a到到b有一条长度为有一条长度为2的路径的路径.F在在R2的图形上,有一条的图形上,有一条a到到b的弧,则在的弧,则在R的图形上的图形上从从a到到b有一条长度为有一条长度为n的路径的路径.F在在Rn的图形上,有一条的图形上,有一条a到到b的弧,则在的弧,则在R的图形上的图形上六、复合关系和逆关系六、复合关系和逆关系(二二) 逆关系逆关系例例例例3.6.33.6.3设二元关系设二元关系R=, , ,其逆,其逆关系关系Rc=, , .F注意一个常用的表达:注意一个常用的表达: R Rc 设设R是从是从X到到Y的二元关系,的二元关系, R的的逆关系逆关系(简称为(简称为R的的逆逆)记为
8、)记为Rc,定义如下:,定义如下: Rc=| R .例例例例3.6.4 3.6.4 整数集上的整数集上的“”关系关系 ;集合族上的集合族上的“ ”关系关系 的逆是的逆是“ ”关系关系 ;六、复合关系和逆关系六、复合关系和逆关系逆关系的求法逆关系的求法 将矩阵将矩阵MR转置,得转置,得Rc的关系矩阵的关系矩阵 ,即即&关系图关系图: 把把R中每一序偶的元素顺序互换,可得到中每一序偶的元素顺序互换,可得到逆关系逆关系Rc的所有序偶的所有序偶.六、复合关系和逆关系六、复合关系和逆关系 在在R的关系图中,颠倒弧(有向边)的箭头的关系图中,颠倒弧(有向边)的箭头方向,得到方向,得到Rc的关系图的关系图.
9、&关系矩阵关系矩阵:&列举法列举法:逆关系的性质逆关系的性质性质一性质一:设:设R, R1, R2是是X到到Y的二元关系,则的二元关系,则6) R1 R25) (R1-R2)c =4) (R)c =3) (R1R2)c =2) (R1R2)c=1) (Rc)c= R; R1cR2c;R1cR2c;(Rc);R1c-R2c; R1c R2c. R R;或或 R R.F其中其中R=X Y-R是是X Y中不属于中不属于R的序偶所的序偶所组成的集合,称为组成的集合,称为R的的关系补关系补,或说,或说R是是R关于关于X Y的补集的补集.有常用关系式:有常用关系式:六、复合关系和逆关系六、复合关系和逆关系
10、性质一的证明性质一的证明1) (Rc)c= R; 证明:证明: 任取任取,则,则 R Rc (Rc)c3) (R1R2)c = R1cR2c;证明:证明: 任取任取,则,则 (R1R2)c R1R2 R1 R2 R1c R2c R1cR2c六、复合关系和逆关系六、复合关系和逆关系性质一的证明性质一的证明4) (R)c =(Rc);证明:证明: 任取任取,则,则 (R)c R R Rc (Rc).5) (R1-R2)c =R1c-R2c; 证明:证明: 因为因为R1-R2=R1R2,故有,故有(R1-R2)c =(R1R2)c =R1c(R2)c =R1c (R2)c =R1c-R2c. 6)
11、R1 R2R1c R2c.证明:证明: 任取任取 R1c,则,则 R1c R1 R2 R2c六、复合关系和逆关系六、复合关系和逆关系逆关系的性质逆关系的性质性质二性质二:设设R1是从是从X到到Y的二元关系,的二元关系, R2是从是从Y到到Z的二元关系,的二元关系, 则则(R1 R2)c=R2c R1c.证明:证明: 任取任取,则,则 (R1 R2)c R1 R2 ( y)(y Y R1 R2) R2c R1c. ( y)(y Y R1c R2c) XYZR1R2(R1 R2)cR1 R2六、复合关系和逆关系六、复合关系和逆关系逆关系的性质逆关系的性质性质三性质三:设设R是集合是集合X上的二元关
12、系,上的二元关系, 则则(1) R是对称的,当且仅当是对称的,当且仅当 R =Rc;(2)证明:证明: (2) R是反对称的,当且仅当是反对称的,当且仅当 R Rc IX.设设R是反对称的,任取是反对称的,任取 R Rc,则则 R Rc R R而而R是反对称的,是反对称的, 故故x=y. 所以所以 = IX即即R Rc IX.六、复合关系和逆关系六、复合关系和逆关系逆关系的性质逆关系的性质性质三性质三:设设R是集合是集合X上的二元关系,上的二元关系, 则则(1) R是对称的,当且仅当是对称的,当且仅当 R =Rc;(2)证明:证明: (2) R是反对称的,当且仅当是反对称的,当且仅当 R Rc
13、 IX.反之,设反之,设R Rc IX , R R故故R是反对称的是反对称的. R R,则,则 R Rc R Rc IX x=y.六、复合关系和逆关系六、复合关系和逆关系任取任取x, y X, 若若(1) R在在X上自反,当且仅当上自反,当且仅当例例例例3.6.5 3.6.5 设设R为为X上的二元关系,证明:上的二元关系,证明:(2) R在在X上反自反,当且仅当上反自反,当且仅当(3) R在在X上传递,当且仅上传递,当且仅当当 证明:证明:IX R.RIX = .R R R.(1)必要性:必要性: 任取任取 IX ,如果如果R在在X上自反,必有上自反,必有 IX x X R ,从而从而IX R
14、.充分性:充分性:当当IX R时,时,x X IX R ,因此因此R在在X上是自反的上是自反的.F从关系矩阵角度看,从关系矩阵角度看, R是自反的,则是自反的,则MR的主对角元的主对角元全为全为1. 所以所以IX R .任取任取x X , 有有六、复合关系和逆关系六、复合关系和逆关系结论结论可直可直接用接用(1) R在在X上自反,当且仅当上自反,当且仅当例例例例3.6.5 3.6.5 设设R为为X上的二元关系,证明:上的二元关系,证明:(2) R在在X上反自反,当且仅当上反自反,当且仅当(3) R在在X上传递,当且仅上传递,当且仅当当证明:证明:IX R.RIX = .R R R.(2)必要性
15、必要性:(反证反证法法)设设R在在X上反自反,但上反自反,但RIX ,则必存在则必存在 RIX , 从而从而 RIX R IX R x= y R . 这与这与“R是反自反的是反自反的”矛盾矛盾.设设RIX = ,充分性充分性:任取任取x X,则,则x X IX R 所以所以R在在X上是反自反的上是反自反的.F从关系矩阵角度看,从关系矩阵角度看, R是反自反的,则是反自反的,则MR的主对角的主对角元全为元全为0. 所以所以RIX = .(1) R在在X上自反,当且仅当上自反,当且仅当例例例例3.6.53.6.5设设R为为X上的二元关系,证明:上的二元关系,证明:(2) R在在X上反自反,当且仅当上反自反,当且仅当(3) R在在X上传递,当且仅上传递,当且仅当当证明:证明:IX R.RIX = .R R R.(3)必要性必要性:设设R在在X上是传递的,上是传递的,设设R R R,任取任取 R R ,有有 ( t)( R R)所以所以R R R. R.充分性充分性:任取任取 R , R ,则则 R R R R R R R . 所以所以R是传递的是传递的. 六、复合关系和逆关系六、复合关系和逆关系HW: 3-7习题习题 (3);(6);(8)