Introduction Karnaugh Map

Minimization of Circuits

Dr. E. Mujuni

April 24, 2025

Introduction Karnaugh Map

Contents

1 Introduction

2 Karnaugh Map
Introduction Karnaugh Map

Contents

1 Introduction

2 Karnaugh Map
Introduction Karnaugh Map

Introduction
Introduction Karnaugh Map

Introduction

The process of designing a combination circuit start with the truth

table specifying the output for each input value. We usually use the
standard SOP to find set of the logic gates that will implement this
circuit.
Consider the following truth table

x y z f (x, y , z)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
Table 1.9
Introduction Karnaugh Map

Introduction

The process of designing a combination circuit start with the truth

table specifying the output for each input value. We usually use the
standard SOP to find set of the logic gates that will implement this
circuit.
Consider the following truth table

x y z f (x, y , z)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
Table 1.9
Introduction Karnaugh Map

Introduction

From the truth table we get f (x, y, z) = xy z + xyz. Its logic circuit is
given below:
Introduction Karnaugh Map

Minimization of Circuits

However, we simplify f (x, y, z) as follows:

f (x, y , z) = xy z + xyz
= xzy + xy y (commutative)
= xz(y + y ) (Distributive)
= xz (Inverse)

Therefore, f (x, y , z) = xz, and the corresponding circuit is

Introduction Karnaugh Map

Minimization of Circuits

However, we simplify f (x, y, z) as follows:

f (x, y , z) = xy z + xyz
= xzy + xy y (commutative)
= xz(y + y ) (Distributive)
= xz (Inverse)

Therefore, f (x, y , z) = xz, and the corresponding circuit is

Introduction Karnaugh Map

Minimization of Circuits

However, we simplify f (x, y, z) as follows:

f (x, y , z) = xy z + xyz
= xzy + xy y (commutative)
= xz(y + y ) (Distributive)
= xz (Inverse)

Therefore, f (x, y , z) = xz, and the corresponding circuit is

Introduction Karnaugh Map

Introduction

Since the efficiency of a combination circuit depends on the

number and arrangement of its gates, we need to find a way to
minimize combination circuits.

There are various methods for minimizing circuits.

In this section we present the Karnaugh Map method

Introduction Karnaugh Map

Introduction

Since the efficiency of a combination circuit depends on the

number and arrangement of its gates, we need to find a way to
minimize combination circuits.

There are various methods for minimizing circuits.

In this section we present the Karnaugh Map method

Introduction Karnaugh Map

Introduction

Since the efficiency of a combination circuit depends on the

number and arrangement of its gates, we need to find a way to
minimize combination circuits.

There are various methods for minimizing circuits.

In this section we present the Karnaugh Map method

Introduction Karnaugh Map

Karnaugh Map
Introduction Karnaugh Map

Karnaugh Map

The Karnaugh map method finds a minimal sum of product

expression of a given Boolean expression which is in standard SOP.

The method is based on the identity : xy + xy = x (proof left as an

exercise)

In particular, if two minterms differ in exactly one literal, the Boolean

expression of those two minterm can be replaced by just one term.

Example
xyz + xy z = xy and xyzw + xyzw = xyz
are adjacent
Introduction Karnaugh Map

Karnaugh Map

The Karnaugh map method finds a minimal sum of product

expression of a given Boolean expression which is in standard SOP.

The method is based on the identity : xy + xy = x (proof left as an

exercise)

In particular, if two minterms differ in exactly one literal, the Boolean

expression of those two minterm can be replaced by just one term.

Example
xyz + xy z = xy and xyzw + xyzw = xyz
are adjacent
Introduction Karnaugh Map

Karnaugh Map

The Karnaugh map method finds a minimal sum of product

expression of a given Boolean expression which is in standard SOP.

The method is based on the identity : xy + xy = x (proof left as an

exercise)

In particular, if two minterms differ in exactly one literal, the Boolean

expression of those two minterm can be replaced by just one term.

Example
xyz + xy z = xy and xyzw + xyzw = xyz
are adjacent
Introduction Karnaugh Map

Karnaugh Map

The Karnaugh map method finds a minimal sum of product

expression of a given Boolean expression which is in standard SOP.

The method is based on the identity : xy + xy = x (proof left as an

exercise)

In particular, if two minterms differ in exactly one literal, the Boolean

expression of those two minterm can be replaced by just one term.

Example
xyz + xy z = xy and xyzw + xyzw = xyz
are adjacent
Introduction Karnaugh Map

