Constructing Truth Tables

A truth table is the most direct, exhaustive description of a Boolean function: it lists every possible combination of inputs alongside the output each one produces. Where a Boolean expression is compact but can hide subtle behaviour, and a circuit diagram is concrete but slow to analyse, the truth table is the honest middle ground — it leaves nothing to interpretation. In OCR H446 you must be fluent moving in both directions: building a truth table from an expression or circuit, and reading an expression back out of a truth table using the sum-of-products technique.

This lesson develops both directions carefully, with full intermediate working, and shows how the truth table doubles as a proof tool — the cleanest way to demonstrate that two different-looking expressions are in fact the same function.

---

Spec Mapping

This lesson covers the truth-table strand of OCR H446 section 1.4.3 (Boolean algebra):

• Constructing a truth table for a given Boolean expression or logic circuit, including all necessary intermediate columns.
• Recognising that a function of $n$n inputs requires $2^n$2n rows, one for every distinct input combination.
• Deriving a Boolean expression from a completed truth table using the sum-of-products (minterm) method.
• Using truth tables to demonstrate the logical equivalence of two expressions.

These skills connect forwards to the algebraic-laws, De Morgan's and simplification lessons (truth tables verify every manipulation) and to the circuit-design content (a truth table is the usual specification a designer is handed).

---

Why Truth Tables Matter

A truth table lets you:

• Verify that an expression or circuit does what was intended.
• Compare two expressions and decide whether they are logically equivalent.
• Debug a circuit by checking expected against actual outputs row by row.
• Prove Boolean identities and the algebraic laws with no risk of hand-waving.
• Specify a brand-new circuit: state the desired output for each input case, then derive and simplify the expression.

Because it is exhaustive, a truth table can never be "almost right" — either every row matches or the functions differ. That completeness is exactly what makes it the gold standard for proof in this topic.

There is a deeper point worth holding onto. An expression and a circuit are representations of a function; the truth table is the function, laid bare. Two expressions that look nothing alike are the same function precisely when they share a truth table, and the entire enterprise of Boolean simplification is the search for the cheapest expression that reproduces a given table. Keeping that hierarchy clear — function first, representations second — makes every later lesson easier to navigate.

---

How Many Rows? The $2^n$2n Rule

Each input is binary, so $n$n independent inputs give $2^n$2n distinct combinations — one row each:

Variables ($n$n)	Rows ($2^n$2n)
1	2
2	4
3	8
4	16
5	32
6	64

The growth is exponential, and this is not a trivial footnote. It is the reason a truth table becomes unwieldy beyond four or five variables, the reason Karnaugh maps and algebraic simplification exist, and a concrete instance of the exponential-blow-up that motivates whole areas of computational complexity later in the course.

Key Term: For $n$n input variables a truth table has exactly $2^n$2n rows. Always compute $2^n$2n before you start drawing, so you know how many rows to rule.

---

Standard Input Ordering

List the inputs in the standard binary-counting order: treat the leftmost variable as the most significant bit and count from $0$0 up to $2^n - 1$2n−1. For three variables A, B, C this gives:

A	B	C	Decimal
0	0	0	0
0	0	1	1
0	1	0	2
0	1	1	3
1	0	0	4
1	0	1	5
1	1	0	6
1	1	1	7

A neat way to fill columns quickly without errors: the rightmost column alternates $0,1,0,1,\ldots$0,1,0,1,…; the next column alternates in pairs $0,0,1,1,\ldots$0,0,1,1,…; the next in fours, and so on — each column to the left doubling the run length.

Exam Tip: Use this ordering every single time. Examiners expect it, it lets a marker check your work at a glance, and it is the ordering that lines up with minterm numbering when you later read an expression back out.

---

Order of Evaluation (Precedence)

Boolean operators have a fixed precedence, directly analogous to arithmetic:

Priority	Operation	Symbols
1 (highest)	NOT	$\overline{\phantom{A}}$A, $A'$A′, $\lnot$¬
2	AND	$\cdot$⋅, juxtaposition
3 (lowest)	OR	$+$+

Brackets override precedence exactly as in arithmetic. A helpful analogy: AND behaves like multiply, OR behaves like add — so just as $2 + 3 \times 4$2+3×4 means $2 + (3 \times 4)$2+(3×4), the expression $A + B \cdot C$A+B⋅C means $A + (B \cdot C)$A+(B⋅C).

Example: evaluate $A + B \cdot \overline{C}$A+B⋅C in the right order:

1. First $\overline{C}$C (NOT binds tightest).
2. Then $B \cdot \overline{C}$B⋅C (AND next).
3. Finally $A + (B \cdot \overline{C})$A+(B⋅C) (OR last).

Misreading precedence is one of the most common ways a truth table goes silently wrong, so when in doubt, insert explicit brackets.

To see precedence bite, evaluate $A + B \cdot \overline{C}$A+B⋅C and the bracketed variant $(A + B) \cdot \overline{C}$(A+B)⋅C side by side — they are genuinely different functions:

A	B	C	$\overline{C}$C	$A + B \cdot \overline{C}$A+B⋅C	$(A + B) \cdot \overline{C}$(A+B)⋅C
0	0	0	1	0	0
0	0	1	0	0	0
0	1	0	1	1	1
0	1	1	0	0	0
1	0	0	1	1	1
1	0	1	0	1	0
1	1	0	1	1	1
1	1	1	0	1	0

