Definition 1.1.
A statement is anything we can say, write or otherwise express that is either true or false.
Section 1.1 Statements
Subsection What is a Statement?
“Each of our acts makes a statement as to our purpose.”―Leo Buscaglia
When we prove theorems in mathematics, we are demonstrating the truth of certain statements. We therefore need to start our discussion of logic with a look at statements, and at how we recognize certain statements as true or false.
The key is that there must be no ambiguity. To be a statement, a sentence must be true or false, and it cannot be both. 1
Example 1.2. Statement Examples.
- “The sky is blue” is a statement, as it is either true or false.
- “Your birthday is October 23rd” is a statement, as it is either your birtday or it isn't.
- “The mitochondria is the powerhouse of the cell” is a statement.
- “Do a backflip” is not a statement, because it cannot be said to be either true or false.
For something to be a statement, it has to be either true or false in principle; it does not matter whether we personally can verify its truth or falsity.
Some sentences that are mathematical in nature often are not statements because we may not know precisely what a variable represents.
Example 1.3. Mathematical (Non-)Statements.
- The equation \(2x + 5 = 10\) is not a statement since we do not know what \(x\) represents.
- \(1 + 2\) isn't a statement either. The mathematical operation “Add one to two” does not have a truth value, it's just an instruction.
Subsection Combining Statements
“Conjunction junction, what's your function?”―Schoolhouse Rock
What makes statements valuable for our purposes is that there are a number of useful ways of forming new statements out of old ones. An analog to this would be the ways we have of combining numbers to get new ones, such as addition and multiplication; if we did not have these operations, then numbers would not be very interesting.
In this section we will discuss five ways of forming new statements out of old ones, corresponding to the English expressions: and; or; not; if, then; if and only if.
Definition 1.4. Conjunction.
Let \(P\) and \(Q\) be statements. The conjunction of \(P\) and \(Q\text{,}\) which is denoted \(P \wedge Q\text{,}\) is the statement that, intuitively, is true if both \(P\) and \(Q\) are true, and is false otherwise. We read \(P \wedge Q\) as “\(P\) and \(Q\text{.}\)” The precise definition of \(P \wedge Q\) is given by the “truth table”
| \(P\) | \(Q\) | \(P\wedge Q\) |
| \(T\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(F\) |
| \(F\) | \(T\) | \(F\) |
| \(F\) | \(F\) | \(F\) |
Remark 1.5.
Truth tables will be at the center of the next several sections, we will be using these a lot!
Example 1.6.
Let \(P =\) “it is raining today,” and let \(Q =\) “it is cold today.” The statement \(P \wedge Q\) would formally be “it is raining today and it is cold today.”
We could express the same idea more succinctly in English by saying “it is raining and cold today.” In general, we will try to use statements that read well in English, as well as being logically correct.
Warning 1.7.
The colloquial use of the word “and” differs from the mathematical usage stated above. The mathematical usage means the above truth table, and nothing else, while colloquially there are other meanings in addition to this one. One source of confusion involving the word “and” that is well worth avoiding is the colloquial use of this word in the sense of “therefore.”
Definition 1.8. Disjunction.
Let \(P\) and \(Q\) be statements. The disjunction of \(P\) and \(Q\text{,}\) which is denoted \(P \vee Q\text{,}\) is the statement that, intuitively, is true if either \(P\) is true or \(Q\) is true or both are true, and is false otherwise. We read \(P \vee Q\) as “\(P\) or \(Q\text{.}\)” The precise definition of \(P \vee Q\) is given by the truth table
| \(P\) | \(Q\) | \(P\vee Q\) |
| \(T\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(T\) |
| \(F\) | \(T\) | \(T\) |
| \(F\) | \(F\) | \(F\) |
Remark 1.9.
The mathematical use of the word “or” always means an inclusive “or,” so that if “\(P\) or \(Q\)” is true, then either \(P\) is true, or \(Q\) is true, or both \(P\) and \(Q\) are true.
Example 1.10.
A simple example of a disjunction is the statement “my car is red or it will rain today.” This statement has the form \(P \vee Q\text{,}\) where \(P =\) “my car is red,” and \(Q =\) “it will rain today.” The truth of this statement implies that at least one of the statements “my car is red” or “it will rain today” is true. The only thing not allowed is that both “my car is red” and “it will rain today” are false.
Definition 1.11. Negation.
Let \(P\) and \(Q\) be statements. The negation of \(P\text{,}\) which is denoted \(¬P\text{,}\) is the statement that, intuitively, is true if \(P\) is false, and is false if \(P\) is true. We read \(¬P\) as “not \(P\text{.}\)” The precise definition of \(¬P\) is given in the truth table
| \(P\) | \(\neg P\) |
| \(T\) | \(F\) |
| \(F\) | \(T\) |
Definition 1.12. Conditional Statement.
Let \(P\) and \(Q\) be statements. The conditional from \(P\) to \(Q\text{,}\) which is denoted \(P \to Q\text{,}\) is the statement that, intuitively, is true if it is never the case that \(P\) is true and \(Q\) is false. We read \(P \to Q\) as if “\(P\) then \(Q\)”. The precise definition of \(P \to Q\) is given in the truth table
| \(P\) | \(Q\) | \(P\to Q\) |
| \(T\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(F\) |
| \(F\) | \(T\) | \(T\) |
| \(F\) | \(F\) | \(T\) |
The above truth table for \(P \to Q\text{,}\) which is universally accepted by mathematicians and logicians, may seem strange at first glance, and perhaps even contrary to intuition, but it is important to get used to it, because we will always use \(P \to Q\) as we have defined it.
Example 1.13.
A simple example of a conditional statement is “if it rains today, then I will see a movie this evening.” This statement has the form \(P \to Q\text{,}\) where \(P =\) “it rains today,” and \(Q =\) “I will see a movie this evening.” The truth of this statement does not say that it is raining today, nor that I will see a movie this evening. It only says what will happen if it rains today, which is that I will see a movie this evening. If it does not rain, I still might see a movie this evening, or I might not; both of these possibilities would be consistent with the truth of the original statement “if it rains today, then I will see a movie this evening.”
Convention 1.14.
There are a number of variations as to how to write the statement \(P \to Q\) in English. In addition to writing “if \(P\) then \(Q\text{,}\)” we could just as well write any of the following:
- If \(P\text{,}\) \(Q\text{;}\)
- \(Q\) if \(P\text{;}\)
- \(P\) only if \(Q\text{;}\)
- \(Q\) provided that \(P\text{;}\)
- Assuming that \(P\text{,}\) then \(Q\text{;}\)
- \(Q\) given that \(P\text{;}\)
- \(P\) is sufficient for \(Q\text{;}\)
- \(Q\) is necessary for \(P\text{.}\)
Definition 1.15. Biconditional Statement.
Let \(P\) and \(Q\) be statements. The biconditional from \(P\) to \(Q\text{,}\) which is denoted \(P ↔ Q\text{,}\) is the statement that, intuitively, is true if \(P\) and \(Q\) are both true or both false, and is false otherwise. We read \(P ↔ Q\) as “\(P\) if and only if \(Q\text{.}\)” The phrase “if and only if” is often abbreviated as “iff.” The precise definition of \(P ↔ Q\) is given in the truth table
| \(P\) | \(Q\) | \(P\to Q\) |
| \(T\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(F\) |
| \(F\) | \(T\) | \(T\) |
| \(F\) | \(F\) | \(T\) |
Example 1.16.
An example of a biconditional statement is “I will go for a walk if and only if Fred will join me.” This statement has the form \(P ↔ Q\text{,}\) where \(P =\) “I will go for a walk,” and \(Q =\) “Fred will join me.” The truth of this statement does not say that I will go for a walk, or that Fred will join me. It says that either Fred will join me and I will go for a walk, or that neither of these things will happen. In other words, it could not be the case that Fred joins me and yet I do not go for a walk, and it also could not be the case that I go for a walk, and yet Fred has not joined me.
Convention 1.17.
There are some variations as to how to write the statement \(P ↔ Q\) in English. In addition to writing “\(P\) if and only if \(Q\text{,}\)” it is common to write “\(P\) is necessary and sufficient for \(Q\text{.}\)”
Rather than memorizing the truth tables, for many people it is easier to remember the rules summarized in Table 1.18
| Operator | Symbolic Form | Truth Values |
| Conjunction | \(P\wedge Q\) | True only when both \(P\) and \(Q\) are true. |
| Disjunction | \(P\vee Q\) | False only when both \(P\) and \(Q\) are false. |
| Negation | \(\neg P\) | Opposite truth value of \(P\) |
| Conditional | \(P\to Q\) | False only when \(P\) is true and \(Q\) is false. |
| Biconditional | \(P ↔ Q\) | True when either both \(P\) and \(Q\) are true or when \(P\) and \(Q\) are false |
Subsection Verifying Compound Statements
Now that we have defined our five basic ways of combining statements, we can form more complicated compound statements by using combinations of the basic operations.
Convention 1.19. Order of Operations.
We use the standard convention that \(¬\) takes precedence over the other four operations, but none of these four takes precedence over the others.
Example 1.20.
We can form \(P ∨ (Q → ¬R)\) out of statements \(P\text{,}\) \(Q\) and \(R\text{.}\) We can form the truth table for the statement \(P ∨ (Q → ¬R)\text{,}\) doing one operation at a time, as follows:
| \(P\) | \(Q\) | \(R\) | \(\neg R\) | \(Q\to\neg R\) | \(P \vee (Q\to \neg R)\) |
| \(T\) | \(T\) | \(T\) | \(F\) | \(F\) | \(T\) |
| \(T\) | \(T\) | \(F\) | \(T\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(T\) | \(F\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(F\) | \(T\) | \(T\) | \(T\) |
| \(F\) | \(T\) | \(T\) | \(F\) | \(F\) | \(F\) |
| \(F\) | \(T\) | \(F\) | \(T\) | \(T\) | \(T\) |
| \(F\) | \(F\) | \(T\) | \(F\) | \(T\) | \(T\) |
| \(F\) | \(F\) | \(F\) | \(T\) | \(T\) | \(T\) |
To save time and effort, it is possible to write a smaller truth table with the same information as the truth table above, by writing one column at a time, and labeling the columns in the order of how we write them. In the truth table shown below, we first write columns 1 and 2, which are just copies of the P and Q columns; we then write column 3, which is the negation of the R column; column 4 is formed from columns 2 and 3, and column 5 is formed from columns 1 and 4. We put the label “5” in a box, to highlight that its column is the final result of the truth table, and refers to the compound statement in which we are interested. It is, however, the same result as in the previous truth table.
| \(P\) | \(Q\) | \(R\) | \(P\) | \(\vee\) | \((Q\) | \(\to\) | \(\neg R)\) |
| \(T\) | \(T\) | \(T\) | \(T\) | \(T\) | \(T\) | \(F\) | \(F\) |
| \(T\) | \(T\) | \(F\) | \(T\) | \(T\) | \(T\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(T\) | \(T\) | \(T\) | \(F\) | \(T\) | \(F\) |
| \(T\) | \(F\) | \(F\) | \(T\) | \(T\) | \(F \) | \(T\) | \(T\) |
| \(F\) | \(T\) | \(T\) | \(F\) | \(F\) | \(T\) | \(F\) | \(F\) |
| \(F\) | \(T\) | \(F\) | \(F\) | \(T\) | \(T\) | \(T\) | \(T\) |
| \(F\) | \(F\) | \(T\) | \(F\) | \(T\) | \(F\) | \(T\) | \(F\) |
| \(F\) | \(F\) | \(F\) | \(F\) | \(T\) | \(F\) | \(T\) | \(T\) |
| \(\) | \(\) | \(\) | \(1\) | \(5\) | \(2\) | \(4\) | \(3\) |
Remark 1.21.
The role that parentheses play in avoiding ambiguity in statements written with symbols is often played in English sentences by punctuation.
Subsection Tautologies and Contradictions
“Do I contradict myself? Very well, then, I contradict myself; I am large - I contain multitudes.”―Walt Whitman
Definition 1.22. Tautology.
A tautology is a statement that is always true by logical necessity, regardless of whether the component statements are true or false, and regardless of what we happen to observe in the real world.
Example 1.23.
An example of a tautology is the statement “Irene has red hair or she does not have red hair.” It seems intuitively clear that this statement is a tautology, and we can verify this fact formally by using truth tables. Let \(P =\) “Irene has red hair.” Then our purported tautology is the statement \(P \vee ¬P\text{.}\) The truth table for this statement is
| \(P\) | \(P\) | \(\vee\) | \(\neg P\) |
| \(T\) | \(T\) | \(T\) | \(F\) |
| \(F\) | \(F\) | \(T\) | \(T\) |
| \(1\) | \(3\) | \(2\) |
We see in column \(3\) that the statement \(P \vee ¬P\) is always true, regardless of whether \(P\) is true or false. This fact tells us that \(P \vee ¬P\) is a tautology.
In general, a statement is a tautology if, as verified using a truth table, it is always true, regardless of whether its component statements are true or false.
Exploration 1.24.
Verify that the statement \([(P ∧ Q) → R] → [P → (Q → R)\) is a tautology by constructing a truth table.
Definition 1.25. Contradiction.
A contradiction is a statement that is always false by logical necessity.
Example 1.26.
The statement “Irene has red hair and she does not have red hair” is a contradiction. In symbols this statement is \(P \wedge ¬P\text{,}\) and it has truth table
| \(P\) | \(P\) | \(\wedge\) | \(\neg P\) |
| \(T\) | \(T\) | \(F\) | \(F\) |
| \(F\) | \(F\) | \(F\) | \(T\) |
| \(1\) | \(3\) | \(2\) |
The statement \(P \wedge ¬P\) is always false, regardless of whether \(P\) is true or false.
In general, a statement is a contradiction if, as verified using a truth table, it is always false, regardless of whether its component statements are true or false.
This assumptions, often referred to as the Law of the Excluded Middle (and known formally as bivalence), may seem innocuous enough, but in fact some mathematicians have chosen to work without this powerful axiom.
