离散数学-2-3关系的运算[2014-10-8]

1、主讲教师：常亮 E-mail: QQ：737059669 办公室电话: 2291071 手机:辅导教师：周小川 答疑时间：星期四 上午 10:20-11:50 答疑地点：5教5楼 软件工程教研室,离散数学,2.3 关系的运算,基本运算 交、并、补、差、对称差运算 复合运算 逆运算 幂运算 闭包运算,复合运算的矩阵实现,令A、B、C为有限集合，R是A到B的关系，S是B到C的关系，MR和MS分别为R和S的关系矩阵。则，RS的关系矩阵为MRS = MRMS 。 关系矩阵乘法: 按照传统矩阵乘法进行运算，得到初步结果； 将大于等于1的地方修改为1。,复合运算的性质,定理2.3

2、 给定任意集合A、B、C和D， 设R、S和T分别是集合A到B、B到C和C到D的关系， 那么(RS)T = R(ST)。,复合运算满足结合律！,复合运算的性质,定理2.4 对于任意集合A、B、C和D， 设R, S1, S2和T分别是A到B, B到C, B到C和C到D的关系。 那么 ： R(S1 S2) = (RS1) (RS2) R(S1 S2) (RS1) (RS2) (S1S2)T = (S1T) ( S2T) (S1S2)T (S1T) ( S2T),复合对并运算满足分配律！ 复合对交运算不满足分配律！,关系的运算-逆运算,定义2.16 设R是从集合A到集合B的关系， 则R的逆为集合B到集

3、合A的关系，并且 R-1 = | R 。,例2.34,设R = , , , , ， S = , , , , 计算R-1、S-1、(R-1)-1、(S-1)-1、(RS) -1和S-1R-1； 解 根据逆运算和复合运算的定义，有 R-1 = , , , , S-1 = , , , , (R-1)-1 = , , , , (S-1)-1 = , , , , RS = , , , , , (RS) -1= , , , , , S-1R-1 = , , , , , ,逆运算的性质,定理2.5 对于任意集合A和B，设R是集合A到B的关系，则有： (R-1)-1 = R。,逆运算的性质,定理2.6 对于任

4、意集合A、B和C， 设R和S分别是集合A到B和集合B到C的关系，那么 (RS)-1 = S-1R-1。,逆运算的性质,定理2.7 对于任意集合A、B和C， 设R和S分别是集合A到B和集合B到C的关系，那么： (RS) -1 = R-1 S-1 (RS) -1 = R-1 S-1 (RS) -1 = R-1S-1 (R) -1 = (R-1) (AB) -1 = BA R-1 S-1当且仅当R S,对关系性质的判断,幂运算,定义2.17 设R是一个集合A上的关系，n为自然数， 则关系R的n次幂定义为： R0 = | xA = IA Rn+1 = Rn R,例2.35,设集合A = a, b, c

5、, d上的关系 R = , , , 用关系矩阵法求R的各次幂。 解： R0的关系矩阵为： R的关系矩阵为: R2的关系矩阵为：,例,幂运算的性质,定理2.9 设R是集合A上的关系，m和n为自然数，那么 RmRn = Rm+n (Rm)n = Rmn R-n=(R-1)n,幂运算的性质,定理2.8 定理2.10 (略) 如果R是一个有限集合上的关系， 则R0、R1、 R2、R3、R4、R5、R6是一个周期变化的序列。,例2.36,设集合A = a, b, d, e, f上的关系 R = , , , , 求出最小的自然数s和t（st）使得Rs = Rt。 解：关系R的关系矩阵为 那么，R2、R3、

6、R4、R5、R6、R7的关系矩阵分别为：,例,由此，s= 0，t = 6。,关系的闭包运算,问题：如果关系R不具有自反性（对称性、传递性），那么给R增加尽可能少的有序对，使R具有这些性质。 要求： 添加序偶后使得二元关系具有所希望的性质； 添加的序偶最少。,关系的自反闭包,定义2.18 设R和R是集合A上的关系，如果满足： （1）R是自反的； （2）R R； （3）对A上任何包含R的自反关系R都有RR。 则将R称为R的自反闭包，记作r(R)。 即，r(R)是包含R的最小的自反关系 。 例2.37 求集合A=1,2,3上的关系R = , , , 的自反闭包。,关系的对称闭包,定义2.18 设R和

7、R是集合A上的关系，如果满足： （1）R是对称的； （2）R R； （3）对A上任何包含R的自反关系R都有RR。 则将R称为R的对称闭包，记作s(R)。 即，s(R)是包含R的最小的对称关系 。 例2.38 求集合A=1,2,3上的关系R = , , , 的对称闭包。,关系的传递闭包,定义2.18 设R和R是集合A上的关系，如果满足： （1）R是传递的； （2）R R； （3）对A上任何包含R的自反关系R都有RR。 则将R称为R的传递闭包，记作t(R)。 即，t(R)是包含R的最小的传递关系 。 例2.39 求集合A=1,2,3上的关系R = , , , 的传递闭包。,闭包运算的性质,设R是非

8、空集合A上的关系（即A并且RAA），则： (1) R是自反的当且仅当r(R) = R (2) R是对称的当且仅当s(R) = R ； (3) R是传递的当且仅当t(R) = R 。,基于关系图求解闭包,例2.40 设集合A = 1, 2, 3上的关系R = , , , ， 画出关系R及其自反闭包、对称闭包和传递闭包的关系图。 解:关系R及其自反闭包r(R)、对称闭包s(R)和传递闭包t(R)的关系图 求r(R)：对不含自环的顶点添加自环。 求s(R)：如果两个不同的结点之间只有一条边，则在它们之间添加一条相反方向的边。 求t(R)：如果存在结点x指向y的一条边，且存在y指向z的一条边，但没有x

9、指向z的一条边，则添加一条x指向z的边；重复该过程，直到不再需要添加有向边为止。,闭包运算的性质,定理2.11 设R是非空集合A上的关系（即A并且RAA），则： (1) r(R) = RIA (2) s(R) = RR1 (3) t(R) = RR2R3 （注意：从R开始） (4) 如果|A|=n，则 t(R) = RR2Rn (5) 当A为有穷集合时，存在自然数k1使得 t(R) = RR2Rk 用来求闭包！,例2.42,设A=a, b, c, d， R=, , , , , 求r(R), s(R), t(R)。 解: 根据定理2.11可以得到 r(R)= RIA =, , , , , , , s(R)= RR-1=, , , , , , , R2 = , , , , R3 = , , , , R4 = , , , , t(R)= R R2 R3 R4 =, , , , , , , , ,闭包的性质,对闭包再进行闭包运算 rs(R) 、sr(R) rt(R) 、tr(R) st(R)、ts(R) 定理2.12 设R是非空集合A上的关系（即A并且RAA），则： (1) rs(R) = sr(R) (2