3. Boolean Algebra and Logic Minimisation

Introduction and Context

Digital systems represent information through discrete states, most commonly 0 and 1. Although physical circuits are built from transistors, interconnections, and signal paths, their logical behaviour is conveniently described using Boolean algebra. Boolean algebra provides the mathematical language for analysing logic circuits, proving equivalence, simplifying expressions, and designing reliable implementations.

Logic minimisation is the process of obtaining an equivalent Boolean expression or circuit with reduced hardware cost, propagation delay, power consumption, or design complexity. In small systems, minimisation can be performed using Boolean laws and Karnaugh maps. For larger systems, algorithmic procedures such as the Quine–McCluskey method and computer-aided logic synthesis are more appropriate. Minimisation must not, however, be treated as a purely algebraic exercise. A theoretically minimal circuit may exhibit static or dynamic hazards, excessive fan-out, or unacceptable timing behaviour. Consequently, practical design requires a balance between algebraic simplicity, technology constraints, reliability, and verification.

Learning Objectives

After studying this chapter, the reader should be able to:

1. Apply the fundamental laws and theorems of Boolean algebra.

2. Convert Boolean functions into canonical sum-of-products and product-of-sums forms.

3. Interpret minterms, maxterms, truth tables, and incompletely specified functions.

4. Minimise two-, three-, and four-variable functions using Karnaugh maps.

5. Explain prime implicants, essential prime implicants, and implicant selection.

6. Use the Quine–McCluskey method for systematic minimisation.

7. Compare two-level and multi-level logic implementations.

8. Identify static and dynamic hazards and apply hazard-removal techniques.

9. Select an appropriate minimisation method for a practical digital design problem.

Boolean Algebra as a Design Language

A Boolean variable can assume only two values, 0 and 1. The basic operations are AND, OR, and NOT, represented respectively by multiplication or juxtaposition, plus, and an overbar or apostrophe. Thus, AB means A AND B, A + B means A OR B, and A′ means NOT A.

The fundamental identities include the identity laws, A + 0 = A and A·1 = A; the null laws, A + 1 = 1 and A·0 = 0; the idempotent laws, A + A = A and AA = A; the complement laws, A + A′ = 1 and AA′ = 0; and the involution law, (A′)′ = A. The commutative, associative, and distributive laws permit terms to be reordered and regrouped:

A + B = B + A, AB = BA

(A + B) + C = A + (B + C), (AB)C = A(BC)

A(B + C) = AB + AC

Unlike ordinary algebra, Boolean algebra also has the dual distributive law:

A + BC = (A + B)(A + C).

The principle of duality states that a valid Boolean identity remains valid when AND and OR are interchanged and 0 and 1 are interchanged. For example, the dual of A + 0 = A is A·1 = A.

Two particularly important theorems are absorption and De Morgan’s theorems. Absorption is expressed as A + AB = A and A(A + B) = A. De Morgan’s theorems are

(A + B)′ = A′B′

(AB)′ = A′ + B′.

These theorems are central to NAND- and NOR-based implementations. For example, a NAND gate can implement an AND function followed by inversion, while De Morgan transformations allow a network expressed with AND gates to be redesigned using NOR gates.

A useful simplification example is

F = AB + AB′.

Factoring gives F = A(B + B′) = A. The two product terms describe all cases in which A is 1, regardless of B. This illustrates why algebraic simplification can remove redundant hardware.

Representation of Boolean Functions

A truth table lists the output for every input combination. For n variables, there are 2ⁿ combinations. A product term containing every variable exactly once is a minterm. A minterm is 1 for exactly one row of the truth table. For variables A, B, and C, the minterm A′BC corresponds to binary input 011 and is conventionally denoted m₃.

A Boolean function can be written in canonical sum-of-products (SOP) form by ORing all minterms for which the output is 1. For example,

F(A,B,C) = Σm(1,3,5,7).

The binary forms 001, 011, 101, and 111 show that C is always 1; hence F = C.

A maxterm is a sum term containing every variable exactly once and is 0 for exactly one input combination. A canonical product-of-sums (POS) function is formed by ANDing the maxterms corresponding to output 0. If

F(A,B,C) = ΠM(0,2,4,6),

then the zero rows all have C = 0, and the function again simplifies to F = C.

