离散数学第4章-关系ppt课件.ppt

《离散数学第4章-关系ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学第4章-关系ppt课件.ppt（145页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第4章 关系1认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目4-1.关系及其运算n关系的基本概念关系的基本概念n“关系”是一个很基本的概念,为了用数学的方法来研究和讨论各种关系,下面从集合论的观点来描述关系.n例:设A=a,b,c,d,e,f,a,b,c,d,e,f分别表示个男人,其中a是b和c的父亲,b是d的父亲,c是 e和f的父亲.则这6个人中所有符合父子关系的两个人可分别用有序偶(a,b),(a,c),(b,d),(c,e),(c,f)来表示，则集合 (a,b),(a,c),(b,d),(c,e),(c,f)可完整地

2、描述出集合中元素的父子关系称R为集合上的一个关系(父子关系).例:，上的小于关系可表示为(1,2),(1,3),(2,3)2认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目两个集合之间的关系n设A=a,b,c,d,B=m,p,e,A中的元素a,b,c,d分别表示4位中学教师,B中的元素m,p,e分别表示数学课程、物理课程和英语课程。如果a和b是数学教师，c是物理教师，d是英语教师。则有序偶:(a,m),(b,m)(c,p),(d,e)表示了这表示了这4位教师和他们所讲授课程的关系。由这些位教师和他们所讲授课程的关系。由这些有

3、序偶有序偶作为元素作为元素构成的集合构成的集合 R=（a,m),(b,m)(c,p),(d,e)称为称为A到到B的二元关系的二元关系。二元关系的实质是什么？二元关系的实质是什么？3认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目关系的实质n由于二元关系就是符合某种特定要求的有序偶的集合.n因此A到B的二元关系应是笛卡儿乘积A B的子集nA上的二元关系应是A上的笛卡儿乘积A A的子集。n为了便于对二元关系进行一般性的讨论，下面把二元关系的概念抽象化，即抽象地把二元关系看做是笛卡儿乘积的子集。4认识到了贫困户贫困的根本原因，才能

4、开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目二元关系的定义n定义 设A,B 是集合，R是笛卡儿乘积A B的子集，则称R为A到B的一个二元关系。n例如:设A=a,b,c,d,B=x,y,z,令R=(a,y),(b,x),(b,y),(d,x)n由于R是A B的子集，所以R是A到B的一个二元关系。n类似,可定义n元关系.5认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目n元关系的定义n定义6认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开

5、了“精准扶贫”项目二元关系的定义n 对于二元关系R,如果(a,b)R，也可记作aRb，并称a 与b 有关系R。如果(a,b)R，也可记作a R b，并称a与b没有关系R。n定义 设A是集合，R是A上的笛卡儿乘积A A的子集，则称R为A上的一个二元关系。n例如:设A=1，2，3，4，5,R=（1，1）,（2，5）,（3，1）,（4,3）,(4,5)，由于R是A A的子集，所以R为A上的一个二元关系。7认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目二元关系的二元关系的定义域定义域和和值域值域n定义 设S是A到B的二元关系，使(

6、x,y)S的所有x组成的集合称为S的定义域，记作D(S)；使(x,y)S的所有y组成的集合称为S的值域，记作C(S)或R(S)。易知:D(S)就是S的所有有序偶的第一个元素构成的集合,C(S)就是S的所有有序偶的第二个元素构成的集合.8认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目求关系的求关系的定义域定义域和和值域值域n例如:设 则R的定义域D(R)，值域C(R)9认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例1n例1:设A=2，4，6，8，R是A

7、上的小于关系，即当a,bA且a0时，（a,b）R。则R=（1，1）,（1，2）,（1，3）,（2，2）,（2，1）,（2，3）,（3，1）,（3，2）,（3，3）所以R是A上的全域关系。若令当a,bA且ab 0时，（a,b）R，则R=即R是A上的空关系。n例5:设A=a,b,c,d,则A上的恒等关系 =(a,a),(b,b),(c,c),(d,d)。练习练习16认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目2 关系的表示方法n1.1.关系矩阵关系矩阵 设集合 ，R是A到B的二元关系，令则称为R的关系矩阵.17认识到了贫困户

