Boolean algebra & digital logic

1 · Boolean values & the core laws essential

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

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

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

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

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

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']