GATE IT 2004 | Question: 8

Question

What is the minimum number of $\text{NAND}$ gates required to implement a $2\text{-input EXCLUSIVE-OR}$ function without using any other logic gate?

• A. $2$
• B. $4$
• C. $5$
• D. $6$

Comments

How A'+AB= A'+B

---

@smartmeet as you know that               A+BC = (A+B)(A+C). So.                        A^+AB=(A^+A)(A^+B)   //A^+A=1.              So we can say A^+AB =A^+B

---

@bikram sir

make edit in option B.

Answer 1

Correct Option B $4.$

$\begin{array}{c | c | c}  \textbf{A} & \textbf{B} & \textbf{Output} \\\hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0  \end{array}$

Comments

and how many NOR gates??

is it three..?

---

Here is NOR implementation

---

@Arjun sir, @Bikram sir

@Subarna Das mam

After drawing a circuit for a question, how can i be sure that this is the most optimal way..

I mean how can i be sure that there is no other way that gives me even less number of gates...

i am facing the same problem for finding minimum number of states of a dfa of a given situation..

Need help in this aspect.. Thanks in advance

---

Method for minimum number of states in a DFA is given in Peter Linz, 6^th edition, section 2.4. Don’t know about minimum number of gates

Answer 2

Using the intuitive way,

XOR (A,B) = A' B + A B'

So, for using NAND Gates, we use double complement method:

XOR (A,B) = ( (A' B + A B' ) ' ) '  =  ( (AB') ' . (AB') ' )'

Now in order to implement A' and B' we will have to use two NAND Gates and then two more to implement  (A' B)'  and  (AB') '. And at last 1 more NAND Gate to implement ( (A' B)' . (AB') ' )'. Hence all in all we Will be using 5 NAND Gates. This WONT WORK !

Hence we have to think of an OPTIMIZED Solution !

Therefore we use a new method to obtain (AB') ' and (AB') ' using lesser number of Gates.

Using NAND gates we directly have (AB)' . Now we can make use of this and obtain (AB') ' and (AB') ' using lesser number of gates:

We see : (A B') ' = ((AB)'.A) '   And  (A' B) ' = ( (AB)'.B ) '

Hence the equation can be reduced to :

XOR(A,B) = ( ( (AB)'.B ) ' . ((AB)'.A) ' ) '

This solution would require 4 Gates only. Hence Logically we can arrive at this solution.

Answer 3

	by using NAND	by using NOR
NOT	1	1
OR	3	2
AND	2	3
NAND	-	4
NOR	4	-
EX-OR	4	5
EX-NOR	5	4

Ans: B

Comments

Just rearranged to remember.

	by using NAND	by using NOR
NOT	1	1
AND	2	3
OR	3	2
NAND	-	4
NOR	4	-
EX-OR	4	5
EX-NOR	5	4

---

$\begin{array}{|c | c | c|} \hline & \textbf{NAND} & \textbf{NOR} \\ \hline \text{NOT} & 1 & 1 \\ \hline \text{AND} & 2 & 3 \\ \hline \text{OR} & 3 & 2 \\ \hline \text{NAND} & 1 & 4 \\ \hline \text{NOR} & 4 & 1 \\ \hline \text{EX-OR} & 4 & 5 \\ \hline \text{EX-NOR} & 5 & 4 \\ \hline \text{HALF ADDER} & 5 & 5 \\ \hline \text{FULL ADDER} & 9 & 9 \\ \hline \end{array}$

Answer 4

Any 2-input Exclusive OR function can be implemented with the 4 NAND gates.

1st NAND gate:

Input: A,B

output: (AB)'

2nd NAND gate:

Input: (AB)' , A

output: A' +AB

3rd NAND gate:

Input: (AB)', B

output: B' +AB

4th NAND gate:

Input: A' +AB, B'+AB

output: A'B + AB'  (Exclusive OR function)