8、贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目关系的表示方法n例1:设 R是A到B的二元关系，且则R的关系矩阵为 A是行，是行，B是列是列18认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目关系的表示方法n设 ,R为A上的二元关系,令 则n阶方阵称为R的关系矩阵19认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目关系的表示方法n例2 设A=1,2,3,4,5,R是A上的小于等于关系,即当a b时,(

9、a,b)R。求R的关系矩阵。解:易知A上的小于等于关系为R=（1,1),(1,2),(1,3),(1,4),(1,5),(2,2),(2,3),(2,4),(2,5),(3,3),(3,4),(3,5),(4,4),(4,5),(5,5)其关系矩阵为20认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目关系的表示方法n2.2.关系图关系图 设集合 ，R是A到B的二元关系。R的图形表示是在平面上用n 个点分别表示A中的元素 ；再在平面上画出m个点分别表示B中元素 ；当 时，从点 至 画一条有向边，其箭头指向 ，否则就不画边。n例

10、3:R是A到B的二元关系，且则R的关系图为？a2a1a3a4a5b1b2b3b421认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目关系的表示方法n当R是A上的二元关系时，经常采用如下的图形表示方法：在平面上仅仅画n个点分别表示A中的元素 ，当 时，从点 至 画一条有向边，箭头指向 。n例如，R是A上的二元关系，且 则R的关系图为 22认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目小结二元关系的表示方法（它们可唯一相互确定）n集合表达式n关系矩阵（用矩阵

11、表示关系，便于在计算机中对关系进行存储和计算，并可充分利用矩阵的结论）n关系图（关系图直观清晰，是分析关系性质的方便形式，但它不便于进行运算）练习练习23认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目3.关系的运算n关系的交、并、差、对称差、补关系的交、并、差、对称差、补n设R和S是集合A上的两个二元关系,则 RS,RS,R-S,R+S,R 仍是A上的二元关系.24认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目关系的运算n例：X=a,b,c，Y=1，2

12、，关系R=(a,1),(b,2),(c,1)S=(a,1),(b,1),(c,1)则：RS=(a,1),(b,1),(b,2),(c,1)RS=(a,1),(c,1)E=(a,1),(a,2),(b,1),(b,2),(c,1),(c,2),R=E-R=(a,2),(b,1),(c,2)练习25认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目复合关系n1.复合关系的定义n定义 R是A到B的二元关系，S是B到C的二元关系，R和S的复合记作RS，它是A到C的二元关系，仅当 (a,b)R，且(b,c)S时，(a,c)RS。n例:设

13、 ，R是A到B的二元关系，S是B到C的二元关系，且 则R和S的复合 26认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目用关系图法求复合关系 R S A B C a1 b1 c1 a2 b2 c2 a3 b3 c3 b427认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目用关系图法求复合关系由R和S的关系图得，复合关系 R S A A A a1 a1 a1 a2 a2 a2 a3 a3 a3 a4 a4 a4 a5 a5 a528认识到了贫困户贫困的根本原

14、因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目复合关系的矩阵表示n定理 R是A到B的二元关系，其关系矩阵为 ，S是B到C的二元关系，其关系矩阵为 ，复合关系RS是A到C的二元关系，其关系矩阵为 ，则 注意:按普通矩阵乘法求 ,只不过是将乘法改为布尔乘,加法改为布尔加.29认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例1n设A=1，2，3，B=a,b,c,d,C=x,y,z，R是A到B的二元关系，R=(1,a),(1,b),(2,b),(3,c)，S是B到C的二元关系，S=(a

15、,x),(b,x),(b,y),(b,z)。求复合关系RS的关系矩阵.n解:因为 n所以30认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例2n设A=1，2，3，4，R和S都是A上的二元关系，R=（1，1），（1，2），（2，3），（2，4），（3，2），（4，3），（4，4），S=（1，2），（1，3），（2，3），（2，4），（3，3），（4，3）,求复合关系RS的关系矩阵。n解:RS=(1,2),(1,3),(1,4),(2,3),(3,3).(3,4),(4,3)练习31认识到了贫困户贫困的根本原因，才能开始对症下

