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: