Page 29 - Discrete Mathematics and Its Applications

8 1 / The Foundations: Logic and Proofs

“If Juan has a smartphone, then 2 + 3 = 5”
is true from the definition of a conditional statement, because its conclusion is true. (The truth
value of the hypothesis does not matter then.) The conditional statement

“If Juan has a smartphone, then 2 + 3 = 6”
is true if Juan does not have a smartphone, even though 2 + 3 = 6 is false. We would not use
these last two conditional statements in natural language (except perhaps in sarcasm), because
there is no relationship between the hypothesis and the conclusion in either statement. In math-
ematical reasoning, we consider conditional statements of a more general sort than we use in
English. The mathematical concept of a conditional statement is independent of a cause-and-
effect relationship between hypothesis and conclusion. Our definition of a conditional statement
specifies its truth values; it is not based on English usage. Propositional language is an artificial
language; we only parallel English usage to make it easy to use and remember.
The if-then construction used in many programming languages is different from that used
in logic. Most programming languages contain statements such as if p then S, where p is a
proposition and S is a program segment (one or more statements to be executed).When execution
of a program encounters such a statement, S is executed if p is true, but S is not executed if p
is false, as illustrated in Example 8.

EXAMPLE 8 What is the value of the variable x after the statement

if 2 + 2 = 4 then x := x + 1

if x = 0 before this statement is encountered? (The symbol := stands for assignment. The
statement x := x + 1 means the assignment of the value of x + 1to x.)

Solution: Because 2 + 2 = 4 is true, the assignment statement x := x + 1 is executed. Hence,
x has the value 0 + 1 = 1 after this statement is encountered. ▲

CONVERSE, CONTRAPOSITIVE, AND INVERSE We can form some new conditional
statements starting with a conditional statement p → q. In particular, there are three related
conditional statements that occur so often that they have special names. The proposition q → p
is called the converse of p → q. The contrapositive of p → q is the proposition ¬q →¬p.
The proposition ¬p →¬q is called the inverse of p → q. We will see that of these three
conditional statements formed from p → q, only the contrapositive always has the same truth
value as p → q.
We first show that the contrapositive, ¬q →¬p, of a conditional statement p → q always
has the same truth value as p → q. To see this, note that the contrapositive is false only when
¬p is false and ¬q is true, that is, only when p is true and q is false. We now show that neither
the converse, q → p, nor the inverse, ¬p →¬q, has the same truth value as p → q for all
possible truth values of p and q. Note that when p is true and q is false, the original conditional
statement is false, but the converse and the inverse are both true.
Remember that the
contrapositive, but neither When two compound propositions always have the same truth value we call them equiv-
the converse or inverse, of alent, so that a conditional statement and its contrapositive are equivalent. The converse and
a conditional statement is the inverse of a conditional statement are also equivalent, as the reader can verify, but neither is
equivalent to it. equivalent to the original conditional statement. (We will study equivalent propositions in Sec-
tion 1.3.) Take note that one of the most common logical errors is to assume that the converse
or the inverse of a conditional statement is equivalent to this conditional statement.
We illustrate the use of conditional statements in Example 9.