Proof using natural deduction

Question

Prove that $$\lnot r\Rightarrow \lnot p,\lnot(q\lor r),s\Rightarrow(p\lor q)\models\lnot s $$

I'm completely stuck on this one. Only natural deduction inference rules can be used, no de morgan's law etc. The premises given all seem to be really irrelevant, and since we can't use transformational proof techniques, all the implications turn the first and third expressions into essentially garbage, and without de Morgan's law the second one seems useless too. How should I proceed?

Answer 1

Hint: After listing your given premises, start by assuming $\lnot\lnot s$ or $s$, and derive a contradiction, using your premises. E.g.

premises
$\quad\vdots\quad$

• $|$ Assume $s$

  • $\quad p\lor q$

EDIT: We can get assumption down to needing to find a contradiction from $p$. But, as noted in the comments, unless there is a typo in the questions statement, as written, this is not provable, as there exists a model (see Henno's comment) $p, s$ true, $q, r$ false, in which we have all premises true, but the conclusion false.

EDIT EDIT: Looks like we are now "good to go"...see comments.

Answer 2

In classical logic, you can derive a contradiction and then either introduce or get rid of a negation. Since you want to get a negation, you consequently might want to assume "s" and then derive a contradiction.

Anytime you have a disjunction, see if you can get both disjuncts to lead to the same conclusion, and then use disjunction elimination.

For your problem, here's an outline of a proof in one system, though I don't know what your rules say exactly, so I don't know what a proof will look like exactly in your system.

1 | s assumption (I assume s, so that I can try and find a contradiction.)

2 | (p $\lor$ q) (I'd hope I don't need the proof analysis as to how I got this)

3 || q assumption (I choose q, since if I have ¬(q∨r), I can easily get the negation of q)

4 || (q $\lor$ r) (disjunction introduction on 3)

5 | $\lnot$q (contradiction from one of the premises and 4)

6 || p assumption

7 | (p->p) (6-6 conditional introduction)

8 || q assumption (I want (q->p), so I start with q))

9 ||| $\lnot$p assumption (I want p, so I assume its negation since I already have a contradiction)

10|| p (6 and 8 contradict each other)

11| (q->p) (8-10 conditional introduction

12| p (2, 7, 11 disjunction elimination)

Now, that I have "p", I can get "r" in the same scope as "p" via the first premise (either I have modus tollens as a rule of inference, or I assume $\lnot$ r and derive a contradiction which gives me r). Then, since I have "r" I use disjunction introduction to (q $\lor$ r). But, that gives us a contradiction within the same scope as s. So, then we can introduce the negation of s within the same scope as the premises for this problem.