4
$\begingroup$

First of all, I know how to prove this theorem below:

A statement form that contains $\leftrightarrow$ as its only connectives is a tautology iff each statement letter occurs an even number of times.

To prove the theorem, I first derived this corollary:

A statement built up using only $\leftrightarrow$ is true iff there are an even number of false terms.

But now, I have to prove the theorem below:

Proving that a statement form that contains $\lnot$ and $\leftrightarrow$ as its only connectives is a tautology iff $\lnot$ and each statement letter occur an even number of times.

The bold texts are the only differences comparing it to the previous question that I could solve. I tried modifying the corollary to help me prove the theorem but it didn't help me, or modifying the corollary made it impossible to prove. Is there anything else I could do?

$\endgroup$

2 Answers 2

1
+50
$\begingroup$

To solve the problem, observe that, for every formulas $\varphi$ and $\psi$, the formulas $$\lnot (\varphi \leftrightarrow \psi) \qquad\qquad \lnot \varphi \leftrightarrow \psi \qquad\qquad \varphi \leftrightarrow \lnot \psi $$ are logically equivalent. It means that in the fragment $\{\lnot, \leftrightarrow\}$ of propositional logic, the truth value of a formula depends on the number of occurrences of $\lnot$, but not on their position. And since the truth values are only two, not even the number of occurrences of $\lnot$ really matters, but only the parity of such a number.

This property gives an intuition about the way to generalize the corollary from the fragment $\{\leftrightarrow\}$ to the fragment $\{\lnot, \leftrightarrow\}$. The generalization is the lemma below.


Lemma. Let $\varphi$ whose only connectives are $\lnot$ and $\leftrightarrow$, and let $v$ be a valuation. Then, $v$ makes $\varphi$ true if and only if the sum of the number of occurrences of $\lnot$ in $\varphi$ and the number of occurrences of statement letters in $\varphi$ made false by $v$ is even.

Proof. By structural induction on the formula $\varphi$. Let us denote by $\#^\lnot_\varphi$ the number of occurrences of $\lnot$ in $\varphi$, and by $\bot^v_\varphi$ the number of occurrences of statement letters in $\varphi$ made false by $v$. We want to prove that $v$ makes $\varphi$ true if and only if $\#^\lnot_\varphi + \bot^v_\varphi$ is even.

Base case. The formula $\varphi$ is a statement letter, hence $\#^\lnot_\varphi = 0$ and either $\bot^v_\varphi = 1$ (if $v$ makes $\varphi$ false) or $\bot^v_\varphi = 0$ (if $v$ makes $\varphi$ true). Clearly, $\varphi$ is true if and only if $\bot^v_\varphi = \#^\lnot_\varphi + \bot^v_\varphi$ is even.

Inductive step. Since $\lnot$ and $\leftrightarrow$ are the only connectives used in the formula $\varphi$, there are only two cases.

  1. $\varphi = \lnot \psi$. By induction hypothesis, $v$ makes $\psi$ true if and only if $\#^\lnot_\psi + \bot^v_\psi$ is even. Clearly, $\#^\lnot_\varphi = \#^\lnot_\psi + 1$ and $\bot^v_\varphi = \bot^v_\psi$. Therefore, $v$ makes $\varphi$ true if and only if $v$ makes $\psi$ false (since $\varphi$ is the negation of $\psi$) if and only if $\#^\lnot_\psi + \bot^v_\psi$ is odd if and only if $\#^\lnot_\varphi + \bot^v_\varphi$ is even.

  2. $\varphi = \psi_1 \leftrightarrow \psi_2$. By induction hypothesis, for each $i \in \{1,2\}$, $v$ makes $\psi_i$ true if and only if $\#^\lnot_{\psi_i} + \bot^v_{\psi_i}$ is even. Clearly, $\#^\lnot_\varphi = \#^\lnot_{\psi_1} + \#^\lnot_{\psi_2}$ and $\bot^v_\varphi = \bot^v_{\psi_1} + \bot^v_{\psi_2}$. Cases:

    • $v$ makes both $\psi_1$ and $\psi_2$ true; then, $v$ makes $\varphi$ true (according to the truth table of $\leftrightarrow$) and $\#^\lnot_\varphi + \bot^v_\varphi = \#^\lnot_{\psi_1} + \#^\lnot_{\psi_2} + \bot^v_{\psi_1} + \bot^v_{\psi_2} = (\#^\lnot_{\psi_1} + \bot^v_{\psi_1}) + (\#^\lnot_{\psi_2} + \bot^v_{\psi_2})$ is even because so are $\#^\lnot_{\psi_1} + \bot^v_{\psi_1}$ and $\#^\lnot_{\psi_2} + \bot^v_{\psi_2}$.
    • $v$ makes both $\psi_1$ and $\psi_2$ false; then, $v$ makes $\varphi$ true (according to the truth table of $\leftrightarrow$) and $\#^\lnot_\varphi + \bot^v_\varphi = \#^\lnot_{\psi_1} + \#^\lnot_{\psi_2} + \bot^v_{\psi_1} + \bot^v_{\psi_2} = (\#^\lnot_{\psi_1} + \bot^v_{\psi_1}) + (\#^\lnot_{\psi_2} + \bot^v_{\psi_2})$ is even because both $\#^\lnot_{\psi_1} + \bot^v_{\psi_1}$ and $\#^\lnot_{\psi_2} + \bot^v_{\psi_2}$ are odd.
    • $v$ makes $\psi_1$ true and $\psi_2$ false; then, $v$ makes $\varphi$ false (according to the truth table of $\leftrightarrow$) and $\#^\lnot_\varphi + \bot^v_\varphi = \#^\lnot_{\psi_1} + \#^\lnot_{\psi_2} + \bot^v_{\psi_1} + \bot^v_{\psi_2} = (\#^\lnot_{\psi_1} + \bot^v_{\psi_1}) + (\#^\lnot_{\psi_2} + \bot^v_{\psi_2})$ is odd because $\#^\lnot_{\psi_1} + \bot^v_{\psi_1}$ is even and $\#^\lnot_{\psi_2} + \bot^v_{\psi_2}$ is odd.
    • $v$ makes $\psi_1$ false and $\psi_2$ true; then, $v$ makes $\varphi$ false (according to the truth table of $\leftrightarrow$) and $\#^\lnot_\varphi + \bot^v_\varphi = \#^\lnot_{\psi_1} + \#^\lnot_{\psi_2} + \bot^v_{\psi_1} + \bot^v_{\psi_2} = (\#^\lnot_{\psi_1} + \bot^v_{\psi_1}) + (\#^\lnot_{\psi_2} + \bot^v_{\psi_2})$ is odd because $\#^\lnot_{\psi_1} + \bot^v_{\psi_1}$ is odd and $\#^\lnot_{\psi_2} + \bot^v_{\psi_2}$ is even. $\qquad\qquad\qquad\square$

