3
$\begingroup$

So yeah, the entire question is pretty much in the title. $$p \rightarrow q \vdash \lnot(p \land \lnot q)$$

I've been able to derive the reverse, but I don't how to logically go from the premise to the conclusion using natural deduction only. I can see that the two formulas are equal using transformations.

These are the rules I'm allowed to use: enter image description here

Please help me understand how to do this.

$\endgroup$
2
$\begingroup$

$1.$ $p \rightarrow q \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ -- (Premise)

$2.$ $p \wedge \neg q \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ -- (Assume the contrary to what has to be proved in the conclusion)

$3.$ $p \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ -- ($\wedge E$ on $2.$)

$4.$ $\neg q \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ -- ($\wedge E$ on $2.$)

$5.$ $q \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ -- (Modus ponens on $1.$ and $3.$)

$6.$ $\bot \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ -- (bot introduction due to contradiction on $4.$ and $5.$)

$7.$ $\neg(p \wedge \neg q) \ \ \ \ \ \ \ \ \ \ \ $ --(assumption wrong due to arrival of contradiction)

$\endgroup$
  • $\begingroup$ Fantastic, thank you. I knew I need to show $p \land \lnot q$ is false based on steps 3, 4 and 5, but I just couldn't think of the process. $\endgroup$ – Shiny_and_Chrome Jan 12 '17 at 6:06

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.