# Homework Help: Show that ((p implies q) and (q implies r)) implies (p implies r) is a tautology

1. Sep 10, 2007

### VinnyCee

1. The problem statement, all variables and given/known data

Show that $$\left[\left(p\,\longrightarrow\,q\right)\,\wedge\,\left(q\,\longrightarrow\,r\right)\right]\,\longrightarrow\,\left(p\,\longrightarrow\,r\right)$$ is a tautology.

2. Relevant equations

Logical equivalences.

3. The attempt at a solution

$$\begin{array}{l} \left[ {\left( {p\; \to \;q} \right)\; \wedge \;\left( {q\; \to \;r} \right)} \right]\; \to \;\left( {p\; \to \;r} \right) \\ \left[ {\left( {\neg p\; \vee \;q} \right)\; \wedge \;\left( {\neg q\; \vee \;r} \right)} \right]\; \to \;\left( {p\; \to \;r} \right) \\ \left\{ {\left[ {\left( {\neg p\; \vee \;q} \right)\; \wedge \;\neg q} \right]\; \vee \;\left[ {\left( {\neg p\; \vee \;q} \right)\; \wedge \;r} \right]} \right\}\; \to \;\left( {p\; \to \;r} \right) \\ \left\{ {\left[ {\left( {\neg p\; \wedge \;\neg q} \right)\; \vee \;\left( {q\; \wedge \;\neg q} \right)} \right]\; \vee \;\left[ {\left( {\neg p\; \wedge \;r} \right)\; \vee \;\left( {q\; \wedge \;r} \right)} \right]} \right\} \to \;\left( {p\; \to \;r} \right) \\ \left\{ {\left[ {\left( {\neg p\; \wedge \;\neg q} \right)\; \vee \;{\rm F}} \right]\; \vee \;\left[ {\left( {\neg p\; \wedge \;r} \right)\; \vee \;\left( {q\; \wedge \;r} \right)} \right]} \right\}\; \to \;\left( {p\; \to \;r} \right) \\ \left\{ {\left[ {\neg p\; \wedge \;\neg q} \right]\; \vee \;\left[ {\left( {\neg p\; \wedge \;r} \right)\; \vee \;\left( {q\; \wedge \;r} \right)} \right]} \right\}\; \to \;\left( {p\; \to \;r} \right) \\ \end{array}$$

What now?

2. Sep 11, 2007

### SiddharthM

Without any prior assumptions we need to assume (p->q) and (q->r) and from there show that p imples r. This may not be legit if your instructor wants a symbolic elimination of the "fluff". Symbollically: keep on working, you are no the right track - expand and cancel falsehoods or tautologies like you have been doing.

3. Sep 11, 2007

### matt grime

As SiddharthM says, you should just expand all you implications (there are two left) as not ors. Or write out a truth table.