离散数学及其应用（英文第七版）奇数题答案_离散数学及其应用第七版答案

离散数学

5星 · 超过95%的资源需积分: 50 66 浏览量更新于2023-03-16 评论 26 收藏 4.84MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

P1: 1

ANS Rosen-2311T MHIA017-Rosen-v5.cls May 13, 2011 10:29

Answers to Odd-Numbered Exercises

CHAPTER 1

Section 1.1

1. a) Yes, T b) Yes, F c) Yes, T d) Yes, F e) No f) No

3. 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 or it is not sunny. 5. a) Steve does not have more than

100 GB free disk space on his laptop b) Zach does not block

e-mails from Jennifer, or he does not block texts from Jennifer

c) 7 ·11 · 13 = 999 d) Diane did not ride her bike 100 miles

on Sunday 7. a) F b) T c) T d) T e) T 9. 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 sharks have been spotted near the shore. d) If swimming

at the New Jersey shore is allowed, then sharks have not been

spotted near the shore. e) If 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

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. (Note that we were able to incorporate the paren-

theses by using the word “either” in the second half of the

sentence.) 11. a) p ∧ q b) p ∧¬q c) ¬p ∧¬q d) p ∨q

p → q f) (p ∨ q) ∧ (p →¬q) g) q ↔ p 13. a) ¬p

b) p ∧¬q c) p → q d) ¬p →¬q e) p → q f) q ∧¬p

g) q → p 15. 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 17. a) False b) True c) True d) True

19.

a) Exclusive or: You 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 qual-

iﬁed. d) Either interpretation possible; a traveler might wish

to pay with a mixture of the two currencies, or the store may

not allow that. 21. a) Inclusive or: It is allowable to take

discrete mathematics if you have had calculus or computer

science, or both. Exclusive or: It is allowable to take discrete

mathematics if you have had calculus or computer science,

but not if you have had both. Most likely the inclusive or is

intended. b) 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. Exclusive or: You can take the rebate, or

you can get a low-interest loan, but you cannot get both the

rebate and a low-interest loan. Most likely the exclusive or is

intended. c) Inclusive or: You can order two items from col-

umn A and none from column B, or three items from column

B and none from column A, or ﬁve items including two from

column A and three from column B. Exclusive or: You can

order two items from column A or three items from column

B, but not both. Almost certainly the exclusive or is intended.

d) Inclusive or: More than 2 feet of snow or windchill below

−100, or both, will close school. Exclusive or: More than 2

feet of snow or windchill below −100, but not both, will close

school. Certainly the inclusive or is intended. 23. 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 Pis-

tons 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 90 days ago.

h) If the water is not too cold, then Jan will go swimming.

25. a) You buy an ice cream cone if and only if it is hot out-

side. b) You win the contest if and only if you hold the only

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 a day I

take the train. 27. 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 a 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.” In-

verse: “If a positive integer is not prime, then it has a divisor

other than 1 and itself.” 29. a) 2 b) 16 c) 64 d) 16

31. a)

¬p p ∧¬p

F F

¬p p ∨¬p

F T

pq¬q p ∨¬q (p ∨¬q) → q

F T T

T T F

F F

T F

pqp ∨ q p ∧ q (p ∨ q) → (p ∧ q)

F F

T F

S-1

P1: 1

ANS Rosen-2311T MHIA017-Rosen-v5.cls May 13, 2011 10:29

Answers to Odd-Numbered Exercises S-3

39.

(p ↔ q) ↔

pqr s

p ↔ q r ↔ s (r ↔ s)

TTTT T T T

TTTF

T F F

TTFT

T F F

TTFF

T T T

TFTT

F T F

TFTF

F F T

TFFT

F F

TFFF

T F

FTTT

FTTF

F F T

FTFT

F F

FTFF

F T F

FFTT

T T T

FFTF

T F F

FFFT

T F F

FFFF

T T T

41. The ﬁrst 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. 43. a) Bitwise OR is 111 1111;

bitwise AND is 000 0000; bitwise XOR is 111 1111. b) Bitwise

OR is 1111 1010; bitwise AND is 1010 0000; bitwise XOR is

0101 1010. c) Bitwise OR is 10 0111 1001; bitwise AND is

00 0100 0000; bitwise XOR is 10 0011 1001. d) Bitwise OR

is 11 1111 1111; bitwise AND is 00 0000 0000; bitwise XOR

