Boolean algebra & digital logic

1 · Boolean values & the core laws essential

Every if you have ever written is Boolean algebra in disguise. Think of the last time you wrote a condition like if user.is_admin and not user.is_banned — and then, three commits later, another engineer bolted an or onto it, and a fourth added a nested negation, until nobody could say for certain when the block actually ran. That tangle is a Boolean expression that was never simplified. The same maths that lets a chip designer shave gates off a circuit is the maths that would have collapsed that condition to something a human can read. Boolean algebra is not an academic warm-up; it is the grammar of every decision your code and your hardware make.

Here is the whole idea in one sentence: there are only two values, and a tiny handful of operations combine them, and the operations obey fixed algebraic laws — exactly like the + and × you learned in school, just with 1 and 0 instead of all the numbers. The everyday analogy is a light switch wired through a hallway: the light is on (1) or off (0), never "sort of on." Feed switches through AND (both must be up), OR (either will do), or NOT (flip it), and you can express any rule about when the light glows. That "only two values" constraint is what makes the algebra so clean — with just two states, you can literally check every case by hand.

The common mistake to name up front: people confuse Boolean + with ordinary addition and expect 1 + 1 = 2. It does not — Boolean + is OR, so 1 + 1 = 1 ("either input true → true, and it can't get truer than true"). Likewise · is AND, not multiplication in any counting sense, even though 1·1 = 1 and 1·0 = 0 happen to look familiar. Read + as "or" and · as "and" in your head every time, and the laws below stop looking like arithmetic tricks and start looking like plain statements about truth. Why the laws earn their own section: each one is a rewrite you're allowed to make without changing what the expression means, and in hardware every eliminated term is a physical gate you don't have to fabricate, power, or wait for.

Boolean algebra works on two values — 1/true and 0/false — with three operations: AND (·), OR (+) and NOT (¬ or ′). The laws below let you simplify expressions, which in hardware means fewer gates — cheaper, faster, cooler chips.

De Morgan is the workhorse: it lets you push a NOT through an AND/OR by flipping the operator. We can prove any law by exhausting the truth table — if both sides agree on all input rows, they're equal:

demorgan.py# ¬(A and B)  ==  (¬A) or (¬B)   for every A, B
def NOT(x): return 1 - x
def AND(a, b): return a & b
def OR(a, b):  return a | b

print("A B | ¬(A·B)  ¬A+¬B  equal?")
ok = True
for A_ in (0, 1):
    for B_ in (0, 1):
        left  = NOT(AND(A_, B_))
        right = OR(NOT(A_), NOT(B_))
        ok = ok and (left == right)
        print(f"{A_} {B_} |   {left}       {right}     {left == right}")
print("law holds for all rows:", ok)

A B | ¬(A·B)  ¬A+¬B  equal?
0 0 |   1       1     True
0 1 |   1       1     True
1 0 |   1       1     True
1 1 |   0       0     True
law holds for all rows: True

2 · Logic gates & truth tables essential

The leap that trips everyone up is realising the algebra is real hardware. In section 1, AND and OR were symbols on paper. Now picture a tiny electronic component — a few transistors — that takes two wires carrying voltage-high (1) or voltage-low (0) and produces a third wire whose voltage is the AND of the inputs. That component is a gate. It is not a metaphor for the algebra; it is the algebra made out of silicon and electrons. The first time this clicks, the whole computer stops being magic: it is millions of these little truth-obeying switches, wired together.

The tool for describing a gate exhaustively is the truth table — and it earns a moment of respect, because it is the single most honest thing in all of computer science. A truth table simply lists every possible input and the output for each. With two one-bit inputs there are exactly four rows (00, 01, 10, 11) — that's all of them, no cases hiding. Compare that to testing normal software, where the inputs are near-infinite and you can only ever sample: a gate's behaviour can be verified completely, forever, in four lines. When you write a truth table you are not summarising the gate, you are giving its full definition.

