Logic Gates Explorer

click inputs and watch signals flow through gates

Loading interactive simulation...

NAND alone can build any circuit 🖖

NAND is functionally complete: NOT, AND, and OR can all be built entirely from NAND combinations, which is why many real chips standardize on a single small gate primitive.

Every gate is a tiny yes/no decision 🖖

A logic gate reads its inputs as HIGH (1) or LOW (0) voltages and outputs a single 1 or 0 by one fixed rule — AND wants both high, OR wants at least one, XOR wants them to differ. The truth table below is the gate's complete definition: list every input combination with its output and there is nothing left to know. Stack enough of these tiny decisions together and you get adders, memory, and eventually a whole processor.

A correct circuit can still flicker 🖖

Signals do not arrive instantly — each gate adds a small propagation delay, and two paths to the same output can have different lengths. When an input changes, the output can momentarily show the wrong value before settling, called a glitch or hazard, even though the truth table is perfectly correct. Watch the timing strip: the output edge lags the input edge by exactly this gate delay, and in multi-gate circuits those delays stack into visible races.

DIGITAL LOGIC — WHICH BUILDING BLOCK DOES THE JOB?

Which Logic Case Are You In?

Every digital circuit is a truth table wearing a diagram. The question is never what a gate does — it is which table you need: one decision taken from two bits, a whole logic family built from a single spare part, arithmetic with its carry, or a switch that picks one signal out of several. These four cases cover most of what a first course will ask of you.

One decision from two bits — pick the gate by its column Y = A ⊕ B

Only one kind of gate available — NAND is enough NOT A = NAND(A, A)

Arithmetic, not a decision — sum is XOR, carry is AND S = A ⊕ B, C = A ∧ B

Choosing rather than combining — use a multiplexer Y = A·¬S + B·S

One decision from two bits — pick the gate by its column

What you know: Two inputs, one output, and a rule you can write as four rows. Choose the gate whose output column matches the rule you want.

Logic: Y = A ⊕ B

Worked example: XOR with A = 1 and B = 0 gives 1; the same gate gives 0 whenever the two inputs agree

Open this case: XOR differs

One decision from two bits — pick the gate by its column. Four rows pin the gate down completely; the highlighted row is the input you set. Two inputs, one output, and a rule you can write as four rows. Choose the gate whose output column matches the rule you want. — Four rows pin the gate down completely; the highlighted row is the input you set.

Only one kind of gate available — NAND is enough

What you know: NAND is functionally complete. Every other gate can be wired from copies of it alone, and so can any circuit you can describe with a truth table.

Logic: NOT A = NAND(A, A)

Worked example: NAND(1, 1) = 0. Tie the inputs together and NAND(A, A) = NOT A; feed that back in and two NANDs make an AND

Open this case: NAND universal

Only one kind of gate available — NAND is enough. A NAND with its inputs tied together is an inverter, and that is the trick the rest is built on. NAND is functionally complete. Every other gate can be wired from copies of it alone, and so can any circuit you can describe with a truth table. — A NAND with its inputs tied together is an inverter, and that is the trick the rest is built on.

Arithmetic, not a decision — sum is XOR, carry is AND

What you know: Adding two bits produces a two-bit answer. The low bit is A XOR B and the high bit, the carry, is A AND B.

Logic: S = A ⊕ B, C = A ∧ B

Worked example: 1 + 1 gives sum = 0 and carry = 1, which is binary 10 — the only row of the four where the carry fires

Open this case: half adder 1+1

The same two inputs feed both gates: XOR produces the sum bit, AND produces the carry.

Choosing rather than combining — use a multiplexer

What you know: Two data inputs and a select line. The output copies whichever input the select points at and ignores the other one completely.

Logic: Y = A·¬S + B·S

Worked example: A = 0, B = 1, S = 1 → out = 1, since out = A·(NOT S) + B·S

Open this case: mux select

Choosing rather than combining — use a multiplexer. The select line routes one input through to the output and blocks the other. Two data inputs and a select line. The output copies whichever input the select points at and ignores the other one completely. — The select line routes one input through to the output and blocks the other.

References (1)

Insight block 3 — the glitch a correct truth table still allows: D. A. Huffman, "The Design and Use of Hazard-Free Switching Networks." Journal of the ACM 4(1), 47–62, 1957.