is 11 1111 1111. 45. 0.2, 0.6 47. 0.8, 0.6 49. 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.

Section 1.2

1. e → a 3. g → (r ∧ (¬m) ∧ (¬b)) 5. e → (a ∧ (b ∨

p) ∧r) 7. a) q → p b) q ∧¬p c) q → p d) ¬q →¬p

9. Not consistent 11. Consistent 13. NEW AND JER-

SEY AND BEACHES, (JERSEY AND BEACHES) NOT

NEW 15. “If I were to ask you whether the right branch

leads to the ruins, would you answer yes?” 17 If the ﬁrst

professor did not want coffee, then he would know that the an-

swer to the hostess’s question was “no.” Therefore the hostess

and the remaining professors know that the ﬁrst professor did

want coffee. Similarly, the second professor must want coffee.

When the third professor said “no,” the hostess knows that the

third professor does not want coffee. 19. A is a knight and

B is a knave. 21. A is a knight and B is a knight. 23. A is

a knave and B is a knight. 25. A is the knight, B is the spy, C

is the knave. 27. A is the knight, B is the spy, C is the knave.

29. Any of the three can be the knight, any can be the spy, any

can be the knave. 31.

No solutions 33. In order of de-

creasing salary: Fred, Maggie, Janice 35. The detective can

determine that the butler and cook are lying but cannot deter-

mine whether the gardener is telling the truth or whether the

handyman is telling the truth. 37. The Japanese man owns

the zebra, and the Norwegian drinks water. 39. One honest,

49 corrupt 41. a) ¬(p∧(q∨¬r))b) ((¬p)∧(¬q))∨(p∧r)

43.

Section 1.3

1. The equivalences follow by showing that the appropriate

pairs of columns of this table agree.

p p ∧ T

p ∨ F p ∧ F

p ∨ T p ∨ p p ∧ p

T T T F T T T

F F F T F F

3. a)

pqp ∨ q q ∨ p

T T

F F

pqp ∧ q q ∧ p

TT T T

F F

(p ∧ q)∨

pqr

q ∨ r p ∧ (q ∨ r) p ∧ q p ∧ r (p ∧ r)

TTT T T T T T

TTF

T T T F T

TFT

T T F T T

TFF

F F F F F

FTT

T F F F F

FTF

T F F F F

FFT

T F F F F

FFF

F F F F F

7. a) Jan is not rich, or Jan is not happy. b) Carlos will not

bicycle tomorrow, and Carlos will not run tomorrow. c) Mei

does not walk to class, and Mei does not take the bus to class.

d) Ibrahim is not smart, or Ibrahim is not hard working.

9. a)

pqp ∧ q (p ∧ q) → p

TT T T

F T

P1: 1

ANS Rosen-2311T MHIA017-Rosen-v5.cls May 13, 2011 10:29

S-4 Answers to Odd-Numbered Exercises

pqp ∨ q p → (p ∨ q)

TT T T

T T

F T

pq¬p

p → q ¬p → (p → q)

F T T

F T

T T

T T T

pqp ∧ q p → q (p ∧ q) → (p → q)

TT T T T

F F T

F T T

pqp → q

¬(p → q) ¬(p → q) → p

T F T

F T T

T F T

p → q ¬(p → q) ¬q ¬(p → q) →¬q

TT T F

F T

F T T T

T F F T

T F T T

11. In each case we will show that if the hypothesis is true,

then the conclusion is also. a) If the hypothesis p ∧ q is true,

then by the deﬁnition of conjunction, the conclusion p must

also be true. b) If the hypothesis p is true, by the deﬁnition

of disjunction, the conclusion p ∨ q is also true. c) If the

hypothesis ¬p is true, that is, if p is false, then the conclusion

p → q is true. d) If the hypothesis p ∧ q is true, then both

p and q are true, so the conclusion p → q is also true. e) If

the hypothesis ¬(p → q) is true, then p → q is false, so

the conclusion p is true (and q is false). f) If the hypothesis

¬(p → q) is true, then p → q is false, so p is true and q is

false. Hence, the conclusion ¬q is true. 13. That the fourth

column of the truth table shown is identical to the ﬁrst column

proves part (a), and that the sixth column is identical to the

ﬁrst column proves part (b).

p ∧ q

p ∨ (p ∧ q) p ∨ q

p ∧ (p ∨ q)

TT T T T T

F T T T

F F T F

F F F F

15. It is a tautology. 17. Each of these is true precisely when

p and q have opposite truth values. 19. The proposition

