The n-ary versions of NOR and NAND

Question

This is really two questions in one. Let $n$ be a natural number greater than or equal to $3$. The $n$-ary NOR is defined to be the $n$-ary operation on $\{0,1\}$ which outputs $1$ when all $n$ arguments are $0$, and outputs $0$ otherwise. The $n$-ary NAND is defined dually. My first question is, for each natural number $n \geq 3$, does the $n$-ary NOR and also the $n$-ary NAND operations generate all operations on $\{0,1\}$? My second question is, for each natural number $n \geq 3$, are the $n$-ary NOR and the $n$-ary NAND operations the only $n$-ary operations which generate, by themselves, all operations on $\{0,1\}$?

Answer 1

The answers are: Yes and No.

Let $A= \{0,1\}$ and let $\neg \colon A\to A$ be the negation operation ($\neg 0=1$ and $\neg 1=0$). A single $n$-ary operation $f(x_1,\ldots,x_n)$ on $A$ generates all operations on $A$ if and only if:

• $f(x,x,\ldots,x) = \neg x$ for $x\in A$, and
  
• $f$ does not commute with $\neg $. (This means: there exists $\bar{a}\in A^n$ such that $\neg f(a_1,\ldots,a_n)\neq f(\neg a_1,\neg a_2,\ldots,\neg a_n)$.)

You can derive this fact from the main result of

Completeness in finite algebras with a single operation
G. Rousseau.
Proc. Amer. Math. Soc. 18 (1967), 1009-1013

The number of $n$-ary operations on $A=\{0,1\}$ which satisfy both conditions is $2^{(2^n-2)}-2^{(2^{n-1}-1)}$. Thus, there are $0$ unary operations on $A$ that generate all operations on $A$, $2$ binary operations on $A$ that generate all operations on $A$ (NAND and NOR), $56$ ternary operations on $A$ that generate all operations on $A$, ETC. One example of a ternary operation on $A$ that generates all operations on $A$, and which is different from NAND and NOR, is NOR$(x_1,x_2,x_3)\vee (x_1\wedge x_2\wedge \neg x_3)$.