When constructing a maxterm, a variable is uncomplemented if its value in the corresponding zero row is 0 and complemented if its value is 1. This is opposite to the pattern used for minterms. Careful distinction between minterm indexing and maxterm notation is essential.

Many practical functions are incompletely specified. A don’t-care condition represents an input combination that never occurs or whose output is irrelevant. Don’t-cares are denoted X or d and may be treated as either 0 or 1 during minimisation, whichever produces a simpler implementation. They must not be used in a way that changes the required behaviour for valid input combinations.

Algebraic and Two-Level Minimisation

A two-level SOP circuit consists of AND terms feeding an OR gate, while a two-level POS circuit consists of OR terms feeding an AND gate. Algebraic minimisation seeks to reduce the number of literals, terms, or gates. Useful techniques include factoring, combining terms, consensus reasoning, and application of complements.

The consensus theorem is

AB + A′C + BC = AB + A′C.

The term BC is the consensus term and is logically redundant for steady-state functionality. However, its importance in hazard-free design is discussed later: a term that is redundant algebraically may be necessary to maintain continuous output during unequal signal transitions.

For example,

F = AB + A′B + AC

reduces first to B + AC because AB + A′B = B. Further simplification may or may not be possible depending on the relationship among variables. A designer should distinguish between literal minimisation and physical optimisation. A factored expression such as F = B + AC may use fewer gates than an expanded form, while a balanced multi-level form may have lower delay than a long cascade.

Karnaugh Maps: Visual Adjacency and Grouping

A Karnaugh map (K-map) is a geometrical representation of a truth table in which adjacent cells differ in only one variable. Cell ordering follows Gray code, such as 00, 01, 11, 10, rather than ordinary binary order. This arrangement makes algebraic combination visible.

For SOP minimisation, cells containing 1 are grouped in rectangles containing 1, 2, 4, 8, or another power of two cells. Groups may wrap around map edges, and corner cells may be adjacent. Diagonal cells are not adjacent. Each group produces a product term consisting only of variables that remain constant throughout the group. A group of 2 eliminates one variable, a group of 4 eliminates two, and so forth.

For POS minimisation, the same procedure is applied to cells containing 0. Each zero group produces a sum term. The largest possible groups are normally preferred because they eliminate the greatest number of literals, although the final objective is to cover all required cells with a low-cost set of terms.

Consider

F(A,B,C,D) = Σm(0,1,2,3,8,9,10,11).

The eight cells correspond to B = 0, while A, C, and D vary. A group of eight therefore gives F = B′. This result is much easier to see on a K-map than through repeated algebraic manipulation.

A prime implicant is a group that cannot be enlarged without including an invalid cell. An essential prime implicant covers at least one required 1-cell not covered by any other prime implicant. Essential prime implicants must be selected. Remaining uncovered cells are covered by suitable non-essential prime implicants, with attention to gate cost and hazards.

K-maps are highly effective for up to four variables and remain usable, with difficulty, for five or six variables. Beyond that size, visual grouping becomes error-prone and algorithmic or computer-based methods are preferable.

The Quine–McCluskey Method

The Quine–McCluskey method is a tabular minimisation procedure. It is systematic, repeatable, and suitable for computer implementation. Its principal stages are:

1. List the minterms in binary form and group them according to the number of 1s.

2. Compare terms in adjacent groups. If two terms differ in exactly one bit, combine them by replacing that bit with a dash.

3. Repeat comparisons until no further combinations are possible.

4. Mark terms that were not combined; these are prime implicants.

5. Construct a prime-implicant chart showing which prime implicants cover which minterms.

6. Select essential prime implicants and then choose additional implicants to cover all remaining minterms.

For example, minterms 4 (0100) and 5 (0101) combine to 010– because they differ only in the final bit. Terms 4 and 6 combine to 01–0. A term may be combined only when all fixed bits agree and exactly one fixed bit differs.

The method can include don’t-care terms during combination, although don’t-cares do not need to be covered in the final function. The prime-implicant chart provides a transparent basis for selecting a cover. When several covers have equal literal counts, technology-specific factors such as fan-in, delay, power, and hazard behaviour should guide the choice.

The method is exact for two-level minimisation but can become computationally expensive as the number of variables and implicants increases. Modern synthesis tools use more advanced algorithms, including heuristic Boolean optimisation, binary decision diagrams, and satisfiability-based techniques.

