3
$\begingroup$

I was trying to prove this statement is a tautology without using truth tables. Something doesn't add it here as I keep getting stuck. Take a look please!

For statements, P, Q and R prove that that the statement $$ [(P \implies Q) \implies R] \lor [\neg P \lor Q]$$

It is possible to do this without truth tables right? Here is what I have so far! :)

The statement $(P \implies Q)$ can be collapsed into $(\neg P \lor Q)$. So we can replace the phrase $[(P \implies Q) \implies R]$ with $(\neg P \lor Q) \implies R$. Again, we can collapse that expression and get $(P \land \neg Q) \lor R)$. From here I am not sure where to go. There isn't even an $R$ in the expression $[\neg P \lor Q]$ ! Help would be greatly appreciated! Thank you :)

$\endgroup$
3
  • 2
    $\begingroup$ You can use \lor and \land for $\lor$ and $\land$. $\endgroup$
    – Brian M. Scott
    Apr 11, 2013 at 20:52
  • 1
    $\begingroup$ Thank you everyone! Very helpful indeed :) $\endgroup$
    – nicefella
    Apr 11, 2013 at 21:14
  • $\begingroup$ You’re welcome. $\endgroup$
    – Brian M. Scott
    Apr 11, 2013 at 21:21

3 Answers 3

Reset to default
2
$\begingroup$

You’ve done much of it. You have

$$\Big((P\land\neg Q)\lor R\Big)\lor(\neg P\lor Q)\;,$$

but you’d be better off backing up a step to

$$\Big(\neg(\neg P\lor Q)\lor R\Big)\lor(\neg P\lor Q)\;.$$

Now rewrite this as

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

and notice that the big parenthesis is of the form $\neg S\lor S$.

You can instead work directly from what you already have, if you want:

$$\begin{align*} (P\land\neg Q)\lor(\neg P\lor Q)&\equiv\Big(P\lor(\neg P\lor Q)\Big)\land\Big(\neg Q\lor(\neg P\lor Q)\Big)\\ &\equiv\Big((P\lor\neg P)\lor Q\Big)\land\Big(\neg P\lor(\neg Q\lor Q)\Big)\\ &\equiv(\top\lor Q)\land(\neg P\lor\top)\\ &\equiv\top\land\top\\ &\equiv\top\;. \end{align*}$$

$\endgroup$
2
$\begingroup$

Applying the same equivalence you used in the first transformation:

From $$((\lnot P \lor Q)\rightarrow R) \lor (P \lor Q)$$

You get $$(\color{blue}{\bf\lnot (\lnot P \lor Q)} \lor R ) \lor \color{blue}{\bf (\lnot P \lor Q)}$$

Which is necessarily true because the law of the excluded middle:

$$\lnot(\lnot P \lor Q) \lor (\lnot P \lor Q)$$ is necessarily true. And $T \lor R$ is necessarily true.

$\endgroup$
4
  • $\begingroup$ Is this clear now? You have three statements "or'd", and two of them are necessarily true, together, giving us $T \lor R$: If one of two terms in a disjunction is true, then the disjunction as a whole is necessarily true. $T \lor R = $ True. Hence the statement is indeed a tautology, necessarily true. $\endgroup$
    – amWhy
    Apr 11, 2013 at 21:17
  • $\begingroup$ Oh yes! Makes perfect sense! Thank you :) $\endgroup$
    – nicefella
    Apr 11, 2013 at 22:03
  • $\begingroup$ When OPs answer like that - it is nice! +1 $\endgroup$
    – Amzoti
    Apr 12, 2013 at 0:32
  • $\begingroup$ Yes, indeed. nicefella's always responsive and shows work, and such. nicefella is a model "asker" for the site. $\endgroup$
    – amWhy
    Apr 12, 2013 at 0:35
1
$\begingroup$

You're almost there.

(¬P∨Q)⟹R = ¬(¬P∨Q)∨R

¬(¬P∨Q)vR∨(¬P∨Q)

Let (¬P∨Q) = A. Then you have ¬A v R v A. So you have NOT A or A. Which is always true.

$\endgroup$

You must log in to answer this question.

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