464 Test Bank Questions and Answers
TEST BANK
Questions for Chapter 1
What is the negation of the propositions in 1–3?
1. Abby has more than 300 friends on facebook.
2. A messaging package for a cell phone costs less than $20 per month.
3. 4.5 + 2.5 = 6
In questions 4–8, determine whether the proposition is TRUE or FALSE.
4. 1 + 1 = 3 if and only if 2 + 2 = 3.
5. If it is raining, then it is raining.
6. If 1 < 0, then 3 = 4.
7. If 2 + 1 = 3, then 2 = 3 − 1.
8. If 1 + 1 = 2 or 1 + 1 = 3, then 2 + 2 = 3 and 2 + 2 = 4.
9. Write the truth table for the proposition ¬(r → ¬q) ∨ (p ∧ ¬r).
p q ?
10. (a) Find a proposition with the truth table at the right. T T F
(b) Find a proposition using only p, q, ¬, and the connective ∨ T F F
that has this truth table. F T T
F F F
11. Find a proposition with three variables p, q, and r that is true when p and r are true and q is false, and false
otherwise.
12. Find a proposition with three variables p, q, and r that is true when at most one of the three variables is true,
and false otherwise.
13. Find a proposition with three variables p, q, and r that is never true.
p q ?
14. Find a proposition using only p, q, ¬, and the connective ∨ T T F
with the truth table at the right. T F T
F T T
15. Determine whether p → (q → r) and p → (q ∧ r) are equivalent. F F F
16. Determine whether p → (q → r) is equivalent to (p → q) → r.
17. Determine whether (p → q) ∧ (¬p → q) ≡ q.
, Test Bank Questions and Answers 465
18. Write a proposition equivalent to p ∨ ¬q that uses only p, q, ¬, and the connective ∧.
19. Write a proposition equivalent to ¬p ∧ ¬q using only p, q, ¬, and the connective ∨.
20. Prove that the proposition “if it is not hot, then it is hot” is equivalent to “it is hot”.
21. Write a proposition equivalent to p → q using only p, q, ¬, and the connective ∨.
22. Write a proposition equivalent to p → q using only p, q, ¬, and the connective ∧.
23. Prove that p → q and its converse are not logically equivalent.
24. Prove that ¬p → ¬q and its inverse are not logically equivalent.
25. Determine whether the following two propositions are logically equivalent: p ∨ (q ∧ r), (p ∧ q) ∨ (p ∧ r).
26. Determine whether the following two propositions are logically equivalent: p → (¬q ∧ r), ¬p ∨ ¬(r → q).
27. Prove that (q ∧ (p → ¬q)) → ¬p is a tautology using propositional equivalence and the laws of logic.
28. Determine whether this proposition is a tautology: ((p → q) ∧ ¬p) → ¬q.
29. Determine whether this proposition is a tautology: ((p → ¬q) ∧ q) → ¬p.
In 30–36, write the statement in the form “If . . . , then . . . .”
30. x is even only if y is odd.
31. A implies B.
32. It is hot whenever it is sunny.
33. To get a good grade it is necessary that you study.
34. Studying is sufficient for passing.
35. The team wins if the quarterback can pass.
36. You need to be registered in order to check out library books.
37. Write the contrapositive, converse, and inverse of the following: If you try hard, then you will win.
38. Write the contrapositive, converse, and inverse of the following: You sleep late if it is Saturday.
In 39–41 write the negation of the statement. (Don’t write “It is not true that . . . .”)
39. It is Thursday and it is cold.
40. I will go to the play or read a book, but not both.
41. If it is rainy, then we go to the movies.
42. Explain why the negation of “Al and Bill are absent” is not “Al and Bill are present”.
43. Using c for “it is cold” and d for “it is dry”, write “It is neither cold nor dry” in symbols.
44. Using c for “it is cold” and r for “it is rainy”, write “It is rainy if it is not cold” in symbols.
45. Using c for “it is cold” and w for “it is windy”, write “To be windy it is necessary that it be cold” in symbols.
46. Using c for “it is cold”, r for “it is rainy”, and w for “it is windy”, write “It is rainy only if it is windy and
cold” in symbols.
, 466 Test Bank Questions and Answers
47. Translate the given statement into propositional logic using the propositions provided: On certain highways
in the Washington, DC metro area you are allowed to travel on high occupancy lanes during rush hour only
if there are at least three passengers in the vehicle. Express your answer in terms of r:“You are traveling
during rush hour.” t:“You are riding in a car with at least three passengers.” and h:“You can travel on a high
occupancy lane.”
48. A set of propositions is consistent if there is an assignment of truth values to each of the variables in the
propositions that makes each proposition true. Is the following set of propositions consistent?
The system is in multiuser state if and only if it is operating normally.
If the system is operating normally, the kernel is functioning.
The kernel is not functioning or the system is in interrupt mode.
If the system is not in multiuser state, then it is in interrupt mode.
The system is in interrupt mode.
49. On the island of knights and knaves you encounter two people, A and B. Person A says “B is a knave.”
Person B says “We are both knights.” Determine whether each person is a knight or a knave.
50. On the island of knights and knaves you encounter two people, A and B. Person A says “B is a knave.”
Person B says “At least one of us is a knight.” Determine whether each person is a knight or a knave.
Exercises 51–53 relate to inhabitants of an island on which there are three kinds of people: knights who always
tell the truth, knaves who always lie, and spies who can either tell the truth or lie. You encounter three people,
A, B, and C. You know one of the three people is a knight, one is a knave, and one is a spy. Each of the three
people knows the type of person each of the other two is. For each of these situations, if possible, determine
whether there is a unique solution, list all possible solutions or state that there are no solutions.
51. A says “I am not a knight,” B says “I am not a spy,” and C says “I am not a knave.”
52. A says “I am a spy,” B says “I am a spy” and C says “B is a spy.”
53. A says “I am a knight,” B says “I am a knave,” and C says “I am not a knave.”
Find the output of the combinatorial circuits in 54–55.
54. p
q
r
55. p
q
q
r
Construct a combinatorial circuit using inverters, OR gates, and AND gates, that produces the outputs in
56–57 from input bits p, q and r.
56. (¬p ∧ ¬q) ∨ (p ∧ ¬r)
57. ((p ∨ ¬q) ∧ r) ∧ ((¬p ∧ ¬q) ∨ r)
Determine whether the compound propositions in 58–59 are satisfiable.
58. (¬p ∨ ¬q) ∧ (p → q)
59. (p → q) ∧ (q → ¬p) ∧ (p ∨ q)
In 60–62 suppose that Q(x) is “x + 1 = 2x”, where x is a real number. Find the truth value of the statement.
, Test Bank Questions and Answers 467
60. Q(2).
61. ∀x Q(x).
62. ∃x Q(x).
In 63–70 P (x, y) means “x+2y = xy”, where x and y are integers. Determine the truth value of the statement.
63. P (1, −1).
64. P (0, 0).
65. ∃y P (3, y).
66. ∀x∃y P (x, y).
67. ∃x∀y P (x, y).
68. ∀y∃x P (x, y).
69. ∃y∀x P (x, y).
70. ¬∀x∃y ¬P (x, y).
In 71–72 P (x, y) means “x and y are real numbers such that x + 2y = 5”. Determine whether the statement
is true.
71. ∀x∃y P (x, y).
72. ∃x∀y P (x, y).
In 73–75 P (m, n) means “m ≤ n”, where the universe of discourse for m and n is the set of nonnegative
integers. What is the truth value of the statement?
73. ∀n P (0, n).
74. ∃n∀m P (m, n).
75. ∀m∃n P (m, n).
In questions 76–81 suppose P (x, y) is a predicate and the universe for the variables x and y is {1, 2, 3}. Suppose
P (1, 3), P (2, 1), P (2, 2), P (2, 3), P (3, 1), P (3, 2) are true, and P (x, y) is false otherwise. Determine whether
the following statements are true.
76. ∀x∃yP (x, y).
77. ∃x∀yP (x, y).
78. ¬∃x∃y (P (x, y) ∧ ¬P (y, x)).
79. ∀y∃x (P (x, y) → P (y, x)).
80. ∀x∀y (x )= y → (P (x, y) ∨ P (y, x)).
81. ∀y∃x (x ≤ y ∧ P (x, y)).
In 82–85 suppose the variable x represents students and y represents courses, and:
U (y): y is an upper-level course M (y): y is a math course F (x): x is a freshman
B(x): x is a full-time student T (x, y): student x is taking course y.
Write the statement using these predicates and any needed quantifiers.
82. Eric is taking MTH 281.
TEST BANK
Questions for Chapter 1
What is the negation of the propositions in 1–3?
1. Abby has more than 300 friends on facebook.
2. A messaging package for a cell phone costs less than $20 per month.
3. 4.5 + 2.5 = 6
In questions 4–8, determine whether the proposition is TRUE or FALSE.
4. 1 + 1 = 3 if and only if 2 + 2 = 3.
5. If it is raining, then it is raining.
6. If 1 < 0, then 3 = 4.
7. If 2 + 1 = 3, then 2 = 3 − 1.
8. If 1 + 1 = 2 or 1 + 1 = 3, then 2 + 2 = 3 and 2 + 2 = 4.
9. Write the truth table for the proposition ¬(r → ¬q) ∨ (p ∧ ¬r).
p q ?
10. (a) Find a proposition with the truth table at the right. T T F
(b) Find a proposition using only p, q, ¬, and the connective ∨ T F F
that has this truth table. F T T
F F F
11. Find a proposition with three variables p, q, and r that is true when p and r are true and q is false, and false
otherwise.
12. Find a proposition with three variables p, q, and r that is true when at most one of the three variables is true,
and false otherwise.
13. Find a proposition with three variables p, q, and r that is never true.
p q ?
14. Find a proposition using only p, q, ¬, and the connective ∨ T T F
with the truth table at the right. T F T
F T T
15. Determine whether p → (q → r) and p → (q ∧ r) are equivalent. F F F
16. Determine whether p → (q → r) is equivalent to (p → q) → r.
17. Determine whether (p → q) ∧ (¬p → q) ≡ q.
, Test Bank Questions and Answers 465
18. Write a proposition equivalent to p ∨ ¬q that uses only p, q, ¬, and the connective ∧.
19. Write a proposition equivalent to ¬p ∧ ¬q using only p, q, ¬, and the connective ∨.
20. Prove that the proposition “if it is not hot, then it is hot” is equivalent to “it is hot”.
21. Write a proposition equivalent to p → q using only p, q, ¬, and the connective ∨.
22. Write a proposition equivalent to p → q using only p, q, ¬, and the connective ∧.
23. Prove that p → q and its converse are not logically equivalent.
24. Prove that ¬p → ¬q and its inverse are not logically equivalent.
25. Determine whether the following two propositions are logically equivalent: p ∨ (q ∧ r), (p ∧ q) ∨ (p ∧ r).
26. Determine whether the following two propositions are logically equivalent: p → (¬q ∧ r), ¬p ∨ ¬(r → q).
27. Prove that (q ∧ (p → ¬q)) → ¬p is a tautology using propositional equivalence and the laws of logic.
28. Determine whether this proposition is a tautology: ((p → q) ∧ ¬p) → ¬q.
29. Determine whether this proposition is a tautology: ((p → ¬q) ∧ q) → ¬p.
In 30–36, write the statement in the form “If . . . , then . . . .”
30. x is even only if y is odd.
31. A implies B.
32. It is hot whenever it is sunny.
33. To get a good grade it is necessary that you study.
34. Studying is sufficient for passing.
35. The team wins if the quarterback can pass.
36. You need to be registered in order to check out library books.
37. Write the contrapositive, converse, and inverse of the following: If you try hard, then you will win.
38. Write the contrapositive, converse, and inverse of the following: You sleep late if it is Saturday.
In 39–41 write the negation of the statement. (Don’t write “It is not true that . . . .”)
39. It is Thursday and it is cold.
40. I will go to the play or read a book, but not both.
41. If it is rainy, then we go to the movies.
42. Explain why the negation of “Al and Bill are absent” is not “Al and Bill are present”.
43. Using c for “it is cold” and d for “it is dry”, write “It is neither cold nor dry” in symbols.
44. Using c for “it is cold” and r for “it is rainy”, write “It is rainy if it is not cold” in symbols.
45. Using c for “it is cold” and w for “it is windy”, write “To be windy it is necessary that it be cold” in symbols.
46. Using c for “it is cold”, r for “it is rainy”, and w for “it is windy”, write “It is rainy only if it is windy and
cold” in symbols.
, 466 Test Bank Questions and Answers
47. Translate the given statement into propositional logic using the propositions provided: On certain highways
in the Washington, DC metro area you are allowed to travel on high occupancy lanes during rush hour only
if there are at least three passengers in the vehicle. Express your answer in terms of r:“You are traveling
during rush hour.” t:“You are riding in a car with at least three passengers.” and h:“You can travel on a high
occupancy lane.”
48. A set of propositions is consistent if there is an assignment of truth values to each of the variables in the
propositions that makes each proposition true. Is the following set of propositions consistent?
The system is in multiuser state if and only if it is operating normally.
If the system is operating normally, the kernel is functioning.
The kernel is not functioning or the system is in interrupt mode.
If the system is not in multiuser state, then it is in interrupt mode.
The system is in interrupt mode.
49. On the island of knights and knaves you encounter two people, A and B. Person A says “B is a knave.”
Person B says “We are both knights.” Determine whether each person is a knight or a knave.
50. On the island of knights and knaves you encounter two people, A and B. Person A says “B is a knave.”
Person B says “At least one of us is a knight.” Determine whether each person is a knight or a knave.
Exercises 51–53 relate to inhabitants of an island on which there are three kinds of people: knights who always
tell the truth, knaves who always lie, and spies who can either tell the truth or lie. You encounter three people,
A, B, and C. You know one of the three people is a knight, one is a knave, and one is a spy. Each of the three
people knows the type of person each of the other two is. For each of these situations, if possible, determine
whether there is a unique solution, list all possible solutions or state that there are no solutions.
51. A says “I am not a knight,” B says “I am not a spy,” and C says “I am not a knave.”
52. A says “I am a spy,” B says “I am a spy” and C says “B is a spy.”
53. A says “I am a knight,” B says “I am a knave,” and C says “I am not a knave.”
Find the output of the combinatorial circuits in 54–55.
54. p
q
r
55. p
q
q
r
Construct a combinatorial circuit using inverters, OR gates, and AND gates, that produces the outputs in
56–57 from input bits p, q and r.
56. (¬p ∧ ¬q) ∨ (p ∧ ¬r)
57. ((p ∨ ¬q) ∧ r) ∧ ((¬p ∧ ¬q) ∨ r)
Determine whether the compound propositions in 58–59 are satisfiable.
58. (¬p ∨ ¬q) ∧ (p → q)
59. (p → q) ∧ (q → ¬p) ∧ (p ∨ q)
In 60–62 suppose that Q(x) is “x + 1 = 2x”, where x is a real number. Find the truth value of the statement.
, Test Bank Questions and Answers 467
60. Q(2).
61. ∀x Q(x).
62. ∃x Q(x).
In 63–70 P (x, y) means “x+2y = xy”, where x and y are integers. Determine the truth value of the statement.
63. P (1, −1).
64. P (0, 0).
65. ∃y P (3, y).
66. ∀x∃y P (x, y).
67. ∃x∀y P (x, y).
68. ∀y∃x P (x, y).
69. ∃y∀x P (x, y).
70. ¬∀x∃y ¬P (x, y).
In 71–72 P (x, y) means “x and y are real numbers such that x + 2y = 5”. Determine whether the statement
is true.
71. ∀x∃y P (x, y).
72. ∃x∀y P (x, y).
In 73–75 P (m, n) means “m ≤ n”, where the universe of discourse for m and n is the set of nonnegative
integers. What is the truth value of the statement?
73. ∀n P (0, n).
74. ∃n∀m P (m, n).
75. ∀m∃n P (m, n).
In questions 76–81 suppose P (x, y) is a predicate and the universe for the variables x and y is {1, 2, 3}. Suppose
P (1, 3), P (2, 1), P (2, 2), P (2, 3), P (3, 1), P (3, 2) are true, and P (x, y) is false otherwise. Determine whether
the following statements are true.
76. ∀x∃yP (x, y).
77. ∃x∀yP (x, y).
78. ¬∃x∃y (P (x, y) ∧ ¬P (y, x)).
79. ∀y∃x (P (x, y) → P (y, x)).
80. ∀x∀y (x )= y → (P (x, y) ∨ P (y, x)).
81. ∀y∃x (x ≤ y ∧ P (x, y)).
In 82–85 suppose the variable x represents students and y represents courses, and:
U (y): y is an upper-level course M (y): y is a math course F (x): x is a freshman
B(x): x is a full-time student T (x, y): student x is taking course y.
Write the statement using these predicates and any needed quantifiers.
82. Eric is taking MTH 281.
