14.4 Boolean function simplification techniques

Boolean function simplification techniques let you take a complex logic expression and reduce it to the simplest form that produces the same output. This matters because simpler expressions translate directly into fewer gates, fewer connections, and cheaper, faster circuits.

This section covers three main approaches: algebraic simplification using Boolean laws, Karnaugh maps for visual simplification, and the Quine-McCluskey method for systematic tabular minimization.

Boolean Algebra Simplification

Fundamental Laws and Theorems

Boolean algebra has its own set of rules, similar to regular algebra but with some key differences. You'll use these laws constantly when simplifying expressions by hand.

• Commutative law: $AB = BA$ and $A + B = B + A$ (order doesn't matter)
• Associative law: $A(BC) = (AB)C$ and $A + (B + C) = (A + B) + C$ (grouping doesn't matter)
• Distributive law: $A(B + C) = AB + AC$ (works just like distributing in normal algebra)
• Identity laws: $A \cdot 1 = A$ and $A + 0 = A$ (ANDing with 1 or ORing with 0 changes nothing)
• Null laws: $A \cdot 0 = 0$ and $A + 1 = 1$
• Complement laws: $A \cdot \bar{A} = 0$ and $A + \bar{A} = 1$ (a variable ANDed with its complement is always 0; ORed is always 1)
• De Morgan's laws: $\overline{A \cdot B} = \bar{A} + \bar{B}$ and $\overline{A + B} = \bar{A} \cdot \bar{B}$

De Morgan's laws are especially useful because they let you convert between AND and OR operations by complementing. If you ever need to implement a circuit using only NAND or only NOR gates, De Morgan's is how you get there.

Redundancy Elimination Techniques

Several theorems let you spot and remove terms that don't actually affect the output.

Absorption law: $A + AB = A$ and $A(A + B) = A$. The intuition here is that if $A$ is already true, the $AB$ term adds nothing new. This is one of the most common simplifications you'll apply.

Idempotent law: $A \cdot A = A$ and $A + A = A$. Duplicating a variable in an AND or OR does nothing.

Consensus theorem: $AB + \bar{A}C + BC = AB + \bar{A}C$. The $BC$ term is redundant because any situation where $BC = 1$ is already covered by one of the other two terms. To see why: if $B$ and $C$ are both 1, then $A$ is either 1 (making $AB = 1$) or 0 (making $\bar{A}C = 1$). Either way, the output is already 1 without $BC$.

Minimal Representations

The goal of simplification is to reach a minimal representation, which uses the fewest literals and terms while producing the same truth table output.

• Minimal Sum of Products (SOP): The expression is written as an OR of AND terms, like $AB + \bar{A}C$.
• Minimal Product of Sums (POS): The expression is written as an AND of OR terms, like $(A + C)(\bar{A} + B)$.

Both forms are valid. Which one you target depends on the circuit you're designing or which form turns out simpler for a given function. Karnaugh maps and the Quine-McCluskey method are the standard tools for finding these minimal forms.

Karnaugh Maps

K-map Representation

A Karnaugh map (K-map) is a visual method for simplifying Boolean expressions. It arranges all possible input combinations in a grid so that adjacent cells differ by exactly one variable. This one-variable-at-a-time arrangement (called Gray code ordering) is what makes the grouping trick work.

The number of cells equals $2^n$, where $n$ is the number of input variables. So a 2-variable function uses a 2×2 grid (4 cells), a 3-variable function uses a 2×4 grid (8 cells), and a 4-variable function uses a 4×4 grid (16 cells). You fill each cell with a 1 or 0 based on the function's output for that input combination.

Simplification Process

Once the K-map is filled in, follow these steps to simplify:

1. Identify all 1-cells (for SOP simplification) or all 0-cells (for POS).
2. Form rectangular groups of adjacent 1-cells. Groups must contain a power-of-2 number of cells: 1, 2, 4, 8, or 16.
3. Make groups as large as possible. A group of 4 eliminates two variables; a group of 2 eliminates one. Bigger groups mean simpler terms.
4. Wrap around edges. The K-map behaves like a torus: the top row is adjacent to the bottom row, and the left column is adjacent to the right column.
5. Cover every 1-cell with at least one group. Overlapping groups are allowed and often necessary.
6. Read off each group as a product term. The variables that stay constant across the entire group appear in the term; variables that change are eliminated.

For example, in a 3-variable K-map, if a group of two cells covers $A=1, B=0, C=0$ and $A=1, B=0, C=1$, the variable $C$ changes while $A$ and $B$ stay constant. That group gives you the term $A\bar{B}$.

Prime Implicants and Essential Prime Implicants

• A prime implicant is a group that cannot be made any larger. It represents a product term that can't be simplified further.
• An essential prime implicant is a prime implicant that covers at least one 1-cell not covered by any other prime implicant. You must include it in your final expression.

To find the minimal expression:

1. Identify all prime implicants on the K-map.
2. Find the essential prime implicants (look for 1-cells covered by only one group).
3. Include all essential prime implicants in your expression.
4. If any 1-cells remain uncovered, select the fewest additional prime implicants needed to cover them.

Quine-McCluskey Method

Tabular Minimization

The Quine-McCluskey method does the same job as a K-map but uses a systematic tabular procedure. K-maps become impractical beyond 4 variables because the visual grouping gets unwieldy. Quine-McCluskey scales to any number of variables and can be programmed on a computer.

The method works with minterms (input combinations where the function outputs 1). Each minterm is written in binary and grouped by the number of 1s in its binary representation.

Finding Prime Implicants

1. List all minterms in binary and sort them into groups by the number of 1s (Group 0 has zero 1s, Group 1 has one 1, etc.).
2. Compare adjacent groups. For each pair of terms from neighboring groups that differ in exactly one bit position, combine them into a new term. Replace the differing bit with a dash ($-$), which means that variable has been eliminated. Check off both original terms.
3. Repeat. Take the newly combined terms and compare them again, combining any that differ in exactly one bit (ignoring dashes, which must be in the same positions).
4. Stop when no more combinations are possible. Any term that was never checked off during the process is a prime implicant.

Prime Implicant Chart

Once you have all prime implicants, build a chart to find the minimal cover:

• Columns represent the original minterms.
• Rows represent the prime implicants.
• Place a checkmark in each cell where a prime implicant covers that minterm.

Minimal Expression Generation

1. Find essential prime implicants. Look for columns with only one checkmark. The prime implicant in that row is essential and must be included.
2. Remove covered minterms. Cross out all columns covered by the essential prime implicants.
3. Cover remaining minterms. If any columns remain, select additional prime implicants to cover them using as few as possible. When multiple choices exist, pick the one that covers the most remaining minterms.
4. Write the final expression. OR together all selected prime implicants to get the minimal SOP expression.

The Quine-McCluskey method always produces a minimal result, which makes it reliable for automated logic minimization tools. For exam problems with 4 or fewer variables, K-maps are usually faster. For anything larger, or when you need a guaranteed systematic approach, Quine-McCluskey is the way to go.