# Using Natural Deduction to Prove that $p\implies q \vdash \lnot p \lor b$

I'm trying to prove that $$p\implies q \vdash \lnot p \lor b$$ only using rules of natural deduction, but am having a lot of difficulty. I was able to prove the other direction. Could anyone show me or point me to the right direction?

• Are you sure about $b$ ? – Mauro ALLEGRANZA Feb 8 at 12:56

I assume that you are trying to prove : $$p \to q \vdash \lnot p \lor q$$.

1) $$p \to q$$ --- premise

2) $$\lnot (\lnot p \lor q)$$ --- assumed [a]

3) $$\lnot p$$ --- assumed [b]

4) $$\lnot p \lor q$$ --- from 3) by $$\lor$$-intro

5) $$\bot$$ --- from 2) and 4)

6) $$p$$ --- from 3) and 5) by $$\lnot$$-elim, discharging [b]

7) $$q$$ --- from 1) and6) by $$\to$$-elim

8) $$\lnot p \lor q$$ --- from 7) by $$\lor$$-intro

9) $$\bot$$ --- from 2) and 8)

10) $$\lnot p \lor q$$ --- from 2) and 9) by $$\lnot$$-elim, discharging [a].