Boolean Algebra with NAND

[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