Proving the universality of NAND using structural induction

Question

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.

Answer 1

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)

Answer 2

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)]$