Propositional Logic: Prove $(p \land \lnot q) \to \lnot p \vdash p \to q$.

Question

I'm having a lot of trouble trying to solve this. Any help would be greatly appreciated, I just can't seem to go any further!

"Give syntactic proofs for the following sequent using only propositional logic rules."

And the proof to prove is:

$$ p \land \neg q \rightarrow \neg p \vdash p \rightarrow q $$

I tried to assume p ( to use the -> introduction rule) and then use the MT to get $$ \neg (p \land \neg q) $$ but I get into this loop of introducing negations and trying to solve bottom!!

Answer 1

Here is a natural deduction proof done fitch style (you can easily re-arrange the proof into other styles):

$(p \land \neg q) \to \neg p\\ \quad | \quad p\\ \quad | \quad \quad | \quad \neg q\\ \quad | \quad \quad | \quad (p \land \neg q)\\ \quad | \quad \quad | \quad \neg p\\ \quad | \quad \quad | \quad \bot\\ \quad | \quad \neg\neg q\\ \quad | \quad q\\ p \to q $

There should be nothing mysterious here. You want to prove the conditional $p \to q$, so you assume $p$ and aim for $q$. Having made that temporary assumption where next? The only sensible option is to make a second temporary assumption $\neg q$ so you get the antecedent of the conditional premiss. And with those proof hints, the rest writes itself!

I've left the line numbers on the left and the commentary on the right for you to fill in (but they are optional anyway in most versions of natural deduction systems).