离散数学关系的运算.ppt

* 基本运算定义 定义域、值域、域 逆、合成、限制、像 基本运算的性质 幂运算 定义 求法 性质 4.2 关系的运算 * 一、关系的基本运算定义 1、定义域、值域 和 域 定义 设R是二元关系，由（x,y）∈R 的所有x 组成的集合 称为 R的前域，记为domR。即domR = { x | ?y (x,y?R) }。 使（x,y）∈R 的所有y组成的集合称为R的值域，记为ranR。 即ranR = { y | ?x (x,y?R) }。称domR ? ranR为R的域，记 为fldR 。即fldR = domR ? ranR 。 解：根据题意R1 ={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)} 故前域dom R1 ={1,2,3}, 值域 ran R1 ={2,3,4}， fldR ={1,2,3,4}。 例1 设A={1，2，3，4}， R1是A上的二元关系，当a,b∈ A， 且ab 时， (a,b) ∈ R1 , 求R和它的前域，值域和域。 * 2、逆与合成 R?1 = {y,x | x,y?R} R°S = |x,z | ? y (x,y?R?y,z?S) } 例2 已知 R={1,2, 1,4, 2,2，2,3, }， S={1,1, 1,3, 2,3, 3,2, 3,3}， 求R?1， R°S ， S°R 。 解：R?1={2,1, 3,2, 4,1, 2,2} R°S ={1,3, 2,2, 2,3} S°R ={1,2, 1,4, 3,2, 3,3} * 合成运算的图示方法 利用图示（不是关系图）方法求合成 R°S ={1,3, 2,2, 2,3} S°R ={1,2, 1,4, 3,2, 3,3} 例2 已知 R={1,2, 1,4, 2,2，2,3, }， S={1,1, 1,3, 2,3, 3,2, 3,3}， 求R?1， R°S ， S°R 。 * 3、限制与像 定义 F 在A上的限制 F?A = {x,y | xFy ? x?A} A 在F下的像 F[A] = ran(F?A) 例3 设 R={1,2, 2,3, 1,4, 2,2} ，则 R?{1}={1,2,1,4} R[{1}]={2,4} R??=? R[{1,2}]={2,3,4} 注意：F?A?F, F[A] ?ranF * 二、关系基本运算的性质 定理1 设F是任意的关系, 则 (1) (F?1)?1=F (2) domF?1=ranF, ranF?1=domF 定理2 设F, G, H是任意的关系, 则 (1) (F°G)°H=F°(G°H) (2) (F°G)?1= G?1°F?1 * 定理　设R, S, T均为A上二元关系， 那么 （1） Rο (S∪T)=(Rο S)∪(Rο T) （2） (S∪T)ο R=(Sο R)∪(Tο R) （3） Rο (S∩T)(Rο S)∩(Rο T) （4） (S∩T)ο R(Sο R)∩(Tο R) （5） Rο (Sο T)=(Rο S)ο T * 三、A上关系的幂运算 设R为A上的关系, n为自然数, 则 R 的 n次幂定义为： (1) R0={x,x | x∈A }=IA (2) Rn+1 = Rn°R 注意： 对于A上的任何关系R1和R2都有 R10 = R20 = IA  对于A上的任何关系 R 都有 R1 = R * 例： * 定理 设 R 是 A 上的关系, m, n∈N, 则 (1) Rm°Rn=Rm+n (2) (Rm)n=Rmn 四、幂运算的性质 * 关系运算的矩阵表示 关系矩阵（matrix of relation）。 设R　　A×B， A=｛a1, a2, …, am｝, B=｛b1, b2, …, bn｝， 那么R的关系矩阵 MR为一m×n矩阵，它的第i , j分量rij只取值0或1， 而 当且仅当aiRbj 当且仅当 * 某关系R的关