From the lemma above, it easily follows the syntactic carachterization of tatulogies in the fragment $\{\lnot, \leftrightarrow\}$: a formula $\varphi$ whose only connectives are $\lnot$ and $\leftrightarrow$ is a tautology if and only if $\lnot$ and each statement letter occur an even number of times in $\varphi$.

Proof.

\begin{align} \varphi \text{ is a tautology } &\iff \text{ every valuation } v \text{ makes } \varphi \text{ true } \\ &\overset{\text{by lemma}}{\iff} \text{ for every valuation $v$, the sum of the number of} \\ &\qquad \quad \text{occurrences of $\lnot$ in $\varphi$ and the number of occurrences} \\ &\qquad \quad \text{of statement letters in $\varphi$ made false by $v$ is even } \\ &\iff \lnot \text{ and each statement letter occur an even number of times in $\varphi$.} \end{align} The last equivalence holds because the number of occurrences of $\lnot$ in $\varphi$ does not depend on $v$, and because of the remark below. In particular, the remark below excludes the possibility that the sum of the number of occurrences of $\lnot$ in $\varphi$ and the number of occurrences of statement letters in $\varphi$ made false by $v$ is even because the two numbers are odd. $\qquad\qquad\qquad \qquad\qquad \square$

Remark. Let $\varphi$ be a formula and $p$ a statement letter. Let $v$ be a valuation and $\overline{v}$ be a valuaiton with the same values as $v$ for every statement letter but $p$. The number of occurrences of statement letters in $\varphi$ made false by $v$ and the number of occurrences of statement letters in $\varphi$ made false by $\overline{v}$ have the same parity if and only if the number of occurrences of $p$ in $\varphi$ is even.


Thanks to the lemma above, in the fragment $\{\lnot, \leftrightarrow\}$ you can provide not only a syntactic carachterization of tautologies but also syntactic carachterizations of contradictions (a formula that is always false, in every row of its truth table) and of fomulas that are neither tautologies nor contradictoins. Indeed, let $\varphi$ be a formula whose only connectives are $\lnot$ and $\leftrightarrow$.

  1. $\varphi$ is a contradiction if and only if $\lnot$ occur an odd number of times in $\varphi$, and each statement letter occur an even number of times in $\varphi$;
  2. $\varphi$ is neither a tautology nor a contradiction if and only if some statement letter occur an even number of times in $\varphi$.
$\endgroup$
1
$\begingroup$

I believe your goal follows from the corollary and the fact that $\lnot\phi$ is equivalent to $\phi\iff\text{false}$.

$\endgroup$
2
  • 1
    $\begingroup$ What is term "false" in this context? $\endgroup$ Jan 5, 2021 at 8:07
  • 1
    $\begingroup$ You can think of it this way. Suppose we have a wff $ \phi $ with $ \lnot $ and $ \iff $ as the only connectives. Pick a statement letter $ \psi $ not appearing in $ \phi $. In $\phi$, replace every $ \lnot \chi $ (where $\chi$ is a wff) by $ \chi \iff \psi $ and call the new wff $ \tilde{\phi} $. Then $ \phi $ is true for a particular valuation $v$ iff $ \tilde{\phi} $ is true for the valuation $ \tilde v $ that agrees with $v$ for statement letters in $\phi$ and such that $ \tilde{v}(\psi) = \text{False} $. $\endgroup$ Jan 5, 2021 at 8:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .