in Digital Logic edited by
9,565 views
26 votes
26 votes

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$
in Digital Logic edited by
9.6k views

4 Comments

How A'+AB= A'+B
0
0
@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
0
0
@bikram sir

make edit in option B.
1
1

4 Answers

21 votes
21 votes
Best answer

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

edited by

4 Comments

and how many NOR gates??

is it three..?
0
0

Here is NOR implementation

10
10

@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

6
6

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

0
0
18 votes
18 votes
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.
13 votes
13 votes

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

5
5
12 votes
12 votes
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
Answer:

Related questions