K-Map Simplification — Part 1

Karnaugh Maps, commonly called K-Maps, provide a visual method for simplifying Boolean expressions.

Before learning how to simplify expressions using K-Maps, it is important to understand:

• Minterms
• Maxterms
• Canonical forms
• Sum of Products and Product of Sums
• Conversion from truth tables
• Algebraic expansion into canonical form
• Structure of a Karnaugh Map
• 2-variable K-Maps
• Grouping or looping adjacent cells

These concepts form the foundation of K-Map simplification.

---

Minterm

A minterm is a product (AND) term in which every variable of the Boolean function appears exactly once, either in its complemented or uncomplemented form.

For two variables $x$ and $y$, the possible minterms are:

$$xy,\quad xy',\quad x'y,\quad x'y'$$

There are four possible minterms because two variables can have:

$$2^2 = 4$$

possible combinations.

For three variables $x$, $y$, and $z$, the eight possible minterms are:

$$xyz$$ $$xyz'$$ $$xy'z$$ $$xy'z'$$ $$x'yz$$ $$x'yz'$$ $$x'y'z$$ $$x'y'z'$$

Therefore, for $n$ Boolean variables, the total number of possible minterms is:

$$\boxed{2^n}$$

---

Truth Property of a Minterm

A particular minterm evaluates to 1 for exactly one combination of input values.

For all other input combinations, it evaluates to $0$.

For example:

$$xy'z$$

is equal to $1$ only when:

$$x=1,\qquad y=0,\qquad z=1$$

For every other combination of $x$, $y$, and $z$:

$$xy'z=0$$

This property makes minterms very useful when constructing Boolean expressions directly from truth tables.

---

Minterm Numbering

Minterms are commonly represented using the notation:

$$m_0,m_1,m_2,\ldots$$

The subscript corresponds to the decimal value of the binary input combination.

For three variables $x$, $y$, and $z$:

For example:

$$xy'z=m_5$$

because

$$101_2=5_{10}$$

---

Maxterm

A maxterm is a sum (OR) term in which every variable appears exactly once, either complemented or uncomplemented.

For two variables $x$ and $y$, the possible maxterms are:

$$x+y$$ $$x+y'$$ $$x'+y$$ $$x'+y'$$

For three variables $x$, $y$, and $z$, the eight possible maxterms are:

$$x+y+z$$ $$x+y+z'$$ $$x+y'+z$$ $$x+y'+z'$$ $$x'+y+z$$ $$x'+y+z'$$ $$x'+y'+z$$ $$x'+y'+z'$$

Therefore, for $n$ Boolean variables, the number of possible maxterms is:

$$\boxed{2^n}$$

---

Truth Property of a Maxterm

A particular maxterm evaluates to 0 for exactly one input combination.

For every other combination, it evaluates to $1$.

For example:

$$x+y'+z$$

becomes $0$ only when:

$$x=0,\qquad y=1,\qquad z=0$$

because:

$$0+0+0=0$$

For every other input combination:

$$x+y'+z=1$$

---

Maxterm Numbering

Maxterms are represented as:

$$M_0,M_1,M_2,\ldots$$

For a maxterm, a variable appears:

• uncomplemented when its corresponding input value is $0$,
• complemented when its corresponding input value is $1$.

For three variables:

---

Minterm Expansion

When a Boolean function is written as a sum of minterms, it is called a:

• Minterm expansion
• Canonical Sum of Products
• Standard Sum of Products
• Canonical SOP form
• Disjunctive Normal Form in the canonical Boolean sense

For example:

$$f(x,y)=xy+x'y$$

Another example is:

$$f(x,y,z) = x'y'z+x'yz+xy'z'+xyz$$

Each product term is a minterm because every variable occurs exactly once.

---

Sigma Notation for Minterms

Instead of writing every minterm explicitly, we can use the compact notation:

$$f=\Sigma m(\ldots)$$

For example:

$$f(x,y,z) = x'y'z+x'yz+xy'z'+xyz$$

corresponds to:

$$m_1,\quad m_3,\quad m_4,\quad m_7$$

Therefore:

$$\boxed{ f(x,y,z)=\Sigma m(1,3,4,7) }$$

This notation becomes especially useful when working with K-Maps.

---

Gate Implementation of Canonical SOP

A canonical Sum of Products expression can be implemented directly using AND and OR gates.

