K-Map Introduction, Grouping Rules, Solved Examples

Karnaugh Map Introduction, Grouping Rules With Solved Examples 

 K-Map is a graphical illustration of a logic circuit in other words it is a graphical illustration of a truth table. 

Learning Objectives:

• Learn about Karnaugh Map, its grouping rules, cell adjacency rules

• Generate K-Map from the truth table

• Generate K-Map from a standard SOP/POS expression

• Generate K-Map from a non-standard SOP/POS expression

What is a K-Map?

It is a graphical method for simplifying Boolean expressions. It is a map containing boxes called "cells". The values in these cells represent a function in standard form (SOP or POS). For ‘n’ variables there are 2n cells. Each cell is denoted by a binary number or its equivalent decimal number. It is similar to the truth table in a way that both methods contain the output of a logic circuit for all possible input combinations. 

1. The truth table has rows and columns, each row has a different input combination. The K-Map has an array of cells, each cell is represented by a different combination of input variables.

2. With the help of the truth table, a standard SOP/POS expression is obtained. Each term in standard SOP/POS contains all the variables in the domain. The K-map is used for simplified SOP/POS expression. If applied properly, no need for further simplification.

3. The values entered in the truth table are curated in ascending order. The counting is in binary number format (not necessary but mostly it is in binary format). While in this method, values are curated in gray code format.

Understanding the principle of K-Map? How to develop a K-Map (Cell Adjacency rules):

Any two adjacent squares on the map differ by only a single variable. If a variable is primed in one cell, it is unprimed in the adjacent cell.

The two minterms are arranged in a way that there is a single variable change in binary numbers. When moving along any row or any column, one and only one variable changes in the product term. Look at the figure below:

How to construct a Karnaugh Map | K-Map?

There are many ways to describe a digital logic system.

• The logical expression

• The schematic

• The truth table 

• The Karnaugh Map

We can analyze the logic system easily if any of the above-mentioned entities is given. The K- Map can easily be implemented with the help of a logic expression either in standard or non-standard form. It is developed either with a schematic diagram or with the help of a truth table.

One Variable Map:

Consider a function with only one variable A. Since n = 1(number of variables), the number of possible cells in a map will be 2 (2n = 21 = 2). Each minterm is adjacent to only one minterm.

Two-Variable Maps

Consider a function with only one variable A and B. Since n = 2(number of variables), the number of possible cells in a map will be 4 (2n = 22 = 4). Each minterm is adjacent to two minterms.

Three Variable Maps

Consider a function with only one variable A, B and C. Since n = 3(number of variables), the number of possible cells in a map will be 8 (2n = 23 = 8). Each minterm is adjacent to three other minterms.

Four Variable Maps

Consider a function with only one variable A, B, C and D. Since n = 4(number of variables), the number of possible cells in a map will be 16 (2n = 24 = 16). Each minterm is adjacent to four other minterms.

Five Variable Maps

Consider a function with only one variable A, B, C, D and E. Since n = 5(number of variables), the number of possible cells in a map will be 2 (2n = 25 = 32). The 32 (4x8 map) cells map is quite large. Instead of a single larger map, it is constructed from two 4-variable K-Map. 

For cell adjacency, place a map on the top of the other.

Examples:

Example: F(A, B, C) = ∑ (0,2,3,7)

Have a look at group 1:

Variables A and C are non-changing while B changes. In one cell it is primed and in the other cell, it is unprimed. 

\[=\bar A \bar B \bar C + \bar A B \bar C\]

\[=\bar A \bar C (B + \bar B)\]

\[=\bar A \bar C\]

Look at group 2:

Variables B and C are non-changing, while A changes. In one cell it is primed and in the other cell, it is unprimed.

\[=\bar A B C +  A B C\]

\[=B C (A + \bar A)\]

\[=BC\]

Look at group 3:

Variables A and B are non-changing, while C changes. In one cell it is primed and in the other cell, it is unprimed.

\[=\bar A B \bar C + \bar A B C\]

\[=\bar A B(C + \bar C)\]

\[=\bar A B\]

\[F = \bar A \bar C+ B C +\bar AB\]

Example: F = \[\bar A \bar B \bar C + A \bar B \bar C + \bar A \bar B C + \bar A B  C \]

Two groups are formed, each group contains only two cells. The simplified expression contains only two SOP terms and each has two variables.

The simplified expression is

\[F = \bar B \bar C + \bar A C\]

Example: R = π (12, 13, 15)

This time a POS expression is given. It is obvious that mapping an SOP expression will give a non-simplified Boolean expression. 

Don't Care Condition:

In digital circuits, in some conditions, some input variables are not allowed. An example is the BCD codes. These codes are 0-9 (that is from binary 0000  to 1001). While the rest of the combinations are 10- 15 (that is from binary 1010 to 1111) are invalid. These input combinations will never occur.

