# Propositional Logic - Deduction

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

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.

Hint

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$$.

• Thank You, i add the solved problem so anyone can benefit. – 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.