applets.

Logic Gates

← All apps

About Logic Gates

Everything a computer does comes down to gates: tiny switches that take in 0s and 1s and give out a 0 or a 1 by a fixed rule. This bench starts with six of them and builds up, one step at a time, to a circuit that adds and a circuit that remembers. A wire that glows red is carrying a 1; a dark wire carries 0.

GATES: each gate on its own chip, with switches in and a lamp out, and its truth table (every input and what comes out); the row that is live is lit. Flip the switches or clicktap a row. NANDS on a card shows that gate built from NAND gates alone, working from the same switches.

BUILD: a breadboard. Pick a chip from the tray and it goes in the next free socket; drag a chip to move it. Drag from a pin to another pin to run a wire (or clicktap one pin, then the other), always from an output (a switch or a chip's right-hand pin) to an input (a chip's left-hand pin or a lamp). An input takes one wire; a new one replaces the old. Select a wire or chip (clicktap it) and press Delete or REMOVE to take it out. Every change travels through the gates one gate delay at a time, at the speed set at the top; if the gates never settle, the page says so. Pick a challenge and press CHECK IT: the checker tries every input and counts your gates against the fewest known. Keys: A, B and C flip the switches; S steps one gate delay; Delete removes; Esc lets go of a wire.

ADDER: four full adders side by side add two numbers from 0 to 15. Change either number and watch the carry ripple from right to left. Each chip shows the gate delay at which it last changed, and the page compares the lamps with the right answer.

MEMORY: two gates, each feeding the other, can hold a 1 or a 0 after the input that set it has gone. The trace underneath records the signals like a logic analyser.

THE STORY

George Boole turned logic into algebra, with symbols for true and false and rules for AND, OR and NOT, in The Mathematical Analysis of Logic (1847) and An Investigation of the Laws of Thought (1854). For decades it was pure mathematics.

Charles Sanders Peirce noticed that one operation is enough: everything in Boole's algebra can be written using only "not both" (NAND), or only "neither ... nor" (NOR). He worked it out around 1880 but never published it; it appeared in his collected papers in 1933. In 1886 he also wrote to his former student Allan Marquand suggesting that logic could be done by electrical circuits. In 1913 Henry Sheffer published a proof that a single operation can do all of Boolean algebra; it is still called the Sheffer stroke, and today usually means NAND.

In 1937 Claude Shannon, a student at MIT, wrote a master's thesis, A Symbolic Analysis of Relay and Switching Circuits (published in 1938), showing that Boole's algebra describes circuits of relays and switches exactly: switches in series make AND, switches in parallel make OR. Telephone engineers could now design switching circuits with algebra instead of by trial. The same year George Stibitz at Bell Labs built a binary adder from relays on his kitchen table.

Gates have been built from relays (slow, clicking, a few thousandths of a second), then from valves (vacuum tubes, as in Colossus and ENIAC in the 1940s), then from transistors, invented at Bell Labs in 1947. From the 1960s whole gates came on integrated circuits: Texas Instruments' 7400 family of chips made the part numbers on these chips familiar (the 7400 holds four NAND gates, the 7402 four NORs, the 7404 six NOTs, the 7408 ANDs, the 7432 ORs, the 7486 XORs), and each gate takes around ten nanoseconds. The logic of the Apollo Guidance Computer was built from NOR gates alone, on integrated circuits. The memory circuit here is older still: William Eccles and F. W. Jordan built a two-valve circuit that holds either state, the first flip-flop, in 1918.

HOW IT WORKS

NAND is enough. A NAND with both inputs joined is NOT. NAND then NOT is AND (2 NANDs). Turn both inputs over first and NAND gives OR (3 NANDs), because NOT (NOT A AND NOT B) is A OR B: one of De Morgan's laws. XOR takes 4. The test file for this page checks by trying every circuit that these are the fewest possible, and that 2 gates make a half adder and 5 a full adder from the six gates here (the usual 5 NAND half adder and 9 NAND full adder are the best known).

Adding. Binary adds like school addition: 1 + 1 is 0, carry 1. A half adder gives the sum bit (A XOR B) and the carry (A AND B). A full adder also takes a carry in: two XORs make the sum of three bits, and the carry out is (A AND B) OR (carry in AND (A XOR B)). Chain four and each passes its carry to the next, a ripple-carry adder. The carry from bit 0 is ready after 2 gate delays and each later bit adds 2 more, so 4 bits can take 8 gate delays and 64 bits 128. Real processors use faster designs, such as carry-lookahead adders, which work the carries out side by side.

Remembering. In the NOR latch, each NOR's output goes into the other. With S and R both 0 each gate just turns over what the other gives it, and the pair stays as it is: Q = 1 keeps Q̄ = 0, which keeps Q = 1. S = 1 forces Q to 1, R = 1 forces it to 0. S = R = 1 forces both outputs to 0, so they are no longer opposites, and if both are let go at the same moment the two identical gates in this page flip together for ever. Real gates are never exactly identical, so one wins, but which one, and how long it takes to decide, can't be predicted (this is called metastability). That is why S = R = 1 is the forbidden input. The NAND latch is the same with every signal turned over. The gated D latch puts two AND gates in front so that S and R can never both be 1: while E is 1, Q follows D; when E goes to 0, Q keeps the last D.

The simulator gives every gate the same delay: at each tick every gate's output becomes what its inputs were asking for at the tick before. A circuit settles when a tick changes nothing; if the gates come back to a pattern they have had before, it never will. A ring of three NOTs passes a wave round and round, repeating every 6 gate delays: real rings like this (ring oscillators) are used to make clock signals and to measure how fast a chip's gates are.

WHAT IT LEAVES OUT

Signals here are exactly 0 or 1 and change in whole gate delays, every gate takes the same time, and wires take none. A real chip has a power supply, a limit on how many inputs one output can drive, and four or six gates in each package. An input with no wire reads 0 here; a real TTL input left loose usually acts as a 1, unreliably, so it should always be tied. The checker starts each test from all gates at 0, so a circuit that only works from a lucky starting state might pass.

Nothing you build is sent anywhere. COPY LINK puts the board in the address so you can share a circuit.

FURTHER WATCHING AND READING

Gate delay
Built from parts like these: Tiny Computer