2.2 Truth table
Now that we have some objects to work with, we want to know what we can do with them. In a mathematical system, statements are either true or false, but not both at once. We sometimes say a statement \(P\) holds to mean it is true. The label ‘true’ or ‘false’ associated to a given statement is its truth value.
Definitions (i.e., \(\mathbb{Z}\)) and axioms (i.e., (A1)-(A11) ) are statements we take to be true, while propositions, theorems and lemmas are statements that we want to prove are true and often consist of smaller statements linked together. While we often don’t write statements symbolically, looking at truth table and statements help us understand the fundamentals of how a proof works. We first introduce the four building blocks of statements.
We use the symbol \(\neg\) to mean not. The truth table below shows the value \(\neg P\) takes depending on the truth value of \(P\).
| \(P\) | \(\neg P\) |
|---|---|
| T | F |
| F | T |
We will see concrete examples of how to negate statements later in this chapter.
We use the symbol \(\wedge\) to mean and. Let \(P\) and \(Q\) be two statements, we have that \(P\wedge Q\) is true exactly when \(P\) and \(Q\) are true. The corresponding truth table is as follows:
| \(P\) | \(Q\) | \(P\wedge Q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
We use the symbol \(\vee\) to mean or. Let \(P\) and \(Q\) be two statements, we have that \(P\vee Q\) is true exactly when at least one of \(P\) or \(Q\) is true. The corresponding truth table is as follows.
| \(P\) | \(Q\) | \(P\vee Q\) |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
We use the symbol \(\implies\) to mean implies. Let \(P\) and \(Q\) be two statements “\(P \implies Q\)” is the same as “If \(P\), then \(Q\)”, or “for \(P\) we have \(Q\)”. The corresponding truth table is as follows.
| \(P\) | \(Q\) | \(P\implies Q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
The above truth table can seem confusing, but consider the following example.
Recall (A1) - “For all \(x,y \in \mathbb{Z}\) we have \(x+y \in \mathbb{Z}\)”. Let \(P\) be the statement \(x,y \in \mathbb{Z}\) and \(Q\) be the statement \(x+y \in \mathbb{Z}\), then (A1) can be written symbolically as \(\forall x,y, P \implies Q\). This statement is true, regardless of what the value of \(x\) and \(y\) are. But let us look at the truth value of \(P\) and \(Q\) with different \(x\) and \(y\)
| \(x\) | \(y\) | \(P\) | \(Q\) |
|---|---|---|---|
| \(0\) | \(1\) | T | T |
| \(0\) | \(\frac{3}{2}\) | F | F |
| \(\frac{1}{2}\) | \(1\) | F | F |
| \(\frac{1}{2}\) | \(\frac{3}{2}\) | F | T |
Many theorems are of the type “If \(P\) then \(Q\)”. A common method to prove such statement is to start with the assumption \(P\) (i.e., assume \(P\) is true) and use logical steps to arrive at \(Q\).These are often referred to as “direct proofs”.
The above example also shows that you can not start a proof with what you want to prove, as you could start with something false and end up with something true.□
Turning back to sets, we look at examples of direct proofs.
A set \(A\) is a subset of a set \(B\), denoted by \(A\subseteq B\), if every element of \(A\) is also an element of \(B\) (Symbolically: \(\forall x \in A\), we have \(x \in B\)).
We write \(A\not\subseteq B\) when \(A\) is not a subset of \(B\), so there is at least one element of \(A\) which is not an element of \(B\) (Symbolically: \(\exists x \in A\) such that \(x\notin B\)).
A set \(A\) is a proper subset of a set \(B\), denoted by \(A\subsetneq B\), if \(A\) is a subset of \(B\) but \(A\neq B\).Let \(A = 4\mathbb{Z}= \{4n: n\in\mathbb{Z}\}\) and \(B = 2\mathbb{Z}=\{ 2n: n\in \mathbb{Z}\}\). We will prove \(A \subseteq B\) using a direct proof. [If we let \(P\) be the statement \(x \in A\) and \(Q\) be the statement \(x \in B\), note that \(\forall x \in A\) we have \(x\in B\) translate symbolically to \(\forall x, P \implies Q\).]
Let \(x\in A\) [i.e., suppose \(P\) is true]. Then there exists \(n\in\mathbb{Z}\) such that \(x=4n\). Hence, \(x=4n=2(2n)=2m\), for some \(m\in\mathbb{Z}\), i.e. there exists \(m\in \mathbb{Z}\) such that \(x = 2m\). Hence, \(x\in B\) [i.e., \(Q\) is true]. Since this argument is true for any \(x \in A\), we have that for all \(x \in A, x \in B\), hence \(A\subseteq B\).
We will now prove that \(B \not\subseteq A\) by showing there is an element of \(B\) which is not an element of \(A\). Take \(x=10\). Then \(x\in B\) [as \(x=5\cdot 2\)] but \(x\not\in A\) [as \(x = \frac{5}{2} \cdot 4\) but \(4\notin \mathbb{Z}\)].
Combining the two statements above, it follows that \(A\subsetneq B\).To prove something is true for all \(x\in X\), we “let \(x\in X\)” or “suppose \(x\in X\)” with no further conditions. Whatever we conclude about \(x\) is true for all \(x\in X\). This is the technique we used in Part 1. above.
Suppose \(A\) and \(B\) are sets. Showing that \(A=B\) is the same as showing that \(A\subseteq B\) and \(B\subseteq A\).□
We show that \(2\mathbb{Q} = \mathbb{Q}\), by showing \(2\mathbb{Q} \subseteq \mathbb{Q}\) and \(\mathbb{Q} \subseteq 2\mathbb{Q}\).
Let \(x \in 2\mathbb{Q}\). Then there exists \(y \in \mathbb{Q}\) such that \(x = 2y\). By (A6), since \(2,y\in\mathbb{Q}\), we have \(x=2y\in \mathbb{Q}\). As this is true for all \(x\in 2\mathbb{Q}\) we have \(2\mathbb{Q} \subseteq \mathbb{Q}\).
Let \(x \in \mathbb{Q}\). Let \(y = \frac{x}{2}\). Note that \(\frac{1}{2} \in \mathbb{Q}\) so by (A6), since \(\frac{1}{2},x \in \mathbb{Q}\), we have \(y = \frac{x}{2} \in \mathbb{Q}\). Hence, there exists \(y \in \mathbb{Q}\) such that \(x = 2y\), so \(x\in 2\mathbb{Q}\). As this is true for all \(x\in \mathbb{Q}\) we have \(\mathbb{Q} \subseteq 2\mathbb{Q}\).
We can combine the three basic symbols together to make more complicated statements, and use truth tables to find when their truth values based on the truth values of \(P\) and \(Q\).
Let \(P\) and \(Q\) be two statements. The corresponding truth table for \((\neg P) \vee Q\) is as follows.
| \(P\) | \(Q\) | \(\neg P\) | \((\neg P)\vee Q\) |
|---|---|---|---|
| T | T | F | T |
| T | F | F | F |
| F | T | T | T |
| F | F | T | T |
Let \(P\) and \(Q\) be two statements. The corresponding truth table for \((\neg Q) \implies (\neg P)\) is as follows.
| \(P\) | \(Q\) | \(\neg P\) | \(\neg Q\) | \((\neg Q) \implies (\neg P)\) |
|---|---|---|---|---|
| T | T | F | F | T |
| T | F | F | T | F |
| F | T | T | F | T |
| F | F | T | T | T |