Proving formula's tautology Prove that a formula that consists only of logical equality, logical negation and has even number of propositional variables and logical negations must be tautological.
I tried it out with couple of examples and it seems pretty obvious, but how should I approach proving this?
 A: Note: the notation in this answer is non-standard. Usually, $a\iff b \iff c$ is taken to mean $(a\iff b)\land(a\iff c)$. Here $\iff$ is used as a Boolean operator.
\begin{align*}
\bigl(a\iff(b\iff c)\bigr)
&\equiv \bigl((a\land b\land c)\lor (a\land\neg b\land \neg c)\lor (\neg a\land b\land \neg c)\lor(\neg a\land \neg b\land c)\bigr)\\
&\equiv\bigl((a\iff b)\iff c\bigr),
\end{align*}
so $\iff$ is associative. It's also (obviously) commutative.
Consider a proposition that looks like $p_1\iff p_2\iff\dotsb\iff p_n$, where $p_k$ is either a propositional variable or its negation, and where each variable appears an even number of times (either in the positive or the negative). By commutativity, we can gather all copies of each variable together, with the positives all together and the negatives all together.
If we have $a \iff a$ anywhere, we can replace it with "true", which will merge into the left or the right: $(a\iff a)\iff b$ is the same as $b$, and $b\iff (a\iff a)$ is also the same.
The same happens with $\neg a\iff \neg a$, and when this collapses it takes two negations with it.
So each variable either collapses altogether or is reduced to something like $a\iff\neg a$. But then $(a\iff \neg a)\iff(b\iff\neg b)$ will collapse to true, taking two negations with it. You can keep collapsing these pairs till you get down to nothing because you assumed an even number of negations.
So your original concept is almost right, but rather than an even number of variables, you need an even number of appearances of each variable.
