定理9(证明(4,续) + 3xVy B(x, y)=Vy=xB(X, y) 证明:在任何解释下,若左1,则右台1 《集合论与图论》第6讲 16
《集合论与图论》第6讲 16 定理9(证明(4),续) (*) ∃x∀yB(x,y) ⇒ ∀y∃xB(x,y) 证明: 在任何解释下, 若左⇔1, 则右⇔1.
定理9(证明(4,续) (*)p(q→)→q→入(∧) 秦证明1:((q→))->(q→(A)是永真式 真值表,等值演算 证明2:(反证)设左1且“右<0” 阳pA(q→)n1且q(An)÷0 由p∧(q→>)÷→1得p=1,q=1; 由q→(A)÷0得q=1,pAr=0 所以=0,q)=0,矛盾!# 《集合论与图论》第6讲
《集合论与图论》第6讲 17 定理9(证明(4),续) (**) p∧(q→r) ⇒ q→(p∧r) 证明1: (p∧(q→r))→(q→(p∧r))是永真式 真值表, 等值演算 证明2: (反证) 设“左⇔1”且“右⇔0” 即p∧(q→r)⇔1且q→(p∧r)⇔0. 由p∧(q→r)⇔1得p=1, q→r=1; 由q→(p∧r)⇔0得q=1, p∧r=0; 所以r=0, q→r=0, 矛盾! #
定理9(证明(5) (5)R[A]RB]∈R(A-B 证明:y,y∈RA]RB]y∈RAy∈RB] 台X(XRyX∈A)∧= X ( XRyAX∈B) 分X(XRyX∈A)∧X(- XRyV XEB) X(XRyX∈A)∧x(XRy>-X∈B) →丑X(XRyX∈AA→XEB) 台彐X(XRy∧X∈AB)y∈RA-B R[A]RB]∈R[A-B 《集合论与图论》第6讲 8
《集合论与图论》第6讲 18 定理9(证明(5)) (5) R[A]-R[B] ⊆ R[A-B]; 证明: ∀y, y∈R[A]-R[B] ⇔ y∈R[A]∧¬y∈R[B] ⇔ ∃x(xRy∧x∈A) ∧ ¬∃x(xRy∧x∈B) ⇔ ∃x(xRy∧x∈A) ∧ ∀x(¬xRy∨¬x∈B) ⇔ ∃x(xRy∧x∈A) ∧ ∀x(xRy→¬x∈B) ⇒ ∃x(xRy∧x∈A∧¬x∈B) ⇔ ∃x(xRy∧x∈A-B) ⇔ y∈R[A-B]. ∴ R[A]-R[B] ⊆ R[A-B].
定理9(证明(5,续) 彐X(XRyX∈A)∧X(XRy→XEB) →X(XRyX∈ A-XEB) 前提:彐X( XRyAX∈A),WX(XRy→>X∈B) 结论;彐X(XRy^XEAA-X∈B) 证明:(1)3 X(XRyAX∈A),前提引入 (2) CRyAC∈A,(1)E (3)WX(XRy→>-X∈B),前提引入 (4)CRy→-C∈B,③3) 《集合论与图论》第6讲 19
《集合论与图论》第6讲 19 定理9(证明(5),续) ∃x(xRy∧x∈A) ∧ ∀x(xRy→¬x∈B) ⇒ ∃x(xRy∧x∈A∧¬x∈B) 前提: ∃x(xRy∧x∈A), ∀x(xRy→¬x∈B) 结论: ∃x(xRy∧x∈A∧¬x∈B) 证明: (1) ∃x(xRy∧x∈A), 前提引入 (2) cRy∧c∈A, (1)EI (3) ∀x(xRy→¬x∈B), 前提引入 (4) cRy→¬c∈B, (3)UI
定理9(证明(5,续) 前提:彐X(XRyX∈A,x(XRy→>-X∈B) 结论:彐X(XRy^XEA-XEB) 证明:(1)3X(×RyAX∈A,前提引入 (2) CRyAC∈A,(1E (3)x(XRy→X∈B,前提引入 (4)CRy→-C∈B,③3)U (5)CRy, (2)化简 6)-c∈B, (4)(5)假言推理 《集合论与图论》第6讲
《集合论与图论》第6讲 20 定理9(证明(5),续) 前提: ∃x(xRy∧x∈A), ∀x(xRy→¬x∈B) 结论: ∃x(xRy∧x∈A∧¬x∈B) 证明: (1) ∃x(xRy∧x∈A), 前提引入 (2) cRy∧c∈A, (1)EI (3) ∀x(xRy→¬x∈B), 前提引入 (4) cRy→¬c∈B, (3)UI (5) cRy, (2)化简 (6) ¬c∈B, (4)(5)假言推理