# Natural deduction: how to prove the argument below

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?

• By "natural deduction" I assume you are looking for a proof "by contradiction". That is, starting from $P \to Q$ and the hypothesis $(P \land \lnot Q)$, produce a contradiction. This seems a straightforward exercise. – hardmath Nov 18 '16 at 13:23
• Would you mind showing me how? I've got: $$1. P \rightarrow Q$$ $$2. \lnot P \lor Q$$ Using Implication elimination rule How do I get to the next step – Shiny_and_Chrome Nov 18 '16 at 14:59
• Instead you want: $$2. P \land \lnot Q$$ When this leads to a contradiction, you will be able say you've done the natural deduction proof. – hardmath Nov 18 '16 at 15:04
• Ok, from my understanding of propositional logic and truth tables, I understand why this is a contradiction and how that proves the original statement, but how do I show that in a natural deduction proof? E.g. $$P \land \lnot Q, Q \lor R \vdash R \lor S$$ $$1. P \land \lnot Q$$ $$2. Q \lor R$$ $$3. \lnot Q$$ $$4. R$$ $$5. R \lor S$$ – Shiny_and_Chrome Nov 18 '16 at 15:17

1. P→Q     premise