So i have to prove that: $$\{\neg A\to B,A\to C,B\to D\}\vdash \neg C\to D$$ I can use logical axioms, modus ponens and 'metatheorems'.

Logical axioms:

  1. φ→(ψ→φ)
  2. (φ→(ψ→χ))→((φ→ψ)→(φ→χ))
  3. (¬φ→¬ψ)→(ψ→φ)

Also i can use modus ponens(the only rule i can use) and metatheorems enter image description here

Some thoughts:So i started experimenting with all $3$ tools i have, started asking myself is any of the hypotheses can give as something new using the logic axioms but then i stalled, and modus ponens can't do much on it's own knowing these hypotheses atleast.My next thought was that i have to use those 2 metatheorems in order to actualy prove one part of $\neg C\to D$ (based on metatheorem 2) meaning i use as a hypothesis $\neg C$ to prove $D$ but i am stuck and i don't undestand even how to start.



1) Using Modus Ponens and your Metatheorem 1, prove Hypothetical Syllogism :

$\varphi \to \psi, \psi \to \chi \vdash \varphi \to \chi$.

2) Using axioms, prove Contraposition :

$(\varphi \to \psi) \vdash (\lnot \psi \to \lnot \varphi)$.

Finally, use them to derive :

$\lnot C \to B, B \to D \vdash \lnot C \to D$.

  • $\begingroup$ Thank You, i add the solved problem so anyone can benefit. $\endgroup$ – Agaeus Dec 14 '18 at 11:23

From contraposition have A->C to ~C->~A and from metateorem 1 my problem becomes {~A→B,~C→~A,B→D,~C}⊢ D

  1. ~C 2.~C->~A
  2. ~A MP 2,1 4.~A->B
  3. B MP 4,3 6.B->D
  4. D MP 5,6

Which gives us that our hypothesis ~C is correct and the original is proven.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.