In these situations simply draw the K-map according to the rules stated above. Mark the unwanted input combinations as 'don't care ('X')'. These terms or input combinations are termed as "don't care" conditions and marked as 'X' in K-map. These terms are advantageous while grouping. Add these 'X' and form larger groups. Larger groups result in simplified expressions. 

Example: \[F (A, B, C, D) =  ∑ (0,2,4,6,8)\]

\[d (A, B, C, D) = (10, 11, 12, 13, 14, 15)\]

Here we add some of them don't care terms to simplify the expression. While the rest of them are not included.

Example: \[F (W, X, Y, Z) = ∑ (1, 3, 7, 11, 15)\]

 \[F (W, X, Y, Z) = (0, 2, 5)\]

Logical Expressions & Their Equivalent Forms Part 2 (Solved Examples | Step By Step Explanation)

 LOGICAL EXPRESSIONS AND THEIR EQUIVALENT FORMS: (PART 2)

In this tutorial, I am going to provide solved examples with all the steps on the topics given in the outline. These topics are explained in detail in the previous tutorial, I discussed the following topics in detail. Please check out the first part here.

OUTLINE:

Solved examples on the following topics:

• Minterms

• Maxterms

• SOP  (Sum of Products)

• POS (Product Of Sum)

• Evaluation of complement of a function with the help of canonical forms (sum of minterms and product of maxterms)

• POS to standard POS

• SOP to standard SOP

• Conversion between standard forms; From SOP to POS and POS to SOP

EXAMPLE 1: Express the function in sum of minterms and product of maxterms (XY + Z)(Y + XZ)

Step 1: Draw ruth table along with sum of minterms and product of maxterms.

X	Y	Z	Output	Minterms	Maxterms
0	0	0	0	X’Y’Z’   m0	X +Y +Z    M0
0	0	1	0	X’Y’Z    m1	X +Y +Z’    M1
0	1	0	0	X’YZ’    m2	X +Y’ +Z    M2
0	1	1	1	X’YZ     m3	X +Y’ +Z’    M3
1	0	0	0	XY’Z’    m4	X’ +Y +Z    M4
1	0	1	1	XY’Z     m5	X’ +Y +Z’    M5
1	1	0	1	XYZ’     m6	X’ +Y’ +Z    M6
1	1	1	1	XYZ     m7	X’ +Y’ +Z’   M7

Step 2: Express the given function in sum of minterms as:

F = X’YZ + XY’Z + XYZ’ + XYZ

F = m3  + m5 +  m6 + m7F = ∑ (3, 5, 6, 7)

Step 3: Express the given function in product of maxterms as:

F = (X +Y +Z)(X +Y +Z’)(X +Y’ +Z)(X’ +Y +Z)

F = M0 . M1 . M2 . M4

F( X, Y, Z) = π (0, 1, 2, 4)

EXAMPLE 2:

Express the function in sum of minterms and product of maxterms (X’ + Y)(Y’ + Z)

Step 1: Draw ruth table along with sum of minterms and product of maxterms.

X	Y	Z	Output	Minterms	Maxterms
0	0	0	1	X’Y’Z’   m0	X + Y + Z    M0
0	0	1	1	X’Y’Z    m1	X + Y + Z’    M1
0	1	0	0	X’YZ’    m2	X + Y’ + Z    M2
0	1	1	1	X’YZ     m3	X + Y’ + Z’    M3
1	0	0	0	XY’Z’    m4	X’ + Y + Z    M4
1	0	1	0	XY’Z     m5	X’ + Y + Z’    M5
1	1	0	0	XYZ’     m6	X’ + Y’ + Z    M6
1	1	1	1	XYZ     m7	X’ + Y’ + Z’   M7

Step 2: Express the given function in sum of minterms as:

F = X’Y’Z’ + X’Y’Z + X’YZ + XYZ

F = m0 ,+  m1 +  m3 +  m7

F = ∑ (0, 1, 3, 7)

Step 3: Express the given function in product of maxterms as:

F = (X + Y’ + Z)(X’ + Y +Z)(X’ + Y +Z’)(X’ + Y’ +Z)

F = M2 M4 M5 M6

F( X, Y, Z) = π (2, 4, 5, 6)

EXAMPLE 3:

Express the function in sum of minterms and product of maxterms Y’Z + WXY’ +WXZ’ +W’X’Z

Step 1: Draw ruth table along with sum of minterms and product of maxterms.