Multi-Level Logic Optimisation

Two-level minimisation is not always the best implementation strategy. Multi-level logic permits intermediate expressions to be shared. For example,

F₁ = AB + AC, F₂ = AB + AD

can be implemented using one shared product AB, followed by separate OR structures. Factoring gives F₁ = A(B + C) and F₂ = A(B + D), potentially reducing hardware.

Multi-level optimisation considers algebraic division, common-subexpression extraction, gate balancing, fan-in limits, and technology mapping. A circuit with fewer literals may nevertheless have greater delay if signals pass through many logic levels. Conversely, a modest increase in literal count may substantially reduce delay by balancing paths or using a faster gate structure.

In CMOS design, minimisation can reduce transistor count, switching activity, and dynamic power. In programmable logic devices, the relevant cost may be the number of lookup tables, product terms, routing resources, or logic levels rather than the number of traditional gates. In standard-cell ASIC design, synthesis tools optimise according to area, timing, power, and design constraints.

Therefore, the appropriate objective is not simply “the shortest Boolean expression.” It is a constrained optimisation problem:

minimise cost subject to functional correctness, timing, power, area, testability, and reliability requirements.

Hazards in Combinational Logic

A hazard is an unwanted transient caused by unequal propagation delays. It may occur even when the Boolean function is logically correct in steady state. Hazards are particularly important in asynchronous systems, clock-gating circuits, reset paths, control logic, and interfaces between independently timed blocks.

A static-1 hazard occurs when the output should remain at 1 but briefly falls to 0 during a single-input transition. Consider

F = AB + A′C.

If B = C = 1 and A changes, both product terms should ensure that F remains 1. Due to unequal delays, AB may turn off before A′C turns on, causing a pulse to 0. Adding the consensus term BC gives

F = AB + A′C + BC,

which provides an overlapping path and removes the static-1 hazard for the relevant transition.

A static-0 hazard occurs when the output should remain at 0 but briefly rises to 1. It is commonly analysed using POS expressions and is removed by adding appropriate redundant sum terms so that neighbouring zero conditions are covered continuously.

A dynamic hazard occurs when the output changes more than once while making a single intended transition, such as 0-1-0-1. Dynamic hazards generally arise in multi-level circuits with multiple reconvergent paths. They are more difficult to eliminate than static hazards. A common design strategy is to use hazard-free two-level structures, avoid unnecessary reconvergence, balance delays where appropriate, and verify the circuit with timing simulation.

K-map hazard analysis provides a useful interpretation: every pair of adjacent 1-cells corresponding to a permitted single-variable transition should be covered by at least one common implicant for static-1 hazard-free SOP operation. For POS circuits, the analogous requirement applies to adjacent zero cells.

Hazard removal illustrates an important engineering principle. A redundant term may be unnecessary for Boolean equivalence but essential for temporal correctness. Logic minimisation must therefore be performed with the operating environment and timing assumptions in view.

Applied Scenario: Minimising a Safety Interlock

The following is an illustrative engineering case. A motor controller permits operation when an enable command E is active, the guard G is closed, and either the automatic authorization A or manual authorization M is present. The intended function is

R = E G (A + M).

A diagnostic review identifies a transition in which automatic authorization is withdrawn while manual authorization is asserted. If the implementation is expanded into several reconvergent paths, unequal delays could cause a brief removal of R. Because R controls a safety-related actuator, even a short pulse is unacceptable.

The design team first writes the truth conditions and marks invalid operating combinations as don’t-cares. A K-map is used to identify a compact expression, but the team does not select solely on literal count. The enable and guard conditions are factored and placed in a controlled logic path. Authorization signals are combined in a way that avoids unnecessary reconvergence. Hazard analysis is then performed for every permitted single-input transition, followed by gate-level timing simulation across process and temperature corners.

The resulting implementation uses a factored multi-level circuit, an explicit guard condition, and additional consensus coverage where the transition analysis requires it. Formal equivalence checking confirms that the circuit matches the specification for all valid input combinations. Timing verification confirms that no unsafe pulse is generated within the assumed delay model.

The central lesson is that minimisation, timing analysis, and safety verification are connected activities. A circuit that is minimal in a truth-table sense may be unsuitable when outputs control physical equipment.

