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!!


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

  • $\begingroup$ you forgot a $\neg$ in the premise ... $\endgroup$ – Bram28 Dec 31 '17 at 0:14
  • $\begingroup$ Ah I get it!! So you assume ~q, hoping to get bottom and then to introduce another negation to ~q getting ~~q, then we can eliminate the double negation to just get q. Thank you so much, I was making it a lot harder on myself. So happy now!! $\endgroup$ – xcx123 Dec 31 '17 at 0:44
  • $\begingroup$ And by hoping to get bottom I mean just using the ~i rule! $\endgroup$ – xcx123 Dec 31 '17 at 0:48

Below a proof using only replacement rules

(P&~Q) --> ~P ______________Given

↔ ~ ( P & ~Q) v ~P __________By definition of -->

↔ (~P v ~ ~Q) v ~P _________ By : DeMorgan’s rule

↔ (~P v Q) v ~P ____________ By : double negation

↔ ~P v ( Q v ~P) ____________ By : associativity of v

↔ ~ P v ( ~P v Q) ____________By : commutativity of v

↔ (~ P v ~P) v Q ___________ By : associacivity of v

↔ ~P v Q ___________________ By : idempotency of v

↔ P --> Q ___________________By : definition of -->


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.