Tautologies in Boolean formulas using the bi-conditional connective

Question

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?

Answer 1

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.

Answer 2

I have a somewhat different approach.

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

1. 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).
2. Wherever any instance of E$\alpha$$\beta$ appears in a formula, we may replace that instance with E$\beta$$\alpha$ (commutation).
3. 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$.
4. 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:

1. 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$.
2. 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$.

1. $\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.
2. $\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.
3. $\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.