Introduction of K-Map (Karnaugh Map)

A Karnaugh map or a K-map refers to a pictorial method that is utilised to minimise various Boolean expressions without using the Boolean algebra theorems along with the equation manipulations. A Karnaugh map can be a special version of the truth table. We can easily minimise various expressions that have 2 to 4 variables using a K-map.

In this article, we will take a look at the Introduction to K-Map (Karnaugh Map) according to the GATE Syllabus for CSE (Computer Science Engineering). Read ahead to learn more.

Table of Contents

• Introduction of K-Map (Karnaugh Map)
• Solving an Expression Using K-Map
  • SOP FORM
    • 3 variables K-map
    • 4 variables K-map
  • POS FORM
    • 3 variables K-map
    • 4 variables K-map
• Practice Problems on Introduction of Karnaugh Map
• FAQs

Introduction of K-Map (Karnaugh Map)

In numerous digital circuits and other practical problems, finding expressions that have minimum variables becomes a prerequisite. In such cases, minimisation of Boolean expressions is possible that have 3, 4 variables. It can be done using the Karnaugh map without using any theorems of Boolean algebra. The K-map can easily take two forms, namely, Sum of Product or SOP and Product of Sum or POS, according to what we need in the problem. K-map is a representation that is table-like, but it gives more data than the TRUTH TABLE. Fill a grid of K-map with 1s and 0s, then solve it by creating various groups.

Solving an Expression Using K-Map

Here are the steps that are used to solve an expression using the K-map method:

1. Select a K-map according to the total number of variables.

2. Identify maxterms or minterms as given in the problem.

3. For SOP, put the 1’s in the blocks of the K-map with respect to the minterms (elsewhere 0’s).

4. For POS, putting 0’s in the blocks of the K-map with respect to the maxterms (elsewhere 1’s).

5. Making rectangular groups that contain the total terms in the power of two, such as 2,4,8 ..(except 1) and trying to cover as many numbers of elements as we can in a single group.

6. From the groups that have been created in step 5, find the product terms and then sum them up for the SOP form.

SOP FORM

1. 3 variables K-map:

Z = ∑P, Q, R (1, 3, 6, 7)

From the red group, the product term would be —

P’R

From the green group, the product term would be —

PQ

If we sum these product terms, then we will get this final expression (P’R + PQ)

2. 4 variables K-map:

F (A, B, C, D) = ∑(0, 2, 5, 7, 8, 10, 13, 15)

From the red group, the product term would be —

BD

From the lilac group, the product term would be —

B’D’

If we sum these product terms, then we will get this final expression (BD + B’D’)

POS FORM

1. 3 variables K-map

F (P, Q, R) = π(0,3,6,7)

From the lilac group, the terms would be

P Q

If we take the complement of these two

P’ Q’

And then sum up them

(P’ + Q’)

From the blue group, the terms would be

B R

When we take the complement of these terms

B’ R’

And then sum them up

(B’ + R’)

From the red group, the terms would be

P’ Q’ R’

If we take the complement of the two terms

P Q R

And then sum them up

(P + Q + R)

If we take the product of these three terms, then we will get this final expression –

(P’ + Q’) (P’ + R’) (P + Q + R)

2. 4 variables K-map

F (P, Q, R, S) = π (3, 5, 7, 8, 10, 11, 12, 13)

From the blue group, the terms would be

R’ S Q

We take their complement and then sum them

(R + S’+ Q’)

From the purple group, the terms would be

R S P’

We take their complement and then sum them

(R’ + S’+ P) S

From the red group, the terms would be

P R’ S’

We take their complement and then sum them

(P’ + R + S)

From the lilac group, the terms would be

P Q’ R

We take their complement and then sum them

(P’ + Q + R’)

Finally, we will express these in the form of the product –

(R + S’+ Q’).(R’ + S’+A).(P’+ R + S).(P’+ Q + R’)

Pitfall – Always remember that POS ≠ (SOP)’

*Here, the correct form would be (POS of F) = (SOP of F’)’

Practice Problems on Introduction of Karnaugh Map

1. There are a total of ______ cells in a K-map with 4-variable.

a) 8

b) 18

c) 16

d) 12

Answer – (c) 16

2. The don’t care condition could be used in order to simplify the Boolean expressions in the ___________.

a) Latches

b) K-maps

c) Terms

d) Registers

Answer – (b) K-maps

3. Logic gates can be widely used in the _______________ design and are therefore available in the IC form.

a) Digital

b) Sampling

c) Systems

d) Analog

Answer – (a) Digital

4. Entries are also called the _______________ mapping.

a) Boolean

b) K

c) Straight

d) Diagonal

Answer – (d) Diagonal

5. Every product term of the group, a’.b.c’ and a.c, represents the ____________ in that particular group:

a) Sum of Maxterms

b) Sum of Minterms

c) POS

d) Input

Answer – (b) Sum of Minterms

Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus, GATE Previous Year Question Paper, and more.

Also Explore,

• Combinational Circuits
• Boolean Algebra
• Laws of Boolean Algebra
• Various Implicants in K-Map
• Representation of Boolean Functions
• Combinational and sequential circuits
• Flip-Flop Types, Conversion and Applications
• The Base of Number System
• Conversion to Base 10
• Number System Notes
• Decimal to Binary Conversion
• Decimal to Hexadecimal Conversion
• Decimal to Octal Conversion
• Minimization of Boolean Functions