Propositions and Truth Tables

Switch the connective and watch the new column fill in while the

P

Q

columns stay fixed. Compare the shaded

P \to Q

column with its contrapositive

\lnot Q \to \lnot P

row by row — identical in all four rows. The converse

Q \to P

, though, splits off in the

(T, F)

row.

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.