第4章二元关系 定理4.24设R,S,T是A上的二元关系,则 (1)Ro(S∪T=RoS∪RoT (2)(R∪S)7= RoTU SoT (3)Ro(S∩ acRoS∩RoT (4)(R∩S)7∈R7nSoT 证明:仅证明(3),类似地可证明(1)、(2)和(4) <xy>∈Ro(S∩T→()<x,x>∈RA∧<y>∈S∩T) →()(<x,z>∈R∧(<y>∈S∧<y>∈T →()(<x,z>∈R∧<y>∈S)∧(<x,z>∈R∧<>∈T) →()(<x,z>∈R∧<>∈S)∧(2)(<x>∈R∧<∈T →<x>∈RS∧<xy>∈RoT →<Xy>∈RoS∩RoT 故Ro(S∩T=RS∩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∩RoT实Ro(S∩T,举反例如下: 设A=11,2,3,4.5} R=1<4,1>,<42>}cA×A S-<15><3,5>}cA×A 1<2,5>,<3,5>cA×A R°S∩RT=<45>}∩<4.5}=<4.5>} R(S∩T)=<4,1,<4,2>81<35>}= RS∩R。TgR(S∩T 定理42.4的(1)说明,关系的复合运算“。″对并运算 ∪”满足左分配律。(2)说明,关系的复合运算“o 对并运算“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章二元关系 定义423设R是A上的二元关系,n为自然数,R的n次幂 记为R,定义为: (1)R0=l (2)Rn+l= Rno R 由定义42.3可以看出,A上的任何二元关系的0次幂都相 等,等于A上的恒等关系l。由定义423还可以看出: Rl=R0。R=l,R=R R2=RoR=R°R R3=R2°R=(RR)°R 因为复合运算满足结合律,所以R3又可以写成: R3= RoToR n个R的复合 同样的道理P也可以写成:R"=RoRo…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章二元关系 例如,在例46中 R2=RR=<1,2><2,2>} =SS=1<4,5><3,3>,<1,1>} R3=RRR=<12><2,2>} 定理425设A是具有n个元素的有限集,R是A上的二元 关系,则必存在自然数s和t,使得R≌=R,0≤s<t≤2”。 证明:R是A上的二元关系,对任何自然数k,由复合关 系的定义知,R仍然是A上的二元关系,即RcA×A。另一 方面,根据定理41.1,A上的二元关系仅有2”种。列出R的 各次幂R0,Rl,R2,…,R2”,共有2”+1个,必存在自然 数和t,使得R=R,0≤s<t≤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章二元关系 【例47】A=1,2,3,4},A上的二元关系R定义如下 R-<12><2,1><2,3><34> 求二元关系R的各次幂,验证定理42.5 解:|=4 R=l=<1,1,<2.2>,<3,3><44>8 Rl=R<12><2,1><2,3><3,4>} R2=RoR=R°R-<1,1><1,3><2,2><24} R3=R2R=<1,2>,<2,1>,<2,3>,1,4> R4=R3oR=<1,1>,<1,3><2,2><2,4>}=R2, 0≤2<4≤216=24 R5=R4oR-R2oR-R3 R6=R5°R=R3°R=R4=R2 Rin=R R 2n+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