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

Question

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,

• reductio ad absurdum,

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

Any help please?

Answer 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

...

{1} n. [some contradiction]

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

Answer 2

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)

Answer 3

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

Answer 4

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.

Any help please?