NAND and NOR are Functionally Complete
Jump to navigation
Jump to search
Theorem
The NAND and NOR operators are each functionally complete.
That is, NAND and NOR are Sheffer operators.
Proof
In NAND is Functionally Complete it is demonstrated that NAND is functionally complete.
In NOR is Functionally Complete it is demonstrated that NOR is functionally complete.
Historical Note
This result is specifically documented here because of its historical and scientific significance.
It was proved in $1913$ by Henry Sheffer, after whom the symbol $\uparrow$, the Sheffer stroke, is named after.
However, it later transpired that Charles Sanders Peirce had noticed the same result in $1880$, but the paper in which this appeared was not published until $1933$.