4

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
Improve this question
1
  • 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
    Commented Oct 14, 2014 at 9:46

1 Answer 1

Reset to default
1

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

Improve this answer
2
  • 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
    Commented Oct 13, 2014 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
    Commented Oct 13, 2014 at 21:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .