Section 3.2 Truth Tables
Objectives
Create truth tables for conjunctions, disjunctions, and negations.
Determine if statements are logically equivalent.
Understand and apply DeMorgan’s Laws.
Subsection 3.2.1 Truth Tables: Conjuction (and), Disjunction (or), Negation (not)
Because complex Boolean statements can get tricky to think about, we can create a truth table to keep track of what truth values for the simple statements make the complex statement true and false.
Definition 3.2.1. Truth Tables.
A table showing what the resulting truth value of a complex statement is for all the possible truth values for the simple statements.
Example 3.2.2.
Suppose you’re picking out a new couch, and your significant other says “get a sectional or something with a chaise”.
This is a complex statement made of two simpler conditions: “is a sectional”, and “has a chaise”. For simplicity, let’s use S to designate “is a sectional”, and C to designate “has a chaise”.
A truth table for this situation would look like this:
| \(S\) | \(C\) | \(S \vee C\) |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
In the table, T is used for true, and F for false. In the first row, if S is true and C is also true, then the complex statement “S or C” is true. This would be a sectional that also has a chaise, which meets our desire. (Remember that or in logic is not exclusive; if the couch has both features, it meets the condition.)
In the previous example about the couch, the truth table was really just summarizing what we already know about how the or statement work. The truth tables for the basic and, or, and not statements are shown below.
| \(A\) | \(B\) | \(A \wedge B\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
| \(A\) | \(B\) | \(A \vee B\) |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
| \(A\) | \(\sim A\) |
|---|---|
| T | F |
| F | T |
Truth tables really become useful when we analyze more complex Boolean statements
Example 3.2.7.
Create a truth table for the statement \(A \vee \sim B\)
Solution.When we create the truth table, first list the variables involved. Then rewrite the statement leaving a column for each part of the statement.
| \(A\) | \(B\) | \(A\) | \(\vee\) | \(\sim B \) |
|---|
Then we need to list all the possible truth value combinations for A and B. Notice how the first column contains 2 Ts followed by 2 Fs, and the second column alternates T, F, T, F. This pattern ensures that all 4 combinations are considered.
| \(A\) | \(B\) | \(A\) | \(\vee\) | \(\sim B \) |
|---|---|---|---|---|
| T | T | T | F | |
| T | F | T | T | |
| F | T | F | F | |
| F | F | F | T |
Notice that we had change the T's to F's and F's to T's when filling out the column for \(/sim B\)
Finally we can fill out the column with the \(/vee\text{.}\) The disjunction is true when at least one of the values in \(A\) or \(/sim B\) is true.
| \(A\) | \(B\) | \(A\) | \(\vee\) | \(\sim B \) |
|---|---|---|---|---|
| T | T | T | T | F |
| T | F | T | T | T |
| F | T | F | F | F |
| F | F | F | T | T |
The last column we completed is our final answer: TTFT
The truth table shows that \(A \vee \sim B\) is true in three cases and false in one case. If you’re wondering what the point of this is, suppose it is the last day of the baseball season and two teams, who are not playing each other, are competing for the final playoff spot. Anaheim will make the playoffs if it wins its game or if Boston does not win its game. (Anaheim owns the tie-breaker; if both teams win, or if both teams lose, then Anaheim gets the playoff spot.) If A = Anaheim wins its game and B = Boston wins its game, then \(A \vee \sim B\) represents the situation “Anaheim wins its game or Boston does not win its game”. The truth table shows us the different scenarios related to Anaheim making the playoffs. In the first row, Anaheim wins its game and Boston wins its game, so it is true that Anaheim makes the playoffs. In the second row, Anaheim wins and Boston does not win, so it is true that Anaheim makes the playoffs. In the third row, Anaheim does not win its game and Boston wins its game, so it is false that Anaheim makes the playoffs. In the fourth row, Anaheim does not win and Boston does not win, so it is true that Anaheim makes the playoffs.
Problem 3.2.11. Try It Now.
Create a truth table for this statement: \(\sim A \wedge B\)
Answer.| \(A\) | \(B\) | \(\sim A\) | \(\wedge\) | \(B\) |
|---|---|---|---|---|
| T | T | F | F | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | F | F |
We start by filling out all columns with A's and B's. Then to finish we compare \(\sim A\) with \(B\text{.}\) The conjuction (and) is true with both statements are true. The values in the \(\wedge\) column are: FFTF
Example 3.2.13.
Create a truth table for this statement: \(\left(p \wedge q \right) \vee \sim q\)
Solution.First create a row for p, q, and each item in the statement. Then fill out all possible combinations values for p and q.
| \(p\) | \(q\) | (\(p\) | \(\wedge\) | \(q\)) | \(\vee \) | \(\sim q \) |
|---|---|---|---|---|---|---|
| T | T | |||||
| T | F | |||||
| F | T | |||||
| F | F | |||||
| Step 1 | Step 1 |
Next fill out the p's and q's in the rest of the table.
| \(p\) | \(q\) | (\(p\) | \(\wedge\) | \(q\)) | \(\vee \) | \(\sim q \) |
|---|---|---|---|---|---|---|
| T | T | T | T | F | ||
| T | F | T | F | T | ||
| F | T | F | T | F | ||
| F | F | F | F | T | ||
| Step 1 | Step 1 | Step 2 | Step 2 | Step 2 |
We work inside the parentheses next; the \(\wedge\) symbol means "and" is only true when both p and q are true.
| \(p\) | \(q\) | (\(p\) | \(\wedge\) | \(q\)) | \(\vee \) | \(\sim q \) |
|---|---|---|---|---|---|---|
| T | T | T | T | T | F | |
| T | F | T | F | F | T | |
| F | T | F | F | T | F | |
| F | F | F | F | F | T | |
| Step 1 | Step 1 | Step 2 | Step 3 | Step 2 | Step 2 |
Finally we compare the result of \(p \wedge q\text{,}\) which is in the column labeled "Step 3," with the values of \(\sim q\text{.}\) We have the \(\vee\) symbol, so the statement is true if we have at least one T.
| \(p\) | \(q\) | (\(p\) | \(\wedge\) | \(q\)) | \(\vee \) | \(\sim q \) |
|---|---|---|---|---|---|---|
| T | T | T | T | T | T | F |
| T | F | T | F | F | T | T |
| F | T | F | F | T | F | F |
| F | F | F | F | F | T | T |
| Step 1 | Step 1 | Step 2 | Step 3 | Step 2 | Step 4 | Step 2 |
The final answer would be the values in the column labeled "Step 4," TTFT
Subsection 3.2.2 De Morgan's Laws
A contemporary of Boole’s, Augustus De Morgan, formalized two rules of logic that had previously been known informally. They allow us to rewrite the negation of a conjunction as a disjunction, and vice-versa.
For example, suppose you want to schedule a meeting with two colleagues at 4:30PM on Friday, and you need both of them to be available at that time. What situation would make it impossible to have the meeting? It is NOT the case that colleague a is available AND colleague b is available: \(\sim \left(a \wedge b\right)\text{.}\) This situation is equivalent to either colleague a NOT being available OR colleague b NOT being available: \(\sim a \vee \sim b\text{.}\)
Definition 3.2.18. De Morgan's Laws.
The negation of a conjunction is equivalent to the disjunction of the negation of the statements making up the conjunction. To negate an "and" statement, negate each part and change the "and" to "or".
\(\sim \left(p \wedge q \right)\) is equivalent to \(\sim p \vee \sim q\)
The negation of a disjunction is equivalent to the conjunction of the negation of the statements making up the disjunction. To negate an "or" statement, negate each part and change the "or" to "and".
\(\sim \left(p \vee q \right)\) is equivalent to \(\sim p \wedge \sim q\)
Example 3.2.19.
For Valentine’s Day, you did not get your sweetie flowers or candy: Which of the following statements is logically equivalent?
You did not get them flowers or did not get them candy.
You did not get them flowers and did not get them candy.
You got them flowers or got them candy.
This statement does not go far enough; it leaves open the possibility that you got them one of the two things.
This statement is equivalent to the original; \(\sim \left(f \vee c\right)\) is equivalent to \(\sim f \wedge \sim c\text{.}\)
This statement says that you got them something, but we know that you did not.
Statements are logically equivalent if they have the same values in a truth table. We can use truth tables to verify DeMorgan's laws.
Example 3.2.20.
Compare truth tables for \(\sim p \vee \sim q\) and \(\sim \left(p \wedge q\right)\text{.}\) Are the statements logically equivalent?
Solution.The truth table for \(\sim p \vee \sim q\) is:
| p | q | \(\sim p\) | \(\vee\) | \(\sim q\) |
|---|---|---|---|---|
| T | T | F | F | F |
| T | F | F | T | T |
| F | T | T | T | F |
| F | F | T | T | T |
| Step 1 | Step 1 | Step 2 | Step 3 | Step 2 |
Notice the values in the column labled "Step 3" are FTTT.
The truth table for \(\sim \left( p \wedge q \right)\) is:
| p | q | \(\sim\) | (\(p\) | \(\wedge\) | \(q\)) |
|---|---|---|---|---|---|
| T | T | F | T | T | T |
| T | F | T | T | F | F |
| F | T | T | F | F | T |
| F | F | T | F | F | F |
| Step 1 | Step 1 | Step 4 | Step 2 | Step 3 | Step 3 |
The values in the column labled "Step 4" are FTTT.
Both of these statements have truth tables that result in FTTT, so they are logically equivalent.
Problem 3.2.23. Try It Now.
To serve as the President of the US, a person must have been born in the US, must be at least 35 years old, and must have lived in the US for at least 14 years. What minimum set of conditions would disqualify someone from serving as President?
Answer.