11. Boolean Algebra

Boolean algebra is the algebra of the two values 0 and 1 under complement, sum (OR) and product (AND). It is the propositional logic of Chapter 1, rewritten so that you can calculate with it the way you calculate with ordinary algebra. This chapter studies Boolean functions and the identities between them, and shows that a few operations are enough to build every function. It then turns expressions into logic circuits, including the adders inside every processor, and ends with systematic methods for making those circuits as small as possible. The same ideas appear in bitmask code, query optimizers, SAT encodings and every digital chip.

<a id="111-boolean-functions"></a>

11.1 Boolean Functions

This subchapter defines Boolean expressions and functions and collects the identities used to rewrite them. It then answers two questions: how to build an expression for any function from its truth table, and which sets of operations are enough to express every function.

Boolean Expressions

Why. Chapter 1 asked whether statements are true. Engineers who design circuits, and programmers who manipulate bitmasks, ask a different question: given these input bits, which output bit should be produced, and how can it be computed cheaply? For that work it helps to write logic as algebra, with + and · in place of ∨ and ∧. Expressions then look like polynomials, and the habits of school algebra (expanding, factoring, collecting terms) carry over, with a few important exceptions.

What. Let B = {0, 1}. Boolean algebra uses three operations on B:

Operation	Notation	Value	Logic (1.1)	Sets (2.1)	Python on 0/1 ints
Complement	x' (also x̄, ¬x)	0' = 1, 1' = 0	¬p	Aᶜ	1 - x or x ^ 1
Boolean sum	x + y	1 if at least one of x, y is 1	p ∨ q	A ∪ B	x | y
Boolean product	x · y or xy	1 if both x and y are 1	p ∧ q	A ∩ B	x & y

  x  y │  x'   x + y   xy
  0  0 │  1      0      0
  0  1 │  1      1      0
  1  0 │  0      1      0
  1  1 │  0      1      1

Note that 1 + 1 = 1. The Boolean sum is neither integer addition (which gives 2) nor addition mod 2 (which gives 0, and is XOR, written ⊕). It means "at least one", so x + y = max(x, y), while xy = min(x, y).

Precedence. Complement binds tightest, then product, then sum, just like ¬, ∧, ∨ in 1.1 and like −, ×, + in arithmetic. So x + yz' means x + (y · (z')).

Definitions.

• A Boolean variable takes values in B.
• Bⁿ is the set of n-tuples of bits. It has 2ⁿ elements.
• A Boolean function of degree n is a function F: Bⁿ → B.
• Boolean expressions are defined recursively (3.3). Basis: 0, 1 and the variables x₁, …, xₙ are expressions. Recursive step: if E₁ and E₂ are expressions, so are (E₁)', (E₁ + E₂) and (E₁E₂).

Every expression defines a function by evaluation. Two expressions are equal (E₁ = E₂) when they define the same function, that is, when they agree on all 2ⁿ inputs. For example, x + xy = x, because both are 1 exactly when x = 1. Many expressions describe the same function, and the rest of the chapter is about picking a good one.

How many functions? A truth table for n variables has 2ⁿ rows, and each row's output can be chosen independently, so by the product rule (5.1) there are 2^(2ⁿ) functions of degree n:

n	Rows 2ⁿ	Functions 2^(2ⁿ)
1	2	4
2	4	16
3	8	256
4	16	65,536
5	32	4,294,967,296
6	64	≈ 1.8 × 10¹⁹

All 16 functions of two variables, with outputs listed for xy = 00, 01, 10, 11. Several of them reappear as gates in 11.2:

Outputs	Expression	Name	Outputs	Expression	Name
0000	0	constant 0	1000	(x + y)'	NOR
0001	xy	AND	1001	(x ⊕ y)'	XNOR (equivalence)
0010	xy'	x and not y	1010	y'	NOT y
0011	x	projection	1011	x + y'	y → x
0100	x'y	y and not x	1100	x'	NOT x
0101	y	projection	1101	x' + y	x → y
0110	x ⊕ y	XOR	1110	(xy)'	NAND
0111	x + y	OR	1111	1	constant 1

Example. F(x, y, z) = xy + z':

  x y z │ xy   z' │ F = xy + z'
  0 0 0 │  0   1  │  1
  0 0 1 │  0   0  │  0
  0 1 0 │  0   1  │  1
  0 1 1 │  0   0  │  0
  1 0 0 │  0   1  │  1
  1 0 1 │  0   0  │  0
  1 1 0 │  1   1  │  1
  1 1 1 │  1   0  │  1

from itertools import product

def truth_table(f, n):
    """Outputs of f on all 2^n inputs, in binary order 00…0, 00…1, …, 11…1."""
    return tuple(f(*bits) for bits in product((0, 1), repeat=n))

NOT = lambda x: 1 - x

F = lambda x, y, z: (x & y) | NOT(z)              # F = xy + z'
print(truth_table(F, 3))                          # (1, 0, 1, 0, 1, 0, 1, 1)

# Two expressions are equal iff their truth tables agree
G = lambda x, y: x | (x & y)                      # x + xy
H = lambda x, y: x                                # x
print(truth_table(G, 2) == truth_table(H, 2))     # True  (absorption, next topic)

# Bit-parallel evaluation: bit r of each mask holds that variable's value in row r = 4x + 2y + z.
# One bitwise expression then computes all 8 rows at once.
x, y, z = 0b11110000, 0b11001100, 0b10101010
table = (x & y) | (~z & 0xFF)                     # ~z flips all bits; the mask keeps 8 of them
print(f"{table:08b}")                             # 11010101  row 7 is the leftmost bit

The last example reads the truth table as one integer. This is not just a trick. An FPGA implements a k-input function as a lookup table: a small memory that stores exactly these 2ᵏ output bits, indexed by the input.

Analogy. A Boolean function is the lookup table and an expression is a recipe that produces it. Many recipes give the same dish. Circuit design is the search for the cheapest recipe.

Key takeaways

• Boolean algebra works on {0, 1} with complement x', sum x + y (OR) and product xy (AND). Precedence is complement, then product, then sum.
• 1 + 1 = 1: the Boolean sum is "at least one", not integer addition and not XOR.
• A Boolean function of degree n maps Bⁿ → B. There are 2^(2ⁿ) of them.
• Expressions are equal when they define the same function, and many expressions define each function.

Practice

1. (Beginner) Build the truth table of F(x, y, z) = x'y + (x + z)'. On which inputs is F = 1?
2. (Intermediate) How many Boolean functions of degree 3 satisfy F(0, 0, 0) = 0? How many are symmetric in x and y, that is, satisfy F(x, y, z) = F(y, x, z) for all inputs?
3. (Interview) In Python, True + True == 2. Write the Boolean sum of two 0/1 integers using only +, − and ×, and explain why (x + y) % 2 is wrong. Hint: inclusion–exclusion (5.5), |A ∪ B| = |A| + |B| − |A ∩ B|.

Boolean Identities

Why. Every operator in an expression costs a gate in hardware or an instruction in software, so simplifying expressions matters. The identities below are the laws of 1.1 rewritten in Boolean notation, and they are the moves you are allowed to make. Several of them hold in more than just {0, 1}, as the abstract definition at the end of this topic shows, so a proof done once applies to sets, bit vectors and logic alike.

What. For all x, y, z ∈ B:

Identity	Sum form	Product form
Double complement	(x')' = x
Idempotent	x + x = x	xx = x
Identity	x + 0 = x	x · 1 = x
Domination	x + 1 = 1	x · 0 = 0
Commutative	x + y = y + x	xy = yx
Associative	x + (y + z) = (x + y) + z	x(yz) = (xy)z
Distributive	x + yz = (x + y)(x + z)	x(y + z) = xy + xz
De Morgan	(x + y)' = x'y'	(xy)' = x' + y'
Absorption	x + xy = x	x(x + y) = x
Unit / zero property	x + x' = 1	xx' = 0

Some of these look wrong if you read them as ordinary algebra:

Identity	Boolean algebra	Real numbers
x + x = x	Always	Only for x = 0
x + 1 = 1	Always	Never
x + yz = (x + y)(x + z)	Always (+ distributes over ·)	Rarely
x(y + z) = xy + xz	Always	Always

Two ways to prove an identity.

1. Truth table. Check all 2ⁿ inputs. This is mechanical and always works, but the cost doubles with every variable.
2. Algebra. Rewrite one side into the other, naming the law used at each step.

Three derived identities are worth memorizing, because they do most of the work of simplification:

Name	Identity	Dual form
Redundant literal	x + x'y = x + y	x(x' + y) = xy
Combining (adjacency)	xy + xy' = x	(x + y)(x + y') = x
Consensus	xy + x'z + yz = xy + x'z	(x + y)(x' + z)(y + z) = (x + y)(x' + z)

x + x'y = (x + x')(x + y)            Distributive (+ over ·)
        = 1 · (x + y)                Unit property
        = x + y                      Identity

xy + xy' = x(y + y')                 Distributive
         = x · 1                     Unit property
         = x                         Identity

xy + x'z + yz = xy + x'z + yz(x + x')        Identity, unit property
              = xy + x'z + xyz + x'yz        Distributive
              = xy(1 + z) + x'z(1 + y)       Commutative, distributive
              = xy + x'z                     Domination, identity

The combining rule xy + xy' = x drives all of circuit minimization (11.3). The consensus theorem says that the term yz is redundant: whenever yz = 1, either x = 1 (so xy = 1) or x = 0 (so x'z = 1).