W	X	Y	Z	Output	Minterms	Maxterms
0	0	0	0	0	W’X’Y’Z’    m0	W + X +Y +Z    M0
0	0	0	1	1	W’X’Y’Z    m1	W + X +Y +Z’    M1
0	0	1	0	0	W’X’YZ’    m2	W + X +Y’ +Z    M2
0	0	1	1	1	W’X’YZ    m3	W + X +Y’ +Z’    M3
0	1	0	0	0	W’XY’Z’    m4	W + X’ +Y +Z    M4
0	1	0	1	1	W’XY’Z    m5	W + X’ +Y +Z’    M5
0	1	1	0	0	W’XYZ’    m6	W + X’ +Y’ +Z    M6
0	1	1	1	0	W’XYZ    m7	W + X’ +Y’ +Z’    M7
1	0	0	0	0	WX’Y’Z’    m8	W’ + X +Y +Z    M8
1	0	0	1	1	WX’Y’Z    m9	W’ + X +Y +Z’    M9
1	0	1	0	0	WX’YZ’    m10	W’ + X +Y’ +Z    M10
1	0	1	1	0	WX’YZ    m11	W’ + X +Y’ +Z’    M11
1	1	0	0	1	WXY’Z’    m12	W’ + X’ +Y +Z    M12
1	1	0	1	1	WXY’Z    m13	W’ + X’ +Y +Z’    M13
1	1	1	0	1	WXYZ’    m14	W’ + X’ +Y’ +Z    M14
1	1	1	1	0	WXYZ    m15	W’ + X’ +Y’ +Z’    M15

Step 2: Express the given function in sum of minterms as:

F = W’X’Y’Z + W’X’YZ + W’XY’Z + WX’Y’Z + WXY’Z’ + WXY’Z + WXYZ’

F =  m1 +  m3 + m5 + m9 + m12 + m13 +  m14

F = ∑ (1, 3, 5, 9, 12, 13, 14)

Step 3: Express the given function in product of maxterms as:

F = (W + X +Y +Z)(W + X +Y’ +Z)(W + X’ +Y +Z)(W + X’ +Y’ +Z)(W + X’ +Y’ +Z’)(W’ + X +Y +Z)(W’ + X +Y’ +Z)(W’ + X +Y’ +Z’)(W’ + X’ +Y’ +Z’)    

F =   M0 .  M2 . M4 .  M6 . M7 . M8 . M10 . M11 .  M15

F(W, X, Y, Z) = π (0, 2, 4, 6, 7, 8, 10, 11, 15)

EXAMPLE 4: Evaluate complement of a function from the following table using canonical forms.

X	Y	Z	Output	Minterms
0	0	0	0
0	0	1	0
0	1	0	1	X’YZ’    m2
0	1	1	1	X’YZ     m3
1	0	0	0
1	0	1	0
1	1	0	1	XYZ’     m6
1	1	1	1	XYZ     m7

The function is evaluated from the truth table as 

F = m2 + m3 + m6 + m7

The complement of the above function is calculated as;

F’ = (m2 + m3 + m6 + m7)’

F’ = m2’ + m3’ + m6’ + m7’ 

Mj’ = Mj

The complement function in maxterms form is written below;

F’ = M2 . M3 . M6 . M7

The complement function in minterms form is written below;

F’ = m0 + m1 + m4 + m5

F’(X, Y, Z) = ∑ ( 0, 1, 4, 5)

EXAMPLE 5: Express complement of the function in sum of minterms. F (A, B, C, D) = ∑ (0, 2, 6, 11, 13, 14) 

F = m0 + m2 + m6 + m11 + m13 + m14

As I discussed in my previous tutorial, the complement of the above function contains minterms that are missing in the original function.

F’ = m1 + m3 + m4 + m5 +m7 + m8 + m9 + m10 + m12 + m15

 

 F’ (A, B, C, D) = ∑ (1, 3, 4, 5, 7, 8, 9, 10, 12, 15)

Or 

It can evaluate from the following method as well;

F’ = (m0 + m2 + m6 + m11 + m13 + m14)’

F’ = m0’ . m2’ . m6’ . m11’ . m13’ . m14’

mj’ = Mj

The complement function in product of maxterms;

F’ = M0 . M2 . M6 . M11 . M13 . M14

The complement function in sum of minterms;

F’ =  m1 + m3 + m4 + m5 +m7 + m8 + m9 + m10 + m12 + m15

 F’ (A, B, C, D) = ∑ (1, 3, 4, 5, 7, 8, 9, 10, 12, 15)

EXAMPLE 6: For each of the following function, determine domain of the function, SOP, standard SOP, and then convert standard SOP into standard POS

1. (A + B)(C + B’)

Domain: A, B, C

SOP: 

Apply distributive law:

= AC + AB’ + BC + B.B’

B.B’ = 0

= AC + AB’ + BC

Standadrd SOP:

Look for non-standard term, and then look for missing variable

= AC (B + B’) + AB’(C + C’) + BC(A +A’)

= ABC + AB’C + AB’C + AB’C’ + ABC + A’BC

Remove those terms that appear twice.

