Logic Gates & Circuits

AND/OR/NOT/NAND, circuit evaluation, and NAND universality.

The idea

A logic gate is a hardware device that takes in one or two binary signals — voltages read as $0$ and $1$ — and sends one signal out. The output it emits for each combination of inputs describes a gate completely.

Three gates realize the Boolean operations. An AND gate, written $x \cdot y$, outputs $1$ only when both inputs are $1$. An OR gate, written $x + y$, outputs $1$ when either input is. A NOT gate, or inverter, written $x'$, takes a single input and flips it.

Wiring gates together, each output feeding a later input, produces a circuit, and a circuit computes a Boolean expression. To evaluate it, start from the input signals and work gate by gate in the order the wires run, exactly as you would work outward from the innermost parentheses.

One compound gate is common enough to have its own name: a NAND gate is an AND followed by a NOT, $x \text{ NAND } y = (x \cdot y)'.$

Ways to work on it

• Walkthrough. Evaluate a circuit gate by gate, and see that one gate type can build all the others.
• Practice. Evaluate a small circuit's output.
• Hardest. Build AND from NAND gates.

Not sure where to start? Take the ten-question placement test.