¬p ↔ q is true when ¬p and q have the same truth val-

ues, which means that p and q have different truth values.

Similarly, p ↔¬q is true in exactly the same cases. There-

fore, these two expressions are logically equivalent. 21. The

proposition ¬(p ↔ q) is true when p ↔ q is false, which

means that p and q have different truth values. Because this is

precisely when ¬p ↔ q is true, the two expressions are logi-

cally equivalent. 23. For (p → r)∧(q → r)to be false, one

of the two conditional statements must be false, which hap-

pens exactly when r is false and at least one of p and q is true.

But these are precisely the cases in which p ∨q is true and r is

false, which is precisely when (p ∨ q) → r is false. Because

the two propositions are false in exactly the same situations,

they are logically equivalent. 25. For (p → r) ∨ (q → r)

to be false, both of the two conditional statements must be

false, which happens exactly when r is false and both p and

q are true. But this is precisely the case in which p ∧ q is

true and r is false, which is precisely when (p ∧ q) → r

is false. Because the two propositions are false in exactly the

same situations, they are logically equivalent. 27. This fact

was observed in Section 1 when the biconditional was ﬁrst

deﬁned. Each of these is true precisely when p and q have the

same truth values. 29. The last column is all Ts.

(p → q) ∧

(p → q) ∧ (q → r) →

pqr

p → q q → r (q → r) p → r (p → r)

TTT T

T T T T

TTF

T F

F F T

TFT

F T

F T T

TFF

F T F F T

FTT

T T T T T

FTF

T F

F T T

FFT

T T T

FFF

T T

T T T

31. These are not logically equivalent because when p, q, and

r are all false, (p → q) → r is false, but p → (q → r) is

true. 33. Many answers are possible. If we let r be true and

p, q, and s be false, then (p → q) → (r → s) will be false,

but (p → r) → (q → s) will be true. 35. a) p ∨¬q ∨¬r

b) (p ∨q ∨r)∧s c) (p ∧T) ∨(q ∧F) 37. If we take duals

twice, every ∨ changes to an ∧ and then back to an ∨, every

∧ changes to an ∨ and then back to an ∧, every T changes to

an F and then back to a T, every F changes to a T and then

back to an F

. Hence, (s

∗

)

∗

= s. 39. Let p and q be equiv-

alent compound propositions involving only the operators ∧,

∨, and ¬, and T and F. Note that ¬p and ¬q are also equiv-

alent. Use De Morgan’s laws as many times as necessary to

push negations in as far as possible within these compound

propositions, changing ∨sto∧s, and vice versa, and chang-

ing TstoFs, and vice versa. This shows that ¬p and ¬q are

the same as p

∗

and q

∗

except that each atomic proposition

within them is replaced by its negation. From this we can

conclude that p

∗

and q

∗

are equivalent because ¬p and ¬q

P1: 1

ANS Rosen-2311T MHIA017-Rosen-v5.cls May 13, 2011 10:29

Answers to Odd-Numbered Exercises S-5

are. 41. (p ∧ q ∧¬r) ∨ (p ∧¬q ∧ r) ∨ (¬p ∧ q ∧ r)

43. Given a compound proposition p, form its truth table

and then write down a proposition q in disjunctive nor-

mal form that is logically equivalent to p. Because q in-

volves only ¬, ∧, and ∨, this shows that these three op-

erators form a functionally complete set. 45. By Exercise

43, given a compound proposition p, we can write down a

proposition q that is logically equivalent to p and involves

only ¬, ∧, and ∨. By De Morgan’s law we can eliminate all

the ∧’s by replacing each occurrence of p

∧ p

∧···∧p

with ¬(¬p

∨¬p

∨···∨¬p

). 47. ¬(p ∧ q) is true

when either p or q, or both, are false, and is false

when both p and q are true. Because this was the deﬁ-

nition of p | q, the two compound propositions are logi-

cally equivalent. 49. ¬(p ∨ q) is true when both p and

q are false, and is false otherwise. Because this was

the deﬁnition of p ↓ q, the two are logically equivalent.

51. ((p ↓ p) ↓ q) ↓ ((p ↓ p) ↓ q) 53. This follows im-

mediately from the truth table or deﬁnition of p | q.

55. 16 57. If the database is open, then either the sys-

tem is in its initial state or the monitor is put in a closed

state. 59. All nine 61. a) Satisﬁable b) Not satisﬁable

