What is the intuition behind the formula $p \leftrightarrow (q \leftrightarrow (r \leftrightarrow ...))$?

61 Views Asked by At

I cooked up the formula $p \leftrightarrow (q \leftrightarrow (r \leftrightarrow ...))$ and naively thought it is a sort of "equivalence" relation. It turns out I am wrong. Suppose you have four variables in total, setting everything to false will make the formula true. However, if you have five variables, setting all variables to false will make the formula false! Having looked at a few experiments on truth tables, I nevertheless failed to find an easy intuition, but I am intrigued by the gap between the formula's simple construction and illusive patterns. I feel something is there but I couldn't grok it.

One thing I noticed include the fact that $\leftrightarrow$ is associative and commutative, so you can shift the variables around. Maybe this helps?

1

There are 1 best solutions below

3
On BEST ANSWER

Let one have the finite sequence of boolean values $p_1, \cdots, p_n$. S/he takes any two among them (say, $p, q$), remove two of them, and add $p \iff q$. This decreases the length of sequence by 1, so by $n-1$ step s/he gets to the final result.

On each step, since $T \iff T$ is true, $F \iff F$ is true and $T \iff F$ is false, the parity of Falses among $p_1, \cdots, p_n$ does not changes. So, by any choice of each steps, the parity of False after final consequence is the parity of number of Falses among initial state.