Minimize logic without changing its meaning

Prerequisites: Truth tables, AND, OR, NOT, and binary inputs.

Learning objectives

• Derive a sum of products from a truth table.
• Explain what minimization preserves and what it does not.
• Exhaustively check a small Boolean identity.

Begin with a specification

A Boolean function maps each combination of input bits to an output bit. A circuit is one implementation of that function. Minimization seeks a cheaper implementation under a chosen cost model. Fewer product terms, fewer gates, smaller area, and shorter delay are related objectives, but they are not identical objectives.

Consider an output that is true exactly when at least two of three inputs are true. Name the inputs A, B, and C. The true rows are 011, 101, 110, and 111. A canonical sum of products contains one AND term for each true row: NOT(A)BC OR A NOT(B)C OR AB NOT(C) OR ABC. Each term initially specifies every input.

Combine rows that differ in one position

The identity XY OR X NOT(Y) = X removes a variable whose value does not affect the result. Combining rows 110 and 111 yields AB. Combining 101 and 111 yields AC. Combining 011 and 111 yields BC. A row may participate in several combinations. The resulting function is AB OR AC OR BC.

A Karnaugh map arranges truth-table rows so neighboring cells differ in one input bit. Groups contain a power of two cells and wrap across appropriate edges. The picture is a bookkeeping aid for the same algebra, not a new definition of equivalence. For this function, each pairwise term covers a true row that neither other pair covers, so all three terms are needed in this two-level form.

Verify the proposed reduction independently:

from itertools import product
for a, b, c in product((False, True), repeat=3):
    specification = int(a) + int(b) + int(c) >= 2
    implementation = (a and b) or (a and c) or (b and c)
    assert specification == implementation

Logical equivalence is only one obligation

A don’t-care input is a combination for which the specification permits either output. It is not an inconvenient row you may silently discard. If hardware can reach that combination after reset or a fault, decide whether unspecified behavior is acceptable before exploiting it.

Equivalent expressions can have different transient behavior because physical paths have different delays. If A changes while the output should remain true, one path may stop asserting before another starts. That is a hazard. Synchronous designs usually sample only after settling, but asynchronous controls may require hazard analysis and redundant terms. Finally, mapping to an actual gate library can favor NAND structures or shared subexpressions over the fewest written literals. Always state whether you are optimizing a Boolean expression, a mapped circuit, or a timed physical implementation.

Primary reading

• Combinational Logic (MIT OpenCourseWare, Computation Structures).

Practice problem

Let F be true for binary inputs ABC equal to 001, 011, 101, and 111. Derive a reduced expression, explain why it is valid, and state one reason the smallest algebraic expression might still be insufficient as a hardware specification. Then change the true rows to 010, 011, 110, and 111.

Worked solution

In the first table every true row has C=1, and all four choices of A and B appear. Pair 001 with 011 to eliminate B, pair 101 with 111 to eliminate B, then combine the resulting NOT(A)C and AC terms to eliminate A. Therefore F=C. In the second table every true row has B=1 and every choice of A and C appears, so F=B. Neither conclusion depends on guessing from only some rows: the false rows must also agree. The Boolean equation alone omits output drive, allowable propagation delay, and sampling conditions. A wire implementation may satisfy the truth table while failing a loading or timing requirement.

Check your understanding

Why may the row 111 be used in more than one implicant?

• Each row must be assigned to exactly one gate.
• ORing overlapping true conditions preserves the Boolean function.
• Repeated use cancels the output.
• It changes a true row into a don’t-care.

Explanation

An OR remains true when several terms are true; overlapping coverage is valid.

When is it legitimate to use a don’t-care during minimization?

• Whenever it reduces gate count.
• Whenever the input is rare.
• When the specification explicitly allows either output for that combination.
• Whenever simulation has not visited it.

Explanation

The freedom comes from the specification, not from frequency or incomplete tests.

Primary reading

• Combinational Logic: MIT OpenCourseWare, Computation Structures

Open the study and save your work →