离散数学离散数学 (11).pdf

《离散数学离散数学 (11).pdf》由会员分享，可在线阅读，更多相关《离散数学离散数学 (11).pdf（22页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、Computer Science&Technology0Computer Science&Technology1RR 对称的s(R)对称的对称传递的传递的传递t(R)RR RR RComputer Science&Technology2Computer Science&Technology3Computer Science&Technology4Computer Science&Technology5例:A=a,b,c,dR=(a,b),(b,a),(b,c),(c,d)r(R)=(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)0000100001

2、0100101000110001110011abcdMr(R)=MRMIAComputer Science&Technology6定理定理2s(R)=R R-1Computer Science&Technology7定理定理2s(R)=R R-1Computer Science&Technology8使用定理使用定理2使用。例:A=a,b,c,dR=(a,b),(b,a),(b,c),(c,d)s(R)=RR-1=(a,b),(b,a),(b,c),(c,d),(c,b),(d,c)0100101001010010abcdMs(R)=MRMTR0000100001010010MRMTR0100

3、001000010010 R-1=(b,a),(a,b),(c,b),(d,c)Computer Science&Technology9定理定理3321)(RRRRRtii321RRRRiiComputer Science&Technology10例:A=a,b,c,dR=(a,b),(b,a),(b,c),(c,d)R2=(a,a),(b,b),(b,d),(a,c)R3=R2R=(a,b),(b,a),(b,c),(a,d)R4=(a,a),(b,b),(b,d),(a,c)=R2,R5=R3,R6=R2Computer Science&Technology11t(R)=R R2 R3=(

4、a,b),(a,c),(a,d),(b,a),(b,c),(b,d),(c,d),(a,a),(b,b)定理定理3321)(RRRRRtiiR4=R2,R5=R3,R6=R2A=a,b,c,d,|A|=4Computer Science&Technology12定理定理3321)(RRRRRtiiiiR1iiR1传递闭包定义的三条：具有传递性，包含传递闭包定义的三条：具有传递性，包含R的所有序偶且序偶最少的所有序偶且序偶最少Computer Science&Technology13定理定理3321)(RRRRRtiiiiR1iiR1Computer Science&Technology14in

5、iRRt1)(定理定理4：集合A是个元素的有限集，即|A|=n，则iniiiRRRt11)(证明证明：iniiiRR11(1)iniiiRR11(2)?Computer Science&Technology15iniiiRR11(2)iniiiRR11 证明 由集合的并运算可知显然成立以下证明也成立iniiiRR11 iiR1iniR1Computer Science&Technology16iniR1iniiiRR11 Computer Science&Technology17例:A=a,b,c,dR=(a,b),(b,a),(b,c),(c,d)，求取关系的闭包。R2=(a,a),(b,b

6、),(b,d),(a,c)0000100001010010MR=0000000010100101MR2=*00001000010100100000100001010010=R2=RR=(a,b),(b,a),(b,c),(c,d)(a,b),(b,a),(b,c),(c,d)=(a,b),(b,a),(b,c),(c,d)Computer Science&Technology18R3=(a,b),(a,d),(b,a),(b,c)0000000001011010=0000000010100101MR20000100001010010MRMR3=MR2R=MR MR2=R3=R2R=(a,a),

7、(b,b),(b,d),(a,c)(a,b),(b,a),(b,c),(c,d)=(a,b),(a,d),(b,a),(b,c)Computer Science&Technology19R4=(a,a),(b,b),(b,d),(a,c)=R20000000010100101=MR2R5=R3MR5=MR3MR4=00001000010100100000000001011010MR3MRComputer Science&Technology20000000001010010100001000010100100000000001011010*23RRRRMMMM=0000100011111111t(R)=R R2 R3=(a,b),(a,c),(a,d),(b,a),(b,c),(b,d),(c,d),(a,a),(b,b)Computer Science&Technology21iniRRt1)(