Truth Tables and Logical Equivalence

The Complete Specification

A truth table lists the output of a boolean function for every possible combination of its inputs. Because each input is 0 or 1, a function of $n$ inputs has $2^n$ rows — a 2-input function has 4 rows, a 3-input function has 8. The truth table is the complete specification of a boolean function: two expressions compute the same function if and only if their truth tables match, row for row.

This gives a foolproof test for logical equivalence: to check whether two boolean expressions are equal, build both truth tables and compare. If they agree on every row, the expressions are equivalent, no matter how different they look.

Truth tables also let you verify the laws of boolean algebra — the rules for manipulating expressions:

• Identity: $A + 0 = A$, $\quad A \cdot 1 = A$.
• Complement: $A + \overline{A} = 1$, $\quad A \cdot \overline{A} = 0$.
• De Morgan's laws: $\overline{A \cdot B} = \overline{A} + \overline{B}$ and $\overline{A + B} = \overline{A} \cdot \overline{B}$ — negation turns AND into OR and vice versa. These are among the most useful identities in all of digital design.

Each row of a truth table where the output is 1 is a minterm. Reading off the minterms and OR-ing them together gives a canonical expression (sum-of-products) that realizes any truth table — proving that every boolean function can be written as a formula, and hence built from gates.

Common pitfall: applying De Morgan's law incorrectly — writing $\overline{A \cdot B} = \overline{A} \cdot \overline{B}$ (wrong) instead of $\overline{A} + \overline{B}$ (right). De Morgan's law flips the operator: the negation of an AND is the OR of the negations, and the negation of an OR is the AND of the negations. Forgetting to flip the operator is one of the most common boolean-algebra mistakes.