The result of the bi-conditional $\leftrightarrow$ is true when n is odd and m is odd, and when n is even and m is even. Proof by induction

Question

Let m be the number of Truth values for each row, and let n be the size of the truth table. $2^n$. I discovered that the result of the bi-conditional $p1\leftrightarrow p2$ $\leftrightarrow p3$ is true when n is odd and m is odd.

I've also discovered that the result of the bi-conditional $p1\leftrightarrow p2$ $\leftrightarrow p3$ $\leftrightarrow p4$ is true when n is even and m is even.

How do I prove this using Induction? I know the base cases the truth table results with odd and even values. I'm having a hard time creating the formula that I would use to prove by Induction.

"The result of the bi-conditional is true when n is odd and m is odd"

Please Help!!!! :)

Answer 1

Proof sketch of the inductive step:

• Let $m_n$ be the number of true $p_i$ in the chained biconditional $(p_1\iff ... \iff p_n)$. Then your statement is equivalent to saying that the chained biconditional is true if and only if $m_n + n$ is even.

• The biconditional is associative, so we have the following equivalence $$ (p_1\iff ... \iff p_{n+1})\equiv [(p_1\iff ... \iff p_n) \iff p_{n+1}]. $$

• Assume that $(p_1\iff ... \iff p_n) \iff (m_n+n \mathrm{\,is\,even})$. Use the above equivalence to show that $(p_1\iff ... \iff p_{n+1}) \iff (m_{n+1} + n+ 1 \mathrm{\,is\,even})$.