I would strongly suggest structural induction. That is, rather than using some unnecessarily convoluted way of doing induction on the length of the statement or number of operators, you can simply follow the recursive definition of statements, which is:
- All propositional variables are statements
2a. If $\psi$ is a statement, then $\neg \psi$ is a statement
2b. If $\psi_1$ and $\psi_2$ are statements, then $\psi_1 \land \psi_2$ is a statement
2c. If $\psi_1$ and $\psi_2$ are statements, then $\psi_1 \land \psi_2$ is a statement
- Nothing else is a statement
Structural induction mirrors this very recursive definition. That is, in order to show that all statements have some property, show that:
Base: Show that all propositional variables have the property
Step:
a. Show that $\neg \psi$ has the property assuming that $\phi$ has the property
b. Show that $\psi_1 \land \psi_2$ has the property assuming that $\psi_1$ and $\psi_2$ have the property
c. Show that $\psi_1 \land \psi_2$ has the property assuming that $\psi_1$ and $\psi_2$ have the property
If we can show these things, and given that nothing else is a statement (that is why 3 in the definition is important to have), we can conclude that all statements haven the property in question.
Also, make sure to clearly and explicitly state what you are trying to prove. Here is what you are trying to prove:
CLAIM
For all statements $\phi$ it is true that $\phi' \Leftrightarrow \neg \phi$
Note that I use $\Leftrightarrow$ here, because that is the symbol typically used for logical equivalence. The $=$ is often used to indicate that some statement is syntactically identical to some other statement, which is not the same as logical equivalence. For example, $P \land Q \Leftrightarrow Q \land P$, but they are not the same symbol string, i.e. $P \land Q \not = Q \land P$
OK, so let's apply structural induction to your problem:
Base case: $\phi$ is some atomic formula $P$. Then $\phi' = P' = \neg P = \neg \phi$, and therefore certainly $\phi' \Leftrightarrow \neg \phi$. Check!
Step: Take any complex $\phi$, i.e. $\phi = \psi_1 \land \psi_2$, $\phi = \psi_1 \lor \psi_2$, or $\phi = \neg \psi$
Let's just do the $\phi = \psi_1 \land \psi_2$ case.
By inductive hypothesis we have $\psi_1' \Leftrightarrow \neg \psi_1$, and $\psi_2'\Leftrightarrow \neg \psi_2$
So then:
$$\phi'=(\psi_1 \land \psi_2)'=(\psi_1' \lor \psi_2') \overset{I.H.}{\Leftrightarrow} (\neg \psi_1 \lor \neg \psi_2) \overset{D.M.}{\Leftrightarrow} \neg (\psi_1 \land \psi_2) = \neg \phi$$
Do you see now how the inductive hypothesis was used?
Let $\varphi$ be some sentence in the language you just described. We prove by induction on the complexity of $\varphi$ that either $\Gamma \vdash \varphi$ or $\Gamma \vdash \neg \varphi$.
The base case is just atomic sentences. That is, $\varphi$ is of the form $S_i$ for some $i$ (or maybe $\top$ or $\bot$, depending on your definitions). So this case is covered by the assumption that either $S_i \in \Gamma$ or $\neg S_i \in \Gamma$, which translates into $\Gamma \vdash S_i$ or $\Gamma \vdash \neg S_i$.
If you want to try the rest of the induction for yourself, you may want to consider to stop reading here.
There are two induction steps: one where $\varphi$ is of the form $\neg \psi$ and one where $\varphi$ is of the form $\psi_1 \lor \psi_2$. Let us consider each case.
If $\varphi$ is of the form $\neg \psi$, then by induction hypothesis we have $\Gamma \vdash \psi$ or $\Gamma \vdash \neg \psi$. In the first case we thus have $\Gamma \vdash \neg \varphi$, and in the second case we find $\Gamma \vdash \varphi$. So again, either $\Gamma \vdash \varphi$ or $\Gamma \vdash \neg \varphi$.
If $\varphi$ is of the form $\psi_1 \lor \psi_2$, we can again use the induction hypothesis to find a two different cases. The first case is that $\Gamma \vdash \psi_1$ or $\Gamma \vdash \psi_2$ (or both), which gives us $\Gamma \vdash \varphi$. The other case is that $\Gamma \vdash \neg \psi_1$ and $\Gamma \vdash \neg \psi_2$, which means that $\Gamma \vdash \neg \varphi$. Once more concluding that indeed $\Gamma \vdash \varphi$ or $\Gamma \vdash \neg \varphi$.
This completes the induction, and so we can conclude that $\Gamma$ is complete.
Best Answer
Say that an $n$-place Boolean function $G$ is realized by a wff $\alpha$ whose atomic sentence symbols are $A_1,...,A_n$ if $G(X_1,...,X_n)$ is equal to the truth value of $\alpha$ when $A_1,...,A_n$ are given the truth values $X_1,...,X_n$ respectively.
The key to answering your question is the following result.
Theorem. Every $n$-place Boolean function $G$ is realized by some $\alpha$.
Proof. If $G$ is constantly false then $A_1 \wedge \neg A_1$ realizes $G$. Otherwise, suppose there are $k$ points at which $G$ is true: $$X_1 = (X_{11},...,X_{1n}),...,X_k=(X_{k1},...,X_{kn}).$$
Now let $\beta_{ij}$ be $A_j$ or $\neg A_j$ according as $X_{ij}$ is true or false. Let $\gamma_i = \beta_{i1} \wedge ... \wedge \beta_{in}$ and let $\alpha = \gamma_1 \vee ... \vee \gamma_k$. Now check that $\alpha$ realizes $G$ (I leave this to you as an instructive exercise). QED
Remark. Notice that $\alpha$ in the foregoing proof is in DNF. From this observation and the theorem just proved, we see that $\{\vee, \wedge, \neg \}$ is adequate.
Finally, we have
Theorem. The set $\{\vee, \neg \}$ is adequate.
Proof. Let $\alpha$ be a wff using only connectives in $\{\vee, \wedge, \neg \}$. We can show by induction on $\alpha$ that there is a tautologically equivalent wff $\alpha '$ using only connectives in $\{\vee, \neg \}$. And from this it follows that $\{ \vee, \neg \}$ is adequate, since if $\alpha$ realizes $G$ and $\alpha \equiv \alpha '$, then $\alpha '$ realizes $G$ too.
The base case in which $\alpha$ is an atomic sentence symbol is trivial (let $\alpha '$ be $\alpha$).
For the inductive step, first suppose $\alpha$ is $\neg \beta$. Then let $\alpha '$ be $\neg \beta '$.
Second, suppose $\alpha$ is $\beta \wedge \gamma$. Then let $\alpha '$ be $\neg(\neg \beta ' \vee \neg \gamma ')$. It's easy to check that $\alpha \equiv \alpha '$. QED