离散数学3-6关系的性质和3-7复合关系.ppt

《离散数学3-6关系的性质和3-7复合关系.ppt》由会员分享，可在线阅读，更多相关《离散数学3-6关系的性质和3-7复合关系.ppt（39页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、离散数学离散数学离离 散散 数数 学学Discrete Mathematics 陈明陈明信息科学与工程学院信息科学与工程学院二零一一年十月二零一一年十月离散数学离散数学1、序偶：记作、序偶：记作2、笛卡尔积：记作、笛卡尔积：记作A B3、关系：序偶的集合；前域、值域、关系：序偶的集合；前域、值域4、X到到Y的关系，的关系，X上的关系上的关系5、关系的表示：关系矩阵、关系图、关系的表示：关系矩阵、关系图回顾回顾离散数学离散数学1,，,设设A-2,-1,0,1离散数学离散数学3-6 关系的性质 离散数学离散数学一、自反性和反自反性一、自反性和反自反性1、自反性自反性：设：设R是集合是集合X上的二元

2、关系，如果对于上的二元关系，如果对于每一个每一个x X，有，有 R，则称，则称R是自反的。是自反的。R在在X上自反上自反(x)(x X R)2、反自反性反自反性：设：设R是集合是集合X上的二元关系，如果对上的二元关系，如果对于于每一个每一个x X，有，有 R，则称，则称R是反自反的。是反自反的。R在在X上反自反上反自反(x)(x X R)离散数学离散数学例如，在实数集合中，例如，在实数集合中，”是自反的，因为对于任意实数是自反的，因为对于任意实数x x成立。成立。平面上三角形的全等关系是自反的。平面上三角形的全等关系是自反的。例：例：X=a，b，c，R1=，R2=，R3=，注意：注意：R不是自

3、反的，未必一定是反自反的。一个关系可不是自反的，未必一定是反自反的。一个关系可能既不是自反的，也不是反自反的。能既不是自反的，也不是反自反的。离散数学离散数学3、关系矩阵的特点、关系矩阵的特点自反关系的关系矩阵的对角元素自反关系的关系矩阵的对角元素均均为为1，反自反，反自反关系的关系矩阵的对角元素均为关系的关系矩阵的对角元素均为0。4、关系图的特点、关系图的特点自反关系的关系图，每个结点均有自回路，而反自反关系的关系图，每个结点均有自回路，而反自反关系的关系图，每个结点均没有自回路。自反关系的关系图，每个结点均没有自回路。离散数学离散数学5、结论、结论(两个充要条件两个充要条件)R是是X上的二

4、元关系，则：上的二元关系，则：(1)R是自反关系的充要条件是是自反关系的充要条件是IX R；(2)R是反自反关系的充要条件是是反自反关系的充要条件是R IX=。离散数学离散数学1、对称性对称性：设：设R是集合是集合X上的二元关系，如果对于上的二元关系，如果对于每一个每一个x，y X，每当每当 R，就有，就有 R，则称则称R是对称的。是对称的。R在在X上对称上对称(x)(y)(x X y X R R)2、反对称性反对称性：设：设R是集合是集合X上的二元关系，如果对上的二元关系，如果对于每一个于每一个x，y X，每当每当 R和和 R必必有有x=y，则称，则称R是反对称的。是反对称的。R在在X上反对

5、称上反对称(x)(y)(x X y X R Rx=y)二、对称性和反对称性二、对称性和反对称性离散数学离散数学例如，平面上三角形的相似关系是对称的。例如，平面上三角形的相似关系是对称的。例：例：R1=，R2=，R3=，R4=，注意：存在关系既不是对称的，也不是反对称的。注意：存在关系既不是对称的，也不是反对称的。也存在关系既是对称的，也是反对称的。也存在关系既是对称的，也是反对称的。离散数学离散数学3、关系矩阵和关系图的特点、关系矩阵和关系图的特点 对称关系的关系矩阵是对称矩阵，即对所有对称关系的关系矩阵是对称矩阵，即对所有i，j，rijrji；对称关系的关系图，任何两个不同；对称关系的关系图

