# Prove that nand is functionally complete

Can anyone explain to me how to

Prove that nand is functionally complete.

(To wit: if we let $p ∗ q$ mean $¬(p ∧ q)$, show that the other connectives, $∧$, $∨$, $¬$ and $→$ are expressible in terms of $∗$.)

I understand that logical function on a fixed set of inputs has a finite number of cases, but unsure how to put that into context.

$¬p\equiv¬(p ∧ p)$

$p ∧ q\equiv¬(¬(p ∧ q))$

$p∨q\equiv¬(¬p ∧ ¬q)$

$p→q\equiv¬p∨q$

Therefore nand is functionally complete.

• Forgive me for being pedantic but shouldn't those equality signs be equivalence signs (ie. $\equiv$ ) instead? Commented Aug 2, 2018 at 6:18
• @DanielMak OK, I edited my post. Thanks!
– user529760
Commented Aug 2, 2018 at 6:31
• @DanielMak: That depends on context. In logic one usually keeps the $=$ sign reserved for equality between terms such that there won't be any confusion when we get to predicate logic -- but if one is doing Boolean algebra (or digital circuits or whatever) there's nothing wrong with using $=$ to assert equality between truth values as well. Commented Aug 2, 2018 at 8:38
• However, I would point out that this answer tacitly assumes that we already know $\{{\neg},{\land},{\lor},{\to}\}$ to be a functionally complete set. Hopefully the OP does already know that in his context. Commented Aug 2, 2018 at 8:41
• Functional completeness means that you can implement all truth tables. You only show a reduction but not functional completeness. Commented Oct 28, 2019 at 9:28

Two well-known basic facts:

Lemma 1: Every boolean function can be represented as a DNF.

Lemma 2: If $$A = \{f_1, ... f_n\}$$ if complete and every its function can be expressed in terms of functions from $$B = \{g_1, ... g_m\}$$, then $$B$$ is complete.

Lemma 1 $$\implies \{\lnot, \lor, \land\}$$ is complete. The following formulas

$$¬p\equiv¬(p ∧ p)$$

$$p ∧ q\equiv¬(¬(p ∧ q))$$

$$p∨q\equiv¬(¬p ∧ ¬q)$$

together with Lemma 2 imply that $$\{NAND\}$$ is complete.

• I do not follow. you have shown that $\{ \neg$, NAND } expresses functions, which set is complete. but why NAND alone is enough Commented Jul 13, 2023 at 10:50
• or you say, that you use $\neg$ after implementing it as NAND? Commented Jul 13, 2023 at 10:58
• @dEmigOd yes, take a look at the very first formula
– Sgg8
Commented Jul 13, 2023 at 10:59