Neither NAND nor NOR generates all n-ary functions on $\{0,1\}$

50 Views Asked by At

It is said that NAND alone can generate all $n$-ary functions on $\{0,1\}$, for all natural numbers $n$. However, I think the correct statement is that it can generate all $n$-ary functions, where $n\geq 1$. I don't think it generates the nullary functions $0$ and $1$ themselves. So, then, why do logic books make this error? Shouldn't they say that $\{NAND, 0\}$, rather than NAND alone, is functionally complete?

1

There are 1 best solutions below

1
On

For all propositions $p$ we may render

$p\text{ nand }p=\text{not }p$

$p\text{ nand }(\text{not }p)=1$

$1\text{ nand }1=0.$