Book of Proof
Page 8
semester your professor makes the following promise.
You pass the class if and only if you get an “A” on the final or you get
a “B” on the final.
This promise has the form P ⇔ (Q ∨ R), so its truth values are tabulated in
the above table. Imagine it turned out that you got an “A” on the exam
but failed the course. Then surely your professor lied to you. In fact, P is
false, Q is true and R is false. This scenario is reflected in the sixth line
of the table, and indeed P ⇔ (Q ∨ R) is false (i.e., it is a lie).
The moral of this example is that people can lie, but true mathematical
statements never lie.
We close this section with a word about the use of parentheses. The
symbol ∼ is analogous to the minus sign in algebra.
It negates the
expression it precedes. Thus ∼ P ∨ Q means (∼ P) ∨ Q, not ∼ (P ∨ Q). In
∼ (P ∨ Q), the value of the entire expression P ∨ Q is negated.
Exercises for Section 2.5
Write a truth table for the logical statements in problems 1–9:
1. P ∨ (Q ⇒ R)
4. ∼ (P ∨ Q) ∨ (∼ P)
7. (P∧ ∼ P) ⇒ Q
2. (Q ∨ R) ⇔ (R ∧ Q)
5. (P∧ ∼ P) ∨ Q
8. P ∨ (Q∧ ∼ R)
3. ∼ (P ⇒ Q)
6. (P∧ ∼ P) ∧ Q
9. ∼ (∼ P∨ ∼ Q)
10. Suppose the statement ((P ∧ Q) ∨ R) ⇒ (R ∨ S) is false. Find the truth values of
P, Q, R and S. (This can be done without a truth table.)
11. Suppose P is false and that the statement (R ⇒ S) ⇔ (P ∧ Q) is true. Find the
truth values of R and S. (This can be done without a truth table.)
Logical Equivalence
49
2.6 Logical Equivalence
In contemplating the truth table for P ⇔ Q, you probably noticed that
P ⇔ Q is true exactly when P and Q are both true or both false. In other
words, P ⇔ Q is true precisely when at least one of the statements P ∧ Q
or ∼ P∧ ∼ Q is true. This may tempt us to say that P ⇔ Q means the same
thing as (P ∧ Q) ∨ (∼ P∧ ∼ Q).
To see if this is really so, we can write truth tables for P ⇔ Q and
(P ∧ Q) ∨ (∼ P∧ ∼ Q). In doing this, it is more efficient to put these two
statements into the same table, as follows. (This table has helper columns
for the intermediate expressions ∼ P, ∼ Q, (P ∧ Q) and (∼ P∧ ∼ Q).)
P
Q
∼ P
∼ Q
(P ∧ Q) (∼ P∧ ∼ Q)
(P ∧ Q) ∨ (∼ P∧ ∼ Q)
P ⇔ Q
T
T
F
F
T
F
T
T
T
F
F
T
F
F
F
F
F
T
T
F
F
F
F
F
F
F
T
T
F
T
T
T
The table shows that P ⇔ Q and (P ∧ Q) ∨ (∼ P∧ ∼ Q) have the same truth
value, no matter the values P and Q. It is as if P ⇔ Q and (P ∧Q)∨(∼ P∧ ∼ Q)
are algebraic expressions that are equal no matter what is “plugged into”
variables P and Q. We express this state of affairs by writing
P ⇔ Q = (P ∧ Q) ∨ (∼ P∧ ∼ Q)
and saying that P ⇔ Q and (P ∧ Q) ∨ (∼ P∧ ∼ Q) are logically equivalent.
In general, two statements are logically equivalent if their truth
values match up line-for-line in a truth table.
Logical equivalence is important because it can give us different (and
potentially useful) ways of looking at the same thing. As an example, the
following table shows that P ⇒ Q is logically equivalent to (∼ Q) ⇒ (∼ P).
P
Q
∼ P
∼ Q
(∼ Q) ⇒ (∼ P)
P ⇒ Q
T
T
F
F
T
T
T
F
F
T
F
F
F
T
T
F
T
T
F
F
T
T
T
T
The fact that P ⇒ Q = (∼ Q) ⇒ (∼ P) is useful because so many theorems
have the form P ⇒ Q. As we will see in Chapter 5, proving such a theorem
may be easier if we express it in the logically equivalent form (∼ Q) ⇒ (∼ P).
50
Logic
There are two pairs of logically equivalent statements that come up
again and again throughout this book and beyond. They are prevalent
enough to be dignified by a special name: DeMorgan’s laws.
Fact 2.1
(DeMorgan’s Laws)
1.
∼ (P ∧ Q) = (∼ P) ∨ (∼ Q)
2.
∼ (P ∨ Q) = (∼ P) ∧ (∼ Q)
The first of DeMorgan’s laws is verified by the following table. You are
asked to verify the second in one of the exercises.
P
Q
∼ P
∼ Q
P ∧ Q
∼ (P ∧ Q)
(∼ P) ∨ (∼ Q)
T
T
F
F
T
F
F
T
F
F
T
F
T
T
F
T
T
F
F
T
T
F
F
T
T
F
T
T
DeMorgan’s laws are actually very natural and intuitive. Consider the
statement ∼ (P ∧ Q), which we can interpret as meaning that it is not the
case that both P and Q are true. If it is not the case that both P and Q
are true, then at least one of P or Q is false, in which case (∼ P) ∨ (∼ Q) is
true. Thus ∼ (P ∧ Q) means the same thing as (∼ P) ∨ (∼ Q).
DeMorgan’s laws can be very useful. Suppose we happen to know that
some statement having form ∼ (P ∨ Q) is true. The second of DeMorgan’s
laws tells us that (∼ Q) ∧ (∼ P) is also true, hence ∼ P and ∼ Q are both true
as well. Being able to quickly obtain such additional pieces of information
can be extremely useful.
Here is a summary of some significant logical equivalences. Those that
are not immediately obvious can be verified with a truth table.
P ⇒ Q = (∼ Q) ⇒ (∼ P)
Contrapositive law
(2.1)
∼ (P ∧ Q) = ∼ P∨ ∼ Q o
∼ (P ∨ Q) = ∼ P∧ ∼ Q
DeMorgan’s laws
(2.2)
P ∧ Q = Q ∧ P o
P ∨ Q = Q ∨ P
Commutative laws
(2.3)
P ∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R) o
P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R)
Distributive laws
(2.4
)
P ∧ (Q ∧ R) = (P ∧ Q) ∧ R o
P ∨ (Q ∨ R) = (P ∨ Q) ∨ R
Associative laws
(2.5)
Notice how the distributive law P ∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R) has the
same structure as the distributive law p · (q + r) = p · q + p · r from algebra.
Quantifiers
51
Concerning the associative laws, the fact that P ∧(Q ∧ R) = (P ∧Q)∧ R means
that the position of the parentheses is irrelevant, and we can write this as
P ∧ Q ∧ R without ambiguity. Similarly, we may drop the parentheses in
an expression such as P ∨ (Q ∨ R).
But parentheses are essential when there is a mix of ∧ and ∨, as in
P ∨ (Q ∧ R). Indeed, P ∨ (Q ∧ R) and (P ∨ Q) ∧ R are not logically equivalent.
(See Exercise 13 for Section 2.6, below.)
Exercises for Section 2.6
A. Use truth tables to show that the following statements are logically equivalent.
1. P ∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R)
5. ∼ (P ∨ Q ∨ R) = (∼ P) ∧ (∼ Q) ∧ (∼ R)
2. P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R)
6. ∼ (P ∧ Q ∧ R) = (∼ P) ∨ (∼ Q) ∨ (∼ R)
3. P ⇒ Q = (∼ P) ∨ Q
7. P ⇒ Q = (P∧ ∼ Q) ⇒ (Q∧ ∼ Q)
4. ∼ (P ∨ Q) = (∼ P) ∧ (∼ Q)
8. ∼ P ⇔ Q = (P ⇒∼ Q) ∧ (∼ Q ⇒ P)
B. Decide whether or not the following pairs of statements are logically equivalent.
9. P ∧ Q and ∼ (∼ P∨ ∼ Q)
12. ∼ (P ⇒ Q) and P∧ ∼ Q
10. (P ⇒ Q) ∨ R and ∼ ((P∧ ∼ Q)∧ ∼ R) 13. P ∨ (Q ∧ R) and (P ∨ Q) ∧ R
11. (∼ P) ∧ (P ⇒ Q) and ∼ (Q ⇒ P)
14. P ∧ (Q∨ ∼ Q) and (∼ P) ⇒ (Q∧ ∼ Q)
2.7 Quantifiers
Using symbols ∧, ∨, ∼, ⇒ and ⇔, we can deconstruct many English
sentences into a symbolic form. As we have seen, this symbolic form can
help us understand the logical structure of sentences and how different
sentences may actually have the same meaning (as in logical equivalence).
But these symbols alone are not powerful enough to capture the full
meaning of every statement. To help overcome this defect, we introduce
two new symbols that correspond to common mathematical phrases. The
symbol “∀” stands for the phrase “For all” or “For every.” The symbol “∃”
stands for the phrase “There exists a” or “There is a.” Thus the statement
For every n ∈ Z, 2n is even,
can be expressed in either of the following ways:
∀ n ∈ Z, 2n is even,
∀ n ∈ Z, E(2n).
52
Logic
Likewise, a statement such as
There exists a subset X of N for which |X | = 5.
can be translated as
∃ X , (X ⊆ N) ∧ (|X | = 5)
or
∃ X ⊆ N, |X | = 5
or
∃ X ∈ P(N),|X | = 5.
The symbols ∀ and ∃ are called quantifiers because they refer in some
sense to the quantity (i.e., all or some) of the variable that follows them.
Symbol ∀ is called the universal quantifier and ∃ is called the existen-
tial quantifier. Statements which contain them are called quantified
statements. A statement beginning with ∀ is called a universally quan-
tified statement, and one beginning with ∃ is called an existentially
quantified statement.
Example 2.5
The following English statements are paired with their
translations into symbolic form.
Every integer that is not odd is even.
∀ n ∈ Z, ∼ (n is odd ) ⇒ (n is even),
or
∀ n ∈ Z, ∼ O(n) ⇒ E(n).
There is an integer that is not even.
∃ n ∈ Z, ∼ E(n).
For every real number x, there is a real number y for which y3 = x.
∀ x ∈ R, ∃ y ∈ R, y3 = x.
Given any two rational numbers a and b, it follows that ab is rational.
∀ a, b ∈ Q, ab ∈ Q.
Given a set S (such as, but not limited to, N, Z, Q etc.), a quantified
statement of form ∀ x ∈ S, P(x) is understood to be true if P(x) is true
for every x ∈ S. If there is at least one x ∈ S for which P(x) is false, then
∀ x ∈ S, P(x) is a false statement. Similarly, ∃ x ∈ S, P(x) is true provided that
P(x) is true for at least one element x ∈ S; otherwise it is false. Thus each
statement in Example 2.5 is true. Here are some examples of quantified
statements that are false:
Example 2.6
The following false quantified statements are paired with
their translations.
Every integer is even.
∀ n ∈ Z, E(n).
Quantifiers
53
There is an integer n for which n2 = 2.
∃ n ∈ Z, n2 = 2.
For every real number x, there is a real number y for which y2 = x.
∀ x ∈ R, ∃ y ∈ R, y2 = x.
p
Given any two rational numbers a and b, it follows that
ab is rational.
p
∀ a, b ∈ Q, ab ∈ Q.
Example 2.7
When a statement contains two quantifiers you must be
very alert to their order, for reversing the order can change the meaning.
Consider the following statement from Example 2.5.
∀ x ∈ R, ∃ y ∈ R, y3 = x.
This statement is true, for no matter what number x is there exists a
p
number y = 3 x for which y3 = x. Now reverse the order of the quantifiers
to get the new statement
∃ y ∈ R, ∀ x ∈ R, y3 = x.
This new statement says that there exists a particular number y with
the property that y3 = x for every real number x. Since no number y can
have this property, the statement is false. The two statements above have
entirely different meanings.
Quantified statements are often misused in casual conversation. Maybe
you’ve heard someone say “All students do not pay full tuition.” when they
mean “Not all students pay full tuition.” While the mistake is perhaps
marginally forgivable in casual conversation, it must never be made in a
mathematical context. Do not say “All integers are not even.” because that
means there are no even integers. Instead, say “Not all integers are even.”
Exercises for Section 2.7
Write the following as English sentences. Say whether they are true or false.
1. ∀ x ∈ R, x2 > 0
6. ∃ n ∈ N,∀ X ∈ P(N),|X | < n
2. ∀ x ∈ R,∃ n ∈ N, xn ≥ 0
7. ∀ X ⊆ N,∃ n ∈ Z,|X | = n
3. ∃ a ∈ R,∀ x ∈ R, ax = x
8. ∀ n ∈ Z, ∃ X ⊆ N,|X | = n
4. ∀ X ∈ P(N), X ⊆ R
9. ∀ n ∈ Z,∃ m ∈ Z, m = n + 5
5. ∀ n ∈ N,∃ X ∈ P(N),|X | < n
10. ∃ m ∈ Z,∀ n ∈ Z, m = n + 5
54
Logic
2.8 More on Conditional Statements
It is time to address a very important point about conditional statements
that contain variables. To motivate this, let’s return to the following
example concerning integers x:
(x is a multiple of 6) ⇒ (x is even).
As noted earlier, since every multiple of 6 is even, this is a true statement
no matter what integer x is. We could even underscore this fact by writing
this true statement as
∀ x ∈ Z, (x is a multiple of 6) ⇒ (x is even).
But now switch things around to get the different statement
(x is even) ⇒ (x is a multiple of 6).
This is true for some values of x such as −6, 12, 18, etc., but false for
others (such as 2, 4, etc.). Thus we do not have a statement, but rather an
open sentence. (Recall from Section 2.1 that an open sentence is a sentence
whose truth value depends on the value of a certain variable or variables.)
However, by putting a universal quantifier in front we get
∀ x ∈ Z, (x is even) ⇒ (x is a multiple of 6),
which is definitely false, so this new expression is a statement, not an open
sentence. In general, given any two open sentences P(x) and Q(x) about
integers x, the expression ∀ x ∈ Z, P(x) ⇒ Q(x) is either true or false, so it is
a statement, not an open sentence.
Now we come to the very important point. In mathematics, whenever
P(x) and Q(x) are open sentences concerning elements x in some set S
(depending on context), an expression of form P(x) ⇒ Q(x) is understood
to be the statement ∀ x ∈ S, P(x) ⇒ Q(x). In other words, if a conditional
statement is not explicitly quantified then there is an implied universal
quantifier in front of it. This is done because statements of the form
∀ x ∈ S, P(x) ⇒ Q(x) are so common in mathematics that we would get tired
of putting the ∀ x ∈ S in front of them.
Thus the following sentence is a true statement (as it is true for all x).
If x is a multiple of 6, then x is even.
Translating English to Symbolic Logic
55
Likewise, the next sentence is a false statement (as it is not true for all x).
If x is even, then x is a multiple of 6.
This leads to the following significant interpretation of a conditional
statement, which is more general than (but consistent with) the interpre-
tation from Section 2.3.
Definition 2.1
If P and Q are statements or open sentences, then
“If P , then Q ,”
is a statement. This statement is true if it’s impossible for P to be true
while Q is false. It is false if there is at least one instance in which P is
true but Q is false.
Thus the following are true statements:
If x ∈ R, then x2 + 1 > 0.
If a function f is differentiable on R, then f is continuous on R.
Likewise, the following are false statements:
If p is a prime number, then p is odd.
(2 is prime.)
If f is a rational function, then f has an asymptote. (x2 is rational.)
2.9 Translating English to Symbolic Logic
In writing (and reading) proofs of theorems, we must always be alert to the