16、药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目二元关系的幂n二元关系的复合可产生一个新的二元关系，因此二元关系的复合也是二元关系的一种运算。n由于二元关系与其关系矩阵一一对应，复合关系RS的关系矩阵等于R的关系矩阵与S的关系矩阵的乘积，而矩阵的乘法是满足结合律的，所以关系的复合也满足结合律，即 (RS)T=R(ST)n二元关系的幂 由于二元关系的复合满足结合律,所以二元关系的幂是有意义的.32认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目逆关系n定义 设R是A到B的二元关系，如果把R中的每一个有

17、序偶中的元素顺序互换，所得的B到A的二元关系称为R的逆关系，记作 n例1:设A=x,y,z,B=a,b，R是A到B的二元关系，且有 R=(x,a),(y,b),(z,a)则R的逆关系 是B到A的二元关系，且有 33认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目逆关系n例2:设A=1,2,3,4,R是A上的二元关系,且有 R=(1,2),(2,3),(3,4)则其逆关系 n由逆关系的定义可知 n如果二元关系R的关系矩阵为 ，则 的转置矩阵 就是逆关系 的关系矩阵，即即n如果把R的关系图中每条有向边的方向颠倒，就得到逆关系 的

18、关系图。34认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目逆关系n又由矩阵的运算法则可知由此可得以下定理。n定理 设R是A到B的二元关系，S是B到C的二元关系，则 练习35认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目4-2 关系的重要性质n关系的基本类型：自反的二元关系反自反的二元关系对称的二元关系反对称的二元关系可传递的二元关系n或称为关系的性质：自反性、反自反性、对称性、反对称性、可传递性36认识到了贫困户贫困的根本原因，才能开始对症下药，然后药

19、到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目1.自反的二元关系n定义定义 设设R R是是A A上的二元关系，如果对于上的二元关系，如果对于A A中中每每一个一个元素元素x x，都有，都有(x,x)R(x,x)R，则称，则称R R是是自反自反的的，也称，也称R R具有具有自反性自反性。n例例1 1:A=a,b,c,A:A=a,b,c,A上的二元关系上的二元关系 R=(a,a),(b,b),(c,c),(a,c),R=(a,a),(b,b),(c,c),(a,c),(c,b)(c,b)，则，则R R是是自反的二元关系。自反的二元关系。n例例2:2:设设A=1,2,3,4,A=1

20、,2,3,4,R=(1,1),(2,2),(3,4),(4,2),R=(1,1),(2,2),(3,4),(4,2),因为因为3A,3A,但但(3,3),(3,3),所以所以R R不是不是A A上的自反关系上的自反关系.37认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目1.自反的二元关系n例3：设A=1,2,3,1.R是A上的小于关系,即当 ab 时,(a,b)R。求R的关系矩阵。2.S是A上的等于关系,即当 a=b 时,(a,b)R。求S的关系矩阵。解:R=(1,2)(1,3)(2,3)38认识到了贫困户贫困的根本原因，

21、才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目1.自反的二元关系n一个集合的关系R是自反的：当且仅当关系矩阵的对角线元素都为1。n例：A=a,b,c,AA=a,b,c,A上的二元关系上的二元关系R=(a,a),(b,b),(c,c),(a,c),(c,b)R=(a,a),(b,b),(c,c),(a,c),(c,b)R是自反关系39认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目2.反自反的二元关系n定义 R是A上的二元关系，如果对于A中每一个元素x,都有(x,x),则称R是反自反的

