Logic Gates and De Morgan's law for "$a \text{ AND } b$"

Question

How can I prove that $(a \text{ NAND } b) \text{ NAND } (a \text{ NAND } b ) \equiv a \text{ AND } b $?

So far I came up with a truth table for all the possibility combinations for the left side of the equation and the right side of the equation. I can see that if the a's and b's were all the same on the left side then I could prove the right side, but I don't know what happens when one of the a's or b's on the left side is different, what happens to the right side?

How can I use De Morgan's law to prove this or any other methods? Thanks.

Answer 1

Using De Morgan's law ($\,\overline{xy}\equiv \overline x+\overline y$), we have $$ \overline{\overline{ab}\cdot\overline{ab}} \equiv \overline{\overline{ab}}+\overline{\overline{ab}} \equiv ab. $$

Answer 2

We can use $\uparrow$ to represent "NAND":

Assume that $x \in \big((a \uparrow b) \uparrow (a \uparrow b)\big) \iff x \in \bigg(\neg\big(\neg(a \wedge b) \wedge \neg(a \wedge b)\big)\bigg)$

Using De Morgan's law:

$\hspace{66.5 mm} \iff x \in \Bigg(\neg\bigg(\neg\big((a \wedge b) \vee (a \wedge b)\big)\bigg)\Bigg)$

$\hspace{66.5 mm} \iff x \in \Big(\big((a \wedge b) \vee (a \wedge b)\big)\Big)$

$\hspace{66.5 mm} \iff x \in \big(a \wedge b\big) \hspace{5 mm}$ (Q.E.D.)

Answer 3

Your truth table needs to show the third and last columns are the same (true when true and false when false): $$\def\nand{\operatorname{N\!A\!N\!D}}\def\true{\mathrm{T}}\def\false{\mathrm{F}}\boxed{\begin{array}{c:c|c:c|l}a & b & a\land b & a\nand b &(a\nand b)\nand(a\nand b)\\ \hline \true & \true & && \\ \hdashline \true & \false & && \\ \hdashline\false & \true & && \\ \hdashline\false& \false &&& \\ \hline && \uparrow && \uparrow\end{array}}$$

Why doesn't yours?