Claim 1: A truth assignment \(v\) satisfies the wff \begin{gather}(\cdots(A_1\leftrightarrow A_2)\leftrightarrow\cdots\leftrightarrow A_n)\end{gather} iff \(v(A_i) = F\) for an even number of \(i\)’s, \(1\leq i\leq n\). (By the associative law for \(\leftrightarrow\), the placement of the parentheses is not crucial.)

To prove this claim, we will need the following lemma.

Lemma: If \(v(A_1) = \cdots = v(A_m) = T\), then \(v\) satisfies \((\cdots(A_1\leftrightarrow A_2)\leftrightarrow\cdots\leftrightarrow A_m)\). We can observe this is true by replacing the sentence symbols with their truth values so that the wff becomes \((\cdots(T\leftrightarrow T)\leftrightarrow\cdots\leftrightarrow T)\), which clearly evaluates to a truth value of \(T\).

If \(v(A_1) = \cdots = v(A_{2m})\) for some \(m\in\mathbb{Z}_{\geq 1}\), then \(v\) satisfies \((\cdots(A_1\leftrightarrow A_2)\leftrightarrow\cdots\leftrightarrow A_{2m})\). We can observe this is true by replacing the sentence symbols with their truth values and applying the associative law so that the wff becomes \(((F\leftrightarrow F)\leftrightarrow\cdots\leftrightarrow(F\leftrightarrow F))\), containing \(m\) many expressions of \((F\leftrightarrow F)\). Since each \((F\leftrightarrow F)\) evaluates to a truth value of \(T\), we may replace each \((F\leftrightarrow F)\) with a \(T\) so that the wff becomes \((T\leftrightarrow \cdots\leftrightarrow T)\) with \(m\) many \(T\)’s. By the first part of this lemma, \((T\leftrightarrow\cdots\leftrightarrow T)\) will evalute to a truth value of \(T\), showing that \(v\) indeed satisfies \((\cdots(A_1\leftrightarrow A_2)\leftrightarrow\cdots\leftrightarrow A_{2m})\)

If \(v(A_1) = \cdots = v(A_{2m+1})\) for some \(m\in\mathbb{Z}_{\geq 0}\), then \(v\) does not satisfy \((\cdots(A_1\leftrightarrow A_2)\leftrightarrow\cdots\leftrightarrow A_{2m+1})\). We can observe this is true by replacing the sentence symbols with their truth values and applying the associative law so that the wff becomes \((F \leftrightarrow (F\leftrightarrow F)\leftrightarrow\cdots\leftrightarrow(F\leftrightarrow F))\), containing \(m\) many expressions of \((F\leftrightarrow F)\). Since each \((F\leftrightarrow F)\) evaluates to a truth value of \(T\), we may replace each \((F\leftrightarrow F)\) with a \(T\) so that the wff becomes \((F\leftrightarrow T\leftrightarrow\cdots\leftrightarrow T)\) with \(m\) many \(T\)’s. Applying the associatve law again the wff becomes \((F\leftrightarrow(T\leftrightarrow\cdots\leftrightarrow T))\). By the first part of this lemma, \((T\leftrightarrow\cdots\leftrightarrow T)\) will evalute to a truth value of \(T\), so that wff becomes \((F\leftrightarrow T)\) which clearly evalutes to \(F\). Thus, \(v\) does not satisfy \((\cdots(A_1\leftrightarrow A_2)\leftrightarrow\cdots\leftrightarrow A_{2m+1})\).

With the aid of this lemma we are ready to prove Claim 1.

Proof of Claim 1:

For the backwards direction, assume that \(v(A_i) = F\) for an even number of \(i\)’s, \(1\leq i \leq n\), say \(2m\) of them for some \(m\in\mathbb{Z}_{\geq 0}\). Since \(\leftrightarrow\) is commutative, we can reindex the \(A_i\) yielding the wff \begin{gather}(A_{k_1}\leftrightarrow A_{k_{2}}\leftrightarrow\cdots\leftrightarrow A_{k_n})\end{gather}where \(v(A_{k_1}) = \cdots = v(A_{k_{2m}}) = F\) and \(v(A_{k_{2m+1}}) = \cdots = v(A_{k_n}) = T\). This reordering yields a wff which is tautologically equivalent to \((\cdots(A_1\leftrightarrow A_2)\leftrightarrow\cdots\leftrightarrow A_n)\). Notice that by the associative law for \(\leftrightarrow\) we can treat this wff as \begin{gather}((A_{k_1}\leftrightarrow\cdots\leftrightarrow A_{k_{2m}})\leftrightarrow(A_{k_{2m+1}}\leftrightarrow\cdots\leftrightarrow A_{k_{n}}))\end{gather} By the lemma we know that \(\overline{v}(A_{k_1}\leftrightarrow\cdots\leftrightarrow A_{k_{2m}}) = T\) and \(\overline{v}(A_{k_{2m+1}}\leftrightarrow\cdots\leftrightarrow A_{k_{n}}) = T\), thus \(\overline{v}(((A_{k_1}\leftrightarrow\cdots\leftrightarrow A_{k_{2m}})\leftrightarrow(A_{k_{2m+1}}\leftrightarrow\cdots\leftrightarrow A_{k_{n}}))) = T\). Since this new wff is tautologically equivalent to the original, it must be that \(v\) satisfies \((\cdots(A_1\leftrightarrow A_2)\leftrightarrow\cdots\leftrightarrow A_n)\).

To prove the forward direction, we prove the contrapositive, that is if \(v(A_i) = F\) for an odd number of \(i\)’s, \(1\leq i\leq n\), then \(v\) does not satisfy \((\cdots(A_1\leftrightarrow A_2)\leftrightarrow\cdots\leftrightarrow A_n)\). Assume \(v(A_i) = F\) for \(2m+1\) \(i\)’s, where \(m\in\mathbb{Z}_{\geq 0}\). Since \(\leftrightarrow\) is commutative, we can reindex the \(A_i\) yielding the wff \begin{gather}(A_{k_1}\leftrightarrow A_{k_{2}}\leftrightarrow\cdots\leftrightarrow A_{k_n})\end{gather} where \(v(A_{k_1}) = \cdots = v(A_{k_{2m+1}}) = F\) and \(v(A_{k_{2m+2}}) = \cdots = v(A_{k_n}) = T\). This reordering yields a wff which is tautologically equivalent to \((\cdots(A_1\leftrightarrow A_2)\leftrightarrow\cdots\leftrightarrow A_n)\). Notice that by the associative law for \(\leftrightarrow\) we can treat this wff as \begin{gather}((A_{k_1}\leftrightarrow\cdots\leftrightarrow A_{k_{2m+1}})\leftrightarrow(A_{k_{2m+2}}\leftrightarrow\cdots\leftrightarrow A_{k_{n}}))\end{gather} By the lemma we know that \(\overline{v}(A_{k_1}\leftrightarrow\cdots\leftrightarrow A_{k_{2m+1}}) = F\) and \(\overline{v}(A_{k_{2m+2}}\leftrightarrow\cdots\leftrightarrow A_{k_{n}}) = T\), thus \(\overline{v}(((A_{k_1}\leftrightarrow\cdots\leftrightarrow A_{k_{2m+1}})\leftrightarrow(A_{k_{2m+2}}\leftrightarrow\cdots\leftrightarrow A_{k_{n}}))) = F\). Since this new wff is tautologically equivalent to the original, it must be that \(v\) does not satisfy \((\cdots(A_1\leftrightarrow A_2)\leftrightarrow\cdots\leftrightarrow A_n)\).