22、，也称R具有反自反性。n例1:设A=a,b,c,R=(a,c),(b,a),(b,c),(b,b)n因为(b,b)R,则R不是A上的反自反关系。n例2:设A=1，2，3，R是A上的小于关系，即(1,2),(1,3),(2,3)n由于(1,1),(2,2),(3,3)都不属于R，所以R是A上的反自反关系。40认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目2.反自反的二元关系n例例3:3:设设A=1,2,3,R=(1,2),(2,3),(3,2),(3,3),A=1,2,3,R=(1,2),(2,3),(3,2),(3,3),

23、S=(1,1),(2,2),(2,3),(3,3),S=(1,1),(2,2),(2,3),(3,3),则则 R R既不是既不是A A上的反自反关系上的反自反关系(因因(3,3)R),(3,3)R),也不是也不是A A上的自反关系上的自反关系(因因(1,1)(1,1)S S是是A A上的自反关系上的自反关系,但不是反自反关系但不是反自反关系.注意注意:一个关系一个关系R R如果不是如果不是自反关系，自反关系，不一定是不一定是反反自反关系自反关系.41认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目2.反自反的二元关系n一个集

24、合的关系R是反自反的：当且仅当关系矩阵的对角线元素都为0。n例：A=a,b,c,AA=a,b,c,A上的二元关系上的二元关系R=(a,b),(a,c),(c,b)R=(a,b),(a,c),(c,b)R是反自反关系42认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目3.对称的二元关系n定义定义 R R是是A A上的二元关系，上的二元关系，每当每当(x,y)R(x,y)R时，时，就一定有就一定有(y,x)R(y,x)R，则称，则称R R是是对称的对称的，也称，也称R R具有具有对称性对称性。n例例1 1:设设A=a,b,c,R

25、=(a,b),(b,A=a,b,c,R=(a,b),(b,a),(a,c),(c,a)a),(a,c),(c,a)，所以，所以R R是对称的是对称的。n例例2 2:设设A=1,2,3,4A=1,2,3,4上的二元关系上的二元关系 R=(1,1),(1,2),(2,1),(3.3),(4,3),(4,4),R=(1,1),(1,2),(2,1),(3.3),(4,3),(4,4),因为因为(4,3)R(4,3)R但但(3,4)(3,4)。所以所以R R不是对称的不是对称的。43认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目3

26、.对称的二元关系n一个集合的关系R是对称的：当且仅当关系矩阵关于对角线对称。n例：A=a,b,cA=a,b,c，d,Ad,A上的二元关系上的二元关系R=(a,b),(a,d),(b,a),(b,c),(c,b),R=(a,b),(a,d),(b,a),(b,c),(c,b),(c,d),(d,a),(d,c),(d,d)(c,d),(d,a),(d,c),(d,d)R是对称关系44认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目3.对称的二元关系n例：A=a,b,cA=a,b,c，d,Ad,A上的二元关系上的二元关系R=(a

27、,b),(a,d),(b,a),(d,d)R=(a,b),(a,d),(b,a),(d,d)R不是对称关系45认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目4.反对称的二元关系n定义定义 R R是是A A上的二元关系，上的二元关系，当当x yx y时，如果时，如果 (x,y)R(x,y)R，则必有，则必有(y,x)(y,x)，称，称R R是是反对反对称的称的，也称，也称R R具有具有反对称性反对称性。n例例1:1:A=1,2,3,A=1,2,3,上的关系上的关系R=(1,2),(2,2),(3,1),R=(1,2),(2,

28、2),(3,1),则则R R是是反对称反对称的的.但但S=(1,2),(1,3),(2,2),(3,1)S=(1,2),(1,3),(2,2),(3,1)不是反对称的不是反对称的.因为因为1313但但(1,3)S,(1,3)S,且且(3,1)S(3,1)S46认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目4.反对称的二元关系n例例2:2:设设A=2A=2，3 3，4 4，6 6，R R是是A A上的整除上的整除关系关系(即当即当a,bAa,bA且且a a能整除能整除b b时，（时，（a,a,b b）R)R)，问，问R R是

