# Using a calculation to show this formula is a tautology

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

• In our text this means that R is a stronger proposition than $Q \lor R$. Like so: $False \vDash P \land Q \vDash P \vDash P \lor Q \vDash True$. False being the strongest proposition, True the weakest. Nevertheless, what you say holds in this definition. P holds true in every instance $P \lor Q$ holds true. – Apeiron Feb 18 '15 at 18:41

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.

• I took me some truth tables & wikipedia to see absorption, but thanks :) Excatly what I needed! – Apeiron Feb 19 '15 at 7:50

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

• Yeah, but I'm specifically asked to show a calculation using the things 'I know' in this chapter. Reasoning like this is treated further along the text (amazon.com/Logical-Reasoning-A-First-Course/dp/095430067X) – Apeiron Feb 18 '15 at 18:21
• Alas, I don't have that book, so it's going to be hard to judge what you're restricted to. Still, I find it very strange that you couldn't use a basic tautology such as $R \Rightarrow (Q \lor R)$ in some way. Regardless of context, it's safe to say you've digested the most important things. – Ken Feb 18 '15 at 18:47