Tan S.T. Finite Mathematics for the Managerial, Life, and Social Sciences
Подождите немного. Документ загружается.
542 A INVERSE FUNCTIONS
30. Let p and q denote the propositions
p: The investment newsletter recommended buying bond
mutual funds.
q: The investment newsletter recommended buying stock
mutual funds.
a. State the exclusive disjunction for these propositions in
words.
b. State the inclusive disjunction for these propositions in
words.
31. Let p and q denote the propositions
p: The SAT verbal scores improved in this school district
last year.
q: The SAT math scores improved in this school district
last year.
Express each of the following statements symbolically.
a. The SAT verbal scores and the SAT math scores
improved in this school district last year.
b. Either the SAT verbal scores or the SAT math scores
improved in this school district last year.
c. Neither the SAT verbal scores nor the SAT math scores
improved in this school district last year.
d. It is not true that the SAT math scores did not improve
in this school district last year.
32. Let p and q denote the propositions
p: Laura purchased a VHS videocassette recorder.
q: Laura did not purchase a DVD player.
Express each of the following statements symbolically.
a. Laura purchased either a VHS recorder or a DVD
player, or both a VHS recorder and a DVD player.
b. Laura purchased a VHS recorder and a DVD player.
c. It is not true that Laura purchased a DVD player.
d. Laura purchased neither a VHS recorder nor a DVD
player.
33. Let p, q, and r denote the propositions
p: The popularity of prime-time soaps increased this year.
q: The popularity of prime-time situation comedies in-
creased this year.
r: The popularity of prime-time detective shows decreased
this year.
Express each of the following propositions in words.
a. p q b. p r
c. (r) q d.
p q
A.2 Truth Tables
A primary objective of studying logic is to determine whether a given proposition
is true or false. In other words, we wish to determine the truth value of a given
statement.
Consider, for example, the conjunction p q formed from the prime propositions
p and q. There are four possible cases:
1. p is true and q is true.
2. p is true and q is false.
3. p is false and q is true.
4. p is false and q is false.
By definition the conjunction is true when both p and q are true, and it is false other-
wise. We can summarize this information in the form of a truth table, as shown in
Table 2.
In a similar manner we can construct the truth tables for inclusive disjunction,
exclusive disjunction, and negation (Tables 3a–c).
pqp q
TTF
TFT
FTT
FFF
p p
TF
FT
TABLE 3
pqp q
TT T
TF T
FT T
FF F
TABLE 2
Conjunction
pqp q
TT T
TF F
FT F
FF F
(a) Inclusive disjunction (b) Exclusive disjunction (c) Negation
87533_10_APP_p537-578 1/30/08 10:27 AM Page 542
In general, when we are given a compound proposition, we are concerned with the
problem of finding every possible combination of truth values associated with the
compound proposition. To systematize this procedure, we construct a truth table
exhibiting all possible truth values for the given proposition. The next several exam-
ples illustrate this method.
EXAMPLE 1
Construct the truth table for the proposition p q.
Solution
The truth table is constructed in the following manner.
1. The two prime propositions p and q are placed at the head of the first two
columns (Table 4).
2. The two propositions containing the connectives, p and p q, are placed at
the head of the next two columns.
3. The possible truth values for p are entered in the column headed by p, and then
the possible truth values for q are entered in the column headed by q. Notice that
the possible T values are always exhausted first.
4. The possible truth values for the negation p are entered in the column headed
by p, and then the possible truth values for the disjunction p q are entered
in the column headed by p q.
EXAMPLE 2
Construct the truth table for the proposition p ( p q).
Solution
Proceeding as in the previous example, we construct the truth table as
shown in Table 5. Since the given proposition is the disjunction of the propositions
p and ( p q), columns are introduced for p, p q, and p ( p q).
The following is an example involving three prime propositions.
EXAMPLE 3
Construct the truth table for the proposition (p q) (r p).
Solution
Following the method of the previous example, we construct the truth
table as shown in Table 6.
A.2 TRUTH TABLES 543
TABLE 4
pqp p q
TT F T
TF F F
FT T T
FF T T
TABLE 5
pqpp q p ( p q)
TT F T T
TF F F F
FT T F T
FF T F T
TABLE 6
pqrp q pr p ( p q) (r p)
TTT T F F T
TTF T F F T
TFT T F F T
TFF T F F T
FTT T T T T
FTF T T F T
FFT F T T T
FFF F T F F
87533_10_APP_p537-578 1/30/08 10:27 AM Page 543
544 A INVERSE FUNCTIONS
Observe that the truth table in Example 3 contains eight rows, whereas the truth
tables in Examples 1 and 2 contain four rows. In general, if a compound proposition
P( p, q, . . .) contains the n prime propositions p, q, . . . , then the corresponding truth
table contains 2
n
rows. For example, since the compound proposition in Example 3
contains three prime propositions, its corresponding truth table contains 2
3
, or 8, rows.
A.2 Exercises
In Exercises 1–18, construct a truth table for each com-
pound proposition.
1. p q 2. p q
3. (p) 4. ( p q)
5. p p 6. (p q)
7. p ( p q) 8. ( p q) q
9. ( p q) ( p q) 10. ( p q) p
11. ( p q) ( p q) 12. ( p q) (p q)
13. ( p q
) ( p r) 14. p (q r)
15. ( p q) r 16. (p q) r
17. ( p q) ( p r) 18. ( p q) (q r)
19. If a compound proposition consists of the prime proposi-
tions p, q, r, and s, how many rows does its corresponding
truth table contain?
A.3 The Conditional and the Biconditional Connectives
In this section, we introduce two other connectives: the conditional and the bicondi-
tional. We also discuss three variations of conditional statements: the inverse, the con-
trapositive, and the converse.
We often use expressions of the form
If it rains, then the baseball game will be postponed
to specify the conditions under which a statement will be true. The “if . . . then” state-
ment is the building block on which deductive reasoning is based, and it is important
to understand its use in forming logical proofs.
The truth table determined by the conditional p 씮 q is shown in Table 7.
One question that is often asked is: Why is a conditional statement true when its
hypothesis is false? We can answer this question by considering the following condi-
tional statement made by a mother to her son:
If you do your homework, then you may watch TV.
Conditional Statement
A conditional statement is a proposition of the form “if p, then q” and is rep-
resented symbolically by
p 씮 q
The connective “if . . . then” is called the conditional connective; the proposi-
tion p is called the
hypothesis; and the proposition q is called the conclusion. A
conditional statement is false if the hypothesis is true and the conclusion is false;
it is true in all other cases.
TABLE 7
pqp 씮 q
TT T
TF F
FT T
FF T
87533_10_APP_p537-578 1/30/08 10:27 AM Page 544
Think of the statement consisting of the two prime propositions
p: You do your homework
q: You may watch TV
as a promise made by the mother to her son. Four cases arise:
1. The son does his homework, and his mother lets him watch TV.
2. The son does his homework, and his mother does not let him watch TV.
3. The son does not do his homework, and his mother lets him watch TV.
4. The son does not do his homework, and his mother does not let him watch TV.
In case 1, p and q are both true, the promise has been kept and, consequently, p 씮 q is
true. In case 2, p is true and q is false, and the mother has broken her promise. There-
fore, p 씮 q is false. In cases 3 and 4, p is not true, and the promise is not broken. Thus,
p 씮 q is regarded as a true statement. In other words, the conditional statement is
regarded as false only if the “promise” is broken.
There are several equivalent expressions for the conditional connective “if p
then q.” Among them are
1. p implies q
2. p only if q
3. q if p
4. q whenever p
5. Suppose p, then q
Care should be taken not to confuse the conditional “q if p” with the conditional
q 씮 p, because the two statements have quite different meanings. For example, the
conditional p 씮 q formed from the two propositions
p: There is a fire
q: You call the fire department
is
If there is a fire, then you call the fire department.
The conditional q 씮 p is
If you call the fire department, then there is a fire.
Obviously, the two statements have quite different meanings.
We refer to statements that are variations of the conditional p 씮 q as logical vari-
ants. We define three logical variants of the conditional p 씮 q as follows:
1. The converse is the compound statement “if q, then p” and is represented symbol-
ically by
q 씮 p
2. The contrapositive is the compound statement “if not q, then not p” and is repre-
sented symbolically by
q 씮 p
3. The inverse is the compound statement “if not p, then not q” and is represented
symbolically by
p 씮 q
EXAMPLE 1
Given the two propositions
p: You vote in the presidential election.
q: You are a registered voter.
A.3 THE CONDITIONAL AND THE BICONDITIONAL CONNECTIVES 545
87533_10_APP_p537-578 1/30/08 10:27 AM Page 545
a. State the conditional p 씮 q.
b. State the converse, the contrapositive, and the inverse of p 씮 q.
Solution
a. The conditional is “If you vote in the presidential election, then you are a regis-
tered voter.”
b. The converse is “If you are a registered voter, then you vote in the presidential
election.” The contrapositive is “If you are not a registered voter, then you do not
vote in the presidential election.” The inverse is “If you do not vote in the presi-
dential election, then you are not a registered voter.”
The truth table for the conditional p 씮 q and its three logical variants is shown in
Table 8. Notice that the conditional p 씮 q and its contrapositive ⬃q 씮 ⬃p have iden-
tical truth tables. In other words, the conditional statement and its contrapositive have
the same meaning.
Referring once again to the truth table in Table 8, we see that p 씮 q is logically
equivalent to its contrapositive. Similarly, the converse of a conditional statement is
logically equivalent to the inverse.
It is sometimes easier to prove the contrapositive of a conditional statement than
it is to prove the conditional itself. We may use this to our advantage in establishing
a proof, as shown in the next example.
EXAMPLE 2
Prove that if n
2
is an odd number, then n is an odd number.
Solution
Let p and q be the propositions
p: n
2
is odd.
q: n is an odd number.
Since p 씮 q is logically equivalent to ⬃q 씮 ⬃p, it suffices to prove ⬃q 씮 ⬃p.
Thus, we wish to prove that if n is not an odd number, then n
2
is an even number and
consequently not odd. If n is even, then n ⫽ 2k, where k is an integer. Therefore,
n
2
⫽ (2k)(2k) ⫽ 2(2k
2
)
Since 2(2k
2
) is a multiple of 2, it is an even number. Thus, we have shown that the
contrapositive ⬃q 씮 ⬃p is true, and it follows that the conditional p 씮 q is also
true.
Logical Equivalence
Two propositions P and Q are logically equivalent, denoted by
P ⇔ Q
if they have identical truth tables.
546 A INTRODUCTION TO LOGIC
TABLE 8
Conditional Converse Contrapositive Inverse
pq p 씮 qq 씮 p ⬃p ⬃q ⬃q 씮 ⬃p ⬃p 씮 ⬃q
TT T T F F T T
TF F T F T F T
FT T F T F T F
FF T T T T T T
87533_10_APP_p537-578 2/18/08 10:50 AM Page 546
We now turn our attention to the last of the five basic connectives.
The truth table for p 씯씮 q is shown in Table 9.
EXAMPLE 3
Let p and q be the propositions
p: Mark is going to the senior prom.
q: Linda is going to the senior prom.
State the biconditional p 씯씮 q.
Solution
The required statement is
Mark is going to the senior prom
if and only if
Linda is going to the senior prom.
As suggested by its name, the biconditional statement is actually composed of two
conditional statements. For instance, an equivalent expression for the biconditional
statement in Example 3 is given by the conjunction of the two conditional statements
Mark is going to the senior prom
if Linda is going to the senior prom.
Linda is going to the senior prom
if Mark is going to the senior prom.
Thus, “p if q, and q if p” is equivalent to “p if and only if q.”
The equivalent expressions that are most commonly used in forming conditional
and biconditional statements are summarized in Table 10. The words necessary and
sufficient occur frequently in mathematical proofs. When we say that p is sufficient
for q we mean that when p is true, q is also true—that is, p 씮 q. In like manner, when
we say that p is necessary for q, we mean that if p is not true, then q is not true—that
is, p 씮 q. But this last expression is logically equivalent to q 씮 p. Thus, when we
say that p is necessary and sufficient for q, we mean p 씮 q and q 씮 p. Example 4
illustrates the use of these expressions.
Biconditional Propositions
Statements of the form “p if and only if q” are called biconditional propositions
and are represented symbolically by
p 씯씮 q
The connective “if and only if ” is called the biconditional connective. The
biconditional p 씯씮 q is true whenever p and q are both true or both false.
A.3 THE CONDITIONAL AND THE BICONDITIONAL CONNECTIVES 547
TABLE 9
pqp 씯씮 q
TT T
TF F
FT F
FF T
TABLE 10
Equivalent Form
Conditional Statement If p, then qpis sufficient for q
p only if q
q is necessary for p
q, if p
Biconditional Statement p if and only if q If p then q; if q then p
p is necessary and sufficient for q
87533_10_APP_p537-578 1/30/08 10:27 AM Page 547
548 A INVERSE FUNCTIONS
EXAMPLE 4
Let p and q be the propositions
p: The stock market goes up.
q: Interest rates decrease.
Represent the following statements symbolically:
a. If interest rates decrease, then the stock market goes up.
b. If interest rates do not decrease, then the stock market does not go up.
c. The stock market will go up if and only if interest rates decrease.
d. Decreasing interest rates is a sufficient condition for the stock market to go up.
e. Decreasing interest rates is a necessary and sufficient condition for a rising stock
market.
Solution
a. q 씮 p b. q 씮 p, or p 씮 q c. p 씯씮 q
d. q 씮 p e. q 씯씮 p
Just as there is an order of precedence when we use the arithmetical operations ,
, , and , we must also observe an order of precedence when we use the logical
connectives. The following list dictates the order of precedence for logical connec-
tives.
Thus, the connective should be applied first, followed by , and so on. For exam-
ple, using the order of precedence, we see that p r s is ( p r) s.
Also, as in the case of arithmetical operations, parentheses can be used to over-
ride the order of precedence.
Order of Precedence of Logical Connectives
, , , 씮, 씯씮
A.3 Exercises
In Exercises 1–4, write the converse, the contrapositive,
and the inverse of the conditional statement.
1. p 씮 q 2. p 씮 q
3. q 씮 p 4. p 씮 q
In Exercises 5 and 6, refer to the following propositions
p and q:
p: It is snowing
q: The temperature is below freezing.
5. Express the conditional and the biconditional of p and q in
words.
6. Express the converse, contrapositive, and inverse of the
conditional p 씮 q in words.
In Exercises 7 and 8, refer to the following propositions
p and q:
p: The company’s union and management reach a set-
tlement.
q: The workers do not strike.
7. Express the conditional and biconditional of p and q in
words.
8. Express the converse, contrapositive, and inverse of the
conditional p 씮 q in words.
In Exercises 9–12, determine whether the statement is
true or false.
9. A conditional proposition and its converse are logically
equivalent.
87533_10_APP_p537-578 1/30/08 10:27 AM Page 548
10. The converse and the inverse of a conditional proposition
are logically equivalent.
11. A conditional proposition and its inverse are logically
equivalent.
12. The converse and the contrapositive of a conditional
proposition are logically equivalent.
13. Consider the conditional statement “If the owner lowers
the selling price of the house, then I will buy it.” Under
what conditions is the conditional statement false?
14. Consider the biconditional statement “I will buy the house
if and only if the owner lowers the selling price.” Under
what conditions is the biconditional statement false?
In Exercises 15–28, construct a truth table for the com-
pound proposition.
15. (p 씮 q) 16. (q 씮 p)
17. (p 씮 q) p 18. (p 씮 q) (q 씮 p)
19. (p 씮 q) p 20. (p 씮 q) (p q)
21. (p 씮 q) 씯씮 (q 씮 p)
22. (p 씮 q) 씯씮 (p q) 23. (p q) 씮 (p q)
24.
q 씮 (p q) 25. (p q) 씮 r
26. (p 씯씮 q) r 27. p 씮 (q r)
28. [(p 씮 q) (q 씮 r)] 씮 (p 씮 r)
In Exercises 29–36, determine whether the compound
propositions are logically equivalent.
29. p q; p 씮 q 30. (p q); p q
31. q 씮 p; p 씮 q 32. p 씮 q; p q
A.4 LAWS OF LOGIC 549
33. p q; p 씮 q 34. (p q); p q
35. (p 씮 q) 씮 r; (p q) r
36. p (q r); (p q) (p r)
37. Let p and q denote the following propositions:
p: Taxes are increased.
q: The federal deficit increases.
Represent the following statements symbolically.
a. If taxes are increased, then the federal deficit will not
increase.
b. If taxes are not increased, then the federal deficit will
increase.
c. The federal deficit will not increase if and only if taxes
are increased.
d. Increased taxation is a sufficient condition for halting
the growth of the federal deficit.
e. Increased taxation is a necessary and sufficient condi-
tion for halting the growth of the federal deficit.
38. Let p and q denote the following propositions:
p: The unemployment rate decreases.
q: Consumer confidence improves.
Represent the following statements symbolically.
a. If the unemployment rate does not decrease, consumer
confidence will not improve.
b. Consumer confidence will improve if and only if the
unemployment rate does not decrease.
c. A decreasing unemployment rate is a sufficient condi-
tion for consumer confidence to improve.
d.
A decreasing unemployment rate is a necessary and suf-
ficient condition for consumer confidence to improve.
A.4 Laws of Logic
Just as the laws of algebra help us perform operations with real numbers, the laws of
logic provide us with a systematic method of simplifying statements.
Laws of Logic
Let p, q, and r be any three propositions. Then
1. p p ⇔ p Idempotent law for conjunction
2. p p ⇔ p Idempotent law for disjunction
3. (p q) r ⇔ p (q r) Associative law for conjunction
4. (p q) r ⇔ p (q r) Associative law for disjunction
5. p q ⇔ q p Commutative law for conjunction
6. p q ⇔ q p Commutative law for disjunction
7. p (q r) ⇔ ( p q) (p r) Distributive law for conjunction
8. p (q r) ⇔ ( p
q) ( p r) Distributive law for disjunction
9. (p q) ⇔ p q De Morgan’s law
10. (p q) ⇔ p q De Morgan’s law
87533_10_APP_p537-578 1/30/08 10:27 AM Page 549
To verify any of these laws, we need only construct a truth table to show that the
given statements are logically equivalent. We illustrate this procedure in the next
example.
EXAMPLE 1
Prove the distributive law for conjunction.
Solution
We wish to prove that p (q r) is logically equivalent to ( p q)
( p r). This is easily done by constructing the associated truth table, as shown
in Table 11. Since the entries in the last two columns are the same, we conclude that
p (q r) ⇔ ( p q) ( p r).
The proofs of the other laws are left to you as an exercise.
De Morgan’s laws, laws 9 and 10, are useful in forming the negation of a state-
ment. For example, if we wish to state the negation of the proposition
Steve plans to major in business administration or economics
we can represent the statement symbolically by p q, where the prime propositions
are
p: Steve plans to major in business administration.
q: Steve plans to major in economics.
Then, the negation of p q is ⬃( p q). Using De Morgan’s laws, we have
⬃( p q) ⇔ ⬃p ⬃q
Thus, the required statement is
Steve does not plan to major in business administration, and
he does not plan to major in economics.
Up to this point we have considered propositions that have both true and false
entries in their truth tables. Some statements have the property that they are always
true; other propositions have the property that they are always false.
EXAMPLE 2
Show that
a. p ⬃p is a tautology. b. p ⬃p is a contradiction.
Tautologies and Contradictions
A tautology is a statement that is always true.
A
contradiction is a statement that is always false.
550 A INTRODUCTION TO LOGIC
TABLE 11
pqrq rp qp rp (q r)(p q) ( p r)
TTTTTT T T
TTF T T F T T
TFT T F T T T
TFFFFF F F
FTT T F F F F
FTF T F F F F
FFT T F F F F
FFFFFF F F
87533_10_APP_p537-578 2/18/08 10:50 AM Page 550
Solution
a. The truth table associated with p p is shown in Table 12a. Since all the
entries in the last column are Ts, the proposition is a tautology.
b. The truth table for p p is shown in Table 12b. Since all the entries in the last
column are Fs, the proposition is a contradiction.
In Section A.3, we defined logically equivalent statements as statements that have
identical truth tables. The definition of equivalence may also be restated in terms of a
tautology.
Consider, for example, the prime propositions p and q. Let’s look more closely at the
truth table for p
씯씮 q (Table 13a).
If the biconditional is always true, then the second and third cases shown in the truth
table are excluded and we are left with the truth table in Table 13b. Notice that the
entries in each row of the p and q columns are identical. In other words, p and q have
identical truth values and hence are logically equivalent.
In addition to the ten laws stated earlier, we have the following six laws involv-
ing tautologies and contradictions.
It now remains only to show how these laws are used to simplify proofs.
Laws of Logic
Let t be a tautology and c a contradiction. Then
11. p p ⇔ t 12. p p ⇔ c 15. p c ⇔ p
13. p t ⇔ t 14. p t ⇔ p 16. p c ⇔ c
Logical Equivalence
Two propositions P and Q are logically equivalent if the biconditional P 씯씮 Q
is a tautology.
A.4 LAWS OF LOGIC 551
(b)
p ppp
TF F
FT F
TABLE 12
p ppp
TF T
FT T
(a)
(b)
pqp씯씮 q
TT T
FF T
TABLE 13
pqp씯씮 q
Case 1 T T T
Case 2 T F F
Case 3 F T F
Case 4 F F T
(a)
87533_10_APP_p537-578 1/30/08 10:27 AM Page 551