Consider:

$$F=A'B+AB'$$

Each minterm is implemented using an AND gate:

$$A'B$$

and

$$AB'$$

The outputs of these AND gates are then connected to an OR gate.

Thus, the general structure is:

$$\text{AND gates} \rightarrow \text{OR gate}$$

If the expression contains $k$ minterms and each minterm is implemented by one AND gate, then a basic two-level implementation contains approximately:

$$k+1$$

main logic gates:

• $k$ AND gates
• $1$ OR gate

excluding any NOT gates required to generate complemented variables.

Canonical expressions are easy to construct but are often not the simplest implementation.

K-Maps help reduce such expressions.

---

Maxterm Expansion

When a Boolean function is written as a product of maxterms, it is called:

• Maxterm expansion
• Canonical Product of Sums
• Standard Product of Sums
• Canonical POS form
• Conjunctive Normal Form in the canonical Boolean sense

For example:

$$f(x,y) = (x+y)(x'+y)$$

For three variables, an expression may look like:

$$f(x,y,z) = (x+y+z) (x+y'+z) (x'+y+z') (x'+y'+z)$$

Each parenthesized term is a maxterm.

---

Pi Notation for Maxterms

Maxterms can be represented compactly using:

$$\Pi M(\ldots)$$

For example:

$$F(x,y,z) = (x+y'+z') (x'+y'+z) (x'+y'+z')$$

corresponds to:

$$M_3,\quad M_6,\quad M_7$$

Therefore:

$$\boxed{ F(x,y,z)=\Pi M(3,6,7) }$$

---

Canonical Form

A Boolean function written as either:

$$\text{Sum of Minterms}$$

or

$$\text{Product of Maxterms}$$

is said to be in canonical form.

Thus, the two important canonical forms are:

$$\boxed{\text{Canonical SOP}}$$

and

$$\boxed{\text{Canonical POS}}$$

---

Complete Minterm Expansion

For $n$ variables, there are:

$$2^n$$

possible minterms.

The sum of all possible minterms is called the complete minterm expansion.

For two variables $x$ and $y$:

$$xy+xy'+x'y+x'y'$$

This expression is always equal to $1$.

Let us verify:

$$xy+xy'+x'y+x'y'$$

Group terms:

$$= x(y+y')+x'(y+y')$$

Using:

$$y+y'=1$$

we get:

$$=x(1)+x'(1)$$

Therefore:

$$=x+x'$$

and:

$$\boxed{1}$$

Hence:

$$xy+xy'+x'y+x'y'=1$$

In general, the sum of all possible minterms of $n$ variables is identically:

$$\boxed{1}$$

---

Complete Maxterm Expansion

Similarly, the product of all possible maxterms of $n$ variables is called the complete maxterm expansion.

For two variables:

$$(x+y)(x+y')(x'+y)(x'+y')$$

This expression evaluates identically to:

$$\boxed{0}$$

Thus:

• Sum of all minterms $\rightarrow 1$
• Product of all maxterms $\rightarrow 0$

---

Expansion of a Boolean Function into Canonical Form

A Boolean function can be converted into canonical form using two common methods:

1. From a truth table
2. Algebraically

---

Canonical Form from a Truth Table

Suppose a truth table describing a Boolean function is given.

The truth table can be used directly to obtain both:

$$\text{Canonical SOP}$$

and:

$$\text{Canonical POS}$$

---

Obtaining the Minterm Expansion

To obtain the sum of minterms:

1. Look at all rows where the output is $1$.
2. Construct a minterm for each such row.
3. OR all those minterms together.

When forming a minterm:

• Input $0$ $\rightarrow$ complemented variable
• Input $1$ $\rightarrow$ uncomplemented variable

---

Obtaining the Maxterm Expansion

To obtain the product of maxterms:

1. Look at all rows where the output is $0$.
2. Construct a maxterm for each such row.
3. AND all those maxterms together.

When forming a maxterm:

• Input $0$ $\rightarrow$ uncomplemented variable
• Input $1$ $\rightarrow$ complemented variable

Notice that this rule is the opposite of the rule used for minterms.

---

Example: Finding Minterm and Maxterm Expansions

Consider the following truth table:

---

Minterm Expansion

The output is $1$ for rows:

$$0,\quad1,\quad2,\quad4,\quad5$$

Therefore:

$$F(X,Y,Z)=\Sigma m(0,1,2,4,5)$$

The corresponding minterms are:

$$m_0=X'Y'Z'$$ $$m_1=X'Y'Z$$ $$m_2=X'YZ'$$ $$m_4=XY'Z'$$ $$m_5=XY'Z$$

Hence:

$$\boxed{ F= X'Y'Z' + X'Y'Z + X'YZ' + XY'Z' + XY'Z }$$

---

Maxterm Expansion

The output is $0$ for rows:

$$3,\quad6,\quad7$$

Therefore:

$$F(X,Y,Z)=\Pi M(3,6,7)$$

The corresponding maxterms are:

$$M_3=X+Y'+Z'$$ $$M_6=X'+Y'+Z$$ $$M_7=X'+Y'+Z'$$

Therefore:

$$\boxed{ F= (X+Y'+Z') (X'+Y'+Z) (X'+Y'+Z') }$$

---

Relationship Between Minterms and Maxterms

For the previous function:

$$F=\Sigma m(0,1,2,4,5)$$

The missing indices are:

$$3,6,7$$

Therefore:

$$F=\Pi M(3,6,7)$$

In general, if:

$$F=\Sigma m(S)$$

then the maxterm indices are the indices not contained in $S$.

For example:

$$F(A,B,C)=\Sigma m(1,2,5,7)$$

Since the possible indices are:

$$0,1,2,3,4,5,6,7$$

the remaining indices are:

$$0,3,4,6$$

Thus:

$$\boxed{ F(A,B,C)=\Pi M(0,3,4,6) }$$

---

Algebraic Method for Canonical Expansion

Canonical forms can also be obtained algebraically.

For a canonical SOP expression, every product term must contain all variables.

If a variable is missing, use the complement law:

$$x+x'=1$$

For a canonical POS expression, every sum term must contain all variables.

If a variable is missing, use:

$$xx'=0$$

along with the Boolean identity:

$$X+YZ=(X+Y)(X+Z)$$

---

Example: Convert to Sum of Minterms

Express:

$$f(x,y,z)=x+y'z$$

as a sum of minterms.

The function contains three variables:

$$x,\quad y,\quad z$$

---

Expanding the Term $x$

The term $x$ is missing both $y$ and $z$.

Introduce $y$ using:

$$y+y'=1$$

Therefore:

$$x=x(y+y')$$ $$=xy+xy'$$

Both terms are still missing $z$.

Introduce $z$:

$$xy=xy(z+z')$$

Therefore:

$$xy=xyz+xyz'$$

Similarly:

$$xy'=xy'(z+z')$$

Hence:

$$xy'=xy'z+xy'z'$$

Thus:

$$x=xyz+xyz'+xy'z+xy'z'$$

---

Expanding the Term $y'z$

The term:

$$y'z$$

is missing $x$.

Using:

$$x+x'=1$$

we obtain:

$$y'z=y'z(x+x')$$

Therefore:

$$y'z=xy'z+x'y'z$$

---

Combining the Terms

Thus:

$$f=x+y'z$$

becomes:

$$f= xyz+xyz'+xy'z+xy'z'+xy'z+x'y'z$$

The term $xy'z$ appears twice.

Using the idempotent law:

$$A+A=A$$

we get:

$$\boxed{ f= xyz+xyz'+xy'z+xy'z'+x'y'z }$$

The corresponding minterm indices are:

$$7,\quad6,\quad5,\quad4,\quad1$$

Therefore:

$$\boxed{ f(x,y,z)=\Sigma m(1,4,5,6,7) }$$

---

Example: Convert to Product of Maxterms

Consider:

$$f(a,b,c)=ab+a'c$$

We want to express it as a canonical Product of Sums.

First convert the expression into POS form.

Using the Boolean identity:

$$XY+Z=(X+Z)(Y+Z)$$

we obtain:

$$ab+a'c$$

One convenient factorization is:

$$ab+a'c = (a'+b)(a+c)(b+c)$$

Now each sum term must contain all three variables.

---

Expanding $a'+b$

The variable $c$ is missing.

Using:

$$cc'=0$$

we may write:

$$a'+b = a'+b+cc'$$

Using:

$$X+YZ=(X+Y)(X+Z)$$

we obtain:

$$a'+b = (a'+b+c)(a'+b+c')$$

---

Expanding $a+c$

The variable $b$ is missing:

$$a+c = a+c+bb'$$

Therefore:

$$a+c = (a+b+c)(a+b'+c)$$

---

Expanding $b+c$

The variable $a$ is missing:

$$b+c = b+c+aa'$$

Therefore:

$$b+c = (a+b+c)(a'+b+c)$$

---

Combining the Maxterms

Thus:

$$f(a,b,c) = (a'+b+c) (a'+b+c') (a+b+c) (a+b'+c) (a+b+c) (a'+b+c)$$

Using the idempotent law:

$$XX=X$$

duplicate factors can be removed.

Hence:

$$\boxed{ f(a,b,c) = (a+b+c) (a+b'+c) (a'+b+c) (a'+b+c') }$$

In maxterm notation:

$$\boxed{ f(a,b,c)=\Pi M(0,2,4,5) }$$

---

Introduction to Karnaugh Maps

Canonical forms are systematic, but they are often not minimal.

For example, a Boolean function may contain several minterms and require many gates even though an equivalent expression with fewer literals and gates exists.

The Karnaugh Map, or K-Map, provides a graphical technique for simplifying Boolean expressions.

It is especially convenient for functions involving:

• 2 variables
• 3 variables
• 4 variables

K-Maps can also be extended to 5 or 6 variables, but the map becomes increasingly difficult to manage manually.

---

What Is a K-Map?

A Karnaugh Map is a diagram made of cells or squares.

If a Boolean function contains $n$ variables, its K-Map contains:

$$\boxed{2^n}$$

cells.

Therefore:

Each cell represents exactly one minterm.

For SOP simplification:

• Write $1$ in cells whose minterms are present.
• Write $0$ in cells whose minterms are absent or generally we keep it empty.

Thus, a K-Map is essentially a two-dimensional rearrangement of a truth table.

Its special arrangement makes simplification easier because logically adjacent minterms are placed next to one another.

---

2-Variable K-Map

For two variables $A$ and $B$:

$$2^2=4$$

Therefore, the K-Map contains four cells.

A common representation is:

Loading image…

Equivalently, using minterm numbers:

where:

$$m_0=A'B'$$ $$m_1=A'B$$ $$m_2=AB'$$ $$m_3=AB$$

---

Adjacent Cells in a K-Map

Two cells are called adjacent when their corresponding minterms differ in exactly one variable.

For example:

$$A'B'$$

and:

$$AB'$$

are adjacent because only $A$ changes:

$$A' \rightarrow A$$

while $B'$ remains unchanged.

Similarly:

$$A'B'$$

and:

$$A'B$$

are adjacent because only $B$ changes.

However:

$$A'B'$$

and:

$$AB$$

are not adjacent, because both variables change.

---

Why Adjacent Terms Simplify

Consider:

$$A'B'+AB'$$

Factor out $B'$:

$$=B'(A'+A)$$

Using:

$$A'+A=1$$

we get:

$$=B'(1)$$

Therefore:

$$\boxed{A'B'+AB'=B'}$$

The variable $A$ disappears because it occurs once complemented and once uncomplemented.

This is the central idea behind K-Map simplification.

---

Looping in a K-Map

The process of combining adjacent cells containing $1$s is called grouping or looping.

When two adjacent minterms are grouped, the variable that changes between them is eliminated.

For example:

$$AB'+A'B'$$

becomes:

$$B'(A+A')$$

Therefore:

$$\boxed{B'}$$

A K-Map allows us to recognize such simplifications visually rather than carrying out Boolean algebra every time.

---

Example 1

Simplify:

$$F=AB'+A'B'$$

The two minterms are:

$$AB'$$

and:

$$A'B'$$

The K-Map is:

Loading image…

The two $1$s are vertically adjacent.

Inside the group:

• $A$ changes from $0$ to $1$.
• $B$ remains $0$.

Therefore $A$ is eliminated.

Since $B=0$, the remaining literal is:

$$B'$$

Hence:

$$\boxed{F=B'}$$

Algebraically:

$$AB'+A'B'$$ $$=B'(A+A')$$ $$=B'(1)$$

Therefore:

$$\boxed{F=B'}$$

---

Example 2

Simplify:

$$F=AB'+A'B$$

The K-Map is:

The two $1$s are diagonally opposite.

Diagonal cells are not adjacent in a K-Map.

Therefore, no grouping is possible.

Hence the expression cannot be simplified further using ordinary SOP grouping:

$$\boxed{ F=AB'+A'B }$$

This expression is also the XOR function:

$$\boxed{ F=A\oplus B }$$

---

Example 3

Simplify:

$$F=AB'+A'B+A'B'$$

Place the corresponding $1$s in the K-Map and group the adjacent cells:

Loading image…

There are three $1$s.

We can form two groups.

---

First Group

Group:

$$A'B'$$

and:

$$AB'$$

Here:

• $A$ changes.
• $B'$ remains constant.

Therefore:

$$A'B'+AB'=B'$$

---

Second Group

Group:

$$A'B'$$

and:

$$A'B$$

Here:

• $B$ changes.
• $A'$ remains constant.

Therefore:

$$A'B'+A'B=A'$$

Notice that the cell corresponding to:

$$A'B'$$

is used in both groups.

This is perfectly valid.

A K-Map cell containing $1$ may be included in more than one group when doing so produces a simpler expression.

Therefore:

$$\boxed{ F=A'+B' }$$

---

Algebraic Verification

Starting with:

$$F=AB'+A'B+A'B'$$

Group the last two terms:

$$F=AB'+A'(B+B')$$

Since:

$$B+B'=1$$

we obtain:

$$F=AB'+A'$$

Now use the Boolean identity:

$$X+X'Y=X+Y$$

Taking:

$$X=A'$$

and:

$$Y=B'$$

we get:

$$A'+AB'=A'+B'$$

Therefore:

$$\boxed{ F=A'+B' }$$

which agrees with the K-Map result.

---

Important Observation About Overlapping Groups

K-Map groups are allowed to overlap.

For example, in the previous expression:

$$AB'+A'B+A'B'$$

the minterm:

$$A'B'$$

participates in two groups.

This is allowed because the objective is not simply to cover every $1$ exactly once.

The objective is to obtain the simplest Boolean expression.

Therefore, a cell may be reused whenever it helps create a larger or more useful group.

---

Basic Idea Behind K-Map Simplification

Whenever adjacent minterms are combined, one or more variables disappear.

For example:

$$AB+A'B=B$$

because $A$ changes while $B$ remains constant.

Similarly:

$$AB+AB'=A$$

because $B$ changes while $A$ remains constant.

Thus:

$$\boxed{ \text{Changing variable disappears} }$$

while:

$$\boxed{ \text{Constant variable remains} }$$

This simple principle is the foundation of Karnaugh Map simplification.

---

Minterm and Maxterm Rules at a Glance

---

Quick Example of the Complementary Relationship

Suppose:

$$F(A,B,C)=\Sigma m(0,2,3,6)$$

The complete set of indices is:

$$\{0,1,2,3,4,5,6,7\}$$

The indices not present in the minterm expansion are:

$$1,4,5,7$$

Therefore:

$$\boxed{ F(A,B,C)=\Pi M(1,4,5,7) }$$

---

Summary

A minterm is an AND term containing every variable exactly once:

$$A'BC$$

and a minterm becomes $1$ for exactly one input combination.

A maxterm is an OR term containing every variable exactly once:

$$A+B'+C$$

and a maxterm becomes $0$ for exactly one input combination.

For $n$ variables:

$$\boxed{\text{Number of minterms}=2^n}$$

and:

$$\boxed{\text{Number of maxterms}=2^n}$$

A Boolean function written as a sum of minterms is expressed as:

$$\boxed{ F=\Sigma m(\ldots) }$$

while a function written as a product of maxterms is expressed as:

$$\boxed{ F=\Pi M(\ldots) }$$

A Karnaugh Map contains:

$$\boxed{2^n}$$

cells for $n$ variables.

Each cell represents one minterm.

K-Map simplification is based on grouping adjacent cells containing $1$s so that changing variables are eliminated.

For example:

$$A'B'+AB'=B'$$

and:

$$A'B'+A'B=A'$$

The main principle is:

$$\boxed{ \text{Group adjacent terms and eliminate the variable that changes} }$$

This idea becomes even more powerful when we move to 3-variable and 4-variable K-Maps, where larger groups of $2$, $4$, $8$, or more cells can eliminate multiple variables simultaneously.