Part (a)

Problem

Determine whether or not \(((P\to Q)\lor (Q\to P))\) is a tautology.

Solution

I will show that, indeed, the formula is a tautology. The only time when the formula would be false is if there exists a truth assignment \(v\) for which both \((P\to Q)\) and \((Q\to P)\) are false. Suppose that this is the case. Then \((P\to Q)\) being false implies that \(v(P) = T\) and \(v(Q) = F\). But then this would implie that \((Q\to P)\) is true, a contradiction. Thus, such a truth assignment does not exist, so that all truth assignments satisfy the formula, i.e. the formula is a tautology.

Part (b)

Problem

Determine whether or not \(((P\land Q)\to R)\) tautologically implies \(((P\to R)\lor(Q\to R))\)

Solution

I will show that there is a tautological implication by using a truth table.

\begin{array}{|c|c|} P & Q & R& (P\land Q)& (P\to R)& (Q\to R)&((P\land Q)\to R) & ((P\to R)\lor(Q\to R))
\hline T & T & T &T & T&T&T&T
T & F & F &F&F&T&T&T\ F & T & F & F&T&F&T&T\ F & F & T & F&T&T&T&T\ T & T & F & T&F&F&F&F
T & F & T & F&T&T&T&T\ F & T & T & F&T&T&T&T\ F & F & F & F&T&T&T&T\ \end{array} Since all the truth assignments which satisfy \(((P\land Q)\to R)\) also satisfy \(((P\to R)\lor(Q\to R))\), there is a tautological implication.