Prove formula's tautology

Question

Prove that a formula that only consists of variables, logical negation and logical equality, and in which all variables and negation appear for an even number of times, must be tautological.

Answer 1

Consider the truth table of negation and biconditional (what you have called logical equality) $$\begin{array}{c|c|c|c} p & q & \neg p & p \leftrightarrow q \\ \hline 1&1&0&1\\ 1&0&0&0\\ 0&1&1&0\\ 0&0&1&1 \end{array}$$

We can define \begin{align} p \leftrightarrow q \quad &:= \quad p+q+1 \text{(mod 2)}\\ \neg p \quad &:= \quad p+1 \text{(mod 2)} \end{align}

Now we can translate any formula of propositional logic which contains only the connectives negation and biconditional, into an algebraic expression. Note that since we are working in mod 2, $p+p=2p=0$ (because 2=0).

Now it should be straightforward to prove the statement in the question.