# Using natural deduction rules give a formal proof

With exams just around the corner I am really struggling with formal proofs.

Using natural deduction rules give a formal proof of Q from the premises

``````(¬P → Q)∧(R → ¬Q)
¬Q → ¬S
¬S → (R ∧ ¬P)
``````

So the strategy I have been trying is to get to a point where I can prove ¬P → Q, but for that to work I first need to prove ¬P but I'm afraid that is where it all falls apart, I have no idea where to start to prove ¬P

This is the final answer I came up with thanks to help from @shane

`````` 1. (¬P → Q)∧(R → ¬Q)
2. ¬Q → ¬S
3. ¬S → (R ∧ ¬P)
4. (¬P → Q)     ∧elim: 1
|  5. ¬Q
|  6. ¬S        →elim: 2,5
|  7. R ∧ ¬P    →elim: 6,3
|  8. ¬P        ∧elim: 7
|  9. Q         →elim: 8,4
| 10. ⊥         ⊥intro: 5,9
11. ¬¬Q          ¬intro: 5-10
12. Q            ¬elim 11
``````
• It's often a good strategy to start from your conclusion (until you are blocked then go back to the premisses). Here the conclusion is Q, so start assuming not-Q to prove a contradiction. – Quentin Ruyant Oct 14 '14 at 9:46

(4) if not P then Q. (by 1 conjunction elimination)

(5) if R then not Q. (by 1, conjunction elimination).

(6) Suppose not Q. (assumption)

(7) Not S, by 2, 6, (conditional elimination)

(8) R and not P (7, 3, conditional elimination)

(9) not P (8, conjunction elimination).

(10) not not P, (by 6,4 modus tollens)

(11) P (10 double negation elimination).

(12) Contradiction (P and not P by conjunction introduction on 9 and 11)

(13) Therefore Q, (by conditional proof 6-12)

• I should have pointed out that I need to do my proofs in Fitch and do not have access to modus tollens, but this answer did guide me in the right direction. – Leon Oct 13 '14 at 21:35
• yeah all you'd need to do is to introduce an additional subproof. the crucial bit is to assume not-Q and get to work from there. This is kind of an unusual problem, but when in doubt just start applying the rules you know to the premises you've got. then re-evaluate and see how you can get to what you want. I didn't see any obvious way to get to the Q from the premises given, so it seemed reasonable to me to try assuming the opposite and proving a contradiction. Good luck. – user5172 Oct 13 '14 at 21:42