ch7 二元关系

第七章二元关系杨圣洪222.240.135.76:8080/ysh007一、有序对有秩序的二个元素排在一块称为有序对,形如元素1,元素2如:天,地,夫,妻,乾,坤,湖南,长沙,1,2,3,6二、笛卡尔积/直积AB形如AB={a,b|aA，bB}如A={1,2,3},B={a,b,c}AB={1,2,3}{a,b,c}={1,a,1,b,1,c,2,a,2,b,2,c,3,a,3,b,3,c}A={中,巴,美,古}AA={中,巴,美,古}{中,巴,美,古}={中,中,中,巴,中,美,中,古,巴,中,巴,巴,巴,美,巴,古,美,中,美,巴,美,美,美,古,古,中,古,巴,古,美,古,古}三、关系将笛卡尔积中前后两个元素之间存在某种关系的序偶检出来,便得到一个关系.AB={1,2,3}{a,b,c}={1,a,1,b,1,c,2,a,2,b,2,c,3,a,3,b,3,c}R1={前后两个元素的序号一样}={1,a,2,b,3,c}AA={1,2,3}{1,2,3}={1,1,1,2,1,3,2,1,2,2,2,3,3,1,3,2,3,3}R2={第一个元素第2个元素}={1,2,1,3,2,3}有时无法用文字描述两者的关系R3={1,1,2,3,3,1}三、关系AB={1,2,3}{a,b,c}={1,a,1,b,1,c,2,a,2,b,2,c,3,a,3,b,3,c}R1={前后两个元素的序号一样}={1,a,2,b,3,c}用如下形式的关系矩阵表示100301020011cba123abc四、复合A={1,2,3},FAxA,GAxAA上的关系设F,G为二元关系,G对F的右复合记为FG,定义FG={x,y|t(x,tF,t,yG)}x,tt,y如F={1,1,1,2}G={2,2,1,3,1,1}FG={1,3,1,1,1,2}M(FG)=M(F)M(G)采用关系矩阵相乘000000111000010101000000011123123A={1,2,3},FAxA,GAxAA上的关系F={1,1,1,2}G={2,2,1,3,1,1}000010101000000011123123123123五、关系的性质与分类自反关系:若关系R前后二个元素来自同一个集合A,若xA,都有x,xR,则R是自反的.反自反关系:若关系R前后二个元素来自同一个集合A,若xA,都有x,xR,则R是反自反的.如:A={1,2,3}R1={1,1,2,2}因为3,3R1不是自反的因为1,1R1,2,2R1,故不是反自反的.R2={1,1,2,2,3,3,1,2}自反的!R3={1,3}反自反的!五、关系的性质与分类自反关系:若xA,有x,xR,则自反的.主对全1反自反关系:若xA,有x,xR,则R反自反主对全0如:A={1,2,3}R1={1,1,2,2,3,3,1,2}自反的!R2={1,3}反自反!R3={1,1,2,2}不是自反,不是反自反.000010001000000100100010011321321321自反自反反自反反自反五、关系的分类自反关系:若xA,都有x,xR反自反关系:若xA有x,xR对称关系:若x,yR有y,xR反对称关系:若x,yR,y,xRx=y若x,yR且xyy,xR则反对称定义等价如:A={1,2,3}R1={1,2,2,1}对称R2={1,1,2,2,3,3,1,2}反对称R3={1,2,2,1,1,3}因3,1R1不对称,因1,2与2,1成对出现,而不是反对称五、关系的分类对称关系:若x,yR有y,xR非对角成对反对称关系:若x,yR且xyy,xR如:A={1,2,3}R1={1,2,2,1}对称R2={1,1,2,2,3,3,1,2}反对称R3={1,2,2,1,1,3}000001110100010011000001010321321321五、关系的性质与分类传递关系:若x,yR,y,zRx,zR表示两个序偶的复合仍在R中,即RRR,M2MA={a,b,c}R={a,b,b,a,b,c,c,d}RR={a,b,b,a,b,c,c,d}{a,b,b,a,b,c,c,d}={a,a,a,c,b,b,b,d}R学会看图000000001010010100001000010100100000100001010010abcdRRRR五、关系的性质与分类传递关系:若x,yR,y,zRx,zR表示两个序偶的复合仍在R中,即RRR,M2M如A={1,2,3}R1={1,2,2,3,1,3,3,3}R1R1={1,2,2,3,1,3,3,3}{1,2,2,3,1,3,3,3}={1,3,2,3,3,3}R故可传递100100100100100110100100110123五、关系的性质与分类传递关系:若x,yR,y,zRx,zR表示两个序偶的复合仍在R中,即RRR,M2M如A={1,2,3}R2={1,2,2,3}传递的产生的1,3R故不是000000100000100010000100010123五、关系的性质与分类传递关系:若x,yR,y,zRx,zR表示两个序偶的复合仍在R中,即RRR,M2M如A={1,2,3}R1={1,1,2,2}可传递的，OKR1R1=R1R1故为可传递！000010001000010001000010001123五、关系的性质与分类自反关系:xAx,xRIAR反自反关系:xAx,xRIAR=对称关系:x,yRy,xRR=R-1反对称关系:x,yR,y,xRx=yx,yR且xyy,xRRR-1IA传递关系:x,yR,y,zRx,zRR2R自反:主对角线均为1反自反:主对角线均为0对称:M=MT。反对称：MMT后只有主对角非0传递:R2R即M2M100010001六、关系的闭包：加点序偶使之成某种类型1、R自反闭包r(R)：加序偶使之成自反的。R={1,1,2,2}不是自反r(R)={1,1,2,2,3,3}r(R)=RIA000010001321321100011011六、关系的闭包：加点序偶使之成某种类型2、R对称闭包s(R)：加序偶使之成对称的。R={1,1,2,2,3,3,1,2}反对称s(R)={1,1,2,2,1,2,2,1}对称s(R)=RRT.100010011321321六、关系的闭包r(R)=RIA=M(R)+M(IA)自反闭包，主对角线1s(R)=RR-1=M(R)+M(R)T.对称闭包，对称补元t(R)=RR2R3...Rn-1.任何两点最多n-1步达=M+M2+M3+...+Mn-1.例A={1,2,3},R={1,1,3,3,1,2,3,1}R不是自反的，加上2,2后自反r(R)={1,1,2,2,3,3,1,2,3,1}=R{1,1,2,2,3,3}R不是对称的，加上2,1,1,3后对称s(R)={1,1,3,3,1,2,3,1,2,1,1,3}=RR-1={1,1,3,3,1,2,3,1}{1,1,3,3,2,1,1,3}六、关系的闭包：加点序偶使之成某种类型1、R自反闭包r(R)的定义：(1)r(R)自反;(2)Rr(R);(3)RR',R'自反r(R)R'最小性恰好增加到变成自反为止。2、R对称闭包s(R)的定义：(1)s(R)对称;(2)Rs(R);(3)RR',R'对称s(R)R'最小性3、R传递闭包t(R)的定义：(1)t(R)传递;(2)Rt(R);(3)RR',R'传递t(R)R'最小性利用求闭包方法也可判断关系性质t(R)=RR2R3...Rn-1.任何两点最多n-1步达=MM2M3...Mn-1.例A={a,b,c,d},R={a,b,b,a,b,c,c,d,d,b}t(R)=RR2R3,R2={a,a,a,c,b,b,b,d,c,b,d,a,d,c}R3={a,a,a,c,b,b,b,d,c,b,d,a,d,c}{a,b,b,a,b,c,c,d,d,b}={a,b,a,d,b,a,b,c,b,b,c,a,c,c,d,b,d,d}t(R)={a,b,b,a,b,c,c,d,d,b,a,a,a,c,b,b,b,d,c,b,d,a,d,c,a,b,a,d,b,a,b,c,b,b,c,a,c,c,d,b,d,d}t(R)=RR2R3...Rn-1.任何两点最多n-1步达=MM2M3...Mn-1.不进位的2进制加乘例A={a,b,c,d},R={a,b,b,a,b,c,c,d,d,b}t(R)={a,b,b,a,b,c,c,d,d,b,a,a,a,c,b,b,b,d,c,b,d,a,d,c,a,b,a,d,b,a,b,c,b,b,c,a,c,c,d,b,d,d}abcd101001010111101000101000010100100101001010100101M010100101010010100101000010100100010100001010010M11111111111111110010100001010010M32t(R)=RR2R3...Rn-1.任何两点最多n-1步达=MM2M3...Mn