2.3 Logical Equivalence
As well as combining statements together to make new statements, we also want to know whether two statements are equivalent, that is they are the same.
We use the symbol \(\iff\) to mean if and only if. For two statements \(P\) and \(Q\), “\(P \iff Q\)” means \(P\implies Q\) and \(Q \implies P\). In this case we say “\(P\) and \(Q\) are equivalent”. The corresponding truth table is as follows.
| \(P\) | \(Q\) | \(P\iff Q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
If we take two statements which are logically equivalent, say \(P\) is equivalent to \(Q\), then proving \(P\) to be true is equivalent to proving \(Q\) to be true. Similarly, proving \(Q\) to be true is equivalent to proving \(P\) to be true. We can use truth tables to prove if two (abstract) statements are equivalent.This will prove to be useful later on when we turn a statement we want to prove is true into another equivalent statement that may be easier to prove.
Let \(P\) and \(Q\) be two statements.
\(P\implies Q\) is equivalent to \((\neg Q)\implies(\neg P)\).
\(P\implies Q\) is equivalent to \((\neg P)\vee Q\).
Using the last two examples and the truth table for \(P\implies Q\), we have the following truth table.
| \(P\) | \(Q\) | \(P\implies Q\) | \((\neg Q)\implies(\neg P)\) | \((\neg P)\vee Q\) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
Hence, for all truth values of \(P\) and \(Q\), we have that \(P\implies Q\) and \((\neg Q)\implies (\neg P)\) have the same truth values. Therefore, \(P\implies Q\) is equivalent to \((\neg Q)\implies(\neg P)\).
Similarly, for all truth values of \(P\) and \(Q\), we have that \(P\implies Q\) and \((\neg P)\vee Q\) have the same truth values. Therefore, \(P\implies Q\) is equivalent to \((\neg P)\vee Q\).□
Notice that the above proof has several sentences to explain to the reader what is going on. It is made up of full sentences with a clear conclusion on what the calculation (in this case the truth table) shows. A proof should communicate clearly to the reader why the statement (be that a theorem, proposition or lemma) is true.
How much detail you put in a proof will be influenced by who your target audience is - this is a skill you will develop over your time as a student.□
Suppose \(P\) and \(Q\) are two statements. Then:
\(P\iff (\neg(\neg P))\).
\((P\vee Q)\iff((\neg P)\implies Q)\)
Exercise.
□
The next proposition shows that \(\wedge\) and \(\vee\) are associative, that is, \(P\wedge Q\wedge R\) and \(P\vee Q\vee R\) are statements that are clear without parentheses (and therefore do not require parentheses).
Suppose \(P,Q,R\) are statements.
\(((P\wedge Q)\wedge R)\iff (P\wedge(Q\wedge R)).\)
\(((P\vee Q)\vee R )\iff (P\vee(Q\vee R)).\)
We prove part a. and leave the proof of part b. as an exercise. We have the following truth table.
| \(P\) | \(Q\) | \(R\) | \(P\wedge Q\) | \((P\wedge Q)\wedge R\) | \(Q\wedge R\) | \(P\wedge (Q\wedge R)\) |
|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T |
| T | T | F | T | F | F | F |
| T | F | T | F | F | F | F |
| T | F | F | F | F | F | F |
| F | T | T | F | F | T | F |
| F | T | F | F | F | F | F |
| F | F | T | F | F | F | F |
| F | F | F | F | F | F | F |
□
Let \(P, Q, R\) be statements. Then \(P \implies (Q \iff R)\) and \((P\implies Q) \iff R\) are not equivalent.
We have the following truth table
| \(P\) | \(Q\) | \(R\) | \(Q \iff R\) | \(P \implies (Q \iff R)\) | \((P\implies Q)\) | \((P\implies Q) \iff R\) |
|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T |
| T | T | F | F | F | T | F |
| T | F | T | F | F | F | F |
| T | F | F | T | T | F | T |
| F | T | T | T | T | T | T |
| F | T | F | F | T | T | F |
| F | F | T | F | T | T | T |
| F | F | F | T | T | T | F |
□
The above proposition shows that the statement \(P \implies Q \iff R\) therefore has no clear meaning without parenthesis. Similarly, there is an exercise to show that \(P \iff (Q \implies R)\) and \((P\iff Q) \implies R\) are not equivalent, so \(P \iff Q \implies R\) is likewise not clear. Hence the meaning of assertions such as \(P\implies Q \iff R \implies S\) is undefined (unless one puts in parenthesis).
As an exercise, one may also prove the following sometimes useful equivalences.
Let \(P,Q,R\) be statements. Then:
\((P\wedge (Q\wedge R))\iff\left((P\wedge Q)\wedge(P\wedge R)\right)\);
\((P\vee (Q\vee R))\iff\left((P\vee Q)\vee(P\vee R)\right).\)
Exercise.
□
Let \(P,Q,R\) be statements. Then
(\(P\wedge(Q\vee R))\iff ((P\wedge Q)\vee(P\wedge R)).\)
(\(P\vee(Q\wedge R))\iff ((P\vee Q)\wedge(P\vee R)).\)
We will prove part a. and leave the proof of part b. as an exercise. We have the following truth table.
| \(P\) | \(Q\) | \(R\) | \(Q\vee R\) | \(P\wedge (Q \vee R)\) | \(P\wedge Q\) | \(P\wedge R\) | \((P\wedge Q) \vee (P\wedge R)\) |
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T | T |
| T | T | F | T | T | T | F | T |
| T | F | T | T | T | F | T | T |
| T | F | F | F | F | F | F | F |
| F | T | T | T | F | T | F | F |
| F | T | F | T | F | F | F | F |
| F | F | T | T | F | F | F | F |
| F | F | F | F | F | F | F | F |
□
Let us return to sets to see how logic may be applied to prove statements.
Suppose that \(A\) and \(B\) are subsets of some set \(X\).
\(A\cup B\) denotes the union of \(A\) and \(B\), that is \[A\cup B=\{x\in X:\ x\in A\text{ or }x\in B\ \}.\]
\(A\cap B\) denotes the intersection of \(A\) and \(B\), that is \[A\cap B=\{x\in X:\ x\in A \text{ and }x\in B\ \}.\]
When \(A\cap B=\emptyset\), we say that \(A\) and \(B\) are disjoint.
We have \(\mathbb{Z}_{\geq 0}\cup \mathbb{Z}_- = \mathbb{Z}\). We also see that \(\mathbb{Z}_{\geq 0} \cap \mathbb{Z}_- =\emptyset\), hence they are disjoint.
The word union comes from the Latin unio meaning “a one-ness”. The union of two sets is a set that lists every element in each set just once (even if the element appears in both sets). While the symbol \(\cup\) looks like a “U” (the first letter of union), this is a coincidence. While the symbol \(\cup\) was first used by Hermann Grassmann (Polish/German mathematician, 1809 - 1877) in 1844, Giuseppe Peano (Italian mathematician, 1858-1932) used it to represent the union of two sets in 1888 in his article Calcolo geometrico secondo Ausdehnungslehre di H. Grassmann. However, at the time the union was referred to as the disjunction of two sets.
The word intersect comes from the Latin inter meaning “within, in between” and sectus meaning “to cut”. The interesection of two curves is the place they cut each other, the intersection of two sets is the “place” where two sets overlaps. While the symbol \(\cap\) was first used by Gottfried Leibniz (German mathematician, 1646 - 1716), he also used it to represent regular multiplication (there are some links between the two ideas). Again, \(\cap\) was used by Giuseppe Peano in 1888 to refer to intersection only.
The word disjoint comes from the Latin dis meaning “away, in two parts” and the word joint. Two sets are disjoint if they are apart from each other without any joints between them. (Compare this to disjunction, which has the same roots but is used to mean joining two things that are apart).Let \(X\) be a set, and for \(x\in X\), let \(P(x)\) be the statement that \(x\) satisfies the criteria \(P\), and let \(Q(x)\) be the statement that \(x\) satisfies the criteria \(Q\). Set \[A=\{x\in X:P(x) \} \qquad\text{and}\qquad B=\{x\in X: Q(x) \}.\] Then \[\begin{align*} A\cap B&=\{x\in X: P(x) \wedge Q(x) \} ,\\ A\cup B&=\{x\in X: P(x) \vee Q(x) \}. \end{align*}\]
For \(x\in X\), we have that \(x\in A\) if and only if the statement \(P(x)\) holds. Similarly, we have that \(x\in B\) if and only if the statement \(Q(x)\) holds. Then \[\begin{align*} A\cap B&=\{x\in X:( x\in A) \wedge (x\in B) \}\\ &=\{x\in X: P(x)\wedge Q(x) \} \end{align*}\] and \[\begin{align*} A\cup B&=\{x\in X:( x\in A) \vee (x\in B) \}\\ &=\{x\in X: P(x)\vee Q(x) \}. \end{align*}\]
□
We can use our work on logical equivalence to show that that \(\cap\) and \(\cup\) are associative.
Suppose \(A,B,C\) are subsets of a set \(X\). Then
\(A\cap(B\cap C)=(A\cap B)\cap C\).
\(A\cup(B\cup C)=(A\cup B)\cup C\).
We will prove part a. and leave part b. as an exercise
Suppose \(x\in X\). Let \(P\) be the statement that \(x\in A\), let \(Q\) be the statement that \(x\in B\), and let \(R\) be the statement that \(x\in C\). Recall Proposition 2.10, \(P\wedge(Q\wedge R)\iff(P\wedge Q)\wedge R\). Then \[\begin{align*} x\in A\cap(B\cap C)&\iff (x\in A)\wedge (x\in B\cap C)\\ &\iff (x\in A)\wedge((x\in B)\wedge (x\in C))\\ &\iff P\wedge(Q\wedge R)\\ &\iff (P\wedge Q)\wedge R\\ &\iff ((x\in A)\wedge (x\in B))\wedge (x\in C)\\ &\iff (x\in A\cap B)\wedge (x\in C)\\ &\iff x\in(A\cap B)\cap C. \end{align*}\] Hence, we have that \(x\in A\cap(B\cap C)\) if and only if \(x\in (A\cap B)\cap C\). It follows that \(A\cap(B\cap C)=(A\cap B)\cap C.\)□
□
Similarly, we have that \(\cup\) and \(\cap\) are distributive.
Let \(A,B,C\) be subsets of a set \(X\). Then
\(A\cap(B\cup C)=(A\cap B)\cup(A\cap C).\)
\(A\cup(B\cap C)=(A\cup B)\cap(A\cup C).\)
We will prove part a. and leave part b. as an exercise
Suppose \(x\in X\). Let \(P\) be the statement that \(x\in A\), let \(Q\) be the statement that \(x\in B\), and let \(R\) be the statement that \(x\in C\). Recall Proposition 2.13 that \(P\wedge(Q\vee R)\iff (P\wedge Q)\vee(P\wedge R).\) Then \[\begin{align*} x\in A\cap(B\cup C) &\iff\ (x\in A)\wedge (x\in B\cup C)\\ &\iff\ (x\in A)\wedge ((x\in B)\vee (x\in C))\\ &\iff\ P\wedge(Q\vee R)\\ &\iff\ (P\wedge Q)\vee(P\wedge R)\\ &\iff\ ((x\in A)\wedge (x\in B))\vee((x\in A)\wedge (x\in C))\\ &\iff\ (x\in A\cap B)\vee(x\in A\cap C)\\ &\iff\ x\in (A\cap B)\cup(A\cap C). \end{align*}\] Hence, we have that \(x \in A\cap(B\cup C)\) if and only if \(x \in (A\cap B)\cup(A\cap C)\). It follows that \(A\cap(B\cup C)=(A\cap B)\cup(A\cap C)\).□