Designing Logic Circuits
Knowing what each gate does is only half the story. The examined skill is moving fluently in both directions — reading a wired-up circuit to deduce its truth table, and starting from a desired truth table to construct a circuit that produces it, including circuits built entirely from a single gate type.
Deducing a truth table from a circuit
Given a wiring diagram of gates, the process for finding its complete truth table is mechanical if you follow it in order.
- Label every gate output. Give each intermediate signal in the circuit its own letter or name, not just the final output. This stops you trying to jump straight from inputs to output and skipping steps where mistakes creep in.
- List every input combination. Two inputs give 4 rows ($2^2$); three inputs give 8 rows ($2^3$); in general, $n$ inputs give $2^n$ rows. Write them out systematically (counting up in binary is the standard way) so none are missed.
- Propagate row by row. For each row, work out every intermediate signal in the order the signal actually flows through the circuit, then finally the output. Gates that only depend on the original inputs can be evaluated first; gates that depend on other gates' outputs must wait until those are known.
| A | B | X = A+B | Y = A·B (bar) | Q = X·Y |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 |
Constructing a circuit from a truth table
The reverse skill — starting from a desired truth table and building a circuit that produces it — is generally the harder direction, but it has a reliable systematic method.
- Find every row where the output is 1. Ignore rows where the output is 0 entirely for now.
- Write an AND-term for each of those rows. For a given row, write down the Boolean product of the inputs (each input used directly if it's 1 in that row, or inverted with a bar if it's 0 in that row) that is true only for that exact input combination. For example, if $A=1, B=0$ gives output 1, the term is $A \cdot \bar{B}$ — this expression equals 1 only when A is 1 and B is 0, and 0 for every other combination.
- OR all the terms together. Combining every 1-row's AND-term with OR gives a complete Boolean expression for the output: it evaluates to 1 whenever any one of the contributing rows' exact input combination occurs, and 0 otherwise — which is exactly the behaviour the truth table specifies.
- Translate directly into gates. Each AND-term becomes an AND gate (with NOT gates on any inputs that need inverting), and the final OR combines their outputs — giving a working circuit built straight from the Boolean expression.
NAND-only implementations
Because NAND is a universal gate, any combinational circuit — including NOT, AND and OR themselves — can be built using NAND gates exclusively. This matters practically: manufacturing a chip from one repeated gate type is simpler and cheaper than stocking and wiring several different gate types.
NOT from NAND
Tie both inputs of a NAND gate together (or equivalently, hold one input permanently high at 1) and feed the same signal into both. The NAND truth table row where both inputs are equal to A collapses to a single-input NOT.
| A | NAND(A, A) |
|---|---|
| 0 | 1 |
| 1 | 0 |
AND from NAND
Feed A and B into one NAND gate, then feed that NAND gate's output into a second NAND gate with both its inputs tied together (i.e. used as a NOT, per above). NAND followed by NOT reconstructs AND.
| A | B | NAND(A,B) | NOT of that = A·B |
|---|---|---|---|
| 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
OR from NAND
Invert A and invert B first (each using a NAND-as-NOT gate), then feed the two inverted signals into a third NAND gate. This is a direct application of De Morgan's relationship between AND and OR: $\overline{\bar{A} \cdot \bar{B}} = A + B$.
| A | B | Ā | B̄ | NAND(Ā,B̄) = A+B |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 |
Once NOT, AND and OR are each available in NAND-only form, any Boolean expression built earlier in this lesson — including the constructed-from-a-truth-table method above — can be rebuilt using nothing but NAND gates, simply by substituting each NOT, AND and OR for its NAND-only equivalent.
Real digital system design constantly shuttles back and forth between "what behaviour do I want?" (a truth table) and "what circuit produces it?" (a network of gates). Being able to go from circuit to truth table, and from truth table to circuit, fluently and in either direction — not just memorising the three standard NAND constructions above — is what's actually being tested. Treat both worked examples in this lesson as templates for a method, not as facts to memorise in isolation.
Key takeaways
- To deduce a truth table from a circuit: label every gate output, list all $2^n$ input rows, then propagate each row through the gates in signal order.
- To construct a circuit from a truth table: write an AND-term for each row where the output is 1, OR all those terms together, then translate the resulting Boolean expression directly into gates.
- An AND-term for a given row uses each input directly if it's 1 in that row, or inverted (barred) if it's 0 in that row — this makes the term true only for that one row.
- NAND is a universal gate: NOT, AND and OR can all be built from NAND gates alone.
- NOT from NAND: tie both inputs together (or hold one input high).
- AND from NAND: a NAND gate followed by a NAND-as-NOT gate.
- OR from NAND: invert both inputs first, then NAND the two inverted signals together (De Morgan's relationship).
- The genuinely examined skill is fluency in both directions — circuit to truth table, and truth table to circuit — not rote memorisation of one direction only.