Verify that $\bigl(p\to(q\to r)\bigr)\to \bigl((p\to q)\to (p\to r)\bigr)$ is a tautology.

Question

Verify that $\bigl(p\to(q\to r)\bigr)\to \bigl((p\to q)\to (p\to r)\bigr)$ is a tautology.

I am confused on this whole tautology even after looking at examples both in my book and on-line. I started a truth table and this is what I have so far. Can someone please explain this to me in a way that I can understand.

\begin{array}{ccc} p & q & r & ? & ? & ? & ?\\ \hline T & T & T\\ T & T & F\\ T & F & T\\ T & F & F\\ F & T & T\\ F & T & F\\ F & F & T\\ F & F & F \end{array}

Answer 1

A completely different approach (called a tableau proof, and a bit on the informal side for one). Feel free to ignore.

1) Assume $p \implies (q \implies r)$.

2) Assume $p\implies q$.

<blockquote>
  <p>3) Assume $p$.</p>

  <blockquote>
    <p>4) By (2) and (3) and modus ponens, $q$.</p>

    <p>5) By (1) and (3) and modus ponens, $q \implies r$.</p>

    <p>6) By (4) and (5) and modus ponens, $r$.</p>
  </blockquote>

  <p>7) By (3)&ndash;(6) and implication, $p \implies r$.</p>
</blockquote>

<p>8) By (2)&ndash;(7) and implication, $(p\implies q)\implies (p\implies r)$.</p>

9) By (1)–(8) and implication, $\bigl(p\implies (q\implies r)\bigr)\implies \bigl((p\implies q)\implies (p\implies r)\bigr)$.

Answer 2

The following solution does not use a full truth table, so may not be the intended solution.

How could $\bigl(p\to(q\to r)\bigr)\to \bigl((p\to q)\to (p\to r)\bigr)$ be false?

The sentence $\bigl(p\to(q\to r)\bigr)$ would have to be true, and the sentence $\bigl((p\to q)\to (p\to r)\bigr)$ would have to be false.

How could $\bigl((p\to q)\to (p\to r)\bigr)$ be false? The sentence $p\to q$ would have to be true, and $p\to r$ would have to be false. To make $p\to r$ false, we must have $p$ true and $r$ false. But if $p$ is true, to make $p\to q$ true, we need $q$ true.

To sum up, the only way that $\bigl((p\to q)\to (p\to r)\bigr)$ can be false if $p$ and $q$ are true and $r$ is false.

However, under these conditions, $\bigl(p\to(q\to r)\bigr)$ is false.

Thus there is no assignment of truth values to $p$, $q$, and $r$ such that $\bigl((p\to q)\to (p\to r)\bigr)$ is false and $\bigl(p\to(q\to r)\bigr)$ is true.

Answer 3

A great way to see results like this is with the help of the method of analytic tableaux. You take the negation of your formula and apply a series of contradiction-hunting rules to get

,

which is closed (meaning that each of its paths end in contradictions), which in turn implies that your original formula is indeed a tautology.

Can you see how this relates to the tables in the other answers?

Answer 4

A tautology is a statement that is always true. For propositions $a$ and $b$, $a\rightarrow b$ is logically equivalent to $\neg a\vee b$. If $a=b$, then $\neg a\vee b$ is logically equivalent to $\neg b\vee b$, which is a tautology. So one way to prove that the given statement is a tautology is to consider $$ a\equiv p\rightarrow\left(q\rightarrow r\right) $$ and $$ b\equiv\left(p\rightarrow q\right)\rightarrow\left(p\rightarrow r\right) $$ and show that $a$ and $b$ are logically equivalent. We can do this by checking the truth table:

\begin{array}{ccccc} p & q & r & p\rightarrow\left(q\rightarrow r\right) & \left(\left(p\rightarrow q\right)\rightarrow\left(p\rightarrow r\right)\right)\\ 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 1 & 1 & 1\\ 0 & 1 & 0 & 1 & 1\\ 0 & 1 & 1 & 1 & 1\\ 1 & 0 & 0 & 1 & 1\\ 1 & 0 & 1 & 1 & 1\\ 1 & 1 & 0 & 0 & 0\\ 1 & 1 & 1 & 1 & 1 \end{array}

(0 is false and 1 is true in the above)

Answer 5

Your well-formed formula is an instance of axioms schema 3 of the Łukasiewicz axiomatization of propositional logic. By the completeness of propositional logic, your wf is a tautology.