Logic synthesis using only NAND gates: How many two-input NAND gates are required to implement a two-input OR function?

Introduction / Context:
NAND is a universal gate, meaning any Boolean function can be built using only NAND gates. A classic exercise is to realize OR using only NANDs via De Morgan's law and input inversion with NAND-as-inverter constructs.

Given Data / Assumptions:

• Available gate: 2-input NAND only.
• Target: 2-input OR, i.e., Y = A OR B.
• Allowed technique: use NAND gates as inverters by tying inputs together.

Concept / Approach:
By De Morgan's law, A OR B = NOT( NOT(A) AND NOT(B) ). With NANDs: NOT(x) = x NAND x. Therefore, implement NOT(A) with one NAND, NOT(B) with one NAND, and then NAND their results to realize the outer NOT of AND.

Step-by-Step Solution:
Form ~A using NAND: N1 = A NAND A.Form ~B using NAND: N2 = B NAND B.Compute OR: Y = N1 NAND N2 = (~A) NAND (~B) = A OR B.Total NAND gates used: 3.

Verification / Alternative check:
Build the truth table for A,B ∈ {0,1} and confirm that Y equals A OR B. The construction matches for all four combinations.

Why Other Options Are Wrong:
1 or 2 NANDs cannot both invert two inputs and implement the final combination. 4 is possible with non-minimal designs, but 3 is the standard minimal count.

Common Pitfalls:
Forgetting you can invert with a NAND by shorting inputs; misapplying De Morgan's law signs.

Final Answer:
3