Common Errors and Design Limitations

Several mistakes recur in Boolean minimisation. Treating diagonal K-map cells as adjacent produces invalid groups. Omitting wrap-around adjacency prevents valid simplification. Confusing minterm and maxterm conventions reverses the function. Grouping a non-power-of-two number of cells is invalid. Using a don’t-care as if it were a required output can alter system behaviour.

Another error is selecting only the largest groups and overlooking coverage requirements. Every required 1 in an SOP map must be covered, and every required 0 in a POS map must be covered. A further mistake is assuming that the expression with the fewest literals always gives the fastest or safest circuit.

At the implementation level, unexamined hazards, excessive fan-out, gate input limitations, and reconvergent paths may undermine a mathematically correct design. Active-low signals and complemented variables also demand disciplined notation. For safety-critical functions, independent verification, traceable requirements, formal equivalence checking, and documented review are preferable to reliance on hand simplification alone.

Professional Practice and Contemporary Tools

Logic minimisation is embedded in electronic-design-automation workflows. Hardware description languages express Boolean behaviour, synthesis tools infer logic, and optimisation engines map the design to FPGA lookup tables or ASIC standard cells. Static timing analysis evaluates path delays, while formal tools verify equivalence and selected safety properties. Power-analysis tools estimate switching activity and energy consumption.

Machine-learning-assisted synthesis is being explored for optimisation and design-space search, but its outputs still require formal functional verification and engineering review. Automated tools can optimise according to stated constraints; they cannot determine whether the specification itself is complete, safe, or ethically acceptable. In systems controlling medical, transport, industrial, or energy equipment, professional responsibility includes clear assumptions, conservative handling of unknown states, independent checking, and compliance with applicable safety standards.

Best-Practice Workflow

A robust workflow begins with a precise specification and explicit identification of valid, invalid, and don’t-care input states. The designer then constructs a truth table or canonical expression, performs an initial algebraic or K-map minimisation, and compares alternative SOP, POS, and multi-level forms. The selected design is evaluated for area, timing, power, fan-in, fan-out, testability, and hazards. Finally, simulation, formal equivalence checking, and—where necessary—hardware measurement confirm implementation behaviour.

The method should match the problem. Boolean laws are efficient for local transformations, K-maps are clear for small functions, Quine–McCluskey is systematic for moderate functions, and synthesis tools are appropriate for large designs. The best implementation is the one that satisfies the complete engineering specification rather than the one that merely appears algebraically shortest.

Chapter Summary

Boolean algebra provides the formal basis for representing and transforming digital logic. Its complement, absorption, distributive, duality, and De Morgan laws support circuit simplification and NAND/NOR implementation. Canonical SOP and POS forms are built from minterms and maxterms, while don’t-care conditions permit controlled flexibility during minimisation.

Karnaugh maps exploit Gray-code adjacency to identify implicants, prime implicants, and essential prime implicants. The Quine–McCluskey method performs the same type of minimisation systematically through binary combination and prime-implicant charts. Multi-level optimisation extends beyond literal reduction by considering sharing, delay, power, fan-in, and technology mapping.

Hazards demonstrate that steady-state Boolean equivalence does not guarantee correct temporal behaviour. Static-1, static-0, and dynamic hazards arise from unequal propagation delays and reconvergent paths. Consensus terms and hazard-aware structural design can prevent unwanted pulses. Professional logic design therefore combines mathematics, implementation constraints, verification, and safety judgement.

Key Terms

Boolean algebra: A mathematical system for variables restricted to binary values and operations.

Minterm: A product term containing every variable once and equal to 1 for one input combination.

Maxterm: A sum term containing every variable once and equal to 0 for one input combination.

Canonical SOP: An OR of minterms representing all input rows where a function is 1.

Canonical POS: An AND of maxterms representing all input rows where a function is 0.

Don’t-care: An input condition whose output is irrelevant or invalid and may assist minimisation.

Implicant: A product term that covers only input combinations where the function is 1.

Prime implicant: An implicant that cannot be enlarged without covering an invalid cell.

Essential prime implicant: A prime implicant covering at least one required cell covered by no other prime implicant.

Karnaugh map: A Gray-code map used to visualise adjacency and simplify Boolean functions.

