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

1,第4章 关系,2,4-1.关系及其运算,关系的基本概念“关系”是一个很基本的概念,为了用数学的方法来研究和讨论各种关系,下面从集合论的观点来描述关系.例:设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)可完整地描述出集合中元素的父子关系称R为集合上的一个关系(父子关系).例:，上的小于关系可表示为,(1 , 2) , (1 , 3) , (2 , 3),3,两个集合之间的关系,设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位教师和他们所讲授课程的关系。由这些有序偶作为元素构成的集合 R=（a ,m) ,(b ,m) (c ,p) ,(d ,e) 称为A到B的二元关系。,二元关系的实质是什么？,4,关系的实质,由于二元关系就是符合某种特定要求的有序偶的集合.因此A到B的二元关系应是笛卡儿乘积A B的子集A上的二元关系应是A上的笛卡儿乘积A A的子集。为了便于对二元关系进行一般性的讨论，下面把二元关系的概念抽象化，即抽象地把二元关系看做是笛卡儿乘积的子集。,5,二元关系的定义,定义 设A, B 是集合，R是笛卡儿乘积A B的子集，则称R为A到B的一个二元关系。例如:设A = a, b, c, d, B = x, y, z, 令R = (a, y), (b, x), (b, y), (d, x)由于R是A B的子集，所以R是A到B的一个二元关系。类似,可定义n元关系.,6,n元关系的定义,定义,7,二元关系的定义,对于二元关系R,如果 (a, b) R，也可记作aRb，并称a 与b 有关系R。如果(a, b) R，也可记作a R b，并称a与b没有关系R。定义 设A是集合，R是A上的笛卡儿乘积A A的子集，则称R为A上的一个二元关系。例如:设A = 1，2，3，4，5, R = （1，1）,（2，5）,（3，1）,（4,3）,(4,5)，由于R是A A的子集，所以R为A上的一个二元关系。,8,二元关系的定义域和值域,定义 设S是A到B的二元关系，使(x, y) S的所有x组成的集合称为S的定义域，记作D(S)；使(x, y) S的所有y组成的集合称为S的值域，记作C(S)或R(S)。易知:D(S)就是S的所有有序偶的第一个元素构成的集合, C(S)就是S的所有有序偶的第二个元素构成的集合.,9,求关系的定义域和值域,例如:设 则R的定义域D(R) ， 值域C(R),10,例1,例1:设A = 2，4，6，8，R是A上的小于关系，即当a, bA且a b时，（a, b）R，求R及D( R ),C( R ) 解:R = （2，4）,（2，6）,（2，8）,（4，6）,（4，8）,（6，8）.R的定义域D( R ) =2，4，6，R的值域C( R ) = 4，6，8。,11,例2,例2:设A = 2，3，4，6，12，R是A上的整除关系，即当a, bA且a能整除b时，（a, b）R，求R及D( R ),C( R ) 解:A上有整除关系为R = （2，2）,（2，4）,（2，6）,（2，12）,（3，3）,（3，6）,（3，12）,（4，4）,（4，12）,（6，6）,（6，12）,（12，12），R的定义域D( R ) =2，3，4，6，12，R的值域C( R ) = 2，3，4，6，12。,12,例3,例3 设A = a, b，B = x，y ，写出所有A到B的二元关系。,，,13,例3,例3 设A = a, b，B = x，y ，写出所有A到B的二元关系。 解: 由于 ，所以 ，由此可知，A B共有子集数为 = 16，即共有16种A到B的二元关系：,，,14,例3的说明,此例说明，当时 ，A到B共可定义 种不同的二元关系。问:在一个有n个元素的集合A上，可以有多少种不同的二元关系？答：共有种,15,三种特殊的关系,对于任意集合，空集和集合本身都是它的子集，常称这两种子集为平凡子集。定义笛卡儿乘积A B的两个平凡子集，空集和A B本身称为集合A到B的空关系和全域关系。定义 设R是A上的二元关系且满足则称R为A上的恒等关系，并记作。,16,例子,例4:设集合A = 1，2，3，R是A上的二元关系， 当a, bA且ab0时，（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上的空关系。例5:设A = a, b, c, d ,则A上的恒等关系 = (a, a), (b, b), (c, c), (d, d)。,练习,17,2 关系的表示方法,1.关系矩阵 设集合 ，R是A到B的二元关系，令则称为R的关系矩阵.,18,关系的表示方法,例1:设 R是A到B的二元关系，且则R的关系矩阵为,A是行，B是列,19,关系的表示方法,设 , R为A上的二元关系,令 则n阶方阵称为R的关系矩阵,20,关系的表示方法,例2 设A = 1,2,3,4,5, R是A上的小于等于关系, 即当a b时, (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)其关系矩阵为,21,关系的表示方法,2.关系图 设集合 ，R是A到B的二元关系。R的图形表示是在平面上用n 个点分别表示A中的元素 ；再在平面上画出m个点分别表示B中元素 ；当 时，从点 至 画一条有向边，其箭头指向 ，否则就不画边。例3:R是A到B的二元关系，且则R的关系图为？,22,关系的表示方法,当R是A上的二元关系时，经常采用如下的图形表示方法： 在平面上仅仅画n个点分别表示A中的元素 ， 当 时，从点 至 画一条有向边，箭头指向 。例如， ，R是A上的二元关系，且 则R的关系图为,23,小结,二元关系的表示方法（它们可唯一相互确定）集合表达式关系矩阵（用矩阵表示关系，便于在计算机中对关系进行存储和计算，并可充分利用矩阵的结论）关系图（关系图直观清晰，是分析关系性质的方便形式，但它不便于进行运算）,练习,24,3.关系的运算,关系的交、并、差、对称差、补设R和S是集合A上的两个二元关系,则 RS , RS , R - S , R + S , R 仍是A上的二元关系.,25,关系的运算,例：X=a,b,c，Y=1，2， 关系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),练习,26,复合关系,1. 复合关系的定义定义 R是A到B的二元关系，S是B到C的二元关系，R和S的复合记作RS，它是A到C的二元关系，仅当 (a, b)R，且(b , c)S时，(a, c)RS。例:设 ，R是A到B的二元关系，S是B到C的二元关系，且 则R和S的复合,27,用关系图法求复合关系,R S A B C a1 b1 c1 a2 b2 c2 a3 b3 c3 b4,28,用关系图法求复合关系,由R和S的关系图得，复合关系 R S A A A a1 a1 a1 a2 a2 a2 a3 a3 a3 a4 a4 a4 a5 a5 a5,29,复合关系的矩阵表示,定理 R是A到B的二元关系，其关系矩阵为 ，S是B到C的二元关系，其关系矩阵为 ，复合关系RS是A到C的二元关系，其关系矩阵为 ，则 注意:按普通矩阵乘法求 ,只不过是将乘法改为布尔乘,加法改为布尔加.,30,例1,设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, x), (b, x), (b, y), (b, z)。求复合关系RS的关系矩阵.解:因为 所以,31,例2,设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的关系矩阵 。 解:,RS=(1,2),(1,3),(1,4),(2,3),(3,3).(3,4),(4,3),练习,32,二元关系的幂,二元关系的复合可产生一个新的二元关系，因此二元关系的复合也是二元关系的一种运算。由于二元关系与其关系矩阵一一对应，复合关系RS的关系矩阵等于R的关系矩阵与S的关系矩阵的乘积，而矩阵的乘法是满足结合律的，所以关系的复合也满足结合律，即 (RS)T = R(ST)二元关系的幂 由于二元关系的复合满足结合律,所以二元关系的幂是有意义的.,33,逆关系,定义 设R是A到B的二元关系，如果把R中的每一个有序偶中的元素顺序互换，所得的B到A的二元关系称为R的逆关系，记作 例1:设A = x, y, z, B = a, b，R是A到B的二元关系，且有 R = (x, a), (y, b), (z, a) 则R的逆关系 是B到A的二元关系，且有,34,逆关系,例2:设A = 1, 2, 3, 4, R是A上的二元关系, 且有 R = (1, 2), (2, 3), (3, 4) 则其逆关系 由逆关系的定义可知 如果二元关系R的关系矩阵为 ，则 的转置矩阵 就是逆关系 的关系矩阵，即如果把R的关系图中每条有向边的方向颠倒，就得到逆关系 的关系图。,35,逆关系,又由矩阵的运算法则可知由此可得以下定理。定理 设R是A到B的二元关系，S是B到C的二元关系，则,练习,36,4-2 关系的重要性质,关系的基本类型：自反的二元关系反自反的二元关系对称的二元关系反对称的二元关系可传递的二元关系或称为关系的性质：自反性、反自反性、对称性、反对称性、可传递性,37,1. 自反的二元关系,定义 设R是A上的二元关系，如果对于A中每一个元素x ，都有(x, x )R，则称R是自反的，也称R具有自反性。例1: A = a, b, c, A上的二元关系 R = (a, a), (b, b), (c, c), (a, c), (c, b) ，则R是自反的二元关系。例2:设A=1,2,3,4, R=(1,1),(2,2),(3,4),(4,2),因为3A,但(3,3) , 所以R不是A上的自反关系.,38,1. 自反的二元关系,例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),39,1. 自反的二元关系,一个集合的关系R是自反的：当且仅当关系矩阵的对角线元素都为1。例： A = a, b, c, A上的二元关系R = (a, a),(b, b),(c, c),(a, c),(c, b),R是自反关系,40,2. 反自反的二元关系,定义 R是A上的二元关系，如果对于A中每一个元素x,都有(x, x ) ,则称R是反自反的，也称R具有反自反性。例1:设A = a, b, c, R = (a, c), (b, a), (b, c), (b, b) 因为(b,b)R, 则R不是A上的反自反关系。 例2:设A = 1，2，3，R是A上的小于关系，即(1,2),(1,3),(2,3)由于(1, 1), (2, 2), (3, 3)都不属于R，所以R是A上的反自反关系。,41,2. 反自反的二元关系,例3:设A=1,2,3,R=(1,2),(2,3),(3,2),(3,3), S=(1,1),(2,2),(2,3),(3,3),则 R既不是A上的反自反关系(因(3,3)R), 也不是A上的自反关系(因(1,1) ) S是A上的自反关系,但不是反自反关系.注意:一个关系R如果不是自反关系，不一定是反自反关系.,42,2. 反自反的二元关系,一个集合的关系R是反自反的：当且仅当关系矩阵的对角线元素都为0。例： A = a, b, c, A上的二元关系R = (a, b),(a, c),(c, b),R是反自反关系,43,3. 对称的二元关系,定义 R是A上的二元关系，每当(x, y) R时，就一定有(y, x) R，则称R是对称的，也称R具有对称性。例1:设A = a, b, c, R = (a, b), (b, a), (a, c), (c, a) ，所以R是对称的。例2:设A=1,2,3,4上的二元关系 R=(1,1),(1,2),(2,1),(3.3),(4,3),(4,4),因为(4,3)R但(3,4) 。所以R不是对称的。,44,3. 对称的二元关系,一个集合的关系R是对称的：当且仅当关系矩阵关于对角线对称。例： A = a, b, c，d, A上的二元关系R = (a, b),(a, d),(b,a),(b,c),(c, b), (c,d),(d,a),(d,c),(d,d) ,R是对称关系,45,3. 对称的二元关系,例： A = a, b, c，d, A上的二元关系R = (a, b),(a,d),(b,a),(d,d) ,R不是对称关系,46,4. 反对称的二元关系,定义 R是A上的二元关系，当x y时，如果 (x, y) R，则必有(y, x) ，称R是反对称的，也称R具有反对称性。例1: A=1,2,3,上的关系R=(1,2),(2,2),(3,1),则R是反对称的.但S=(1,2),(1,3),(2,2),(3,1)不是反对称的.因为13但(1,3)S,且(3,1)S,47,4. 反对称的二元关系,例2: 设A = 2，3，4，6，R是A上的整除关系(即当a, bA且a能整除b时，（a, b）R)，问R是否是A上的反对称关系?解:因为R = （2，2）,（2，4）,（2，6）,（3，3）,（3，6）,（4，4）,（6，6） 由定义知：R是反对称的.例3: 实数集合上的小于关系和小于等于关系都是反对称的.,48,4. 反对称的二元关系,关系R是反对称的，则其关系矩阵为：如果rij=1,并且ij，则rji=0A = 2，3，4，6，R = (2,4),(2,6),(3,6),49,4. 反对称的二元关系,例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既是对称的,也是反对称的.,50,4. 反对称的二元关系 小结,注意:对称关系和反对称关系不是两个相互否定的概念. 存在既是对称的也是反对称的二元关系,也存在既不是对称的也不是反对称的二元关系.,51,5. 可传递的二元关系,定义 设R是A上的二元关系， 每当(x, y) R且(y, z) R时，必有 (x, z) R，则称R是可传递的，也称R具有可传递性。例1:实数集上的小于关系和小于等于关系都是可传递关系.如：ab,bc 则ac,52,5. 可传递的二元关系,例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不是可传递关系,53,例3,设A = a, b, c， R是A上的二元关系， R = (a, a), (b, b), (a, b), (a, c) , (c, a)，问：R是自反的吗？是反自反的吗？是对称的吗？是反对称的吗？是可传递的吗？解 由于c A，而(c, c) ，所以R不是自反的。由于(a, a) R，(b, b) R，所以R不是反自反的。由于(a, b) R，而(b, a) ，所以R不是对称的。由于(a, c) R，且(c, a) R，所以R不是反对称的。由于(c, a) R且(a, c) R，但(c, c) ，所以R不是可传递的。,54,自反,反自反,对称,反对称,可传递关系判定方法,定义法关系矩阵法关系图法,55,几种基本关系的关系矩阵和关系图的特征,56,例1：判断关系的性质,设A = 1，2，3，分析A上的下述5个关系各具有哪些性质？ L = , , , , N = , S = , , G = , , ,57,L = , , , , ,1.自反性：,对角线全为1，所以具自反性 ,矩阵对称，所以具对称性 ,3.对称性：,对角线全不为0，所以不具自反性 ,2.反自反性：,不具反对称性 ,4.反对称性：,5.传递性：,具传递性 ,关系矩阵法,58,N = , ,1.自反性：,对角线全为0，所以不具自反性 ,矩阵不对称，所以不具对称性 ,3.对称性：,对角线全为0，所以具自反性 ,2.反自反性：,具反对称性 ,4.反对称性：,5.传递性：,具传递性 ,关系矩阵法,59,S = , , ,1.自反性：,所有点均无环，所以不具自反性 ,出现单边，所以不具对称性 ,3.对称性：,所有点均无环，所以具自反性 ,2.反自反性：,出现双边，不具反对称性 ,4.反对称性：,5.传递性：,不具传递性 ,关系图法,60,G = , , ,1.自反性：,存在点无环，所以不具自反性 ,出现单边，所以不具对称性 ,3.对称性：,点1有环，所以不具自反性 ,2.反自反性：,没有出现双边，具反对称性 ,4.反对称性：,5.传递性：,不具传递性 ,关系图法,61,例2：,A=1，2，3，R1=，R2=AA，试判断两关系的性质。,R1：,反自反,对称,反对称,传递,R2：,自反,对称,传递,R2=(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3),62,例题,设R1,R2为A上的对称关系，证明R1R2也是A上的对称关系。,所以(x,y)和(y,x)成对的出现在R1R2中， R1R2是对称关系,思考R1R2是对称的吗？,63,例题,设 为A上的反对称关系，则 不一定是A上的反对称关系。 例如 这里 R1,R2都是A上的反对称关系，但 R1R2 不是A上的反对称关系，却是对称的。思考: R1R2 在A上是否是反对称的? 是反对称的！,64,例5,设R是集合A上的二元关系，如果RR2，证明R是传递关系。证明 当存在(a, b)R，(b, c) R时，由复合关系的定义可知，必有(a,c)R2 ，而RR2 ，所以(a, c) R，由此证得R是传递关系。证毕。,练习,65,4-3 关系的闭包运算,1.自反闭包、对称闭包、传递闭包的定义定义： R是A上的二元关系，若A上二元关系 R满足（1）R是自反的（对称的，传递的）（2）R R（3）对于任何自反的（对称的，传递的）二元关系R如果 R R，则有R R则称R为R的自反闭包（对称闭包，传递闭包）。,66,关系上的闭包运算,由上述定义可知，R的自反闭包（对称闭包，传递闭包） R：是含有R并且具有自反性质（对称性质，传递性质）的“最小”的二元关系。通常把二元关系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，并且自反，并且元素个数最少,67,关系的闭包运算分析,求R的自反闭包比较简单，只需把所有(a, a) R 的有序对补上即可。求R的对称闭包也比较简单，每当(a, b)R，而(b, a) R 时，把有序偶(b, a)添加到R上即得。,68,关系的闭包运算分析,求二元关系的传递闭包并不是一件容易的事情。例如：A = a, b, c, d,R = (a, b), (b, c), (c, d)。易见:R不是传递关系，在R中有:(a, b)R和(b, c) R，但(a, c) R (b, c) R和(c, d) R，但(b, d) R,如果把有序对(a, c)和(b, d)添加到R中去，使之扩充为R1，,所以R1仍然不是传递关系，也即R1不是R的传递闭包。,R1= (a, b), (b, c), (c, d), (a, c), (b, d),但是，由于(a, c)R1和(c, d) R1,而(a, d) R1，,69,总结：求闭包的算法,设R为A上的关系，则有,70,总结：求闭包的算法,证明（3）先证：,根据数学归纳法：1)根据闭包的定义，Rt(R)，所以n=1时R1t(R)成立2) 首先假设当n1时， Rnt(R)成立，则再看看任意(x,y) Rn+1时，(x,y)是否也属于t(R)。因为： Rn+1 =Rn R，根据复合关系的定义，必存在(x,c) Rn, (c,y) R, 才能满足复合关系。因此 又可以得到(x,c) t(R)， (c,y) t(R), 根据传递闭包的定义，(x,y) t(R). 根据包含的定义，所以Rn+1t(R)3) 所以:,71,总结：求闭包的算法,再证：,1) 假设(x,y) , (y,z) 必存在(x,y) Rs，(y,z)Rt, 因此：(x,z) RsRt =Rs+t,所以(x,z) 所以对于关系 来说，它是传递的。包含R的传递关系都包含了t(R)，所以两个集合互相包含，只能说明两者相等，所以,72,总结：求闭包的算法,可以证明，当A为有限集：,73,求闭包的例子：,例1：设A = a, b, c, d，A上的关系 R = (a, b), (b, a), (b, c), (c, d) 求r(R)、s(R)、t(R),74,例1（续）,R = (a, b), (b, a), (b, c), (c, d),75,关系矩阵下 闭包的构造方法,设关系R, r(R), s(R), t(R)的关系矩阵分别为M, Mr, Ms 和 Mt , 则 Mr = M + E Ms = M + M T Mt = M + M2 + M3 + E 是和 M 同阶的单位矩阵, MT是 M 的转置矩阵. 注意在上述等式中矩阵的元素相加时使用逻辑加.,76,例：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),77,例：A=a,b,c, R=(a,b),(b,c),(c,a)求r(R), S(R)和t(R) (续1),s(R)=M+MT=,s(R)=(a,b),(b,c),(c,a),(a,c),(b,a),(c,b),78,例：A=a,b,c, R=(a,b),(b,c),(c,a)求r(R), S(R)和t(R) (续2),t(R)=M+M2+M3=,s(R)=(a,b),(b,c),(c,a),(a,c),(b,a),(c,b),(a,a),(b,b),(c,c),M,M2,M3,79,关系图下 闭包的构造方法,设关系R, r(R), s(R), t(R)的关系图分别记为G, Gr, Gs, Gt , 则Gr, Gs, Gt 的顶点集与G 的顶点集相等. 除了G 的边以外, 以下述方法添加新边：,3.考察G的每个顶点 xi, 找从 xi 出发的每一条路径，如果从 xi 到xj存在路径，但没有边，就加上这条边. 当检查完所有的顶点后就得到图Gt .,1.考察G的每个顶点, 如果没有环就加上一个环，最终得到Gr .,2.考察G的每条边, 如果有一条 xi 到 xj 的单向边, ij, 则在G中加一条 xj 到 xi 的反方向边，最终得到Gs.,80,实例,例1 设A=a,b,c,d, R=, R和 r(R), s(R), t(R)的关系图如下图所示.,R,r(R),s(R),t(R),练习,81,求传递闭包的算法,Warshall算法: (1）置新矩阵 是关系矩阵）（2）置 j = 1，i=1（3）对所有 i，如果 ，则对k = 1, 2, , n ，置 (4) j = j + 1（5）如果j n ，则转到步骤（3），否则停止。,82,例题：求传递闭包,设求R的传递闭包。解 利用Warshall算法，求解步骤如下。先写出R的关系矩阵,83,例题：求传递闭包,84,用程序实现算法：,#include stdafx.h#include int main(int argc, char* argv)int R55=0,1,0,0,0, 0,0,1,0,0, 1,0,0,0,0, 0,0,0,0,1, 0,0,0,1,0;int tR55;for(int i=0;i5;i+) /copy R to tR for(int j=0;j5;j+)tRij=Rij;,85,for(int j=0;j5;j+)for(int i=0;i5;i+)if(tRij=1)for(int k=0;k5;k+)tRik=tRik|tRjk;/ print for(int a=0;a5;a+)for(int b=0;b5;b+)couttRab ;coutendl;coutendl;,86,4-4 等价关系和相容关系,集合的覆盖与划分1.覆盖给定非空集合S，有非空集合A=A1, A2, Am。若AiS，Ai空集(i=1,2,m)且 则称集合A为集合S的覆盖。,87,等价关系,例如：S=a,b,cA=a,b,a,cB=a,a,c,bC=a,a,cA、B是S的覆盖C不是S的覆盖,88,等价关系,2.划分：给定非空集合S，有非空集合A=A1, A2, Am。若AiS，Ai空集(i=1,2,m)且 ，还有AiAj=空集，则称集合A为集合S的划分。,89,等价关系,例如：S=a,b,cA=a,b,a,cB=a,c,bC=a,b,cD=a,b,cA是S的覆盖,但不是划分B、C、D是S的划分。,90,例题,例1 设Aa, b, c, d, 给定1,2,3,4,5,6如下： 1= a, b, c, d ， 2= a, b, c, d 3= a, a, b, c, d , 4= a, b, c 5= ,a, b, c, d , 6= a, a, b, c, d 则1和2 是A的划分, 其他都不是 A 的划分. 为什么？,91,等价关系的定义与实例,定义 设 R 为非空集合上的关系. 如果 R 是自反的、对称的和传递的, 则称 R 为 A 上的等价关系. 设 R 是一个等价关系, 若(x,y)R, 称 x 等价于y, 记做 xy.实例 设 A=1,2,8, 如下定义A上的关系 R： R = (x,y) | x,yAxy(mod 3) 其中 xy(mod 3) 叫做 x 与 y 模3相等, 即 x 除以3的余数与 y 除以3的余数相等.,92,等价关系的验证,验证模 3 相等关系 R 为 A上的等价关系, 因为 xA, 有x x(mod 3) x, yA, 若 x y(mod 3), 则有 y x(mod 3) x, y, zA, 若x y(mod 3), y z(mod 3), 则有 xz(mod 3)自反性、对称性、传递性得到验证,93,A上模3等价关系的关系图,设 A=1,2,8, R= | x,yAxy(mod 3) ,94,等价关系的验证,例：所有三角形间的相似关系是等价关系。证：1）三角形A与它自己相似，满足自反性。2）三角形A与B相似，则可以反过来说B与A相似，满足对称性。3）三角形A与B相似，B与C相似，则可推断出A与C相似，满足传递性。所以：所有三角形间的相似关系是等价关系,95,思考题,A=1,2,3,4R=(1,1),(1,2),(1,4),(2,1),(2,2),(3,3),(4,1),(4,4),判断R是否是等价的。,自反,对称,不传递,所以不是等价关系,96,思考题,R是整数Z上的关系R=(a,b)|aZ, bZ,a=b a=-b求证R是等价关系,97,等价类,定义 设R为非空集合A上的等价关系, xA，令xR = y | yAxRy 称 xR 为 x 关于R 的等价类, 简称为 x 的等价类, 简记为x. 实例 A= 1, 2, , 8 上模 3 等价关系的等价类： 1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,6,98,等价类的性质,定理1 设R是非空集合A上的等价关系, 则 (1) xA, x 是A的非空子集. (2) x, yA, 如果 x R y, 则 x=y. (3) x, yA, 如果 x y, 则 x与y不交. (4) x | xA=A，即所有等价类的并集就是A. (5)A中每个元素必属于某个等价类。,99,实例,A= 1, 2, , 8 上模 3 等价关系的等价类： 1=4=7=1,4,7， 2=5=8=2,5,8， 3=6=3,6 以上3 类两两不交， 1,4,72,5,83,6 = 1,2, ,8,100,商集,定义 设R为非空集合A上的等价关系, 以R的所有等价类作为元素的集合称为A关于R的商集, 记做A/R, A/R = xR | xA 实例 A=1,2,8，A关于模3等价关系R的商集为 A/R = 1,4,7, 2,5,8, 3,6 A关于恒等关系和全域关系的商集为： A/IA = 1,2, ,8 A/EA = 1, 2, ,8 ,101,等价关系与划分的一一对应,商集 A/R 就是 A 的一个划分 不同的商集对应于不同的划分,例： 给出A1,2,3上所有的等价关系,任给 A 的一个划分, 如下定义 A 上的关系 R： R = | x,yAx 与 y 在的同一划分块中则 R 为 A上的等价关系, 且该等价关系确定的商集就是.,求解思路：先求出A的所有划分, 然后根据划分写出对应的等价关系.,102,等价关系与划分之间的对应,1,2和3分别对应等价关系 R1, R2 和 R3. R1=,IA，R2=,IA R3=,IA,4 对应于全域关系 EA，5 对应于恒等关系 IA,103,练习：,1.判断下列关系是否为等价关系？(1)A=a,b,c,dR=(a,a),(b,a),(b,b),(c,c),(d,d),(d,c)(2)A=1,2,3,4R=(1,1),(1,2),(1,3),(2,1),(2,2),(3,1),(2,3),(3,3),(4,4),(3,2),(5,5),答案：(1)不是 （b，a)无(a,b) ,对成性不满足,(2)是,104,练习：,2. A=1,2,3,4,在幂集P(A)上定义二元关系如下：R=(S,T)|S,TP(A),|S|=|T|,写出商集P(A)/R,105,2. A=1,2,3,4,在幂集P(A)上定义二元关系如下：R=(S,T)|S,TP(A),|S|=|T|,写出商集P(A)/R,首先P(A)=?,P(A)=,1,2,3,4,1,21,3,1,4,2,3,2,4,3,4,1,2,3,1,2,4,1,3,4,2,3,4,1,2,3,4 16个元素！,R关系：P(A)中每个元素，作为集合，元素个数相同的作为一个等价类。,共5个等价类：,（1）,（2）1=1,2,3,4,（3）1,2=1,21,3,1,4,2,3,2,4,3,4,（4）1,2,3=1,2,3,1,2,4,1,3,4,2,3,4,（5）1,2,3,4=1,2,3,4,P(A)=,1,1,2, 1,2,3,1,2,3,4,106,相容关系,定义1：给定集合A上的关系r，若r是自反的，对称的，则称r是相容关系。,所以：等价关系一定是相容关系 相容关系不一定是等价关系,107,相容关系,定义2：设是R集合A上的相容关系，若C A，如果对于C中任意两个元素a1,a2有a1Ra2，称C是相容关系R产生的相容类。,108,例1：,设集合X=2166，243，375，648，455X中的关系R为：R=(x,y)|x,yX，并且x和y中有相同数字检验它的自反性：xRx成立检验它的对称性：xRy成立，自然也yRx成立检验它的传递性：x1= 2166, x2= 243, x3= 375(x1, x2)R, (x2, x3)R, 但是(x1, x3)R,不满足传递性所以是一个相容关系！,109,相容关系,上述例子对应的关系矩阵：由于相容关系是自反、对称，所以考察矩阵，可以发现对角线元素都为1，并且是对称矩阵。,110,相容关系,所以可以把关系矩阵简化表示：去掉对角线及其以上的元素！,111,相容关系,在关系图上：由于相容关系是自反的和对称的，所以每个节点必定有环，两个节点出现边的话，一定是成对出现。所以进行简化：去掉环，把一对有向边变换成一根线段，没有方向。上面例子对应的简化关系图：,x1,x2,x3,x4,x5,112,相容关系,设R是集合A上的相容关系，不能真包含在任何其它相容类中的相容类，称作最大相容类。记作Cr。,113,偏序关系,定义 非空集合A上的自反、反对称和传递的关系，称为A上的偏序关系. 实例 集合A上的恒等关系 IA 是A上的偏序关系. 小于等于关系, 整除关系和包含关系也是相应集合上的偏序关系.,114,偏序关系的定义,常常把集合A以及A上的偏序关系R合在一起统称为偏序集，记作（A，R）。由于偏序关系是自反的、反对称的、传递的二元关系，所以一般用符号“”表示偏序。当(a, b)R，时，常记作ab，偏序集也常记作（A，）。,115,线性次序,定义 设R是集合A上的偏序，如果对每个x,yA，必有xy或y x ，则称R是线性次序的(全序的)，或称R是集合A上的线性次序关系。易知：在线性次序关系中，任意两个元素都是有关系的。,116,线性次序,例在整数集合中，大于等于关系是线性序关系。例设1,3,6,12,24, 是整除关系 ,则是线性次序的,并且对A中元素有 1 3 6 12 24,117,线性次序,例3：集合1，2，4，8，1，3，6，1，3，9，27，1，5，10，20上的整除关系都是线性次序的。,118,线性次序,查字典，英文单词也有顺序，例如boy在book后面，我们把这种顺序叫做字典顺序。字典顺序也是一个偏序关系，由所有单词构成的集合，按照字典顺序排列，也是一个线性次序。,119,偏序关系的哈斯图表示,定义 设R是集合A上的偏序关系，a和b是A中的元素，如果(a, b) R，且在A中没有其他元素c，使得 (a, c) R，(c, b) R，则称元素b盖住a。例1:A = 1，2，3，4，5，6，8，10，12，16，24，R是A上的整除关系，由“盖住”的定义可知，元素4盖住2；但元素8并不盖住2，因为有元素4，使得(2, 4)R和(4, 8)R，所以8不盖住2。利用元素间的盖住关系，能较方便地画出偏序关系的哈斯图(即关系图的简化),120,画哈斯图的方法,用平面上的点代表集合中的元素，当b盖住a时，代表b的点应