电子工业出版社：计算机类本科规划教材《离散数学》课程教学资源（PPT课件讲稿）第4章 二元关系

第4章二元关系 在二元关系运算中,认为全域关系是全集。所以 ~R=X×YRcX×Y,即~R是X到Y二元关系 由以上结论可以得到: (R-S)≤X×Y和(S- R)CXXY,从而 (R-S)∪(S-RX×Y,所以 RGS=(R-S∪(S-RX×Y,即RS是X到Y的二元关 系 【例45】设1,2,3,4},X上的二元关系H和S定义如 H=<xy|”是整数 xJ>|xy是正整数 试求HUS,H∩S,~H,SH

第4章 二元关系 在二元关系运算中，认为全域关系是全集。所以 ~R= X×Y-R X×Y，即~R是X到Y的二元关系。 由以上结论可以得到： (R－S)X×Y和(S－R)X×Y，从而 (R－S)∪(S－R)X×Y，所以 R S=(R－S)∪(S－R)X×Y，即R S是X到Y的二元关 系。 【例4.5】设X=1,2,3,4，X上的二元关系H和S定义如 下： H=x,y | 是整数 S=x,y | 是正整数 试求H∪S，H∩S，~H，S-H  2 x − y 3 x − y 

第4章二元关系 解:将H和S用列举法表示: H<1,1>,<1,3><2,2><24>,<3,3><31><44,<4,2>} S-<4,1> H∪S-1<1,1>,<1,3>,<2,2>,<2,4>,<3,3>,<3,1>,<44>, <4,2>,<4,1>} H∩s= H=X2-H=1<1,2><14><2,1><2,3><3,2><3,4> <4,3><4,1>} S-H=<4,1>} 422二元关系的复合运算 定义422设X,Y,Z是集合, RoXY, ScYXZ,集 1<x→>|x∈X∧∈Z∧(y)yv∈F∧<xy∈R∧<y>∈S) 叫做R和S的复合关系。记为RoS, RoScXXz,即RoS是X到 Z的二元关系

第4章 二元关系 解：将H和S用列举法表示： H=1,1,1,3,2,2,2,4,3,3,3,1,4,4,4,2 S=4,1 H∪S=1,1,1,3,2,2,2,4,3,3,3,1,4,4, 4,2,4,1 H∩S= ~H=X 2- H=1,2,1,4,2,1,2,3,3,2,3,4, 4,3,4,1 S－H=4,1 4.2.2二元关系的复合运算 定义4.2.2 设X，Y，Z是集合，RX×Y，SY×Z，集 合 x,zxX∧zZ∧(y)(yY∧x,yR∧y,zS) 叫做R和S的复合关系。记为R∘S，R∘SX×Z，即R∘S是X到 Z的二元关系

第4章二元关系 【例46】X=11,2,3,4,5},X上的二元关系R和S定义如 R=1<1,2>,<3,4>,<2,2> S-<4,2><2,5>,<3,1><13>} 试求RoS,S°R,Ro(SoR),(RoS)oR,RoR,SoS, Ro RoR 解:RoS=<1,5>,<32><2,5>} SoR=1<4,2><3,2>1,4>} (RoS)⊙R=1<3,2>} R(SR=<3,2>} RR=<12><2,2>} SoS=1<4,5><3,3><1,1> rotoR=<1,2><22>} 从例46可以看出,RoS≠SoR,这说明,二元关系的 复合运算不满足交换律

第4章 二元关系 【例4.6】X=1,2,3,4,5，X上的二元关系R和S定义如 下： R=1,2,3,4,2,2 S=4,2,2,5,3,1,1,3 试求R∘S，S∘R，R∘(S∘R)，(R∘S)∘R，R∘R，S∘S，R∘R∘R 解：R∘S=1,5,3,2,2,5 S∘R=4,2,3,2,1,4 (R∘S)∘R=3,2 R∘(S∘R)=3,2 R∘R=1,2,2,2 S∘S=4,5,3,3,1,1 R∘R∘R =1,2,2,2 从例4.6可以看出，R∘S≠S∘R，这说明，二元关系的 复合运算不满足交换律。 

第4章二元关系 定理4.2.2设X,Y,Z,W是集合,RcX×Y,ScY×Z, 7Z×W,则(RoS)7=R(SoT) 证明:<x,w>∈(RoS)o7>(z)(<x,x>∈RoS∧<,w>∈7) >()(y)(<x>∈R∧y>∈S)∧<,>∈T (z)(3y)(xy>∈R∧yz>∈S)∧<,>∈T) >(y)(3)<xy>∈R∧(<y2>∈S∧<,>∈T)) (y)(<x,少>∈R∧()(<y,2>∈S∧<,>∈T) >(y)(<x>∈R∧<y,w>∈S0)<<x,>∈Ro(SoT) 所以(RoS)o7=R(SoT)

第4章 二元关系 定理4.2.2 设X，Y，Z，W是集合，RX×Y，SY×Z， T Z×W，则 (R∘S)∘T= R∘(S∘T) 证明：x,w(R∘S)∘T(z)(x,zR∘S∧z,wT) (z)((y)(x,yR∧y,zS)∧z,wT) (z)(y)((x,yR∧y,zS)∧z,wT) (y)(z)(x,yR∧(y,zS∧z,wT)) (y)(x,yR∧(z)(y,zS∧z,wT)) (y)(x,yR∧y,wS∘T)x,wR∘(S∘T) 所以 (R∘S)∘T=R∘(S∘T) 

第4章二元关系 定理4,23设R是A上的二元关系,Rol=R=R 证明:先证Rol=R <x>∈Ro→>(z)(<x,>∈R∧<zy>∈ →()(<x,>∈R∧x=y)→<x少∈R 所以RolR <xy>∈R→<x>∈R∧<yy>∈l→<x>∈Rol4 所以 RCROLA 故Rol=R 类似的,可以证明I°R=R

第4章 二元关系 定理4.2.3 设R是A上的二元关系，R∘IA =IA ∘R=R 证明：先证R∘IA =R x,yR∘IA(z)(x,zR∧z,yIA ) (z)(x,zR∧z=y)x,yR 所以 R∘IAR x,yRx,yR∧y,yIAx,yR∘IA 所以 RR∘IA 故 R∘IA =R 类似的，可以证明IA ∘R= R