The GATE Grind

GATE 2017 CS – Question 31

Digital Logic · Boolean Algebra and Minimization · 1 mark · Numerical answer

Consider the Karnaugh map given below, where X represents "don't care" and blank represents 0.

[Karnaugh map with columns $ba$ = 00, 01, 11, 10 and rows $dc$ = 00, 01, 11, 10. The cells with 1 are ($dc$ = 01, $ba$ = 00), ($dc$ = 11, $ba$ = 00) and ($dc$ = 11, $ba$ = 10). The cells with X are ($dc$ = 00, $ba$ = 01), ($dc$ = 00, $ba$ = 11), ($dc$ = 01, $ba$ = 10), ($dc$ = 10, $ba$ = 01) and ($dc$ = 10, $ba$ = 11).]

Assume for all inputs $(a, b, c, d)$, the respective complements $(\bar{a}, \bar{b}, \bar{c}, \bar{d})$ are also available. The above logic is implemented using 2-input NOR gates only. The minimum number of gates required is ________.

Diagram for GATE 2017 CS question 31

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 1

Explanation

All three 1-cells have $c = 1$ and $a = 0$. The four cells with $c = 1$ and $a = 0$ are the three 1s and one don't-care, so the whole group can be used, and the function simplifies to $f = c\,\bar{a}$. Since $c\,\bar{a} = \overline{\bar{c} + a}$, a single 2-input NOR gate with inputs $\bar{c}$ and $a$ implements it.