Construct a truth table

6. Worked Example 2 – Half‑Adder

A half‑adder adds two single‑bit numbers A and B. Outputs:

• Sum = A ⊕ B (XOR)
• Carry = A ∧ B (AND) – the more complex expression ¬(A⊕B) ∧ (A∨B) reduces to this.

The circuit consists of an XOR gate (Sum) feeding into the output and an AND gate (Carry). The same pattern recurs in full‑adders, multiplexers and many ALU control units.

7. From Truth Table to Circuit (Design Checklist)

1. Identify every column that represents a gate output.
2. Draw the corresponding gate symbol; label its inputs with the appropriate variable or intermediate column.
3. Connect intermediate outputs to downstream gates exactly as indicated by the table.
4. Verify that the final output column matches the behaviour of the drawn circuit.
5. If the circuit is sequential (e.g., includes flip‑flops), add clock and feedback lines – this note focuses on combinational logic only.

Example circuit for F = (A ∧ B) ∨ ¬C:

• AND gate: inputs A, B → output A∧B
• NOT gate: input C → output ¬C
• OR gate: inputs A∧B and ¬C → final output F

8. Linking Truth Tables to Later Topics

• Combinational circuit design: Truth tables precede Karnaugh‑map minimisation and gate‑level synthesis.
• Processor design: Control‑unit micro‑operations (e.g., “load IR”, “increment PC”) are described by truth tables that generate control signals.
• Practical exam (Paper 4): You may be asked to implement a given truth table using only NAND or only NOR gates – recall functional completeness.
• Networking & security: Packet‑filter rules and simple access‑control policies are Boolean conditions that can be modelled with truth tables.
• Programming: Translate a Boolean expression into an if statement and verify its correctness with the table.
• A‑Level extensions (optional): Decision‑tree evaluation in AI, XOR‑based stream ciphers, and parallel‑processing control logic all rely on the same Boolean foundations.

9. Practice Exercise

Construct a complete truth table for the Boolean expression below and then sketch the corresponding logic circuit.

G = ¬(A ∨ B) ∧ (B ⊕ C)

Steps

1. List the three inputs (A, B, C). You will need 2³ = 8 rows.
2. Create intermediate columns for:
   • A ∨ B
   • ¬(A ∨ B)
   • B ⊕ C
   • Final output G
3. Fill the table row‑by‑row using the gate truth tables from Section 3.
4. Translate each intermediate column into a gate:
   • A ∨ B → OR gate
   • ¬(A ∨ B) → NOT gate (after the OR)
   • B ⊕ C → XOR gate
   • Final ∧ → AND gate combining the NOT output and the XOR output.

Suggested Solution (Self‑Check)

The resulting circuit uses one OR gate, one NOT gate, one XOR gate and one AND gate – exactly the gates listed in the syllabus.

10. Algorithmic Generation of a Truth Table (Programming Exercise)

Write pseudocode that, given any Boolean expression in infix notation, outputs its full truth table. This reinforces the link between algorithm design and digital logic.

Algorithm GenerateTruthTable(expr):
    inputs ← list of distinct variables in expr
    n      ← length(inputs)
    rows   ← 2ⁿ
    Print header: inputs + sub‑expressions + final result
    for i from 0 to rows‑1 do
        // binary counting to assign values
        for j from 0 to n‑1 do
            inputs[j] ← (i >> (n‑1‑j)) & 1
        end for
        // evaluate sub‑expressions in order of parentheses
        result ← evaluate(expr, inputs)
        Print inputs and result
    end for
end Algorithm

In an exam you won’t be asked to code this, but understanding the systematic nature of the algorithm helps avoid mistakes when constructing tables manually.

11. Quick Reference Checklist

1. Count inputs → rows = 2ⁿ.
2. Write inputs in binary order (000… to 111…).
3. Add a column for every sub‑expression (parentheses, intermediate gates).
4. Use the gate truth tables (Section 3) to fill intermediate columns.
5. Final column = overall expression.
6. Cross‑check the final column against a hand‑drawn circuit or a simple program.

12. Further Reading / Extension Activities (Optional)

• Decision trees (AI): each node evaluates a Boolean condition – truth tables can be used to verify the tree’s logic.
• Simple encryption: the XOR gate is the core of many stream ciphers; construct truth tables for encrypt/decrypt functions.
• Parallel processing control: design a truth table for a basic pipeline stall detector (e.g., “if (RegWrite && MemRead) …”).
• Flip‑flops and sequential logic: extend the current combinational approach to include clocked elements – see the “Sequential circuits” section of the syllabus.

Mastering truth tables equips you with a universal tool for analysing, designing, and testing all digital systems covered in the Cambridge A‑Level Computer Science syllabus, and provides a solid bridge to programming, processor design, networking and beyond.