1、第三章 集合与关系3-7 复合关系和逆关系讲课人：李朔Email:第1页1一关系复合一关系复合二元关系是以序偶为元素集合，能够进行集合运算，产生新集合，本课介绍关系一个新运算，关系复合。定义定义3.7.13.7.1 设R为X到Y关系，S为从Y到Z关系，则RS称为R和S复合关系复合关系，表示为 RS RS x x X X z z Z Zy(yy(y Y Y R R y,z S)S)易见RS是从X到Z关系。*从R和S，求RS称为关系合成运算关系合成运算。合成运算由两个关系生成一个新关系*P114P114比如：比如：R R1 1是关系是关系“是是弟兄弟兄”，R R2 2是关系是关系“是是父父亲亲”，
2、那么，那么R1R2是关系是关系“是是叔伯叔伯”若若R1R1是关系是关系“是是父亲父亲”，那么，那么R1R2是关系是关系“是是祖父祖父”第2页2一关系复合一关系复合例题1：R=,S=,则 RS=,SR=,(RS)R=?R(SR)=?SS=RR=,RRR=,能够证实，关系复合运算满足结合律，即：（RS）TR（ST）故可记为 RSTP115 例题2*当R与自己复合时，记记RRRRR R2 2。普通定义 R Rn+1n+1=R=Rn nRR第3页3一关系复合一关系复合例：设X=0,1,2,3,则 R=,R2=RR=?,R3=R2R=?,*关系可用矩阵表示，故复合关系亦可用矩阵表示。（类似矩阵乘法，但采
3、取逻辑加）P115第4页4例例例题例题3 A=1,2,3,4,5，A上二元关系R和S定义以下：R=1,2,2,2,3,4 S=1,3,2,5,3,1,4,2试求MR S和MR MS，它们是否相等?解：按照R 和S定义，求出 RS=1,5,2,5,3,2 写出R、S和R S关系矩阵以下：MR=MS=MR S=第5页5例例 MR MS=所以MR S=MR MS第6页6二、关系逆二、关系逆 关系是序偶集合，因为序偶有序性，关系还有一关系是序偶集合，因为序偶有序性，关系还有一些特殊运算。些特殊运算。P117 P117 定义定义3.7.23.7.2 设R为X到y二元关系，如将R中每一序偶元素次序交换，所
4、得集称为R R逆关系逆关系，记为Rc，即：Rc=Rn比如：R=,则 Rc=,n易见(Rc)c=R n又如集合Z上，关系“”第7页7二、关系逆二、关系逆 P117 P117 定理定理3.7.13.7.1 设R，S，T都是从A到B二元关系，则1）(ST)C=SCTC2）(ST)C=SCTC3）(AB)C=BA4）(R)C=RC (R=AB-R,RC=BA-RC)5）(S-T)C=SCTC 第8页8二、关系逆二、关系逆 证：1)(ST)CSTSTS C T c S C T C4)(R)CRRR C(R)C5)因STST，故(S-T)C=(ST)C=S C(T)C =S C T C=S C-T C 第
5、9页9二、关系逆二、关系逆P117 P117 定理定理3.7.23.7.2 设T为从X到Y关系，S为从Y到Z关系，则（TSTS）C CS S C CTT C C证：（TS）CTSy(yYTS)y(yYT C S C)S CT C第10页10二、关系逆二、关系逆定理定理3.7.33.7.3 设R为X上二元关系，则：n1）R是对称，当且仅当RR C；n2）R是反对称，当且仅当RR C IX。证证：1）R对称，故RRR C,故RR C反之R CR，则RR CR，即R对称。第11页11二、关系逆二、关系逆定理定理3.7.33.7.3 设R为X上二元关系，则：n1）R是对称，当且仅当RR C；n2）R是
6、反对称，当且仅当RR C IX。证证：2）设R反对称RR C 则 R且 R C 故有Rx=y 即 IXRRC IX,反之设RR C IX R且R则 R C RR C即有IX x=y R是反对称。第12页12二、关系逆二、关系逆*关于R C图形，是R图形中将其弧线箭头反置即得，而R C关系矩阵是R关系矩阵转置。例：X=a,b,c其上二元关系R关系阵为则R C关系阵为第13页13例例 例例 设X=1,2,3,4，Y=a,b,c，X到Y二元关系 R=1,a,2,b,4,c，试求RC，写出MR和 ，验证 =MRT 画出R和RC关系图，验证将R关系图中弧线箭头反置可得到RC关系图。解：RC=a,1,b,2,c,4 R和RC关系矩阵是：MR=显然，=MRT 第14页14例例 R和RC关系图分别是图1和图2，它们中弧线方向是相反。第15页15本课小结关系复合关系逆 第16页16作业P119(6)(7)第17页17
