3

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?

user114579
  • 35
  • No, only equality and negation are allowed. You can easily make a theorem that is not tautology, for example $A \sim \neg A$. But in that case negation is used only once, which is an odd number, if we would have $A\sim \neg \neg A$, then that would be tautology and it would also fit the conditions set in this problem. – user114579 Dec 09 '13 at 20:20
  • I'm sorry. I'm not studying this subject in english. I think it should be correct now. – user114579 Dec 09 '13 at 20:31
  • You haven't said anything about parentheses. Are those allowed? If not, how do you interpret something like $a\land b \lor c$? – dfeuer Dec 09 '13 at 21:34
  • Also, you seem to assume only one variable, $A$; a statement like $a\iff b$ is not a tautology. – dfeuer Dec 09 '13 at 21:36
  • Amount of variables must be even number, for example $A\sim A \sim \neg B\sim \neg B$. I think parentheses are not needed as only negation and equality are allowed. – user114579 Dec 09 '13 at 22:19
  • I don't understand what $A\sim A\sim \neg B\sim \neg B$ is supposed to mean. – dfeuer Dec 09 '13 at 22:30
  • You can construct a truth table for $A$ and $B$ and see that it's tautology. – user114579 Dec 09 '13 at 22:33

1 Answers1

3

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.

dfeuer
  • 9,069
  • It's perhaps easier to just talk about an even number of letters in formula, or maybe an even number of symbols which are not symbols for connectives. – Doug Spoonwood Dec 10 '13 at 04:44
  • @DougSpoonwood, how is that relevant? $a\iff b$ has an even number of letters, but is not a tautology. – dfeuer Dec 10 '13 at 05:37
  • You're right. I should have said an even number of instances of the same (or equiform) letter (s). – Doug Spoonwood Dec 10 '13 at 19:21