Logic gates explained for beginners: AND, OR, NOT, XOR
A logic gate takes one or two inputs that are each on or off and gives a single on or off output by a fixed rule. AND is on when both inputs are on. OR is on when at least one is on. XOR is on when exactly one is on. NOT has one input and flips it.
The game above is Logic Gate. It draws a small circuit of these gates and asks if the last lamp is lit. This page has logic gates explained in the order a beginner needs: single gates first, then circuits, then what a set of gates can build.
What is a logic gate?
It is a device that computes a yes/no function of its inputs. Engineers write the two states as 1 and 0, and this page uses “on” and “off” because that is what the lamps in the game show.
A gate has no memory. The same inputs always give the same output, so a gate is fully described by a table that lists the output for every input combination. That table is called a truth table.
What do AND, OR, XOR and NOT do?
Each two-input gate has a truth table of four rows, one for each combination of inputs A and B.
| A | B | AND | OR | XOR | NAND | NOR |
|---|---|---|---|---|---|---|
| off | off | off | off | off | on | on |
| off | on | off | on | on | on | off |
| on | off | off | on | on | on | off |
| on | on | on | on | off | off | off |
Short ways to remember them:
- AND: on only in the last row. One off input is enough to switch it off.
- OR: off only in the first row. One on input is enough to switch it on.
- XOR: on when the inputs differ. The X stands for “exclusive”.
- NOT: one input, and the output is the opposite of it.
OR and XOR agree in three rows. They differ when both inputs are on, where OR gives on and XOR gives off.
What are NAND and NOR?
NAND is AND followed by NOT, and NOR is OR followed by NOT. Compare the columns in the table: NAND is the AND column flipped, and NOR is the OR column flipped.
They matter because each of them can build everything else. A set of gates that can express every truth table is called functionally complete, and NAND alone and NOR alone both qualify. Henry Sheffer published this result in 1913. AND with OR is not complete, because no combination of the two can produce a NOT.
How do you read a circuit from inputs to output?
Work from left to right, one gate at a time, and write down each result before moving on. Take a circuit with three inputs, where A and B feed an AND gate, its output and C feed an XOR gate, and a NOT gate comes last.
Say A is on, B is off and C is on.
- AND of on and off is off.
- XOR of that off and C, which is on, is on.
- NOT of on is off.
The last lamp is off. You never needed to hold more than one result in your head, because each step uses only the value before it and one fresh input.
Some shortcuts save a step. If one input to an AND is off, its output is off whatever the other input is. If one input to an OR is on, its output is on. XOR has no shortcut of this kind, since it always needs both inputs.
Where did logic gates come from?
The algebra came about eighty years before the circuits. George Boole set out an algebra of logic in An Investigation of the Laws of Thought, published in 1854. Claude Shannon connected it to hardware in his master’s thesis at MIT, A Symbolic Analysis of Relay and Switching Circuits, which he wrote in 1937 and which appeared in the Transactions of the American Institute of Electrical Engineers in 1938. The thesis showed that Boolean algebra could be used to simplify the arrangements of relays in telephone exchanges, and that arrangements of relays could in turn solve problems in Boolean algebra. MIT’s library record for the thesis carries the date 1940.
How many functions can each set of gates build?
There are 16 possible functions of two inputs, and the number a gate set can reach depends on which gates it has and how many it may use. We counted them with a short program.
The program starts with the two input wires, A and B. A gate may take its inputs from A, from B or from the output of an earlier gate, and both inputs of a gate may come from the same wire. It then tries every circuit of up to six gates and records which of the 16 truth tables appear. The plain wires A and B count as two functions that need no gates.
| Gates allowed | No gates | Up to 1 gate | Up to 2 gates | Gates needed to reach all 16 |
|---|---|---|---|---|
| AND, OR | 2 | 4 | 4 | Never, it stops at 4 |
| AND, OR, NOT | 2 | 6 | 14 | 4 |
| AND, OR, XOR, NOT | 2 | 8 | 16 | 2 |
| NAND only | 2 | 5 | 9 | 5 |
| NOR only | 2 | 5 | 9 | 5 |
| XOR, AND | 2 | 5 | 7 | Never, it stops at 8 |
With AND, OR and NOT, the two functions still missing after two gates are XOR and its opposite, XNOR. Each needs four gates. One way to build XOR is (A OR B) AND NOT (A AND B).
With NAND alone, XOR needs four gates and XNOR needs five. With NOR alone it is the other way round.
The four gates in our game reach all 16 functions within two gates, including always on and always off. The game’s own wirings use only some of those circuits: its NOT sits before or after a two-input gate.
How does Logic Gate build its circuits by level?
It moves through four stages, from a single AND or OR gate to three gates on three inputs. The step starts at the level saved for you and rises by one after every four circuits. A round lasts 45 seconds.
We read the stages from the game’s generator and counted the distinct circuits in each one, where a circuit means a wiring, a choice of gates and a setting of the input lamps.
| Step | Gates | Wirings | Input lamps | Distinct circuits | Points |
|---|---|---|---|---|---|
| 0 | AND, OR | One gate | 2 | 8 | 1 |
| 1 to 2 | AND, OR, XOR, NOT | One gate, or a gate followed by NOT | 2 | 24 | 1 |
| 3 to 5 | AND, OR, XOR, NOT | A gate followed by NOT, NOT on the first input and then a gate, or two gates in a chain | 2 or 3 | 96 | 1 |
| 6 and up | AND, OR, XOR, NOT | Two gates in a chain, a chain with NOT on the third input, or a chain followed by NOT | 3 | 216 | 1 for two gates, 2 for three |
In a chain, the first gate combines A and B, and the second gate combines that result with C.
At steps 1 and 2 the single-gate wiring comes up twice as often as the one with NOT.
In every stage exactly half of the distinct circuits end with the lamp on. The generator also aims for an even split while you play. In 4,000 circuits we generated at each of seven steps, between 50.7 and 51.0 percent ended on. Answering “off” every time gets about half of them right.
What is a good way to practice?
Say the gate’s rule to yourself as you pass it, and commit to each intermediate lamp before looking at the next gate. After you answer, the game lights every wire, so you can see which step went wrong.
When a NOT comes last, solve the rest of the circuit first and flip the result at the end.
For other rule-following puzzles, Code Breaker asks you to reason from clue marks and is covered in our code breaker strategy guide. Balance Scale compares weights across two scales, and Rule Flip keeps changing which rule applies. Mini Sudoku has its own page of rules for the 4x4 grid.
Common questions
What is a logic gate in simple terms?
A logic gate is a part of a circuit that takes one or two on/off inputs and gives one on/off output according to a fixed rule.
What is the difference between OR and XOR?
OR is on when at least one input is on, including when both are. XOR is on only when exactly one input is on, so two on inputs give off.
Why are NAND and NOR called universal gates?
Because every other gate can be built from NAND gates alone, or from NOR gates alone. With two inputs, either one can produce all 16 possible functions using at most five gates.
How many two-input logic functions are there?
Sixteen. Two inputs have four on/off combinations, and each combination can give on or off, which makes 2 to the power 4.