Sheffer function

Remarks

Example: NAND, $x \uparrow y = \neg(x \wedge y)$ on $\set{0, 1}$, is a Sheffer function. Check: $\neg x = x \uparrow x$ and $x \wedge y = \neg(x \uparrow y)$, and $\set{\wedge, \neg}$ is functionally complete. Non-example: $\wedge$ on $\set{0, 1}$ is not a Sheffer function. Every operation generated by $\wedge$ maps $(0, \dots, 0)$ to $0$, so $\neg$ is not generated. NOR, $x \downarrow y = \neg(x \vee y)$, is the only other binary Sheffer function on $\set{0, 1}$. A Sheffer function must have arity at least $2$, since a unary operation generates only essentially unary operations.