I've been stuck on this question and I'm confused as to how to approach it:
Let $G$ be a set defined as follows:
- if $x$ is a propositional variable, then $x \in G$;
- if $f_1,f_2 \in G$, then $\lnot f_1 \in G$, and $(f_1 \land f_2) \in G$;
- nothing else belongs to $G$.
For a formula $f \in G$, let $c_{not}(f)$ be the number of occurrences of $\lnot$ in $f$, and $c_{and}(f)$ be the number of occurrences of $\land$ in $f$. Let $H = \{f \in G : c_{not}(f) = c_{and}(f)\}$. That is, $H$ is the set of formulas in $G$ with equal number of $\lnot$'s and $\land$'s.
Prove that for any formula $f \in G$, there is a formula $f'$ such that $f' \in H$ and $f'$ and $f$ are logically equivalent.
Here's an approach for part of the inductive part.
Suppose $\neg f$ is a formula in $G$. $f$ has a formula $f'$ which has the same number of $\neg$s as $\wedge$s. Now, you need to find a formula equivalent to $\neg f'$ with the same number of visible $\neg$s as visible $\wedge$s. (In the formula $\neg f'$, you have one visible $\neg$ and no visible $\wedge$s; I'm not counting the $\neg$s and $\wedge$s in $f'$, which balance by induction.)
Now, you just need to come up with a bunch of equivalent formulas to $\neg f'$; I'll try a few: $\neg\neg\neg f'$ (nope), $\neg f' \wedge \neg f'$ (nope), $\neg (f'\wedge f')$ ... and we have a winner! It has one visible $\neg$ and one visible $\wedge$, and since the $\neg$s and $\wedge$s balance in $f'$, we have the equivalent formula for $\neg f$ which is in $H$ as well.
Now you do $f\wedge g$.