Propositional Logic Proof using I.P. or C.P or rules of inference

Question

I'm attempting to solve a proof my professor asked. We are able to use any of the rules of inference, Indirect Proof or Conditional Proof. Every time I think am making progress I run into a brick wall. Here is the question.

1. $Q \lor (R \rightarrow S)$
2. $[R \rightarrow (R \rightarrow S)] \rightarrow (T \lor U)$
3. $(T \rightarrow Q) \land (U \rightarrow V)$
4. Conclusion: $Q \lor V$

I believe the easiest solution would be to attain $(T \lor U)$ from line 2 and then use as a Constructive Dilemma with line 3 but I'm really struggling to get past the $[R \rightarrow (R \rightarrow S)]$ part in order to get $(T \lor U)$. If anyone can help it would be greatly appreciated.

edit* I got by the previously mentioned part, but I am now struggling to get $(R \rightarrow S)$ from line one.

Translations:

• "$\supset = \rightarrow$"(if...then)
• "$\bullet = \land$"(and)
• ~ = $\lnot$(not)

here is my work thus far. I have been trying any and everything for the past 4 hours and I have no idea where I am going from here.

Answer 1

1. [Q∨(R→S)] assumption

2. {[R→(R→S)]→(T∨U)} assumption

3. [(T→Q)∧(U→V)] assumption

4. [~~Q∨(R→S)] 1 double negation

5. [~Q→(R→S)] 4 material implication

6. [~Q→((R∧R)→S)] 5 ∧ tautology

7. [~Q→((R→(R→S)] 6 exportation

8. [~Q→(T∨U)] 7, 2 hypothetical syllogism

9. (U→V) 3 simplification (this step isn't correct... we first have to use ∧ commutativity, and then use simplification.. shall I edit this to make this explicit, or is this clear enough?).

10. [~Q→(~~T∨U)] 8 double negation

11. [~Q→(~T→U)] 10 material implication

12. [(~Q∧~T)→U) 11 exportation

13. [(~Q∧~T)→V] 12, 9 hypothetical syllogism

14. [(~T∧~Q)→V] 13 ∧ commutation

15. [~(T∨Q)→V] 14 De Morgan

16. [~~(T∨Q)∨V] 15 material equivalence

17. [(T∨Q)∨V] 16 double negation

18. [T∨(Q∨V)] 17 associativity

19. [(Q∨V)∨T] 18 ∨ commutativity

20. (T→Q) 3 simplification

21. [~~(Q∨V)∨T] 19 double negation

22. [~(Q∨V)→T] 21 material implication

23. [~(Q∨V)→Q] 21, 19 hypothetical syllogism

24. [~~(Q∨V)∨Q] 23 material implication

25. [(Q∨V)∨Q] 24 double negation

26. [(V∨Q)∨Q] 25 ∨ commutativity

27. [V∨(Q∨Q)] 26 associativity

28. [V∨Q] 27 ∨ tautology

29. [Q∨V] 28 ∨ commutativity

Answer 2

It turns out $R \rightarrow (R \rightarrow S)$ is actually equivalent to $R \rightarrow S$. You can show this in a couple of different ways: use Material Equivalence twice, plus the associative and commutative laws for disjunction, or alternatively, use exportation. (For the latter, though, you'd need some extra lines to justify turning $R \wedge R$ into $R$, since this doesn't appear to be one of your allowed equivalences.)

How to fit this into an overall solution, based on Indirect Proof: Suppose the desired conclusion is false, which by De Morgan and Simplification gives you both $\neg Q$ and $\neg V$. By Disjunctive Syllogism you then obtain $R \rightarrow S$, and after applying the aforementioned equivalence followed by Modus Ponens, you arrive at $T \vee U$. Simplifying the third premise and applying a Constructive Dilemma gets you to $Q \vee V$, a contradiction.

Answer 3

We can "formalize" Dave's answer, using Indirect Proof :

1) $\lnot (Q \lor V) \equiv (\lnot Q \land \lnot V)$ --- assumed [1] and using (DM)

2) $\lnot Q$ --- from 1) by (Simp)

3) $R \rightarrow S$ --- from premise 1. and 2) by (DS)

4) $(R \land R) \rightarrow S$ --- from 3) by (Taut)

5) $R→(R→S)$ --- from 4) by (Exp)

6) $T \lor U$ --- from premise 2. and 5) by (MP)

7) $Q \lor V$ --- from 6) and premise 3. by (CD)

but 7) contradicts 1); thus we have :

9) $Q \lor V$ --- by Indirect Proof, discharging [1].

Conclusion :

$Q∨(R→S), [R→(R→S)]→(T∨U), (T→Q)∧(U→V) \vdash Q \lor V$.