计算机类本科规划教材：《离散数学》课程配套电子教案（PPT课件讲稿）第4章 二元关系

第4章二元关系 在二元关系运算中，认为全域关系是全集。所以 ~R=XXY-RCYXY,即~R是X到Y的二元关系。 由以上结论可以得到： (R-S)sXXY和(S-R)cXXY,从而 (R-S)U(S-R)cXXY,所以 R④S=(R一S)U(S-R)cXXY,即R⊕S是X到Y的二元关 系。 【例4.5】设X日1,2,3,4}，X上的二元关系H和S定义如 下： H<x心1，'是整数 S<x>,y是正整数} 试求HUS,H∩S,~H,S-H

第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>,<2,4>,<3,3>,<3,1>,<4,4>,<4,2> S-<4,1>Y HUS-<1,1>,<1,3>,<22>,<2,4>,<3,3>,<3,1>,<4,4>, <4,2>,<4,1>7 H∩S=⑦ H=X2-H=<1,2>,<1,4>,<2,1>,<2,3>,<3,2>,<3,4> <4,3>,<4,1>7 S-H=<4,1> 4.2.2二元关系的复合运算 定义4.2.2 设X,Y,Z是集合，RcX×Y,SCYXZ,集 合 {<x,>|xeX∧zeZ∧（臼y0veYΛ<x,>eRΛ<y,>∈S)} 叫做R和S的复合关系。记为RS,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章二元关系 【例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>7 试求RS,SoR,Ro(SoR),(RS)R,RoR,SoS,RoRoR 解：RoS-<1,5>,<3,2>,<2,5>7 SoR=<4,2>,<3,2>,<1,4>7 (RS)R=<3,2>7 R(SR)=<3,2>} RoR-<1,2>,<2,2>} SS-<4,5>,<3,3>,<1,1>7 RoRoR=<1,2>,<2,2>7 从例4.6可以看出，RS≠SR,这说明，二元关系的 复合运算不满足交换律

第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, TZXW,则(RS)T=R(SoT) 证明：<x,1w>∈(RS)T→(3z)(<x,>∈RoS∧<z,>∈T →(3z(日y)(<x,>∈R∧<y,>∈S)∧<，w>∈T) 台（自z)日y)(<x>∈R∧y,>∈S)∧<3，w>∈T) →（自y)3z(<x,>∈R∧(y,>∈S∧<，1w>∈T) →（日y)(<x,J>∈R∧（日z(y,>∈S∧<z,w∈T) 台3y)(<x,>∈R∧<y,w>∈SoT)台<x,w>∈Ro(SoT) 所以(RoS)T=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.2.3设R是A上的二元关系，RoL=IOR=R 证明：先证RI=R <x,>∈RoI4→（自z(<x,>∈R∧<zy>∈I) →3z(<x,>∈R∧2=y)→<x,y>∈R 所以RoL CR <x,y>∈R→<x,>∈R∧<y,y>∈IA→<x,ERoL 所以RCRoIA 故RolR 类似的，可以证明IoR=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