Quine–McCluskey method: A tabular, systematic procedure for two-level Boolean minimisation.

Consensus term: A logically redundant term that may provide continuity and remove a hazard.

Two-level logic: A circuit structured as SOP or POS with two principal logic stages.

Multi-level logic: A circuit using shared intermediate expressions across several logic levels.

Static-1 hazard: A transient 0 when the output should remain 1.

Static-0 hazard: A transient 1 when the output should remain 0.

Dynamic hazard: Multiple unwanted output transitions during one intended transition.

Reconvergent path: A structure in which a signal divides and later returns through different logic paths.

Review Questions

Short Answer Questions

1. State the two De Morgan theorems and explain their circuit significance.

2. What distinguishes a minterm from a maxterm?

3. Why are K-map cells arranged in Gray-code order?

4. Define an essential prime implicant.

5. What is a static-1 hazard?

Long Answer Questions

1. Explain the principal Boolean laws and illustrate how they simplify a digital circuit.

2. Describe the complete procedure for minimising a function using a Karnaugh map.

3. Explain the Quine–McCluskey method, including prime-implicant chart construction.

4. Compare two-level and multi-level logic optimisation with respect to area, delay, and power.

5. Explain static and dynamic hazards and discuss methods for reducing them.

Analytical / Application Questions

1. Minimise F(A,B,C,D) = Σm(0,1,2,3,8,9,10,11) using a K-map and justify the grouping.

2. For F = AB + A′C, identify the possible static hazard and propose a hazard-free expression.

3. A design has fewer gates after minimisation but produces a short pulse on a reset line. Analyse why this may occur and recommend a verification and redesign strategy.

22. Multiple Choice Questions with Answers

Question 1

Which expression is an application of the absorption law?

A. A + AB = A

B. A + A′ = 1

C. A(B + C) = AB + AC

D. (AB)′ = A′ + B′

Correct Answer: A. A + AB = A

Question 2

The canonical SOP representation of a Boolean function contains

A. Maxterms for which the output is zero

B. Minterms for which the output is one

C. Only essential prime implicants

D. Only complemented variables

Correct Answer: B. Minterms for which the output is one

Question 3

In a Karnaugh map, two cells are adjacent when they

A. Are diagonally positioned

B. Differ in exactly two variables

C. Differ in exactly one variable

D. Have identical binary addresses

Correct Answer: C. Differ in exactly one variable

Question 4

What is the principal purpose of a don’t-care condition?

A. To force the output permanently to zero

B. To permit either value during minimisation when useful

C. To indicate a required output of one

D. To eliminate the need for verification

Correct Answer: B. To permit either value during minimisation when useful

Question 5

In the Quine–McCluskey method, an uncombined term after all possible comparisons is a

A. Maxterm

B. Consensus term

C. Prime implicant

D. Hazard term

Correct Answer: C. Prime implicant

Question 6

Which expression illustrates the consensus theorem?

A. AB + A′C + BC = AB + A′C

B. AB + A′B = A′

C. A + AB = B

D. A + A′B = A + B′

Correct Answer: A. AB + A′C + BC = AB + A′C

Question 7

A static-1 hazard occurs when an output that should remain high

A. Changes from 0 to 1 only once

B. Briefly falls to 0 because of unequal delays

C. Remains permanently at 0

D. Oscillates due to a clock signal

Correct Answer: B. Briefly falls to 0 because of unequal delays

Question 8

For F = AB + A′C, which additional term can remove the relevant static-1 hazard?

A. A + B

B. A′B′

C. BC

D. AC′

Correct Answer: C. BC

Question 9

Why might a multi-level implementation be preferred over a two-level minimum SOP?

A. It always uses more literals

B. It can share intermediate expressions and meet timing or fan-in constraints

C. It cannot contain hazards

D. It eliminates the need for a truth table

Correct Answer: B. It can share intermediate expressions and meet timing or fan-in constraints

Question 10

Which design decision best reflects hazard-aware minimisation?

A. Always delete algebraically redundant terms

B. Ignore propagation delay after truth-table verification

C. Retain suitable consensus coverage when signal transitions require continuity

D. Use diagonal K-map groupings to maximise reduction

Correct Answer: C. Retain suitable consensus coverage when signal transitions require continuity