Combinational Logic Design

A combinational circuit is a network of logic gates whose output values at any instant are a pure function of the input values at that same instant — formally, an output vector $\mathbf{Z} = f(\mathbf{X})$ with no dependence on prior inputs or internal state. This distinguishes it from sequential logic, where outputs also depend on stored state (flip-flops, latches). Because a combinational function has no memory, it is completely and exactly described by a truth table: an enumeration of every possible input combination alongside the corresponding output value(s). The central design question is: given a truth table, how do we systematically obtain a Boolean expression — and hence a gate circuit — that reproduces it exactly? The answer rests on two canonical forms, each derived directly from the table without any need for insight or trial and error. A minterm for an $n$-input function is a product (AND) term that includes every one of the $n$ input variables, each appearing either uncomplemented or complemented, chosen so that the term evaluates to 1 for exactly one row of the truth table. For inputs $A, B, C$, the minterm for the row $A{=}1, B{=}0, C{=}1$ is $A \cdot \bar{B} \cdot C$. The sum-of-products (SOP) form of a function is the logical OR of the minterms corresponding to every row where the output is 1:

Dually, a maxterm is a sum (OR) term including every variable, chosen so it evaluates to 0 for exactly one row; for $A{=}1,B{=}0,C{=}1$ the maxterm is $\bar{A} + B + \bar{C}$. The product-of-sums (POS) form is the AND of the maxterms corresponding to every row where the output is 0:

SOP and POS are duals of each other under Boolean Algebra's duality principle (swap AND↔OR, 0↔1), and De Morgan's laws let you convert between them. Every Boolean function has both an SOP and a POS canonical form, and both are unique up to term ordering — this uniqueness is what makes the synthesis procedure mechanical rather than creative.

The synthesis procedure has four steps: build the truth table, extract the relevant terms, form the algebraic expression, then draw the two-level circuit. The same procedure works for SOP and POS; only which rows you pick and which gates you use differ.

SOP construction. Scan the truth table for every row where the output is 1. For each such row, write the minterm: variable $X_i$ appears uncomplemented if $X_i{=}1$ in that row, complemented if $X_i{=}0$. OR all these minterms together.

POS construction. Scan for every row where the output is 0. For each such row, write the maxterm: variable $X_i$ appears complemented if $X_i{=}1$ in that row, uncomplemented if $X_i{=}0$ (the opposite convention from SOP — this is what makes the term evaluate to 0 exactly on that row). AND all maxterms together. ``` ALGORITHM: TruthTableToSOP(truth_table, variables) // truth_table: list of rows, each row = (input_assignment, output_bit) // variables: ordered list of n Boolean variable names terms = empty list for each row (assignment, output) in truth_table: if output == 1: term = empty list for i = 1 to n: if assignment[i] == 1: term.append( variables[i] ) // uncomplemented literal else: term.append( NOT(variables[i]) ) // complemented literal terms.append( AND(term) ) // one minterm if terms is empty: return CONSTANT_0 // edge case: F is identically 0 return OR(terms) // sum of all minterms

ALGORITHM: TruthTableToPOS(truth_table, variables) clauses = empty list for each row (assignment, output) in truth_table: if output == 0: clause = empty list for i = 1 to n: if assignment[i] == 1: clause.append( NOT(variables[i]) ) // opposite convention vs. SOP else: clause.append( variables[i] ) clauses.append( OR(clause) ) // one maxterm if clauses is empty: return CONSTANT_1 // edge case: F is identically 1 return AND(clauses) ``` Once the algebraic expression is obtained, the circuit follows mechanically:

• SOP → AND-OR circuit: one AND gate per minterm (with inverters feeding complemented inputs), all AND-gate outputs feeding a single final OR gate.
• POS → OR-AND circuit: one OR gate per maxterm (with inverters feeding complemented inputs), all OR-gate outputs feeding a single final AND gate.

Both are called two-level logic, since ignoring inverters, a signal passes through exactly two gate stages from input to output. This uniformity is why canonical forms are the natural starting point for programmable logic devices (PLDs and PLAs), which are physically organized as an AND-plane followed by an OR-plane.

Correctness argument. The proof that SOP synthesis is correct follows directly from the structure of minterms. Each minterm $m_i$ is constructed so that it evaluates to exactly 1 on row $i$'s input assignment and exactly 0 on every other assignment — this is because a minterm is an AND of all $n$ literals, and an AND is 1 only when every literal is 1, which by construction happens only for the one assignment it was built from. Since $F = m_{i_1} + m_{i_2} + \cdots + m_{i_k}$ (OR of the minterms for all rows where $F{=}1$), and an OR is 1 exactly when at least one term is 1, $F$ evaluates to 1 precisely on the union of those single rows — which is exactly the set of rows where the truth table says $F{=}1$, and 0 everywhere else. This is not an approximation or heuristic: it is an exact algebraic reconstruction of the table, term by term. The POS argument is the exact dual: each maxterm is 0 on exactly one row (where $F{=}0$) and 1 elsewhere, so the AND of all such maxterms is 0 exactly on the union of those rows and 1 everywhere else.

Uniqueness. For a fixed variable ordering, the canonical SOP (sum of all minterms where $F=1$, no more, no fewer) is unique, and likewise for canonical POS. This matters pedagogically: two people deriving the canonical form of the same table from the same variable order will always get the identical expression, which is what makes the method mechanical rather than a matter of taste.

