Discrete Mathematics

Discrete Mathematics and Its Applications 8 th Edition Kenneth H. Rosen

• / 4

1

CHAPTER 1

The Foundations: Logic and Proofs

SECTION 1.1

2.Propositions must have clearly dened truth values, so a proposition must be a declarative sentence with no free variables.a)This is not a proposition; it's a command.b)This is not a proposition; it's a question.c)This is a proposition that is false, as anyone who has been to Maine knows.d)This is not a proposition; its truth value depends on the value ofx.e)This is a proposition that is false.f)This is not a proposition; its truth value depends on the value ofn.

• Janice does not have more Facebook friends than Juan.

b)Quincy is not smarter than Venkat.c)Zelda does not drive more miles to school than Paola.d)Briana does not sleep longer than Gloria.

• Jennifer and Teja are not friends.

b)There are not 13 items in a baker's dozen. (Alternatively: The number of items in a baker's dozen is not equal to 13.) c)Abby sent fewer than 101 text messages yesterday. Alternatively, Abby sent at most 100 text messages yesterday.d)121 is not a perfect square.

• True, because 288>256 and 288>128.

b)True, because C has 5 MP resolution compared to B's 4 MP resolution. Note that only one of these conditions needs to be met because of the wordor.c)False, because its resolution is not higher (all of the statements would have to be true for the conjunction to be true).d)False, because the hypothesis of this conditional statement is true and the conclusion is false.e)False, because the rst part of this biconditional statement is false and the second part is true.

• I did not buy a lottery ticket this week.

b)Either I bought a lottery ticket this week, or [in the inclusive sense] I won the million dollar jackpot on Friday.c)If I bought a lottery ticket this week, then I won the million dollar jackpot on Friday.d)I bought a lottery ticket this week, and I won the million dollar jackpot on Friday.e)I bought a lottery ticket this week if and only if I won the million dollar jackpot on Friday.f)If I did not buy a lottery ticket this week, then I did not win the million dollar jackpot on Friday.g)I did not buy a lottery ticket this week, and I did not win the million dollar jackpot on Friday. 2 / 4

2Chapter 1 The Foundations: Logic and Proofs

h)Either I did not buy a lottery ticket this week, or else I did buy one and won the million dollar jackpot on Friday.

• 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)Either the votes have not been counted, or else the election is not decided and the votes have been counted.Note that we were able to incorporate the parentheses by using the wordseitherandelse.

• If you have the u, then you miss the nal exam.

b)You do not miss the nal exam if and only if you pass the course.c)If you miss the nal exam, then you do not pass the course.d)You have the u, or miss the nal exam, or pass the course.e)It is either the case that if you have the u then you do not pass the course, or the case that if you miss the nal exam then you do not pass the course (or both, it is understood).f)Either you have the u and miss the nal exam, or you do not miss the nal exam and do pass the course.

• r^ :q b)p^q^r c)r!p d)p^ :q^r e)(p^q)!r f)r$(q_p)
• This isT$T, which is true.

b)This isT$F, which is false.c)This isF$F, which is true.d)This isF$T, which is false.

• This isF!F, which is true.

b)This isF!F, which is true.c)This isT!F, which is false.d)This isT!T, which is true.

• The employer making this request would be happy if the applicant knew both of these languages, so this

is clearly an inclusiveor.b)The restaurant would probably charge extra if the diner wanted both of these items, so this is an exclusive or.c)If a person happened to have both forms of identication, so much the better, so this is an inclusiveor.d)This could be argued either way, but the inclusive interpretation seems more appropriate. This phrase means that faculty members who do not publish papers in research journals are likely to be red from their jobs during the probationary period. On the other hand, it may happen that they will be red even if they do publish (for example, if their teaching is poor).

• The necessary condition is the conclusion: If you get promoted, then you wash the boss's car.

b)If the winds are from the south, then there will be a spring thaw.c)The sucient condition is the hypothesis: If you bought the computer less than a year ago, then the warranty is good. 3 / 4

Section 1.1 Propositional Logic3 d)If Willy cheats, then he gets caught.e)The \only if" condition is the conclusion: If you access the website, then you must pay a subscription fee.f)If you know the right people, then you will be elected.g)If Carol is on a boat, then she gets seasick.

• If I am to remember to send you the address, then you will have to send me an e-mail message. (This has

been slightly reworded so that the tenses make more sense.) b)If you were born in the United States, then you are a citizen of this country.c)If you keep your textbook, then it will be a useful reference in your future courses. (The word hen" is understood in English, even if omitted.) d)If their goaltender plays well, then the Red Wings will win the Stanley Cup.e)If you get the job, then you had the best credentials.f)If there is a storm, then the beach erodes.g)If you log on to the server, then you have a valid password.h)If you do not begin your climb too late, then you will reach the summit.i)If you are among the rst 100 customers tomorrow, then you will get a free ice cream cone.

• You will 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. (It sounds better in this order; it would be logically equivalent to state this as \You read the newspaper every day if and only if you will be informed.") c)It rains if and only if it is a weekend day.d)You can see the wizard if and only if he is not in.e)My airplane ight is late if and only if I have to catch a connecting ight.

• Converse: If I stay home, then it will snow tonight. Contrapositive: If I do not stay at home, then it will

not snow tonight. Inverse: If it does not snow tonight, then I will not stay 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 day, I do not go to the beach.c)Converse: If I sleep until noon, then I stayed up late. Contrapositive: If I do not sleep until noon, then I did not stay up late. Inverse: If I don't stay up late, then I don't sleep until noon.

32.A truth table will need 2 n rows if there arenvariables.a)2 2 = 4 b)2 3 = 8 c)2 6 = 64 d)2 5 = 32 34.To construct the truth table for a compound proposition, we work from the inside out. In each case, we will show the intermediate steps. In part (d), for example, we rst construct the truth tables forp^qand forp_q and combine them to get the truth table for (p^q)!(p_q). For parts (a) and (b) we have the following table (column three for part (a), column four for part (b)).p:p p! :p p$ :p

T F F F

F T T F

For parts (c) and (d) we have the following table.p q p_q p^q p(p_q) (p^q)!(p_q)

T T T T F T

T F T F F T

F T T F T T

F F F F F T

• / 4