# Proving the universality of NAND using structural induction

I need to prove that every formula in propositional logic has an equivalent formula that uses only NAND operator by using structural induction. I know how to rewrite formulas with simple operators (NOT, AND, OR) into NAND, which I wrote below, but have no idea how should I proceed with the structural induction.

NOT A = A NAND A
A AND B = (A NAND B) NAND (A NAND B)
A OR B = (A NAND A) NAND (B NAND B)

I guess my base case would be to prove the negation operator and in inductive step somehow the AND and OR operators and say that every formula can be constructed using only these three operators. However, my idea might be completely wrong.

The set of formulas is defined inductively by:

• For every variable $p$, $p$ is a formula
• If $f$ is a formula, NOT $f$ is a formula
• If $f$ and $g$ are formulas, $f$ AND $g$ is a formula
• And so on...

If you have a property $P(f)$ on formulas, to prove it by structural induction, you need to prove that:

• For every variable $p$, $P(p)$
• If $f$ is a formula so that $P(f)$, then $P($NOT $f)$
• If $f$ and $g$ are formulas so that $P(f)$ and $P(g)$, then $P(f$ AND $g)$
• And so on...

(So the base case is the variable, not the NOT)

In your case, $P(f)$ is "There is a formula equivalent to $f$ that contains only variables and NAND"

Now, depending what in in the "And so on...", you may need to do many cases. But if you have already proved that "For every formula $f$, there is an equivalent formula using only AND, OR and NOT", then you only need to handle those cases and variables. The reason for that is that if I give you a formula $f$ and want an equivalent formula that contains only NAND, I can first find a formula $g$ equivalent to $f$ that contains only AND, NOT and OR and then define my formula with only NAND by induction on $g$.

By the way, Post has completely characterized the sets of functions that allow you to express all boolean function: https://en.wikipedia.org/wiki/Post's_lattice (He characterized sets that are closed under composition, and then ordered them by inclusion, and being complete means not being included in an set closed by composition except the one containing all functions)

• Thanks! However, how would I show the base case scenario? Let's assume p is an atomic formula then the way I would show this is just rewriting p using nand like p = NAND(p NAND p)? Mar 26, 2017 at 16:47
• @Chilcone Your $P(f)$ is "there is a formula equivalent to $f$ written using NAND and atomic formulas (which I call variables)". So in the base case, there is nothing to do, you just leave the formula as is :-) Mar 26, 2017 at 16:49

It is enough to see that:

$p\rightarrow q \equiv (\sim p)\vee q$

$p\leftrightarrow q \equiv [(p\rightarrow q)\wedge (q\rightarrow p)]$

• Not really. $\to$ by itself isn't complete. How would you express the always false formula ? You can't because no matter what you do, if you have a formula with only $\to$ and variables, setting the rightmost variable to true will make your formula true. | And I'm not sure he has trouble finding such expressions, it looks like he's more interested in the methodology. Mar 26, 2017 at 15:33