= AB’C + AB’C’ + ABC + A’BC

Standard SOP To Standard POS:

There is 23 = 8 possible combinations. The standard SOP contains 4 combinations, the rest of the combinations are part of the standard POS.

You can write directly as well, but for ease, I draw a truth table and then write standard POS expression.

A	B	C	Output	Minterms	Maxterms
0	0	0			A + B + C
0	0	1			A + B + C’
0	1	0			A + B’ +C
0	1	1	1	A’BC
1	0	0	1	AB’C’
1	0	1	1	AB’C
1	1	0			A’ + B’ +C
1	1	1	1	ABC

The standard POS expression is 

= (A + B + C)(A + B + C’)(A + B’ +C)(A’ + B’ +C)

2. (A + B’C)C

Domain: A, B, C

SOP:

= AC + B’CC = AC + B’C

C.C = C

Standadrd SOP:

Look for non-standard term, and then look for missing variable

= AC (B + B’) + B’C (A + A’)

= ABC + AB’C + AB’C + A’B’C

Remove those terms that appear twice.

= ABC + AB’C + A’B’C

Standard SOP To Standard POS:

There is 23 = 8 possible combinations. The standard SOP contains 3 combinations, the rest of the combinations are part of the standard POS.

You can write directly as well, but for ease, I draw a truth table and then write standard POS expression.

A	B	C	Output	Minterms	Maxterms
0	0	0			A + B + C
0	0	1	1	A’B’C
0	1	0			A + B’ + C
0	1	1			A + B’ + C’
1	0	0			A’ + B + C
1	0	1	1	AB’C
1	1	0			A’ + B’ + C
1	1	1	1	ABC

The standard POS expression is 

= (A + B + C)(A + B’ + C)(A + B’ +C’)(A’ + B +C)(A’ + B’ + C)

3. (A + C)(AB + AC)

Domain: A, B, C

SOP:

= AAB + AAC + ABC + AAC

A.A = A

= AB + AC + ABC + AC

Remove those terms that appear twice.

= AB + AC + ABC

Standard SOP:

Look for non-standard term, and then look for missing variable

= AB (C + C’) + AC (B + B’) + ABC

= ABC + ABC’ + ABC + AB’C + ABC

Remove those terms that appear twice.

= ABC’ + ABC + AB’C

Standard SOP To Standard POS:

There is 23 = 8 possible combinations. The standard SOP contains 3 combinations, the rest of the combinations are part of the standard POS.

You can write directly as well, but for ease, I draw a truth table and then write standard POS expression.

A	B	C	Output	Minterms	Maxterms
0	0	0			A + B + C
0	0	1			A + B + C’
0	1	0			A + B’ + C
0	1	1			A + B’ + C’
1	0	0			A’ + B + C
1	0	1	1	AB’C
1	1	0	1	ABC’
1	1	1	1	ABC

The POS expression is

= (A + B + C)(A + B + C’)(A + B’ + C)(A + B’ + C’)(A’ + B + C)

4. AB + CD(AB’ + CD)

Domain: A, B, C, D

SOP:

= AB + AB’CD + CD.CD

= AB + AB’CD + CD

Standard SOP:

Look for non-standard term, and then look for missing variable

= AB (C + C’) + AB’CD + (A + A’)CD

= ABC + ABC’ + AB’CD + ACD + A’CD

Again, look for non-standard terms,  and then look for missing variables.

= ABC(D + D’) + ABC’(D + D’) + AB’CD + ACD (B + B’) A’CD (B + B’)

= ABCD + ABCD’ + ABC’D + ABC’D’ + AB’CD + ABCD + AB’CD + A’BCD + A’B’CD

Remove those terms that appear twice.

= ABCD + ABCD’ + ABC’D + ABC’D’ + AB’CD + A’BCD + A’B’CD

A	B	C	D	Output	Minterms	Maxterms
0	0	0	0			A + B + C +D
0	0	0	1			A + B + C + D’
0	0	1	0			A + B + C’ +D
0	0	1	1	1	A’B’CD
0	1	0	0			A + B’ + C +D
0	1	0	1			A + B’ + C +D’
0	1	1	0			A + B’ + C’ +D
0	1	1	1	1	A’BCD
1	0	0	0			A’ + B + C +D
1	0	0	1			A’ + B + C +D’
1	0	1	0			A’ + B + C’ +D
1	0	1	1	1	AB’CD
1	1	0	0	1	ABC’D’
1	1	0	1	1	ABC’D
1	1	1	0	1	ABCD’
1	1	1	1	1	ABCD

The POS expression is 

= (A + B + C +D)(A + B + C + D’)(A + B + C’ +D)(A + B’ + C +D)(A + B’ + C +D’)(A + B’ + C’ +D)(A’ + B + C +D)(A’ + B + C +D’)(A’ + B + C’ +D)