1
$\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$
1
  • $\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, 2015 at 18:41

2 Answers 2

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$
1
  • $\begingroup$ I took me some truth tables & wikipedia to see absorption, but thanks :) Excatly what I needed! $\endgroup$
    – Apeiron
    Feb 19, 2015 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$
2
  • $\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, 2015 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, 2015 at 18:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .