[Math] Natural deduction: how to prove the argument below

natural-deductionpropositional-calculus

Sorry my title is a bit vague, but I have a specific problem I'm trying to solve.

$$P \rightarrow Q \vdash \lnot(P\land\lnot Q)$$

I need to prove this using natural deduction, I can do it using equivalent symbols in propositional logic, but I can't seem to figure out where to even begin in terms of natural deduction.

I (mostly) understand the introduction and elimination rules for connectives, but I just don't know what to do here. I know I've got to turn the premise into the conclusion step by step using introduction and elimination of these logical connectives, but how?

Best Answer

1. P→Q     premise
  2. P∧¬Q    assumption
  3. P       ∧elim 2
  4. ¬Q      ∧elim 2
  5. Q       MP 1 3
  6. ⊥       4 5
7. ¬[P∧¬Q] ¬intro 2 6
Related Question