第6讲关系表示与关系性质 内容提要 关系运算性质(续) 关系矩阵,关系图 癱自反,反自反,对称,反对称,传递 《集合论与图论》第6讲
《集合论与图论》第6讲 1 第6讲 关系表示与关系性质 内容提要 关系运算性质(续) 关系矩阵, 关系图 自反, 反自反, 对称, 反对称, 传递
关系基本运算的性质(续) 婚定理6~定理9 定理6:设R,R2R3是集合,则 (1)R1(R2R3)=(R1R2)(R10R3) (2)(R心R2)0R3=(R10R3/(R2R3) (3)R1(R2R3)∈(R1oR2)⌒(R1R3) (4)(RnRyoR3S(ROR3)(R2oR3 《集合论与图论》第6讲
《集合论与图论》第6讲 2 关系基本运算的性质(续) 定理6~定理9 定理6: 设R1,R2,R3是集合,则 (1) R1○(R2∪R3) = (R1○R2)∪(R1○R3) (2) (R1∪R2)○R3 = (R1○R3)∪(R2○R3) (3) R1○(R2∩R3) ⊆ (R1○R2)∩(R1○R3) (4) (R1∩R2)○R3 ⊆ (R1○R3)∩(R2○R3)
定理6(证明1) (1)R1(R)=(R10R2R1R3) 鲁证明:{<Xy>, <X,y>∈R1p(R2R BHZ(X(R2UR3)ZAZR)3z(XR2ZVXR3Z ZRy 2(XR2A2R)×R3ZA2R1) BHz(xR2ZAZR,y VEz(XR3ZAZR,y BX(RyoR2lyVX(,oR3) yeX((ROR2 U(R,oR3)y X,y>∈(R1R2y/(R1oR3) 《集合论与图论》第6讲
《集合论与图论》第6讲 3 定理6(证明(1)) (1) R1○(R2∪R3) = (R1○R2)∪(R1○R3) 证明: ∀<x,y>, <x,y>∈R1○(R2∪R3) ⇔∃z(x(R2∪R3)z∧zR1y)⇔∃z((xR2z∨xR3z)∧zR1y) ⇔∃z((xR2z∧zR1y)∨(xR3z∧zR1y)) ⇔∃z(xR2z∧zR1y)∨∃z(xR3z∧zR1y) ⇔x(R1○R2)y∨x(R1○R3)y⇔x((R1○R2)∪(R1○R3))y ⇔<x,y>∈(R1○R2)∪(R1○R3)
定理6(证明(3) 3)R1(R2R3∈(R10R2)⌒(R1oR3) 证明:<Xy>, <X,y>∈R1p(R2R 分2(X(R2^R3)ZA2Ry(XR2Z入XR32)zR1) BIZ(R2ZNZR1y)A(XR3ZAZR,Y)) =Z(xR2ZAZRY A3Z(XR3ZAZR,y BX(RyoR2lyAX(,oR3) yeX((ROR2)O(R,oR3)y <X,y>∈(R1R2)∩(R1oR3.# 《集合论与图论》第6讲
《集合论与图论》第6讲 4 定理6(证明(3)) (3) R1○(R2∩R3) ⊆ (R1○R2)∩(R1○R3) 证明: ∀<x,y>, <x,y>∈R1○(R2∩R3) ⇔∃z(x(R2∩R3)z∧zR1y)⇔∃z((xR2z∧xR3z)∧zR1y) ⇔∃z((xR2z∧zR1y)∧(xR3z∧zR1y)) ⇒∃z(xR2z∧zR1y)∧∃z(xR3z∧zR1y) ⇔x(R1○R2)y∧x(R1○R3)y⇔x((R1○R2)∩(R1○R3))y ⇔<x,y>∈(R1○R2)∩(R1○R3). #
定理6(讨论(3) (3)R1(R2R3)c(R10R)(R1oR3) 反例(说明=不成立) 设R={b>,<c.d R2{ab,R3-{a,c}0 刂R(R2∩R3)=R10O=⑦, R,oR2=(a, d>), R,oR3=a, d>1, (R1R2)/(R10R)={ad)}.# 《集合论与图论》第6讲
《集合论与图论》第6讲 5 定理6(讨论(3)) (3) R1○(R2∩R3) ⊆ (R1○R2)∩(R1○R3) 反例(说明=不成立): 设 R1={<b,d>,<c,d>}, R2={<a,b>}, R3={<a,c>}. 则R1○(R2∩R3) = R1○∅ = ∅, R1○R2={<a,d>}, R1○R3={<a,d>}, (R1○R2)∩(R1○R3)={<a,d>}. # a b c d