GATE CS 2009 Q6 — Combinational Circuits

To find the minimum number of $2$-input NOR gates required to implement the Boolean function $F = AB + C$, we can use the distributive law and De Morgan's laws to express the function in terms of NOR operations.

Step 1: Apply the Distributive Law
$$F = AB + C = (A + C)(B + C)$$

Step 2: Apply Double Negation and De Morgan's Law
Using the identity $X \cdot Y = \overline{\overline{X} + \overline{Y}}$: $$F = \overline{\overline{(A + C)(B + C)}} = \overline{\overline{A + C} + \overline{B + C}}$$

Step 3: Express using the NOR operator ($\downarrow$)
Recall that the $2$-input NOR operation is defined as $x \downarrow y = \overline{x + y}$. Using this definition:

• Let $G_1 = \overline{A + C} = A \downarrow C$   (requires $1$ NOR gate)
• Let $G_2 = \overline{B + C} = B \downarrow C$   (requires $1$ NOR gate)

Conclusion:
We can implement the function using exactly $3$ NOR gates as follows: $$F = (A \downarrow C) \downarrow (B \downarrow C)$$ Thus, the minimum number of $2$-input NOR gates required is 3.