离散数学第四章(第3讲)课件.ppt

1、4 关系的运算关系的运算关系的复合关系的复合定义定义：设 YX（R关系），关系），ZY（S关系），关系），于是可获得：于是可获得：ZX（R S）的关系，称的关系，称 R S为为R和和S的复合关系，并规定为：的复合关系，并规定为：),(|,SzyRyxYyyZzXxzxSR),(|,SzyRyxYyyZzXxzxSR例：设例：设A=1,2,3,4,5，R,S均为均为AA的关系，且的关系，且R=S=则则 R S=S R=讨论：讨论：（1）RS SR，因此因此“”是不可交换的。是不可交换的。（2）RS为新的二元关系，且为新的二元关系，且RS为X Z Z上的二元关系。上的二元关系。定理定理：设 WZY

2、XRRR321则有：则有：321321321)()(RRRRRRRRR即即:关系的复合运算满足结合律关系的复合运算满足结合律.定义定义给定集合给定集合X，R是是X中的二元关系，设中的二元关系，设 Nn于是于是R的的n次幂次幂)(nR可以定义成：可以定义成：RRRnn)1()(,Ra bb cc a,cbaX 例：例：多个相同的二元关系多个相同的二元关系R 复合复合(3)(2),xRRRa ab bc cI (2),RR Ra cb ac b 复合运算的矩阵表示：复合运算的矩阵表示：设有三个集合：设有三个集合：ZYXzzzZyyyYxxxXSRpnm,212121nmikRaM而而|X|=m,|

3、Y|=n,|Z|=p，则关系矩阵：，则关系矩阵：pnkjSbMpmijSRcMSRSRMMM)(1kjiknkijbac例：设例：设X=1,2,3,R,S均是均是X中的二元关系，中的二元关系，R=,S=0 1 00 1 01 0 0MR=0 1 10 0 11 0 0MS=（0 0）（1 0）（0 1）=00 0 10 0 10 1 1MRS=2逆关系逆关系 定义定义:设设X,Y是二个集合，若是二个集合，若R是是XY的关系，从的关系，从YX的的关系，称为关系，称为R的逆关系，用的逆关系，用,|,RyxxyR表示，或用表示，或用 cR表示。表示。例：例：X=0,1,2，R=110100001,1

4、00001011RRMMR=2逆关系逆关系 讨论定义：讨论定义：（1）只要将）只要将R中每一个序偶中的元素全部调换位置，就可得到中每一个序偶中的元素全部调换位置，就可得到R的的逆关系逆关系。（2）R的关系矩阵为的关系矩阵为 RM的转置矩阵；的转置矩阵；（3）在）在R的关系图中，只要把所有箭头改换方向就可得到的关系图中，只要把所有箭头改换方向就可得到的关系图。（自回路箭头改变与否无关）的关系图。（自回路箭头改变与否无关）R定理定理设 ZYXSR，则可有：，则可有：RSSR RSSR同样 xRSzxRyySz)(xSRzzSRxySzxRy)()(证明：对于任一证明：对于任一 ZzYyXx,来讲，

5、若有来讲，若有 R SSR同理可证同理可证SRR SR一定是对称的一定是对称的 定理定理:设设R是集合是集合X中的二元关系，当且仅当中的二元关系，当且仅当RR则则R才是对称的。才是对称的。证明：充分性：证明：充分性：R是对称的是对称的 RR对于任一对于任一 RbaRabRba,RR必要性：必要性：RRR是对称的，是对称的，RR对任一对任一 RabRbaRba,定理：给定集合定理：给定集合X,Y,YXSRRR,21，于是可有：，于是可有：RR)1(SRSR)2(SRSR)3(XYYX)4()6(2121)5(RRRR3.闭包运算闭包运算定义定义：给定集合：给定集合X，R是是X中的二元关系，若有另

6、一中的二元关系，若有另一关系关系R满足下列条件：满足下列条件：（1）R 是自反的（对称，可传递的）；是自反的（对称，可传递的）；（2）RR则称则称R是是R的自反（对称，传递的）闭包，的自反（对称，传递的）闭包，并依次用并依次用r(R),s(R),t(R)来表示。来表示。4关系的运算关系的运算RR，则 RR（3）对于任一自反（对称，传递的）关系）对于任一自反（对称，传递的）关系 ，若，若 R 例：设例：设A=1,2,3，R为为AA的关系，且的关系，且R=R=具有自反性质具有自反性质RRR=具有具有自反性质自反性质RR RR R是包含是包含R的具有自反性质的的具有自反性质的最小最小的二元关系的二元

7、关系讨论定义：讨论定义：（1）已知一个集合中的二元关系）已知一个集合中的二元关系R，则，则r(R),s(R),t(R)是是包含包含R的具有自反（对称，传递）性质的的具有自反（对称，传递）性质的最小最小的二元关系的二元关系,它它们是们是唯一唯一的；的；（2）若）若R不是自反（对称，传递）的，则我们可以补上不是自反（对称，传递）的，则我们可以补上最少最少序偶，使之变为自反、对称、传递关系，从而得到序偶，使之变为自反、对称、传递关系，从而得到r(R),s(R),t(R)；定理定理：给定集合：给定集合X，R是是X中的二元关系，于是可有：中的二元关系，于是可有：（1）当且仅当）当且仅当r(R)=R，则，

8、则R是自反的；是自反的；（2）当且仅当）当且仅当s(R)=R，则，则R是对称的；是对称的；（3）当且仅当）当且仅当t(R)=R，则，则R是可传递的。是可传递的。该定理说明：若该定理说明：若R是自反（对称，传递）的，则是自反（对称，传递）的，则r(R),s(R),t(R)就是就是R本身。本身。xI定理定理：R是是X中的二元关系中的二元关系,是是X中的恒等关系，中的恒等关系，则有则有 xIRRr)(证明：按定义证：证明：按定义证：（1）设设 xIRR，则，则R是自反的，是自反的，（3）设有任一包含）设有任一包含R的二元关系的二元关系R也是自反的，即也是自反的，即则 )(RRIRRxRRIRx RR

9、)2(xIRR 例：设例：设X=a,b,c,R=，求，求r(R)解：解：r(R)=,ccbbaaaccbbaIRx定理定理：给定集合：给定集合X，R是是X中的二元关系，则有中的二元关系，则有 RRRS)(例：设例：设X=a,b,c,R=，求，求s(R)s(R)=,caacbccbabbaRR 定理定理：设：设X是一集合，是一集合，R是是X中的二元关系，则：中的二元关系，则：(2)()1(),()iit RRRU RiI例：例：X=a,b,c,R=，|X|=3,计算计算t(R)(2)(3)(2)(4)(3),=,=RR Ra cb ac bRRRa ab bc cRRR R,)()3()2(cc

10、bbaabcabcaaccbbaRRRRt例：例：X=a,b,c,d,R=,计算t(R)4()3()2(,RdaRdbcaR,)()4()3()2(dadbcadccbbaRRRRRt定理定理：设：设|X|=n，R是是X中的二元关系，则中的二元关系，则)()2()(kRRRRt)0(nK 例：设例：设X=a,b,R=，求，求r(R),s(R),t(R)r(R)=s(R)=t(R)=R定理定理：设：设X是一集合，是一集合，R是是X中的二元关系，则有：中的二元关系，则有：r(S(R)=S(r(R)r(t(R)=t(r(R)S(t(R)t(S(R)证明：r(s(R)()xr RRRRI()()xxRIRI()()xxRIRI()()()r Rr RSr Rr(S(R)=S(r(R)例：设例：设X=a,b,c,R=（1）rs(R)=r=sr(R)=s=（2）rt(R)=r=tr(R)=t=（3）ts(R)=t=st(R)=S=