29、否是是否是A A上的反对称关系上的反对称关系?n解解:因为因为R=R=（2 2，2 2）,（2 2，4 4）,（2 2，6 6）,（3 3，3 3）,（3 3，6 6）,（4 4，4 4）,（6 6，6 6）n由定义知：由定义知：R R是反对称的是反对称的.n例例3 3:实数集合上的实数集合上的小于关系小于关系和和小于等于关系小于等于关系都是都是反对称反对称的的.47认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目4.反对称的二元关系n关系R是反对称的，则其关系矩阵为：如果rij=1,并且ij，则rji=0nA=2A=2，3

30、 3，4 4，6 6，nR=(2,4),(2,6),(3,6)R=(2,4),(2,6),(3,6)48认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目4.反对称的二元关系n例4:设A=a,b,c,d上的关系 R=(a,a),(b,c),(c,d),(d,c),S=(a,a),(b,b),(d,d),则R既不是对称的(因为(b,c)R但(c,b),也不是反对称的(因为(c,d)R且(d,c)R)而S既是对称的,也是反对称的.49认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展

31、开了“精准扶贫”项目4.反对称的二元关系 小结n注意:对称关系和反对称关系不是两个相互否定的概念.存在既是对称的也是反对称的二元关系,也存在既不是对称的也不是反对称的二元关系.50认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目5.可传递的二元关系n定义 设R是A上的二元关系，每当(x,y)R且(y,z)R时，必有 (x,z)R，则称R是可传递的，也称R具有可传递性。n例1:实数集上的小于关系和小于等于关系都是可传递关系.如：ab,bc 则ac51认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫

32、工作高度重视，已经展开了“精准扶贫”项目5.可传递的二元关系n例2:设A=a,b,c上的关系R=(a,a),(a,b),(b,c),(a,c),S=(a,b),(c,b),T=(a,b),(b,b),(b,c),则R,S,T是否可传递？R,S是可传递的,T不是可传递的 因为T中有(a,b)T,(b,c)T但(a,c),所以T不是可传递关系52认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例3n设A=a,b,c，R是A上的二元关系，R=(a,a),(b,b),(a,b),(a,c),(c,a)，问：R是自反的吗？是反自反的吗

33、？是对称的吗？是反对称的吗？是可传递的吗？n解 n由于c A，而(c,c)，所以R不是自反的。n由于(a,a)R，(b,b)R，所以R不是反自反的。n由于(a,b)R，而(b,a)，所以R不是对称的。n由于(a,c)R，且(c,a)R，所以R不是反对称的。n由于(c,a)R且(a,c)R，但(c,c)，所以R不是可传递的。53认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目自反,反自反,对称,反对称,可传递关系判定方法n定义法n关系矩阵法n关系图法54认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对

34、扶贫工作高度重视，已经展开了“精准扶贫”项目几种基本关系的关系矩阵和关系图的特征表达方式自反性反自反性对称性反对称性传递性关系矩阵主对角线元素全是1.主对角线元素全是0.矩阵是对称矩阵.如果 ,且 ,则 .对 中1所在的位置,在M中相应的位置也都是1.关系图每个顶点都有环.每个顶点都没有环.如果两个顶点之间有边,一定是一对方向相反的边(无单边).如果两个顶点之间有边,一定是一条有向边(无双向边).如果顶点 到 有边,到 有边,则从 到 有边.55认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例1：判断关系的性质n设设A=1

35、A=1，2 2，33，分析，分析A A上的下述上的下述5 5个关系各具有个关系各具有哪些性质？哪些性质？L=,L=,N=,N=,S=,S=,G=,G=,56认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 L=,L=,1.1.自反性：自反性：对角线全为对角线全为1 1，所以具，所以具自反性自反性 矩阵矩阵对称对称，所以具，所以具对称性对称性 3.3.对称性：对称性：对角线全不为对角线全不为0 0，所以不具，所以不具自反性自反性 2.2.反自反性：反自反性：不具不具反反对称性对称性 4.4.反对称性：反对称性：5.5.传递性：

36、传递性：具具传递性传递性 关系矩阵法关系矩阵法57认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目N=,N=,1.1.自反性：自反性：对角线全为对角线全为0 0，所以不具，所以不具自反性自反性 矩阵不矩阵不对称对称，所以不具，所以不具对称性对称性 3.3.对称性：对称性：对角线全为对角线全为0 0，所以具，所以具自反性自反性 2.2.反自反性：反自反性：具具反反对称性对称性 4.4.反对称性：反对称性：5.5.传递性：传递性：具具传递性传递性 关系矩阵法关系矩阵法58认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病

37、除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目S=,1,S=,31.1.自反性：自反性：所有点均无环，所以不具所有点均无环，所以不具自反性自反性 出现单边，所以不具出现单边，所以不具对称性对称性 3.3.对称性：对称性：所有点均无环，所以具所有点均无环，所以具自反性自反性 2.2.反自反性：反自反性：出现双边，不具出现双边，不具反反对称性对称性 4.4.反对称性：反对称性：5.5.传递性：传递性：不具不具传递性传递性 关系图法关系图法59认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目G=,2,G=,31.1.

38、自反性：自反性：存在点无环，所以不具存在点无环，所以不具自反性自反性 出现单边，所以不具出现单边，所以不具对称性对称性 3.3.对称性：对称性：点点1 1有环，所以不具有环，所以不具自反性自反性 2.2.反自反性：反自反性：没有出现双边，具没有出现双边，具反反对称性对称性 4.4.反对称性：反对称性：5.5.传递性：传递性：不具不具传递性传递性 关系图法关系图法60认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例2：A=1A=1，2 2，33，R R1 1=，R R2 2=AA=AA，试判断两关，试判断两关系的性质。系的性

39、质。R R1 1：反自反对称反对称传递R R2 2：自反 对称 传递R R2 2=(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),=(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)(3,1),(3,2),(3,3)61认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例题n设R1,R2为A上的对称关系，证明R R1 1RR2 2也是A上的对称关系。所以所以(x,y)(x,y)和和(y,x)(y,x)成对的出现在成对的出现在R1R2R1R2中，中，

40、R1R2R1R2是对称关系是对称关系思考思考R1 R2是对称的吗？是对称的吗？62认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例题n设 为A上的反对称关系，则 不一定是A上的反对称关系。例如 这里 R R1 1,R,R2 2都是A上的反对称关系，但 R R1 1RR2 2 不是A上的反对称关系，却是对称的。思考:R R1 1RR2 2 在A上是否是反对称的?是反对称的！63认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例5n设R是集合A上的二元关系，

41、如果RR2 2，证明R是传递关系。n证明 当存在(a,b)R，(b,c)R时，由复合关系的定义可知，必有(a,c)R2，而RR2 2，所以(a,c)R，由此证得R是传递关系。证毕。练习练习64认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目4-3 关系的闭包运算n1.自反闭包、对称闭包、传递闭包的定义n定义：R是A上的二元关系，若A上二元关系 R满足（1）R是自反的（对称的，传递的）（2）R R（3）对于任何自反的（对称的，传递的）二元关系R如果 R R，则有R R则称R为R的自反闭包（对称闭包，传递闭包）。65认识到了贫困

42、户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 关系上的闭包运算n由上述定义可知，R的自反闭包（对称闭包，传递闭包）R R：是含有R并且具有自反性质（对称性质，传递性质）的“最小”的二元关系。n通常把二元关系R的自反闭包记作r(R)，对称闭包记作s(R)，传递闭包记作t(R)。例：例：A=1,2,3R=(1,1),(2,2)R1=(1,1),(2,2),(3,2),(3,3)R2=(1,1),(2,2),(3,3)R3=(1,1),(2,2),(1,2),(3,2),(3,3)哪一个关系是哪一个关系是R的的自反闭包自反闭包？包含包含R

43、 R，并且自反，并且自反，并且并且元素个数元素个数最少最少66认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目关系的闭包运算分析n求R的自反闭包比较简单，只需把所有(a,a)R 的有序对补上即可。n求R的对称闭包也比较简单，每当(a,b)R，而(b,a)R 时，把有序偶(b,a)添加到R上即得。67认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目关系的闭包运算分析n求二元关系的传递闭包并不是一件容易的事情。例如：A=a,b,c,d,R=(a,b),(b,c

44、),(c,d)。易见:R不是传递关系，在R中有:(a,b)R和(b,c)R，但(a,c)(a,c)R R(b,c)R和(c,d)R，但(b,d)(b,d)R R如果把有序对如果把有序对(a,c)(a,c)和和(b,d)(b,d)添加到添加到R R中去，使之扩充为中去，使之扩充为R R1 1，所以所以R R1 1仍然仍然不是不是传递关系，也即传递关系，也即R R1 1不是不是R R的传递闭包。的传递闭包。R R1 1=(a,b),(b,c),(c,d),=(a,b),(b,c),(c,d),(a,c),(b,d)(a,c),(b,d)但是，由于但是，由于(a,c)(a,c)R1R1和和(c,d)

45、R1,(c,d)R1,而而(a,d)(a,d)R R1 1，68认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目总结：求闭包的算法n设R为A上的关系，则有69认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目总结：求闭包的算法n证明（3）n先证：根据数学归纳法：1)根据闭包的定义，Rt(R)，所以n=1时R1t(R)成立2)首先假设当n1时，Rnt(R)成立，则再看看任意(x,y)Rn+1时，(x,y)是否也属于t(R)。因为：Rn+1=Rn R，根据复合关

