第4章二元关系 定理4.2.4设R,S,T是A上的二元关系，则 (1)Ro(SUT)=RoSURoT (2)(RUS)oT=RoTUSoT (3)R(S∩T)cRS∩RoT (4)(R∩S)TCRoT∩S.T 证明：仅证明(3)，类似地可证明(1)、(2)和(4)。 <x,>∈R(S∩T)→(3z)(<x,>∈R∧<z,>∈S∩T) →(3z(<x,>∈R∧(<2,2∈S∧<2>∈T) →(3z)(<x,>∈R∧<z,>∈S)∧(<x,>∈R∧<，>∈T) →（自z)(<x,>∈R∧<，>∈S)∧（日z)(<x,>∈R∧<3，>∈T →<x,>∈RoS∧<x,y>∈RoT →<x,y>∈RoS∩RoT 故R(S∩T)cRS∩RT
第4章 二元关系 定理4.2.4 设R，S，T是A上的二元关系, 则 ⑴ R∘(S∪T)=R∘S∪R∘T ⑵ (R∪S)∘T=R∘T∪S∘T ⑶ R∘(S∩T)R∘S∩R∘T ⑷ (R∩S)∘TR∘T∩S∘T 证明：仅证明⑶，类似地可证明⑴、⑵和⑷。 x,yR∘(S∩T)(z)(x,zR∧z,yS∩T) (z)(x,zR∧(z,yS∧z,yT)) (z)((x,zR∧z,yS)∧(x,zR∧z,yT)) (z)(x,zR∧z,yS)∧(z)(x,zR∧z,yT) x,yR∘S∧x,yR∘T x,yR∘S∩R∘T 故 R∘(S∩T)R∘S∩R∘T
第4章二元关系 一 般地说，RS∩RoTR(S∩T),举反例如下： 设A=1,2,3,4,5} R<4,1>,<4,2>cA×A S<1,5>,<3,5>7cAXA T=<2,5>,<3,5>7cA×A RS∩RT=<4,5>7∩<4,5>=<4,5>} R(S∩T)=<4,1>,<4,2>o<3,5>=☑ RS∩RT±R(S∩T 定理4.2.4的(1)说明，关系的复合运算"。”对并运算 ”U”满足左分配律。(2)说明，关系的复合运算”。” 对并运算“U”满足右分配律。所以，复合运算”。” 对并运算”U”满足分配律。由(3)和(4)知，复合运算 。”对交运算“∩”不满足分配律
第4章 二元关系 一般地说，R∘S∩R∘T⊈R∘(S∩T)，举反例如下： 设A=1,2,3,4,5 R=4,1,4,2A×A S=1,5,3,5A×A T=2,5,3,5A×A R∘S∩R∘T =4,5∩4,5 =4,5 R∘(S∩T) =4,1,4,2∘3,5= R∘S∩R∘T⊈R∘(S∩T) 定理4.2.4的⑴说明，关系的复合运算“ ∘ ”对并运算 “∪”满足左分配律。⑵说明，关系的复合运算“ ∘ ” 对并运算“∪”满足右分配律。所以，复合运算“ ∘ ” 对并运算“∪”满足分配律。由⑶和⑷知，复合运算 “ ∘ ”对交运算“∩”不满足分配律
第4章二元关系 定义4.2.3设R是A上的二元关系，n为自然数，R的n次幂 记为R”,定义为： (1)R0=IA (2)Rn+1=RnoR 由定义4.2.3可以看出，A上的任何二元关系的0次幂都相 等，等于A上的恒等关系14。由定义4.2.3还可以看出： R=RO。R=I°R=R R2=R1oR=RoR R3=R2oR=(RR)°R 因为复合运算满足结合律，所以3又可以写成： R3=RoRoR n个R的复合 同样的道理Rn也可以写成：Rn=R。R。…oR
第4章 二元关系 定义4.2.3 设R是A上的二元关系，n为自然数，R的n次幂 记为R n ，定义为： ⑴ R 0=IA ⑵ R n+1= R n∘R 由定义4.2.3可以看出，A上的任何二元关系的0次幂都相 等，等于A上的恒等关系IA。由定义4.2.3还可以看出： R 1= R 0 ∘ R=IA ∘R=R R 2= R 1∘R= R∘R R 3= R 2∘R=(R∘R)∘R …… 因为复合运算满足结合律，所以R 3又可以写成： R 3= R∘R∘R 同样的道理R n也可以写成： R n= n个R的复合 R R R
第4章二元关系 例如，在例4.6中 R2=RR=<1,2>,<2,2> S2=SS<4,5>,<3,3>,<1,1> R3=RRR-<1,2>,<2,2>/ 定理4.2.5设A是具有n个元素的有限集，R是A上的二元 关系，则必存在自然数s和t,使得R=R,0≤s<≤2”。 证明：R是A上的二元关系，对任何自然数k,由复合关 系的定义知，R仍然是A上的二元关系，即R&CAXA。另一 方面，根据定理4.1.1，A上的二元关系仅有2”种。列出R的 各次幂R,R,R2,…,R2,共有2+1个，必存在自然 数s和t,使得R=R,0≤s<≤2
第4章 二元关系 例如,在例4.6中 R 2=R∘R=1,2,2,2 S 2 =S∘S=4,5,3,3,1,1 R 3=R∘R∘R=1,2,2,2 定理4.2.5设A是具有n个元素的有限集，R是A上的二元 关系，则必存在自然数s和t，使得R s=R t ，0≤s＜t≤2 。 证明：R是A上的二元关系，对任何自然数k，由复合关 系的定义知，R k仍然是A上的二元关系，即R kA×A。另一 方面，根据定理4.1.1， A上的二元关系仅有2 种。列出R的 各次幂R 0 ，R 1 ，R 2 ，…， ，共有2 ＋1个，必存在自然 数s和t，使得R s=R t ，0≤s＜t≤2 。 2 n 2 n 2 n 2 2 n R 2 n
第4章二元关系 【例4.7】A=1,2,3,4,A上的二元关系R定义如下： R=<1,2>,<2,1>,<2,3>,<3,4>7 求二元关系R的各次幂，验证定理4.2.5。 解：A=4 R0=l<1,1>,<2,2>,<3,3>,<4,4>} R1=R=<1,2>,<2,1>,<2,3>,<3,4> R2=1oR=RR=<1,1>,<1,3>,<2,2>,<2,4> R3=R2oR月<1,2>，<2,1>，<2,3>，<1,4>7 R4=R3R-<1,1>,<1,3>,<2,2>,<2,4>=R2, 0≤2<4≤216-24 R5=R40R=R2R=R3 R6=R5R=R3R=R4=R2 ●●●●●● R2n=R2 R2+1=R3,n=1,2,3,…
第4章 二元关系 【例4.7】A= 1,2,3,4，A上的二元关系R定义如下： R=1,2,2,1,2,3,3,4 求二元关系R的各次幂，验证定理4.2.5。 解：|A|=4 R 0=IA =1,1,2,2,3,3,4,4 R 1=R=1,2,2,1,2,3,3,4 R 2=R 1∘R= R∘R=1,1,1,3,2,2,2,4 R 3= R 2∘R =1,2,2,1,2,3,1,4 R 4=R 3 ∘R=1,1,1,3,2,2,2,4=R 2 ， 0≤2＜4≤2 16=2 R 5=R 4∘R=R 2∘R=R 3 R 6=R 5∘R=R 3∘R=R 4= R 2 …… R 2n=R 2 R 2n+1=R 3 , n =1,2,3,… 2 4