There is no cancellation. x + y = x + z does not imply y = z: take x = 1, y = 0, z = 1. Likewise xy = xz does not imply y = z: take x = 0. Boolean algebra has no subtraction or division to undo an operation.

Boolean algebra as a structure. A Boolean algebra is a set B with two binary operations ∨ and ∧, a unary operation ', and two distinct elements 0 and 1, satisfying, for all x, y, z, the identity, complement (unit/zero), associative, commutative and distributive laws from the table. The other laws (idempotent, domination, absorption, De Morgan) can be derived from these. Equivalently, a Boolean algebra is a bounded distributive lattice (2.5) in which every element has a complement.

Boolean algebra	Elements	∨	∧	x'	0	1
Bits	{0, 1}	OR	AND	1 − x	0	1
Power set	Subsets of S	∪	∩	S − A	∅	S
Bit vectors	n-bit words	bitwise OR	bitwise AND	bitwise NOT	00…0	11…1
Boolean functions	Functions Bⁿ → B	pointwise +	pointwise ·	pointwise '	constant 0	constant 1
Divisors of 30	{1, 2, 3, 5, 6, 10, 15, 30}	lcm	gcd	30 / a	1	30

The divisors of 12 do not form a Boolean algebra. A complement c of 2 would need gcd(2, c) = 1 (so c is odd) and lcm(2, c) = 2c = 12 (so c = 6), which is impossible. In general, the divisors of n form a Boolean algebra exactly when n is squarefree. Every finite Boolean algebra is isomorphic to the power set of some finite set, so its size is a power of 2. The divisors of 30 correspond to P({2, 3, 5}).

from itertools import product
from math import gcd

def is_identity(lhs, rhs, n):
    """Check lhs = rhs on all 2^n inputs: a proof by exhaustion over the truth table."""
    return all(lhs(*v) == rhs(*v) for v in product((0, 1), repeat=n))

NOT = lambda x: 1 - x
print(is_identity(lambda x, y, z: x | (y & z), lambda x, y, z: (x | y) & (x | z), 3))  # True   distributive
print(is_identity(lambda x, y: x | (NOT(x) & y), lambda x, y: x | y, 2))              # True   redundant literal
print(is_identity(lambda x, y, z: (x & y) | (NOT(x) & z) | (y & z),
                  lambda x, y, z: (x & y) | (NOT(x) & z), 3))                          # True   consensus
print(is_identity(lambda x, y: x | y, lambda x, y: x ^ y, 2))                          # False  OR is not XOR

