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

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.

• Hint: Assume ¬q, Can you produce a contradiction? Sep 24 at 19:57
• Obviously deriving a contradiction from $\neg q$ would classically work. But not intuitionistically, and yet this inference is intuitionistically valid. So it is nicer to use intuitionistically valid reasoning and good to get into the habit it of seeing when DN or LEM isn't needed. Sep 24 at 21:35

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.

• haha i am face smacking myself for not seeing the obvious use of or-elimination Sep 24 at 21:50
• Okay so I was going on the right path. Now that you have said it feels so obvious. Thank you so much for the clarification!!!!
– User
Sep 25 at 5:15

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}$$

• Follow up question, I am stuck at your step 9. How can step 8 help us draw a conclusion about step 9?
– User
Sep 25 at 5:11
• RAA (short for reductio ad absurdem) is a proof technique/inference rule that permits you to infer the negation of an assumed formula if a contradiction is derived from that assumption. On line $4$, I assumed $\neg q$. Under that assumption, I derived the contradiction $r \wedge \neg r$ on line $8$. Thus, according to RAA I am permitted to infer $\neg \neg q$, that is, the negation of my assumption, on line $9$. Sep 25 at 6:01
• In other words, the reasoning is as follows... either $A$ or $\neg A$ is true. If I assume $A$ is true and this results in a contradiction, then it cannot be the case that $A$ is true. Thus, it must be the case $\neg A$ is true. This is the essence of a proof by contradiction. Sep 25 at 6:04

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}$$

• The OP asked for a proof using basic natural deduction rules and neither conditional equivalence nor hypothetical syllogism would normally count. Sep 24 at 21:38

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