6、，任何两个不同的结点之间，或者有双向两条弧，或者没有弧。的结点之间，或者有双向两条弧，或者没有弧。反对称关系的关系矩阵，如果在非对角元上反对称关系的关系矩阵，如果在非对角元上rij1，则在其对称位置上，则在其对称位置上rji0，反对称关系的，反对称关系的关系图，任何两个不同的结点之间至多有一条弧。关系图，任何两个不同的结点之间至多有一条弧。离散数学离散数学1、定义：设、定义：设R是集合是集合X上的二元关系，如果对于任上的二元关系，如果对于任意意x，y，z X，每当每当 R，R时就有时就有 R，则称则称R是传递的。是传递的。R在在X上传递上传递(x)(y)(z)(x X y X z X R R

7、R)例：例：R1=,是传递的，是传递的，R2=,也是传递的，它没有违背定义。也是传递的，它没有违背定义。R3=,不是传递的。不是传递的。三、传递性三、传递性离散数学离散数学2、定理：设、定理：设R、S是是A上的传递关系，则上的传递关系，则R S也也是是A上的传递关系。上的传递关系。注意：R、S均是传递的，但RS未必是传递的。例：R=，S=，则R、S均是传递的，但RS=，不是传递的。证明：设 RS，RS，则 R，R且 S，S。因为R、S是A上的传递关系，所以R，S，从而 RS，即RS是A上的传递关系。离散数学离散数学综合练习：综合练习：集合集合A上的关系上的关系R，如果是对称且传递的，则它，如果

8、是对称且传递的，则它也是自反的。其理由是，从也是自反的。其理由是，从aRb，由对称性得，由对称性得bRa，再由传递性得，再由传递性得aRa，你说对吗？为什么？，你说对吗？为什么？不对！再看自反性、对称性、传递性的定义。离散数学离散数学自反性：自反性：设设R是集合是集合X上的二元关系，如果上的二元关系，如果对于每一个对于每一个x X，有，有 R，则称，则称R是自反的。是自反的。对称性：对称性：设设R是集合是集合X上的二元关系，如果对于每一个上的二元关系，如果对于每一个x，y X，每当每当 R，就有，就有 R，则称，则称R是对称的。是对称的。传递性：传递性：设设R是集合是集合X上的二元关系，如果对

9、于任意上的二元关系，如果对于任意x,y,z X，每当每当 R，R时就有时就有 R，则称，则称R是传递的。是传递的。离散数学离散数学 自反性是说自反性是说对于每一个对于每一个x X，有，有 R。对称性是说对称性是说每当每当 R，就有，就有 R，没有要求没有要求对于每一个对于每一个x X，传递性是说传递性是说每当每当 R，R时就有时就有 R，也没有，也没有要求要求对于每一个对于每一个x X。因此不能从一个关系是对因此不能从一个关系是对称且传递的推出它是是自反的。称且传递的推出它是是自反的。例如例如A=a，b，c，R=，是是A上的上的一个二元关系，一个二元关系，R是对称且传递的，但是对称且传递的，但

10、R不是自不是自反的，因为对于反的，因为对于c A，没有，没有 R。离散数学离散数学非空集合上的空关系是反自反的，对称的，反非空集合上的空关系是反自反的，对称的，反对称的和传递的，但不是自反的。对称的和传递的，但不是自反的。空集合上的空关系则是自反的，反自反的，对空集合上的空关系则是自反的，反自反的，对称的，反对称的和传递的。称的，反对称的和传递的。非空集合上的全域关系是自反的，对称的和传非空集合上的全域关系是自反的，对称的和传递的，但不是反自反的和反对称的。递的，但不是反自反的和反对称的。离散数学离散数学112页页例题例题4 设某人有三个儿子，组成集合设某人有三个儿子，组成集合A=T,G,H，

