# formula !x using only x and NAND

Hi how would I get formula that is equivalent to NOT X, using only the variable X and the NAND connective?

Regards

J

• Why is this question tagged "calculus"? Logical calculus of propositions, perhaps? Perhaps someone who knows how could re-tag; or tell me how. Oct 26, 2013 at 19:18
• @RobertLewis To retag, just click the "Edit" button below the post. Oct 26, 2013 at 19:21
• @NicholasR.Peterson: OK, thanks, will do! Oct 26, 2013 at 19:23
• @NicholasR.Peterson: Done! and thanks again! Oct 26, 2013 at 19:24
• @User103388: I re-tagged your question; hope it's OK! Regards, RKL Oct 26, 2013 at 19:25

Since $\operatorname{NAND}(A, B) = \neg (A \wedge B)$, and $A \wedge A = A$,

we have $\neg X = \neg(X \wedge X) = \operatorname{NAND}(X, X)$ !

Hope this helps! Cheerio,

and as always,

Fiat Lux!!!

• Man, I sure wish I had a buck for every time I used this trick when I was digital circuit/logic designer, back when the Code of Hammurabi was first carved in cuneiform! Oct 26, 2013 at 19:35
• NB: The final "!" in the above is exactly that, an exclamation point, not to be confused with a (conceivably misplaced) logical connective! ;) Oct 26, 2013 at 19:52
• haha! (on a different note: had you made it even-numbered, it wouldn't matter!) Oct 26, 2013 at 19:54
• What's the difference (in principle; ignoring matters of physical nature) between an even sequence of NOT gates and a piece of wire? Oct 26, 2013 at 20:14
• @HunanRostomyan: Gotcha! ROFL!!! Oct 26, 2013 at 20:15

The truth table for NOT x goes as follows:

 x  NOT
F   T
T   F


The truth table for NAND(x, y) goes as follows:

 x\y   F   T
F    T   T
T    T   F


Now just observe the diagonal:

 x\y   F   T
F    T
T        F


In other words, we have that NAND(F, F)=T, and NAND(T, T)=F. Thus, if p=q, NAND(p, q)=NOT(p)=NOT(q)=NAND(p, p)=NAND(q, q). So, NAND(x)=NOT(x).