From Boolean Algebra to Logic

Lesson 1 placed the design loop's "equations" stage between a written specification and a line of Verilog. This lesson fills that stage: the Boolean algebra that turns a truth table into an expression, and one subtlety — static hazards — that explains why synchronous design, assumed throughout this course and examined directly in lesson 8, is not just a convenience but a way of sidestepping a real class of combinational-logic bug.

Reading time: about 11 minutes.

2.1 The Boolean laws that actually get used

Boolean algebra has many named axioms and theorems, but a short subset accounts for nearly every simplification a designer or synthesis tool performs. Worth naming them precisely, since an interviewer asking "simplify this expression" is really asking whether these are available on demand.

• Idempotence: A + A = A and A · A = A. A term ORed or ANDed with itself contributes nothing new.
• Complement laws: A + A′ = 1 and A · A′ = 0. A variable and its complement always resolve to the identity for that operator.
• Absorption: A + AB = A and A(A + B) = A. The larger term is already guaranteed whenever the smaller one is true, so the larger term is redundant.
• Distributivity: A(B + C) = AB + AC, the algebra that lets a shared factor be pulled out of — or pushed into — a sum of products.
• De Morgan's laws: (A + B)′ = A′B′ and (AB)′ = A′ + B′. The mechanical rule behind converting between AND/OR and NAND/NOR forms, which matters because many cell libraries are NAND- or NOR-based rather than AND/OR-based.
• The consensus theorem: AB + A′C + BC = AB + A′C. The term BC is called the consensus of AB and A′C — whenever BC = 1, either A = 1 (so AB = 1) or A = 0 (so A′C = 1), so BC never adds a 1 the other two terms do not already cover, and it can be dropped from a minimal expression. Section 2.5 revisits this exact theorem, because the consensus term being redundant algebraically is also precisely the term whose absence causes a static hazard.

Every one of these can be checked by expanding both sides into a truth table and confirming they agree on all rows; that mechanical check is the definition of two Boolean expressions being equivalent, independent of which simplification path was used to get from one to the other.

2.2 Canonical form versus minimal form: SOP and POS

Any Boolean function has a canonical sum-of-products (SOP) form — one AND term per row where the function is 1, each term containing every input variable, ORed together — and, symmetrically, a canonical product-of-sums (POS) form, one OR term per row where the function is 0, ANDed together. Both are always correct and mechanical to write straight from a truth table, which is exactly why they are rarely the cheapest circuit: a function with ten 1-rows out of sixteen needs ten four-literal terms in canonical SOP, when the actual minimum might be two short terms.

A minimal SOP or minimal POS form is the fewest terms, with the fewest literals per term, that is still logically equivalent to the canonical form — fewer literals means fewer gate inputs, less area, less delay. SOP and POS are both always available for the same function; which one ends up cheaper depends on how well the 1s group compared with how well the 0s group. Whichever value is rarer is a useful first guess, not a rule: F = A + BCD has fewer 0s than 1s, yet its SOP form (two terms) is cheaper than its POS form (A+B)(A+C)(A+D). When it matters, minimize both and compare.

2.3 Minimizing with a Karnaugh map — one step of a larger example

The Digital Electronics lesson on Karnaugh maps already works through the full method — Gray-code adjacency, grouping rules, a complete four-variable example — and this lesson leans on that mechanism rather than re-deriving it. Worth walking through here is how a K-map grouping step turns directly into the equations this lesson needs next.

Let us consider F(A,B,C) = Σm(1,5,6,7), a three-variable function. Written on a K-map (by the method covered in full in the lesson linked above), the 1s fall into two overlapping groups: m6 and m7 are adjacent and both have A=1, B=1, giving the pair AB; m1 and m5 are adjacent and both have B=0, C=1, giving the pair B′C. Covering all four 1s with these two pairs gives the minimal SOP:

F = AB + B′C

Two two-literal terms, down from four three-literal terms in canonical SOP — the same payoff the linked lesson's own worked example demonstrates at a larger scale. This particular function is deliberately not a throwaway example: section 2.5 uses exactly this F = AB + B′C to show a static hazard, and the fix for it applies the consensus theorem from section 2.1 again, adding back the consensus term AC.

2.4 Don't-care conditions

A specification sometimes leaves certain input combinations undefined because they are guaranteed never to occur — a four-bit input that is promised to always be a valid BCD digit, say, never actually takes the values 1010 through 1111. Those rows are marked X in the truth table and treated as don't-cares. The rule, covered in the linked K-map lesson in full, is that a don't-care may be included in a group if doing so allows a bigger rectangle, and should be ignored otherwise — it is never required to be covered, only useful. The same idea carries over to equation-level minimization directly: a don't-care row simply has no term written for it in canonical SOP, and is free to be absorbed into whichever neighboring group makes the final expression smallest.

