# How to prove : (( P → Q ) ∨ ( Q → R )) by natural deduction

Here's another of Tomassi's exercises I can't solve (Logic, page 106):

: (( P → Q ) ∨ ( Q → R ))

I have to use natural deduction and the only rules I know are:

• assumptions,

• modus ponendo ponens,

• modus tollendo tollens,

• double negation,

• conditional proof,

• v-introduction,

• v-elimination,

• and introduction,

• and elimination.

Tomassi's proof consists of 20 steps.

Thanks for the help.

This is my answer so far:

{1} 1. (P -> Q) v (Q->R) Assumption

{2} 2. P -> Q Ass for vE

{3} 3. P Ass for CP

{4} 4. ~Q Ass for RAA

{2,4} 5. ~P 2,4 MT

{2,3,4} 6. P & ~P 3, 5 &I

{2,3} 7. ~~Q 4, 6 RAA

{2,3} 8. Q 7 DNE

{2} 9. P -> Q 3, 8 CP

{2} 10. (P -> Q) v (Q->R) 9 vI

{11} 11. Q -> R Ass for vE

{12} 12. Q Ass for CP

{13} 13. ~R Ass for RAA

{11,13} 14. ~Q 11, 13 MT

{11,12,13} 15. Q & ~Q 12, 14 &I

{11,12} 16. ~~R 13, 15 RAA

{11,12} 17. R 16 DNE

{11} 18. Q -> R 12, 17 CP

{11} 19. (P -> Q) v (Q->R) 18 vi

{1} 20. (P -> Q) v (Q->R) 1, 2, 10, 11, 19 vE

I don't know how to discharge the assumption 1.

It doesn't help to start your proof with the statement that you are trying to prove. Indeed, (( P → Q ) ∨ ( Q → R )) should be the last line of your proof, not the first. So, your whole set-up for the proof is not good.

In his book, Tomassi lays out what he calls the 'golden rule':

ask: (i) is the conclusion a conditional? If it is, apply CP. If not, ask: (ii) are any or all of the premises disjunctions? If so, apply vE. If not, assume the negation of the desired conclusion and try the RAA strategy.

If you apply the golden rule to your problem, you'll find that you end up with the last strategy: negate the desired conclusion and try the RRA strategy. So, it'll look something like this:

{1} 1. ~(( P → Q ) ∨ ( Q → R )) Assumption for RAA

...

{} n+1. ~~(( P → Q ) ∨ ( Q → R )) 1,n RAA

{} n+2. (( P → Q ) ∨ ( Q → R )) n+1 DNE

Indeed, notice how both eliran's and Frank's proof look like this .... except neither is in Tomassi's format. Here is how you do the rest in Tomassi's format:

{1} 1. ~(( P → Q ) ∨ ( Q → R )) Assumption for RAA

{2} 2. Q Assumption for RAA

{3} 3. P Assumption

{2,3} 4. P&Q 2,3 &I

{2,3} 5. Q 4 &I (here is the augmentation trick again, see p. 53-54)

{2} 6. P → Q 3,5 CP

{2} 7. ( P → Q ) ∨ ( Q → R ) 6 ∨I

{1,2} 8. (( P → Q ) ∨ ( Q → R )) & ~(( P → Q ) ∨ ( Q → R )) 1,7 &I

{1} 9. ~Q RAA 2,8

{10} 10. ~R Assumption for RAA

{2,10} 11. Q & ~R 2,10 &I

{2,10} 12. Q 11 &E (augmentation trick yet again!)

{1,2,10} 13. Q & ~Q 9,12 &I

{1,2} 14. ~~R 10,13 RAA

{1,2} 15. R 14 DNE

{1} 16. Q → R 2,15 CP

{1} 17. ( P → Q ) ∨ ( Q → R ) 16 ∨I

{1} 18. (( P → Q ) ∨ ( Q → R )) & ~(( P → Q ) ∨ ( Q → R )) 1,17 &I

{} 19. ~~(( P → Q ) ∨ ( Q → R )) 1,18 RAA

{} 20. (( P → Q ) ∨ ( Q → R )) 19 DNE

Since the argument has no premises, we must start with an assumption, either for reductio or for conditional proof. In this case, conditional proof would not work, so we have to go with reductio. So we start with:

``````1. | ~((P→Q)∨(Q→R))        assumption
``````

Since we're going for reductio, we need to derive a contradiction. Since all we've got is this assumption, our contradiction is going be with its negation. So we have to generate `(P→Q)∨(Q→R)`. How? By generating one of the disjuncts. So add another assumption for another reductio.

``````2. || ~(P→Q)               assumption
``````

Getting a contradiction from this is a bit complicated, but that's how the proof proceeds. Here's the complete proof:

