Information security department Logic Design
1st class Dr. Rasim Azeez
Simplify the Boolean Function using Karnaugh Map
(K-Map)
The second method that used to simplify the Boolean function is the
Karnaugh map. K-map basically deals with the technique of inserting the
values of the output variable in cells within a rectangle or square grid
according to a definite pattern. The number of cells in the K-map is
determined by the number of input variables and is mathematically
expressed as two raised to the power of the number of input variables, i.e.,
2n, where the number of input variables is n.
Thus, to simplify a logical expression with two inputs, we require a K-
map with (22 = 4) cells. A four-input logical expression would lead to a
(24 = 16) celled-K-map, and so on.
Advantages of K-Maps
1- The K-map simplification technique is simpler and less error-prone
compared to the method of solving the logical expressions using
Boolean laws.
2- It prevents the need to remember each and every Boolean algebraic
theorem.
3- It involves fewer steps than the algebraic minimization technique to
arrive at a simplified expression.
4- K-map simplification technique always results in minimum
expression if carried out properly.
Disadvantages of K-Maps
1- As the number of variables in the logical expression increases, the
K-map simplification process becomes complicated.
2- The minimum logical expression arrived by using the K-map
simplification procedure may or may not be unique depending on
the choices made while forming the groups
57
Information security department Logic Design
1st class Dr. Rasim Azeez
K-mapping & Minimization Steps
Step 1: generate K-map based on the number of input variables n
Step 2: group all adjacent 1s without including any 0s. All groups must be
rectangular and contain a “power-of-2” number of 1s 1, 2, 4, 8, 16, 32, …
Step 3: define product terms using variables common to all minterms in
group
Step 4: sum all essential groups plus a minimal set of remaining groups to
obtain a minimum SOP.
1- Two variables K-Map
Number of input variables are 2
Hence the number of squares = 2n = 22 = 4
Inputs Decimal Minterms Output
A B equivalent F
0 0 0 m0 ̅̅
0 1 1 m1 ̅
1 0 2 m2 ̅
1 1 3 m3
And K-Map of two variables is:
̅
0 1
̅ 0 1
0
2 3
58
Information security department Logic Design
1st class Dr. Rasim Azeez
Example: simplify the Boolean expression by using K-Map
̅
Solution:
Number of input variables are 2
Hence the number of squares = 2n = 22 = 4
̅
0 1
̅ 0 1
0 0 1
2 3
1 0 1
Example: simplify the Boolean expression by using K-Map
∑
Solution:
Number of input variables are 2
Hence the number of squares = 2n = 22 = 4
̅
0 1
̅ 0 1
0 1 0
2 3
1 1 1
59
Information security department Logic Design
1st class Dr. Rasim Azeez
Example: simplify the Boolean expression by using K-Map
̅ ̅̅
Solution:
Number of input variables are 2
Hence the number of squares = 2n = 22 = 4
̅
0 1
̅ 0 1
0 1 1
2 3
1 0 0
Example: simplify the Boolean expression by using K-Map
∑
Solution:
Number of input variables are 2
Hence the number of squares = 2n = 22 = 4
̅
0 1
̅ 0 1
0 1 0
2 3
1 0 1
∑ ̅̅
5:
Information security department Logic Design
1st class Dr. Rasim Azeez
2- Three Variables K-Map
Number of input variables are 3
Hence the number of squares = 2n = 23 = 8
The truth table is
Inputs Decimal Minterms Output
A B C equivalent F
0 0 0 0 m0 ̅ ̅̅
0 0 1 1 m1 ̅̅
0 1 0 2 m2 ̅ ̅
0 1 1 3 m3 ̅
1 0 0 4 m4 ̅̅
1 0 1 5 m5 ̅
1 1 0 6 m6 ̅
1 1 1 7 m7
And the K-Map of three variables is:
̅̅ ̅ ̅
00 01 11 10
̅ 0 1 3 2
4 5 7 6
5;
Information security department Logic Design
1st class Dr. Rasim Azeez
Example: simplify the Boolean expression by using K-Map
̅ ̅̅ ̅ ̅ ̅
Solution:
Number of input variables are 3
Hence the number of squares = 2n = 23 = 8
̅̅ ̅ ̅
00 01 11 10
̅ 0 1 3 2
0 1 0 1 1
4 5 7 6
1 0 0 0 0
̅̅ ̅
Example: simplify the Boolean expression by using K-Map
∑
Solution:
Number of input variables are 3
Hence the number of squares = 2n = 23 = 8
̅̅ ̅ ̅
00 01 11 10
̅ 0 1 3 2
0 1 0 1 0
4 5 7 6
1 0 0 1 1
̅ ̅̅
64
Information security department Logic Design
1st class Dr. Rasim Azeez
3- Four Variables K-map
Number of input variables are 4
Hence the number of squares = 2n = 24 = 16
The truth table is
Inputs Decimal Minterms Output
A B C D equivalent F
0 0 0 0 0 m0 ̅ ̅̅ ̅
0 0 0 1 1 m1 ̅ ̅̅
0 0 1 0 2 m2 ̅̅ ̅
0 0 1 1 3 m3 ̅̅
0 1 0 0 4 m4 ̅ ̅̅
0 1 0 1 5 m5 ̅ ̅
0 1 1 0 6 m6 ̅ ̅
0 1 1 1 7 m7 ̅
1 0 0 0 8 m8 ̅̅ ̅
1 0 0 1 9 m9 ̅̅
1 0 1 0 10 m10 ̅ ̅
1 0 1 1 11 m11 ̅
1 1 0 0 12 m12 ̅̅
1 1 0 1 13 m13 ̅
1 1 1 0 14 m14 ̅
1 1 1 1 15 m15
And the K-Map of four variables is:
̅̅ ̅ ̅
00 01 11 10
̅̅ 0 1 3 2
00
̅ 4 5 7 6
01
12 13 15 14
11
̅ 8 9 11 10
10
64
Information security department Logic Design
1st class Dr. Rasim Azeez
Example: simplify the Boolean expression by using K-Map
̅ ̅̅ ̅ ̅ ̅ ̅ ̅̅̅ ̅ ̅ ̅ ̅
Solution: Number of input variables are 4
Hence the number of squares = 2n = 24 = 16
̅̅ ̅ ̅
00 01 11 10
̅̅ 0 1 3 2
00 1 0 0 1
̅ 4 5 7 6
𝑭 𝑨𝑩𝑪𝑫 ̅𝑫
𝑩 ̅ ̅ 𝑩𝑪𝑫
𝑨 ̅𝑫
𝑨𝑩𝑪
01 0 0 1 0
12 13 15 14
11 0 1 0 0
̅ 8 9 11 10
10 1 0 0 1
Example: simplify the Boolean expression by using K-Map
∑
Solution: Number of input variables are 4
Hence the number of squares = 2n = 24 = 16
̅̅ ̅ ̅
00 01 11 10
̅̅ 0 1 3 2
00 1 0 0 1
̅ 4 5 7 6
01 1 0 0 1 ̅
𝑭 𝑨𝑩𝑪𝑫 𝑫 𝑨𝑩𝑪
12 13 15 14
11 1 0 1 1
̅ 8 9 11 10
10 1 0 0 1
64
Information security department Logic Design
1st class Dr. Rasim Azeez
K-Map with Don’t Care Conditions
In certain cases some of the minterms may never occur or it may
not matter what happens if they do
– In such cases we fill in the Karnaugh map with an X that meaning
don't care
– When minimizing an X is like a "joker"
• X can be 0 or 1 - whatever helps best with the minimization
Example: simplify the Boolean expression by using K-Map
∑ ∑
Solution: Number of input variables are 4
Hence the number of squares = 2n = 24 = 16
̅̅ ̅ ̅
00 01 11 10
̅̅ 0 1 3 2
00 0 X 1 0
̅ 4 5 7 6
01 0 X 1 0
12 13 15 14
11 X 0 0 X
̅ 8 9 11 10
10 0 1 1 0
̅ ̅
65