Logic Gates & Boolean Simplification
Logic gates are the physical switches everything else in a computer is built from. This page focuses on two things worth genuinely understanding: how simple gates combine into a circuit that actually adds binary numbers, and how to simplify a Boolean expression with proof at every step, not just a final answer to trust.
The basic gates
Pick a gate and toggle its inputs. Watch which row of the truth table lights up to match.
Choose a gate
Exam tips
- NAND and NOR are just AND/OR with the output inverted, one extra NOT on the end.
- XOR outputs 1 only when the inputs differ, this is exactly what makes it useful for addition.
Proof: NAND alone can build every other gate
This is why NAND is called a universal gate. You don't strictly need separate NOT, AND and OR gates at all, wiring NAND gates together in the right pattern reproduces every one of them exactly. This is a genuine reason real chips are built almost entirely from one repeated gate design.
How each gate is built from NAND alone
| Gate | Built from NAND as |
|---|---|
| NOT(A) | NAND(A, A) |
| AND(A,B) | NAND(NAND(A,B), NAND(A,B)) |
| OR(A,B) | NAND(NAND(A,A), NAND(B,B)) |
NOT is just NAND fed the same input twice. AND is NAND's output inverted (using the NOT-from-NAND trick on itself). OR is built by inverting both inputs first, then NANDing those, which is exactly De Morgan's law in physical form.
Building a real circuit: binary addition in hardware
Remember doing binary column addition by hand, writing the bit and carrying the 1? This is the actual circuit that does exactly that, built from nothing but two gates.
Half adder (adds two single bits)
Full adder (adds two bits plus a carry-in, so they can be chained)
Built from exactly two half adders (the circuit above, used twice) plus one OR gate to combine their two carry outputs.
Exam tips
- Half adder: SUM = A XOR B, CARRY = A AND B. It only handles two bits with no incoming carry, so it can't be chained on its own.
- Full adder: SUM = A XOR B XOR Cin, COUT = (A AND B) OR (Cin AND (A XOR B)). Chain several full adders together, each one's carry-out feeding the next one's carry-in, and you can add numbers of any size.
- This is genuinely how addition happens in a real CPU's ALU, not a simplified analogy.
Chaining full adders: a real 4-bit adder
Four full adders, wired so each one's carry-out feeds the next one's carry-in, exactly like the overflow work you've already covered, except this time it's genuinely happening in the circuit, not just described in words. Set two 4-bit numbers and watch the carry ripple through, right to left.
A (bits 8,4,2,1)
B (bits 8,4,2,1)
Exam tips
- Carries ripple from the least significant bit (rightmost) to the most significant (leftmost), exactly the direction you were taught for binary addition by hand.
- A final carry out of the leftmost full adder, with nowhere further to go, is precisely what overflow looks like in hardware: it's the same discarded bit from the overflow lesson, now visibly produced by a real chain of gates.
- This "ripple" design is simple but has a real downside: bit 3's adder can't finish until bit 0, 1 and 2 have all rippled their carries through first, which is why faster (but more complex) adder designs exist in real CPUs.
Boolean laws, verified live
Not just a table to memorise, toggle A, B and C and watch every law hold true for every combination you try. That's what makes these laws, laws, rather than a coincidence for one specific input.
Simplifying with proof, not just an answer
Every step below is checked against a live truth table. If simplifying ever changed the actual logic, you'd see the table stop matching, it doesn't, at any step.
Truth table (unchanged throughout)
De Morgan's law: the classic exam trap
It's tempting to think NOT(A AND B) is just NOT(A) AND NOT(B). It isn't. Toggle the inputs and watch both sides of each law stay identical, while the "wrong" version breaks.