`````` 1. | ~((P→Q)∨(Q→R))                assumption (for reductio)
2. || ~(P→Q)                       assumption (for reductio)
3. ||| Q                           assumption (for reductio)
4. |||| P                          assumption (for conditional)
5. |||| Q                          3
6. ||| P→Q                         4-5 (conditional)
7. ||| (P→Q)&~(P→Q)                6,2 (&-intro)
7. || ~Q                           3-7 (reductio)
8. ||| Q                           assumption (for conditional)
9. |||| ~R                         assumption (for reductio)
10. |||| Q&~Q                       7,8 (&-intro)
11. ||| R                           9-10 (reductio)
12. || Q→R                          8-11 (conditional)
13. || (Q→R)∨(P→Q)                  12 (∨-intro)
14. || ((Q→R)∨(P→Q))&~((Q→R)∨(P→Q)) 13,1 (&-intro)
15. | P>Q                           2-14 (reductio)
16. | (P→Q)∨(Q→R)                   15 (∨-intro)
17. | ((P→Q)∨(Q→R))&~((P→Q)∨(Q→R))  16,1 (&-intro)
18. (P→Q)∨(Q→R)                     1-17 (reductio)
``````
• Many thanks for your reply. Would you mind clarifying me the step number 5 please? Nov 25, 2018 at 16:08
• 5 is just a repetition of 3 (some proof systems require to repeat statements that are outside the current sub-proof), in order to get the conditional in 6.
– E...
Nov 25, 2018 at 16:10

Here is a proof similar to Eliran's. It uses reiteration (line 4) and indirect proof (lines 12 and 16) which I don't think were introduced prior to this exercise in Tomassi's text (page 106). I am presenting it in Klement's proof checker to show such a proof would work with different rules, but we have to use the permitted rules. Tomassi shows how to avoid reiteration on pages 63-4 by using first conjunction introduction and then conjunction elimination. This next proof replaces reiteration (lines 4 and 5) and indirect proof with contradiction introduction and double negation elimination (lines 13-14 and 18-19) that would correspond to reductio ad absurdum. This takes one less step than Tomassi required, however, I think it follows only the rules you are permitted to use. I will leave the final formatting of the proof to you.

References

Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/

P. D. Magnus, Tim Button with additions by J. Robert Loftis remixed and revised by Aaron Thomas-Bolduc, Richard Zach, forallx Calgary Remix: An Introduction to Formal Logic, Winter 2018. http://forallx.openlogicproject.org/

Paul Tomassi, Logic, Routledge 1999

• Thanks a lot Frank. This proof is not completely clear to me. Could you please explain me why the reiteration at line 4 is necessary? Why just don't firstly assume P and then get Q by MP? I don't understand lines 9,10,11 either. Please accept my apologies beforehand if these are rather silly questions but I'm a real beginner. Nov 26, 2018 at 18:18
• @DiegoRuizHaro The reiteration isn't necessary. It is a derived rule. I provided two proofs. The second one is what you may need. However, one cannot use modus ponens on the assumption in line 1 because there is a negation in front of it and it is part of a disjunction. To get P>Q we have to derive it. We also need Q after P for the conditional. On line 9, ~Q is the result of a reductio ad absurdum from lines 2-8. Line 10, Q, is an hypothesis. It is there to contradict with ~Q on line 9. Line 11 is ~R. What I want is R to derive Q>R on line 15. To get there I use reductio ad absurdum. Nov 26, 2018 at 23:58
• Thanks again. It's way clearer now. However, I can't discharge the dependency number 11. What did I get wrong? Nov 28, 2018 at 17:15
• @DiegoRuizHaro An example of how to do this is in Tomassi's text on page 103. What I provided would have to be converted to his system using a reduction ad absurdum subproof rather than the contradiction introduction that I used. To do this, line 11 is still "~R" but with justification "Assumption for RAA". Line 12, however, would be "Q & ~Q" with justification "9,10 &I" Then on line 13 we still have "~~R" but with justification "11,12 RAA". That would allow you to discharge the assumption on line 11. Nov 28, 2018 at 17:28
• Indeed, I did it that way. So according to that, the dependency numbers for line 9 is {1}, for line 10 is {10}, line 11 {11}, line 12 {1,10}, line 13 {1,10,11}. And then I'm able to discharge {10} at line 15 with 10,14 CP, and {1} at line 18 with 1,17 RAA. So {11} is still there. What did I do wrong? Nov 28, 2018 at 18:02

This is my answer so far:

{1} 1. (P -> Q) v (Q->R) Assumption

{2} 2. P -> Q Ass for vE

{3} 3. P Ass for CP

{4} 4. ~Q Ass for RAA

{2,4} 5. ~P 2,4 MT

{2,3,4} 6. P & ~P 3, 5 &I

{2,3} 7. ~~Q 4, 6 RAA

{2,3} 8. Q 7 DNE

{2} 9. P -> Q 3, 8 CP

{2} 10. (P -> Q) v (Q->R) 9 vI

{11} 11. Q -> R Ass for vE

{12} 12. Q Ass for CP

{13} 13. ~R Ass for RAA

{11,13} 14. ~Q 11, 13 MT

{11,12,13} 15. Q & ~Q 12, 14 &I

{11,12} 16. ~~R 13, 15 RAA

{11,12} 17. R 16 DNE

{11} 18. Q -> R 12, 17 CP

{11} 19. (P -> Q) v (Q->R) 18 vi

{1} 20. (P -> Q) v (Q->R) 1, 2, 10, 11, 19 vE

I don't know how to discharge the assumption 1.