Discrete Mathematics and Its Applications 8th Edition
Chapter 1.1 Solution:
1. Which of these sentences are propositions? What are the truth values of those that are propositions?
Solution:
a) Proposition, T
b) Proposition, F
c) Proposition, T
d) Proposition, F
e) Not a Proposition
f) Not a Proposition
2.Which of these are propositions? What are the truth values of those that are propositions?
Solution:
a) Not a Proposition
b) Not a Proposition
c) Proposition, F
d) Not a proposition
e) Proposition, F
f) Not a Proposition
3.What is the negation of each of these propositions?
Solution:
a) Linda is not younger than Sanjay.
b) Mei does not make more money than Isabella.
c) Moshe is not taller than Monica.
d) Abby is not richer than Ricardo.
4. What is the negation of each of these propositions?
Solution:
a) Janice does not have more Facebook friends than Juan.
b) Quincy is not smarter than Venkat.
c) Zelda does not drive more miles to a school than Paolo.
d) Brianna does not sleep longer than Gloria.
5. What is the negation of each of these propositions?
Solution:
a) Mei does not have an MP3 player.
b) There is pollution in New Jersey.
c) 2 + 1 ≠ 3.
d) The summer in Maine is not hot and it is not sunny.
6. What is the negation of each of these propositions?
Solution:
a) Jennifer and Teja are not friends.
b) There are not 13 items in a baker's zone.
c) Abby has not sent more than 100 text messages yesterday.
d) 121 is not a perfect square.
7. What is the negation of each of these propositions?
Solution:
a) Steve does not have more than 100 GB free disk on his laptop.
b) Zach does not block e-mails and texts from Jennifer.
c) 7•11•13 ≠ 999.
d) Diane did not ride her bicycle 100 miles on Sunday.
8. Suppose that Smartphone A has 256 MB RAM and 32 GB ROM, and the resolution of its camera is 8 MP; Smartphone B has 288 MB RAM and 64 GB ROM, and the resolution of its camera is 4 MP; and Smartphone C has 128 MB RAM and 32 GB ROM, and the resolution of its camera is 5 MP. Determine the truth value of each of these propositions.
Solution:
a) True
b) True
c) False
d) False
e) False
9. Suppose that during the most recent fiscal year, the annual revenue of Acme Computer was 138 billion dollars and its net profit was 8 billion dollars, the annual revenue of Nadir Software was 87 billion dollars and its net profit was 5 billion dollars, and the annual revenue of Quixote Media was 111 billion dollars and its net profit was 13 billion dollars. Determine the truth value of each of these propositions for the most recent fiscal year.
Solution:
a) False
b) True
c) True
d) True
e) True
10. Let p and q be the propositions
p: I bought a lottery ticket this week.
q: I won the million dollar jackpot.
Express each of these propositions as an English sentence.
Solution:
a) I did not buy a lottery ticket this week.
b) I bought a lottery ticket this week or I won the million-dollar jackpot.
c) If I bought a lottery ticket this week, then I won the million-dollar jackpot.
d) I bought a lottery ticket this week and I won the million-dollar jackpot.
e) I bought a lottery ticket this week if and only if I won the million-dollar jackpot.
f) If I did not buy a lottery ticket this week, then I did not win the million-dollar jackpot.
g) I did not buy the lottery ticket this week and I did not win the million-dollar jackpot.
h) I did not buy a lottery ticket this week or, I bought a lottery ticket this week and won the million-dollar jackpot.
11. Let p and q be the propositions “Swimming at the New Jersey shore is allowed” and “Sharks have been spotted near the shore,” respectively. Express each of these compound propositions as an English sentence.
Solution:
a) Sharks have not been spotted near the shore.
b) Swimming at the New Jersey shore is allowed and, sharks have been spotted near the shore.
c) Swimming at the New Jersey shore is not allowed or, the sharks have been spotted near the shore.
d) If the swimming at the New Jersey Shore is allowed, then the sharks have not been spotted near the shore.
e) If the sharks have not been spotted near the shore, then swimming at the New Jersey shore is allowed.
f) If swimming at the New Jersey shore is not allowed, then the sharks have not been spotted near the shore.
g) Swimming at the New Jersey shore is allowed if and only if sharks have not been spotted near the shore.
h) Swimming at the New Jersey shore is not allowed and either, swimming at the New Jersey shore is allowed or sharks have not been spotted near the shore.
12. Let p and q be the propositions “The election is decided” and “The votes have been counted,” respectively. Express each of these compound propositions as an English sentence.
Solution:
a) The election is not decided.
b) The election is decided or the votes have been counted.
c) The election is not decided and the votes have been counted.
d) If the votes have been counted, then the election is decided.
e) If the votes have not been counted, then the election is not decided.
f) If the election is not decided, then the votes have not been counted.
g) The election is decided if and only if the votes have been counted.
h) The votes have not been counted or, the election is not decided and the votes have been counted.
13. . Let p and q be the propositions
p: It is below freezing.
q: It is snowing.
Write these propositions using p and q and logical connectives (including negations).
Solution:
a) p ˄ q
b) p ˄ ~q
c) ~p ˄ ~q
d) p ˅ q
e) p → q
f) (p ˅ q) ˄ (p → ~q)
g) q ↔ p
14. Let p, q, and r be the propositions
p: You have the flu.
q: You miss the final examination.
r: You pass the course.
Express each of these propositions as an English sentence.
Solution:
a) If you have flu, then you will miss the final examination.
b) You won't miss the final examination if and only if you pass the course.
c) If you miss the final examination, then you will not pass the course.
d) You have the flu or, you miss the final examination or, you will pass the course.
e) If you have the flu then you will not pass the course or, if you miss the final examination then you will not pass the course.
f) You have the flu and you pass the examination or, you will not miss the examination and you will pass the course.
15. Let p and q be the propositions
p: You drive over 65 miles per hour.
q: You get a speeding ticket.
Write these propositions using p and q and logical connectives (including negations).
Solution:
a) ~p
b) p ˄ ~q
c) p → q
d) ~p → ~q
e) p → q
f) q ˄ ~p
g) q → p
16. Let p, q, and r be the propositions
p: You get an A on the final exam.
q: You do every exercise in this book.
r: You get an A in this class.
Write these propositions using p, q, and r and logical connectives (including negations).
Solution:
a) r ˄ ~q
b) p ˄ q ˄ r
c) r → p
d) p ˄ ~q ˄ r
d) (p ˄ q) → r
e) r ↔ (q ˅ p)
17. Let p, q, and r be the propositions
p: Grizzly bears have been seen in the area.
q: Hiking is safe on the trail.
r: Berries are ripe along the trail.
Write these propositions using p, q, and r and logical connectives (including negations).
Solution:
a) r ˄ ~p
b) ~p ˄ q ˄ r
c) r → (q ↔ ~p)
d) ~q ˄ ~p ˄ r
e) (q → (~r ˄ ~p)) ˄ ~((~r ˄ ~p) → q)
f) (p ˄ r) → ~q
18. Determine whether these biconditionals are true or false.
Solution:
a) True
b) False
c) True
d) False
19. Determine whether each of these conditional statements is true or false.
Solution:
a) False
b) True
c) True
d) True
20. Determine whether each of these conditional statements is true or false.
Solution:
a) True
b) True
c) False
d) True
21. For each of these sentences, determine whether an inclusive or, or an exclusive or, is intended. Explain your answer.
Solution:
a) Exclusive or: You can get only one beverage
b) Inclusive or: Long passwords can have any combination of symbols.
c) Inclusive or: A student with both courses is even more qualified.
d) Both are possible: A traveller might wish to pay with a mixture of the two currencies, or the store may not allow that.
22. For each of these sentences, determine whether an inclusive or, or an exclusive or, is intended. Explain your answer.
Solution:
a) Inclusive or: We can know either one language or we can know both.
b) Exclusive or: We can have either soup or salad, but not both.
c) Inclusive or: You can have either a passport or a voter registration card, or you can have both.
d) Exclusive or: You can choose either public or perish, but not both.
23. . For each of these sentences, state what the sentence means if the logical connective or is an inclusive or (that is, a disjunction) versus an exclusive or. Which of these meanings of or do you think is intended?
Solution:
ai) Inclusive or: It is allowable to take discrete mathematics if you have had calculus or computer science, or both.
ii) Exclusive or: It is allowable to take discrete mathematics if you had calculus or computer science, but not both.
bi) Inclusive or: You can take the rebate or you can get a low-interest loan, or you can get both the rebate and a low-interest loan.
ii) Exclusive or: You can take the rebate or you can get a low- interest loan, but not both.
ci) Inclusive or: You can order two items from column A and none from column B, or three items from column B and none from column A, two items from column A and three items from column B both.
ii) Exclusive or: You can order two items from column A, or three items from column B, but not both.
di) Inclusive or: It can be more than 2 feet of snow or windchill below -100° F, or both, will close the school.
ii) Exclusive or: It can be more than 2 feet of snow or windchill below -100° F, bit not both, will close the school.
24. Write each of these statements in the form “if p, then q” in English. [Hint: Refer to the list of common ways to express conditional statements provided in this section.]
Solution:
a) If you get promoted, then you can wash boss's car.
b) If the wind comes from the south, then there will be a spring thaw.
c) If you bought the computer, less than a year ago, then the warranty is good.
d) If Willy cheats, then he gets caught.
e) If you can access the website, then you pay a subscription fee.
f) If you know the right people, then you get elected.
g) If Carol gets on a boat, then she gets seasick.
25. Write each of these statements in the form “if p, then q” in English. [Hint: Refer to the list of common ways to express conditional statements.]
Solution:
a) If the wind blows from the northeast, then it snows.
b) If it stays warm for a week, then the apple trees will bloom.
c) If the Pistons win the championship, then they beat the Lakers.
d) If you get to the top of Long's Peak, then you must have walked 8 miles.
e) If you are world-famous, then you will get tenure as a professor.
f) If you drive more than 400 miles, then you will need to buy gasoline.
g) If your guarantee is good, then you must have bought your CD player less than 90days ago.
h) If the water is not too cold, then Jan will go swimming.
i) If people believe in science, then we will have a future.
26. Write each of these statements in the form “if p, then q” in English. [Hint: Refer to the list of common ways to express conditional statements provided in this section.]
Solution:
a) If you send an e-mail, then I will remember to send the address.
b) If you were born in the US, then you are a citizen.
c) If you keep your textbook, then it will be a useful reference.
d) If the goalie plays well, then they will win.
e) If you get the job, then you have the best credentials.
f) If there is a storm, then the beach erodes.
g) If you have a valid passport, then you can logon.
h) If you begin your climb late, then you will not reach the summit.
i) If you are among the first 100, then you get the ice cream.
27. Write each of these propositions in the form “p if and only if q” in English.
Solution:
a) You buy an ice cream cone if and only if it is hot outside.
b) You win the contest if and only if you hold the winning ticket.
c) You get promoted if and only if you have connections.
d) Your mind will decay if and only if you watch television.
e) The train runs late if and only if it is the day I take the train.
28. Write each of these propositions in the form “p if and only if q” in English.
Solution:
a) You get an A in this course if and only if you learn how to solve discrete mathematics problems
b) You will be informed if and only if you read the newspaper every day.
c) It rains if and only if it is a weekend day.
d) You can see the wizard if and only if the wizard is not in.
e) My airplane flight is always late if and only if when I have to catch a connecting flight.
29. State the converse, contrapositive, and inverse of each of these conditional statements.
Solution:
a) Converse: I will ski tomorrow only if it snows today.
Contrapositive: If I do not ski tomorrow, then it will not have snowed today.
Inverse: If it does not snow today, then I will not ski tomorrow.
b) Converse: If I come to class, then there will be a quiz.
Contrapositive: If I do not come to class, then there will not be a quiz.
Inverse: If there is not going to be a quiz, then I don’t come to class.
c) Converse: A positive integer is prime if it has no divisors other than 1 and itself.
Contrapositive: If a positive integer has a divisor other than 1 and itself, then it is not prime.
Inverse: If a positive integer is not prime, then it has a divisor other than 1 and itself.
30. State the converse, contrapositive, and inverse of each of these conditional statements.
Solution:
a) Converse: If I stay at home, then it will snow tonight.
Contrapositive: If I don't stay at home tonight, then it won't be snowing.
Inverse: If it does not snow tonight, then I will not stay at home.
b) Converse: Whenever I go to the beach, it is a sunny summer day.
Contrapositive: Whenever I do not go to the beach, it is not a sunny summer day.
Inverse: Whenever it is not a sunny summer day, I do not go to the beach.
c) Converse: If I need to sleep until noon, then I stayed up late.
Contrapositive: If I don't need to sleep until noon, then I didn't stay up late.
Inverse: If I don't stay up late, then I don't need to sleep until noon.
31. How many rows appear in a truth table for each of these compound propositions?
Solution:
a) 2
b) 16
c) 64
d) 16
32. How many rows appear in a truth table for each of these compound propositions?
Solution:
a) 4
b) 8
c) 64
d) 32
33. Construct a truth table for each of these compound propositions.
Solution:
a)
b)
c)
Solution:
a)
c)
e)
f)
Solution:
a)
e)
f)
36. Construct a truth table for each of these compound propositions.
Solution:
a)
37. Construct a truth table for each of these compound propositions.
Solution:
a), b), c), d), e), f)
38. Construct a truth table for each of these compound propositions.
Solution:
a), b), c), d), e), f)
39. Construct a truth table for each of these compound propositions.
Solution:
a), b), c), d), e), f)
40. Construct a truth table for ((p → q) → r) → s.
Solution:
41. Construct a truth table for (p ↔ q) ↔ (r ↔ s).
Solution:
42. Explain, without using a truth table, why (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p) is true when p, q, and r have the same truth value and it is false otherwise.
Solution:
Assume p, q, r. If p, q, r are all true then the whole statement is true. If p, q, r are all false then the whole statement is true. p, q have unequal truth values. (p ˅ ~q) ˄ (q ˅ ~r) ˄ (r ˅ ~p). The statement is true if and only if they have all the truth value.
43. Explain, without using a truth table, why (p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r) is true when at least one of p, q, and r is true and at least one is false, but is false when all three variables have the same truth value.
Solution:
The first clause is true if and only if at least one of p, q, and r is true. The second clause is true if and only if at least one of the three variables is false. Therefore, the entire statement is true if and only if there is at least one T and one F among the truth values of the variables, in other words, that they don’t all have the same truth value.
44. If p1, p2,… , pn are n propositions, explain why
⋀n−1 i=1 ⋀n j=i+1 (¬pi ∨ ¬pj )
is true if and only if at most one of p1, p2,… , pn is true.
Solution:
If we write the expended form, we have
(¬𝑃_1 ∨ ¬𝑃_2) ∧ (¬𝑃_1 ∨ ¬𝑃_3) ∧ (¬𝑃_1 ∨ ¬𝑃_4) ∧ … ∧ (¬𝑃_1 ∨ ¬𝑃_𝑛) ∧ (¬𝑃_2 ∨ ¬𝑃_3) ∧ (¬𝑃_2 ∨ ¬𝑃_4) ∧ … ∧ (¬𝑃_2 ∨ ¬𝑃_𝑛) ∧ … ∧ (¬𝑃_(𝑛−1) ∨ ¬𝑃_𝑛) ≡ 𝐼
We know that (¬𝑃_𝑖 ∨ ¬𝑃_𝑗) ≡ ¬(𝑃_𝑖 ∧ 𝑃_𝑗)
We also know that 𝐼 is true when ¬(𝑃_𝑖 ∧ 𝑃_𝑗) is true for every i and j
This means that 𝑃_𝑖 ∧ 𝑃_𝑗 should be false for every i and j. This means that we can have zero or one 𝑃_𝑖 that is true.
On the other hand, if we have zero or one 𝑃_𝑖 equal to true then ¬𝑃_𝑖 ∨ ¬𝑃_𝑗 is always true. That results in 𝐼 to be true.
45. Use Exercise 44 to construct a compound proposition that is true if and only if exactly one of the propositions p1, p2,… , pn is true. [Hint: Combine the compound proposition in Exercise 44 and a compound proposition that is true if and only if at least one of p1, p2,… , pn is true.]
Solution:
Solution:
a) 2
b) 1
c) 2
d) 1
e) 2
47. Find the bitwise OR, bitwise AND, and bitwise XOR of each of these pairs of bit strings.
Solution:
a) Bitwise OR: 111 1111
Bitwise AND: 000 0000
Bitwise XOR: 111 1111
b) Bitwise OR:1111 1010
Bitwise AND: 1010 0000
Bitwise XOR: 0101 1010
c) Bitwise OR: 10 0111 1001
Bitwise AND: 00 0100 0000
Bitwise XOR: 10 0011 1001
d) Bitwise OR:11 1111 1111
Bitwise AND: 00 0000 0000
Bitwise XOR: 11 1111 1111
48. Evaluate each of these expressions.
Solution:
a) 11000
b) 01101
c) 11001
d) 11011
49. The truth value of the negation of a proposition in fuzzy logic is 1 minus the truth value of the proposition. What are the truth values of the statements “Fred is not happy” and “John is not happy”?
Solution:
Truth value of the negation of the statement "Fred is happy" is:
= 1 - 0.8
=0.2
Truth value of the negation of the statement "John is happy" is:
= 1 - 0.4
= 0.6
50. The truth value of the conjunction of two propositions in fuzzy logic is the minimum of the truth values of the two propositions. What are the truth values of the statements “Fred and John are happy” and “Neither Fred nor John is happy”?
Solution:
Truth value of the statement "Fred and John are happy" is:
0.4
Truth value of the statement "Neither Fred nor John is happy" is:
= 0.2
51. The truth value of the disjunction of two propositions in fuzzy logic is the maximum of the truth values of the two propositions. What are the truth values of the statements “Fred is happy, or John is happy” and “Fred is not happy, or John is not happy”?
Solution:
Truth value of the statement "Fred is happy, or John is happy" is:
= 0.8
Truth value of the statement "Fred is not happy, or John is not happy" is:
= 0.6
52. Is the assertion “This statement is false” a proposition?
This is not a proposition.
53. The nth statement in a list of 100 statements is “Exactly n of the statements in this list are false.”
Solution:
a) The 99th statement is true and the rest are false.
b) Statements 1 through 50 are all true and statements 51 through 100 are all false.
c) This cannot happen; it is a paradox, showing that these cannot be statements.
54. An ancient Sicilian legend says that the barber in a remote town who can be reached only by traveling a dangerous mountain road shaves those people, and only those people, who do not shave themselves. Can there be such a barber?
Solution:
No, it is a paradox.
The end
Hope the solutions helped. Comment which book's solution you want me to upload.
Thank You
0 Comments