# How to construct XOR gate using only 4 NAND gate?

xor gate, now I need to construct this gate using only 4 nand gate

a b out
0 0 0
0 1 1
1 0 1
1 1 0


the xor = (a and not b) or (not a and b), which is \begin{split}\overline{A}{B}+{A}\overline{B}\end{split}

I know the answer but how to get the gate diagram from the formula?

EDIT

I mean intuitively, to me, I should get this one if I do it step by step followed by the definition xor = (a and not b) or (not a and b).

\begin{split}\overline{\overline{\overline{A}{B}}\cdot\overline{{A}\overline{B}}}\end{split}

and xor will be constructed with 5 nand gates (first #1 image below)

my question is more like: imagine the first person in history figure out this formula, how can he or she (the thinking process) get the 4 nand soltuion from this formula, step by step.

\begin{split}\overline{A}{B}+{A}\overline{B}\end{split}

• I'm sure you know how to take a XOR (or any other function) and convert it to an equivalent circuit that only uses NAND (which is always possible, since NAND is complete). However if you ask how to reduce this formula to using only 4 NANDs, or in general, less than $k$ NANDs, and whether it is even possible to obtain an equivalent circuit with $\le k$ NANDs -- I'm not sure there is an easy answer for that. – Ran G. Jun 7 '15 at 16:05
• Below are two answers to the problem. Mine is quite candid about the fact that you can design (a posteriori) a way to find the desired construction from knowing the final result in advance, which was given in the question and is available on the Internet. It is clearly the simpler way of doing thing, absurd as it may seem, short of giving a general procedure, which no answer is doing. Hence, I am interested in knowing why voters prefer one answer over the other, when they do ... if you will take the time for a short comment. Thanks in advance. – babou Jun 8 '15 at 9:43
• This question is up for being closed as unclear. I think it might be fairly clear what the OP is asking, and more i8nteresting, if the OP bothered to react to the various users who try to answer him, – babou Jun 14 '15 at 11:21
• electronics.stackexchange.com/questions/84714/… -- this question is more general, the answers give more information on a general approach to solving this problem, and this answer electronics.stackexchange.com/a/84803 shows how to derive NAND representation for the XOR operator – Anton Trunov Nov 12 '15 at 13:46
• I played around with some similar problems and just wrote a program that tried everything systematically... Fine for up to four inputs, where there are only 65,536 possible functions. For slightly more complicated circuits this also allowed me to optimise delays, and to find optimal circuits if one or two inputs were available later than others. Circuits with 5 inputs = 2^32 possible functions would probably be doable using brute force. – gnasher729 Aug 11 '16 at 16:20

From that formula? It can be done. But it's easier to start with this one: (using a different notation here)

a ^ b = ~(a & b) & (a | b)


Ok, now what? Eventually we should derive ~(~(~(a & b) & a) & ~(~(a & b) & b)) (which looks like it has 5 NANDs, but just like the circuit diagram it has a sub-expression which is used twice).

So make something that looks like ~(a & b) & a (and the same thing but with a b at the end) and hope that it'll stick around: (and distributes over or)

(~(a & b) & a) | (~(a & b) & b)


Pretty close now, just apply DeMorgan to turn that middle or into an and:

~(~(~(a & b) & a) & ~(~(a & b) & b))


And that's it.

I think you are asking for this proof:

A^B = (!A)B + A(!B)
= !!((!A)B) + !!(A(!B))
= !(!!A + !B) + !(!A + !!B)
= !(A + !B) + !(!A + B)
= !((A + !B)(!A + B))
= !(A(!A) + AB + (!A)(!B) + B(!B))
= !(AB + (!A)(!B))
= !(AB)(!(!A)(!B))
= !(AB)(!!A + !!B)
= !(AB)(A+B)
= !(AB)A + !(AB)B
= !!(!(AB)A + !(AB)B)
= !((!(!(AB)A))(!(!(AB)B)))


Although apparently there are 5 NANDs used in the resultant equation, but the duplicate !(AB) will be used only once when you are designing its circuit.

• I am sorry, but isn't A^B means A AND B? It seems your intention was to proof XOR which symbol should be ⊕ or ⊻. However this proof was what I really looked for, thank you! – osiixy Feb 15 '19 at 9:53
• @oslixy: ^ is used for bitwise XOR in the C language. Here he's using multiplication (written as juxtaposition) for AND, which is quite common. – wnoise Dec 6 '20 at 19:14

Since you already have the diagram answer, easily awailable from wikipedia by typing you question title in Google, as a .png diagram identical to yours, it should be easy for you to find the formula by extracting it from that diagram. Given the definition NAND as $\text{NAND}(A,B)=\overline{AB}\;$:

• The leftmost gate gives $C=\overline{AB}$;

• The top gate gives $D_1=\overline{AC}$;

• The top gate gives $D_2=\overline{BC}$, as the NAND is commutatve like the AND;

• The rightmost gate gives $E=\overline{D_1D_2}$.

Putting it all together we first note that

$C=\overline{AB}=\overline A+\overline B$

\begin{align} \overline{D_1}&=AC\\ &=A(\overline A+\overline B)\\ &=A\overline A+A\overline B\\ &=0+A\overline B\\ &=A\overline B\\ \end{align}

Similarly: $\overline{D_2}=B\overline A$

Thus
\begin{align} E&=\overline{D_1D_2}\\ &=\overline{D_1}+\overline{D_2}\\ &=A\overline B + B\overline A \end{align}

Which is precisely the definition of XOR. You may just reverse all this if you want to start from your initial data, rather than just check the answer.

## Finding the answer with no prior knowledge

This is intended to answer the explicit request, added as an edit to the question, for a way of finding the solution from scratch. Given that the question is about a thought process, I am giving all details.

I would try to rely on the constraints of the problem (only 4 NAND gates) and on its symmetry between $A$ and $B$ which may be preserved in the solution.

One thing I know (assuming information flows from left to right as in the question diagrams) is that there must be a rightmost NAND gate that produces the desired answer $\text{XOR}(A,B)=A\overline B + B\overline A\;$.

So we can try to guess what kind of input to this gate would produce the desired output.

We know that $\text{NAND}(X,Y)=\overline{XY}= \overline X+\overline Y\;$

Unifying this last formula with the result we have to get, we obtain:

• $\overline X=A\overline B\;$, thus $X=\overline{A\overline B}=\overline A+B\;$.

• and symetrically $Y=\overline{\overline A B}=A+\overline B\;$.

Note that this is only the simplest possibility. There are other pairs of inputs that would give the desired result, because we are not unifying in a free algebra, since NAND has equational properties. But we try that for a start.

The problem is now whether we can obtain both $X$ and $Y$ from $A$ and $B$ with 3 NAND gates.

We could try to repeat the unification procedure (I did), but this will naturally lead us to using four more gates, hence to a 5 gates solution.

Assuming we are on the right track, we need two NAND gates to produce $X$ and $Y$. So that leaves us with only one gate to produce a formula $Z$ that combined with $A$ or $B$ will provide the input for these two intermediate gates.

Given that we have to provide symetrically for $X$ and $Y$, we can expect that $Z$ should be symmetric in $A$ and $B$. Hence this leftmost NAND gate should take both $A$ and $B$ as input.

This first NAND gate, with $A$ and $B$ as input, produces as output:

$Z=\text{NAND}(A,B)=\overline{AB}= \overline A+\overline B\;$

Now, we have to check whether combining $Z$ with itself, $A$, $B$, 0, or 1 through a NAND gate can produce $X$, and also $Y$.

We know that combining a value with itself, 0 or 1 through a NAND gate is either the identity function or the negation. So the only remaining candidates are $A$ and $B$.

It is easy to check that

\begin{align} \text{NAND}(Z,A)&=\overline{ZA}\\ &=\overline{\overline{AB}\;A}\\ &=\overline{(\overline A+\overline B)\;A}\\ &=\overline{\overline AA+\overline BA}\\ &=\overline{0+\overline BA}\\ &=\overline{\overline BA}\\ &=\overline{A\overline B}\\ &=X \end{align}

Similarly $\text{NAND}(Z,B)=Y$

Hence we can compose these four gates to get the desired result, i.e., the XOR function.

• Not in a reverse way to prove that they are equal. But image that you don't know the diagram but to construct the gate using minimum nand gate. – Timeless Jun 7 '15 at 13:05
• What do you expect as an answer? A systematic technique for doing that. I do not know that there is any that is tractable enough to be worth using in complex cases. Given that I know the answer I can just lie to you and pretend to have found by reasonning what I discovered by checking the answer. This said, looking at what I get with NAND(A,B) is all that seems useful for a start. Then NANDing the result with one argument A or B, is also one thing to look at, to get a view of where I am. From there, one is pretty close to the final answer. – babou Jun 7 '15 at 13:27
• @Timeless Another way to go about it is backward from the answer, knowing that the answer is fron a NAND gate. If you assume that the solution is symmetrical in A and B, it gives you a likely form of the inputs to the last NAND gate. There are many way to go about it, either to find the answer, or to justify finding it a posteriory. But a proof is a proof, whether found by your ingenuity, or given by some oracle or a good friend. And at some point no one can tell the difference. Actually, the backward proof I give could be the best proof, even if the solution was found some other way. – babou Jun 7 '15 at 13:41
• Actually, it is quite common in math to have an analysis part to find a solution, then a synthesis part where you prove it is the solution. One usually gives both, but only the second part is really necessary. – babou Jun 7 '15 at 13:43
• @Timeless Both answers were based on the knowledge of a formula to obtain, deduced from the diagram to be obtained. Your edit asked for a plausible intuitive scenario to find the answer without any prior knowledge of the result. I did add that to my answer, but it would be nice to know whether it fits what you expected. – babou Jun 10 '15 at 23:33

I take the input $(0,0)$ as an example.

For $\text{XOR}$, the desired output is 0. However, $\text{NAND}(0,0) = 1$.

• Because the only way to get a 0 using $\text{NAND}$ is (at the last layer) $\text{NAND}(1,1) = 0$, you should first produce two 1's.

• According to $\text{NAND}(0,1) = 1$ or $\text{NAND}(1,0) = 1$, you produce a 1 using one $\text{NAND}(0,0)$ at the first layer and feed it, along with one input 0, into a second layer $\text{NAND}$.

Only four $\text{NAND}$s are involved. But it is only correct for the input $(0,0)$ so far. So you need to check other inputs $(0,1), (1,0),$ and $(1,1)$ against the solution and find that it just works. Lucky.

I tried my best to give the answer using formula as asked.Hope you appreciate it.
Z=AB'+A'B
Z=AA'+AB'+BB'+A'B --->BB'=AA'=0
Z=A(A'+B')+B(B'+A')
Z=A(AB)'+B(AB)' --> Hint
so now (AB)' can get through 1st NAND gate,then in 2nd and third NAND gate the output of 1st NAND gate pass through with one of the input as A and B.After this we need one more complement so use fourth NAND gate.
NAND(1st)=(AB)'=A'+B'
NAND(2nd)=(A(AB)')'=(A(A'+B'))'=(AB')'=A'+B
NAND(3rd)=(B(AB)')'=(B(A'+B'))'=(A'B)'=A+B'
NAND(4th)=[(A'+B)(A+B')]' =[A'B'+AB]'=(A+B)(A'+B')=AB'+A'B

Happy!

The formula: XOR = (a and not b) or (not a and b).

Thats' not what you want, you want a formula that is a NAND. Remember that not (a or b) = not a and not b, and therefore (a or b) = not (not a and not b). Therefore

(a and not b) or (not a and b) =

not (not (a and not b) and not (not a and b)) =

not ((not a or b) and (a or not b)) =

NAND (not a or b, a or not b).

So we used one NAND gate, and have to calculate (not a or b) and (a or not b) using three NANDs. We turn each expression into a NAND:

not a or b = not (a and not b) = NAND (a, not b)

a or not b = not (not a and b) = NAND (not a, b)

Now we observe that (x and y) = x and (not x or y): If x is false then both sides are false. If x is true then (not x or y) = (false or y) = y. This is true for NAND just as it's true for AND. Therefore

NAND (a, not b) = NAND (a, not a or not b) = NAND (a, NAND (a, b))

NAND (b, not a) = NAND (b, not b or not a) = NAND (b, NAND (a, b)).

So we first find mid = NAND (a, b), left = NAND (a, mid) and right = NAND (b, mid), finally XOR = NAND (left, right).

*From left to right--D1,D2,D3,D4 ** D1=(A.B)' OR(A'+B')

suppose

(A.B)'=C

D2=(A.C)'=A'+C'

D3=(B.C)'=B'+C' then

D4=(D2.D3)'

D4=((A.C)'.(B.C)')'

D4=(A.C)''+(B.C)''

D4=(A.C)+(B.C)

D4=A.(A'+B')+B.(A'+B')

D4=AB'+BA' {A.A'=B.B'=0}**

• I find it hard to follow this answer or understand what process you are using. Can you add some text sentences to explain the approach, so this isn't just a sequence of equations? – D.W. Nov 12 '15 at 7:37