0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Apeiron Feb 18 '15 at 18:41
1
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Apeiron Feb 18 '15 at 18:21
  • $\begingroup$ 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. $\endgroup$ – Ken Feb 18 '15 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.