COMPUTER ORGANIZATION & ARCHITECTURE / 2. BOOLEAN ALGEBRA

Boolean Algebra & Logic Simplification

The math behind digital logic — minimizing circuits saves transistors

EXPLANATION

Boolean Algebra is the mathematical framework for working with binary values (0 and 1, True and False). It was invented by George Boole in 1854 — nearly 100 years before computers. Claude Shannon proved in 1937 that Boolean algebra could describe electrical circuits. This is the mathematical foundation of all digital logic.

Boolean Algebra Laws — these let you simplify logic expressions, reducing the number of gates needed (fewer gates = smaller chip = less power = faster):

Identity Laws:
- A + 0 = A (OR with 0 changes nothing)
- A · 1 = A (AND with 1 changes nothing)

Null Laws:
- A + 1 = 1 (OR with 1 is always 1)
- A · 0 = 0 (AND with 0 is always 0)

Idempotent Laws:
- A + A = A
- A · A = A

Complement Laws:
- A + A' = 1 (something OR its opposite is always true)
- A · A' = 0 (something AND its opposite is always false)

Commutative: A + B = B + A, A · B = B · A
Associative: (A+B)+C = A+(B+C)
Distributive: A·(B+C) = A·B + A·C

De Morgan's Theorems — the most important laws for circuit design:
- (A · B)' = A' + B' → NAND equals NOT-A OR NOT-B
- (A + B)' = A' · B' → NOR equals NOT-A AND NOT-B
These let you convert between AND/OR forms, and explain why NAND and NOR are universal.

Karnaugh Maps (K-Maps):
A visual tool for minimizing Boolean expressions. Group adjacent 1s in powers of 2 (1, 2, 4, 8). Each group eliminates one variable. The result is the minimal Sum of Products (SOP) expression — the fewest gates possible.

Canonical forms:
- Sum of Products (SOP): F = AB + AC' + BC — ORing together AND terms
- Product of Sums (POS): F = (A+B)(A+C') — ANDing together OR terms
Both are equivalent. SOP maps to AND-OR circuit, POS maps to OR-AND circuit.

Minterms and Maxterms: every Boolean function can be expressed as a sum of minterms (one per row where output=1) or product of maxterms (one per row where output=0).

DIAGRAM

K-MAP EXAMPLE (3 variables: A, B, C):
  Truth table:          K-Map (Gray code order!):
  A B C | F                  BC
  ──────┼──           A  │ 00  01  11  10
  0 0 0 │ 1              ───┼────────────────
  0 0 1 │ 1           0  │  1   1   0   0
  0 1 0 │ 0              │
  0 1 1 │ 0           1  │  1   0   0   1
  1 0 0 │ 1              
  1 0 1 │ 0           Groups:
  1 1 0 │ 0           ┌──────────┐  A=0, B=0 → B'
  1 1 1 │ 1           │  1    1  │  eliminates C
                      └──────────┘  → term: A'B'

                       ┌──┐    ┌──┐
                       │1 │    │ 1│  A=0,C=0 + A=1,C=0
                       └──┘    └──┘  → term: C'  ... etc

  Simplified: F = A'B' + A'C' + AB C  (fewer gates than SOP from truth table!)

  DE MORGAN'S — the most useful identity:
  (AB)' = A' + B'    ← NAND = OR of NOTs
  (A+B)' = A' · B'   ← NOR = AND of NOTs

CODE

PYTHON

1from itertools import product
2
3# ── Boolean expression evaluator ───────────────────────
4def evaluate(expr_fn, variables):
5    """Evaluate a boolean function for all input combinations"""
6    n = len(variables)
7    print(f"
8{'  '.join(variables)} | F")
9    print("─" * (3*n + 4))
10    minterms = []
11    for values in product([0, 1], repeat=n):
12        kwargs = dict(zip(variables, values))
13        result = expr_fn(**kwargs)
14        row = "  ".join(str(v) for v in values)
15        print(f"  {row} | {result}")
16        if result:
17            minterms.append(values)
18    return minterms
19
20# ── Example: F = A'B' + AB ─────────────────────────────
21def F1(A, B):
22    return (not A and not B) or (A and B)  # XNOR!
23
24print("F = A'B' + AB  (which is XNOR):")
25minterms = evaluate(F1, ["A", "B"])
26
27# ── De Morgan's theorem verification ──────────────────
28print("
29De Morgan's Verification:")
30print("(A AND B)' should equal (A' OR B')")
31for A, B in product([0,1], repeat=2):
32    lhs = not (A and B)
33    rhs = (not A) or (not B)
34    match = "✓" if lhs == rhs else "✗"
35    print(f"  A={A} B={B}: NAND={int(lhs)}, NOT-A OR NOT-B={int(rhs)} {match}")
36
37print("
38(A OR B)' should equal (A' AND B')")
39for A, B in product([0,1], repeat=2):
40    lhs = not (A or B)
41    rhs = (not A) and (not B)
42    match = "✓" if lhs == rhs else "✗"
43    print(f"  A={A} B={B}: NOR={int(lhs)}, NOT-A AND NOT-B={int(rhs)} {match}")
44
45# ── Boolean law verification ───────────────────────────
46print("
47Boolean Laws verified:")
48laws = [
49    ("A + 0 = A",  lambda A: (A or 0) == A),
50    ("A · 1 = A",  lambda A: (A and 1) == A),
51    ("A + 1 = 1",  lambda A: (A or 1) == 1),
52    ("A · 0 = 0",  lambda A: (A and 0) == 0),
53    ("A + A' = 1", lambda A: (A or not A) == 1),
54    ("A · A' = 0", lambda A: (A and not A) == 0),
55    ("A + A = A",  lambda A: (A or A) == A),
56]
57for name, law in laws:
58    holds = all(law(A) for A in [0, 1])
59    print(f"  {name:<20} {'✓ holds' if holds else '✗ FAILS'}")

← PREV1. Transistors & Logic Gates NEXT →3. Combinational Circuits