9,565 views

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?

1. $2$
2. $4$
3. $5$
4. $6$

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.

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}$

and how many NOR gates??

is it three..?

Here is NOR implementation

@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, 6th edition, section 2.4. Don’t know about minimum number of gates

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.
 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

### 1 comment

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
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)
by