A Switch That Answers a Question
A logic gate is a small circuit that takes one or more on-off inputs and produces an on-off output according to a fixed rule. Think of 1 as “on” or “true” and 0 as “off” or “false”. Each gate answers a tiny question, and the answer depends only on the inputs at that moment.
Only a few kinds of gate are needed to understand how computation works.
The Basic Gates
NOT has one input and flips it. If the input is 1, the output is 0, and the reverse.
AND has two inputs and outputs 1 only if both inputs are 1. A household analogy is two switches wired in a row: the lamp lights only when both are closed.
OR outputs 1 if at least one input is 1. This is like two switches wired side by side: closing either one lights the lamp.
A table listing every input combination and the matching output is called a truth table. For AND, the four rows are: 0 and 0 gives 0; 0 and 1 gives 0; 1 and 0 gives 0; 1 and 1 gives 1.
Other gates are built from these or sit alongside them. XOR, short for exclusive or, outputs 1 when exactly one input is 1. NAND is AND followed by NOT, and NOR is OR followed by NOT. NAND and NOR have a special property: either one alone can be used to build every other gate, so in principle a whole processor could be made from a single gate type.
Where the Idea Came From
The mathematics comes from George Boole, who in the mid-19th century wrote about an algebra for reasoning in which statements are either true or false. For decades this was mostly a topic in logic and philosophy. In the late 1930s Claude Shannon, then a student, showed in his work on relay circuits that Boolean algebra could describe and simplify networks of switches. Engineers independently in other countries were reaching related ideas, and the topic developed quickly as telephone and computing machines grew complicated.
This link let designers reason about circuits on paper with algebra, rather than by trial and error with wires.
How Gates Are Physically Made
The same logic can be built from different parts.
- Relays are switches moved by electromagnets. Several electromechanical machines of the 1930s and 1940s used them. They are reliable but slow, since a metal contact has to move.
- Vacuum tubes control current with no moving parts and are much faster than relays. They were used in the electronic computers of the 1940s and 1950s, but they were large, used a lot of power and burned out.
- Transistors, invented in the late 1940s, did the same job in a small, cool, durable solid device. Gates built from transistors replaced tubes through the 1950s and 1960s.
- Integrated circuits, from the late 1950s onward, placed many transistors and their connections on one piece of silicon. The number of gates on a chip grew steadily over the following decades.
The logic is the same in each case. Only the speed, size, cost and reliability change.
From Gates to Arithmetic
Here is how gates can add. Suppose you want to add two single bits. The sum bit is 1 when exactly one input is 1, which is the XOR rule. The carry bit is 1 only when both inputs are 1, which is the AND rule. Check this against the binary numbers rules: 0 + 0 gives sum 0 and carry 0; 0 + 1 gives sum 1 and carry 0; 1 + 1 gives sum 0 and carry 1, which is the binary number 10. The circuit built from these two gates is called a half adder.
Chaining adders, with each stage passing its carry to the next, lets a circuit add numbers many bits long. A full adder also accepts the incoming carry. Subtraction, multiplication and comparison can be built using the same approach, with more gates and more steps.
From Gates to Memory and Control
Gates can also hold state. When the output of one gate is fed back into the input of another in a loop, the circuit can settle into one of two stable states and stay there. This arrangement, often called a latch or flip-flop, stores a single bit, and many of them form fast memory inside a processor.
Control works similarly. A gate network can look at the bits of an instruction and decide which other circuits should be switched on, such as whether to add two numbers or move a value. That decision-making is part of what a central processing unit does. A processor is, at its heart, a very large, carefully organized arrangement of gates.
Why Simplicity Scales
The remarkable thing about gates is that nothing about them is complicated. A processor’s behavior seems intelligent only because enormous numbers of them operate together at high speed. Modern chips contain very large numbers of transistors acting as gates, though the exact count depends on the chip and the year.
The practical value of this design is in layers. Gates form adders and latches, those form larger units, and those form a processor. Each layer can be understood without knowing every detail of the one below it, which is one reason computing could grow so complex and still be designed by people.