Base CS from zero
Logic gates
In the previous lesson you learned AND, OR, and NOT as abstract operations on truth values.
Every if statement, every access-control check, every cache-invalidation rule reduces to
some combination of these three operations. But where do they actually live?
They live in hardware — as physical components called logic gates. A gate is a tiny circuit built from transistors that has wires as inputs and a wire as output. You feed voltage (1) or no voltage (0) into the inputs, and the gate produces the correct output according to the operation it implements. The AND gate produces 1 only when both inputs are
- The OR gate produces 1 when at least one input is 1. The NOT gate inverts its single input.
That is the bridge: boolean logic, which you can reason about on paper with 1s and 0s, becomes hardware you can physically build and connect. And once you can connect gates, you can build anything a computer does — including arithmetic.
After this lesson you can explain what a logic gate is and how it relates to a boolean operation, describe the behaviour of AND, OR, and NOT gates from their inputs to their output, read a simple gate diagram, explain how gates compose into circuits, and describe at a conceptual level how AND and XOR gates together form a half-adder that sums two bits.
What a gate is. A logic gate is a hardware component with one or more input wires and one output wire. It is built from transistors — switches that turn on or off depending on voltage. The exact transistor arrangement differs between gate types, but the behaviour is always a boolean function: given inputs that are each 0 or 1, the gate outputs 0 or 1 according to its truth table.
From the outside, the internal transistors do not matter. What matters is the contract: AND gate → AND truth table, OR gate → OR truth table, NOT gate → NOT truth table. The gate is a black box that computes one operation reliably, billions of times per second, from inputs and an output.
Gates are physical: they consume a tiny amount of power, produce a tiny amount of heat, and take a tiny amount of time (nanoseconds) to settle on their output after their inputs change. But at the level of logic, you treat them as instantaneous and abstract, just like the truth tables from the previous lesson.
The three fundamental gates. The same three operations that are functionally complete in boolean logic map directly to three gate types.
NOT gate (also called an inverter): one input, one output. Output is the opposite of input.
| Input A | Output |
|---|---|
| 0 | 1 |
| 1 | 0 |
AND gate: two inputs, one output. Output is 1 only when both inputs are 1.
| Input A | Input B | Output |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
OR gate: two inputs, one output. Output is 1 when at least one input is 1.
| Input A | Input B | Output |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
These are the same truth tables as in the previous lesson, now understood as the precise specifications of physical components you can manufacture and connect.
Connecting gates into circuits. The real power of gates is that they compose. You can wire the output of one gate into the input of another. A collection of connected gates is called a circuit. The circuit as a whole computes a function: given some input bits, it produces output bits. The function is determined entirely by which gates you use and how you connect them.
Consider building XOR from AND, OR, and NOT. The previous lesson showed the XOR truth table (true when inputs differ). In gate terms:
- Feed A and B into an AND gate. Its output is
A AND B. - Feed A and B into an OR gate. Its output is
A OR B. - Feed
A AND Binto a NOT gate. Its output isNOT(A AND B). - Feed
A OR BandNOT(A AND B)into a final AND gate.
The final output is (A OR B) AND NOT(A AND B) — which is exactly XOR.
This is the mechanism by which AND, OR, NOT being functionally complete becomes hardware reality: any truth table you can write down can be turned into a circuit by wiring together the right gates.
Why this works
Why gates can be cascaded at all. A gate’s output is 0 or 1 — the same type as its inputs. This means the output of one gate is directly compatible with the input of the next. There is no conversion step, no protocol negotiation. The output voltage level that means “1” on one gate is exactly the input voltage level that means “1” on the next. This uniformity is what makes circuits composable: you can build a new gate out of existing gates, and that composed gate behaves identically to a primitive gate from the outside.
Circuits build arithmetic: the half-adder. With gates composing freely, you can build circuits that do arithmetic. The simplest example is the half-adder, which adds two single bits together.
When you add two bits A and B by hand:
- 0 + 0 = 0, no carry
- 0 + 1 = 1, no carry
- 1 + 0 = 1, no carry
- 1 + 1 = 10 in binary (decimal 2): sum bit is 0, carry bit is 1
The half-adder has two outputs: the sum bit and the carry bit. Look at the pattern:
- Sum = 1 exactly when the inputs differ (0+1 or 1+0). That is XOR.
- Carry = 1 exactly when both inputs are 1 (1+1). That is AND.
So a half-adder is just an AND gate (for carry) and an XOR circuit (for sum) connected to the same two inputs. No new primitives needed — the gates already defined are enough.
A full-adder extends this to handle a carry-in from a previous bit position, allowing you to chain adders together to add multi-bit numbers. A full-adder is built from two half-adders and one OR gate. Chain enough full-adders and you have the arithmetic logic unit (ALU) inside a real CPU — still just gates, all the way down.
Edge cases
NAND: one gate to rule them all. In lesson 4 you learned that AND, OR, NOT are functionally complete. There is a stronger result: the NAND gate (NOT AND — output is 0 only when both inputs are 1, otherwise 1) is by itself functionally complete. You can build NOT, AND, and OR from NAND gates alone. This means you can build an entire computer from a single gate type. The nand2tetris course does exactly this, starting from only NAND. In practice, chip designers use other gate types for efficiency, but the theoretical completeness of NAND is a foundational result.
Trace through a half-adder circuit for inputs A=1, B=1.
A half-adder has two parts wired to the same inputs A and B:
- An AND gate for the carry output.
- An XOR circuit for the sum output. Recall XOR =
(A OR B) AND NOT(A AND B).
With A=1, B=1:
Carry (AND gate):
- A AND B = 1 AND 1 = 1
Sum (XOR circuit):
- A OR B = 1 OR 1 = 1
- A AND B = 1 AND 1 = 1
- NOT(A AND B) = NOT 1 = 0
- (A OR B) AND NOT(A AND B) = 1 AND 0 = 0
Result: sum = 0, carry = 1. That is correct: 1 + 1 = 10 in binary, which is “sum bit 0, carry bit 1.” The carry will propagate into the next bit position when chained with a full-adder.
An AND gate has inputs A=1 and B=1. What is its output?
An OR gate has inputs A=0 and B=0. What is its output?
A NOT gate has input A=1. What is its output?
In a half-adder, what gate produces the carry bit?
Half-adder with A=1, B=0: what is the sum bit?
Half-adder with A=1, B=0: what is the carry bit?
A half-adder computes the sum and carry of two single bits. Which gate produces the sum bit, and which gate produces the carry bit?
A logic gate is a physical hardware component that computes one boolean operation: AND, OR, or NOT. Its inputs and output are bits (0 or 1), and its behaviour is defined exactly by its truth table. Gates are built from transistors but are used as black-box abstractions. Connecting gates together produces a circuit that computes a more complex boolean function — any truth table you can write down can be realised as a circuit. A half-adder is a simple circuit built from an AND gate (carry output) and an XOR circuit (sum output) that adds two single bits correctly. Chaining full-adders extends this to multi-bit addition, forming the arithmetic logic unit inside every CPU. The path from bits to arithmetic is entirely made of gates.