Karnaugh Map

When two minterms differ in exactly one literal, they are said to be
adjacent.

To construct a Karnaught map for a Boolean expression which is

involving n variables, we first construct a rectangular (block/square)
grid of 2n squares; one square for each possible minterm in n
variables.

We label each square in the grid with the minterms in such a way that
if two square are adjacent, then the minterm that labels them re
adjacent.
Introduction Karnaugh Map

Karnaugh Map

When two minterms differ in exactly one literal, they are said to be
adjacent.

To construct a Karnaught map for a Boolean expression which is

involving n variables, we first construct a rectangular (block/square)
grid of 2n squares; one square for each possible minterm in n
variables.

We label each square in the grid with the minterms in such a way that
if two square are adjacent, then the minterm that labels them re
adjacent.
Introduction Karnaugh Map

Karnaugh Map

When two minterms differ in exactly one literal, they are said to be
adjacent.

To construct a Karnaught map for a Boolean expression which is

involving n variables, we first construct a rectangular (block/square)
grid of 2n squares; one square for each possible minterm in n
variables.

We label each square in the grid with the minterms in such a way that
if two square are adjacent, then the minterm that labels them re
adjacent.
Introduction Karnaugh Map

Karnaugh Map

Rectangular blocks for Boolean expressions involving 2, 3 and 4

variables are given below
x x
y xy xy
y xy xy
Table 1.10: Rectangular Block for n = 2
Introduction Karnaugh Map

Karnaugh Map

Rectangular blocks for Boolean expressions involving 2, 3 and 4

variables are given below
x x
y xy xy
y xy xy
Table 1.10: Rectangular Block for n = 2
Introduction Karnaugh Map

xy xy xy xy
z xyz x yz xyz xy z
z xyz x yz xyz xy z
Table 1.11: Rectangular Block for n = 3
Introduction Karnaugh Map

Karnaugh Map

xy xy xy xy
zw xyzw x yzw x y zw xy zw
zw xy z w x yz w xyzw xy z w
zw xy z w x yz w xyzw xy z w
zw xyzw x yzw x y zw xy zw
Table 1.12: Rectangular Block for n = 4
Introduction Karnaugh Map

Karnaugh Map

To find a Karnaugh map for a Boolean expression which involves n

variables.

we just add 1 in each square of the grid that is labeled by minterm

appearing in the standard SOP of the function.
Introduction Karnaugh Map

Karnaugh Map

To find a Karnaugh map for a Boolean expression which involves n

variables.

we just add 1 in each square of the grid that is labeled by minterm

appearing in the standard SOP of the function.
Introduction Karnaugh Map

Example
Find the Kargaugh map for f (x, y ) = xy + x y
Solution
x x
y 1
y 1
Introduction Karnaugh Map

f (x, y, z, w) = xyzw + xy zw + xy z w + xy z w + x y zw Solution

xy xy xy xy
zw 1 1 1
zw
zw
zw 1 1
Introduction Karnaugh Map

Algorithm

The following seven steps consitutes an algorithm by which we use in

the Karnaugh map to minimize circuits.

Algorithm

Step 1 Find the Karnaugh map for the expression

Step 2 Circle all isolated 1’s
Step 3 Find 1’s that are adjacent to exactly one other 1. Encircle each
such 1 together with its unique neighbour 1.
Step 4 Find all 1’s that are in exactly one rectangle block of four adjacent
1’s. Encricle such 1’s together with other 1’s in its block, only if at
leas one member of the block has not been included in any circle.
Introduction Karnaugh Map

Algorithm

The following seven steps consitutes an algorithm by which we use in

the Karnaugh map to minimize circuits.

Algorithm

Step 1 Find the Karnaugh map for the expression

Step 2 Circle all isolated 1’s
Step 3 Find 1’s that are adjacent to exactly one other 1. Encircle each
such 1 together with its unique neighbour 1.
Step 4 Find all 1’s that are in exactly one rectangle block of four adjacent
1’s. Encricle such 1’s together with other 1’s in its block, only if at
leas one member of the block has not been included in any circle.
Introduction Karnaugh Map

Algorithm

The following seven steps consitutes an algorithm by which we use in

the Karnaugh map to minimize circuits.

Algorithm

Step 1 Find the Karnaugh map for the expression