c) Not satisﬁable 63. Use the same propositions as were

given in the text for a 9 × 9 Sudoku puzzle, with the vari-

ables indexed from 1 to 4, instead of from 1 to 9, and

with a similar change for the propositions for the 2 × 2

blocks:



r=0



s=0



n=1



i=1



j=1

p(2r + i, 2s + j, n)

65.



i=1

p(i, j, n) asserts that column j contains the number

n,so



n=1



i=1

p(i, j, n) asserts that column j contains all

9 numbers; therefore



j=1



n=1



i=1

p(i, j, n) asserts that

every column contains every number.

Section 1.4

1. a) T b) T c) F 3. a) T b) F c) F d) F 5. a) There

is a student who spends more than 5 hours every weekday

in class. b) Every student spends more than 5 hours ev-

ery weekday in class. c) There is a student who does not

spend more than 5 hours every weekday in class. d) No

student spends more than 5 hours every weekday in class.

7. a) Every comedian is funny. b) Every person is a funny

comedian. c) There exists a person such that if she or he is

a comedian, then she or he is funny. d) Some comedians

are funny. 9. a) ∃x(P(x) ∧ Q(x)) b) ∃x(P(x) ∧¬Q(x))

c) ∀x(P(x)∨Q(x)) d) ∀x¬(P (x) ∨Q(x)) 11. a) T b) T

c) F d) F e) T f) F 13. a) T b) T c) T d) T 15. a) T

b) F c) T d) F 17. a) P(0) ∨ P(

1) ∨ P(2) ∨ P(3) ∨ P(4)

b) P(0) ∧P(1) ∧P(2) ∧P(3) ∧P(4) c) ¬P(0) ∨¬P(1) ∨

¬P(2) ∨¬P(3) ∨¬P(4) d) ¬P(0) ∧¬P(1) ∧

¬P(2) ∧¬P(3) ∧¬P(4) e) ¬(P (0) ∨ P(1) ∨ P(2) ∨

P(3) ∨ P(4)) f) ¬

(P (0) ∧ P(1) ∧ P(2) ∧ P(3) ∧ P(4))

19. a) P(1) ∨P(2) ∨P(3)∨P(4)∨P(5) b) P(1) ∧P(2)∧

P(3) ∧P(4) ∧P(5) c) ¬(P (1) ∨P(2) ∨P(3) ∨P(4) ∨P(5))

d) ¬(P (1) ∧ P(2) ∧ P(3) ∧ P(4) ∧ P(5

)) e) (P (1) ∧

P(2) ∧ P(4) ∧ P(5)) ∨ (¬P(1) ∨¬P(2) ∨¬P(3) ∨

¬P(4) ∨¬P(5)) 21. Many answers are possible. a) All

students in your discrete mathematics class; all students in

the world b) All United States senators; all college football

players c) George W. Bush and Jeb Bush; all politicians

in the United States d) Bill Clinton and George W. Bush;

all politicians in the United States 23. Let C(x) be the

propositional function “x is in your class.” a) ∃xH (x) and

∃x(C(x) ∧ H(x)), where H(x) is “x can speak Hindi”

b) ∀xF (x) and ∀x(C(x) → F(x)), where F(x) is “x is

friendly” c) ∃x¬B(x) and ∃x(C(x) ∧¬B(x)), where B(x) is

“x was born in California” d) ∃xM(x) and ∃x(C(x)∧M(x)),

where M(x) is “x has been in a movie” e) ∀x¬L(x) and

∀x(C(x) →¬L(x)), where L(x) is “x has taken a course

in logic programming” 25. Let P(x) be “x is perfect”;

let F(x) be “x is your friend”; and let the domain be all

people. a) ∀x ¬P(x) b) ¬∀x P (x) c) ∀x(F(x) → P(x))

d) ∃x(F(x) ∧ P(x)) e) ∀x(F(x) ∧ P(x)) or (∀x F (x)) ∧

(∀x P (x)) f) (¬∀x F (x)) ∨ (∃x ¬P(x)) 27. Let Y(x) be

the propositional function that x is in your school or class, as

appropriate. a) If we let V(x) be “x has lived in Vietnam,”

then we have

∃xV (x) if the domain is just your schoolmates,

or ∃x(Y(x) ∧ V(x)) if the domain is all people. If we let

D(x, y) mean that person x has lived in country y, then we

can rewrite this last one as ∃x(Y(x) ∧D(x, Vietnam)). b) If

