1

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?

user107952
  • 20,508

1 Answers1

2

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.$

Oscar Lanzi
  • 39,403
  • But p nand (not p) represents a unary function. Granted, the unary function is constant, but it is still a unary function, not a nullary function. I think most universal algebra textbooks only consider the set of all non-nullary functions on a set. – user107952 Dec 05 '20 at 18:04