Think of a truth table like the settings chart on the back of a kitchen appliance: for each combination of dials, here is exactly what happens — no surprises, no "it depends." The common confusion to head off is between the negated gates and their bases. NAND is literally "AND, then flip the answer" (it's 1 everywhere AND is 0, and 0 only where AND is 1); NOR is "OR, then flip." And XOR — exclusive-or — is the one people misremember most: it is 1 only when the two inputs disagree, so it is really a "these two bits are different" detector, which is exactly why it becomes the sum bit of an adder later in this lesson. Read each column of the table below as its own gate, and notice how NAND/NOR are just the AND/OR columns turned upside down.

A gate is the physical realisation of a Boolean operation. Six matter. Note NAND (not-and) and NOR (not-or) are the negations of AND/OR, and XOR (exclusive-or) is 1 when the inputs differ.

gates.pygates = {
    "AND":  lambda a, b: a & b,
    "OR":   lambda a, b: a | b,
    "NAND": lambda a, b: 1 - (a & b),
    "NOR":  lambda a, b: 1 - (a | b),
    "XOR":  lambda a, b: a ^ b,
}
def truth_table(name):
    fn = gates[name]
    print(f"-- {name} --")
    for a in (0, 1):
        for b in (0, 1):
            print(f"  {a} {b} -> {fn(a, b)}")

truth_table("NAND")
truth_table("XOR")

-- NAND --
  0 0 -> 1
  0 1 -> 1
  1 0 -> 1
  1 1 -> 0
-- XOR --
  0 0 -> 0
  0 1 -> 1
  1 0 -> 1
  1 1 -> 0

3 · NAND is universal intermediate

Here is a fact that sounds like a party trick but reshapes how you see every chip: one single gate type can build everything. Not AND and OR and NOT — just NAND, repeated. A modern CPU with billions of transistors could, in principle, be built from nothing but one gate design stamped out over and over. When you first hear it you assume there must be a catch. There isn't. This is the closest thing digital logic has to a magic-is-real moment, and it's worth slowing down for.

The idea you need is functional completeness (engineers say a gate set is "universal"): a set of operations is complete if you can express every possible Boolean function using only those operations. We already know {AND, OR, NOT} is complete — anything true/false can be written with those three. So the whole argument reduces to a single question: can NAND alone reproduce AND, OR, and NOT? If yes, then by substitution NAND can build the three, and the three can build anything, so NAND can build anything. That chain — NAND → {AND, OR, NOT} → everything — is the entire proof, and the table and lab below just fill in the three constructions.

The everyday analogy: think of NAND as a Lego brick that happens to be shaped so cleverly that you can assemble any other brick shape out of copies of it. You don't stock a warehouse of a hundred part types; you stock one, and your factory line never has to change tools. That is precisely why fabrication plants adore it — a single, deeply optimised, well-characterised gate laid down millions of times is cheaper and more reliable than a zoo of different gates. The mistake to avoid is thinking universality makes NAND the fastest or smallest way to build any given circuit — it usually isn't; a purpose-built design uses fewer gates. Universality is a statement about what's possible with one primitive, not about what's optimal. (NOR is universal too, by the mirror-image argument.) Read the constructions below as recipes: tie NAND's inputs together to get NOT, then bolt an inverter onto NAND to recover AND, and invert the inputs to recover OR.

A gate set is universal if you can build every other gate from it. NAND alone is universal — which is why fabs love it: one gate type, laid down millions of times, becomes an entire processor. The constructions:

nand_universal.pydef NAND(a, b): return 1 - (a & b)

def NOT(a):    return NAND(a, a)
def AND(a, b): return NOT(NAND(a, b))
def OR(a, b):  return NAND(NOT(a), NOT(b))

for a in (0, 1):
    for b in (0, 1):
        print(a, b, "| NOT_a", NOT(a),
              "AND", AND(a, b), "OR", OR(a, b))

0 0 | NOT_a 1 AND 0 OR 0
0 1 | NOT_a 1 AND 0 OR 1
1 0 | NOT_a 0 AND 0 OR 1
1 1 | NOT_a 0 AND 1 OR 1

4 · Combinational logic: half & full adders advanced

At some point everyone wonders: how does a computer actually add? It has no notion of numbers, no fingers to count on — just gates that flip voltages. The honest, slightly astonishing answer is that a computer adds the exact same way a schoolchild does long addition: it adds one column at a time and carries the overflow to the next column. The only difference is the columns are bits, and the "carry the one" is a wire. In this section you will build that adder out of the gates you already have, and by the end you'll have assembled the arithmetic core of a real CPU from nothing but XOR and AND.

First, the word that gates this whole section: combinational. It means the circuit has no memory — the output depends only on the inputs sitting on the wires right now, never on what happened a moment ago. Give it the same inputs and you always get the same outputs, instantly, like a vending machine that dispenses the same snack for the same button every time. (Contrast that with sequential logic in section 6, which remembers — that distinction is the hinge the rest of the lesson turns on.) Addition is combinational because the sum of two bits depends only on those two bits, full stop.

Now recall single-column addition: 1 + 1 is 2, which in binary is 10 — you write down 0 and carry a 1. So adding two bits needs two outputs: the sum bit you keep, and the carry bit you pass left. Here's the beautiful part, and the reason XOR mattered earlier: the sum bit is 1 exactly when the inputs differ (that's XOR — 0+1 or 1+0 gives sum 1), and the carry is 1 exactly when both are 1 (that's AND). Two gates, and you've built a half adder. The common confusion is why it's only "half": it can't accept a carry coming in from a lower column, so it's useless past the first bit. Bolt on that third input and you get a full adder, and chaining full adders — each one's carry-out feeding the next one's carry-in, exactly like carrying the one leftward — gives a ripple-carry adder that adds full multi-bit numbers. That is the very binary arithmetic from df6, now built from this lesson's gates.

Combinational logic has no memory: outputs depend only on current inputs. The classic example is binary addition. A half adder adds two bits and outputs a sum and a carry: sum = A XOR B, carry = A AND B. A full adder also takes a carry-in, so you can chain them into a ripple-carry adder for multi-bit numbers — this is arithmetic in df6, built from the gates in this lesson.

adders.pydef half_adder(a, b):
    return (a ^ b, a & b)                 # (sum, carry)

def full_adder(a, b, cin):
    s1, c1 = half_adder(a, b)
    s2, c2 = half_adder(s1, cin)
    return (s2, c1 | c2)                  # (sum, carry_out)

def ripple_add(x, y, bits=4):
    "add two ints via chained full adders; return (result, overflow)"
    carry, out = 0, 0
    for i in range(bits):
        a = (x >> i) & 1
        b = (y >> i) & 1
        s, carry = full_adder(a, b, carry)
        out |= (s << i)
    return out, carry                     # carry = overflow out of top bit

print("half_adder(1,1) =", half_adder(1, 1))       # (0, 1)
print("full_adder(1,1,1) =", full_adder(1, 1, 1))  # (1, 1)
print("7 + 6 (4-bit) ->", ripple_add(7, 6))        # 13 fits, no overflow
print("9 + 8 (4-bit) ->", ripple_add(9, 8))        # 17 > 15 -> wraps + carry

half_adder(1,1) = (0, 1)
full_adder(1,1,1) = (1, 1)
7 + 6 (4-bit) -> (13, 0)
9 + 8 (4-bit) -> (1, 1)

5 · Minimizing with Karnaugh maps advanced

Picture two circuits that do the identical job — same truth table, same outputs on every input — but one uses twelve gates and the other uses two. The twelve-gate version is what you get by transcribing a truth table naively; the two-gate version is what a good engineer ships. That gap is money, heat, and nanoseconds: fewer gates means a cheaper chip, less power drawn, and a shorter path for the signal to travel. Minimization is the craft of getting from the twelve to the two without changing what the circuit means, and the Karnaugh map is the friendliest tool for doing it by eye.

You can minimize with pure algebra — grinding the laws from section 1 until nothing simplifies — but that's error-prone and easy to give up on too early. The K-map is the same job turned into a picture, and it exploits one gorgeous trick: it lays the truth table out so that physically adjacent cells differ by exactly one variable. That ordering is called Gray code (00, 01, 11, 10 — notice only one bit flips between neighbours, unlike the natural 00, 01, 10, 11). The whole point of that layout is that when two adjacent cells are both 1, the variable that changed between them cannot matter to the output, so you cross it out. Grouping is just "spot the variable that doesn't matter, and delete it."

The mental model is a printed map where you draw rings around clusters of 1s: the bigger the ring, the more variables vanish, so you always circle the largest groups you can, and groups must be rectangles sized in powers of two (1, 2, 4, 8…). The single most common mistake beginners make is forgetting that the map wraps around — the left edge is adjacent to the right edge, and the top to the bottom, like a globe — so a group can straddle the seams; miss that and you'll circle two small groups where one big one was hiding. The other trap is circling a group whose size isn't a power of two, which simply doesn't correspond to any valid algebraic simplification. In the worked example below, watch how the two columns where C=1 form one clean group of four, and both A and B change inside it — so both drop out and a four-term expression collapses to the single wire F = C.

A Karnaugh map (K-map) is a visual way to minimise a Boolean function — fewer terms means fewer gates. You arrange the truth table so adjacent cells differ by one variable (Gray code order: 00, 01, 11, 10), then circle groups of 1s in powers of two. Each group drops the variable that changes across it.

Worked example. Function F(A,B,C) is 1 for these minterms: A=0,B=0,C=1; A=0,B=1,C=1; A=1,B=1,C=1; A=1,B=0,C=1 — i.e. whenever C=1. The K-map (rows A, columns BC in Gray order):

Both 1-columns are exactly the C=1 columns (01 and 11) across both rows — one group of four cells. A and B both change inside the group, so they drop out. The minimised function is simply F = C. K-maps turn a 4-term sum-of-products into a single wire.

kmap.py# original sum-of-products vs the minimized form F = C
def F_full(A, B, C):
    return (((1-A) & (1-B) & C) | ((1-A) & B & C) |
            (A & B & C)         | (A & (1-B) & C))
def F_min(A, B, C):
    return C

same = all(F_full(a, b, c) == F_min(a, b, c)
           for a in (0, 1) for b in (0, 1) for c in (0, 1))
print("minimized form matches on all 8 rows:", same)

minimized form matches on all 8 rows: True

6 · Sequential logic: memory, clocks & state professional

Every circuit so far has had amnesia. The adder, the gates, the K-map — feed them inputs and they answer, but they never remember the last answer. That's fine for arithmetic, but it can't build a computer: a CPU has to hold a running total, keep a program counter, know which instruction is next. Something has to store a bit and keep storing it after the inputs go away. The question that opens this section is deceptively deep: how do you make a circuit remember, using only gates that forget?

The answer is one of the most elegant ideas in all of engineering: feedback. Take a gate's output and wire it back into its own input. Now the circuit's next state depends on its current state, and a value can chase its own tail around the loop, holding steady with no outside help. Cross-couple two NOR gates this way and you get an SR latch — one bit of genuine memory built from pure combinational parts. The everyday analogy is a seesaw that's been pushed fully to one side: it stays there, resting against the ground, until something actively shoves it the other way. The latch "rests" holding a 0 or a 1, and only a Set or Reset signal tips it over. Left alone, it remembers.

Raw feedback, though, is twitchy — the moment inputs jitter, the latch can react at unpredictable instants, and a big circuit full of latches updating whenever they please is a race-condition nightmare. The fix is the clock: a steady heartbeat (a square wave ticking millions or billions of times a second) that says "now, and only now, everyone update." A flip-flop is a latch disciplined to change only on the clock's edge — the instant it ticks — so the entire machine advances in lockstep, one clean step per tick. The mistake to avoid is imagining the clock stores anything; it doesn't, it only decides when storage happens. Bank a row of flip-flops together and you have a register (df8); the pattern of combinational logic computing the next value, plus registers holding the current value, plus a clock deciding when to swap them, is the template for every stateful machine — a counter, a traffic light, a CPU. This is exactly where state enters hardware, and it's why the model below is a state machine, not a wiring diagram.

Combinational logic forgets instantly. To remember a bit you need feedback. Cross-couple two NOR gates and you get an SR latch — the simplest 1-bit memory. A clock paces updates; a flip-flop is a latch that only changes on a clock edge. Registers (df8) are just banks of flip-flops. This is where state enters hardware.

We can model the latch's behaviour as a state machine in software (this is a behavioural model, not a gate-level circuit — real latches are analog feedback):

latch.pyclass SRLatch:
    def __init__(self): self.Q = 0        # stored bit
    def step(self, S, R):
        if S and R:
            raise ValueError("S=R=1 is invalid for an SR latch")
        if S:   self.Q = 1                 # set
        elif R: self.Q = 0                 # reset
        # else: hold previous Q (this is the "memory")
        return self.Q

l = SRLatch()
print("set   ->", l.step(1, 0))
print("hold  ->", l.step(0, 0))   # remembers 1 with no input
print("reset ->", l.step(0, 1))
print("hold  ->", l.step(0, 0))   # remembers 0

set   -> 1
hold  -> 1
reset -> 0
hold  -> 0

Knowledge check check yourself

def XOR(a, b): return a ^ b
for a in (0, 1):
    for b in (0, 1):
        print(a, b, '->', XOR(a, b))
# 0 0 -> 0 / 0 1 -> 1 / 1 0 -> 1 / 1 1 -> 0

ok = all((A | (A & B)) == A
         for A in (0, 1) for B in (0, 1))
print('absorption holds:', ok)   # True

def NAND(a, b): return 1 - (a & b)
def XOR(a, b):
    t = NAND(a, b)
    return NAND(NAND(a, t), NAND(b, t))

ok = all(XOR(a, b) == (a ^ b)
         for a in (0, 1) for b in (0, 1))
print('XOR-from-NAND correct:', ok)   # True

def full_adder(a, b, cin):
    s = a ^ b ^ cin
    cout = (a & b) | (cin & (a ^ b))
    return s, cout

def add(x, y, bits):
    carry, out = 0, 0
    for i in range(bits):
        s, carry = full_adder((x>>i)&1, (y>>i)&1, carry)
        out |= s << i
    return out, carry

print(add(13, 3, 4))   # (0, 1)  -> 16 wraps to 0, carry set
print(add(13, 3, 5))   # (16, 0) -> fits in 5 bits

def F_full(A, B, C):
    return (A&B&C) | (A&B&(1-C)) | (A&(1-B)&C)
def F_min(A, B, C):
    return A & (B | C)

assert all(F_full(a,b,c) == F_min(a,b,c)
           for a in (0,1) for b in (0,1) for c in (0,1))
print('F = A(B + C) verified')

class TrafficLight:
    NEXT = {'GREEN': 'YELLOW', 'YELLOW': 'RED', 'RED': 'GREEN'}
    def __init__(self): self.state = 'RED'   # stored in flip-flops
    def tick(self):                           # clock edge
        self.state = self.NEXT[self.state]
        return self.state

fsm = TrafficLight()
print([fsm.tick() for _ in range(6)])
# ['GREEN', 'YELLOW', 'RED', 'GREEN', 'YELLOW', 'RED']