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)