we let H(x) be “x can speak Hindi,” then we have ∃x¬H(x)

if the domain is just your schoolmates, or ∃x(Y(x)∧¬H(x))

if the domain is all people. If we let S(x, y) mean that per-

son x can speak language y, then we can rewrite this last

one as ∃x(Y(x) ∧¬S(x, Hindi)). c) If we let J(x), P(x),

and C(x) be the propositional functions asserting x’s knowl-

edge of Java, Prolog, and C++, respectively, then we have

∃x(J(x) ∧ P(x) ∧ C(x)) if the domain is just your school-

mates, or ∃x(Y(x) ∧ J(x) ∧ P(x) ∧ C(x)) if the domain

is all people. If we let K(x, y) mean that person x knows

programming language y, then we can rewrite this last one as

∃x(Y(x) ∧ K(x, Java) ∧

K(x,Prolog) ∧K(x, C++)). d) If

we let T(x) be “x enjoys Thai food,” then we have ∀x T (x)

if the domain is just your classmates, or ∀x(Y(x) → T(x))

if the domain is all people. If we let E(x, y) mean that

person x enjoys food of type y, then we can rewrite this

last one as ∀x(Y(x) → E(x, Thai)). e) If we let H(x)

be “x plays hockey,” then we have ∃x ¬H(x) if the do-

main is just your classmates, or ∃x(Y(x) ∧¬H(x)) if

the domain is all people. If we let P(x, y) mean that per-

son x plays game y, then we can rewrite this last one as

∃x(Y(x) ∧¬P(x,hockey)). 29. Let T(x)mean that x is a

tautology and C(x) mean that x is a contradiction. a) ∃x T (x)

b) ∀x(C(x) →T(¬x)) c) ∃x∃y(¬T(x)∧¬C(x)

∧¬T(y)∧

¬C(y)∧T(x ∨ y)) d) ∀x∀y((T (x) ∧T(y)) → T(x∧y))

31. a) Q(0,0,0) ∧ Q(0,1,0) b) Q(0,1,1) ∨Q(1, 1, 1) ∨

Q(2, 1, 1) c) ¬Q(0, 0, 0) ∨¬Q(0, 0, 1) d) ¬Q(0, 0, 1) ∨

¬Q(1, 0, 1) ∨¬Q(2,0

,1) 33. a) Let T(x)be the predicate

that x can learn new tricks, and let the domain be old dogs.

Original is ∃x T (x). Negation is ∀x ¬T(x): “No old dogs can

learn new tricks.” b) Let C(x) be the predicate that x knows

calculus, and let the domain be rabbits. Original is ¬∃x C(x).

剩余96页未读，继续阅读

zyqbit

2016-06-16

挺好的很全面

橘子一方

粉丝: 150
资源: 2

会员权益专享

离散数学及其应用（英文第七版）奇数题答案

评论30

会员权益专享

最新资源

离散数学及其应用（英文第七版）奇数题答案

评论30

离散数学及其应用（第七版）中文答案

离散数学及其应用第七版(本科教学版)中文版答案

离散数学及其应用奇偶数题答案（英文第七版）

离散数学任何图中，度数为奇数的顶点个数是偶数是什么意思啊

离散数学哈密顿图的判断

离散数学用演绎法证明应该如何证明比较好，给出具体方法和例子

python练习题及答案

习题5-2 使用函数求奇数和 (15 分)

算法设计与分析基础anany levitin第三版课后答案

离散数学<Z6,⊕>是什么

求4个整数中偶数的和与奇数的个数。

nth-child 奇数

//判断无向图是否欧拉图 //返回值为奇度数结点数离散数学

本题要求计算给定的一系列正整数中奇数的和。

css选择器选择奇数

c语言程序设计双色版(张玉生) 课后习题参考答案 完

每个立方数都是一个连续的奇数序列之和。编写一程序，输入一个整数（2 <= n <= 20），输出构成n的立方的最长连续奇数序列（即：起始奇数最小的序列）的最小奇数和序列长度。

mysql语句定义函数应用while语句编程求1到50 的所有奇数之和。

给定一个非负整数数组 a， a 中一半整数是奇数，一半整数是偶数。对数组进行排序，以便当 a[i] 为奇数时，i 也是奇数；当 a[i] 为偶数时， i 也是偶数。你可以返回任何满足上述条件的数组作为答案。java

会员权益专享

最新资源

c语言程序设计双色版(张玉生) 课后习题参考答案完