What is the minimum number of NAND gates required to implement a 2-input…
2004
What is the minimum number of NAND gates required to implement a 2-input EXCLUSIVE-OR function without using any other logic gate?
- A.
3
- B.
4
- C.
5
- D.
6
Attempted by 363 students.
Show answer & explanation
Correct answer: B
Answer: 4 NAND gates.
Construction (using only NAND gates):
N1 = A NAND B
N2 = A NAND N1
N3 = B NAND N1
Output = N2 NAND N3
Why this yields XOR:
N1 = ¬(A ∧ B)
N2 = ¬(A ∧ N1) = ¬(A ∧ ¬(A ∧ B)) = ¬(A ∧ ¬B) = (¬A ∨ B)
N3 = ¬(B ∧ N1) = ¬(B ∧ ¬(A ∧ B)) = ¬(B ∧ ¬A) = (¬B ∨ A)
Output = ¬(N2 ∧ N3) = ¬((¬A ∨ B) ∧ (¬B ∨ A)) = A XOR B
Therefore the minimum number of NAND gates required to implement a 2-input exclusive-OR is 4.
A video solution is available for this question — log in and enroll to watch it.