Lesson 0. Logic: 0 and 1, gates from transistors, an adder

The foundation before the watch. What 0 and 1 are, the three operations on them (Boolean algebra), how a logic gate is made of transistors, and how gates make something useful — a circuit that adds two 4-bit numbers. Everything later in the kit is the same gates, just more of them.

Result: NOT (2 transistors), NAND and NOR (4 each), AND and OR (6 each), XOR (16), the full adder FA (50), the 4-bit adder ADD4 (200) — all 256 sums from 0+0 to 15+15 are correct.

0.1. The simulator

Everything is built in the browser: cs.khanin.info. No install, no sign-up; a computer with a mouse is the most comfortable.

This is a learning simulator, not a tool for designing real electronics. A transistor in it is an ideal switch (open or closed), and a signal is only 0 or 1. There are no voltages, currents, wire delays, heat or noise. That is more than enough to understand how logic, memory and a processor work; you can't design a real board with it — that needs resistors, power calculations and timing margins.

How to place parts, labels and chips is in "The simulator in five minutes" before the lessons. The key points: labels with the same name are connected, Ctrl+G turns a selection into a chip, Export saves your work.

0.2. Boolean algebra: 0, 1 and three operations

A signal is 0 or 1 (no/yes, false/true, off/on). Boolean algebra (George Boole, 1847) is the arithmetic of such values. There are only three operations:

NOT — flips: NOT 0 = 1, NOT 1 = 0. In the kit we write it with an n prefix: nA = NOT A.
AND — A·B is 1 only when both inputs are 1.
OR — A + B is 1 when at least one input is 1.

Their combinations got names of their own because they come up all the time:

A	B	A·B	A + B	NAND	NOR	XOR
0	0	0	0	1	1	0
0	1	0	1	1	0	1
1	0	0	1	1	0	1
1	1	1	1	0	0	0

NAND = NOT(AND), NOR = NOT(OR).
XOR ("exclusive OR", A ⊕ B) — 1 when the inputs differ. It is one-bit addition without the carry: 1 + 1 = 0, and the one goes to the carry (we'll need this in 0.5).

⚠ The plus in Boolean algebra is OR, not addition: 1 + 1 = 1.

The laws used to simplify formulas (each one checks out by substituting 0 and 1):

Law	Example
with a constant	A·1 = A A·0 = 0 A + 0 = A A + 1 = 1
with itself	A·A = A A + A = A
with its opposite	A·nA = 0 A + nA = 1
double NOT	NOT(nA) = A
factoring out	A·B + A·C = A·(B + C)
merging	A·B + A·nB = A
De Morgan	NOT(A·B) = nA + nB NOT(A + B) = nA·nB

De Morgan's law in words: "not (both)" = "at least one is not". It lets you swap AND for OR at the cost of inversions — that's how in lesson 3 the multiplexer is rebuilt from NANDs only and becomes cheaper.

0.3. A transistor is a switch

The palette has a Transistor part. It has three pins: the gate G on the left, top and bottom. The gate controls whether top and bottom are connected. Alt + click on the body (on a Mac — ⌥ or ⌘ + click) switches the type N ↔ P — a plain click leaves it alone:

N: gate = 1 → top and bottom connected; gate = 0 → open.
P: the other way round — connected when the gate = 0.

The CMOS rule (almost every chip since the 1980s is built this way): P transistors go on top, between VCC (the source of 1) and the output; N ones go at the bottom, between the output and GND (the source of 0). For any input exactly one half conducts — the output is always connected either to 1 or to 0. Never to both at once (a short) and never to nothing (an open, the output "floats").

A transistor in the simulator is a switch between the "top" and "bottom" pins, controlled by the gate G. N conducts at G = 1, P at G = 0. What is connected is highlighted.

0.4. NOT, NAND, NOR from transistors

NOT — two transistors. Input A goes to both gates: with A = 0 the top P is open and pulls the output to 1, with A = 1 the bottom N pulls it to 0.

INPUT PORTS: A · OUTPUT PORTS: Y

Transistor	Gate	Top	Bottom
P	A	VCC	Y
N	A	Y	GND

NOT from two transistors at A = 1: the bottom N conducts and ties the output to ground, the top P is closed. Y = 0. At A = 0 it is the other way round — P conducts, Y = 1.

Make it a chip: Ctrl+G → NOT.

NAND — four. Two P in parallel on top: a single 0 on an input is enough to make the output 1. Two N in series at the bottom: the output connects to ground only when both inputs are 1. The point between the two N gets the label mid.