Logic gates
Intel's first microprocessor, the 4004 of 1971, held 2,300 transistors. They were wired into gates, and gates are all a processor is made of.
Shannon's two circuits on a desk
You can build Shannon's two circuits with a battery, a lamp and two switches. Put the switches in a row and the lamp lights only if the first and the second are both closed. Put them side by side and the lamp lights if either one is closed. These circuits already make decisions. A logic gate is a small circuit of the same kind, built from transistors instead of hand switches. It takes one or two input bits and produces one output bit by a fixed rule.
Six gates and the tables that define them
AND gives 1 only when both inputs are 1, like the switches in a row. OR gives 1 when at least one input is 1, like the switches side by side. NOT has a single input and flips it, so 0 becomes 1 and 1 becomes 0. XOR, short for "exclusive or", gives 1 when the two inputs differ. NAND and NOR are AND and OR with a NOT on the end, which makes their outputs the exact opposite. A truth table lists every combination of inputs and the output for each. Two inputs make four rows, three make eight, and n inputs make 2 to the power n.
Drag to turn. Scroll or pinch to zoom.
| A | B | AND | OR | XOR | NAND | NOR |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 |
An alarm, an equality test and a password check
Gates combine into rules of any size. Take a burglar alarm. It should ring when the system is armed AND (the door is open OR a window is open). That is one OR gate feeding one AND gate. To check whether two bits are equal, put a NOT after an XOR, because XOR gives 1 exactly when the bits differ. Set eight of those side by side, join their outputs with AND, and the circuit tells you whether two whole bytes match. Every comparison a program makes, from "is the password right" to "has the timer reached zero", ends up as a circuit like this.
Why chip makers can get by with NAND alone
NAND has a handy property: every other gate can be built from NAND gates alone. Tie both inputs of a NAND together and it becomes NOT, because NAND of 1 and 1 is 0 and NAND of 0 and 0 is 1. Put that NOT after another NAND and you have AND again. A few more make OR and XOR. Chip makers like this because they can lay down enormous numbers of one well-tested shape. In a real chip a gate is a handful of transistors. The 4004 had 2,300 of them, and Intel lists 1.16 billion for its 2010 second-generation Core processor. That is about 500,000 times as many in 39 years.
- "OR means one or the other, but not both." Everyday "or" often works that way: "tea or coffee?" usually means pick one. In logic that rule is XOR. OR also gives 1 when both inputs are 1.
- "A truth table for 3 inputs has 6 rows." 3 × 2 is the wrong count. Each extra input doubles the rows, because every earlier row appears once with the new input at 0 and once at 1. 2³ = 8. Four inputs already need 16.
- "NAND and NOR are new kinds of switch." NAND is AND with a NOT on the end, and NOR is OR with a NOT on the end. Nothing new happens inside. What makes NAND special is that it alone is enough to build every other gate.
- AND with inputs 1 and 0 gives?
- OR with inputs 1 and 0 gives?
- XOR with inputs 1 and 1 gives?
- NAND with inputs 1 and 1 gives?
- NOR with inputs 0 and 0 gives?
- How many rows does the truth table of a 3-input gate have?
- Two switches in series with a lamp behave like which gate?
- AND
- OR
- XOR
- NOT
- You join both inputs of a NAND gate together. What gate do you get?
- NOT
- AND
- OR
- XOR
- How many transistors did Intel's 4004 of 1971 have?
- What did Shannon's 1938 paper show?
- Switching circuits follow Boole's algebra of true and false
- Transistors are faster than relays
- Binary numbers were invented in 1938
- Computers need decimal digits
- A gate turns input bits into an output bit by a fixed rule.
- AND: both 1. OR: at least one 1. NOT: flip. XOR: inputs differ.
- NAND and NOR are AND and OR with the output flipped; NAND alone can build every gate.
- A truth table with n inputs has 2ⁿ rows.
Sources for this course (9)
- (checked 2026-10-17; reordered 2026-10-19: standards first, then official documentation, then the teaching model and calculations, history sources last)
- Standards: NIST, "Prefixes for binary multiples" (physics.nist.gov/cuu/Units/binary.html: IEC approved kibi, mebi, gibi in December 1998; 1 B = 8 bit; 1 MiB = 1 048 576 B; 1 MB = 1 000 000 B; 1 GiB = 1 073 741 824 B; historical note: memory makers usually mean 2²⁰ bytes by megabyte, storage makers 1 000 000, and the "1.44 MB" diskette uses a megabyte of 1 024 000 bytes)
- IETF RFC 20 "ASCII format for Network Interchange" (1969, 7-bit codes, A = 65, a = 97, 0 = 48)
- IETF RFC 3629 "UTF-8, a transformation format of ISO 10646" (2003: 1 to 4 octets per character, ASCII unchanged, code points up to U+10FFFF, U+0800 to U+FFFF take three octets, "the first octet of a multi-octet sequence indicates the number of octets", example U+D55C U+AD6D U+C5B4 = ED 95 9C EA B5 AD EC 96 B4)
- Official documentation: MDN Web Docs, "<color>" (hexadecimal colour notation #RRGGBB)
- Intel, "Intel Chips" timeline poster (2012: Intel 4004 of 1971 with 2,300 transistors; 2nd generation Core 2010 with 1.16 billion)
- Claude E. Shannon, "A Symbolic Analysis of Relay and Switching Circuits", Transactions of the AIEE vol. 57 (1938)
- abstract of his MIT master's thesis. Computer History Museum, The Silicon Engine, "1947: Invention of the Point-Contact Transistor" (Bardeen and Brattain, December 1947, germanium)
- John von Neumann, "First Draft of a Report on the EDVAC" (30 June 1945, Moore School, reprinted in IEEE Annals of the History of Computing 15:4, 1993).
Checked: 2026-10-17