Trying to prove, by symbol manipulation, that if $(P \rightarrow Q) \wedge (Q \rightarrow R) \rightarrow (P \rightarrow R)$
I am stuck after doing these steps:
(P $\rightarrow Q) \wedge (Q \rightarrow R) \rightarrow (P \rightarrow R$)
$(\neg P \vee Q) \wedge (\neg Q \vee R) \rightarrow (P \rightarrow R)$
$\neg [ (\neg P \vee Q) \wedge (\neg Q \vee R) ] \vee (\neg P \vee R)$
$[\neg (\neg P \vee Q) \vee \neg (\neg Q \vee R) ] \vee (\neg P \vee R)$
$(P \wedge \neg Q) \vee (Q \wedge \neg R) \vee (\neg P \vee R)$
I am really clueless by this point, this is the first problem propositional calculus problem I ever try. I was thinking maybe if there was some way to negate one of the Qs so I could then group them together then maybe I could get somewhere but I'm not sure how.
Sorry if this is a bad use of LaTex, its my first time using it.
Best Answer
You want to prove that your first formula (expression) is a tautology (has value true, whatever the truth values of the variables $P$, $Q$, $R$).
Use repeatedly the rewrite rule $$A\to B\quad \rightsquigarrow\quad \neg A\vee B \ .$$ The given expression is then equivalent to $$\neg\bigl((\neg P\vee Q)\wedge(\neg Q\vee R)\bigr)\vee(\neg P \vee R)\ .\tag{1}$$ According to $\neg(A\wedge B)=\neg A\vee\neg B$ and its dual the left part of expression $(1)$ is equivalent to $$\neg(\neg P\vee Q)\vee\neg(\neg Q\vee R)=(P\wedge\neg Q)\vee(Q\wedge\neg R)=P\vee\neg R\ .$$ This shows that $(1)$ is equivalent with $$(P\vee\neg R)\vee(\neg P \vee R)\ ,$$ which is certainly true.