سوال ۷۶ کنکور ارشد مهندسی کامپیوتر ۱۴۰۴

We must realize the four-term SOP $f = AB + CD + EF + GH$ using only two-input NAND gates. Let $x \uparrow y = \overline{xy}$.

Level 1 — the four products (4 gates). Form the complemented products: $p_1 = \overline{AB},\quad p_2 = \overline{CD},\quad p_3 = \overline{EF},\quad p_4 = \overline{GH}.$ Each is one 2-input NAND, so this costs 4 gates.

Level 2 — combine into the OR (5 gates). By De Morgan, the standard NAND-NAND form is $f = AB + CD + EF + GH = \overline{\,\overline{AB}\cdot\overline{CD}\cdot\overline{EF}\cdot\overline{GH}\,} = \overline{p_1 p_2 p_3 p_4},$ i.e. a 4-input NAND of $p_1,p_2,p_3,p_4$. Since only 2-input NANDs exist, build it from 2-input gates:

• $q_1 = \overline{p_1 p_2}$ (gate 5) and $q_2 = \overline{p_3 p_4}$ (gate 6).
• Then $p_1 p_2 = \overline{q_1}$, $p_3 p_4 = \overline{q_2}$, so $f = \overline{p_1 p_2 p_3 p_4} = \overline{\overline{q_1}\,\overline{q_2}} = q_1 + q_2$.
• The OR $q_1 + q_2 = \overline{\overline{q_1}\,\overline{q_2}}$ needs two NAND-inverters $\overline{q_1}$ (gate 7), $\overline{q_2}$ (gate 8) and a final NAND (gate 9).

That is 5 more gates.

Total: $4 + 5 = 9$ gates.

Equivalently, split as $f=(AB+CD)+(EF+GH)$: each half is a NAND-NAND pair $\overline{AB},\overline{CD}$ followed by one NAND $= 3$ gates, giving $g_1,g_2$ uncomplemented ($6$ gates); the final OR $g_1+g_2$ costs $3$ more (two inverters + one NAND) $= 9$ gates.

So the answer is $9$ — option 2.

Exam trick: A two-level AND-OR maps to NAND-NAND for free only if a wide NAND is available. With just 2-input NANDs you must (a) realize each product as a 2-input NAND, and (b) build the wide output NAND from a tree of 2-input NANDs plus inverters — each extra OR-merge of two signals costs 3 NANDs (two inverters + one NAND).