Don't-cares matter for more than circuit size. Marking a row don't-care is an explicit claim that the circuit's behavior there genuinely does not matter — if that turns out to be wrong, the output for that input is whatever minimization happened to produce, which is unpredictable by construction. A row should only be marked don't-care when it truly cannot occur, not merely because it is inconvenient to handle.

2.5 Static hazards

A static hazard is a momentary, unwanted glitch at a combinational circuit's output when exactly one input changes, even though the output's steady-state value before and after the change is the same. A static-1 hazard is a glitch from 1 down to 0 and back to 1; a static-0 hazard is the mirror case. The cause is always the same: two gate paths that both correctly produce the final value briefly disagree while the changing input propagates through one path and not yet through the other, because the two paths have different propagation delays (here, from the extra inverter on one of them; in general from gate count, gate type, load or wiring).

Take F = AB + B′C from section 2.3, with A = C = 1 held constant and only B changing. Algebraically F stays at 1 regardless of B here, since AB = B and B′C = B′ under this assumption, and B + B′ = 1. But as a circuit, F is built from two separate AND gates feeding an OR gate, and when B falls, the AB term's AND gate has to fall while the B′C term's AND gate has to rise through an inverter on B, which adds extra delay on that path. If the falling path is even slightly faster, there is a brief window where neither AND gate output is high, and the OR gate glitches low before settling back to 1.

The fix is the consensus term from section 2.1: adding AC back in, giving F = AB + B′C + AC, removes the hazard even though AC is, by the consensus theorem, logically redundant. What AC buys is a third path that does not depend on B at all, so while the two B-dependent terms are both momentarily low, AC is already high and holds the output at 1 through the transition. The general rule: for every pair of adjacent 1-groups whose shared boundary is the variable that changes, add the consensus term covering that boundary, even though algebraic minimization alone would remove it.

A behavioral Verilog simulation of this function, run with zero-delay semantics, never shows this glitch — the simulator jumps directly from one stable value to the next, with no gate delay modeled. This is why static hazards are a timing phenomenon that RTL-level simulation hides by default, and why synchronous design sidesteps the problem rather than solving it: a clocked register samples its input only at the clock edge, after every combinational signal has had a full clock period to settle. A glitch that resolves well before the next edge is never sampled and therefore never matters — one more reason real designs build synchronous datapaths rather than long chains of untimed combinational feedback.

2.6 A verified minimal implementation

module hazard_fn (
    input  wire a,
    input  wire b,
    input  wire c,
    output wire f
);
    // Minimized SOP for F(A,B,C) = sum of minterms 1,5,6,7
    assign f = (a & b) | (~b & c);
endmodule

Checked against the canonical truth table for all eight input combinations, the minimized expression matches exactly, as it must if the algebra in section 2.3 was done correctly:

OK  a=0 b=0 c=1 -> f=1
OK  a=1 b=1 c=0 -> f=1
OK  a=1 b=1 c=1 -> f=1
ALL TESTS PASSED

Yosys's synthesis of this module produces a single multiplexer cell and nothing else — confirmation that the two-term minimal SOP really is this cheap in practice, not merely on paper. No latch is inferred, since the module is a single continuous assignment with no feedback and no incompletely specified branch.

2.7 Interview questions

What is a static-1 hazard, and what causes it? A momentary glitch to 0 in an output whose value is 1 both before and after a single input change. Two gate paths correctly determine the final value but have different propagation delays, leaving a brief window where neither path's signal is asserted.

How is a static hazard eliminated at the gate level? By adding the consensus term for the two groups whose boundary the changing variable crosses — algebraically redundant, but it holds the output steady through the transition by not depending on the variable that is changing.

Why don't static hazards show up in an RTL simulation? Zero-delay behavioral simulation updates outputs instantly, with no modeling of relative gate delay, so there is no mechanism for two paths to momentarily disagree. The hazard is a physical timing phenomenon that only appears with gate delays, or in real silicon.

Why don't synchronous designs need to fix every hazard? A register samples its input only at the clock edge, after a full period has passed for every combinational signal to settle. A glitch resolved well before the next edge is never sampled. The exceptions are signals that are not sampled by a clock: clocks and clock enables built from logic, asynchronous set and reset inputs, signals crossing into another clock domain, and outputs leaving the chip. Glitches also cost dynamic power even when they are never sampled.

When is a don't-care actually used in minimizing a real function? When the specification guarantees certain combinations cannot occur — an input promised to always be valid BCD, say — those rows can be marked X and absorbed into whichever group makes the result smallest.