Logic gates
Every chip is built from logic gates: tiny circuits that take bits in and give one bit out. Start with two switches in a row (AND) and side by side (OR), then meet the standard gate symbols and step through the truth tables of NOT, AND, OR, NAND, NOR and XOR, one row at a time.
5 quick questions
Pick an answer to see why. Your score saves with your progress.
01Two switches are wired in series (one after the other) with a bulb. When does the bulb light?
There is only one path for the current, so one open switch breaks it. Both must be on: that is AND.
02Which gate gives 1 only when both of its inputs are 0?
NOR is OR followed by NOT. OR gives 0 only for 0 0, so NOR gives 1 only for 0 0.
03What does an XOR gate output when both inputs are 1?
XOR (exclusive OR) gives 1 only when the inputs are different. 1 and 1 match, so the output is 0.
04What does the small circle at the output of a gate symbol mean?
The circle is the NOT bubble: NAND is AND with a bubble, NOR is OR with a bubble.
05How many transistors does a CMOS NAND gate with two inputs use?
Four: two in series and two in parallel. A CMOS NOT gate uses two.
Glossary
- Bit
- One binary digit: 0 or 1. In a circuit it is a low or high voltage, off or on.
- Logic gate
- A small circuit that takes one or more input bits and gives one output bit by a fixed rule.
- Truth table
- A list of every possible input combination and the output a gate gives for each one.
- AND / OR / NOT
- AND gives 1 only if all inputs are 1; OR gives 1 if any input is 1; NOT gives the opposite of its one input.
- NAND / NOR
- NOT AND and NOT OR: the same gates with every output flipped, shown by a small circle on the symbol.
- XOR
- Exclusive OR: gives 1 when its two inputs are different and 0 when they match.
- Series and parallel
- Series: parts one after the other on a single path. Parallel: parts side by side, each on its own path.
- CMOS
- Complementary MOS: the way most chips build gates, using pairs of two kinds of transistor (nMOS and pMOS).
Notes and sources
- Switches in series behave like AND and switches in parallel like OR. Claude Shannon showed this for relay circuits in his 1937 MIT thesis, published in 1938.
- Inside a chip, 1 and 0 are two voltage levels (high and low); here the bulbs and lamps just show them. A lit wire means it carries a 1.
- Counts are for static CMOS gates with two inputs: NOT 2, NAND 4, NOR 4 (Harris and Harris, Digital Design and Computer Architecture, section 1.7). In a NAND the two series transistors connect the output to ground and the two parallel ones connect it to power.
- A real example: Texas Instruments' SN74HC00 contains four independent 2-input NAND gates and runs on 2 V to 6 V.
- In Python, &, | and ^ on the numbers 0 and 1 work as AND, OR and XOR. For NOT write 1 - a, because ~a in Python gives -(a + 1).
- Harris and Harris, Digital Design and Computer Architecture (sections 1.5 and 1.7)
- Shannon, A Symbolic Analysis of Relay and Switching Circuits (MIT, 1937)
- Texas Instruments SN74HC00 datasheet: quad 2-input NAND gates
- Python reference: binary bitwise operations
- Nisan and Schocken, Nand2Tetris: Boolean logic
- MIT OpenCourseWare 6.004 Computation Structures
Quiz Unlocks after the last step.