Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Questions
3.
Frequently Asked Questions
4.
Conclusion
Last Updated: Mar 27, 2024

K Maps

Author Abhay Trivedi
1 upvote
Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

A Karnaugh map (K-map) is a pictorial technique used to minimize Boolean expressions without using Boolean algebra theorems and equation manipulations. A K-map can be considered a particular version of a truth table. The K Maps is a way of simplifying Boolean algebra expressions. Maurice Karnaugh introduced K Maps in 1953 as a refinement of Edward W. Veitch's 1952 Veitch chart, which was a rediscovery of Allan Marquand's 1881 logical diagram, i.e., Marquand diagram but with a focus now set on its utility for switching circuits. This article has popular questions on K maps that came in the past year.

Questions

1. Consider the following interm expression of F:

F(P, Q, R, S) = Σ(0, 2, 5, 7, 8, 10, 13, 15).

The minterms 2, 7, 8, and 13 are don't care terms. The minimal sum of products form is? [GATE CSE 2014 Set 3]

Answer: B

Explanation: On solving the k-map, we get,

Thus, the answer is QS + Q’S’

Option (B) is correct.

2. The Karnaugh map below shows that X represents a 'do not care' term. What is the minimal form of the function depicted by the Karnaugh map? [GATE CSE 2008]

Answer: A

Explanation: One group is (0000, 0010, 1000, 1010), which gives b'.d'.

Another group is (0000, 0001, 1000, 1001), which gives a'.d'.

So, the solution is b'.d' + a'.d'

3. The minimum SOP for f(w,x,y,z) shown in the Karnaugh map below is: [GATE CSE 2002]

Answer: B

Explanation:

 

Two quads are getting formed xz’ and zx’

4. Given the following Karnaugh map, which one of the next represents the minimal Sum-Of-Products of the map? [GATE CSE 2001]

Answer: A

Explanation:

 

Two quads are getting formed xy and y’z.

5. Which of the following functions implements the Karnaugh map shown below? [GATE CSE 1999]

Answer: B

Explanation: 

CD+AD 

=D(C+A)

6. What is the minimum number of 2-input NOR gates needed to implement a 4-variable function represented in sum-of-minterms form as

f = Σ(0, 2, 5, 7, 8, 10, 13, 15).

Assuming that all the inputs and their complements are available. [GATE CSE 2019]

Answer: 3

Explanation: f=(B′+D).(B+D′)

(Since both Complimentary as well as Uncomplimentary forms are available)

B′ NOR D=(B′+D)′

B NOR D′=(B+D′)′

(B′ NOR D) NOR (B NOR D′)

=((B′+D)′ + (B+D′)′)′

=((B′+D)′′.(B+D′)′′)

=((B′+D).(B+D′))

=f

Thus, 3 NOR Gates are required.

7. Consider the minterm list form of a Boolean function F given as: F(P,Q,R,S)= ∑(m(0, 2, 5, 7, 9, 11) + d(3, 8, 10, 12, 14)). where m is a minterm and d is a don’t care term. The number of crucial prime implicants of the function F is _______. [GATE CSE 2018]

Answer: 3

Explanation: Essential Prime Implicants are those subcubes (groups) that cover at least one minterm that any other prime implicant can’t cover. Essential prime implicants (EPI) are those prime implicants that always appear in the final solution.

There are three prime implicants P’QS, PQ’, and Q’S’. Also, all of them are essential. Therefore, the number of crucial prime implicants of function F is 3.

8. What is the minimal form of the Karnaugh map shown below? Assume that X represents a don’t care term. [GATE CSE 2012]

Answer: B

Explanation: 

Twenty-two quads are getting formed.

The value for the First one is b′d′b′d′, and the value for 2nd2nd one is b′c′b′c′. So, the answer is option B.

9. Consider a multiplexer with X and Y as data inputs and Z as a control input. If z = 0 selects input x and z = 1 sets information Y. What are the connections needed to realize the 2-variable Boolean function f = T + R without using additional Hardware? [GATE CSE 2004]

Answer: A

Explanation: For mux, we will be having equations like z’x+zy --(1)

Now putting X=R, Y=1, and Z=T in eq(1), we find

= T’R + T(1)

= T + T’R

= T + R (Since a+a’b = a+b)

So the answer is (A) part.

10. The literal count of a Boolean expression is the sum of the times every literal appears in that expression. For example, the literal count of xy + xz equals 4. What are the minimum likely literal counts of the product of sum and sum of product representations of the function given by the subsequent Karnaugh map? Here, X denotes “don’t care.” [GATE CSE 2003]

Answer: C

Explanation: S.O.P. : wy + w’y’ + z’wx’ + xyz’

Literal count = 10

P.O.S. : (w’ + z’)(x’ + y)(z + w + x)(z’ + y’)

Literal count = 9

So, option (C) is correct.

11. Which function does NOT implement the Karnaugh map given below? [GATE CSE 2000]

Answer: D

Explanation: We can simplify each equation given in the option and get that all of them give xy+wyxy+wy. But let's think in another way.

1st option is written in POS form, as we can check, we get the same if we consider the following applicants:

which is (w+x)y

For the second one, which gives wy+xy.

Now for 3rd one, we can verify like this

which is (w+x)(w'+y)(x'+y)

So as we can verify each equation in a given K-Map, so the answer is option D.

12. What is the equivalent Boolean expression in the sum form product for the Karnaugh map given in the fig? [GATE CSE 1996]

Answer: C

Explanation: The following K-Map shows the boolean expression for POS form:

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

  1. What are K Maps?
    The Karnaugh map(K Maps) is a way of simplifying Boolean algebra expressions. Maurice Karnaugh introduced K Maps in 1953 as a refinement of Edward W. Veitch's 1952 Veitch chart, which was a rediscovery of Allan Marquand's 1881 logical diagram, i.e., Marquand diagram but with a focus now set on its utility for switching circuits.
     
  2. Where do we use K-maps?
    A Karnaugh map (K-map) is a pictorial method used to minimize Boolean expressions without using Boolean algebra theorems and equation manipulations. A K-map can be considered a particular version of a truth table. We can quickly reduce expressions with two to four variables using a K-map.
     
  3. What are the advantages of the k map?
    The K-map simplification technique is more straightforward and less error-prone than solving the logical expressions using Boolean laws. It prevents the need to remember every Boolean algebraic theorem.
     
  4. What are the disadvantages of the K map?
    K maps are not suitable for computer reduction. It is not appropriate when the number of variables involved exceeds four. Special Care must be taken to a field in every cell with relevant entry, such as 0, 1 (or) don't care terms.
     
  5. What are SOP and POS in K-map?
    Boolean functions can be described by using NAND gates and the K-map (Karnaugh map) method. We can formalize the Boolean expressions by using two standard forms. SOP form - Sum Of Products form. POS form - Product Of Sums form.

Conclusion

This article gives information about the K Maps and how this technique can improve an individual's skill to solve boolean algebra expressions.

Click here to read about Sequential circuits.

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow.

Happy Learning!

Live masterclass