离散数学关系的运算.ppt

1,基本运算定义 定义域、值域、域 逆、合成、限制、像 基本运算的性质 幂运算 定义 求法 性质,4.2 关系的运算,2,一、关系的基本运算定义,1、定义域、值域 和 域,定义 设R是二元关系，由（x,y）R 的所有x 组成的集合 称为 R的前域，记为domR。即domR = x | y (R) 。 使（x,y）R 的所有y组成的集合称为R的值域，记为ranR。 即ranR = y | x (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和它的前域，值域和域。,3,2、逆与合成 R1 = | R RS = | | y (RS) ,例2 已知 R=, , ，, ， S=, , , , ， 求R1， RS ， SR 。,解：R1=, , , ,RS =, , ,SR =, , , ,4,合成运算的图示方法,利用图示（不是关系图）方法求合成 RS =, , SR =, , , ,例2 已知 R=, , ，, ， S=, , , , ， 求R1， RS ， SR 。,5,3、限制与像,定义 F 在A上的限制 FA = | xFy xA A 在F下的像 FA = ran(FA),例3 设 R=, , , ，则 R1=, R1=2,4 R= R1,2=2,3,4 注意：FAF, FA ranF,6,二、关系基本运算的性质,定理1 设F是任意的关系, 则 (1) (F1)1=F (2) domF1=ranF, ranF1=domF,定理2 设F, G, H是任意的关系, 则 (1) (FG)H=F(GH) (2) (FG)1= G1F1,7,定理 设R, S, T均为A上二元关系， 那么 （1） R (ST)=(R S)(R T) （2） (ST) R=(S R)(T R) （3） R (ST)(R S)(R T) （4） (ST) R(S R)(T R) （5） R (S T)=(R S) T,8,三、A上关系的幂运算,设R为A上的关系, n为自然数, 则 R 的 n次幂定义为： (1) R0= | xA =IA (2) Rn+1 = RnR 注意： 对于A上的任何关系R1和R2都有 R10 = R20 = IA 对于A上的任何关系 R 都有 R1 = R,9,例：,10,定理 设 R 是 A 上的关系, m, nN, 则 (1) RmRn=Rm+n (2) (Rm)n=Rmn,四、幂运算的性质,11,关系运算的矩阵表示 关系矩阵（matrix of relation）。 设R AB， A=a1, a2, , am, B=b1, b2, , bn， 那么R的关系矩阵 MR为一mn矩阵，它的第i , j分量rij只取值0或1， 而,当且仅当aiRbj,当且仅当,12,某关系R的关系图为：,则R的关系矩阵为：,13,思考： 写出集合A=1 , 2 , 3 , 4 上的恒等关系、 空关系、 全域关系和小于关系的关系矩阵。,答案：分别为：,14,在讨论关系矩阵运算前, 我们先定义布尔运算, 它只涉及数字0和1。 布尔加法（ ）： 0 + 0 = 0 0 + 1 = 1 + 0 = 1 + 1 = 1 布尔乘法（ ）： 1 1 = 1 0 1 = 1 0 = 0 0 = 0,15,R0, R1, R2, R3,的关系图如下图所示,五、幂的求法,例3 设A=a,b,c,d, R=, 求R的各次幂, 分别用矩阵和关系图表示. 解 R与R2的关系矩阵分别为,16,幂的求法（续）,对于集合表示的关系R，计算 Rn 就是n个R右复合 . 矩阵表示就是n个矩阵相乘, 其中相加采用逻辑加. 例3 设A=a,b,c,d, R=, 求R的各次幂, 分别用矩阵和关系图表示. 解 R与R2的关系矩阵分别为,17,同理，R0=IA, R3和R4的矩阵分别是： 因此M4=M2, 即R4=R2. 因此可以得到 R2=R4=R6=, R3=R5=R7=,幂的求法（续）,18,六、幂运算的性质,定理 设A为n元集, R是A上的关系, 则存在自然数 s 和 t, 使得 Rs = Rt. 证 R为A上的关系, 由于|A|=n, A上的不同关系只有 个. 当列出 R 的各次幂 R0, R1, R2, , , , 必存在自然数 s 和 t 使得 Rs=Rt.,19,定理 设R A A, 若存在自然数s, t (st), 使得Rs = Rt, 则下面等式成立： (1) Rs+q = Rt+q, qN; 证明 Rs+q = RsRq = RtRq = Rt+q。 (2) Rs+(ts)q+r = Rs+r, 其中q, rN; 证明对q用归纳法证明。 当q=1, Rs+(ts)q+r = Rs+(ts)+r = Rt+r = Rs+r (1) 设q = k时, 命题成立, 即Rs+(ts)k+r = Rs+r, 其中q, rN; 当q = k+1时, Rs+(ts)(k+1)+r = Rs+(ts)k+r +(ts) = Rs+(ts)k+r R (ts) = Rs+r Rts (归纳假设) = Rs+r +ts = Rt+r = Rs+r (1) 所以, (2)成立,20,(2) Rs+(ts)q+r = Rs+r, 其中q, rN; (3) 令S = R0, R1, , Rt1, 则对于任意nN, 均有RnS。(ss, 因而存在q, rN, 使得 n s = (t s)q + r (0rt s 1) 即 n = s + (t s)q + r Rn = Rs+(ts)q+r = Rs+r (2) 而s + rs + t s 1= t 1, 所以 Rn = Rs+r S。,21,Rs+(ts)q+r = Rs+r, 例 设R A A, 化简R2003的指数。 (1)已知 R3 = R5； (2) 已知 R7 = R15。 解 (1) s = 3, t = 5, n = 2003, = = 1000,= 1000 1 + 0, 因此, q = 1000, r = 0, R2003 = R3+21000+0 = R3+0 = R3