Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Sep 10, 2007 #1
    1. The problem statement, all variables and given/known data

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

    2. Relevant equations

    Logical equivalences.

    3. The attempt at a solution

    \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) \\

    What now?
  2. jcsd
  3. Sep 11, 2007 #2
    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.
  4. Sep 11, 2007 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    As SiddharthM says, you should just expand all you implications (there are two left) as not ors. Or write out a truth table.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook