How to show that $p∨q, q∨r, p\to ¬r ⊢ q$?

Question

How to prove $p∨q, q∨r, p\to ¬r ⊢ q$ using natural deduction?

I don't really know how to go about it since I have 2 or statements, but here is my try.

1. $p∨q$ premise

2. $q∨r$ premise

3. $p\to ¬r$ premise

4. $p$ Assumption 1

5. $¬r$ $\to e 3,4$

6. $q$ Assumption 2

I am kinda lost and don't know if I have done right so far and how to continue.

Edit: I am only allowed to use the basic natural deduction rules such as elemination and introduction for disjunction, conjunction, implication and negation.

Answer 1

Heavens! If I'd been setting this as a natural deduction exercise, I'd have expected to see this as the most obvious derivation:

$$ \begin{array}{llll} 1)&p\lor q&&\text{Premise}\\ 2)&q\lor r&&\text{Premise}\\ 3)&p\to\neg r&&\text{Premise}\\ 4)&& p & \text{Assumption)}\\ 5)&& \neg r &\text{From 3, 4 by modus ponens}\\ 6)&& q&\text{From 2, 5, by however your system handles disjunctive syllogism)}\\ && --\\ 7)&& q &\text{Assumption}\\ 8)&q& &\text{From 1, 4-6, 7-7 by $\lor$-Elimination}\\ \end{array} $$ With the fine details depending, as noted, on how your preferred system delivers disjunctive syllogism and also on how exactly it handles $\lor$-Elimination. If disjunctive syllogism isn't basic in your system, you need to plug in whatever works from the basic rules you are allowed.

And not only is this the obvious proof strategy, there is a deeper reason to prefer something like this. For the argument is intuitionistically valid. So you shouldn't want to go via the intuitionistically unacceptable double negation rule as in @RyRy's proof, or by the equivalent rule used at the last step by Camelot, or by the intuitionistically unacceptable rule used in getting from 7 to 8 in @manoooh's proof.

Answer 2

For the sake of variety, I offer a proof by contradiction.

$ \begin{array}{lllll} \{ 1 \} & 1. & p ∨ q & \text{premise} & \\ \{ 2 \} & 2. & q ∨ r & \text{premise} & \\ \{ 3 \} & 3. & p \to ¬r & \text{premise} & \\ \{ 4 \} & 4. & ¬q & \text{Assumption for RAA} & \\ \{ 1,4 \} & 5. & p & \text{1,4 SI: Disjunctive Syllogism} & \\ \{ 1,3,4 \} & 6. & ¬r & \text{3,5 Modus Ponens} & \\ \{ 2,4 \} & 7. & r & \text{2,4 SI: Disjunctive Syllogism} & \\ \{ 1,2,3,4 \} & 8. & r \wedge ¬r & \text{6,7 Conjunction Introduction} & \\ \{ 1,2,3 \} & 9. & ¬¬q & \text{4,8 RAA} & \\ \{ 1,2,3 \} & 10. & q & \text{9 Double Negation Elimination} & \square \\ \end{array} $

Answer 3

I would not go down the path of assuming, but I would work directly with the premises:

$$ \begin{array}{lll} 1)&p\lor q&\text{Premise}\\ 2)&q\lor r&\text{Premise}\\ 3)&p\to\neg r&\text{Premise}\\ 4)&\neg q\to p&\text{Conditional equivalence 1)}\\ 5)&\neg q\to\neg r&\text{Hypothetical syllogism 4), 3)}\\ 6)&\neg r\to q&\text{Conditional equivalence 2)}\\ 7)&\neg q\to q&\text{Hypothetical syllogism 5), 6)}\\ 8)&q\lor q&\text{Conditional equivalence 7)}\\ 9)&q&\text{Tautology 8)} \end{array} $$

Answer 4

Why did you assume $p$? You are trying to derive the truth of $q$; it doesn't seem like you can derive that readily from your given premises; hence, you employ the next ready tactic: derivation by contradiction. Assume $\lnot q$ (now you are trying to derive 2 contradictory statements, hence concluding that your assumption was false). The choise to be made now is which statement you want to make a contradiction of. As a rule of thumb, it's always wise to derive the contradiction from a negation that you already have, in this case, since we already assumed $\lnot q$ in our subderivation, and that's the only sentence using a negation as it's main connective, we are going to try and derive $q$. Our premises are $p \lor q$, $q \lor r$, $p \to \lnot r$. The argument should follow properly as so:

1. $p \lor q$ (primary assumption)
2. $q \lor r$ (primary assumption)
3. $p \to \lnot r$ (primary assumption)
4. $\lnot q$ (auxiliary assumption)
5. $\lnot q \to r$ (line 2 implication)
6. $r$ (lines 4,5 conditional elimination)
7. $r \to \lnot p$ (line 3 transposition)
8. $\lnot p$ (lines 6,7 conditional elimination)
9. $\lnot p \to q$ (line 1 transposition)
10. $q$ (lines 8,9 conditional elimination)
11. $q$ (lines 4-10, negation elimination)

Note that lines 4 to 10 are within the subderivation (because the way I wrote it might be a little confusing).