3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Why "false atomic sentence" ? $\endgroup$ – Mauro ALLEGRANZA Mar 30 '17 at 15:42
  • $\begingroup$ @MauroALLEGRANZA You mean why in the Lemma I don't say that $\phi$ is true iff $\phi$ contains an even number of true atomic statements? Because if you take $A \equiv B \equiv C$ and $A$ and $B$ are true and $C$ is false, then $\phi$ contains an even number of true atomic sentences, but $\phi$ itself is false. $\endgroup$ – Bram28 Mar 30 '17 at 16:07
  • $\begingroup$ @MauroALLEGRANZA Hmm, I am still not quite seeing what you are getting at, sorry! That claim you mention is not a rephrasing of anything .. it is just a claim I make and prove. And once I have proven that, I use that to prove the claim the OP had to prove. Maybe it helps if I rephrase the Clima as Lemma, given that in the second proof I refer to it as the Lemma as well? $\endgroup$ – Bram28 Mar 30 '17 at 21:57
  • 1
    $\begingroup$ @MichelleGarcía under the assumption that each atomic variable has an even number of instances (e.g there are an even number of $P$'s, an even number of $Q$'s, etc) you cannot possible have an odd number of false ones, for as soon as I set one $P$ to false, all of them, and thus an even number of them, are set to false. $\endgroup$ – Bram28 Oct 31 '17 at 12:40
  • 1
    $\begingroup$ @MichelleGarcía yes. COnsider $P \equiv (P \equiv Q)$ . It has two variables, $P$ and $Q$, but it has three instances of a variable, two of $P$ and one of $Q$ $\endgroup$ – Bram28 Oct 31 '17 at 23:04
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.