Toffoli gate (CCNOT): truth table and circuit, live
A Toffoli gate, or controlled-controlled-NOT (CCNOT), has three inputs and three outputs: A and B pass straight through, and the third bit is flipped only when both A and B are 1, so P = A, Q = B and R = C XOR (A AND B). It is reversible: every output pattern comes from exactly one input pattern, and applying the gate twice gives the inputs back.
The gate is named after Tommaso Toffoli, whose 1980 paper on reversible computing introduced it. Ordinary gates throw information away (from an AND output of 0 you cannot tell which input was 0), and the Toffoli gate is built not to: with three outputs for three inputs, the truth table below is a permutation of the eight input patterns. It is universal for reversible logic: set C = 0 and R = A AND B; set C = 1 and R = A NAND B, and NAND alone builds everything (see the NAND universal gates). In quantum computing the same operation is the CCNOT gate on qubits. In ordinary logic it is just an AND feeding an XOR, which is what this live circuit is; all eight rows are checked before the page is built, and it starts at 000.
Open this circuit in the lab →
What you need
- 1× AND: A AND B, the control condition
- 1× XOR: R = C XOR (A AND B): flips C when both controls are 1
Step by step
- Place inputs
A,B,Cand probesP,Q,R. - Wire A straight to P and B straight to Q: the two control bits pass through unchanged.
- AND A with B.
- XOR that result with C and probe it as R.
- Set A = B = 1 and toggle C: R is always the opposite of C. With either control at 0, R just copies C.
Toffoli gate truth table
| A | B | C | P | Q | R |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 |
Each of the eight output rows appears exactly once, so the gate can be run backwards: feed P, Q, R back in and you get A, B, C. Only the last two rows, where A = B = 1, change anything. Its partner in reversible logic is the Fredkin gate, a controlled swap, introduced in Fredkin and Toffoli's 1982 paper on conservative logic. With only one control bit it becomes the CNOT gate.
You can also read the full theory in the lesson on the XOR gate. Prefer to build it yourself from scratch? Open the digiwleea lab and place the gates on the canvas, or start from the logic gate simulator.
More builds: Universal gates: NAND only, NOR only
All 246 build guides, by topic
Each of these is one step from a transistor to a working CPU. Build every gate from CMOS transistors and work all the way up in the free digiwleea lab, with the free theory reference alongside.
Open the Toffoli gate in the lab →Frequently asked
What is a Toffoli gate?
A three-bit reversible logic gate, also called CCNOT: it passes A and B through unchanged and flips C when both A and B are 1, so its outputs are A, B and C XOR (A AND B).
Why is the Toffoli gate universal?
With C fixed at 1 its third output is NAND(A, B), and NAND can build every other logic function, so Toffoli gates alone can compute anything, while staying reversible.
Is the Toffoli gate reversible?
Yes. Its truth table maps the eight input patterns one to one onto the eight output patterns, and applying the gate twice returns the original inputs.
What is the difference between a Toffoli gate and a Fredkin gate?
A Toffoli gate flips its third bit when both controls are 1. A Fredkin gate is a controlled swap: when its control bit is 1 it swaps the other two bits. Both are reversible and universal.