The GATE Grind

GATE 2019 CS – Question 60

Digital Logic · Boolean Algebra and Minimization · 2 marks · Numerical answer

What is the minimum number of 2-input NOR gates required to implement a 4-variable function expressed in sum-of-minterms form as $f=\Sigma(0,2,5,7,8,10,13,15)$? Assume that all the inputs and their complements are available.

Answer: ________.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 3

Explanation

Minterms $0,2,8,10$ are the cells where $B=0$ and $D=0$ (that is $\overline B\,\overline D$). Minterms $5,7,13,15$ are the cells where $B=1$ and $D=1$ ($BD$). So
$$f=\overline B\,\overline D+BD=\overline{B\oplus D}\quad(\text{XNOR of }B\text{ and }D).$$

Using only 2-input NOR gates, with $B,\overline B,D,\overline D$ available:
1. $G_1=\mathrm{NOR}(\overline B,D)=B\,\overline D$
2. $G_2=\mathrm{NOR}(B,\overline D)=\overline B\,D$
3. $G_3=\mathrm{NOR}(G_1,G_2)=\overline{B\overline D+\overline BD}=\overline{B\oplus D}=f$

Three gates are enough. Two gates cannot produce XNOR from 2-input NORs, so the minimum is **3**.

More Boolean Algebra and Minimization questions

All Boolean Algebra and Minimization questions →