Skip to main content

Section 1.10 Logical equivalence

Definition 1.10.1.

We say that two statements \(\phi\) and \(\psi\) are equivalent if \(\phi\) is true if and only if \(\psi\) is true.

One also says “\(\phi\) if and only if \(\psi\)” or “\(\phi\) iff \(\psi\)” or \(\phi \iff \psi\text{.}\) Here is the truth table for this connective:

\(\phi\) \(\psi\) \(\phi \iff \psi\)
T T T
T F F
F T F
F F T

In other words, \(\quine{\phi \iff \psi}\) is the same statement as \(\quine{(\phi\implies \psi) \wedge (\psi \implies \phi)}\text{.}\)

Equivalence behaves like “=” does in algebra: you are free to swap one statement for another equivalent statement. For example, if \(\phi\iff \psi\text{,}\) then the statement \(\quine{\phi \vee \chi}\) is equivalent to the statement \(\quine{\psi \vee \chi}\text{.}\)

Let \(\phi\) be a statement. The double negation of \(\phi\) is the statement \(\quine{\neg{\neg{\phi}}}\text{.}\) Then \(\quine{\neg{\neg{\phi}}}\) is equivalent to \(\phi\text{.}\) In other words, \(\neg{\neg{\phi}} \iff \phi\text{.}\) Indeed, \(\phi\) is true if and only if \(\quine{\neg{\phi}}\) is false, which happens if and only if \(\quine{\neg{\neg{\phi}}}\) is true.

To prove \(\phi\iff \psi\text{,}\) you'll usually have to prove both \(\phi\implies \psi\) and \(\psi\implies \phi\text{.}\)

We begin with the forward direction; that is, we shall show first that \((\phi \implies \psi) \implies (\neg{\phi} \vee \psi)\text{.}\) So assume \(\phi\implies \psi\text{.}\) We aim to show \(\neg{\phi} \vee \psi\text{.}\)

There are two options for \(\phi\text{:}\) it is either true or false. Let's consider these options in turn:

  • If \(\phi\) is false, then \(\neg{\phi}\) is true, and so certainly \(\neg{\phi} \vee \psi\) is true as well.

  • If \(\phi\) is true, then since we are assuming \(\phi\implies \psi\text{,}\) we can conclude \(\psi\text{.}\) Thus \(\neg{\phi} \vee \psi\) is true as well.

Either way, we see that \(\neg{\phi} \vee \psi\) holds, so it follows that \(\phi\implies \psi\) implies \(\neg{\phi} \vee \psi\text{.}\)

Now we prove the reverse direction; that is, we shall show that \((\neg{\phi} \vee \psi) \implies (\phi \implies \psi)\text{.}\) Assume \(\neg{\phi} \vee \psi\text{.}\) We aim to show that \(\phi\Rightarrow \psi\) is true. To prove this, we assume that \(\phi\) is true, and we aim to conclude \(\psi\text{.}\) But we are assuming that either \(\neg{\phi}\) is true or \(\psi\) is true. Since \(\phi\) is true, \(\neg{\phi}\) is false. So \(\psi\) must be true. Thus, we conclude \(\phi\implies \psi\text{,}\) and so we have shown that \(\neg{\phi} \vee \psi\) implies \(\phi \implies \psi\text{.}\)

We begin with the forward direction; that is, we shall show first that \((\phi \implies \psi) \implies (\neg{\psi} \implies \neg{\phi})\text{.}\) So assume \(\phi\implies \psi\text{.}\) We aim to show that \(\neg{\psi} \implies \neg{\phi}\text{.}\) So assume \(\neg{\psi}\text{;}\) that is, that \(\psi\) is false.

The previous theorem shows that \(\phi \implies \psi\) is equivalent to \(\neg{\phi} \vee \psi\text{.}\) Since \(\psi\) is false, the only remaining option is that \(\neg{\phi}\) holds. We have thus shown that \(\neg{\psi} \implies \neg{\phi}\text{.}\)

Now we prove the reverse direction; that is, we shall show that \((\neg{\psi} \implies \neg{\phi}) \implies (\phi \implies \psi)\text{.}\) So assume that \(\neg{\psi} \implies \neg{\phi}\text{.}\) We aim to show that \(\phi \implies \psi\text{.}\) So assume \(\phi\text{.}\) We aim to deduce \(\psi\text{.}\)

By the previous theorem, \(\neg{\psi} \implies \neg{\phi}\) is equivalent to \(\neg{\neg{\psi}} \vee \neg{\phi}\text{,}\) which is in turn equivalent to \(\psi \vee \neg{\phi}\text{.}\) Since \(\phi\) is true, \(\neg{\phi}\) is false, and so the only option remaining is that \(\psi\) holds. Thus we have shown that \(\phi \implies \psi\text{.}\)