2.3 关系的运算

第二章1第三节关系的运算第二章2一.逆关系关系是一种特殊的集合(其元素为有序对)。那么，集合的性质和运算能够满足.例如，RA×B(1)R的补集R′=（A×B）-R；(2)(a,b)∈R′(a,b)∈R;(3)(a,b)∈R1∪R2,则(a,b)∈R1或(a,b)∈R2；(4)(a,b)∈R1∩R2,则(a,b)∈R1且(a,b)∈R2.第二章3定义1设R为二元关系,把R的逆关系(ConverseRelation)简称R的逆,记作R-1,其中R-1={x,y|y,xR}注：逆关系是对调有序对的位置.逆关系的几个重要性质：(1)（R-1）-1=R;(2)若RS,则R-1S-1;(3)(R∪S）-1=R-1∪S-1;(4)(R∩S）-1=R-1∩S-1;第二章4证明：这里只证明(3),利用集合的相等，只需证明(R∪S)-1与R-1∪S-1相互包含。任取(a,b)∈(R∪S）-1，则(b,a)∈(R∪S）,即有(b,a)∈R或(b,a)∈S,由逆关系定义知,(a,b)∈R-1或(a,b)∈S-1,即(a,b)∈R-1∪S-1,故(R∪S)-1R-1∪S-1.同理可证，R-1∪S-1(R∪S)-1,略.故结论成立，证毕.练习，证明(4).第二章5定义2设F,G为二元关系。称为G对F的右复合(或F对G的左复合)。例如,F={3,3,6,2},G={2,3},则G)}yt,Ftx,t(yx,{GF}6,3{GF}2,3{FG二.复合关系第二章6复合关系的重要性质：设A,B,C,D是四个非空集合，R,F,G,H是关系，则;RRIIRΦ;RΦΦR(1)AA;D(S)D(R),Φ)D(R)2((3)满足结合律;H)(GFHG)(F(4)○对∪满足分配律;H)(FG)F(H)G(F;H)(FG)F(H)G(F;FGG)(F(5)111第二章7证明：这里主要证明(3)和(5)(3)(FG)H=F(GH);(5)(FG)–1=G–1F–1.证:(3)∵x,y((FG)H)t(x,t(FG)∧t,yH)t(s(x,sF∧s,tG)∧t,yH)ts(x,sF∧s,tG)∧t,yH)s(x,sF∧t(s,tG∧t,yH))s(x,sF∧s,y(GH))x,yF(GH)∴(FG)H=F(GH)(5)∵x,y(FG)–1y,xFGt(y,tF∧t,xG)t(x,tG–1∧t,yF–1)x,y(G–1F–1)∴(FG)–1=G–1F–1第二章8练习(2)和(4)证:∵x,yF(G∩H)t(x,tF∧t,y(G∩H))t(x,tF∧t,yG∧t,yH)t((x,tF∧t,yG)∧(x,tF∧t,yH))t(x,tF∧t,yG)∧t(x,tF∧t,yH)x,yFG∧x,yFHx,yFG∩FH∴F(G∩H)=FG∩FH;H)(FG)F(H)G(F第二章9定义1设R是A上的关系,n为自然数,则R的n次幂定义为:(1)R0={x,x|xA}=IA;(2)注:1.对A上的任何关系R,都有R0=IA,R1=R。2.Rn的求法:除了根据定义按关系的复合来求之外,还可以用矩阵法和关系图法。RRRn1n三.关系的复合幂与闭包第二章10定理设R为A上的关系,m,nN,则(1)RmRn=Rm+n;(2)(Rm)n=Rmn证:(1)对于任意取定的mN，关于n作数学归纳法。当n=0时，RmR0=RmIA=Rm=Rm+0假设RmRn=Rm+n,则RmRn+1=Rm(RnR)=(RmRn)R=Rm+nR1=Rm+n+1由归纳法原理,知命题成立。(2)对任意取定的mN,关于n作数学归纳法。当n=0时,(Rm)0=IA=R0=Rm·0假设(Rm)n=Rmn,则(Rm)n+1=(Rm)nRm=RmnRm=Rmn+m=Rm(n+1)由归纳法原理,知命题成立。第二章11定义2设A是非空集合，R是A上的关系，则称为R+关系R的包,R*关系R的星包.,RR1kk注：(1)(a,b)∈R+,表明k(k≥1∧(a,b)∈Rk)即当a与b有关系R+时，则a与b总有有穷阶的间接关系.A*IRR第二章12定理2设R为A上的关系,若存在自然数s,t(st),使得Rs=Rt,则(1)kN都有Rs+k=Rt+k(2)k,iN都有Rs+kp+i=Rs+i,其中p=t–s(3)令S={R0,R1,…Rt–1},则对qN都有RqS。证明略。注:(1)有穷集A上的关系R的幂序列R0,R1,R1,R2,...是一个周期性变化的序列.(2)利用该周期性可将R的高次幂化简为R的低次幂.第二章13例设A={a,b,c,d,e,f},R={a,b,b,a,d,e,e,f,f,d},求出自然数m和n(mn),使得:Rm=Rn.解:由R的定义可以看出A中的元素可分成两组,即:{a,b}和{d,e,f}.它们在R的右复合运算下有下述变化规律:abab...defdef...对于a和b,它们的变化周期是2;对于d,e,f,它们的变化周期是3,因此,一定有:Rm=Rm+6,其中6是2和3的最小公倍数.第二章141.补四.关系的矩阵表示},a,,a,{aAm21},b,,b,{bBn21BAR,nmijR)(xM关系矩阵.)(yMMMnmij1RR则这里：（1）M1是元素全为1的矩阵。.(2)表示布尔异或1.xy(3)ijij第二章152.并，交四.关系的矩阵表示},a,,a,{aAm21},b,,b,{bBn21BARR21,,)(xM,)(xMnm(2)ijRnm(1)ijR21关系矩阵,)(xMMMnmijRRRR2121则这里：.xxy;xxx(2)(2)ij(1)ijij(2)ij(1)ijij.(1)表示布尔加和布尔乘和.)(yMMMnmijRRRR2121第二章163.逆TRRMM1-关系矩阵4.复合借助矩阵乘法，对应修改:(1)加法—布尔加(2)乘法—布尔乘第二章17例},c,c,c,{cC},b,{bB},a,a,{aA432121321B,AR)},(),,(),,{(132211bababaC,BS)},(),,(),,{(322241cbcbcb则,011001MR,01101000MS.100001101000MMMSRSRC.ASR)},(),,(),,(),,{(43322241cacacaca第二章18作业：P5113,14