Gates & Truth Tables

Read a gate-level circuit and write the Boolean expression it implements.

A logic gate is a small piece of hardware that computes one Boolean operation on its inputs. Wire a handful of gates together and the whole circuit computes some larger Boolean expression — reading that expression back off the circuit diagram is the skill this topic practices.

Ready to put it into practice?

Start practicing

The basic gates and the expression each one computes for two inputs A and B:

\begin{aligned} \text{AND} &: AB \\ \text{OR} &: A+B \\ \text{NOT} &: \overline{A} \\ \text{NAND} &: \overline{AB} \\ \text{NOR} &: \overline{A+B} \\ \text{XOR} &: A \oplus B \end{aligned}

Basic gates

$A \oplus B$ XOR — true when exactly one of A, B is true, not both and not neither.
$\overline{AB}$ NAND — the complement of AND; false only when both inputs are true.

A multi-level circuit is just gates feeding other gates. Work from the inputs toward the final output, one gate at a time: write the expression each gate produces from what feeds into it, then use that as an input to the next gate downstream, the same way you'd evaluate a nested arithmetic expression from the inside out.

NAND and NOR are called universal gates because either one alone, wired different ways, can reproduce AND, OR, and NOT. That's why you'll see circuits built entirely out of NAND gates (or entirely out of NOR gates) with no other gate type in sight — it's not a puzzle for its own sake, it's how a lot of real hardware is actually built, since a chip that only has to fabricate one gate type is simpler to manufacture.

Once you have the circuit's expression, the truth table is the ground truth for what it does: evaluate that expression for every combination of inputs. Two circuits that look different but produce the same truth table are functionally the same circuit — this is the same equivalence idea as the Boolean Laws topic, just arrived at by reading a diagram instead of simplifying an expression.

Worked example

\text{NAND gate, inputs } A, B

$\text{NAND}(A, B) = \overline{AB}$
NAND is AND followed by a NOT — complement whatever the AND gate would have output.
$\begin{array}{cc|c} A & B & \overline{AB} \\ \hline 0&0&1 \\ 0&1&1 \\ 1&0&1 \\ 1&1&0 \end{array}$
Only false (0) when both inputs are true — every other combination outputs true.

Answer:

\overline{AB}

How to solve one of these

1.
Identify the inputs. List every distinct input variable feeding the circuit.
2.
Work gate by gate, from inputs to output. Write the expression each gate produces, using the previous gates' outputs as its inputs.
3.
Combine into one final expression. The last gate's output, written in terms of the original inputs, is the circuit's expression.
4.
Sanity-check with the truth table. Evaluate your expression on a couple of input rows and confirm the result matches what you'd expect the circuit to output for those inputs.

A \oplus B, \quad \overline{AB}, \quad \overline{A+B}

XOR, NAND, and NOR — the three gates built from a basic gate plus a complement.

Ready to put it into practice?

Start practicing

Want the rest of Calc III? Leave your email and I'll tell you the day the pack's live.