Step 2 Circle all isolated 1’s
Step 3 Find 1’s that are adjacent to exactly one other 1. Encircle each
such 1 together with its unique neighbour 1.
Step 4 Find all 1’s that are in exactly one rectangle block of four adjacent
1’s. Encricle such 1’s together with other 1’s in its block, only if at
leas one member of the block has not been included in any circle.
Introduction Karnaugh Map

Algorithm

The following seven steps consitutes an algorithm by which we use in

the Karnaugh map to minimize circuits.

Algorithm

Step 1 Find the Karnaugh map for the expression

Step 2 Circle all isolated 1’s
Step 3 Find 1’s that are adjacent to exactly one other 1. Encircle each
such 1 together with its unique neighbour 1.
Step 4 Find all 1’s that are in exactly one rectangle block of four adjacent
1’s. Encricle such 1’s together with other 1’s in its block, only if at
leas one member of the block has not been included in any circle.
Introduction Karnaugh Map

Algorithm

Algorithm

Step 5 Find all 1’s that belong to exactly one rectangular block of eight
1’s. Encircle such 1’s together with other 1’s in its block of eight,
only if at one memberof that block has not arleady appeared in
any circle.
Step 6 Encirle ech remaining 1 together with the largest possible
rectangle of two, four or eight 1’s to which it belong. Stop as soos
as each 1 has appeared in some circle.
Step 7 From each circle appearing in the map, after Step 1-6 has
completed, form the term that is a product of literals common to
all minterm.
Step 8 Take a sum of the products obtained in Step 7.
Introduction Karnaugh Map

Algorithm

Algorithm

Step 5 Find all 1’s that belong to exactly one rectangular block of eight
1’s. Encircle such 1’s together with other 1’s in its block of eight,
only if at one memberof that block has not arleady appeared in
any circle.
Step 6 Encirle ech remaining 1 together with the largest possible
rectangle of two, four or eight 1’s to which it belong. Stop as soos
as each 1 has appeared in some circle.
Step 7 From each circle appearing in the map, after Step 1-6 has
completed, form the term that is a product of literals common to
all minterm.
Step 8 Take a sum of the products obtained in Step 7.
Introduction Karnaugh Map

Algorithm

Algorithm

Step 5 Find all 1’s that belong to exactly one rectangular block of eight
1’s. Encircle such 1’s together with other 1’s in its block of eight,
only if at one memberof that block has not arleady appeared in
any circle.
Step 6 Encirle ech remaining 1 together with the largest possible
rectangle of two, four or eight 1’s to which it belong. Stop as soos
as each 1 has appeared in some circle.
Step 7 From each circle appearing in the map, after Step 1-6 has
completed, form the term that is a product of literals common to
all minterm.
Step 8 Take a sum of the products obtained in Step 7.
Introduction Karnaugh Map

Algorithm

Algorithm

Step 5 Find all 1’s that belong to exactly one rectangular block of eight
1’s. Encircle such 1’s together with other 1’s in its block of eight,
only if at one memberof that block has not arleady appeared in
any circle.
Step 6 Encirle ech remaining 1 together with the largest possible
rectangle of two, four or eight 1’s to which it belong. Stop as soos
as each 1 has appeared in some circle.
Step 7 From each circle appearing in the map, after Step 1-6 has
completed, form the term that is a product of literals common to
all minterm.
Step 8 Take a sum of the products obtained in Step 7.
Introduction Karnaugh Map
Introduction Karnaugh Map

Example
Use the Karnaugh Map method to simplify
1 f (x, y, z) = x yz + xy z + xy z + x y z
Solution
First we construct the Karnaugh Map for f (x, y , z)

From Step 1; we circle the isolated 1 in the first row second column.
From Step 2; we only encircle 1 in second row and third row with its
unique neighbour/adjacent (2nd row, 4th column).
From Step 2, again, we encricle 1 in the 1st row 4th column with its
unique neighbour (2nd row, 4th column).
After step 1 & 2 all 1’s have been circled. So we have nothing to do
with the remaining stjpg. From each cicle we form the product of
literals common to that circle, that is x yz, y z and xy
Introduction Karnaugh Map

Exercise
Use Karnagh maps to minimize the following boolean functions
1 xyz + xy z + x yz + x y z

2 xyz + xyz + xy z + xy z + x yz + x y z + x y z

3 wxyz + wxyz + wxy z + wx yz + wx y z + wx y z + w xy z +

w x yz + w x y z

4 wxy z + wxy z + wx yz + wx y z + wx y z + w xy z +
w xyz + w xy z + w xy z + w xy z + w x y z + w x y z .