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.

Question

I just started to study Mathematical Logic and I am having trouble finding a simple proof of the following exercise.
Let A be a propositional formula that contains only the $\equiv$ connective. For those who are not familiar with it $f_\equiv(T,T)=f_\equiv(F,F)=T$ and $f_\equiv(F,T)=f_\equiv(T,F)=F$.
Show that A is a tautology if and only if each atomic proposition that appears in A appears an even number of times.
I have managed to find a complicated proof using inductions and the fact that $\equiv$ is both commutative and associative but I don't believe this was the point of the exercise. Any help would be appreciated.

Answer 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.

Answer 2

I'd prove the commutative property, the associative property, that ($\alpha$ iff $\alpha$) = T, and ($\alpha$ iff T) = $\alpha$.

Then it follows that any formula with an even number of instances of an atomic sentences, that you can using commutation and association to eliminate those two into a T. So, any formula with an even number of instances of atomic sentences has truth value of T.

Conversely, every formula can get built up starting from T, making it into say (p iff p), then ((q iff q) iff p) and so on and then using commutation and association to construct the formula.