Using a calculation to show this formula is a tautology

Question

In a chapter regarding strenghtening and weakening of propositions, the following is asked:

Show with a calculation that the following is a tautology:

$$( R \land (P \Rightarrow Q)) \Rightarrow ((R \Rightarrow P) \Rightarrow Q) $$

I'm not sure I'm on the right track with my solution or if I'm missing steps. Here goes:

To show this, it is enough to show that

$$( R \land (P \Rightarrow Q)) \vDash ((R \Rightarrow P) \Rightarrow Q) $$

I begin by rewrting the right hand side.

1) Implication, twice:

$$ \neg (\neg R \lor P) \lor Q $$

2) De morgan

$$ (\neg \neg R \land \neg P) \lor Q$$

3) Double negation

$$ (R \land \neg P) \lor Q$$

4) Distribution and implication

$$ (Q \lor R) \land (P \Rightarrow Q) $$

Now, by the standard weakening rules I know that $ R \vDash Q \lor R$

So this concludes the proof that $$( R \land (P \Rightarrow Q)) \vDash ((R \Rightarrow P) \Rightarrow Q) $$

and thus ive shown $$( R \land (P \Rightarrow Q)) \Rightarrow ((R \Rightarrow P) \Rightarrow Q) $$ is a tautology.

Now, does this make any sense :) Especially the weakening part. Can I use that rule like this?

Text used: http://www.amazon.com/Logical-Reasoning-A-First-Course/dp/095430067X in which $P \vDash Q$ is specified as meaning 'P is a stronger proposition than Q'. False being the strongest, true being the weakest: $$ False \vDash P \land Q \vDash P \vDash P \lor Q \vDash True$$

Answer 1

Don't start on the RHS, start on the LHS.

$$\begin{align} & R \wedge (P\to Q) \\ \iff & \text{implication equivalence} \\ & R\wedge (\neg P \vee Q) \\ \iff & \text{distribution} \\ & (R\wedge \neg P)\vee (R\wedge Q) \\ \iff & \text{distribution} \\ & [(R\wedge \neg P)\vee R]\wedge [(R\wedge \neg P)\vee Q] \\ \iff & \text{absorption} \\ & R\wedge [(R\wedge \neg P)\vee Q] \\ \iff & \text{double negation then DeMorgan's} \\ & R\wedge [\neg (\neg R\vee P)\vee Q] \\ \iff &\text{implication equivalence} \\ & R\wedge [\neg (R\to P)\vee Q] \\ \iff &\text{implication equivalence} \\ & R\wedge [(R\to P)\to Q] \end{align}$$

Now $R\wedge S \to S$ is a tautology, and we have the RHS as $S$, so we're done.

$$\therefore (R\wedge (P\to Q))\to ((R\to P)\to Q))$$

---

Alt. $R\wedge S \vDash S$ if you prefer.

Answer 2

$R \Rightarrow (Q \lor R)$ is certainly a tautology, so you can use it.

Put another way, you can assume $R \land (P \Rightarrow Q)$. So now you have $R$ as well as $P \Rightarrow Q$. From the above tautology and $R$, you have $Q \lor R$. Hence, you have $(Q \lor R) \land (P \Rightarrow Q)$, which you've already established as being equivalent to $((R \Rightarrow P) \Rightarrow Q)$.

Hence, $(R \land (P \Rightarrow Q)) \Rightarrow ((R \Rightarrow P) \Rightarrow Q)$.