The two output columns differ on three rows (101, 111 and any row where $A = 1$A=1 but $\overline{C} = 0$C=0). The lesson is stark: brackets are not optional cosmetics — moving them changes the function. When a question's expression is unbracketed, apply NOT-then-AND-then-OR faithfully.

---

Step-by-Step Method for Building a Truth Table

Expression: $Q = (A + B) \cdot \overline{A \cdot B}$Q=(A+B)⋅A⋅B

• Step 1 — count variables: A and B, so $2^2 = 4$22=4 rows.
• Step 2 — list the four input combinations in standard order.
• Step 3 — add one intermediate column per sub-expression, building outward:
  • $A + B$A+B
  • $A \cdot B$A⋅B
  • $\overline{A \cdot B}$A⋅B
  • and finally $Q = (A + B) \cdot \overline{A \cdot B}$Q=(A+B)⋅A⋅B.

A	B	$A + B$A+B	$A \cdot B$A⋅B	$\overline{A \cdot B}$A⋅B	$Q$Q
0	0	0	0	1	0
0	1	1	0	1	1
1	0	1	0	1	1
1	1	1	1	0	0

The output is 1 exactly when one and only one input is 1 — this is $A \oplus B$A⊕B. So the table has proved that $(A + B) \cdot \overline{A \cdot B} = A \oplus B$(A+B)⋅A⋅B=A⊕B, which is the standard way XOR is built from basic gates.

---

Completing a Truth Table from a Logic Circuit

Given a circuit, the procedure is to trace signals left to right:

1. Label every input wire (A, B, C, …).
2. Work out the expression each gate produces, naming intermediate wires (P, R, …).
3. Move stage by stage from inputs toward the output.
4. Fill the intermediate value at each gate for every row.
5. The final gate's column is the output Q.

Worked Example. Consider this circuit:

flowchart LR
    A["A"] --> AND["AND"]
    B["B"] --> AND
    C["C"] --> NOT["NOT"]
    AND --> OR["OR"]
    NOT --> OR
    OR --> Q["Q"]

The AND produces $P = A \cdot B$P=A⋅B; the NOT produces $R = \overline{C}$R=C; the OR gives $Q = P + R = (A \cdot B) + \overline{C}$Q=P+R=(A⋅B)+C.

A	B	C	$P = A \cdot B$P=A⋅B	$R = \overline{C}$R=C	$Q = P + R$Q=P+R
0	0	0	0	1	1
0	0	1	0	0	0
0	1	0	0	1	1
0	1	1	0	0	0
1	0	0	0	1	1
1	0	1	0	0	0
1	1	0	1	1	1
1	1	1	1	0	1

Naming the internal wires P and R is not optional decoration — it keeps a multi-gate trace organised and is exactly what mark schemes reward as "working".

When a circuit reconverges — where one wire fans out and feeds two later gates — careful labelling matters even more, because the same intermediate value appears in more than one column. In the multiplexer-style circuit $Q = (A \cdot B) + (\overline{B} \cdot C)$Q=(A⋅B)+(B⋅C), the input B is used twice: once directly into the upper AND, and once through a NOT into the lower AND. A disciplined trace gives B its own column, derives $\overline{B}$B from it, and only then forms the two products — rather than trying to evaluate the whole thing in one mental leap. The habit pays off most when an exam circuit has five or six gates: build the table one gate-column at a time and the answer assembles itself.

---

Using Truth Tables to Prove Equivalence

Two expressions are logically equivalent if, and only if, their output columns match on every row. This is the most reliable proof technique in the whole topic.

Example: prove $\overline{A \cdot B} = \overline{A} + \overline{B}$A⋅B=A+B (De Morgan's first law):

A	B	$A \cdot B$A⋅B	$\overline{A \cdot B}$A⋅B	$\overline{A}$A	$\overline{B}$B	$\overline{A} + \overline{B}$A+B
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

The $\overline{A \cdot B}$A⋅B column and the $\overline{A} + \overline{B}$A+B column are identical — $(1,1,1,0)$(1,1,1,0) — so the two expressions are equivalent. Notice this is a proof: there are only four input cases and all four agree, leaving nothing unchecked.

---

Truth Tables with Four Variables

For four inputs you need $2^4 = 16$24=16 rows. Here is $Q = (A \cdot B) + (C \cdot D)$Q=(A⋅B)+(C⋅D):

A	B	C	D	$A \cdot B$A⋅B	$C \cdot D$C⋅D	$Q$Q
0	0	0	0	0	0	0
0	0	0	1	0	0	0
0	0	1	0	0	0	0
0	0	1	1	0	1	1
0	1	0	0	0	0	0
0	1	0	1	0	0	0
0	1	1	0	0	0	0
0	1	1	1	0	1	1
1	0	0	0	0	0	0
1	0	0	1	0	0	0
1	0	1	0	0	0	0
1	0	1	1	0	1	1
1	1	0	0	1	0	1
1	1	0	1	1	0	1
1	1	1	0	1	0	1
1	1	1	1	1	1	1

Sixteen rows is around the practical ceiling for hand work; the doubling-run trick for the input columns keeps errors at bay.

---

Deriving an Expression from a Truth Table: Sum of Products

The reverse direction is just as examinable. Given a completed truth table, you can read out an expression as follows: