Logic Function Simplification

Introduction

Digital systems process binary information using logic variables that take one of two values: 0 or 1. A logic function describes the relationship between input variables and an output. Although a function may be implemented directly from its truth table, that implementation is often inefficient. Simplification reduces the number of gates, literals, interconnections, propagation delay, power consumption, circuit area, and cost.

This chapter develops systematic methods for simplifying Boolean functions. It covers canonical sum-of-products (SOP) and product-of-sums (POS) forms, Boolean algebra, Karnaugh maps, don’t-care conditions, and an introduction to tabulation-based algorithmic minimization. The emphasis is on selecting practical implementations rather than merely obtaining an algebraically shorter expression.

Learning Objectives

By the end of this chapter, a learner should be able to:

1. Convert a truth table into canonical SOP and POS expressions.
2. Apply Boolean identities and theorems to simplify logic functions.
3. Minimize functions using two-, three-, and four-variable Karnaugh maps.
4. Use don’t-care conditions appropriately.
5. Explain the basic Quine–McCluskey minimization procedure.
6. Compare alternative implementations using gate count, literals, delay, power, and cost.
7. Recognize practical hazards and limitations of minimized combinational circuits.

1. Boolean Functions and Logic Literals

A Boolean function is written as F(A,B,C,...) where each variable belongs to the set {0,1}. The principal operations are:

• NOT: A' or ¬A
• AND: AB
• OR: A+B

A literal is a variable or its complement. Thus, A, B', and C are literals. A product term is an AND combination of literals, such as AB'C. A sum term is an OR combination, such as (A+B'+C).

A function is in SOP form when product terms are ORed together:

It is in POS form when sum terms are ANDed together:

SOP is naturally associated with AND gates feeding an OR gate. POS is naturally associated with OR gates feeding an AND gate. NAND-only and NOR-only implementations can also be derived from these forms.

2. Minterms and Maxterms

For n variables, there are 2ⁿ possible input combinations. A minterm is a product term containing every variable exactly once. It is 1 for exactly one input combination. A maxterm is a sum term containing every variable exactly once. It is 0 for exactly one input combination.

For variables A, B, and C, the minterm corresponding to 101 is:

The associated maxterm is formed by using an uncomplemented variable when its input is 0 and a complemented variable when its input is 1. Therefore, for 101:

The minterm is 1 at 101, whereas the maxterm is 0 at 101.

Canonical SOP

Canonical SOP is the sum of all minterms for which the function equals 1:

This notation means that F is 1 at minterm indices 1, 3, 5, and 7. Expanding:

Factoring gives:

Canonical POS

Canonical POS is the product of all maxterms for which the function equals 0. If the same function is 1 at 1, 3, 5, and 7, it is 0 at 0, 2, 4, and 6:

The expanded POS is:

This expression also simplifies to F=C. In general, for n variables, minterm and maxterm indices are interpreted as binary numbers with A conventionally treated as the most significant variable.

3. Boolean Algebraic Simplification

Boolean algebra provides identities for transforming equivalent expressions. The most frequently used laws are shown below.

The duality principle states that a valid Boolean identity remains valid when AND and OR are interchanged and 0 and 1 are interchanged.

Worked Example 1: SOP Simplification

Simplify:

Factor the first two terms:

Because B+B'=1:

Using X+X'Y=X+Y:

The original expression contains three product terms and five literal occurrences. The simplified form contains two literals and can usually be implemented with one NOT gate and one OR gate, depending on available complemented signals.

Worked Example 2: POS Simplification

Simplify:

Apply the identity (X+Y)(X+Z)=X+YZ:

This is also obtained by recognizing that the factor is 1 when A is 1 and is 0 when A is 0, regardless of B.

Algebraic simplification can be fast for small expressions, but it does not always reveal the globally minimal two-level form. Different algebraic paths can produce different-looking expressions, and a shorter expression is not necessarily the fastest physical circuit.

4. Karnaugh Maps

A Karnaugh map (K-map) is a graphical arrangement of truth-table cells in Gray-code order. Adjacent cells differ in exactly one variable. This arrangement allows adjacent 1s to be combined, eliminating variables that change within a group.

For SOP minimization, place 1s in cells corresponding to minterms. Groups must contain 1, 2, 4, 8, or another power of two cells. Groups may wrap around edges, and the four corners of a rectangular map are adjacent. Groups should be as large as possible, although overlapping groups are permitted when they produce a simpler expression.

For POS minimization, place 0s in the map and group them using the same adjacency rules. A grouped 0 produces a sum term. A variable appears uncomplemented in that sum term if it is 0 throughout the group and complemented if it is 1 throughout the group.

K-map Procedure for SOP

1. Draw the map using Gray-code row and column labels.
2. Enter 1 for every required minterm.
3. Enter don’t-care symbols, if applicable.
4. Form the largest legal groups.
5. Ensure every required 1 is covered.
6. Derive one product term from each group.
7. OR the product terms and verify the result.

Worked Example 3: Three-Variable K-map

Minimize:

All four listed minterms have C = 1. They form a group of four, while A and B vary. Therefore only C remains:

The K-map makes the simplification visually immediate.

Worked Example 4: Four-Variable K-map

Minimize:

The eight cells correspond to A = 0 or 1, while C = 0 and C = 1, and D = 0 or 1. The only constant variable is B = 0. Thus:

A group of eight is preferable to smaller groups because it eliminates three variables.

Prime and Essential Prime Implicants

An implicant is a product term that covers only 1-cells (and possibly don’t-care cells). A prime implicant cannot be enlarged without covering a required 0. An essential prime implicant covers at least one required 1 that no other prime implicant covers. Essential prime implicants must be included in the final expression.

A practical K-map strategy is to select essential groups first, then cover any remaining 1s with the fewest additional groups and literals.

5. Don’t-Care Conditions

A don’t-care condition is an input combination that never occurs, is irrelevant, or may produce either output without affecting system operation. It is denoted by X, d, or included after a semicolon:

During minimization, a don’t-care cell may be treated as 1 when it helps form a larger SOP group, or as 0 when it does not help. It must not be used in a way that changes any required output.

Worked Example 5

Suppose:

The required 1s and don’t-cares together form an eight-cell group in which B = 0. The minimized result is therefore:

If the don’t-cares were treated as 0, the result would require more terms. This illustrates why don’t-cares can reduce hardware, although they should be used only when their input conditions are genuinely unspecified.

6. Algorithmic Minimization: Quine–McCluskey Method

Karnaugh maps become inconvenient for many variables. The Quine–McCluskey method is a tabulation algorithm that provides a systematic minimization procedure and is suitable for computer implementation.

The principal stages are:

1. List the minterms in binary form.
2. Group them according to the number of 1s.
3. Compare terms in adjacent groups.
4. Combine terms differing in exactly one bit, replacing that bit with a dash.
5. Repeat combination until no further combination is possible.
6. Record the prime implicants.
7. Construct a prime-implicant chart.
8. Select essential prime implicants and cover remaining minterms economically.

For example, minterms 5 (0101) and 7 (0111) differ only in the C position. They combine as 01–1, representing AB'D if the variable order is A, B, C, D. A dash indicates a variable that has been eliminated.

The method guarantees a minimum two-level SOP under the chosen cost criterion, provided the chart-selection stage is solved correctly. However, “minimum” must be defined. Minimum literal count, minimum number of product terms, minimum gate count, and minimum delay may lead to different choices. Algorithmic minimization also does not automatically account for hazards, fan-out, wiring, technology mapping, or physical layout.

7. Measuring Implementation Quality

Logic minimization is valuable because circuit resources are limited. Important evaluation criteria include:

• Gate count: the number of logic gates.
• Literal count: the number of variable occurrences in an expression.
• Logic levels: the number of gate stages between input and output.
• Propagation delay: the time between an input transition and the corresponding valid output transition.
• Power: energy consumed during switching and leakage.
• Area: silicon or circuit-board space.
• Cost: component, manufacturing, testing, and maintenance cost.
• Reliability: sensitivity to noise, hazards, loading, and failure.

A rough first-order estimate for a two-level circuit is:

where t_pd is the worst-case propagation delay and t_AND and t_OR are the delays of the active AND and OR stages. This estimate assumes a simple two-level implementation, similar loading, and negligible interconnect delay. Real devices may require additional terms for inversion, fan-out, wiring, and technology-specific gate delays.

Dynamic CMOS switching power is commonly approximated by:

where α is the activity factor, C_L is switched load capacitance in farads, V_DD is supply voltage in volts, and f is switching frequency in hertz. The units are watts because F·V²·Hz = C/V × V² × 1/s = J/s. This model excludes leakage and short-circuit power.

A simpler expression may reduce gate count but increase fan-out or create an additional logic level. Consequently, minimization should be evaluated against the actual design objective rather than expression length alone.

8. Hazards and Practical Limitations

A static hazard is an unwanted temporary transition caused by unequal propagation delays. In a static-1 hazard, the output should remain 1 but briefly falls to 0. In a static-0 hazard, the output should remain 0 but briefly rises to 1.

For example, the function:

is logically correct, but when A changes while B = C = 1, the two product terms may not switch at exactly the same time. Adding the consensus term BC gives:

The consensus term does not change the steady-state function because XY+X'Z+YZ=XY+X'Z, but it can remove a static-1 hazard in a suitable implementation.

Other practical issues include:

• fan-in limits of physical gates;
• fan-out and signal loading;
• availability of active-low signals;
• glitches caused by reconvergent paths;
• testability and observability;
• timing constraints in synchronous systems;
• use of NAND, NOR, or programmable logic technologies.

A minimized expression should always be verified by truth-table simulation, Boolean reasoning, or hardware testing.

9. Applied Case: Safety Interlock Controller

Background

Consider an illustrative industrial controller for a small motor. The motor may run only when the enable switch E is 1, the guard is closed G = 1, and the emergency stop is not active S = 0. A maintenance key K can be used to test the motor under a controlled procedure. In this scenario, the combinations in which the maintenance key is used while the guard is open are prohibited by operating procedure and may be treated as don’t-cares only if the safety specification explicitly permits that assumption.

Problem

A direct SOP expression based on permitted operating states may contain several minterms. The design team wants fewer gates but must not weaken the emergency-stop requirement.

Analysis and Approach

The primary safety condition is:

If a separately approved maintenance mode is represented by K, the functional expression might be:

Factoring gives:

The factored form shares the guard and emergency-stop conditions and can reduce duplicated logic. However, the maintenance term must be authorized by the safety requirements. It is not acceptable to mark unsafe states as don’t-cares merely to obtain a smaller circuit.

Outcome

The factored circuit may use one inverter for S, one AND function for GS′, and one OR function for E + K, followed by the final AND operation. The exact gate count depends on available multi-input gates and technology. Verification must include normal operation, emergency-stop activation, power-up behavior, and all prohibited states.

Learning Points

1. Functional simplification must respect system requirements.
2. Don’t-care conditions are engineering specifications, not convenient omissions.
3. A smaller circuit is not automatically safer.
4. Safety-related logic requires independent review, simulation, and testing.

10. Best Practices

• Convert the specification to a complete, checked truth table before simplifying.
• State variable ordering clearly when using minterm indices.
• Use Gray-code order in K-maps; ordinary binary order is not valid for adjacency.
• Make groups as large as possible, but cover every required 1 or 0.
• Distinguish required outputs from don’t-care outputs.
• Compare literal count, gate count, logic depth, and fan-in.
• Check for hazards when signals can change asynchronously.
• Map the expression to the actual gate family or programmable device.
• Verify the final implementation independently from the simplification process.
• In safety, medical, or security applications, never assign don’t-care status without documented authorization.

Chapter Summary

Canonical SOP expresses a Boolean function as the OR of minterms corresponding to output 1, while canonical POS expresses it as the AND of maxterms corresponding to output 0. Boolean algebra uses identities such as absorption, distributive laws, and De Morgan’s theorems to transform expressions. Karnaugh maps provide a visual method for grouping adjacent 1s or 0s and eliminating changing variables. Don’t-care conditions may be included selectively to produce larger groups and simpler circuits. The Quine–McCluskey method extends systematic minimization to functions with more variables.

The best implementation is not necessarily the expression with the fewest symbols. Gate count, literals, logic depth, delay, power, fan-out, hazards, reliability, and cost must be considered together. In practical and safety-critical systems, simplification must remain faithful to the specification and must be verified through simulation and testing.

Key Terms

Boolean function: A function whose variables and output take values 0 or 1.

Literal: A variable or its complement.

Product term: An AND combination of literals.

Sum term: An OR combination of literals.

SOP: Sum-of-products form.

POS: Product-of-sums form.

Minterm: A product term that is 1 for exactly one input combination.

Maxterm: A sum term that is 0 for exactly one input combination.

Canonical form: A form in which every term contains every variable.

Karnaugh map: A Gray-code map used for visual Boolean minimization.

Implicant: A term that covers no required 0-cells.

Prime implicant: An implicant that cannot be enlarged further.

Essential prime implicant: A prime implicant covering a required minterm not covered by another prime implicant.

Don’t-care condition: An input combination for which either output value is acceptable.

Consensus term: A redundant algebraic term that may help eliminate hazards.

Propagation delay: Time between an input change and the corresponding output response.

Fan-in: Number of inputs accepted by a gate.

Fan-out: Number of loads driven by a gate output.

Quine–McCluskey method: A tabulation algorithm for Boolean minimization.

Hazard: An unwanted transient caused by unequal signal propagation delays.

Review Questions

Short Answer Questions

1. What is the difference between a minterm and a maxterm?
2. State the two De Morgan laws.
3. Why are Karnaugh-map cells arranged in Gray-code order?
4. What is an essential prime implicant?
5. Define a don’t-care condition.

Long Answer Questions

1. Explain how a truth table is converted into canonical SOP and canonical POS forms.
2. Describe the principal Boolean algebra laws used in logic simplification, with examples.
3. Explain the complete procedure for minimizing a four-variable function using a Karnaugh map.
4. Describe the Quine–McCluskey method and explain why it is useful for larger functions.
5. Discuss why literal count alone is insufficient for evaluating a practical logic circuit.

Analytical / Application Questions

1. Minimize F(A,B,C,D)=Σm(0,1,4,5,8,9,12,13) using a Karnaugh map and state the resulting expression.
2. A controller has required 1s at minterms 3, 7, 11, and 15, with don’t-cares at 1, 5, 9, and 13. Determine a simplified SOP expression and explain how the don’t-cares were used.
3. Compare two implementations of the same function: one has two logic levels and eight literals, while another has three logic levels and five literals. Explain which additional electrical and timing information is needed before selecting an implementation.

Multiple Choice Questions with Answers

Question 1

Which expression is the canonical SOP representation of a function that is 1 at minterms 1 and 6 for variables A, B, and C?

A. A'B'C + ABC'

B. A'BC + AB'C'

C. (A+B+C)(A'+B'+C')

D. A'B'C' + ABC

Correct Answer: A. A'B'C + ABC'

Question 2

In a Karnaugh map, adjacent cells differ in:

A. All variables

B. Exactly one variable

C. Exactly two variables

D. No variables

Correct Answer: B. Exactly one variable

Question 3

What is the simplified form of AB+AB'?

A. A

B. B

C. AB

D. 1

Correct Answer: A. A

Question 4

For SOP minimization, a don’t-care cell may be treated as:

A. Only 0

B. Only 1

C. Either 0 or 1, as useful for simplification

D. Both 0 and 1 simultaneously in the final circuit

Correct Answer: C. Either 0 or 1, as useful for simplification

Question 5

Which group size is not valid in a standard Karnaugh map?

A. 1

B. 2

C. 3

D. 4

Correct Answer: C. 3

Question 6

If F=Σm(1,3,5,7) for variables A, B, and C, the simplified function is:

A. A

B. B

C. C

D. A+B

Correct Answer: C. C

Question 7

The Quine–McCluskey method is primarily used to:

A. Measure propagation delay

B. Tabulate and minimize Boolean functions

C. Generate analog waveforms

D. Calculate transistor doping levels

Correct Answer: B. Tabulate and minimize Boolean functions

Question 8

Which expression is equivalent to (A+B)'?

A. A'+B'

B. AB

C. A'B'

D. A+B

Correct Answer: C. A'B'

Question 9

In the approximation P_dynamic≈αC_LV_DD²f, increasing the supply voltage generally causes dynamic power to:

A. Decrease linearly

B. Remain unchanged

C. Increase approximately with the square of voltage

D. Become zero

Correct Answer: C. Increase approximately with the square of voltage

Question 10

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

A. Temporarily falls to 0

B. Temporarily rises to 1 from 0

C. Remains permanently at 0

D. Changes only during initialization

Correct Answer: A. Temporarily falls to 0