46、系的定义，必存在(x,c)Rn,(c,y)R,才能满足复合关系。因此 又可以得到(x,c)t(R)，(c,y)t(R),根据传递闭包的定义，(x,y)t(R).根据包含的定义，所以Rn+1t(R)3)所以:70认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目总结：求闭包的算法n再证：1)假设(x,y),(y,z)必存在(x,y)Rs，(y,z)Rt,因此：(x,z)RsRt=Rs+t,所以(x,z)所以对于关系 来说，它是传递的。包含R的传递关系都包含了t(R)，所以两个集合互相包含，只能说明两者相等两个集合互相包含，只能说

47、明两者相等，所以71认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目总结：求闭包的算法可以证明，当可以证明，当A A为有限集：为有限集：72认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目求闭包的例子：n例1：设A=a,b,c,d，A上的关系 R=(a,b),(b,a),(b,c),(c,d)求r(R)、s(R)、t(R)73认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例1（续）nR

48、=(a,b),(b,a),(b,c),(c,d)74认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目关系矩阵关系矩阵下下 闭包的构造方法闭包的构造方法n设关系设关系R,r(R),s(R),t(R)的关系矩阵分别为的关系矩阵分别为M,Mr,Ms 和和 Mt,则则 Mr=M+E Ms=M+M T Mt=M+M2+M3+nE 是和是和 M 同阶的单位矩阵同阶的单位矩阵,MT是是 M 的转置矩阵的转置矩阵.n注意在上述等式中矩阵的元素相加时使用注意在上述等式中矩阵的元素相加时使用逻辑加逻辑加.75认识到了贫困户贫困的根本原因，才能开

49、始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例：A=a,b,c,R=(a,b),(b,c),(c,a)求r(R),S(R)和t(R)r(R)=M+E=r(R)=(a,b),(b,c),(c,a),(a,a),(b,b),(c,c)76认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例：A=a,b,c,R=(a,b),(b,c),(c,a)求r(R),S(R)和t(R)(续1)s(R)=M+MT T=s(R)=(a,b),(b,c),(c,a),(a,c),(b,a),(c,b)77认识到

50、了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例：A=a,b,c,R=(a,b),(b,c),(c,a)求r(R),S(R)和t(R)(续2)t(R)=M+M2 2+M3 3=s(R)=(a,b),(b,c),(c,a),(a,c),(b,a),(c,b),(a,a),(b,b),(c,c)M MM M2 2M M3 378认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 关系图关系图下下 闭包的构造方法闭包的构造方法设关系设关系R,r(R),s(R),t(R