北京大学：《离散数学》系列课程之一《集合论与图论》第6讲 关系表示与关系性质

第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) 鲁证明:{, ∈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) 证明: ∀, ∈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 ⇔∈(R1○R2)∪(R1○R3)

定理6(证明(3) 3)R1(R2R3∈(R10R2)⌒(R1oR3) 证明:, ∈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 ∈(R1R2)∩(R1oR3.# 《集合论与图论》第6讲

《集合论与图论》第6讲 4 定理6(证明(3)) (3) R1○(R2∩R3) ⊆ (R1○R2)∩(R1○R3) 证明: ∀, ∈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 ⇔∈(R1○R2)∩(R1○R3). #

定理6(讨论(3) (3)R1(R2R3)c(R10R)(R1oR3) 反例(说明=不成立) 设R={b>,), R,oR3=a, d>1, (R1R2)/(R10R)={ad)}.# 《集合论与图论》第6讲

《集合论与图论》第6讲 5 定理6(讨论(3)) (3) R1○(R2∩R3) ⊆ (R1○R2)∩(R1○R3) 反例(说明=不成立): 设 R1={,}, R2={}, R3={}. 则R1○(R2∩R3) = R1○∅ = ∅, R1○R2={}, R1○R3={}, (R1○R2)∩(R1○R3)={}. # a b c d

定理7 定理7:设F,G为二集合,则 (FoG)=G0F-1 G 1 《集合论与图论》第6讲

《集合论与图论》第6讲 6 定理7 定理7: 设F,G为二集合, 则 (F○G)-1 = G-1○F-1. G G-1 F F-1

定理7(证明) (FoG)1=G-1oF- 证明:V∈(FoG ∈(FoG) 分→丑2(GFx)÷z(G1yxF12) 台→丑2(xF1AG1y) 台∈GoF1.# 《集合论与图论》第6讲

《集合论与图论》第6讲 7 定理7(证明) (F○G)-1 = G-1○F-1 证明: ∀, ∈(F○G)-1 ⇔ ∈(F○G) ⇔ ∃z(yGz∧zFx)⇔∃z(zG-1y∧xF-1z) ⇔ ∃z((xF-1z∧zG-1y) ⇔ ∈G-1○F-1. # y x z

定理8 定理8:设R,SAB,,为集合,1≠,则 1)R↑(AB)=(R个A(R个B); (2)R个U=U{R个A|AE小 3)R↑AB)=(R个A(R个B) (4)R个∩=∩{R个A|A∈丹 (5)(R0S)个A=R(S↑) 《集合论与图论》第6讲

《集合论与图论》第6讲 8 定理8 定理8: 设R,S,A,B,A,为集合,A≠∅,则 (1) R↑(A∪B) = (R↑A)∪(R↑B); (2) R↑∪A = ∪{ R↑A | A∈A}; (3) R↑(A∩B) = (R↑A)∩(R↑B); (4) R↑∩A = ∩{ R↑A | A∈A}; (5) (R○S)↑A = R○(S↑A).

定理8(证明(2) (2)R个UA=U{R个A|A∈对 秦证明:V,X(R↑U小y台XRy∈U 分XRy∧丑A(A∈AAX∈A) →A(XRy∧X∈AAA∈) 引A(X( RTAJYAA∈n) 台X(U{R个A|A∈丹y R个U=U{R个A|A∈ 《集合论与图论》第6讲

《集合论与图论》第6讲 9 定理8(证明(2)) (2) R↑∪A = ∪{ R↑A | A∈A}; 证明: ∀, x(R↑∪A)y ⇔ xRy∧x∈∪A ⇔ xRy ∧ ∃A( A∈A ∧ x∈A ) ⇔ ∃A( xRy ∧x∈A ∧A∈A ) ⇔ ∃A( x(R↑A)y ∧ A∈A ) ⇔ x(∪{ R↑A | A∈A} )y. ∴ R↑∪A = ∪{ R↑A | A∈A}

定理8(证明(4) (4)R个∩=∩{R个A|A∈;(=0) 证明,x(R个∩y分XRyX∈∩ (0XRy)八X∈n(A(A∈XRy)八X∈∩ ≌A( AE AVXRy)AAA∈A∈A) 台A(A∈XRy)(_A∈XA) A(Ae(XRyX∈A)A(Ae小XR个A)y) AAR个Ay)分x(∩{R^A|Aey R个∩=∩R个AA丹 《集合论与图论》第6讲

《集合论与图论》第6讲 10 定理8(证明(4)) (4) R↑∩A = ∩{ R↑A | A∈A}; (A≠∅) 证明:∀, x(R↑∩A)y ⇔ xRy∧x∈∩A ⇔(0∨xRy)∧x∈∩A ⇔(∀A(¬A∈A)∨xRy)∧x∈∩A ⇔∀A(¬A∈A∨xRy)∧∀A(A∈A→x∈A) ⇔∀A((¬A∈A∨xRy)∧(¬A∈A∨x∈A)) ⇔∀A(¬A∈A∨((xRy)∧ x∈A))⇔∀A(¬A∈A)∨x(R↑A)y) ⇔∀A(A∈A→x(R↑A)y)⇔ x(∩{ R↑A | A∈A} )y. ∴ R↑∩A = ∩{ R↑A | A∈A}