400 - Lecture 2 Problems DM
400 - Lecture 2 Problems DM
400 - Lecture 2 Problems DM
2 Conditional Statements 49
1. This loop will repeat exactly N times if it does not contain If it walks like a duck and it talks like a duck, then it is
a stop or a go to. a duck.
2. I am on time for work if I catch the 8:05 bus. Either it does not walk like a duck or it does not talk
3. Freeze or I’ll shoot. like a duck, or it is a duck.
4. Fix my ceiling or I won’t pay my rent. If it does not walk like a duck and it does not talk like
a duck, then it is not a duck.
Construct truth tables for the statement forms in 5–11.
19. True or false? The negation of “If Sue is Luiz’s mother, then
5. ∼p ∨ q → ∼q 6. ( p ∨ q) ∨ (∼p ∧ q) → q
Ali is his cousin” is “If Sue is Luiz’s mother, then Ali is not
7. p ∧ ∼q → r 8. ∼p ∨ q → r his cousin.”
9. p ∧ ∼r ↔ q ∨ r 10. ( p → r ) ↔ (q → r ) 20. Write negations for each of the following statements.
(Assume that all variables represent fixed quantities or enti-
11. ( p → (q → r )) ↔ (( p ∧ q) → r ) ties, as appropriate.)
12. Use the logical equivalence established in Example 2.2.3, a. If P is a square, then P is a rectangle.
p ∨ q → r ≡ ( p → r ) ∧ (q → r ), to rewrite the follow- b. If today is New Year’s Eve, then tomorrow is January.
ing statement. (Assume that x represents a fixed real c. If the decimal expansion of r is terminating, then r is
number.) rational.
d. If n is prime, then n is odd or n is 2.
If x > 2 or x < −2, then x 2 > 4. e. If x is nonnegative, then x is positive or x is 0.
13. Use truth tables to verify the following logical equiv- f. If Tom is Ann’s father, then Jim is her uncle and Sue is
alences. Include a few words of explanation with your her aunt.
answers. g. If n is divisible by 6, then n is divisible by 2 and n is
divisible by 3.
a. p → q ≡ ∼p ∨ q b. ∼( p → q) ≡ p ∧ ∼q.
21. Suppose that p and q are statements so that p → q is false.
H 14. a. Show that the following statement forms are all logically
Find the truth values of each of the following:
equivalent.
a. ∼p → q b. p ∨ q c. q → p
p → q ∨ r, p ∧ ∼q → r, and p ∧ ∼r → q
H 22. Write contrapositives for the statements of exercise 20.
b. Use the logical equivalences established in part (a) to
rewrite the following sentence in two different ways. H 23. Write the converse and inverse for each statement of
(Assume that n represents a fixed integer.) exercise 20.
If n is prime, then n is odd or n is 2. Use truth tables to establish the truth of each statement in 24–27.
24. A conditional statement is not logically equivalent to its
15. Determine whether the following statement forms are logi- converse.
cally equivalent:
25. A conditional statement is not logically equivalent to its
p → (q → r ) and ( p → q) → r inverse.
In 16 and 17, write each of the two statements in symbolic form 26. A conditional statement and its contrapositive are logically
and determine whether they are logically equivalent. Include a equivalent to each other.
truth table and a few words of explanation.
27. The converse and inverse of a conditional statement are log-
16. If you paid full price, you didn’t buy it at Crown Books. ically equivalent to each other.
You didn’t buy it at Crown Books or you paid full price.
H 28. “Do you mean that you think you can find out the answer
17. If 2 is a factor of n and 3 is a factor of n, then 6 is a factor to it?” said the March Hare.
of n. 2 is not a factor of n or 3 is not a factor of n or 6 is a
“Exactly so,” said Alice.
factor of n.
“Then you should say what you mean,” the March Hare
18. Write each of the following three statements in symbolic went on.
form and determine which pairs are logically equivalent. “I do,” Alice hastily replied; “at least—at least I mean
Include truth tables and a few words of explanation. what I say—that’s the same thing, you know.”
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).
Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
50 Chapter 2 The Logic of Compound Statements
“Not the same thing a bit!” said the Hatter. “Why, you 38. Ann will go unless it rains.
might just as well say that ‘I see what I eat’ is the same
39. This door will not open unless a security code is entered.
thing as ‘I eat what I see’!”
—from “A Mad Tea-Party” in Alice in Wonderland, Rewrite the statements in 40 and 41 in if-then form.
by Lewis Carroll
The Hatter is right. “I say what I mean” is not the same 40. Catching the 8:05 bus is a sufficient condition for my being
thing as “I mean what I say.” Rewrite each of these two on time for work.
sentences in if-then form and explain the logical relation 41. Having two 45◦ angles is a sufficient condition for this tri-
between them. (This exercise is referred to in the introduc- angle to be a right triangle.
tion to Chapter 4.)
Use the contrapositive to rewrite the statements in 42 and 43 in
If statement forms P and Q are logically equivalent, then
if-then form in two ways.
P ↔ Q is a tautology. Conversely, if P ↔ Q is a tautology,
then P and Q are logically equivalent. Use ↔ to convert each 42. Being divisible by 3 is a necessary condition for this num-
of the logical equivalences in 29–31 to a tautology. Then use a ber to be divisible by 9.
truth table to verify each tautology.
43. Doing homework regularly is a necessary condition for Jim
29. p → (q ∨ r ) ≡ ( p ∧ ∼q) → r to pass the course.
30. p ∧ (q ∨ r ) ≡ ( p ∧ q) ∨ ( p ∧ r ) Note that “a sufficient condition for s is r ” means r is a suffi-
31. p → (q → r ) ≡ ( p ∧ q) → r cient condition for s and that “a necessary condition for s is r ”
means r is a necessary condition for s. Rewrite the statements
Rewrite each of the statements in 32 and 33 as a conjunction of in 44 and 45 in if-then form.
two if-then statements.
44. A sufficient condition for Jon’s team to win the champi-
32. This quadratic equation has two distinct real roots if, and onship is that it win the rest of its games.
only if, its discriminant is greater than zero.
45. A necessary condition for this computer program to be cor-
33. This integer is even if, and only if, it equals twice some rect is that it not produce error messages during translation.
integer.
46. “If compound X is boiling, then its temperature must be at
Rewrite the statements in 34 and 35 in if-then form in two ways, least 150◦ C.” Assuming that this statement is true, which of
one of which is the contrapositive of the other. the following must also be true?
34. The Cubs will win the pennant only if they win tomorrow’s a. If the temperature of compound X is at least 150◦ C, then
game. compound X is boiling.
b. If the temperature of compound X is less than 150◦ C,
35. Sam will be allowed on Signe’s racing boat only if he is an then compound X is not boiling.
expert sailor. c. Compound X will boil only if its temperature is at least
150◦ C.
36. Taking the long view on your education, you go to the Pres- d. If compound X is not boiling, then its temperature is less
tige Corporation and ask what you should do in college to than 150◦ C.
be hired when you graduate. The personnel director replies e. A necessary condition for compound X to boil is that its
that you will be hired only if you major in mathematics temperature be at least 150◦ C.
or computer science, get a B average or better, and take f. A sufficient condition for compound X to boil is that its
accounting. You do, in fact, become a math major, get a B+ temperature be at least 150◦ C.
average, and take accounting. You return to Prestige Cor-
poration, make a formal application, and are turned down. In 47–50 (a) use the logical equivalences p → q ≡∼p ∨ q and
Did the personnel director lie to you? p ↔ q ≡ (∼p ∨ q) ∧ (∼q ∨ p) to rewrite the given statement
forms without using the symbol → or ↔, and (b) use the logi-
Some programming languages use statements of the form cal equivalence p ∨ q ≡∼(∼p∧ ∼q) to rewrite each statement
“r unless s n ” to mean that as long as s does not happen, then form using only ∧ and ∼.
r will happen. More formally:
47. p ∧ ∼q → r 48. p ∨ ∼q → r ∨ q
Definition: If r and s are statements,
r unless s means if ∼s then r. 49. ( p → r ) ↔ (q → r )
50. ( p → (q → r )) ↔ (( p ∧ q) → r )
In 37–39, rewrite the statements in if-then form.
51. Given any statement form, is it possible to find a logi-
37. Payment will be made on the fifth unless a new hearing is cally equivalent form that uses only ∼ and ∧? Justify your
granted. answer.
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).
Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.