Thread: Logic: formulas, proof

Hello!
I have just started learning logic and have to idea how to solve this, can anyone help with ideas please?

Prove that a formula that contains only variables and equivalence and negation as operations is identically true if and only if the number each variable and operation of negation appears in the formula is even.

Thank you in advance!

Interesting problem. An obvious idea is to try proving this by induction on formulas. However, as often happens, one needs a stronger induction statement because in a formula A <-> B, A and B separately don't have to be tautologies or contain even number of occurrences of each variable even if the whole formula does this. So the challenge is to come up with a generalization of the claim that will let induction go through.

I'll denote truth values by T and F. Let is call a formula A(p) containing a variable p stable with respect to p if for all values of other variables, A(T) and A(F) have the same truth values, i.e., A(T) <-> A(F) is a tautology. Similarly, A(p) is called unstable w.r.t. p if for all values of other variables, A(T) and A(F) have the opposite truth values, i.e., A(T) <-> A(F) is a contradiction. Note that if A is not stable w.r.t. p, it does not necessarily follow that it is unstable w.r.t. p.

Lemma 1. Let a formula A(p) be built from variables, truth values, equivalences and negations only. Then A is stable w.r.t. p if the number of occurrences of p is even, and A is unstable w.r.t. p if the number of occurrences of p is odd.

Proved by induction on A.

Corollary. If a formula as above contains even number of occurrences of every variable, then it is either a tautology or a contradiction.

Lemma 2. A formula built from T, equivalences and negations only is true iff it contains an even number of negations.

Proved by induction.

From this the claim follows.

Thank you! I appreciate it.