Skip to main content

PLP: An introduction to mathematical proof

Seçkin Demirbaş, Andrew Rechnitzer

Section 4.2 Logical equivalence

Not all tautologies are terribly useful, but we will use one family of tautologies again and again as we write proofs: logical equivalences. We have seen that the two statements
\begin{align*} (P \land Q) \amp \qquad \text{and}\qquad (Q \land P) \end{align*}
have the same truth tables; it only takes a moment to write down the table to convince yourself.
We could write this “have the same truth tables”-fact as follows:
\begin{align*} (P \land Q) \iff (Q \land P) & \text{ is a tautology} \end{align*}
Take a moment to parse this. The biconditional at the heart of the statement must be true, and a quick review of the biconditional tells us that both sides must be true at the same time and false at the same time — exactly what we want to express. This way of writing things is still cumbersome, and mathematicians will always seek out nicer notation if it is available.

Definition 4.2.1.

We say that two statements \(R\) and \(S\) are logically equivalent when the statement \(R\iff S\) is a tautology. In this case we write \(R \equiv S\text{.}\)

Remark 4.2.2. Equivalent and equal?

Note that some texts use “\(=\)” to denote logical equivalence, while this author much prefers “\(\equiv\)”. One can get into long debates as to whether or not “\(=\)” is equivalent to “\(\equiv\)” despite not being equal. And unfortunately there is no clean and well established convention in the mathematical community. You should, as a reader, recognise both (from context).
Another logical equivalence we’ve already seen (back in Section 2.4) is
\begin{gather*} (P \implies Q) \equiv ( (\neg P)\lor Q ) \end{gather*}
where we have written this down with plenty of brackets to avoid potential ambiguities.
Logical equivalence becomes very useful when we are trying to prove things. If we start with a difficult statement \(R\text{,}\) and transform it into an easier and logically equivalent statement \(S\text{,}\) then a proof of \(S\) automatically gives us a proof of \(R\text{.}\)
Here is a list of useful logical equivalences which will be very handy for proving things as we continue in the text. These constitute our first important result and since we will use it frequently we should call it a theorem.
These can all be proved in a straightforward, but slightly tedious, manner by computing and comparing truth tables.
By chaining the logical equivalences in Theorem 3 together we can make new ones. For example, we can show the equivalence of the contrapositive as follows:

Example 4.2.4.

Show that the contrapositive is logically equivalent to the original implication.
\begin{align*} (P \implies Q) &\equiv ((\neg P) \lor Q) & \text{implication as or}\\ & \equiv Q \lor (\neg P) & \text{commutation of or}\\ & \equiv \neg(\neg Q) \lor (\neg P) & \text{double negation}\\ & \equiv (\neg Q)\implies (\neg P) & \text{or as implication} \end{align*}
Arguably this would be easier to do using a truth table, but the above is much more informative.
Here is a nice, and useful, example.

Example 4.2.5.

Prove that \(\neg(P \implies Q) \equiv P \land (\neg Q)\text{.}\)
\begin{align*} \neg(P \implies Q) & \equiv \neg ( (\neg P) \lor Q) & \text{rewrite implication as or}\\ & \equiv (\neg(\neg P)) \land (\neg Q) & \mbox{DeMorgan}\\ & \equiv P \land (\neg Q) & \text{double negation} \end{align*}
Another nice, and useful example. In fact it is so nice and useful, we probably should have made it an exercise:

Example 4.2.6.

Show \(\neg(P \iff Q) \equiv (P \land \neg Q) \lor (Q \land \neg P)\text{.}\)
\begin{align*} \neg(P \iff Q) & \equiv \neg( (P \implies Q) \land (Q \implies P) ) & \text{rewrite biconditional}\\ & \equiv ( \neg(P \implies Q) \lor \neg(Q \implies P) ) & \text{DeMorgan}\\ & \equiv ( P \land (\neg Q) ) \lor (Q \land (\neg P) ) & \text{previous example} \end{align*}
So we now have another useful theorem
This one will be very useful later on, so we’ll call it a lemma. It isn’t quite complete, you’ll have to finish it off as an exercise later.
We leave the proof as an exercise.
Some practice negating things.

Example 4.2.9.

What is the negation of
\begin{equation*} (x^2 \geq 4) \land (x \lt 1) \end{equation*}
Remeber to be careful when we negating inequalities. The negation of \(a \lt b\) is \(a \geq b\text{,}\) and the negation of \(a \leq b\) is \(a \gt b\text{.}\)
Solution.
\begin{align*} \neg( (x^2\geq 4) \land (x \lt 1) ) \amp \equiv ( \neg(x^2\geq 4) \lor \neg(x \lt 1) )\\ \amp \equiv (x^2 \lt 4) \lor (x \geq 1) \end{align*}

Example 4.2.10.

Negate the statement
\begin{equation*} (x^2 \geq 1) \implies (x \geq 1). \end{equation*}
Solution.
Remeber to be careful with those inequalities.
\begin{align*} \neg( (x^2 \geq 1) \implies (x\geq 1)) \amp\equiv (x^2\geq 1) \land \neg(x\geq 1)\\ \amp\equiv (x^2 \geq 1) \land (x \lt 1) \end{align*}

Example 4.2.11.

Negate “The integer \(x\) is odd if and only if \(x^2\) is odd.”
Solution.
This is actually a true statement (one we’ll prove soon), but we can negate it anyway. We’ll make use of the fact that if an integer is not odd, then it must be even (and vice-versa).
\begin{align*} \neg( (x \text{ is odd}) \iff (x^2 \text{ is odd}) ) & \equiv \Big( ( x \text{ is odd}) \land \neg (x^2 \text{ is odd} ) \Big) \lor \Big( (x^2 \text{ is odd}) \land \neg (x \text{ is odd}) \Big)\\ & \equiv \Big( (x \text{ is odd}) \land (x^2 \text{ is not odd}) \Big) \lor \Big( (x^2 \text{ is odd}) \land (x \text{ is not odd}) \Big) \\ & \equiv \Big( (x \text{ is odd}) \land (x^2 \text{ is even})\Big) \lor \Big( (x^2 \text{ is odd}) \land (x \text{ is even}) \Big) \end{align*}
Oof! That is not so pretty.
We are ready for some more proofs, but first — there are some exercises for you.
<Prev^TopNext>