\usepackage{array}

Part (a)

Problem

Is \((((P\to Q)\to P)\to P)\) a tautology?

Solution

Yes, it is. To show this, we simply check the four possible truth assignment for \(P\) and \(Q\) \begin{array}{|c|c|c|c|c|c|} P & Q & (P\to Q)& ((P\to Q)\to P) & (((P\to Q)\to P) \to P)
\hline T & T & T &T & T
T & F & F &T & T\ F & T & T & F & T\ F & F & T & F & T\ \end{array} Since the given formula is true given any truth assignment for \(P\) and \(Q\), we conclude it is indeed a tautology.

Part (b)

Problem

Define \(\sigma_k\) recursively as follows: \(\sigma_0 = (P\to Q)\) and \(\sigma_{k+1} = (\sigma_k\to P\)). For which value of \(k\) is \(\sigma_k\) a tautology?

Solution

I will show that the only \(k\) for which \(\sigma_k\) is a tautology are the even \(k\geq 2\).

Suppose that \(\sigma_k\) is a tautology for some \(k\), then we have the following truth table: \begin{array}{|c|c|c|c|c|c|} P & Q & \sigma_k& \sigma_{k+1}= (\sigma_k\to P) & \sigma_{k+2} = (\sigma_{k+1}\to P)
\hline T & T & T &T & T
T & F & T &T & T\ F & T & T & F & T\ F & F & T & F & T\ \end{array} The truth table reveals that \(\sigma_{k+2}\) is also a tautology, and that \(\sigma_{k+1}\) is not.

Since part (a) showed that \(\sigma_2\) is a tautology, we then have that \(\sigma_4,\sigma_6,\sigma_8,\ldots\) are tautologies, and that \(\sigma_3,\sigma_5,\sigma_7,\ldots\) are not.

All that is left to check are \(\sigma_0\) and \(\sigma_1\). \(\sigma_0 = (P\to Q)\) and \(\sigma_1 = ((P\to Q)\to P\) are clearly not tautologies as showin in the truth table from part (a).

Therefore, the only \(k\) for which \(\sigma_k\) is a tautology are the even \(k\geq 2\).