# The divisors of 30 under lcm/gcd satisfy the same laws
lcm = lambda a, b: a * b // gcd(a, b)
D = [d for d in range(1, 31) if 30 % d == 0]
print(all(lcm(a, 30 // a) == 30 and gcd(a, 30 // a) == 1 for a in D))                  # True   complements
print(all(lcm(a, gcd(b, c)) == gcd(lcm(a, b), lcm(a, c)) for a in D for b in D for c in D))  # True

Analogy. An identity is a refactoring that is guaranteed to preserve behavior. The truth table is the test suite, and it happens to be exhaustive.

Key takeaways

• The Boolean identities are the laws of 1.1 in +, ·, ' notation. They come in pairs.
• Unlike arithmetic: x + x = x, x + 1 = 1, and + distributes over ·.
• Learn the redundant-literal, combining and consensus identities. Combining (xy + xy' = x) is the basis of minimization.
• There is no cancellation law. You cannot "subtract" or "divide" both sides.
• Sets, bit vectors, logic and squarefree divisors all form Boolean algebras, so one proof covers all of them.

Practice

1. (Beginner) Prove x(x' + y) = xy algebraically, naming each law. Then confirm it with is_identity.
2. (Intermediate) Prove that if x + y = x + z and xy = xz, then y = z. Hint: start from y = y + xy (absorption) and substitute.
3. (Interview) Simplify the condition if (a and b) or (not a and c) or (b and c): and justify the step. Hint: consensus.

Duality

Why. Look at the tables in the previous topic: nearly every identity appears twice, once with + and once with ·. Duality explains why and gives you the second identity of each pair without a second proof. It also separates two operations that are easy to confuse, the dual and the complement, a confusion that causes real bugs when people negate a filter by hand.

What. The dual Eᵈ of an expression E is obtained by swapping + with · and 0 with 1. Variables and complements are left unchanged. Parenthesize E fully first, so that the grouping survives the swap.

E	Eᵈ
x + 0	x · 1
x(y + z)	x + yz
x + yz	x(y + z), not xy + z
x + x'y	x(x' + y)
(x + 1)(y + 0)'	x · 0 + (y · 1)'

Duality principle. If E₁ = E₂ is an identity, then E₁ᵈ = E₂ᵈ is also an identity.

Why it holds. The axioms of Boolean algebra come in dual pairs. Take any proof of E₁ = E₂ and replace every step by its dual. Each new step is justified by the dual axiom, so the result is a proof of E₁ᵈ = E₂ᵈ. There is also a direct argument. By the generalized De Morgan law,

Eᵈ(x₁, …, xₙ) = ( E(x₁', …, xₙ') )'

so if E₁ and E₂ agree on every input, they still agree after their inputs and output are complemented.

From x + xy = x (absorption) the principle gives x(x + y) = x. From x + x'y = x + y it gives x(x' + y) = xy. The principle applies only to identities, which hold for every input. x + y = 1 is true for some inputs, but xy = 0 is not "its dual fact".

Dual versus complement.

• The complement E' is 1 exactly where E is 0. By the generalized De Morgan law, you form it by swapping +/· and 0/1 and complementing every literal.
• The dual Eᵈ swaps the operators and constants but leaves the literals alone. It is generally a different function.

E	Dual Eᵈ	Complement E'
x + y'z	x(y' + z)	x'(y + z')
xy + x'z	(x + y)(x' + z)	(x' + y')(x + z')
xy	x + y	x' + y'

Dual of a function. The formula Eᵈ(x) = E(x')' depends only on the function E defines, not on the expression chosen, so every function F has a well-defined dual Fᵈ(x) = F(x')'. A function is self-dual if Fᵈ = F. Examples are x, x' and the majority function xy + yz + xz (its dual, (x + y)(y + z)(x + z), multiplies out to the same thing). AND and OR are duals of each other, and the dual of XOR is XNOR.

Lattice view. In the lattice picture of 2.5, taking the dual turns the Hasse diagram upside down: join and meet trade places, 0 and 1 trade places, and ≤ becomes ≥. For a power set, ∪ ↔ ∩ and ∅ ↔ S.

from itertools import product

# Expression trees: 0, 1, a variable name, ("not", e), ("or", a, b), ("and", a, b)
def evaluate(e, env):
    if isinstance(e, str): return env[e]
    if e in (0, 1):        return e
    op, *args = e
    v = [evaluate(a, env) for a in args]
    return 1 - v[0] if op == "not" else (v[0] | v[1] if op == "or" else v[0] & v[1])

def dual(e):
    if isinstance(e, str): return e                        # variables stay as they are
    if e in (0, 1):        return 1 - e                    # swap the constants
    op, *args = e
    return ({"or": "and", "and": "or", "not": "not"}[op], *map(dual, args))

def complement(e):
    """Generalized De Morgan: the dual, with every variable complemented as well."""
    if isinstance(e, str): return ("not", e)
    if e in (0, 1):        return 1 - e
    op, *args = e
    if op == "not":        return args[0]                  # (E')' = E
    return ({"or": "and", "and": "or"}[op], *map(complement, args))

def table(e, names):
    return tuple(evaluate(e, dict(zip(names, v))) for v in product((0, 1), repeat=len(names)))

E, names = ("or", "x", ("and", ("not", "y"), "z")), "xyz"     # E = x + y'z
print(dual(E))                     # ('and', 'x', ('or', ('not', 'y'), 'z'))          x(y' + z)
print(complement(E))               # ('and', ('not', 'x'), ('or', 'y', ('not', 'z')))  x'(y + z')
print(table(complement(E), names) == tuple(1 - b for b in table(E, names)))   # True
print(table(dual(E), names) == table(complement(E), names))                   # False  dual ≠ complement

# Duality principle: absorption x + xy = x gives x(x + y) = x
lhs, rhs = ("or", "x", ("and", "x", "y")), "x"
print(table(dual(lhs), "xy") == table(dual(rhs), "xy"))                       # True

# Self-duality at the level of functions: F^d(x) = F(x')'
dual_fn = lambda f: (lambda *xs: 1 - f(*(1 - x for x in xs)))
maj = lambda x, y, z: (x & y) | (y & z) | (x & z)
xor = lambda x, y: x ^ y
print(all(dual_fn(maj)(*v) == maj(*v) for v in product((0, 1), repeat=3)))    # True   majority is self-dual
print([dual_fn(xor)(*v) for v in product((0, 1), repeat=2)])                  # [1, 0, 0, 1]  XNOR

Key takeaways

• The dual swaps + ↔ · and 0 ↔ 1 and keeps the literals. Parenthesize before you swap.
• Duality principle: the dual of an identity is an identity, so every law comes with a free partner.
• Dual is not complement. The complement also complements every literal (generalized De Morgan).
• Fᵈ(x) = F(x')'. Self-dual functions such as majority equal their own duals.

Practice

1. (Beginner) Write the duals of x(y + 0), x' · 1 + (y + z) and (x + y)(x + y'). Then write the complement of each.
2. (Intermediate) Show that there are 2^(2^(n−1)) self-dual functions of n variables. Hint: F(x') = F(x)' pairs each input with its bitwise complement, and choosing F on one member of each pair fixes it on the other.
3. (Interview) A teammate "negates" the filter (status = open AND priority = high) OR assignee = me by swapping AND with OR. What did they actually compute, and how do you fix it? Hint: they took the dual. A negation must also negate each comparison (= becomes ≠).

Sum-of-Products Expansion

Why. Specifications usually arrive as a table of desired outputs: "for these inputs, output 1". We need a systematic way to turn such a table into an expression, and from there into a circuit. The method below always works, and it also proves something important: every Boolean function can be written using only +, · and '. It is the DNF construction of 1.1, here with the names and index notation that circuit designers use.

What.

• A literal is a variable or its complement: x or x'.
• A minterm in x₁, …, xₙ is a product y₁y₂⋯yₙ with each yᵢ either xᵢ or xᵢ'. A minterm equals 1 for exactly one input: use xᵢ where the input bit is 1 and xᵢ' where it is 0. The input (x, y, z) = (1, 0, 1) has the minterm xy'z.
• Index notation: mᵢ is the minterm of the row whose bits spell i in binary. For example, xy'z = m₅ because 101₂ = 5.
• The sum-of-products expansion (canonical SOP, or disjunctive normal form) of F is the sum of the minterms of the rows where F = 1. It is written F = Σm(i₁, …, iₖ).

Theorem. Every Boolean function equals the sum of its minterms. Proof. At an input a, the sum is 1 iff one of its minterms is 1 at a. Only mₐ is 1 at a, and mₐ is in the sum iff F(a) = 1. ∎

The expansion is canonical: two expressions define the same function iff they have the same minterm list. This gives a mechanical equality test.

Dual construction. A maxterm Mᵢ is a sum of literals that is 0 at exactly row i, and Mᵢ = mᵢ'. The product-of-sums expansion (CNF) is F = ΠM(rows where F = 0).

Row i	x y z	Minterm mᵢ	Maxterm Mᵢ
0	0 0 0	x'y'z'	x + y + z
1	0 0 1	x'y'z	x + y + z'
2	0 1 0	x'yz'	x + y' + z
3	0 1 1	x'yz	x + y' + z'
4	1 0 0	xy'z'	x' + y + z
5	1 0 1	xy'z	x' + y + z'
6	1 1 0	xyz'	x' + y' + z
7	1 1 1	xyz	x' + y' + z'

Example: majority vote. Three judges x, y, z each vote 0 or 1, and F is the majority. F = 1 on rows 3, 5, 6, 7:

SOP:  F = x'yz + xy'z + xyz' + xyz                         = Σm(3, 5, 6, 7)
POS:  F = (x + y + z)(x + y + z')(x + y' + z)(x' + y + z)  = ΠM(0, 1, 2, 4)

Canonical forms are correct but rarely small. Duplicate xyz twice (idempotent), then combine each copy with one of the other three terms (x'yz + xyz = yz, and so on). The result is F = xy + yz + xz. Section 11.3 does this systematically.

Algebraic method. You can also expand a non-canonical expression directly. Multiply each product term by (v + v') for every variable v it is missing, then distribute. For F = x + y'z over (x, y, z):

x    = x(y + y')(z + z') = xyz + xyz' + xy'z + xy'z'     = m₇ + m₆ + m₅ + m₄
y'z  = (x + x')y'z       = xy'z + x'y'z                  = m₅ + m₁
F    = Σm(1, 4, 5, 6, 7)                                 m₅ appears once: x + x = x

Complements come for free: F' is the sum of the missing minterms, F' = Σm(0, 2, 3), and F = ΠM(0, 2, 3).

	Sum of products Σm	Product of sums ΠM
Built from	Rows where F = 1	Rows where F = 0
Building block	Minterm: product, 1 at one row	Maxterm: sum, 0 at one row
Logic name (1.1)	DNF	CNF
Two-level circuit	AND gates feeding one OR	OR gates feeding one AND
Shorter when	F has few 1s	F has few 0s

from itertools import product

def minterm_indices(f, n):
    """Row numbers i (input bits read as binary) where f is 1."""
    return [i for i, bits in enumerate(product((0, 1), repeat=n)) if f(*bits)]

def sop(f, names):
    """Canonical sum of products: one minterm per row where f is 1."""
    terms = ["".join(v if b else v + "'" for v, b in zip(names, bits))
             for bits in product((0, 1), repeat=len(names)) if f(*bits)]
    return " + ".join(terms) or "0"

def pos(f, names):
    """Canonical product of sums: one maxterm per row where f is 0 (each literal flipped)."""
    clauses = ["(" + " + ".join(v + "'" if b else v for v, b in zip(names, bits)) + ")"
               for bits in product((0, 1), repeat=len(names)) if not f(*bits)]
    return "".join(clauses) or "1"

maj = lambda x, y, z: (x & y) | (y & z) | (x & z)
print(minterm_indices(maj, 3))     # [3, 5, 6, 7]
print(sop(maj, "xyz"))             # x'yz + xy'z + xyz' + xyz
print(pos(maj, "xyz"))             # (x + y + z)(x + y + z')(x + y' + z)(x' + y + z)

F = lambda x, y, z: x | ((1 - y) & z)        # x + y'z
print(minterm_indices(F, 3))       # [1, 4, 5, 6, 7]

Analogy. A minterm is a key that fits exactly one lock, one row of the table. The sum-of-products expansion is a key ring holding one key for every row where the output must be 1.

Key takeaways

• A minterm is 1 at exactly one input. Every function is the sum of the minterms of its 1-rows: F = Σm(…).
• Dually, every function is the product of the maxterms of its 0-rows: F = ΠM(…).
• Canonical forms are unique, so they decide equality, but they can have up to 2ⁿ terms of n literals each.
• To expand algebraically, multiply each term by (v + v') for each missing variable.
• The SOP expansion proves that {+, ·, '} can express every Boolean function.

Practice

1. (Beginner) Find the SOP and POS expansions of the function F(x, y, z) that is 1 exactly when an odd number of its inputs are 1.
2. (Intermediate) Use the algebraic method to find the minterm list of F(x, y, z) = (x + y)z', and check it with minterm_indices. Then write F' as a minterm list without any further work.
3. (Interview) A config validator must accept exactly 37 specific combinations of 10 boolean flags. Write down the obvious expression and estimate its size. How could you shrink it? Hint: the canonical SOP has 37 terms of 10 literals. Look for accepted combinations that differ in a single flag (the combining rule, 11.3). In software, also consider a hash-set lookup.

Functional Completeness

Why. The SOP expansion shows that complement, sum and product are enough to express every function. Can we get by with fewer operations? The answer matters for hardware (a chip built from one kind of gate is cheaper to make), and so does the converse: proving that a restricted system cannot express something. A circuit with no inverters can never compute x'. A query language without negation cannot express "not in".

What. A set of operations is functionally complete if every Boolean function can be expressed using only those operations and the variables. Constants are not available for free. If a set needs them, they must be in the set.

Proving completeness. Express the operations of a set that is already known to be complete.

Set	Why it is complete
{+, ·, '}	Sum-of-products expansion. The constant 0 is xx'
{·, '}	x + y = (x'y')' (De Morgan)
{+, '}	xy = (x' + y')'
{|}, NAND (x | y = (xy)')	x' = x | x, xy = (x | y) | (x | y), x + y = (x | x) | (y | y)
{↓}, NOR (x ↓ y = (x + y)')	x' = x ↓ x, x + y = (x ↓ y) ↓ (x ↓ y), xy = (x ↓ x) ↓ (y ↓ y)
{→, 0}	x' = x → 0, x + y = x' → y
{⊕, ·, 1}	x' = x ⊕ 1. These are polynomials mod 2 (the field GF(2), 12.2)

Proving incompleteness. Find an invariant: a property that every variable has and that every operation in the set preserves. By structural induction (3.3), every expression built from the set has the property. If some function lacks it, the set cannot be complete.

• {+, ·} is incomplete. Every expression built from it is monotone: raising an input from 0 to 1 never lowers the output. x' is not monotone.
• {→} is incomplete. Every expression built from it preserves 1: with all inputs 1, the output is 1, because 1 → 1 = 1. So neither x' nor the constant 0 can be built.
• {⊕, '} is incomplete. Every expression built from it is affine, of the form c₀ ⊕ c₁x₁ ⊕ ⋯ ⊕ cₙxₙ, and xy is not.

Post's theorem (1941). Exactly five such invariants matter. Each one defines a class of functions that is closed under composition:

Class	F belongs to it when	Members	Non-members
T₀ (0-preserving)	F(0, …, 0) = 0	AND, OR, XOR	NOT, NAND
T₁ (1-preserving)	F(1, …, 1) = 1	AND, OR, →	NOT, XOR
S (self-dual)	F(x') = F(x)'	NOT, majority	AND, OR
M (monotone)	x ≤ y componentwise implies F(x) ≤ F(y)	AND, OR, majority	NOT, XOR
L (affine)	F = c₀ ⊕ c₁x₁ ⊕ ⋯ ⊕ cₙxₙ	NOT, XOR, XNOR	AND, OR

A set of operations is functionally complete if and only if, for each of the five classes, it contains at least one operation outside that class.

Operation	T₀	T₁	S	M	L
NOT	no	no	yes	no	yes
AND	yes	yes	no	yes	no
OR	yes	yes	no	yes	no
XOR	yes	no	no	no	yes
XNOR	no	yes	no	no	yes
→	no	yes	no	no	no
NAND	no	no	no	no	no
NOR	no	no	no	no	no
Majority	yes	yes	yes	yes	no
Constant 0	yes	no	no	yes	yes
Constant 1	no	yes	no	yes	yes

To use the table, look for a "no" in every column:

• {AND, NOT}: NOT escapes T₀, T₁ and M, and AND escapes S and L. Complete.
• {XOR, AND}: both are in T₀, so the constant 1 can never be built. Incomplete. Adding the constant 1 makes it complete.
• {→} is stuck in T₁. Adding the constant 0 makes it complete.
• NAND and NOR have "no" in every column, so each is complete on its own. They are the only two-input operations with this property (11.2 builds circuits from them).

from itertools import product

def post_classes(f, k):
    """Which of Post's five classes contain the k-ary Boolean function f?"""
    pts = list(product((0, 1), repeat=k))
    c0 = f(*[0] * k)
    coef = [f(*[int(i == j) for j in range(k)]) ^ c0 for i in range(k)]   # forced if f is affine
    return {
        "T0": c0 == 0,
        "T1": f(*[1] * k) == 1,
        "S":  all(f(*[1 - a for a in p]) == 1 - f(*p) for p in pts),
        "M":  all(f(*a) <= f(*b) for a in pts for b in pts if all(u <= v for u, v in zip(a, b))),
        "L":  all(f(*p) == c0 ^ (sum(c & x for c, x in zip(coef, p)) % 2) for p in pts),
    }

def is_complete(ops):
    """Post's criterion: for every class, some operation lies outside it."""
    classes = [post_classes(f, k) for f, k in ops]
    return all(any(not c[name] for c in classes) for name in ("T0", "T1", "S", "M", "L"))

AND, OR = (lambda x, y: x & y, 2), (lambda x, y: x | y, 2)
NOT, XOR = (lambda x: 1 - x, 1), (lambda x, y: x ^ y, 2)
NAND, IMP = (lambda x, y: 1 - (x & y), 2), (lambda x, y: (1 - x) | y, 2)
ZERO, ONE = (lambda: 0, 0), (lambda: 1, 0)                  # constants are 0-ary operations

print(is_complete([AND, OR]))          # False  monotone: x' is out of reach
print(is_complete([AND, NOT]))         # True
print(is_complete([NAND]))             # True   NAND lies outside all five classes
print(is_complete([XOR, AND]))         # False  both preserve 0
print(is_complete([XOR, AND, ONE]))    # True   arithmetic mod 2
print(is_complete([IMP]))              # False  preserves 1
print(is_complete([IMP, ZERO]))        # True   x' = x → 0

Analogy. Each of Post's classes is a closed room: compose functions inside the room and you never leave it. A set of operations can reach every function only if it holds a key to each of the five rooms.

Key takeaways

• A set of operations is functionally complete if it can express every Boolean function.
• To prove completeness, express a known complete set such as {+, ·, '} or {·, '}.
• To prove incompleteness, find an invariant (monotone, 0-preserving, 1-preserving, self-dual, affine) that the set preserves.
• Post's theorem: a set is complete iff it escapes all five classes. NAND and NOR are each complete alone.

Practice

1. (Beginner) Express x ⊕ y using only · and '.
2. (Intermediate) Prove by structural induction that every expression built from variables using only ⊕ and ' is affine. Conclude that {⊕, '} is not complete, and name a two-variable function it cannot express.
3. (Interview) A rules engine offers only if c then a else b (ITE), applied to variables. Is it functionally complete? What changes if the constants true and false are allowed? Hint: check ITE against T₀ and T₁. Then build NOT and AND from ITE and constants. A 2:1 multiplexer (11.2) computes exactly ITE, and binary decision diagrams are built from it.

<a id="112-logic-circuits"></a>

11.2 Logic Circuits

This subchapter turns Boolean expressions into hardware. It introduces gates, combines them into circuits without memory, builds the adders at the heart of every arithmetic unit, and shows why real chips can be built from a single kind of gate.

Logic Gates

Why. In his 1937 master's thesis, Claude Shannon showed that circuits of relay switches obey Boolean algebra. Every digital computer since then has been built from switches whose two states (low and high voltage) represent 0 and 1. A logic gate is the physical counterpart of a Boolean operation, so Boolean algebra is a design language for hardware.

What. A gate takes one or more input bits and produces an output bit computed by a basic Boolean function. The inverter (NOT gate) has one input and outputs x'. The common two-input gates:

Gate	Expression	Output for xy = 00, 01, 10, 11	Python on 0/1	Output is 1 when
AND	xy	0 0 0 1	x & y	All inputs are 1
OR	x + y	0 1 1 1	x | y	At least one input is 1
NAND	(xy)'	1 1 1 0	1 - (x & y)	Not all inputs are 1
NOR	(x + y)'	1 0 0 0	1 - (x | y)	No input is 1
XOR	x ⊕ y	0 1 1 0	x ^ y	An odd number of inputs are 1
XNOR	(x ⊕ y)'	1 0 0 1	1 - (x ^ y)	An even number of inputs are 1

Standard schematics draw AND as a D shape, OR as a curved shield and NOT as a triangle, and they mark inversion with a small circle (a "bubble") on a pin, so NAND is an AND with a bubble on its output. This chapter draws every gate as a labeled box:

         ┌─────┐                ┌─────┐
  x ─────┤     │         x ─────┤     │                 ┌─────┐
         │ AND ├── xy           │ OR  ├── x + y   x ────┤ NOT ├── x'
  y ─────┤     │         y ─────┤     │                 └─────┘
         └─────┘                └─────┘

Switches. Shannon's observation is easy to see with two switches and a lamp. Switches in series behave like AND, and switches in parallel behave like OR:

  Series (AND): the lamp is lit iff x AND y are closed

  ──[x]──[y]──(lamp)

  Parallel (OR): the lamp is lit iff x OR y is closed

     ┌──[x]──┐
  ───┤       ├──(lamp)
     └──[y]──┘

Gates with more inputs. AND, OR and XOR are associative (11.1), so an n-input version is unambiguous: x₁x₂⋯xₙ, x₁ + ⋯ + xₙ, and the parity x₁ ⊕ ⋯ ⊕ xₙ. NAND and NOR are not associative. An n-input NAND means (x₁x₂⋯xₙ)', which is not a chain of 2-input NANDs:

(1 | 1) | 0 = 0 | 0 = 1        but        1 | (1 | 0) = 1 | 1 = 0

Physical parameters.

Parameter	Meaning
Fan-in	Number of inputs of a gate
Fan-out	Number of gate inputs that one output can drive
Propagation delay	Time for the output to settle after an input changes (picoseconds in modern chips)
Transistor count	In CMOS, NOT takes 2 transistors, 2-input NAND and NOR take 4, and AND (NAND + NOT) takes 6

The transistor counts explain why inverting gates such as NAND and NOR are the natural primitives in silicon (more on this in NAND and NOR Universality).

GATES = {
    "AND":  lambda x, y: x & y,
    "OR":   lambda x, y: x | y,
    "NAND": lambda x, y: 1 - (x & y),
    "NOR":  lambda x, y: 1 - (x | y),
    "XOR":  lambda x, y: x ^ y,
    "XNOR": lambda x, y: 1 - (x ^ y),
}

print("x y " + "".join(f"{name:>6}" for name in GATES))
for x in (0, 1):
    for y in (0, 1):
        print(f"{x} {y} " + "".join(f"{g(x, y):>6}" for g in GATES.values()))
# x y    AND    OR  NAND   NOR   XOR  XNOR
# 0 0      0     0     1     1     0     1
# 0 1      0     1     1     0     1     0
# 1 0      0     1     1     0     1     0
# 1 1      1     1     0     0     0     1

# A CPU's 64-bit `a & b` is 64 AND gates working side by side, one per bit position
a, b = 0b1100, 0b1010
print(f"{a & b:04b} {a | b:04b} {a ^ b:04b}")   # 1000 1110 0110

Key takeaways

• A logic gate computes a basic Boolean function. Wires carry bits, and circuits are Boolean expressions in hardware.
• The basic gates are NOT, AND, OR, NAND, NOR, XOR and XNOR. A bubble on a pin means inversion.
• Series switches compute AND and parallel switches compute OR, which is Shannon's link between circuits and algebra.
• Multi-input AND, OR and XOR are well defined because those operations are associative. NAND and NOR are not associative.

Practice

1. (Beginner) Write the truth table of a 3-input XOR and describe in words when its output is 1.
2. (Intermediate) Which of AND, OR, XOR, NAND, NOR and XNOR are associative? Give a counterexample for each one that is not. (Check XNOR carefully before you answer.)
3. (Interview) Compute the parity of a 64-bit word (1 if it has an odd number of 1 bits) with bit operations, using only O(log n) steps. Hint: XOR is associative and commutative, so fold the word in half repeatedly: x ^= x >> 32, then x ^= x >> 16, and so on. As a circuit, this is a balanced tree of XOR gates of depth 6.

Combinational Circuits

Why. Interesting functions need many gates. A combinational circuit wires gates together so that its outputs depend only on its current inputs: it has no memory. This is the hardware form of a Boolean function. Circuits with memory (flip-flops, registers) are called sequential, and finite-state machines (13.2) model them.

What. A combinational circuit is a network of gates with no feedback loops. Viewed as a directed graph, with gates as vertices and wires as edges, it is acyclic. Each output computes a Boolean function of the inputs. One output can feed several gates (fan-out), so a circuit is a DAG rather than a tree. When it is a tree, it is exactly the expression tree of 9.3, with gates in place of operators.

Cost measure	Definition	Physical meaning
Size	Number of gates	Chip area and power
Depth	Most gates on any path from an input to an output	Delay: the output settles after about depth × gate delay
Fan-in	Most inputs on any gate	Bounded by the technology

Design procedure.

1. State the problem: name the inputs and outputs.
2. Write the truth table.
3. Write the sum-of-products expansion of each output (11.1).
4. Simplify, with identities (11.1) or maps (11.3).
5. Draw the circuit, or write it in a hardware description language.

Example 1: majority voter. Safety-critical systems often run three copies of a sensor or computer and take the majority of their answers (triple modular redundancy), so that one failure is outvoted. From 11.1, the majority is F = xy + yz + xz. Each input fans out to two AND gates; the drawing repeats input names instead of drawing branching wires.

        ┌─────┐
  x ────┤     │
        │ AND ├── xy ──┐
  y ────┤     │        │
        └─────┘        │     ┌─────┐
        ┌─────┐        └─────┤     │
  y ────┤     │              │     │
        │ AND ├── yz ────────┤ OR  ├── F = xy + yz + xz
  z ────┤     │              │     │
        └─────┘        ┌─────┤     │
        ┌─────┐        │     └─────┘
  x ────┤     │        │
        │ AND ├── xz ──┘
  z ────┤     │
        └─────┘

Size 4 (three 2-input ANDs and one 3-input OR), depth 2. The canonical expansion x'yz + xy'z + xyz' + xyz would need three inverters, four 3-input ANDs and a 4-input OR, which shows what simplification is worth.

Example 2: two-way light switch. A stairway light has a switch at the top (x) and one at the bottom (y). Flipping either switch toggles the light, and the light is off when both switches are down.

  x y │ L
  0 0 │ 0
  0 1 │ 1
  1 0 │ 1
  1 1 │ 0

L = x'y + xy' = x ⊕ y, which is a single XOR gate. With a third switch, L = x ⊕ y ⊕ z: each flip changes the parity.

Standard building blocks. Larger designs reuse a few combinational components:

Block	Inputs → outputs	Function	Typical use
Multiplexer (2:1)	a, b, select s → 1	s'a + sb	Choose between two data sources. The hardware if-then-else
Decoder (2-to-4)	2 → 4	Output i is the minterm mᵢ	Select one memory row or device from an address
Encoder (4-to-2)	4 → 2	Inverse of a decoder	Report which line is active, such as an interrupt number
Equality comparator	Two n-bit numbers → 1	(a₁ ⊙ b₁)(a₂ ⊙ b₂)⋯(aₙ ⊙ bₙ), where ⊙ is XNOR	a == b
Adder	Two n-bit numbers → n + 1 bits	Next topic	Arithmetic

Because a decoder's outputs are exactly the minterms, a decoder plus one OR gate of the right outputs realizes any function, which is the sum-of-products expansion in hardware. A read-only memory is built the same way.

# A netlist lists each gate as (output wire, gate type, input wires), in topological order
OPS = {
    "AND": lambda v: int(all(v)),
    "OR":  lambda v: int(any(v)),
    "NOT": lambda v: 1 - v[0],
    "XOR": lambda v: sum(v) % 2,
}

MAJORITY = [
    ("xy", "AND", ("x", "y")),
    ("yz", "AND", ("y", "z")),
    ("xz", "AND", ("x", "z")),
    ("F",  "OR",  ("xy", "yz", "xz")),          # one 3-input OR gate
]

def simulate(netlist, inputs):
    wires = dict(inputs)
    for out, kind, ins in netlist:              # topological order: each gate's inputs are already known
        wires[out] = OPS[kind]([wires[w] for w in ins])
    return wires

def depth(netlist, input_names):
    level = dict.fromkeys(input_names, 0)
    for out, _, ins in netlist:
        level[out] = 1 + max(level[w] for w in ins)   # longest path in a DAG
    return max(level.values())

ok = all(simulate(MAJORITY, {"x": x, "y": y, "z": z})["F"] == int(x + y + z >= 2)
         for x in (0, 1) for y in (0, 1) for z in (0, 1))
print(ok, len(MAJORITY), depth(MAJORITY, "xyz"))    # True 4 2

Key takeaways

• A combinational circuit is an acyclic network of gates. Its outputs depend only on its current inputs.
• Size measures area and power, and depth measures delay. The two often trade off against each other.
• Design flow: specification, truth table, sum of products, simplification, circuit.
• Multiplexers, decoders, encoders, comparators and adders are the standard reusable blocks. A decoder plus an OR gate realizes any function.

Practice

1. (Beginner) Draw a circuit for (x + y)z' and give its size and depth.
2. (Intermediate) Design a 2-to-4 decoder: write each output as a minterm and draw it. Then show how the decoder plus one OR gate realizes x ⊕ y.
3. (Interview) Why must a combinational circuit be acyclic? Consider two NOR gates whose outputs are fed back into each other's inputs (an SR latch). What new behavior appears? Hint: with both external inputs at 0, the loop has two stable states, so the circuit remembers which input was last set to 1. That is memory, and it makes the circuit sequential.

Adders

Why. Adding binary numbers is a Boolean function: each output bit is determined by the input bits. Every processor's arithmetic logic unit is built on adders, and they are the classic example of building a large circuit from small identical cells. Their design also shows the trade-off between size and depth.

Half adder. A half adder adds two bits x and y. It produces a sum bit s and a carry bit c, so the two-bit number cs is x + y in ordinary arithmetic.

  x y │ c s
  0 0 │ 0 0
  0 1 │ 0 1
  1 0 │ 0 1
  1 1 │ 1 0          1 + 1 = 10 in binary

So s = x'y + xy' = x ⊕ y and c = xy:

          ┌─────┐
  x ───┬──┤     │
       │  │ XOR ├── s = x ⊕ y
  y ──┬┼──┤     │
      ││  └─────┘
      ││  ┌─────┐
      │└──┤     │
      │   │ AND ├── c = xy
      └───┤     │
          └─────┘

Full adder. To add multi-bit numbers, each column must also accept a carry from the column to its right. A full adder adds x, y and a carry-in cᵢₙ:

  x y cᵢₙ │ cₒᵤₜ s
  0 0  0  │  0   0
  0 0  1  │  0   1
  0 1  0  │  0   1
  0 1  1  │  1   0
  1 0  0  │  0   1
  1 0  1  │  1   0
  1 1  0  │  1   0
  1 1  1  │  1   1

s    = Σm(1, 2, 4, 7) = x ⊕ y ⊕ cᵢₙ                      parity of the three inputs
cₒᵤₜ = Σm(3, 5, 6, 7) = xy + xcᵢₙ + ycᵢₙ = xy + cᵢₙ(x ⊕ y)  majority of the three inputs

A full adder is two half adders and an OR gate. The first adds x and y, and the second adds the carry-in to that partial sum. A carry out occurs if either half adder produces one:

           ┌──────┐  x ⊕ y   ┌──────┐
  x ───────┤      ├──────────┤      ├─────────────── s = x ⊕ y ⊕ cᵢₙ
           │  HA  │          │  HA  │
  y ───────┤      ├──┐  cᵢₙ ─┤      ├──┐ cᵢₙ(x ⊕ y)
           └──────┘  │       └──────┘  │   ┌─────┐
                     │ xy              └───┤     │
                     │                     │ OR  ├── cₒᵤₜ
                     └─────────────────────┤     │
                                           └─────┘

(Each HA box outputs its sum on top and its carry below.)

Ripple-carry adder. To add two n-bit numbers, chain n full adders. The carry out of bit i is the carry into bit i + 1, and c₀ = 0:

     x₃ y₃         x₂ y₂         x₁ y₁         x₀ y₀
      │  │          │  │          │  │          │  │
    ┌─┴──┴─┐      ┌─┴──┴─┐      ┌─┴──┴─┐      ┌─┴──┴─┐
 ┌──┤  FA  │◄─c₃──┤  FA  │◄─c₂──┤  FA  │◄─c₁──┤  FA  │◄── c₀ = 0
 │  └──┬───┘      └──┬───┘      └──┬───┘      └──┬───┘
 │     │             │             │             │
 c₄    s₃            s₂            s₁            s₀

Trace of 0110 + 0111 (6 + 7):

  bit i            3  2  1  0
  carry in  cᵢ     1  1  0  0        c₀ = 0
  x                0  1  1  0
  y                0  1  1  1
  sum       sᵢ     1  1  0  1        = 13
  carry out cᵢ₊₁   0  1  1  0        c₄ = 0: no overflow

Cost. Each full adder has 5 gates (2 XOR, 2 AND, 1 OR), so the size is 5n, which is O(n). But bit n − 1 cannot settle until the carry has passed through every stage, about 2 gate levels each, so the depth is about 2n, also O(n). For 64-bit numbers that is roughly 128 gate delays, too slow for a modern clock cycle.

Carry-lookahead. For each bit, define

gᵢ = xᵢyᵢ        generate:  this bit produces a carry whatever comes in
pᵢ = xᵢ ⊕ yᵢ     propagate: this bit passes an incoming carry along
cᵢ₊₁ = gᵢ + pᵢcᵢ

Unrolling the recurrence writes every carry directly in terms of the gs, the ps and c₀, with no rippling:

c₁ = g₀ + p₀c₀
c₂ = g₁ + p₁g₀ + p₁p₀c₀
c₃ = g₂ + p₂g₁ + p₂p₁g₀ + p₂p₁p₀c₀

Each carry is now a two-level sum of products, but the terms grow with i. Practical adders instead combine (g, p) pairs with the associative operator (g, p) ∘ (g', p') = (g + pg', pp') arranged as a balanced tree. These are the parallel-prefix adders, such as Kogge–Stone and Brent–Kung.

Adder	Size	Depth	64-bit depth, roughly
Ripple-carry	O(n)	O(n)	about 128 gate levels
Parallel-prefix lookahead	O(n log n) (Kogge–Stone)	O(log n)	under 20 gate levels

Subtraction. In two's complement, x − y = x + y' + 1: complement every bit of y and set c₀ = 1. Since y ⊕ 1 = y' and y ⊕ 0 = y, XOR gates controlled by a single sub line, with c₀ = sub, turn one adder into an adder–subtractor. For signed numbers, overflow occurred iff cₙ ⊕ cₙ₋₁ = 1.

def half_adder(x, y):
    return x ^ y, x & y                         # (sum, carry)

def full_adder(x, y, c):
    s1, c1 = half_adder(x, y)
    s, c2 = half_adder(s1, c)
    return s, c1 | c2                           # c1 and c2 are never both 1

def ripple_add(xs, ys, c=0):
    """Add two little-endian bit lists (index 0 is the least significant bit)."""
    out = []
    for x, y in zip(xs, ys):
        s, c = full_adder(x, y, c)              # the carry ripples into the next stage
        out.append(s)
    return out + [c]                            # the final carry is one extra high-order bit

bits  = lambda n, width: [(n >> i) & 1 for i in range(width)]
value = lambda bs: sum(b << i for i, b in enumerate(bs))

print(value(ripple_add(bits(6, 4), bits(7, 4))))            # 13
print(all(value(ripple_add(bits(a, 4), bits(b, 4))) == a + b
          for a in range(16) for b in range(16)))           # True  all 256 cases

def subtract(xs, ys):
    """x − y = x + y' + 1: complement y with XOR, feed in carry 1, keep n bits."""
    return ripple_add(xs, [y ^ 1 for y in ys], c=1)[:-1]

print(value(subtract(bits(13, 4), bits(6, 4))))             # 7
print(value(subtract(bits(3, 4), bits(5, 4))))              # 14  (-2 in 4-bit two's complement)

In a hardware description language, the full adder is two lines:

module full_adder(input x, y, cin, output s, cout);
  assign s    = x ^ y ^ cin;                    // parity of the three inputs
  assign cout = (x & y) | (cin & (x ^ y));      // generate, or propagate the incoming carry
endmodule

Analogy. A ripple-carry adder works like column addition on paper, right to left, carrying one digit at a time. Carry-lookahead works like a clerk who glances over all the columns at once to see where carries will be generated and how far they will travel.

Key takeaways

• Half adder: s = x ⊕ y, c = xy. Full adder: s = x ⊕ y ⊕ cᵢₙ, and cₒᵤₜ is the majority of x, y, cᵢₙ.
• A ripple-carry adder chains n full adders. It has O(n) size and O(n) delay.
• Carry-lookahead uses generate and propagate signals and a prefix tree to reach O(log n) delay, at the cost of more gates.
• Subtraction reuses the adder: x − y = x + y' + 1 (two's complement).

Practice

1. (Beginner) Trace the 4-bit ripple-carry adder on 1011 + 0110, listing every carry. What does the final carry tell you?
2. (Intermediate) Prove algebraically that xy + xc + yc = xy + c(x ⊕ y). Then explain why the OR gate in the two-half-adder construction could be replaced by an XOR gate.
3. (Interview) Add two integers without using + or −. Hint: x ^ y adds without carries and (x & y) << 1 gives the carries. Repeat until the carry is 0. In Python, mask to a fixed width (for example 32 bits) or the loop never ends for negative numbers.

NAND and NOR Universality

Why. 11.1 proved algebraically that NAND alone is functionally complete. In hardware this has a practical consequence: an entire processor can be built from one kind of gate. Manufacturing, testing and timing analysis are simpler when there is one cell type, and NAND and NOR are the cheapest gates in CMOS (4 transistors each, against 6 for AND or OR). The Apollo Guidance Computer that flew to the Moon used about 5,600 identical 3-input NOR gates. The Nand2Tetris course builds a working computer from NAND gates.

What. A gate is universal if every combinational circuit can be built from copies of it alone. NAND and NOR are the only universal 2-input gates, because they are the only 2-input functions outside all five of Post's classes (11.1). Write x | y = (xy)' for NAND and x ↓ y = (x + y)' for NOR.

Function	From NAND	Gates	From NOR	Gates
x'	x | x	1	x ↓ x	1
xy	(x | y) | (x | y)	2	(x ↓ x) ↓ (y ↓ y)	3
x + y	(x | x) | (y | y)	3	(x ↓ y) ↓ (x ↓ y)	2
x ⊕ y	t = x | y, then (x | t) | (y | t)	4	t = x ↓ y, u = (x ↓ t) ↓ (y ↓ t), then u ↓ u	5

The gate counts assume that a gate's output can be reused (fan-out). In (x | y) | (x | y) the inner gate is built once and feeds both inputs of the second gate.

x | x             = (xx)'       = x'           Idempotent
(x | y) | (x | y) = ((xy)')'    = xy           since z | z = z'
(x | x) | (y | y) = (x'y')'     = x + y        De Morgan

Two-level conversion: AND–OR to NAND–NAND. Any sum of products converts directly. For F = xy + zw:

F = ((xy + zw)')'          Double complement
  = ((xy)'(zw)')'          De Morgan on the inner complement
  = (x | y) | (z | w)      Definition of NAND

So in an AND–OR circuit you can replace every gate with a NAND and keep the same wiring, size and depth:

     AND–OR (sum of products)                  NAND–NAND (same function)

        ┌─────┐                                   ┌──────┐
  x ────┤ AND ├── xy ──┐                    x ────┤ NAND ├── (xy)' ──┐
  y ────┤     │        │   ┌────┐           y ────┤      │           │   ┌──────┐
        └─────┘        └───┤ OR ├── F             └──────┘           └───┤ NAND ├── F
        ┌─────┐        ┌───┤    │                 ┌──────┐           ┌───┤      │
  z ────┤ AND ├── zw ──┘   └────┘           z ────┤ NAND ├── (zw)' ──┘   └──────┘
  w ────┤     │                             w ────┤      │
        └─────┘                                   └──────┘

The reason is bubble pushing. By De Morgan, an OR gate is an AND gate with bubbles on all its inputs and on its output: x + y = (x'y')'. Its input bubbles cancel the bubbles on the NAND outputs feeding it. Complemented literals such as x' cost one extra NAND each (x | x), unless the complement is already available. Dually, a product of sums (OR–AND) converts to NOR–NOR.

Example. The majority function xy + yz + xz becomes ((x | y)(y | z)(x | z))': three 2-input NANDs feeding one 3-input NAND. That is 4 gates, the same as the AND–OR version.

from itertools import product

def nand(*xs):
    return 1 - all(xs)                          # n-input NAND: 0 only when every input is 1

def NOT(x):    return nand(x, x)
def AND(x, y): t = nand(x, y); return nand(t, t)                  # 2 gates: t fans out
def OR(x, y):  return nand(nand(x, x), nand(y, y))                # 3 gates: De Morgan
def XOR(x, y): t = nand(x, y); return nand(nand(x, t), nand(y, t))  # 4 gates

for x, y in product((0, 1), repeat=2):
    assert (NOT(x), AND(x, y), OR(x, y), XOR(x, y)) == (1 - x, x & y, x | y, x ^ y)

def literals(term):
    """"xy'z" -> [("x", 1), ("y", 0), ("z", 1)], where 0 marks a complemented variable."""
    out = []
    for ch in term:
        if ch == "'": out[-1] = (out[-1][0], 0)
        else:         out.append((ch, 1))
    return out

def nand_nand(terms, env):
    """Evaluate a sum of products as a NAND–NAND circuit. Complemented literals use an inverter NAND."""
    first_level = [nand(*(env[v] if positive else NOT(env[v]) for v, positive in literals(t)))
                   for t in terms]
    return nand(*first_level)

print(all(nand_nand(["xy", "yz", "xz"], dict(x=x, y=y, z=z)) == int(x + y + z >= 2)
          for x, y, z in product((0, 1), repeat=3)))              # True  majority
print(all(nand_nand(["s'a", "sb"], dict(s=s, a=a, b=b)) == (b if s else a)
          for s, a, b in product((0, 1), repeat=3)))              # True  2:1 multiplexer

Key takeaways

• NAND and NOR are each universal: any circuit can be built from copies of either gate alone.
• NOT, AND, OR and XOR take 1, 2, 3 and 4 NAND gates, and 1, 3, 2 and 5 NOR gates.
• An AND–OR circuit (sum of products) becomes NAND–NAND by replacing every gate. OR–AND (product of sums) becomes NOR–NOR.
• Single-gate design is what fabrication favors, because NAND and NOR are the cheapest CMOS gates.

Practice

1. (Beginner) Build x → y = x' + y from NAND gates using as few gates as possible, and verify it with a truth table.
2. (Intermediate) Write F = (x + y)(x' + z) as a NOR–NOR circuit. Then build the same F from NANDs only, and compare gate counts.
3. (Interview) Using only 2-input NAND gates, build a 2:1 multiplexer (output a when s = 0, b when s = 1) with four gates. Hint: write it as s'a + sb and convert to NAND–NAND. The one inverter you need is s | s.

<a id="113-circuit-minimization"></a>

11.3 Circuit Minimization

The canonical sum of products from 11.1 is always correct but usually far from minimal. This subchapter finds equivalent sums of products with as few terms and literals as possible, first by eye with Karnaugh maps and then by algorithm with the Quine–McCluskey method.

Karnaugh Maps

Why. The engine of minimization is the combining rule Pa + Pa' = P: two product terms that differ only in one variable merge, and that variable disappears. The hard part is finding such pairs. In a truth table they can be far apart (rows 0 and 4 differ only in x), and trying identities by hand turns into guesswork. A Karnaugh map (Maurice Karnaugh, 1953) arranges the truth table so that every such pair sits side by side. Simplifying then becomes drawing rectangles.

Vocabulary. The goal is a minimal sum of products: as few product terms as possible and, among those, as few literals as possible. In a two-level AND–OR circuit, terms are AND gates and literals are gate inputs.

• An implicant of F is a product term P such that F = 1 whenever P = 1.
• A prime implicant is an implicant that stops being one if any literal is removed. It is a group that cannot be enlarged.
• An essential prime implicant is a prime implicant that covers some 1 of F that no other prime implicant covers. It must appear in every minimal sum.

Every minimal sum of products uses only prime implicants. If a term were not prime, removing a literal from it would give a smaller correct sum.

What. A K-map has one cell per minterm. Rows and columns are labeled in Gray code order (00, 01, 11, 10), so that neighboring cells differ in exactly one variable. The edges wrap around: the leftmost column is adjacent to the rightmost, and the top row to the bottom. Topologically the map is a torus. Each cell below shows its minterm index:

  3 variables (rows x, columns yz)

             yz
          00    01    11    10
  x  0 │  m0 │  m1 │  m3 │  m2 │
     1 │  m4 │  m5 │  m7 │  m6 │


  4 variables (rows wx, columns yz)

              yz
           00    01    11    10
  wx  00 │  m0 │  m1 │  m3 │  m2 │
      01 │  m4 │  m5 │  m7 │  m6 │
      11 │ m12 │ m13 │ m15 │ m14 │
      10 │  m8 │  m9 │ m11 │ m10 │

Grouping rules.

1. A group is a rectangle of 1-cells, possibly wrapping around an edge, whose size is a power of 2 (1, 2, 4, 8, …).
2. A group of 2ᵏ cells is a product term with n − k literals. Variables that change inside the group drop out. A variable that stays constant appears as v if it is 1 and as v' if it is 0.
3. Make every group as large as possible (this gives prime implicants), and use as few groups as possible. Groups may overlap, since x + x = x.

Procedure.

1. Write a 1 in each cell of the on-set.
2. Find the prime implicants: the maximal groups.
3. Take the essential ones. A 1-cell that lies in exactly one maximal group forces that group.
4. Cover any remaining 1s with as few additional prime implicants as possible.
5. Read off one product term per group and add them.

Example 1: majority, Σm(3, 5, 6, 7).

             yz
          00    01    11    10
  x  0 │   0 │   0 │   1 │   0 │
     1 │   0 │   1 │   1 │   1 │

• {m3, m7} (column yz = 11): x changes and y = z = 1, so the term is yz.
• {m5, m7} (row 1, columns 01 and 11): y changes, so the term is xz.
• {m7, m6} (row 1, columns 11 and 10): z changes, so the term is xy.

All three groups are essential (m3, m5 and m6 each lie in only one), so F = xy + yz + xz: 3 terms with 6 literals, against 4 terms with 12 literals in the canonical form.

Example 2: wraparound, F(w, x, y, z) = Σm(0, 2, 5, 7, 8, 10, 13, 15).

              yz
           00    01    11    10
  wx  00 │   1 │   0 │   0 │   1 │
      01 │   0 │   1 │   1 │   0 │
      11 │   0 │   1 │   1 │   0 │
      10 │   1 │   0 │   0 │   1 │

• The four corners {m0, m2, m8, m10} form one group, because the map wraps in both directions. In it x = 0 and z = 0, so the term is x'z'.
• The center square {m5, m7, m13, m15} has x = 1 and z = 1, so the term is xz.

So F = xz + x'z' = (x ⊕ z)'. Eight terms of four literals shrink to two terms of two literals, and w and y turn out to be irrelevant.

Product of sums from a map. Group the 0s instead. That gives a minimal sum of products for F', and De Morgan turns it into a product of sums for F. For the majority function, the 0s at m0, m1, m2, m4 group into x'y' + x'z' + y'z', so F = (x + y)(x + z)(y + z).

Limitations. Five- and six-variable maps exist (two or four 4-variable maps stacked, with adjacency between the layers), but beyond that the visual method breaks down. Minimal forms are not always unique, and a careless choice in step 4 can miss the minimum. K-maps also optimize only two-level circuits: a factored form such as x(y + z) can be cheaper than any sum of products. Larger problems use the Quine–McCluskey method or heuristic tools.

from itertools import product

GRAY = [0b00, 0b01, 0b11, 0b10]

def kmap4(on, dc=()):
    """Print a 4-variable K-map: rows wx and columns yz, both in Gray-code order."""
    print("wx\\yz  00 01 11 10")
    for r in GRAY:
        cells = ["1" if (m := (r << 2) | c) in on else "X" if m in dc else "0" for c in GRAY]
        print(f"  {r:02b}   " + "  ".join(cells))

ON = {0, 2, 5, 7, 8, 10, 13, 15}
kmap4(ON)
# wx\yz  00 01 11 10
#   00   1  0  0  1
#   01   0  1  1  0
#   11   0  1  1  0
#   10   1  0  0  1

spec    = lambda w, x, y, z: int(8 * w + 4 * x + 2 * y + z in ON)
minimal = lambda w, x, y, z: (x & z) | ((1 - x) & (1 - z))       # xz + x'z'
print(all(spec(*v) == minimal(*v) for v in product((0, 1), repeat=4)))   # True

Key takeaways

• A K-map places minterms that differ in one variable next to each other, using Gray-code order and wraparound edges.
• A rectangular group of 2ᵏ ones is a product term with k fewer literals. The variables that change inside the group drop out.
• Take the essential prime implicants first, then cover the remaining 1s with as few primes as possible.
• Grouping the 0s gives a minimal product of sums.
• K-maps are practical up to about 4–6 variables and optimize two-level circuits only.

Practice

1. (Beginner) Use 3-variable maps to minimize Σm(1, 3, 5, 7) and Σm(0, 2, 4, 6). Describe each result in words.
2. (Intermediate) Minimize F(w, x, y, z) = Σm(0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14). Then find a minimal product of sums by grouping the 0s. Hint: one group has eight cells.
3. (Interview) Why do K-map axes run 00, 01, 11, 10 instead of 00, 01, 10, 11? What would break with binary order? Hint: which neighboring cells would then differ in two bits, and what does the combining rule need?

Don't-Care Conditions

Why. Specifications often leave some outputs open. Certain input combinations can never occur: a BCD digit is 4 bits but only uses the codes 0000–1001, and two mutually exclusive sensors never both fire. For other inputs, nobody reads the output. Leaving those outputs unspecified gives the minimizer freedom, which allows larger groups and therefore smaller circuits.

What. A don't-care is an input combination whose output may be either 0 or 1. Mark it X (or d) in the truth table and the map, and write F = Σm(…) + d(…). The specification is now an incompletely specified function with an on-set (must be 1), an off-set (must be 0) and a don't-care set. Any function that agrees with the specification on the on-set and the off-set is a correct implementation.

When grouping on a map:

• Treat an X as 1 when it lets a group grow.
• Treat it as 0 otherwise. Don't-cares never need to be covered.
• Never add a group made only of Xs. It adds a term and covers nothing required.

Example: BCD "round up" detector. The input wxyz is a BCD digit 0–9, and the output is 1 iff the digit is at least 5. Codes 10–15 never occur.

F = Σm(5, 6, 7, 8, 9) + d(10, 11, 12, 13, 14, 15)

              yz
           00    01    11    10
  wx  00 │   0 │   0 │   0 │   0 │
      01 │   0 │   1 │   1 │   1 │
      11 │   X │   X │   X │   X │
      10 │   1 │   1 │   X │   X │

	Don't-cares treated as 0	Don't-cares used
Groups	{m8, m9}, {m5, m7}, {m6, m7}	Rows 11 and 10 (8 cells); {m5, m7, m13, m15}; {m6, m7, m14, m15}
Expression	wx'y' + w'xz + w'xy	w + xz + xy
Cost	3 terms, 9 literals	3 terms, 5 literals

The choice made for each don't-care can be read off the result. With F = w + xz + xy, every code from 10 to 15 has w = 1, so the circuit outputs 1 for all of them.

Caution. "Never occurs" is a promise, not a fact of physics. If a fault, a glitch at power-up or an uninitialized register produces 1100, the circuit outputs whatever the minimization happened to choose. In safety-critical designs, either check the input invariant explicitly or assign the unused codes a safe output on purpose, and accept a slightly larger circuit. Compilers make the same trade with undefined behavior: they assume it never happens and optimize on that assumption, so code that relies on it can behave arbitrarily.

from itertools import product

ON, DC = {5, 6, 7, 8, 9}, set(range(10, 16))
F = lambda w, x, y, z: w | (x & z) | (x & y)            # w + xz + xy

for v in product((0, 1), repeat=4):
    m = int("".join(map(str, v)), 2)                    # the input bits read as a binary number
    if m in DC:
        print(f"code {m}: circuit outputs {F(*v)}")     # whatever minimization chose
    else:
        assert F(*v) == (m in ON)                       # must match the spec on every valid digit
# code 10: circuit outputs 1
# ...
# code 15: circuit outputs 1

Key takeaways

• A don't-care is an input whose output does not matter. Mark it X and write F = Σm(…) + d(…).
• Use an X as 1 only when it enlarges a group. It never has to be covered.
• Don't-cares often cut literal counts sharply, as in BCD decoders and seven-segment displays.
• The finished circuit commits to a specific output for every don't-care. Make sure the "impossible" inputs really cannot occur.

Practice

1. (Beginner) A BCD prime detector outputs 1 for the digits 2, 3, 5 and 7. Minimize it with and without the don't-cares 10–15 and compare literal counts.
2. (Intermediate) Segment a (the top bar) of a seven-segment display is lit for the digits 0, 2, 3, 5, 6, 7, 8 and 9. Write F = Σm(…) + d(10, …, 15) and minimize it with a 4-variable map. Hint: four groups suffice, one of them made of the four corners.
3. (Interview) The spec says the input is a BCD digit. QA feeds in 1100 and files a bug: "output is 1, expected 0". Is it a bug? What would you do? Hint: the spec's don't-care set, who owns the input contract, and the cost of defensive decoding.

Quine–McCluskey Method

Why. Karnaugh maps depend on human pattern recognition and stop working at about six variables. The Quine–McCluskey method (Quine 1952, McCluskey 1956) performs the same combining systematically on binary strings. It is an algorithm, so a program can run it on any number of variables. The logic-synthesis tools that design today's chips descend from it.

What. Represent each term as a string over {0, 1, -}. Position i holds 1 for xᵢ, 0 for xᵢ', and - if xᵢ is absent. For variables wxyz, the string 0-01 is w'y'z. The method has two phases.

Phase 1: find all prime implicants.

1. Write each minterm and each don't-care as an n-bit string. Group the strings by their number of 1s.
2. Compare every term in group k with every term in group k + 1. If two terms have dashes in the same positions and differ in exactly one other position, combine them, putting a - in that position, and check off both. Only neighboring groups need comparing, because strings that differ in one bit have 1-counts that differ by one.
3. Repeat on the new list until nothing combines. The terms that were never checked off are the prime implicants.

Phase 2: choose a cover.

4. Build the prime implicant chart: one row per prime, one column per minterm. Don't-cares get no column, since they need not be covered.
5. A column with a single mark identifies an essential prime. Take it, and delete every column it covers.
6. Cover the remaining columns with as few primes as possible, by inspection, by dominance rules, or exactly with Petrick's method. In general this step is the set cover problem, which is NP-hard (10.3).

Worked example. F(w, x, y, z) = Σm(0, 1, 2, 5, 6, 7, 8, 9, 10, 14).

Step 1, grouped by the number of 1s (✓ = combined in the next step):

  ones  minterm  wxyz
  0     0        0000  ✓
  1     1        0001  ✓
        2        0010  ✓
        8        1000  ✓
  2     5        0101  ✓
        6        0110  ✓
        9        1001  ✓
        10       1010  ✓
  3     7        0111  ✓
        14       1110  ✓

Step 2, pairs:

  pair    wxyz
  0,1     000-  ✓
  0,2     00-0  ✓
  0,8     -000  ✓
  1,5     0-01        prime: nothing to combine with
  1,9     -001  ✓
  2,6     0-10  ✓
  2,10    -010  ✓
  8,9     100-  ✓
  8,10    10-0  ✓
  5,7     01-1        prime
  6,7     011-        prime
  6,14    -110  ✓
  10,14   1-10  ✓

Step 3, quads (each one arises from two different pairings, for example 0,1 + 8,9 and 0,8 + 1,9, and is listed once):

  quad         wxyz
  0,1,8,9      -00-        prime
  0,2,8,10     -0-0        prime
  2,6,10,14    --10        prime

No two quads combine, so phase 1 ends with six prime implicants. The prime implicant chart:

                    0   1   2   5   6   7   8   9  10  14
  x'y'    -00-      X   X                   X   X
  x'z'    -0-0      X       X               X       X
  yz'     --10              X       X               X   X
  w'y'z   0-01          X       X
  w'xz    01-1                  X       X
  w'xy    011-                      X   X

• Column 9 has a single mark, so x'y' is essential. Column 14 has a single mark, so yz' is essential.
• Together they cover 0, 1, 2, 6, 8, 9, 10 and 14. Only 5 and 7 remain.
• w'xz covers both remaining columns with one term. Any other choice needs two terms (w'y'z + w'xy).

F = x'y' + yz' + w'xz          3 terms, 7 literals (the canonical form has 10 terms, 40 literals)

from itertools import combinations

def combine(a, b):
    """Merge implicants like '01-1' and '0111' if they differ in exactly one non-dash position."""
    diff = [i for i, (p, q) in enumerate(zip(a, b)) if p != q]
    if len(diff) == 1 and "-" not in (a[diff[0]], b[diff[0]]):
        i = diff[0]
        return a[:i] + "-" + a[i + 1:]
    return None

def prime_implicants(n, minterms, dont_cares=()):
    terms = {format(m, f"0{n}b") for m in (*minterms, *dont_cares)}
    primes = set()
    while terms:
        merged, used = set(), set()
        for a, b in combinations(sorted(terms), 2):    # all pairs: simpler than comparing only neighboring groups
            if c := combine(a, b):
                merged.add(c)
                used.update((a, b))
        primes |= terms - used                         # terms nothing absorbed are prime
        terms = merged
    return primes

def covers(implicant, m, n):
    return all(p in ("-", b) for p, b in zip(implicant, format(m, f"0{n}b")))

def to_expr(implicant, names):
    return "".join(v + ("" if b == "1" else "'") for v, b in zip(names, implicant) if b != "-") or "1"

def minimize(names, minterms, dont_cares=()):
    n = len(names)
    primes = prime_implicants(n, minterms, dont_cares)
    chart = {m: [p for p in primes if covers(p, m, n)] for m in minterms}   # no columns for don't-cares
    chosen = {ps[0] for ps in chart.values() if len(ps) == 1}               # essential prime implicants
    left = [m for m in minterms if not any(covers(p, m, n) for p in chosen)]
    while left:                        # greedy: take the prime covering the most remaining minterms
        best = max(sorted(primes - chosen), key=lambda p: sum(covers(p, m, n) for m in left))
        chosen.add(best)
        left = [m for m in left if not covers(best, m, n)]
    return sorted(to_expr(p, names) for p in chosen)

print(minimize("wxyz", [0, 1, 2, 5, 6, 7, 8, 9, 10, 14]))       # ["w'xz", "x'y'", "yz'"]
print(minimize("wxyz", [5, 6, 7, 8, 9], range(10, 16)))         # ['w', 'xy', 'xz']  BCD example
print(minimize("xyz", [0, 1, 2, 5, 6, 7]))                      # ["x'z'", 'xz', "y'z", "yz'"]  4 terms, but 3 suffice

The last line shows the limit of the greedy cover. Σm(0, 1, 2, 5, 6, 7) has six prime implicants and none is essential (a cyclic chart). Every prime covers exactly two minterms, so greedy picks by tie-breaking and ends with four terms, although three are enough. Petrick's method finds the true minimum: write "every column is covered" as a product of sums over the primes, multiply it out, and choose the smallest product.

	Karnaugh map	Quine–McCluskey
Performed by	A person, visually	An algorithm
Practical size	Up to 4–6 variables	Dozens of variables. Exponential in the worst case
Finding prime implicants	By eye, error-prone	Systematic, guaranteed complete
Choosing the cover	By eye	Chart: essentials, then exact (Petrick) or heuristic
Don't-cares	X cells	Used in combining, excluded from the chart

Complexity. A function of n variables can have on the order of 3ⁿ/n prime implicants, and choosing a minimum cover is NP-hard. Exact two-level minimization is therefore infeasible for large functions. Industrial tools use heuristics such as Espresso (Berkeley, 1980s), which iteratively expands, reduces and makes irredundant a cover without listing every prime. Modern synthesis also optimizes multi-level circuits.

Key takeaways

• Quine–McCluskey is the combining rule Pa + Pa' = P applied systematically to binary strings with - for eliminated variables.
• Phase 1 repeatedly merges terms that differ in one bit. The terms never merged are the prime implicants.
• Phase 2 builds a chart, takes the essential primes, and covers the rest. That last step is set cover, which is NP-hard in general.
• Don't-cares take part in combining but get no column in the chart.
• Greedy covering is fast but not always minimal. Petrick's method is exact but exponential.

Practice

1. (Beginner) Run phase 1 by hand on F(w, x, y, z) = Σm(0, 1, 3, 7, 8, 9, 11, 15) and list the prime implicants. Which are essential?
2. (Intermediate) For F(x, y, z) = Σm(0, 1, 2, 5, 6, 7), build the prime implicant chart and use Petrick's method to find both minimal covers. Then change minimize so that it falls back to an exact search over subsets of primes when no essential prime exists.
3. (Interview) Phase 2 of Quine–McCluskey is the set cover problem. What does that imply for exact minimization of a 40-input function, and what would you do in practice? Hint: NP-hardness (10.3) and the possible number of primes. Consider heuristics such as Espresso, and the ln n approximation guarantee of greedy set cover.

<a id="12-algebraic-structures"></a>