Show that $(p \rightarrow q) \land (q \rightarrow r) \rightarrow (p \rightarrow r)$ is a tautology.

Question

Given there are 3 logical variables $p$, $q$ ,$r$. Show that $(p \rightarrow q) \land (q \rightarrow r) \rightarrow (p \rightarrow r)$ is a tautology

And here is my steps: $\neg(p\rightarrow q) \land (q\rightarrow r) \lor (p\rightarrow r)$

What should I do in order to get rid of it? ps: I am studing from Discrete mathematics and its application 7th edition rosen thanks

The easiest way to show this is a tautology is by truth tables. — NasuSama, Jan 13 '14 at 21:38
Yes but don't have to use truth table but using logcial equivlance — JAWA, Jan 13 '14 at 21:39

score 5 · Answer 1 · answered Jan 13 '14 at 21:45

$$\begin{array}{cl} &\left(p\Longrightarrow q\right) \land \left(q \Longrightarrow r\right) \Longrightarrow \left(p\Longrightarrow r\right) \\ \Longleftrightarrow & \neg \left(\left(\neg p \lor q \right) \land \left(\neg q \lor r \right)\right)\lor \left(\neg p \lor r\right) \\ \Longleftrightarrow & \neg \left(\neg p \lor q \right) \lor \left(\neg q \lor r \right)\lor \left(\neg p \lor r\right) \\ \Longleftrightarrow & \left(p \lor \neg q\right) \lor \left(\neg q \lor r\right) \lor \left(\neg p \lor r\right) \\ \Longleftrightarrow & \left(p \lor \neg p\right) \lor \left(q \lor \neg q\right) \lor \left(r \lor \neg r\right) \\ \Longleftrightarrow & 1 \end{array} $$

borg · Answer 2 · 2014-01-13T21:50:43.170

1

If you don't want to use the truth tables just try to bring your formula to conjunctive normal form or disjunctive normal form then apply appropriate theorem and you're done.

edited Jan 13 '14 at 21:50

answered Jan 13 '14 at 21:42

borg

811
6
11

Show that $(p \rightarrow q) \land (q \rightarrow r) \rightarrow (p \rightarrow r)$ is a tautology.

2 Answers2

Linked