The NAND gate. One gate to rule them all

Re:The NAND gate. One gate to rule them all by pbsd on Tuesday October 05, 2021 @07:14AM (#28757864)

Any boolean function can be represented as a polynomial over the integers modulo 2 (that is, its algebraic normal form).

Modulo 2, AND is multiplication and XOR is addition. We also have the useful properties 1+1=0, x+x=0, and x^2 = x. Thus:

    NAND(0, 0) = 0*0 + 1 = 1

    NAND(x, y) = x*y + 1

    AND(x, y) = NAND(NAND(x, y), NAND(x, y)) = (x*y + 1)*(x*y + 1) + 1 = x*y + x*y + x*y + 1 + 1 = x*y

    XOR(x, y) = NAND(NAND(x, NAND(x, y)), NAND(y, NAND(x, y))) = (x * (x*y + 1) + 1) * (y * (x*y + 1) + 1) + 1 = (x*y + x + 1) * (x*y + y + 1) + 1 = x*y + x*y + x*y + x*y + x*y + x + x*y + y + 1 + 1 = x + y

Since both AND and XOR can be obtained from NAND, any polynomial can be constructed. It also becomes obvious that you can't get x*y from x+y and vice-versa, so neither XOR nor AND can be universal gates on their own.

NOR's algebraic form is x*y + x + y + 1, from which you can similarly derive AND and XOR. XNOR is x + y + 1, from which AND cannot be obtained.

[ Parent | on HN ]

Re:The NAND gate. One gate to rule them all by eynsham on Tuesday October 05, 2021 @08:01AM (#28758223)

Ah yes, this is probably a more intuitive way of doing things than in my comment (though of course we prove different things).⁰ I should add that for those interested, the SEP page on algebraic propositional logic is quite interesting, although I regrettably have not actually gotten round to working through it.¹

0: https://news.ycombinator.com/item?id=28756727

1: https://plato.stanford.edu/entries/logic-algebraic-propositi...

[ Parent | on HN ]