Time and space complexity of synthesis. For $n$ input variables, a truth table has $2^n$ rows. Building the canonical SOP or POS requires scanning all $2^n$ rows once — $O(2^n)$ time — and in the worst case (e.g., a parity function, where exactly half the rows are 1) produces $2^{n-1}$ terms, each of length $n$ literals. So:

• Time to derive the expression: $O(n \cdot 2^n)$ (scan $2^n$ rows, build an $n$-literal term for up to $2^n$ of them).
• Circuit size (gate count): $O(n \cdot 2^n)$ in the worst case — up to $2^{n-1}$ AND gates each with $n$ inputs, plus one OR gate with up to $2^{n-1}$ inputs.
• Circuit depth: exactly 2 gate levels (plus 1 level of inverters), independent of $n$ — this is the defining feature of two-level logic, and it is why SOP/POS forms are prized for speed (constant propagation delay in terms of gate levels) even when they are not gate-count-minimal.

The honest tradeoff. Canonical forms are always correct but almost never minimal. A function might have a 2-gate implementation using shared sub-expressions or algebraic factoring, yet its canonical SOP might require dozens of gates because every minterm is written out in full with no term-sharing. For example, $F = A$ (a function of one relevant variable among three inputs $A,B,C$) still requires 4 minterms in canonical SOP over $A,B,C$, even though the circuit "just wire $A$ to $F$" is obviously simpler. This gap between correct-by-construction and minimal is precisely the motivation for algebraic simplification and, more systematically, for Karnaugh Maps, which exploit adjacency between minterms to merge terms and shrink the circuit — without ever risking incorrectness, because every simplification step is a Boolean-algebra-justified equivalence. Real synthesis tools (and human designers) therefore use canonical forms as a correctness baseline — a ground truth to check simplified designs against — rather than as the final circuit to fabricate.

Consider a 1-bit full adder's carry-out logic, a building block that reappears inside every Adders and the Ripple-Carry Adder design. Inputs are $A$, $B$ (the bits being added) and $C_{in}$ (carry in from the previous bit position). The output $C_{out}$ is 1 whenever at least two of the three inputs are 1 (majority function).

Step 1 — SOP. Collect minterms for the four rows where $C_{out}=1$:

• Row $(0,1,1)$: $\bar{A} \cdot B \cdot C_{in}$
• Row $(1,0,1)$: $A \cdot \bar{B} \cdot C_{in}$
• Row $(1,1,0)$: $A \cdot B \cdot \bar{C_{in}}$
• Row $(1,1,1)$: $A \cdot B \cdot C_{in}$

This is exactly correct — four AND gates feeding one OR gate, 3 inputs and 2 inverters ($\bar A$, $\bar B$ needed once each, $\bar{C_{in}}$ once) — but it is not minimal. Applying Boolean algebra (idempotence, $X + X = X$, then factoring) collapses it to the familiar 3-term form:

which uses only 3 two-input AND gates and one 3-input OR gate — smaller, same function. This shrinkage is a preview of exactly what Karnaugh Maps automate.

Step 2 — POS, for cross-check. Collect maxterms for the four rows where $C_{out}=0$:

• Row $(0,0,0)$: $A + B + C_{in}$
• Row $(0,0,1)$: $A + B + \bar{C_{in}}$
• Row $(0,1,0)$: $A + \bar{B} + C_{in}$
• Row $(1,0,0)$: $\bar{A} + B + C_{in}$

Verification. Plug in $A{=}1, B{=}1, C_{in}{=}0$ (row where table says $C_{out}=1$) into both forms:

• Simplified SOP: $AB + BC_{in} + AC_{in} = (1)(1) + (1)(0) + (1)(0) = 1 + 0 + 0 = 1$. ✓ matches table.
• POS: $(1+1+0)(1+1+1)(1+0+0)(0+1+0) = (1)(1)(1)(1) = 1$. ✓ matches table.

Both derivations, obtained independently from disjoint sets of table rows, agree with the truth table and with each other — exactly as the correctness argument guarantees, since SOP and POS are two different but logically equivalent reconstructions of the same function.

Two-level canonical logic is the conceptual seed for a huge swath of digital hardware. Programmable Logic Arrays (PLAs) and Programmable Array Logic (PAL) devices are literally fabricated as a fixed AND-plane followed by an OR-plane, mirroring SOP structure directly in silicon — engineers program them by specifying exactly which minterms feed which OR gate. Read-only memories (ROMs) used as lookup tables implement arbitrary combinational functions by storing precomputed truth-table outputs, an SOP-equivalent brute-force approach. ALU control logic inside a CPU's datapath — deciding which operation an ALU performs based on instruction opcode bits — is routinely derived by writing the truth table of desired control signals and reducing it via SOP/POS before further optimization. Decoders, which turn an $n$-bit address into one-of-$2^n$ select lines, and multiplexers, which select one of several inputs based on a control code, are themselves standard combinational building blocks whose internal gate-level designs and whose usage as building blocks for arbitrary functions both trace directly back to canonical-form reasoning; see Multiplexers and Decoders for the next layer of this story. Finally, every hardware description language (Verilog, VHDL) synthesis tool, when compiling an `assign` statement or `case` block describing combinational behavior, internally represents the logic in a canonical or near-canonical form before applying industrial-strength minimization — the exact pipeline (truth table → canonical form → minimized circuit) taught here, at industrial scale.

Ask the tutor: How do Karnaugh maps use minterm adjacency to simplify an SOP expression without changing the function it computes?