Propositions and Truth Tables

Switch the connective and a new truth-table column fills in. All four cases sit side by side for comparison.

Two statements with identical columns mean the same thing. If the true rows and false rows match completely, the statements are equivalent. A statement and its contrapositive always match. The converse does not.

For example, 'if it rains, the ground gets wet' and 'if the ground is not wet, it did not rain' say the same thing. But 'if the ground is wet, it rained' can be false. A hose wets the ground too.

Examples & Exercises

Use a truth table to prove completely that $P \to Q$ is logically equivalent to its contrapositive $\lnot Q \to \lnot P$ .

Compute all four rows explicitly and explain why matching truth values in every row means logical equivalence.

(P \to Q) \;\equiv\; (\lnot Q \to \lnot P)

Connective: implication, contrapositive column shown: the

P \to Q

and

\lnot Q \to \lnot P

columns agree in all 4 rows, while the converse

Q \to P

column differs in the

(T, F)

row.

Show proof

By definition $P \to Q$ is $\lnot P \lor Q$ .
Compute the four rows explicitly.
$(P, Q) = (T, T)$ : $P \to Q = T$ , contrapositive $(\lnot Q) \to (\lnot P) = F \to F = T$ .
$(T, F)$ : $P \to Q = T \to F = F$ , contrapositive $T \to F = F$ .
$(P, Q) = (F, T)$ : $P \to Q = F \to T = T$ (an implication with a false antecedent is true), contrapositive $F \to T = T$ .
$(F, F)$ : $P \to Q = F \to F = T$ , contrapositive $T \to T = T$ .
So the row-by-row truth pairs are $(T,T), (F,F), (T,T), (T,T)$ — the two columns match in every row.
Matching truth values in every row means the two propositions take the same value under every assignment of truth values to $P$ and $Q$ .
Their "when is this true" answers coincide in every possible case, so the two propositions are logically equivalent.
This justifies proof by contrapositive: instead of $P \to Q$ we may prove the equivalent $\lnot Q \to \lnot P$ .

Prove De Morgan's law $\lnot(P \land Q) \iff (\lnot P) \lor (\lnot Q)$ with a truth table.

Compute both sides in all four rows, and observe in which rows the $\land$ column is $F$ .

\lnot(P \land Q) \;\iff\; (\lnot P) \lor (\lnot Q)

Connective: conjunction, contrapositive column shown: the

P \land Q

column is

T

only in the

(T, T)

row, and only in that row are

\lnot(P \land Q)

and

(\lnot P) \lor (\lnot Q)

both

F

Show proof

First the $P \land Q$ column: $(T,T) \to T$ , $(T,F) \to F$ , $(F,T) \to F$ , $(F,F) \to F$ — $T$ occurs only in the $(T, T)$ row. Hence the left side $\lnot(P \land Q)$ has the column $(F, T, T, T)$ in row order.
Now compute the right side $(\lnot P) \lor (\lnot Q)$ row by row.
$(T,T)$ : $F \lor F = F$ .
$(T,F)$ : $F \lor T = T$ .
$(F,T)$ : $T \lor F = T$ .
$(F,F)$ : $T \lor T = T$ .
So the right side also has column $(F, T, T, T)$ — matching the left side row by row.
Since the two columns agree in every row, $\lnot(P \land Q)$ and $(\lnot P) \lor (\lnot Q)$ are logically equivalent.
Observe: in exactly the three rows where $P \land Q$ is $F$ — i.e. where at least one of $P, Q$ is false — the right side is $T$ .
"Not both are true" says the same thing as "at least one is false".

Show that $P \to Q$ is NOT equivalent to its converse $Q \to P$ .

Exhibit the row $(P, Q) = (T, F)$ where they split, and instead prove the true equivalence $P \to Q \iff \lnot P \lor Q$ with a truth table.

(P \to Q) \;\not\equiv\; (Q \to P), \qquad (P \to Q) \;\equiv\; (\lnot P \lor Q)

Connective: implication, contrapositive column hidden: the

P \to Q

column

(T, F, T, T)

and the converse

Q \to P

column

(T, T, F, T)

split

F

T

in the

(T, F)

row.

Show proof

Look at the row $(P, Q) = (T, F)$ .
There $P \to Q = T \to F = F$ , while the converse $Q \to P = F \to T = T$ .
A single row with different truth values rules out logical equivalence, so $P \to Q$ and $Q \to P$ are not equivalent.
Intuitively: "if $x$ is prime then $x$ is odd or equal to $2$ " is true, but its converse is false.
Instead we prove $P \to Q \iff \lnot P \lor Q$ — which is also the definition of implication.
Computing the $\lnot P \lor Q$ column: $(T,T)$ : $F \lor T = T$ ; $(T,F)$ : $F \lor F = F$ ; $(F,T)$ : $T \lor T = T$ ; $(F,F)$ : $T \lor F = T$ .
That is $(T, F, T, T)$ — matching the $P \to Q$ column row by row.
Hence $P \to Q$ is equivalent to $\lnot P \lor Q$ .
This form makes negations easy to push inward: $\lnot(P \to Q) \equiv \lnot(\lnot P \lor Q) \equiv P \land \lnot Q$ (by De Morgan).
So there is exactly one way an implication can be false — the row $(T, F)$ : true antecedent, false consequent.