Section 2.1 Statements and connectives
In mathematics, we spend a lot of time worried about whether a sentence is true or false. This is fine in the case of a simple sentence such as “The number \(2\) is prime.” (That sentence is true.) But there are much more complicated sentences lurking around, and whole constellations of sentences whose truth depends on one another. For example, a famous unsolved problem in the theory of prime numbers is called the Riemann hypothesis. Many mathematical statements are true if the Riemann hypothesis is true. Some theorems live or die by the Riemann hypothesis.
So, we are interested in tools that will allow us to judge whether complicated statements are true. Such models of truth are called logic.
Subsection 2.1.1 Propositional logic
Propositional logic concerns the study of statements and connectives between those statements.
Definition 2.1.1.
A statement is a sentence that is either true or false.
Example 2.1.2.
Atomic propositional statements of the type discussed in this chapter are flatly always true or false. You may think of them in the same way you think of constant functions in algebra, like how the function \(f(x)=2\) always outputs the value \(2\) no matter what \(x\) is. Atomic statements are denoted with lowercase letters \(p\text{,}\) \(q\text{,}\) \(r\text{,}\) etc. If the only statements were atomic, logic would be boring. Fortunately, we can combine statements with connectives. In the next chapter, we will look at predicate statements whose truth values depend on an input. Likewise, these may be thought of as the non-constant functions.
Compound statements arise from combining atomic statements with connectives. They are denoted using Greek letters like \(\varphi\) (“phi”, pronounced fee), \(\psi\) (“psi”, pronounced sy), and \(\gamma\) (“gamma”). The truth of a compound statement depends on the connectives involved and the truth values of the constituent statements. A tool for determining the truth of a compound statement is called a truth table.
In a truth table for the compound statement \(\varphi\text{,}\) the left side of the table is the atomic statements involved in \(\varphi\) and the right side of the table is \(\varphi\) itself. Each row gives a possible combination of truth values for the atomic statements, and the corresponding truth value for \(\varphi\text{.}\) At this point, it is easier to start introducing connectives and seeing some truth tables.
Definition 2.1.3.
Let \(p\) be a statement. Its negation is the statement \(\neg p\text{,}\) the statement that is true exactly when \(p\) is false and vice-versa. Below is the truth table for \(\neg p\text{.}\)
| \(p\) | \(\neg p\) |
| \(T\) | \(F\) |
| \(F\) | \(T\) |
Above you see your first truth table. On the left side of the table are the component statements, the ones whose truth the compound statement depends on. On the right is the compound statement we are interested in. Sometimes, we use additional columns to “break down” the compound statement if it is complicated.
Each row of the truth table is a distinct combination of truth values. Since \(\neg p\) depends only on \(p\text{,}\) we only need to consider the case that \(p\) is true and the case \(p\) is false.
The statement \(\neg p\) is typically read "not \(p\)" or "it is not the case that \(p\) is true." If we have an English rendering of \(p\text{,}\) we try to write \(\neg p\) in a natural-sounding way that also conveys its logical structure.
Example 2.1.5.
Suppose \(p\) represents the statement “It is raining.” Then, \(\neg p\) stands for “It is not raining.”
Let \(q\) represent the statement “\(2\) is a prime number.” Then \(\neg q\) stands for “\(2\) is not a prime number.” Since we know \(q\) is true, \(\neg q\) is false.
Negation is called a unary connective because it only involves one statement. (Remember the unary operation on sets?) Our remaining connectives are all binary connectives, as they combine two statements.
Definition 2.1.6.
Let \(p\) and \(q\) be statements. Their conjunction is the statement \(p \wedge q\text{,}\) which is true only when \(p\) and \(q\) are both true. The statements \(p\) and \(q\) are called conjuncts.
| \(p\) | \(q\) | \(p \wedge q\) |
| \(T\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(F\) |
| \(F\) | \(T\) | \(F\) |
| \(F\) | \(F\) | \(F\) |
Here is a more complicated truth table because \(p \wedge q\) depends on both \(p\) and \(q\text{.}\) There are now four possibilities: \(p\) and \(q\) both true, \(p\) true while \(q\) false, \(p\) false while \(q\) true, and both false. In general, if you have \(n\) different letters in your statement, your truth table will have \(2^n\) rows. (Each row of the truth table is a function from your set of letters to the set \(\{T,F\}\text{,}\) and we learned there are \(2^n\) such functions last chapter.)
Does it matter what order the rows are in? Well, yes and no. Mathematically, no; the truth table conveys the same information if you change the order of the rows. However, it is easier to write and read truth tables if you pick a convention and stick to it. We start by listing all the rows where our first letter is true. In the rows where the first letter is true, we start with the rows where the second letter is true, and so on. What this looks like visually is cutting the rows in half repeatedly, so that your left-most letter's column is half true and half false, the next letter's column is a quarter true, quarter false, quarter true, quarter false, etc., and the right-most letter's column alternates between true and false.
The symbol in the conjunction is called a “wedge,” and \(p \wedge q\) is read “\(p\) and \(q\text{.}\)” This definition is meant to be analogous to our English understanding of the word “and.”
Example 2.1.8.
Letting \(p\) be “It is raining” and \(q\) be “I brought an umbrella,” the statement \(p \wedge q\) is “It is raining and I brought an umbrella.” The statement is true only if it is currently raining and the speaker brought an umbrella. If it is not raining, or if the speaker did not bring their umbrella, the conjunction is false. Confirm this with the truth table above. For instance, in the third row, where it is not raining but the speaker brought an umbrella, the statement is false.
| \(p\) | \(q\) | \(p \wedge q\) |
| \(F\) | \(T\) | \(F\) |
Example 2.1.10.
Consider “\(2\) is a prime number or \(2\) is odd”. This statement is the conjunction of the conjuncts “\(2\) is a prime number” and “\(2\) is (an) odd (number)”. The conjunction is false, because even though \(2\) is prime, it is not odd.
If \(r\) were the statement that \(2\) is prime and \(s\) were the statement that \(2\) is odd, then “\(2\) is a prime number or \(2\) is odd” can be symbolized as \(r \wedge s\text{.}\)
Definition 2.1.11.
Let \(p\) and \(q\) be statements. Their disjunction is the statement \(p \vee q\text{,}\) which is true if at least one of \(p\) or \(q\) is true. The statements \(p\) and \(q\) are called disjuncts.
| \(p\) | \(q\) | \(p \vee q\) |
| \(T\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(T\) |
| \(F\) | \(T\) | \(T\) |
| \(F\) | \(F\) | \(F\) |
The symbol in the conjunction is called a “vee” and \(p \vee q\) is read “\(p\) or \(q\text{.}\)” This definition is meant to be analogous to our English understanding of the word “or.” The statements \(p\) and \(q\) are called disjuncts. (Did you notice that I was able to copy and paste from an above paragraph? Conjunction and disjunction share a very similar structure. They are said to be dual to one another.)
Example 2.1.13.
Letting \(p\) be “It is raining” and \(q\) be “I brought an umbrella,” the statement \(p \vee q\) is “It is raining or I brought an umbrella.” This time, the speaker only needs to meet one of their conditions. They are telling the truth as long as it is raining or they brought an umbrella, or even if both statements are true. This time, if it is not raining but the speaker brought their umbrella anyway, the disjunction is true as evidenced by the third row of the truth table.
| \(p\) | \(q\) | \(p \vee q\) |
| \(F\) | \(T\) | \(T\) |
Example 2.1.15.
Consider the statement “\(2\) is a prime number or \(2\) is odd”. This is the disjunction of the disjuncts “\(2\) is a prime number” and “\(2\) is (an) odd (number)”. This disjunction is true, since at least one of the disjuncts is true.
Symbolically, again let \(r\) be the statement that \(2\) is prime and \(s\) be the statement that \(2\) is odd. Then “\(2\) is a prime number or \(2\) is odd” is \(r \vee s\text{.}\)
Of great importance to computer science and electrical engineering, but not so much in mathematics (so it will not appear again in this book), is the exclusive disjunction (or “exclusive-or”). It is a modified disjunction where exactly one of the disjuncts must be true.
Definition 2.1.16.
If \(p\) and \(q\) are statements, their exclusive disjunction is the statement \(p \oplus q\text{,}\) which is true if exactly one of \(p\) and \(q\) is true, but not both.
| \(p\) | \(q\) | \(p \oplus q\) |
| \(T\) | \(T\) | \(F\) |
| \(T\) | \(F\) | \(T\) |
| \(F\) | \(T\) | \(T\) |
| \(F\) | \(F\) | \(F\) |
Example 2.1.18.
The statement "You can have the soup or the salad" is likely meant as an exclusive disjunction.
In mathematics, disjunctions are generally considered inclusive unless stated otherwise.
Our next connective is probably the most important, as it captures the idea of one statement implying another. As we discussed earlier in the chapter, mathematics is nothing but such statements. It is also the only connective that does not map so closely onto its English interpretation. So, we will consider each row of the truth table carefully in an example.
Definition 2.1.19.
If \(p\) and \(q\) are statements, the conditional statement \(p \to q\) is true if \(p\) can never be true while \(q\) is false. We call \(p\) the antecedent and \(q\) the consequent.
| \(p\) | \(q\) | \(p \to q\) |
| \(T\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(F\) |
| \(F\) | \(T\) | \(T\) |
| \(F\) | \(F\) | \(T\) |
There are many ways to read \(p \to q\text{,}\) including:
“if \(p\text{,}\) then \(q\)”,
“\(p\) implies \(q\)”, and
“\(p\) is sufficient for \(q\text{.}\)”
That \(p \to q\) is true in the bottom two rows may surprise you. So, let's consider each row separately.
Example 2.1.21.
Consider the statements \(p\text{,}\) “You do your homework”, and “q”, “You pass your math class.” Then the statement \(p\to q\) is “If you do your homework then you pass your math class.”
| \(p\) | \(q\) | \(p \to q\) |
| \(T\) | \(T\) | \(T\) |
The first row of the truth table corresponds to the situation where you do your homework and pass your math class. In this case, you fulfilled the conditions of the speaker's promise (doing your homework) and received the promised outcome (a passing grade). Therefore, we consider the speaker truthful.
| \(p\) | \(q\) | \(p \to q\) |
| \(T\) | \(F\) | \(F\) |
In the second row, you do your homework but do not pass the class. Even though you held up your end of the bargain, you do not receive the promised result. The speaker lied, so the statement \(p \to q\) is false.
| \(p\) | \(q\) | \(p \to q\) |
| \(F\) | \(T\) | \(T\) |
| \(F\) | \(F\) | \(T\) |
Let's consider the last two rows, where you don't do your homework. In these two cases, whether you pass or not, the speaker hasn't lied! You didn't hold up your end of the bargain. So, here, we consider \(p \to q\) true.
Another interpretation is that \(p \to q\) means that \(p\) cannot be true without \(q\text{.}\) In the second row, \(p\) is true but \(q\) isn't, contradicting the definition of the conditional statement.
It is critically important that \(p \to q\) and \(q \to p\) are not the same sentence.
Example 2.1.25.
With the notation from the preceding example, \(p \to q\) says “If you do your homework you will pass the class” and \(q \to p\) means “If you passed the class then you did your homework.” These are not the same statement. For example, there may be a way to pass the class without doing homework (such as acing every exam).
If \(p \to q\) and \(q \to p\) do happen to both be true— meaning that \(p\) and \(q\) each necessitate the other to be true —then we get the following type of statement.
Definition 2.1.26.
If \(p\) and \(q\) are statements, the biconditional statement \(p \leftrightarrow q\) is true if \(p\) and \(q\) are both true, or both false.
| \(p\) | \(q\) | \(p \leftrightarrow q\) |
| \(T\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(F\) |
| \(F\) | \(T\) | \(F\) |
| \(F\) | \(F\) | \(T\) |
The statement \(p \leftrightarrow q\) may be read as
“\(p\) if and only if \(q\text{,}\)”
“\(p\) is necessary and sufficient for \(q\text{,}\)" and”
“\(p\) is equivalent to \(q\text{.}\)”
Example 2.1.28.
Continuing from the prior examples, let \(p\) be “You do your homework” and \(q\) be “You pass the class”. The statement \(p \leftrightarrow q\) says “You will pass the class if and only if you do your homework.” (This is technically \(q\leftrightarrow p\text{,}\) but we will soon see these are the same statement.)
This statement means that if you do your homework, you will pass the class (doing homework is sufficient for passing), and conversely that the only way to pass is if your homework is done (doing homework is necessary sufficient for passing). If a student passes without doing homework, or does homework but doesn't pass, then the statement \(p \leftrightarrow q\) would be false.
Subsection 2.1.2 Compound statements
We are not required to use one connective at a time, of course. Most statements involve two or more connectives being combined at once. If \(\varphi\) and \(\psi\) are statements, then so are:
\(\neg \varphi\) and \(\neg \psi\text{,}\)
\(\varphi \wedge \psi\text{,}\)
\(\varphi \vee \psi\text{,}\)
\(\varphi \to \psi\text{,}\) and
\(\varphi \leftrightarrow \psi\text{.}\)
This fact allows us to combine as many connectives and statements as we like.
How should we read the statement \(p \wedge q \to r\text{?}\) Should it be read “\(p\text{;}\) also, if \(q\) then \(r\)”? Or, “If \(p\) and \(q\text{,}\) then \(r\text{?}\)” Just like with arithmetic, there are conventions defining which connective to apply first. The order of operations is thus:
Negation (\(\neg\))
Conjunction (\(\wedge\)) and disjunction (\(\vee\))
Implication (\(\to\))
Mutual implication (\(\leftrightarrow\))
Example 2.1.29.
Because of the order of operations, \(p \wedge q \to r\) is the same as \((p \wedge q) \to r\text{.}\) The other statement, \(p \wedge (q \to r)\text{,}\) means something different.
However, to eliminate confusion in this book we will always use parentheses to make our statements clear. So, for now at least, it is not necessary to memorize the order of operations.
Remember that a statement involving \(n\) letters will have \(2^n\) rows in its truth table. The column for the left-most statement letter should be true for half the rows then false for half the rows, and you should continue dividing the rows in half so that the right-most statement letter's column is alternating between true and false.
Finally, when constructing the truth table for a complex statement, it is a good idea to break a statement into small "chunks" and make a column for each "chunk" separately. Observe the following examples.
Example 2.1.30.
Construct the truth table for the statement \((\neg u \vee \neg v) \leftrightarrow w\text{.}\)
First, observe that there are three statement letters involved: \(u\text{,}\) \(v\text{,}\) and \(w\text{.}\) Therefore our truth table will have \(2^3=8\) rows. We will include additional columns for \(\neg u\text{,}\) \(\neg v\text{,}\) and \(\neg u \vee \neg v\text{.}\) Once you have more practice, all of these additional columns are not necessary, but for now they help.
As said before, the left-most letter column will be half true and half false. We will continue dividing in half until the right-most letter column is alternating.
| \(u\) | \(v\) | \(w\) | \(\neg u\) | \(\neg v\) | \(\neg u \vee \neg v\) | \((\neg u \vee \neg v) \leftrightarrow w\) |
| \(T\) | \(T\) | \(T\) | \(F\) | \(F\) | \(F\) | \(F\) |
| \(T\) | \(T\) | \(F\) | \(F\) | \(F\) | \(F\) | \(T\) |
| \(T\) | \(F\) | \(T\) | \(F\) | \(T\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(F\) | \(F\) | \(T\) | \(T\) | \(F\) |
| \(F\) | \(T\) | \(T\) | \(T\) | \(F\) | \(T\) | \(T\) |
| \(F\) | \(T\) | \(F\) | \(T\) | \(F\) | \(T\) | \(F\) |
| \(F\) | \(F\) | \(T\) | \(T\) | \(T\) | \(T\) | \(T\) |
| \(F\) | \(F\) | \(F\) | \(T\) | \(T\) | \(T\) | \(F\) |
This can be a lot to take in all at once. Let's take it one row at a time. On the first row, all three statements are true. Since \(u\) and \(v\) are both true, that means \(\neg u\) and \(\neg v\) are both false. Because neither \(\neg u\) nor \(\neg v\) is true, the disjunction \(\neg u \vee \neg v\) must be false. The biconditional requires \(\neg u \vee \neg v\) and \(w\) to have the same truth value. Since \(\neg u \vee \neg v\) is false but \(w\) is true, the biconditional statement \((\neg u \vee \neg v) \leftrightarrow w\) is false.
See if you can run through a similar line of reasoning for the other seven rows of the truth table to understand why each of them is the way it is.
Example 2.1.32.
Write down the truth table for the statement \((p \wedge q) \to (r \to \neg s)\text{.}\)
As with the preceding example, go through each row and make sure you understand where each truth value comes from.
| \(p\) | \(q\) | \(r\) | \(s\) | \(p \wedge q\) | \(\neg s\) | \(r \to \neg s\) | \((p \wedge q) \to (r \to \neg s)\) |
| \(T\) | \(T\) | \(T\) | \(T\) | \(T\) | \(F\) | \(F\) | \(F\) |
| \(T\) | \(T\) | \(T\) | \(F\) | \(T\) | \(T\) | \(T\) | \(T\) |
| \(T\) | \(T\) | \(F\) | \(T\) | \(T\) | \(F\) | \(T\) | \(T\) |
| \(T\) | \(T\) | \(F\) | \(F\) | \(T\) | \(T\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(T\) | \(T\) | \(F\) | \(F\) | \(F\) | \(T\) |
| \(T\) | \(F\) | \(T\) | \(F\) | \(F\) | \(T\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(F\) | \(T\) | \(F\) | \(F\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(F\) | \(F\) | \(F\) | \(T\) | \(T\) | \(T\) |
| \(F\) | \(T\) | \(T\) | \(T\) | \(F\) | \(F\) | \(F\) | \(T\) |
| \(F\) | \(T\) | \(T\) | \(F\) | \(F\) | \(T\) | \(T\) | \(T\) |
| \(F\) | \(T\) | \(F\) | \(T\) | \(F\) | \(F\) | \(T\) | \(T\) |
| \(F\) | \(T\) | \(F\) | \(F\) | \(F\) | \(T\) | \(T\) | \(T\) |
| \(F\) | \(F\) | \(T\) | \(T\) | \(F\) | \(F\) | \(F\) | \(T\) |
| \(F\) | \(F\) | \(T\) | \(F\) | \(F\) | \(T\) | \(T\) | \(T\) |
| \(F\) | \(F\) | \(F\) | \(T\) | \(F\) | \(F\) | \(T\) | \(T\) |
| \(F\) | \(F\) | \(F\) | \(F\) | \(F\) | \(T\) | \(T\) | \(T\) |
There are tricks to calculate truth tables more efficiently. For example, since a conjunction is only true when both conjuncts are true, you can find those rows first, put \(T\text{,}\) and then quickly fill in \(F\) for the remaining rows. Similar tricks exist for other types of statements. Practice will help you find these tricks for yourself!