(1.5.8)--ch3—第四讲离散数学离散数学.pdf
离离 散散 数数 学学 Discrete MathematicsDiscrete Mathematics 3-7 关系的运算关系的运算 一、一、复合关系复合关系(Compound Relations)定义定义3.7.1 设设 R 是由是由X 到到Y 的关系的关系,S 是由是由Y 到到Z 的关系的关系,则则 R S 称为称为R 和和 S 复合关系复合关系,表示为表示为 R S=|x Xz Z(y)(y YxRyySz)两个关系的合成运算可以推广到多个两个关系的合成运算可以推广到多个.例如例如:R S P、R S P Q 等等.且合且合成成运算满足结合律运算满足结合律.即即:(P R)Q=P(R Q)关系关系R自身合成自身合成n次可以记为次可以记为:R R R=R(n)(1)R0=IA 即即R0是是A上的恒等关系上的恒等关系.(2)R(n+1)=R(n)R 规定规定:(R的的n次次幂幂)例例1.设设R1 ,R2是集合是集合X=0,1,2,3 上的关系上的关系,有有 解解.,R2=|i=j+2 R1=|j=i+1或或 12ji 求求:R1 R2,R2 R1,R1 R1,R1 R2 R1,R1 R1 R1.R1=,R2=,R1 R2=,R2 R1=,R1 R2 R1=,R1 R1=,R1 R1 R1=,练习练习 令令R=,S=,求求 R S，S R，R R，S S,R(S R),(R S)R.解解 S R R R S S R S=,=,=,R(S R)=(R S)R=复合关系的关系矩阵复合关系的关系矩阵 定理定理 设设 A、B、C均是有限集均是有限集,R是由是由A到到B的关系的关系,S是由是由B 到到C的关系的关系,它们的关系矩阵分别为它们的关系矩阵分别为MR和和MS,则复合关系则复合关系R S 的关系矩阵的关系矩阵MR S 满足满足:MR S=MR MS 其中其中 MR=(rij),MS=(sij),MR S=MR Ms=(wij)且且 nijikkjkwrs1()式中式中代表代表逻辑乘逻辑乘,满足满足 00=0,01=0,10=0,11=1.代表代表逻辑加逻辑加,满足满足 00=0,01=1,10=1,11=1.例例4.设集合设集合A=1,2,3,4,B=2,3,4,C=1,2,3 A到到B的关系的关系R=,B到到C的关系的关系S=,求求 R S 的矩阵的矩阵.R SRSMMM 解解 100100001010010101100 1 0 0 1 0 1 0 1 0 1 0 0 1 2 3 4 1 2 3 R S=,练习练习.设有集合设有集合A=a,b,c,d,R为为A上的关系上的关系 R=,求求 R R的矩阵的矩阵.R RRRMMM 解解 01000100101010100011001100000000 1010011100110000 定义定义3.7.2 设设R是由集合是由集合 X 到到Y的二元关系的二元关系,若将若将R中每一有序中每一有序 二、二、逆关系逆关系(Inverse Relations)对的元素顺序互换对的元素顺序互换,所得到的集合称为所得到的集合称为R 的的逆关系逆关系,记作记作Rc,即即 Rc=|R 例例.设有集合设有集合A=a,b,c,d,R为为A上的关系上的关系 R=,则则Rc=,定理定理3.7.1 定理定理3.7.2 设设T为从集合为从集合X到到Y的关系的关系,S为从为从Y 到到Z 的关系的关系,则则 (T S)c=Sc Tc 定理定理3-7.3 设设R为为X上的二元关系上的二元关系,则则 R是是对称的对称的,当且仅当当且仅当R=Rc R是是反对称的反对称的,当且仅当当且仅当RRc IX R是是传递的传递的,当且仅当当且仅当R R R ccRRRA BR(Rc)c=R (RS)c=RcSc (RS)c=RcSc (RS)c=SR (R-S)c=Rc-Sc 例例.设集合设集合A=1,2,3,4,R为为A上的关系上的关系,求求MRc及及MR 其中其中 R=,解解 Rc=,MR =MRc=110000110010011234001 2 3 4 100010010110011234001 2 3 4 Rc的关系矩阵及关系图的关系矩阵及关系图 Rc的关系矩阵及关系图的关系矩阵及关系图 Rc的关系矩阵的关系矩阵MRc与与R的关系矩阵的关系矩阵MR满足满足:Rc的关系图只需将的关系图只需将R的关系图中的有向弧改向即得的关系图中的有向弧改向即得.MRc=(MR)T 101110111RM 求求,.CCRR RMMo o解解:111011,101CRM CR RM101110110011111101 例例6 给定集合给定集合 X=a,b,c,X上的二元关系上的二元关系R的关系矩阵为的关系矩阵为 111111111 三、关系的闭包运算三、关系的闭包运算(Closure Operations)定义定义3.8.1 设非空集合设非空集合A上的二元关系上的二元关系R,若有若有A 上的另一个上的另一个 是自反的是自反的(对称的对称的,传递的传递的);R RR RR 则称关系则称关系 为为R的的自反自反(对称的对称的,传递的传递的)闭包闭包.R 分别记作分别记作:r(R),s(R),t(R).R 满足满足:二元二元关系关系 (1)(2)(3)对对A上任何包含上任何包含R的自反的自反(对称的对称的,传递的传递的)关系关系 R 都有都有 从上述定义可以看出从上述定义可以看出,R 的自反的自反(对称对称,传递传递)闭包是包含闭包是包含 R并具有自反并具有自反(对称对称,传递传递)性质的性质的最小关系最小关系.定理定理3.8.1 设设R是集合是集合X上的二元关系上的二元关系,则则 R自反自反 r(R)=R R对称对称 s(R)=R R传递传递 t(R)=R 定理定理3.8.2 设设 R 是集合是集合 X 上的二元关系上的二元关系,IX 是集合是集合X上上 的恒等关系的恒等关系,则则 r(R)=RIX 定理定理3.8.3 设设 R 是集合是集合 X 上的二元关系上的二元关系,则则 s(R)=RRc 定理定理3.8.4 设设 R 是集合是集合 X 上的二元关系上的二元关系,则则 iit RRRRRR23+1()=例例1.设设A=a,b,c,R为为A上的二元关系上的二元关系,且且 解解:r(R)=RIA =,s(R)=RRc=,试求试求r(R),s(R)和和t(R).R=,R2=R R=,R3=R2 R=,iit RR1()R2=R R=,R3=R2 R=,=RR2R3=,R4=R3 R=,=R R5=R4 R=,=R2 R6=R5 R=,=R3 iit RR1()定理定理3.8.5 设设A是含有是含有n个元素的集合个元素的集合,R是是 A上的二元关系上的二元关系,则存在一个正整数则存在一个正整数kn，使得，使得 t(R)=RR2R3Rk 例例2.设设A=a,b,c,d,R为为A上的二元关系上的二元关系,且且 试求试求t(R).R=,解解:因为因为|A|=4,所以所以k4.R2=R R=,R3=R2 R=,=,t(R)=RR2R3 R4 R4=R3 R=,R=,R2=R R=,R3=R2 R=,利用关系矩阵求关系的闭包利用关系矩阵求关系的闭包 r(R)=RIX s(R)=RRc t(R)=RR2R3Rk 相应的关系矩阵有相应的关系矩阵有 Xr RRIMME()cTs RRRRRMMMMM()kt RRRRMMMM2()其中其中代表代表逻辑加逻辑加 例例7 设设 A=a,b,c,d,R=,求求 t(R).0100101000010000RM RM2010001001010101010100101000100010000000000000000 解解 RM3101001000101010110101010000000010000000000000000 RM4010101001010101010100101000000010000000000000000 t RRRRRMMMMM234()t(R)=,1111111100010000(1)置新矩阵置新矩阵 A:=M(4)i加加1;(5)如果如果in,则转到步骤则转到步骤(3),否则停止否则停止.当有限集当有限集 X 的元素较多时的元素较多时,对关系对关系R的传递闭包进行的传递闭包进行 矩阵运算很繁琐矩阵运算很繁琐,Warshall(沃舍尔沃舍尔)在在1962年提出了年提出了R+的的 一个有效算法一个有效算法:(2)置置 i:=1 则对则对k=1,2,n(3)对所有对所有 j,如果如果 A j,i=1;A j,k:=A j,k +A i,k )()().a rs Rsr R 定理定理3-8.6 设设R是集合是集合X上的二元关系，则上的二元关系，则 )()().b rt Rtr R)()().c ts Rst R 自反性自反性 反自反性反自反性 对称性对称性 反对称性反对称性 传递性传递性 Rc R1R2 R1R2 R1-R2 R1 R2 原有性质原有性质 运算运算 关系在各种运算下保持原有特性问题关系在各种运算下保持原有特性问题
