Tautologies in Boolean formulas using the bi-conditional connective How can I prove a formula $\phi$ written using only the bi-conditional connective $\leftrightarrow$ (besides variables and parentheses) is a tautology if and only if every variable in $\phi$ occurs an even number of times?
I have attempted to prove this by using the fact that $p \leftrightarrow q \equiv (p \rightarrow q ) \wedge (q \rightarrow p)$ and by generalizing my proof for the fact that $(...((p\rightarrow p)\rightarrow p)\rightarrow...)\rightarrow p$ is a tautology if and only if $p$ occurs an even number of times, but I did not succeed. Would induction be a good choice for this proof?
 A: Show by induction that:


*

*$\iff$ is associative: in an expression built only using variables, "$\iff$," and parentheses, you can rearrange the parentheses however you like. (E.g. "$x\iff (y\iff z)$" is equivalent to "$(x\iff y)\iff z$.")

*$\iff$ is commutative: "$x\iff y$" can always be replaced with "$y\iff x$".
Once you have these two facts, then you can show:

Any $\iff$-formula in which every variable appears an even number of times is equivalent to one of the form $$(x_0\iff x_0)\iff (x_1\iff x_1)\iff . . . \iff (x_n\iff x_n),$$ which is a tautology since "$x\iff x$" is a tautology.

This completes one half of the problem. For the other half:

If $\varphi$ is a $\iff$-formula in which some variable $x$ occurs an odd number of times, consider the valuation which makes every variable but $x$ true, and makes $x$ false; you can show by induction that this makes $\varphi$ false, so $\varphi$ is not a tautology.

A: I have a somewhat different approach.
First, we'll take Epp as an axiom (I use Polish notation).  We have four rules of inference:


*

*Wherever any instance of E$\alpha$E$\beta$$\gamma$ appears within a formula, we can replace it with EE$\alpha$$\beta$$\gamma$ and conversely (association).

*Wherever any instance of E$\alpha$$\beta$ appears in a formula, we may replace that instance with E$\beta$$\alpha$ (commutation).

*We may uniformly substitute any small letter $\lambda$, $\top$, or $\bot$, in any formula $\phi$ only have E's in it with some formula $\psi$, provided that for each instance of the letter $\lambda$, $\top$, or $\bot$, it gets substituted with $\psi$ in $\phi$.

*From E$\alpha$$\beta$, as well as $\alpha$, we may infer $\beta$.


Now, with Epp as an axiom, the above four rules allow us to infer all instances of formulas having every variable appearing in a formula $\phi$ an even number of times.  Note that Epp is a tautology, and each of the above four rules qualifies as tautology preserving, so
Meta-Claim 1: This system only produces tautologies.  (Soundness of the above formulation of the equivalential calculus.)
Now, we'll suppose that we can infer some formula $\chi$ having an odd number of at least one variable in $\chi$ to the above.  We proceed as follows:


*

*If there exists two instances of some variable in $\phi$ we use rules 1. and 2. (association and commutation), until it has the form EE$\gamma$$\gamma$$\delta$.  Then we substitute in the axiom Epp, and use rule 4. to detach $\delta$.

*If $\delta$ only has variables which appear an odd number of times in $\delta$, then stop.  Otherwise, set $\chi$ to $\delta$ and go to step 1.


Now consider the following cases for $\delta$.


*

*$\delta$ is a propositional variable.  But, if we deduced p, we could substitute it with $\bot$.  By the above, it is not a tautology and not deducible in the above system.

*$\delta$ has three symbols.  We can then substitute $\top$ for the first symbol, and $\bot$ for the second symbol.  Similar to case 1., this is not a tautology, and thus not deducible in the above system.

*$\delta$ has more then three symbols.  In which case we then substitute $\top$ for the first small letter, $\bot$ for the second small letter, and $\top$ for every other small letter (any letter subscripted by a numeral qualifies as a small letter, as well as any small letter of the ABC's).  Whatever $\delta$ comes as since E$\top$$\bot$ evaluates to $\bot$ and E$\bot$$\top$ evaluates to $\bot$, $\delta$ evaluates to $\bot$.


1., 2., and 3. show that $\delta$ is never a tautology.  Since $\delta$ is never a tautology, $\chi$ is also never a tautology also.  Thus:
Meta-Claim 2: No instances of any formula $\phi$ having some variable appearing an odd number of times occurs in the above system.
Now, it's known that EEpqEErqEpr is a single axiom for all formulas using only the bi-conditional connective... see here for example: http://web.ics.purdue.edu/~dulrich/Single-axioms-for-EQ-page.htm
under rule 3. and rule 4.
I'll use the notation $\nu$ $\alpha$/$\beta$ to indicate that letter $\alpha$ gets uniformly substitute with $\beta$ in formula $\nu$ in the following.
axiom      1 Epp
1 p/EpEqr  2 E EpEqr EpEqr
2, rule 1. 3 EE Epq r EpEqr
3, rule 1. 4 E Epq E r EpEqr
4, rule 1. 5 EEpqEr E Epq r
5, rule 2. 6 EEpqEr EEqpr
6, rule 1. 7 EEpq Er Eq Epr
7, rule 1. 8 EEpq EErq Epr

Thus, EEpqEErqEpr is in the above system.  The above system also has the rule of detachment.  Therefore,
Meta-Claim 3: The above system produces all tautologies having only E in them (completeness).
Since the above system has all tautologies having only E in them (E-tautology hereafter), and since every formula in the above system has it's variables appearing an even number of times, it follows that:
Meta-Claim 4: For all variables in any E-tautology, those variables appear in that tautology an even number of times.
Thus,
If a formula $\phi$ is an E-tautology, then every variable in $\phi$ appears an even number of times.
And the other half of your statement follows also.