Problem solved in full

A half adder built from NAND gates alone, and why five is the floor 8 steps
A fab will sell you one part and one part only: the two-input NAND gate. Build the half adder the tool draws under Half Adder — one sum bit, one carry bit — out of nothing else. How many NAND gates does it take, and how would you know you had found the cheapest one?
1. Start with NOT, which is the cheapest thing a NAND can be talked into. Tie both its inputs to the same wire. The gate asks "are both of these high?", and both of them are A, so it answers whenever A does not.
  
  $A ↑ A = \neg (A \land A) = \neg A$
2. AND costs one more. A NAND already is an AND with its answer turned upside down, so turn it back up: feed the output into a NOT, which by step 1 is a second NAND with its legs tied. OR takes three, by inverting each input before a NAND, which is De Morgan read backwards.
  
  $(A ↑ B) ↑ (A ↑ B) = \neg\neg (A \land B) = A \land B$
3. XOR is the one that resists. The trick is to compute the middle term once and play it back against each input in turn. Call it C, and feed it into a NAND against A, and again against B.
  
  $C = A ↑ B, D = A ↑ C, E = B ↑ C$
4. Expand D. It reads "not both A and (not A or not B)". The A-and-not-A half of that can never happen, so it falls out, and what is left is short. E is the same sentence with the letters swapped.
  
  $D = \neg (A \land (\neg A \lor \neg B)) = \neg (A \land \neg B), E = \neg (B \land \neg A)$
5. The last NAND joins them. De Morgan turns a NAND of two negations into a plain OR, and an OR of "A but not B" with "B but not A" is what XOR means. Four gates for the sum bit.
  
  $D ↑ E = (A \land \neg B) \lor (B \land \neg A) = A \oplus B$
6. Now the carry. It is A AND B, which you priced at two gates in step 2 — but the first of those two is C, and C is already sitting on a wire in the middle of the XOR you just built. Read it a third time and tie it to itself.
  
  $C ↑ C = \neg (A ↑ B) = A \land B$
7. So five, not six. Half of that you have just built: the carry costs 2 on its own by step 2, the sum costs 4 by step 5, and step 6 is the observation that they share exactly one gate, so 2 + 4 − 1 = 5. That nothing beats five is a separate claim, and nothing on this page establishes it: it comes from exhaustively searching every NAND network of six gates or fewer over two inputs, which is a computation rather than an argument.
  
  $\neg : 1, \land : 2, \lor : 3, \oplus : 4, {S, C} : 5$
8. The gate count says nothing about time. Follow the carry: out of G1, straight into G5, two gates deep. The sum has to pass G2 or G3 and then G4, so it is three deep. Count the routes from A to the sum and they are not even the same length as each other.
  
  $A \to G_{2} \to G_{4} = 2 gates, A \to G_{1} \to G_{2} \to G_{4} = 3 gates$
Answer

Five NAND gates, and five is the floor. Set the tool to Half Adder with A = 1 and B = 1 and it says the sum bit wraps to 0 and carry becomes 1. Trace that row through the sketch: C = 0, then D = E = 1, then S = 0, and the carry gate reading C against itself gives 1. C is computed once and read three times, and that is the whole saving.

The depths in step 8 have a consequence the truth table cannot show. Come at 1 + 1 from the row above it, with A already high and B rising. The carry goes up after two gate delays; the sum does not come down until the third. For one full gate delay the two output pins read 1 and 1, which as carry-and-sum is binary 11, and the adder is briefly claiming that 1 + 1 = 3. A clocked chip never sees it, because the clock period is chosen to be longer than the slowest path through the logic. Choosing it too short is what a timing violation is.

By the 42Math team · Updated 2026-07-27

Reviewed against published sources. Corrections welcome. Editorial policy · Corrections

All Computing lessons →

Example problems

XOR differs - XOR A=1 B=0 -> 1: true when inputs differ
NAND universal - NAND(1,1) = 0 - NAND inverts AND; it can build every other gate
half adder 1+1 - Half adder 1+1: Sum=0 Carry=1 - the same carry ripples through every CPU
mux select - Multiplexer S=1 routes input B to output regardless of A