A is a proposition formula that contains only iff. A is a tautology iff each atomic proposition in A appears an even number of times.

Solution 1:

I think you're on the right track. You can use induction to prove the following:

Lemma

Any statement $\phi$ built up from atomic statements and $\equiv$’s alone is true if and only if it contains an even number of instances of false atomic statements

Proof by structural induction on syntactical formation of $\phi$:

Base: $\phi = A$ for some atomic A. So it would be True iff A is True, i.e. iff $\phi$ contains an even number (0) of instances of false atomic statements. Check!

Step: Consider any statement $\phi \equiv \psi$. Assume the inductive hypothesis holds for $\phi$ and $\psi$. Now: $\phi \equiv \psi$ is true iff either both $\phi$ and $\psi$ are true or both are false iff (inductive hypothses) either both $\phi$ and $\psi$ contains an even number of instances of false atomic statements or both $\phi$ and $\psi$ contain an odd number of instances of false atomic statements iff $\phi \equiv \psi$ contains an even number of instances of false atomic statements. Check!

OK, so now we can prove what you need to prove:

Theorem

Any statement $\phi$ built up from atomic statements and $\equiv$’s alone is a tautology if and only if each atomic proposition that appears in $\phi$ appears an even number of times.

Proof:

'if': If each atomic proposition that appears in $\phi$ appears an even number of times, then $\phi$ contains an even number of instances of false atomic statements, regardless of whether you set any of the atomic propositions to True or False. Hence by the Lemma, $\phi$ will always be true, i.e. $\phi$ is a tautology.

'only if' Proof by contradiction: Suppose $A$ is some atomic statement that occurs an odd number of times in $\phi$. Then if we set $A$ to False, and all other atomic statements in $\phi$ to True, we would end up with an odd number of instances of false atomic statements in $\phi$, so by the Lemma this meas that $\phi$ is False, and hence not a tautology. So, if $\phi$ is a tautology, any atomic proposition that appears in $\phi$ must appear an even number of times.