- “\(2+3=5\)” is a statement. It is a true statement.
- “\(2+1=5\)” is a statement. It is a false statement.
- “\(x+y=5\)” is not a statement. It is neither true nor false. If we had additional information, such as specific information about the variables, then this might be a statement.
- “I ate breakfast today.” is a statement. Although you might not be able to determine whether I ate breakfast, the statement is either true or false.
Section 2.1 Truth-Tables and Logical Equivalence
We want to understand what makes a mathematical proof. One of the foundations for proofs is logical structure. If we build a good foundation in logic, then we can better understand mathematical statements and proof structures. So we begin by looking at logical forms, independent of content.
A logical argument consists of premises and a conclusion. The premises and conclusion are statements. A statement is a sentence that is either true of false (not both!).
Example 2.1.1. Statements.
If \(p\) and \(q\) are variables representing statements, we can combine these statements into new statements using logical connectives.
Logical Connectives: NOT, AND, OR.
-
Negation.NOT. Notation: \(\sim p\), read as “not \(p\text{.}\)”
-
Conjunction.AND. Notation: \(p\wedge q\), read as “\(p\) and \(q\text{.}\)”
-
Disjunction.OR. Notation: \(p\vee q\), read as “\(p\) or \(q\text{.}\)”
Our goal is to determine when these new statements are true or false based on whether \(p\) and \(q\) are true or false. We can create a truth-table that looks at all the possibilities of true of false for \(p\) and \(q\text{.}\) When writing a truth-table, make a column for each variable, list all the possible cases of true and false, then for each case, determine whether the new statement (with the connective) is true or false.
| \(p\) | \(\sim p\) |
| T | F |
| F | T |
It should make sense that if we negate T we get F, and vice versa.
| \(p\) | \(q\) | \(p\wedge q\) |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Again, the truth values for an “and” statement should make sense. The only time it should be true is if both parts of the statement are true.
| \(p\) | \(q\) | \(p\vee q\) |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
The truth values for an “or” statement should, mostly, make sense, as long as one part of the “or” statement is true, the whole statement is true. You may ask about the case where both parts are true. We think of this as an “inclusive or,” which means we allow both to be true. For example, “A computer science major must take Math 175 or Math 250.” You will still get a major if you take both. There is a connective for an “exclusive or” (one or the other, not both), but we won’t use it in this course.
Now that we can connect two statements, we can connect as many as we’d like using multiple quantifiers. For example, we could form the statement \(p\vee(q\ \wedge \sim p)\text{.}\) Make sure you use parentheses when combining statements. For example, \(\sim p\vee q\) is not the same as \(\sim (p\vee q)\text{.}\)
| \(p\) | \(q\) | \(\sim p\) | \(\sim p \vee q\) | \(p \vee q\) | \(\sim (p \vee q)\) |
| T | T | F | T | T | F |
| T | F | F | F | T | F |
| F | T | T | T | T | F |
| F | F | T | T | F | T |
Activity 2.1.1.
Give the truth-table for \(\sim p\ \vee \sim q\text{.}\)
Activity 2.1.2.
Give the truth-table for \((p \vee q) \wedge \sim(p \wedge q)\text{.}\)
Activity 2.1.3.
truth-tables can have more than two variables. We just need to make sure we have a row for every possible combination of truth values for the variables. How many rows will you need in a truth-table for 3 variables? Give the truth-table for \((p \wedge q) \vee r\text{.}\)
One of the things we want to be able to do is to translate English (or mathematical) sentences into logical statements. We have to be careful about how common phrases are really hidden “and”s. For example, “\(p\) but \(q\)” is really \(p\wedge q\text{.}\) Similarly, “neither \(p\) nor \(q\)” is really \(\sim p\ \wedge \sim q\text{.}\)
Definition 2.1.6.
A tautology is a statement that is always true.
For example, \(p\ \vee \sim p\) is a tautology. If you check the truth-table, you will see that the only values in the column for the statement are T.
Definition 2.1.7.
A contradiction is a statement that is always false.
For example, \(p\ \wedge \sim p\) is a contradiction. If you check the truth-table, you will see that the only values in the column for the statement are F.
Note that tautologies and contradictions are logical statements that are always true or always false, independent of the content of \(p\text{.}\)
If we want to make bigger statements using tautologies or contradictions, we can use \(\mathbf{t}\) to represent a tautology and \(\mathbf{c}\) to represent a contradiction. For example, we could find the truth-table for \(p\wedge \mathbf{t}\text{.}\)
Example 2.1.8. Example of \(p\wedge \mathbf{t}\).
| \(p\) | \(\mathbf{t}\) | \(p\wedge \mathbf{t}\) |
| T | T | T |
| F | T | F |
Definition 2.1.10.
Two statements are logically equivalent if they have identical truth-tables. If statements \(P\) and \(Q\) are logically equivalent, we denote it \(P\equiv Q\).
For example, we can see that \(p\) is logically equivalent to \(p\wedge \mathbf{t}\) by comparing the first and last columns of Table 2.1.9.
Activity 2.1.4.
Use a truth-table to determine if \(\sim(p \vee q)\) and \(\sim p\ \vee \sim q\) are logically equivalent. What does this tell you about “distributing” negation?
Activity 2.1.5.
Use a truth-table to show \(\sim(p \vee q)\) and \(\sim p\ \wedge \sim q\) are logically equivalent.
Activity 2.1.6.
Use a truth-table to show \(\sim(p \wedge q)\) and \(\sim p\ \vee \sim q\) are logically equivalent.
The equivalences in Activity 2.1.5 and Activity 2.1.6 are called DeMorgan’s Laws. These are useful equivalences and are worth committing to memory. As we’ve seen in the above activities, we cannot simply distribute a negation sign. However, DeMorgan’s Laws allow us to distribute the negation as long as we also change from “and” to “or” and vice versa. Given the importance of this concept in mathematics, it is useful at this point to convince yourself that the negation of and “and” statement is an “or” statement and vice versa using statements in English. For example, if the weather is not cold and rainy, then it is either not cold or not rainy.
One thing to be careful about with English statements is that they do not naturally contain parentheses, we often really have to think about the meaning of the statement and infer the intended parentheses. Even in the above cold and rainy sentence, we have to understand that we mean “not (cold and rainy)” rather than “(not cold) and rainy.”
The following is a list of important logical equivalences. All of them can be checked using truth-tables.
Summary of Logical Equivalences.
Let \(p, q,\) and \(r\) be variables representing statements. Let \(\mathbf{t}\) be a tautology and \(\mathbf{c}\) be a contradiction.
-
Commutative Laws.\(p \wedge q \equiv q \wedge p; \ \ \ p \vee q \equiv q \vee p\)
-
Associative Laws.\((p \wedge q)\wedge r \equiv p \wedge (q \wedge r);\ \ \ (p \vee q)\vee r \equiv p \vee (q \vee r)\)
-
Distributive Laws.\(p \wedge (q \vee r) \equiv (p \wedge q)\vee (p \wedge r);\ \ \ p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)\)
-
Identity Laws.\(p \wedge {\rm\textbf{t}} \equiv p;\ \ \ p \vee {\rm\textbf{c}} \equiv p\)
-
Negation Laws.\(p\ \vee \sim p \equiv {\rm\textbf{t}};\ \ \ p\ \wedge \sim p \equiv \rm{\textbf{c}}\)
-
Double Negation Law.\(\sim(\sim p)\equiv p\)
-
Idempotent Laws.\(p \wedge p \equiv p;\ \ \ p \vee p \equiv p\)
-
Universal Bound Laws.\(p \vee {\rm\textbf{t}} \equiv {\rm\textbf{t}};\ \ \ p \wedge \rm{\textbf{c}} \equiv {\rm\textbf{c}}\)
-
DeMorgan’s Laws.\(\sim(p \wedge q) \equiv \sim p \vee \sim q;\ \ \ \sim(p \vee q) \equiv \sim p\ \wedge \sim q\)
-
Absorption Laws.\(p \vee (p \wedge q) \equiv p;\ \ \ p \wedge (p \vee q) \equiv p\)
Reading Questions Check Your Understanding
1.
Fill in the truth-table for \(\sim(\sim p \vee q)\text{.}\)
| \(p\) | \(q\) | \(\sim(\sim p\vee q)\) |
| T | T | |
| T | F | |
| F | T | |
| F | F |
2.
Fill in the truth-table for \((p\ \vee \sim q)\text{.}\)
| \(p\) | \(q\) | \((p\ \vee \sim q)\) |
| T | T | |
| T | F | |
| F | T | |
| F | F |
3.
Fill in the truth-table for \((p\ \wedge \sim q)\text{.}\)
| \(p\) | \(q\) | \((p\ \wedge \sim q)\) |
| T | T | |
| T | F | |
| F | T | |
| F | F |
4.
- \(\sim(\sim p\vee q)\) is logically equivalent to \((p\ \vee \sim q)\)
- \(\sim(\sim p\vee q)\) is logically equivalent to \((p\ \wedge \sim q)\)
- \((p\ \vee \sim q)\) is logically equivalent to \((p\ \wedge \sim q)\)
- None of the statements are logically equivalent.
Which of the three statements in the above exercises are logically equivalent?
Exercises Exercises
1.
Write the following statements in symbolic form using the logical connectives \(\sim, \vee, \wedge\) and the indicated letters to represent component statements. Let \(h=\) “Jane is healthy,” \(w=\) “Jane is wealthy,” and \(s=\) “Jane is wise.”
- Jane is healthy and wealthy but not wise.
- Jane is not wealthy but she is healthy and wise.
- Jane is neither healthy, wealthy, nor wise.
- Jane is neither wealthy nor wise, but she is healthy.
- Jane is wealthy, but she is not both healthy and wise.
2.
Give the truth-table for \(\sim(p\ \wedge q)\vee (p \vee q)\text{.}\)
3.
Use truth-tables to determine whether the two statements in each part are logically equivalent. Clearly state your conclusion about whether they are logically equivalent or not, and how your truth-table justifies your conclusion.
- \(p\ \vee (p\ \wedge q)\) and \(p\)
- \(\sim(p\ \wedge q)\) and \(\sim p\ \wedge \sim q\)
- \(p\ \wedge {\rm\bf{c}}\) and \(p\ \vee {\rm\bf{c}}\)
- \((p\ \wedge q) \vee r\) and \(p\ \wedge (q\ \vee r)\)
4.
Use DeMorgan’s Laws to write the negation of the statement: Zoro is a math major and Zoro’s sister is a computer science major.
5.
Use DeMorgan’s Laws to write the negation of the statement: The units digit of \(4^{185}\) is 4 or it is 6.
6.
Assume \(x\) is a real number. Use DeMorgan’s Laws to write the negation of the statement: \(-8\leq x <3\text{.}\)
7.
Use truth-tables to establish whether the following statements are tautologies, contradictions, or neither.
- \(\displaystyle \sim(p\ \wedge q)\)
- \(\displaystyle (p\ \wedge \sim q) \wedge (\sim p\ \vee q)\)
- \(\displaystyle (\sim p\ \vee q) \vee (p\ \wedge \sim q)\)
You have attempted of activities on this page.
