Boolean algebra and logic minimization

Explanation

Boolean variables and gates

A Boolean variable is either 0 or 1. Common operations are:

NAND and NOR are universal: either gate type can implement every Boolean function. In an RTL design, describe the intended logic clearly and allow synthesis to choose physical gates unless implementation requirements say otherwise.

Truth tables turn words into behavior

Suppose an alarm must assert when the system is enabled and either temperature or pressure is high:

alarm = enable && (temp_high || pressure_high)

A three-input truth table has 2^3 = 8 rows. Writing every row exposes ambiguous requirements and supplies direct verification cases.

Minterms, maxterms, SOP, and POS

A minterm is an AND term true for exactly one input combination. OR together all minterms for output-1 rows to form canonical sum of products (SOP).

A maxterm is an OR term false for exactly one input combination. AND together maxterms for output-0 rows to form canonical product of sums (POS).

Canonical forms are systematic but often larger than needed. They provide a reliable starting point for simplification and equivalence checking.

Identities used in simplification

A && 1 = A                 A || 0 = A
A && 0 = 0                 A || 1 = 1
A && A = A                 A || A = A
A && !A = 0                A || !A = 1
A && (A || B) = A          A || (A && B) = A
!(A && B) = !A || !B       !(A || B) = !A && !B

Use one transformation at a time and preserve the original expression for comparison. A shorter expression is useful only when it is equivalent for every legal input.

Karnaugh maps

A Karnaugh map places truth-table rows so adjacent cells differ in one input. Group output-1 cells in rectangles of 1, 2, 4, 8, and so on. Groups may wrap across edges and overlap. Prefer the largest groups because changing variables disappear.

For three variables, the columns must follow Gray order 00, 01, 11, 10, not ordinary binary order. Each group produces a product term containing only variables that remain constant throughout that group.

Don't-care conditions

A don't-care marks an input combination whose output is irrelevant or impossible under an enforced assumption. It may be treated as 0 or 1 to simplify the circuit. Document why the combination cannot occur. If it later becomes reachable, a casual don't-care can create unsafe behavior.

Combinational equivalence

Two expressions are equivalent if their outputs match for every relevant input combination. For small logic, compare truth tables. Larger designs use formal equivalence tools. Testing a few convenient inputs does not prove equivalence.

Hazards and glitches

Boolean algebra assumes gates change instantly. Physical paths have delay. If one signal reaches the output along reconvergent paths with different delays, the output may pulse briefly even though the steady-state expression is correct.

For F = A·B + !A·C, changing A can momentarily make both product terms zero when B=C=1. Adding the consensus term B·C removes this static-1 hazard:

F_hazard_free = A·B + !A·C + B·C

Registering an output can prevent downstream sampling of a settled combinational glitch, but asynchronous controls and clock signals require special care. Functional equivalence alone does not prove glitch-free behavior.

Common design mistakes

• Reading ^ as exponentiation instead of XOR.
• Simplifying without respecting operator precedence.
• Treating an unproven illegal state as a don't-care.
• Verifying only output-1 rows.
• Assuming a logically equivalent expression has identical delay behavior.

Worked example

A grant is asserted when a valid request has either high priority or no competing request:

G = V && (H || !C)

Distribute AND to obtain SOP:

G = (V && H) || (V && !C)

Key truth-table observations:

• If V=0, grant is always 0.
• If V=1 and H=1, grant is 1 regardless of C.
• If V=1, H=0, and C=0, grant is 1.
• If V=1, H=0, and C=1, grant is 0.

The factored and SOP expressions match for all eight rows. The factored version communicates the requirement clearly; the SOP form maps directly to output-1 conditions.

Check yourself

What evidence proves two small Boolean expressions are equivalent? Why can two equivalent expressions behave differently for a brief time after an input transition?