(George Orwell)
14. A man should look for what is, and not for what he thinks should be.
(Albert Einstein)
2.3 Conditional Statements
There is yet another way to combine two statements. Suppose we have in
mind a specific integer a. Consider the following statement about a.
R : If the integer a is a multiple of 6, then a is divisible by 2.
We immediately spot this as a true statement based on our knowledge of
integers and the meanings of the words “if” and “then.” If integer a is a
multiple of 6, then a is even, so therefore a is divisible by 2. Notice that R
is built up from two simpler statements:
P : The integer a is a multiple of 6.
Q : The integer a is divisible by 2.
R : If P, then Q.
In general, given any two statements P and Q whatsoever, we can form
the new statement “If P , then Q .” This is written symbolically as P ⇒ Q
which we read as “If P , then Q ,” or “ P implies Q .” Like ∧ and ∨, the symbol
⇒ has a very specific meaning. When we assert that the statement P ⇒ Q
is true, we mean that if P is true then Q must also be true. (In other words
we mean that the condition P being true forces Q to be true.) A statement
of form P ⇒ Q is called a conditional statement because it means Q will
be true under the condition that P is true.
42
Logic
You can think of P ⇒ Q as being a promise that whenever P is true, Q
will be true also. There is only one way this promise can be broken (i.e.
be false) and that is if P is true but Q is false. Thus the truth table for
the promise P ⇒ Q is as follows:
P
Q
P ⇒ Q
T
T
T
T
F
F
F
T
T
F
F
T
Perhaps you are bothered by the fact that P ⇒ Q is true in the last two
lines of this table. Here’s an example to convince you that the table is
correct. Suppose your professor makes the following promise:
If you pass the final exam, then you will pass the course.
Your professor is making the promise
(You pass the exam) ⇒ (You pass the course).
Under what circumstances did she lie? There are four possible scenarios,
depending on whether or not you passed the exam and whether or not you
passed the course. These scenarios are tallied in the following table.
You pass exam
You pass course
(You pass exam) ⇒ (You pass course)
T
T
T
T
F
F
F
T
T
F
F
T
The first line describes the scenario where you pass the exam and you
pass the course. Clearly the professor kept her promise, so we put a T in
the third column to indicate that she told the truth. In the second line,
you passed the exam, but your professor gave you a failing grade in the
course. In this case she broke her promise, and the F in the third column
indicates that what she said was untrue.
Now consider the third row. In this scenario you failed the exam but
still passed the course. How could that happen? Maybe your professor felt
sorry for you. But that doesn’t make her a liar. Her only promise was that
if you passed the exam then you would pass the course. She did not say
Conditional Statements
43
passing the exam was the only way to pass the course. Since she didn’t
lie, then she told the truth, so there is a T in the third column.
Finally look at the fourth row. In that scenario you failed the exam
and you failed the course. Your professor did not lie; she did exactly what
she said she would do. Hence the T in the third column.
In mathematics, whenever we encounter the construction “If P , then
Q ” it means exactly what the truth table for ⇒ expresses. But of course
there are other grammatical constructions that also mean P ⇒ Q. Here is
a summary of the main ones.
If P, then Q.
Q
if P.
Q
whenever P.
Q
, provided that P.
Whenever P, then also Q.
P ⇒ Q
P is a sufficient condition for Q.
For Q, it is sufficient that P.
Q is a necessary condition for P.
For P, it is necessary that Q.
P
only if Q.
These can all be used in the place of (and mean exactly the same thing as)
“If P , then Q .” You should analyze the meaning of each one and convince
yourself that it captures the meaning of P ⇒ Q. For example, P ⇒ Q means
the condition of P being true is enough (i.e., sufficient) to make Q true;
hence “P is a sufficient condition for Q . ”
The wording can be tricky. Often an everyday situation involving a
conditional statement can help clarify it. For example, consider your
professor’s promise:
(You pass the exam) ⇒ (You pass the course)
This means that your passing the exam is a sufficient (though perhaps
not necessary) condition for your passing the course. Thus your professor
might just as well have phrased her promise in one of the following ways.
Passing the exam is a sufficient condition for passing the course.
For you to pass the course, it is sufficient that you pass the exam.
However, when we want to say “If P , then Q ” in everyday conversation,
we do not normally express this as “ Q is a necessary condition for P ” or
“ P only if Q .” But such constructions are not uncommon in mathematics.
To understand why they make sense, notice that P ⇒ Q being true means
44
Logic
that it’s impossible that P is true but Q is false, so in order for P to be
true it is necessary that Q is true; hence “Q is a necessary condition for
P . ” And this means that P can only be true if Q is true, i.e., “P only if Q . ”
Exercises for Section 2.3
Without changing their meanings, convert each of the following sentences into a
sentence having the form “If P , then Q . ”
1. A matrix is invertible provided that its determinant is not zero.
2. For a function to be continuous, it is sufficient that it is differentiable.
3. For a function to be integrable, it is necessary that it is continuous.
4. A function is rational if it is a polynomial.
6. Whenever a surface has only one side, it is non-orientable.
7. A series converges whenever it converges absolutely.
8. A geometric series with ratio r converges if |r| < 1.
9. A function is integrable provided the function is continuous.
10. The discriminant is negative only if the quadratic equation has no real solutions.
11. You fail only if you stop writing. (Ray Bradbury)
12. People will generally accept facts as truth only if the facts agree with what
they already believe. (Andy Rooney)
13. Whenever people agree with me I feel I must be wrong. (Oscar Wilde)
2.4 Biconditional Statements
It is important to understand that P ⇒ Q is not the same as Q ⇒ P. To see
why, suppose that a is some integer and consider the statements
(a is a multiple of 6)
⇒ (a is divisible by 2),
(a is divisible by 2)
⇒ (a is a multiple of 6).
The first statement asserts that if a is a multiple of 6 then a is divisible
by 2. This is clearly true, for any multiple of 6 is even and therefore
divisible by 2. The second statement asserts that if a is divisible by 2 then
it is a multiple of 6. This is not necessarily true, for a = 4 (for instance) is
divisible by 2, yet not a multiple of 6. Therefore the meanings of P ⇒ Q and
Q ⇒ P are in general quite different. The conditional statement Q ⇒ P is
called the converse of P ⇒ Q, so a conditional statement and its converse
express entirely different things.
Biconditional Statements
45
But sometimes, if P and Q are just the right statements, it can happen
that P ⇒ Q and Q ⇒ P are both necessarily true. For example, consider
the statements
(a is even)
⇒ (a is divisible by 2),
(a is divisible by 2)
⇒ (a is even).
No matter what value a has, both of these statements are true. Since both
P ⇒ Q and Q ⇒ P are true, it follows that (P ⇒ Q) ∧ (Q ⇒ P) is true.
We now introduce a new symbol ⇔ to express the meaning of the
statement (P ⇒ Q) ∧ (Q ⇒ P). The expression P ⇔ Q is understood to have
exactly the same meaning as (P ⇒ Q) ∧ (Q ⇒ P). According to the previous
section, Q ⇒ P is read as “P if Q,” and P ⇒ Q can be read as “P only if Q.”
Therefore we pronounce P ⇔ Q as “ P if and only if Q .” For example, given
an integer a, we have the true statement
(a is even) ⇔ (a is divisible by 2),
which we can read as “Integer a is even if and only if a is divisible by 2 .”
The truth table for ⇔ is shown below. Notice that in the first and last
rows, both P ⇒ Q and Q ⇒ P are true (according to the truth table for ⇒),
so (P ⇒ Q) ∧ (Q ⇒ P) is true, and hence P ⇔ Q is true. However, in the
middle two rows one of P ⇒ Q or Q ⇒ P is false, so (P ⇒ Q)∧(Q ⇒ P) is false,
making P ⇔ Q false.
P
Q
P ⇔ Q
T
T
T
T
F
F
F
T
F
F
F
T
Compare the statement R : (a is even) ⇔ (a is divisible by 2) with this
truth table. If a is even then the two statements on either side of ⇔
are true, so according to the table R is true. If a is odd then the two
statements on either side of ⇔ are false, and again according to the table
R is true. Thus R is true no matter what value a has. In general, P ⇔ Q
being true means P and Q are both true or both false.
Not surprisingly, there are many ways of saying P ⇔ Q in English. The
following constructions all mean P ⇔ Q:
46
Logic
P
if and only if Q.
P
is a necessary and sufficient condition for Q. P ⇔ Q
For P it is necessary and sufficient that Q.
If P, then Q, and conversely.
The first three of these just combine constructions from the previous
section to express that P ⇒ Q and Q ⇒ P. In the last one, the words “...and
conversely” mean that in addition to “If P , then Q ” being true, the converse
statement “If Q , then P ” is also true.
Exercises for Section 2.4
Without changing their meanings, convert each of the following sentences into a
sentence having the form “P if and only if Q . ”
1. For matrix A to be invertible, it is necessary and sufficient that det(A) 6= 0.
2. If a function has a constant derivative then it is linear, and conversely.
3. If xy = 0 then x = 0 or y = 0, and conversely.
4. If a ∈ Q then 5a ∈ Q, and if 5a ∈ Q then a ∈ Q.
5. For an occurrence to become an adventure, it is necessary and sufficient for
one to recount it. (Jean-Paul Sartre)
2.5 Truth Tables for Statements
You should now know the truth tables for ∧, ∨, ∼, ⇒ and ⇔. They should
be internalized as well as memorized. You must understand the symbols
thoroughly, for we now combine them to form more complex statements.
For example, suppose we want to convey that one or the other of P and
Q is true but they are not both true. No single symbol expresses this, but
we could combine them as
(P ∨ Q)∧ ∼ (P ∧ Q),
which literally means:
P or Q is true, and it is not the case that both P and Q are true.
This statement will be true or false depending on the truth values of P
and Q. In fact we can make a truth table for the entire statement. Begin
as usual by listing the possible true/false combinations of P and Q on four
lines. The statement (P ∨ Q)∧ ∼ (P ∧ Q) contains the individual statements
(P ∨ Q) and (P ∧ Q), so we next tally their truth values in the third and
fourth columns. The fifth column lists values for ∼ (P ∧ Q), and these
Truth Tables for Statements
47
are just the opposites of the corresponding entries in the fourth column.
Finally, combining the third and fifth columns with ∧, we get the values
for (P ∨ Q)∧ ∼ (P ∧ Q) in the sixth column.
P
Q
(P ∨ Q)
(P ∧ Q)
∼ (P ∧ Q)
(P ∨ Q)∧ ∼ (P ∧ Q)
T
T
T
T
F
F
T
F
T
F
T
T
F
T
T
F
T
T
F
F
F
F
T
F
This truth table tells us that (P ∨ Q)∧ ∼ (P ∧ Q) is true precisely when
one but not both of P and Q are true, so it has the meaning we intended.
(Notice that the middle three columns of our truth table are just “helper
columns” and are not necessary parts of the table. In writing truth tables,<
br />
you may choose to omit such columns if you are confident about your work.)
For another example, consider the following familiar statement con-
cerning two real numbers x and y:
The product x y equals zero if and only if x = 0 or y = 0.
This can be modeled as (x y = 0) ⇔ (x = 0 ∨ y = 0). If we introduce letters
P, Q and R for the statements xy = 0, x = 0 and y = 0, it becomes P ⇔ (Q ∨R).
Notice that the parentheses are necessary here, for without them we
wouldn’t know whether to read the statement as P ⇔ (Q ∨ R) or (P ⇔ Q) ∨ R.
Making a truth table for P ⇔ (Q ∨R) entails a line for each T/F combina-
tion for the three statements P, Q and R. The eight possible combinations
are tallied in the first three columns of the following table.
P
Q
R
Q ∨ R
P ⇔ (Q ∨ R)
T
T
T
T
T
T
T
F
T
T
T
F
T
T
T
T
F
F
F
F
F
T
T
T
F
F
T
F
T
F
F
F
T
T
F
F
F
F
F
T
We fill in the fourth column using our knowledge of the truth table
for ∨. Finally the fifth column is filled in by combining the first and fourth
columns with our understanding of the truth table for ⇔. The resulting
table gives the true/false values of P ⇔ (Q ∨ R) for all values of P, Q and R.
48
Logic
Notice that when we plug in various values for x and y, the statements
P : x y = 0, Q : x = 0 and R : y = 0 have various truth values, but the statement
P ⇔ (Q ∨ R) is always true. For example, if x = 2 and y = 3, then P,Q and R
are all false. This scenario is described in the last row of the table, and
there we see that P ⇔ (Q ∨ R) is true. Likewise if x = 0 and y = 7, then P
and Q are true and R is false, a scenario described in the second line of
the table, where again P ⇔ (Q ∨ R) is true. There is a simple reason why
P ⇔ (Q∨R) is true for any values of x and y: It is that P ⇔ (Q∨R) represents
(x y = 0) ⇔ (x = 0 ∨ y = 0), which is a true mathematical statement. It is
absolutely impossible for it to be false.
This may make you wonder about the lines in the table where P ⇔ (Q∨R)
is false. Why are they there? The reason is that P ⇔ (Q ∨ R) can also
represent a false statement. To see how, imagine that at the end of the
Book of Proof Page 7
