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.