11、在在A上的兄弟关系具有哪些性质。上的兄弟关系具有哪些性质。例题例题5 集合集合I=1,2,3,4，I上的关系上的关系R=,讨论讨论R的性质。的性质。离散数学离散数学3-7 复合关系和逆关系 本节讲述关系的运算。本节讲述关系的运算。离散数学离散数学一、复合关系一、复合关系引例：引例：（1）若设）若设R是兄妹关系，是兄妹关系，S是母子关系，则是母子关系，则R与与S的复的复合合T是舅甥关系。是舅甥关系。（2）如）如R是父子关系，是父子关系，R与与R复合是祖孙关系。复合是祖孙关系。离散数学离散数学1、复合关系、复合关系(关系的复合运算关系的复合运算)定义定义3-7.1：设：设X、Y、Z是三个集合，是三

12、个集合，R是是X到到Y的关系，的关系，S是是Y到到Z的关系，则的关系，则R S称为称为R和和S的复合关系，表示的复合关系，表示为为R S=x X z Z(y)(y Y R S)从从R和和S求求R S，称为关系的合成运算。，称为关系的合成运算。离散数学离散数学说明：说明：R与与S能进行复合的前提是能进行复合的前提是R的值域所属集的值域所属集合合Y与与S前域所属集合前域所属集合Y是同一个集合。是同一个集合。例：例：X=1，2，3，4，5，Y=3，4，5，Z=1，2，3，R是是X到到Y的关系，的关系，S是是Y到到Z的关系：的关系：R=|x+y=6=，S=y-z=2=，则则R S=，另可以用推导：另可

13、以用推导：x+y=6，y-z=2，消去，消去y得得x+z=4例：集合例：集合X=x，y，z，d，e，R=，S=，则则R S=，S R=，R R=，S S=离散数学离散数学例题例题1：令：令R=，S=，试求，试求R S，S R，R(S R)，(R S)R，R R，S S，R R R。解：RS=，SR=，R(SR)=(RS)R=RR=，SS=，RRR=，关系的复合运算不满足交换律，满足结合律。离散数学离散数学例题例题2：设：设R1和和R2是集合是集合X=0，1，2，3上的关系，上的关系，R1=|j=I+1或或j=I/2，R2=|I=j+2试求试求R1 R2，R2 R1，R1 R2 R1，R1 R1

14、，R1 R1 R1。解：R1=,R2=,R1R2=,R2R1=,R1R2R1=,R1R1=,R1R1R1=,离散数学离散数学关系的关系的n次幂：次幂：设设R是是X上的二元关系上的二元关系，n N，则关系的，则关系的n次幂次幂R(n)定定义为：义为：(1)R(0)=x；(2)R(n+1)=R(n)R说明：如果说明：如果R是是X到到Y的关系，且的关系，且XY，则，则R2是无意义是无意义的，因为的，因为R R是无法复合的。是无法复合的。离散数学离散数学定理：设定理：设R是集合是集合X上的二元关系，上的二元关系，m，n N，则，则(1)R(m)R(n)=R(m+n)(称第一指数律称第一指数律)(2)(

15、R(m)(n)=R(mn)(称第二指数律称第二指数律)此定理证明可以用数学归纳法加以证明。说明：第三指数律(RS)(n)=R(n)S(n)一般是不成立的。因为：(RS)(2)=(RS)(RS)=R(SR)S，R(2)S(2)=(RR)(SS)=R(RS)S，只要交换律不成立，第三指数律不成立。离散数学离散数学例：设例：设X=1，2，3，4，5，X上关系上关系R为为R=,，则：，则：R(0)=x=,，R(1)=RR(2)=,R(3)=,R(4)=,R(5)=,离散数学离散数学2、复合关系矩阵、复合关系矩阵：设集合X=x1，x2，xm，Y=y1，y2，yn，Z=z1，zP，R是X到Y的关系，其关系

16、矩阵MR=(uij)mn，S是Y到Z的关系，其关系矩阵MS=(vjk)np，复合关系RS是X到Z的关系，其关系矩阵MRS=(wik)mp，则wik=(uijvjk)。j=1n离散数学离散数学例题例题3：给定集合：给定集合A=1，2，3，4，5，在，在A上定义两个关上定义两个关系。系。R=，S=，。求。求R S和和S R的矩阵。的矩阵。解：0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1M RS=0 0 0 1 0 1 0 0 0 0 =0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0

17、 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0M SR=1 0 0 0 0 0 0 0 1 0 =0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0离散数学离散数学3、复合关系的性质、复合关系的性质(1)复合运算结合律设R、S、T分别是X到Y、Y到Z、Z到D的关系，则(RS)T=R(ST)证明：(RS)T zZ，RS，T，yY，R，S，T R，STR(ST)所以(RS)TR(ST)类似可

18、以证R(ST)(RS)T，从而(RS)T=R(ST)离散数学离散数学(2)复合运算与，的关系设R是从集合X到Y的关系，S和T均为Y到Z的关系，U是Z到D的关系，则R(ST)=RSRTR(ST)RSRT(ST)U=SUTU(ST)USUTU证明：R(ST)yY，R(y，z)STR(ST)(RS)(RT)RSRT)RSRT从而R(ST)=RSRT离散数学离散数学1、逆关系、逆关系定义定义3-7.2：设：设R是集合是集合X到到Y的二元关系，如将的二元关系，如将R中每一序偶中每一序偶中的元素顺序互换，所得到的集合称为中的元素顺序互换，所得到的集合称为R的逆关系，记作的逆关系，记作Rc=|R。说明：说明

