3.2 关系的合成.ppt

* 南京信息工程大学数学系 南京信息工程大学 离散数学教学组 制作 离 散 数 学 电 子 课 件 * 南京信息工程大学数学系 * 第三章 二元关系 3.1 基本概念 3.2 关系的合成 3.3 关系上的闭包运算 3.4 次序关系 3.5 等价关系和划分 * 南京信息工程大学数学系 * 第3-2讲 关系的合成 1. 关系的合成 2. 关系的幂运算 3. 第3-2讲 作业 * 南京信息工程大学数学系 * 1、关系的合成 关系是序偶的集合，因此可以定义集合运算，由于序偶的特殊性，定义新的运算关系－－合成（复合）运算。 定义1 设R是A到B上的关系，S是B到C的关系，则R?S称为R和S的合成关系，定义为： R?S＝ { x,z? x?A ? z?C ? ?y( y?B ? x,y?R?y,z?S）} * 南京信息工程大学数学系 * 例1 (1) 如果R1是关系“…是……的兄弟”,R2是关系“…是……的父亲”,那么R1R2是关系“…是……的叔伯”.R2R2是关系“…是……的祖父” (2)设A={1,2,3,4,5},R和S都是A上二元关系.如果 R={〈1,2〉,〈3,4〉,〈2,2〉}, S={〈4,2〉,〈2,5〉,〈3,1〉,〈1,3〉} 则 R·S={〈1,5〉,〈3,2〉,〈2,5〉}, S·R ={〈4,2〉,〈3,2〉,〈1,4〉} (R·S)·R={〈3,2〉}, R·(S·R)={〈3,2〉} R·R={〈1,2〉,〈2,2〉},S·S={〈4,5〉,〈3,3〉,〈1,1〉} * 南京信息工程大学数学系 * 例1 (3) A={1,2,3,4},B={2,3,4},C={1,2,3},设R是A到B的关系; S是B到C的关系. R={〈x,y〉｜x+y=6｝； S={〈y,z〉｜y-z=1}， 分别用列举法、图示法和关系矩阵表示RS关系。 解 1)列举法 R={2,4,3,3,4,2} S={2,1,3,2,4,3} 则 RS＝{2,3,3,2,4,1} 2)图示法 * 南京信息工程大学数学系 * 3)关系矩阵 所以 RS＝{2,3,3,2,4,1} * 南京信息工程大学数学系 * 合成关系的矩阵表达 关系的复合运算可以利用关系矩阵求出： 定理： 设 其中 分别是R,S的关系矩阵。 则： 其中矩阵相乘是矩阵的布尔乘运算，即： 式中： ? 表示布尔乘(逻辑加) ? 表示布尔加(逻辑乘) * 南京信息工程大学数学系 * 合成关系的性质 不可交换性：一般有 设R为A到B的关系，IA，IB为A，B上的恒等关系，则 IAR＝RIB＝R 3. 结合律： (RS)T= R(ST) * 南京信息工程大学数学系 * 例2 设R={0,0,0,1,1,2,2,2,2,3} S={2,0,3,1}, T={0,4,1,5} 求 (RS)T， R(ST) 解：(RS)T={1,0,2,0,2,1}T ={1,4,2,4,2,5} R(ST) =R{2,4,3,5} ={1,4,2,4,2,5} 所以 (RS)T= R(ST) 注：如果关系R的值域与关系S的定义域的交集是空集,则合成关系RS是空关系. 如上例中TS是空关系 * 南京信息工程大学数学系 * 分配律：设 则：a. b. c. d. * 南京信息工程大学数学系 * 成立合成在并上的分配律: R1( R2∪R3 )=(R1R2 )∪( R1R3 ) ?a,c??R1(R2∪R3) ? ?b(?a,b??R1∧?b,c??(R2∪R3) ? ?b(?a,b??R1∧(?b,c??R2∨?b,c??R3)) ? ?b(?a,b??R1∧?b,c??R2 ∨?a,b??R1∧?b,c??R3) ? ?a,c??R1R2∨?a,c??R1R3 ? ?a,c??R1R2∪R3R1 * 南京信息工程大学数学系 * 用“幂”表示集合A上同一个关系的乘积，即 定义2 设R为A上的关系，n为自然数，将R的n次 幂记为Rn，规定，R0=IA，则Rn+1＝RnR。 注： Rn一定为A上的关系。 2、关系的幂运算 * 南京信息工程大学数学系 * R1＝R0R＝IAR＝R Rm?Rn=Rm+n， (Rm)n=Rmn ｜A