Truth tables, equivalence, and the logical laws

What a truth table is

An interpretation assigns a truth value to each propositional symbol. A formula over $n$ symbols has $2^n$ interpretations, and a truth table simply lists all of them, computing the formula's value on each row. For two symbols $P, Q$ there are $2^2 = 4$ rows. The standard convention is to count down from all-true:

P Q
T T
T F
F T
F F

You fill the table inside-out: evaluate the innermost sub-expressions first, then combine them with the outer connective, using the connective definitions (recall: $P \to Q$ is false only when $P$ is true and $Q$ false).

Equivalence = identical columns

Two formulas are logically equivalent ($\equiv$) when they produce the *same truth value on every interpretation* — i.e. their final columns are identical, row for row. That is the entire method, and it is the literal task on exam Q1.

Worked example (exam Q1): prove $P \leftrightarrow Q \equiv (P \to Q) \wedge (Q \to P)$

The biconditional $P \leftrightarrow Q$ ("P if and only if Q") is *defined* as both directions holding at once. Let us verify the two formulas have the same column. Recall $P \to Q$ is false only on the row $P=T, Q=F$, and $Q \to P$ is false only on $P=F, Q=T$:

P Q | P->Q | Q->P | (P->Q)&(Q->P) | P<->Q
T T |  T   |  T   |       T       |   T
T F |  F   |  T   |       F       |   F
F T |  T   |  F   |       F       |   F
F F |  T   |  T   |       T       |   T

The last two columns are identical (T, F, F, T), so $P \leftrightarrow Q \equiv (P \to Q) \wedge (Q \to P)$. Read it in words: the biconditional is true exactly when $P$ and $Q$ *agree*, and the conjunction of the two implications is true exactly when neither one-way arrow fails — which is the same rows. The Python exercise below generates exactly this table and prints the verdict.

The logical laws (memorise these)

Rather than build a table every time, you can transform a formula with known equivalences:

- De Morgan: $\neg(P \vee Q) \equiv \neg P \wedge \neg Q$ and $\neg(P \wedge Q) \equiv \neg P \vee \neg Q$. Negation flips the connective and distributes over both operands. - Implication as disjunction: $P \to Q \equiv \neg P \vee Q$. This is the rewrite that converts implications into clause form for resolution (Lesson 7, and Module 9). - Contrapositive: $P \to Q \equiv \neg Q \to \neg P$. The contrapositive is equivalent to the original; the *converse* $Q \to P$ and the *inverse* $\neg P \to \neg Q$ are not. - Double negation: $\neg\neg P \equiv P$. - Distributive: $P \wedge (Q \vee R) \equiv (P \wedge Q) \vee (P \wedge R)$, and the dual with $\wedge/\vee$ swapped.

A formula true under *every* interpretation (an all-T column) is a tautology; one false under every interpretation (all-F) is a contradiction.