19、：Rc的关系矩阵是的关系矩阵是R的关系矩阵的转置，的关系矩阵的转置，Rc的关系图是的关系图是将将R的关系图中的弧改变方向。的关系图中的弧改变方向。例：设某集合例：设某集合X=x，y，z，X上的关系上的关系R=，则，则Rc=，二、逆关系二、逆关系离散数学离散数学例题例题4：给定集合：给定集合X=a，b，c，R是是X上的二元关系。上的二元关系。R的关系矩阵的关系矩阵 1 0 1M R=1 1 0 1 1 1求求Rc和和R Rc的关系矩阵。的关系矩阵。解：解：1 1 1M Rc=0 1 1 1 0 1 1 0 1 1 1 1 1 1 1M R Rc=1 1 0 0 1 1 =1 1 1 1 1 1

20、1 0 1 1 1 1离散数学离散数学2、定理、定理3-7.1：设R，R1和R2均是A到B的二元关系，则(1)(Rc)c=R(2)(R1R2)c=R1cR2c(3)(R1R2)c=R1cR2c(4)(AB)c=BA(5)(R)c=Rc R=AB-R(6)(R1-R2)c=R1c-R2c证明：(2)(R1R2)c R1R2 R1R2 R1c R2c R1cR2c离散数学离散数学3、定理、定理3-7.2：设R是X到Y的关系，S是Y到Z的关系，则(RS)c=ScRc。证明：(RS)c RS (y)(yYRS)(y)(yYRcSc)ScRc离散数学离散数学例：例：X=x，y，z，Y=1，2，3，4，5

21、，R是是X上关系，上关系，S是是X到到Y的关系。的关系。R=，S=，则，则R S=，Rc=，Sc=，Sc Rc=，可验证：可验证：Sc Rc=(R S)c离散数学离散数学4、定理、定理3-7.3：设：设R是是X上的二元关系，则上的二元关系，则(1)R是对称的，当且仅当是对称的，当且仅当R=Rc(2)R是反对称的，当且仅当是反对称的，当且仅当R Rc Ix证明：证明：(1)因为因为R是对称的，是对称的，故故RRRc，所以，所以R=Rc。反之，若反之，若R=Rc，因为，因为RRcR，所以所以R是对称的。是对称的。(2)设设R是反对称的，是反对称的，R Rc R Rc R R，因为因为 R是反对称的，是反对称的，所以所以x=y，故，故R Rc Ix。反之，若反之，若R Rc Ix，R Rc有有 Ix，即，即x=y。又又 R Rc R Rc R R，但，但x=y，故故R是反对称的。是反对称的。即当R和R时，必有x=y。离散数学离散数学作业P113:(2);(3);(6).P119:(2)a,b;(4)b,d.离散数学离散数学1、关系的性质、关系的性质自反性、反自反性；自反性、反自反性；对称性、反对称性；对称性、反对称性；传递性；传递性；2、复合关系、复合关系 逆关系逆关系回顾回顾