How Is XOR Implemented Using Only NAND Gates?

[Lomion]

An example in the book asks us to implement the XOR (exclusive-or) function using only 2-input NAND gates.

So:

f = x_1 \overline{x_2} + \overline{x_1}x_2

If we let \uparrow represent the NAND function. That means that: f = (x_1 \uparrow \overline{x_2}) \uparrow (\overline{x_1} \uparrow x_2)

I follow everything up to that step. And then they attempt to decompose it by manipulating one of the terms.

(x_1 \uparrow \overline{x_2} ) = \overline{x_1 \overline{x_2}} = \overline{x_1 (\overline{x_1} + \overline{x_2})} = x_1 \uparrow (\overline{x_1} + \overline{x_2}) = x_1 \uparrow (x_1 \uparrow x_2)

Can anyone please explain what exactly went on in that step? How did they go from the second equation to the third, and then the fourth? I understand the first and final steps, but that's it.

Any help would be greatly appreciated!

 

[AKG]

Can anyone please explain what exactly went on in that step? How did they go from the second equation to the third, and then the fourth? I understand the first and final steps, but that's it.

Draw truth tables. If the left side of the second equation has the same truth table as the right side, you know it works. Also, if you have a text, see if they have some general laws that may have used in going from the first to second equation. Or, it shouldn't be too hard (using truth tables) to generalize some "laws" for yourself.

 

[Janitor]

A variable AND its negation is always false. A variable OR false is just the variable itself. Those ideas plus DeMorgan's Law are being applied here.

 

[ehild]

(x_1 \uparrow \overline{x_2} ) = \overline{x_1 \overline{x_2}} = \overline{x_1 (\overline{x_1} + \overline{x_2})} = x_1 \uparrow (\overline{x_1} + \overline{x_2}) = x_1 \uparrow (x_1 \uparrow x_2)

Can anyone please explain what exactly went on in that step? How did they go from the second equation to the third, and then the fourth? I understand the first and final steps, but that's it.

Any help would be greatly appreciated!

To get the third equation from the second

\overline{x_1 \overline{x_2}} = \overline{x_1 (\overline{x_1} + \overline{x_2})}

it was used that x_1 \overline{x_1}=0

The fourth equation came from the third

x_1 \uparrow (\overline{x_1} + \overline{x_2}) = x_1 \uparrow (x_1 \uparrow x_2)

by using Morgan's rule

\overline{x_1} + \overline{x_2}= \overline {x_1 x_2} = x_1\uparrow x_2

ehild

 

[smh62]

You could draw a truth table to verify but I think you'll get more mileage from an intuitive understanding of the reasoning. Here goes:

Ignoring one of the negations in the second expression we can just consider this conjunction: x_1 \overline{x_2}

If x_1 is false then the whole conjunction is false regardless of \overline{x_2}. If however x_1 is true then the truth of the whole conjunction depends on \overline{x_2} being true. I don't alter this dependence in any way if I replace \overline{x_2} with a disjunction with any false expression:

<br /> x_1 \overline{x_2}<br /> = x_1 (\bold{F} + \overline{x_2})<br />

In this context, I can actually guarantee that \overline{x_1} is false whenever \overline{x_2} is relevant to evaluation. This guarantee comes from the observation that \overline{x_2} is relevant only if x_1 is true in which case \overline{x_1} must be false. Therefore:

<br /> x_1 \overline{x_2}<br /> = x_1 (\bold{F} + \overline{x_2})<br /> = x_1 (\overline{x_1} + \overline{x_2})<br />

Hope that clears up why the second step is valid. The third step is just replacing a negated conjunction with a NAND which is valid by definition.

<br /> (x_1 \uparrow \overline{x_2} )<br /> = \overline{x_1 \overline{x_2}}<br /> = \overline{x_1 (\overline{x_1} + \overline{x_2})}<br /> = x_1 \uparrow (\overline{x_1} + \overline{x_2})<br /> = x_1 \uparrow (x_1 \uparrow x_2)<br />