Prove $q \lor r \vdash (q \land s) \lor (s \to r)$ using natural deduction

Question

Am I going in the right direction? I'm stuck after this point and I don't really know what to do from here. I know I have to assume and introduce s but I'm unsure how.

1. q v r premise
2. q ʌ s assumption
3. q ʌe 2,3
4. s ʌe 2,4
5. r assumption

Answer 1

So, you start with a disjunction. Thus, you might manage to use disjunction elimination to solve this.

If you assume r, hopefully, you can see how you can get to ((q$\land$s)$\lor$(s$\rightarrow$r)).

Now suppose that you assume 1. q.

Next assume 2. $\lnot$((q$\land$s)$\lor$(s$\rightarrow$r)).

That hopefully will enable you to produce $\lnot$(q$\land$s).

Once you have that, hopefully you can produce ($\lnot$q$\lor$$\lnot$s).

But, we have q still in effect. So, hopefully you have some way that you can now produce $\lnot$s.

Hopefully then you can produce (s$\rightarrow$r) which makes getting to ((q$\land$s)$\lor$(s$\rightarrow$r) possible in one step.

Then we discharge 2. and somehow get to ((q$\land$s)$\lor$(s$\rightarrow$r)) with just 1. still under effect.

That hopefully makes using disjunction elimination with the premiss (q$\lor$r) possible.

Answer 2

Fitch style natural deduction. Unfortunately the excluded middle assumption on $s$ is not avoidable.

$$\begin{array} {rll} (1) & q \lor r & \text{Given} \\ \\ (2) & \quad \quad q & \text{Premise} \\ (3) & \quad \quad s \lor \lnot s & \text{Excluded Middle on s} \\ (4) & \quad \quad \quad \quad s & \text{Premise} \\ & \quad \quad \quad \quad \vdots & \text{Fill these in} \\ (5) & \quad \quad \quad \quad (q \land s) \lor (s \to r) & \\ \\ (6) & \quad \quad \quad \quad \lnot s & \text{Premise} \\ & \quad \quad \quad \quad \vdots & \text{Fill these in} \\ (7) & \quad \quad \quad \quad (q \land s) \lor (s \to r) & \\ \\ (8) & \quad \quad (q \land s) \lor (s \to r) & \text{Or Elimination of 3, 4 to 5, 6 to 7} \\ \\ (9) & \quad \quad r & \text{Premise} \\ & \quad \quad \vdots & \text{Fill in the dots} \\ (10) & \quad \quad (q \land s) \lor (s \to r) & \\ \\ (11) & (q \land s) \lor (s \to r) & \text{Or Elimination of 1, 2 to 8, 9 to 10} \\ \end{array}$$

That's the basic outline. Let me know if you need hints filling in the dots.