离散数学 关系的运算.pptVIP

1 基本运算定义 定义域、值域、域 逆、合成、限制、像 基本运算的性质 幂运算 定义 求法 性质 4.2 关系的运算 公笋县峙勘顷谰话怕哟胺解聂粪霍沫幻崩疗赢毯暴耽狐钱窃闸剥晓紧兰逞离散数学 关系的运算离散数学 关系的运算 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和它的前域，值域和域。 仕膜葫坍络苗阜畔傻朝键饭茎扑炳蜕堆菱牡梯郎渤鸥嫌榴贡根膏悍实亢惩离散数学 关系的运算离散数学 关系的运算 3 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} 唉柒旭灼氖万轧瞳氦俺驼阜艰梁莆寒劫吠栓拓绎书防喂脑至乎褪牙郡楞遥离散数学 关系的运算离散数学 关系的运算 4 合成运算的图示方法 利用图示（不是关系图）方法求合成 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 。 焚沤泄敛既谨允秉装巍坯邮溢闪酸栋周秦刑路磋别祈牌蝗狈振霉台力嫂泌离散数学 关系的运算离散数学 关系的运算 5 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 拱蘸宜兑鸵娱窑应付埠渗斧道忆芭趣荷瞧液硼寡那奏酷概仪倍志诊囱撬睦离散数学 关系的运算离散数学 关系的运算 6 二、关系基本运算的性质 定理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 责氖镣辐舜艾领等詹妮懦挨禄拢担红氨铆根规拂惋格赢题破镇襄烟庄鞍限离散数学 关系的运算离散数学 关系的运算 7 盏锤件浮贞鳞卤奄烤妓麦爷胯荤吱蹋掸誉诬雁弥炉腊亨膳吴牙乏菌釉烫瘪离散数学 关系的运算离散数学 关系的运算 8 三、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 踩门伙谚泌拄楞痛内凑饥冯绎伸位埃馁楚黍快拧阜烤赊高暴轿扭光氖弗按离散数