Truth Tables for Tautology and Contradiction Proofs in Propositional Logic

In propositional logic, a truth table lets us verify whether a compound proposition is a tautology or a contradiction.

We will use the standard equivalence for implication:
$(p \to q) \equiv (\neg p \lor q).$
This allows each row of a truth table to be computed mechanically.

Key connectives and how to evaluate them

For any truth assignment:

• negation: $\neg p$
• conjunction: $p \land q$
• disjunction: $p \lor q$
• implication: $p \to q$

Using implication as disjunction: $p \to q \equiv \neg p \lor q.$

(i) Show $((p \\to (q \\to r)) \\to ((p \\to q) \\to (p \\to r)))$ is a tautology

Let $F = (p \to (q \to r)) \to ((p \to q) \to (p \to r)).$

We build a truth table for $p,q,r$ (8 rows) and compute $F$ row-by-row.

Truth table computation

We will compute key subexpressions per row:

• $A = (q \to r)$
• $B = (p \to A) = (p \to (q \to r))$
• $C = (p \to q)$
• $D = (p \to r)$
• $E = (C \to D) = ((p \to q) \to (p \to r))$
• $F = (B \to E) = ( (p \to (q \to r)) \to ((p \to q) \to (p \to r)) )$

Remember: $X \to Y \equiv \neg X \lor Y.$

Because Coursify tables must be rendered as markdown/HTML rather than interactive chart tables, here is the standard truth-table layout explicitly:

Let’s compute cleanly (using $q\to r \equiv \neg q \lor r$ and then repeatedly $X\to Y\equiv \neg X\lor Y$). The correct completed table is:

Thus $F$ evaluates to T in every row, so: $((p \to (q \to r)) \to ((p \to q) \to (p \to r)))$ is a tautology.

(ii) Show $\neg(q \to r)\ \land\ r\ \land\ (p \to q)$ is a contradiction

Let $G = \neg(q \to r)\ \land\ r\ \land\ (p \to q).$

A contradiction means $G$ must be false for every truth assignment to $p,q,r$.

Key observation from implication

Start with: $q \to r \equiv \neg q \lor r.$

If $\neg(q \to r)$ is true, then $(q \to r)$ must be false. The only way an implication is false is:

• $q \to r$ is false exactly when $q = T$ and $r = F$.

So from $\neg(q\to r)$ true, we get: $q = T \quad \text{and} \quad r = F.$

But $G$ also contains the conjunct $r$ (i.e., it requires $r=T$).

So $\neg(q\to r)$ forces $r=F$, while $r$ forces $r=T$—cannot both hold in the same row.

Formally, in every valuation:

• If $\neg(q\to r)$ is true, then $r$ must be false, so the conjunction with $r$ becomes false.
• If $\neg(q\to r)$ is false, then the whole conjunction is false.

Therefore $G$ is false in all rows.

(Optional) Micro-truth-table for the critical part

The only potentially nontrivial part is $\neg(q\to r)\land r$; the $(p\to q)$ conjunct is irrelevant once that is already impossible.

So $\neg(q\to r)\land r$ is always F, and therefore: $G=\neg(q \to r)\land r\land(p\to q)$ is always F, i.e., a contradiction.