《离散数学课件：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)
