第1页 / 共576页
第2页 / 共576页
第3页 / 共576页
第4页 / 共576页
第5页 / 共576页
第6页 / 共576页
第7页 / 共576页
第8页 / 共576页
离散数学及应用（第七版）奇数题答案.pdf
Cover
TOC
Ch.1
Sec. 1.1
Sec. 1.2
Sec. 1.3
Sec. 1.4
Sec. 1.5
Sec. 1.6
Sec. 1.7
Sec. 1.8
Guide to Review Ch.1
Supp. Excercises Ch.1
Writing Projects Ch.1
Ch.2
Sec. 2.1
Sec. 2.2
Sec. 2.3
Sec. 2.4
Sec. 2.5
Sec. 2.6
Guide to Review Ch.2
Supp. Excercises Ch.2
Writing Projects Ch.2
Ch.3
Sec. 3.1
Sec. 3.2
Sec. 3.3
Guide to Review Ch.3
Supp. Excercises Ch.3
Writing Projects Ch.3
Ch.4
Sec. 4.1
Sec. 4.2
Sec. 4.3
Sec. 4.4
Sec. 4.5
Sec. 4.6
Guide to Review Ch.4
Supp. Excercises Ch.4
Writing Projects Ch.4
Ch.5
Sec. 5.1
Sec. 5.2
Sec. 5.3
Sec. 5.4
Sec. 5.5
Guide to Review Ch.5
Supp. Excercises Ch.5
Writing Projects Ch.5
Ch.6
Sec. 6.1
Sec. 6.2
Sec. 6.3
Sec. 6.4
Sec. 6.5
Sec. 6.6
Guide to Review Ch.6
Supp. Excercises Ch.6
Writing Projects Ch.6
Ch.7
Sec. 7.1
Sec. 7.2
Sec. 7.3
Sec. 7.4
Guide to Review Ch.7
Supp. Excercises Ch.7
Writing Projects Ch.7
Ch.8
Sec. 8.1
Sec. 8.2
Sec. 8.3
Sec. 8.4
Sec. 8.5
Sec. 8.6
Guide to Review Ch.8
Supp. Excercises Ch.8
Writing Projects Ch.8
Ch.9
Sec. 9.1
Sec. 9.2
Sec. 9.3
Sec. 9.4
Sec. 9.5
Sec. 9.6
Guide to Review Ch.9
Supp. Excercises Ch.9
Writing Projects Ch.9
Ch.10
Sec. 10.1
Sec. 10.2
Sec. 10.3
Sec. 10.4
Sec. 10.5
Sec. 10.6
Sec. 10.7
Sec. 10.8
Guide to Review Ch.10
Supp. Excercises Ch.10
Writing Projects Ch.10
Ch.11
Sec. 11.1
Sec. 11.2
Sec. 11.3
Sec. 11.4
Sec. 11.5
Guide to Review Ch.11
Supp. Excercises Ch.11
Writing Project Ch.11
Ch.12
Sec. 12.1
Sec. 12.2
Sec. 12.3
Sec. 12.4
Guide to Review Ch.12
Supp. Excercise Ch.12
Writing Projects Ch.12
Ch.13
Sec. 13.1
Sec. 13.2
Sec. 13.3
Sec. 13.4
Sec. 13.5
Guide for Review Ch.13
Supp. Excercises Ch.13
Writing Projects Ch.13
Appendixes
Appendix 1
Appendix 2
Appendix 3
Guide to Proof-Writing
General Advice on the Writing Projects
List of Referenes for the Writing Projects
Sample Tests
Sample Test Ch.1
Solutions Sample Test Ch.1
Sample Test Ch.2
Solutions Sample Test Ch.2
Sample Test Ch.3
Solitions Sample Test Ch.3
Sample Test Ch.4
Solutions Sample Test Ch.4
Sample Test Ch.5
Solutions Sample Test Ch.5
Sample Test Ch.6
Solutions Sample Test Ch.6
Sample Test Ch.7
Soutions Sample Test Ch.7
Sample Test Ch.8
Solutions Sample Test Ch.8
Sample Test Ch.9
Solutions Sample Test Ch.9
Sample Test Ch.10
Solutions Sample Test Ch.10
Sample Test Ch.11
Solutions Sample Test Ch.11
Sample Test Ch.12
Solutions Sample Test Ch.12
Sample Test Ch.13
Solutions Sample Test Ch.13
Common Mistakes in Discrete Mathematics
Solving Problems in Discrete Mathematics
List of Common Mistakes
Ch.1
Ch.2
Ch.3
Ch.4
Ch.5
Ch.6
Ch.7
Ch.8
Ch.9
Ch.10
Ch.11
Ch.12
Ch.13
Appenixes
Crib Sheets
Ch.1
Ch.2
Ch.3
Ch.4
Ch.5
Ch.6
Ch.7
Ch.8
Ch.9
Ch.10
Ch.11
Ch.12
Ch.13
NOTES
Student's Solutions Guide
to accompany
.:..·
~'
:
· ·Discrete· .
. . ·.Mathematics·
. .
.
'
and Its
Applications
SEVENTH EDITION
Prepared by
Jerrold Grossman .
Student's Solutions Guide
to accompany
Discrete Mathematics
and Its Applications
Seventh Edition
Kenneth H. Rosen
Monmouth University
(and formerly AT&T Laboratories)
Prepared by
Jerrold W. Grossman
Oakland University
~~onnect
Learn
Succeed"
•
The McGrow·Hill Companies
~~onnect
learn
Succeed'
•
Student's Solutions Guide to accompany
DISCRETE MATHEMATICS AND ITS APPLICATIONS, SEVENTH EDITION
KENNETH H. ROSEN
Published by McGraw-Hill Higher Education, an imprint of The McGraw-Hill Compames, Inc., 1221 Avenue of the Americas, New
York, NY 10020. Copyright© 2012 and 2007 by The McGraw-Hill Companies, Inc. All rights reserved.
Pnnted in the United States of America.
No part of this publication may be reproduced or distributed many form or by any means, or stored ma database or retrieval system,
without the prior written consent of The McGraw-Hill Companies, Inc., including, but not limited to, network or other electronic
storage or transm1ss10n, or broadcast for distance leammg.
1234567890QDB~DB10987654321
ISBN: 978-0-07-735350-6
MHID: 0-07-735350-1
www.mhhe.com
Preface
This Student's Solutions Guide for Discrete Mathematics and Its Applications, seventh edition,
contains several useful and important study aids.
• SOLUTIONS TO ODD-NUMBERED EXERCISES
The bulk of this work consists of solutions to all the odd-numbered exercises in
the text. These are not just answers, but complete, worked-out solutions, showing how
the principles discussed in the text and examples are applied to the problems. I have also
added bits of wisdom, insights, warnings about errors to avoid, and extra comments that
go beyond the question as posed. Furthermore, at the beginning of each section you will
find some general words of advice and hints on approaching the exercises in that section.
• REFERENCES FOR CHAPTER REVIEWS
Exact page references, theorem and example references, and answers are provided as a
guide for all the chapter review questions in the text. This will make reviewing for
tests and quizzes particularly easy.
• A GUIDE TO WRITING PROOFS
Near the end of this book is a section on writing proofs, a skill that most stu
dents find difficult to master. Proofs are introduced formally in Chapter 1 (and proofs by
mathematical induction are studied in Chapter 5), but exercises throughout the text ask
for proofs of propositions. Reading this section when studying Sections 1.6-1.8, and then
periodically thereafter, will be rewarded, as your proof-writing ability grows.
• REFERENCES AND ADVICE ON THE WRITING PROJECTS
Near the end of this book you will find some general advice on the Writing Projects
given at the end of each chapter. There is a discussion of various resources available in the
mathematical sciences (such as Mathematical Reviews and the World Wide Web), tips on
doing library research, and some suggestions on how to write well.
In addition, there
is a rather extensive bibliography of books and articles that will be useful when
researching these projects. We also provide specific hints and suggestions for each project,
with pointers to the references; these can be found in the solutions section of this manual,
at the end of each chapter.
• SAMPLE CHAPTER TESTS
Near the end of this book you will find a sequence of 13 chapter tests, comparable
to what might be given in a course. You can take these sample tests in a simulated test
setting as practice for the real thing. Complete solutions are provided, of course.
• PROBLEM-SOLVING TIPS AND LIST OF COMMON MISTAKES
People beginning any endeavor tend to make the same kinds of mistakes. This is
especially true in the study of mathematics. I have included a detailed list of common
misconceptions that students of discrete mathematics often have and the kinds of errors
they tend to make. Specific examples are given. It will be useful for you to review this list
from time to time, to make sure that you are not falling into these common traps. Also
included in this section is general advice on solving problems in mathematics, which you
will find helpful as you tackle the exercises.
• CRIB SHEETS
Finally, I have prepared a set of 13 single-page "crib sheets," one for each chapter
of the book. They provide a quick summary of all the important concepts, definitions, and
lll
theorems in the chapter. There are at least three ways to use these. First, they can be used
as a reference source by someone who wants to brush up on the material quickly or reveal
gaps in old knowledge. Second, they provide an excellent review sheet for studying for tests
and quizzes, especially useful for glancing over in the last few minutes. And third, a copy
of this page (augmented by your own notes in the margins) is ideal in those cases where an
instructor allows the students to come to a test with notes.
Several comments about the solutions in this volume are in order. In many cases, more
than one solution to an exercise is presented, and sometimes the solutions presented here are
not the same as the answers given in the back of the text. Indeed, there is rarely only one way
to solve a problem in mathematics. You may well come upon still other valid ways to arrive at
the correct answers. Even if you have solved a problem completely, you will find that reviewing
the solutions presented here will be valuable, since there is insight to be gained from seeing how
someone else handles a problem that you have just solved.
Exercises often ask that answers be justified or verified, or they ask you to show or prove
a particular statement. In all these cases your solution should be a proof, i.e., a mathematical
argument based on the rules of logic. Such a proof needs to be complete, convincing, and correct.
Read your proof after finishing it. Ask yourself whether you would understand and believe it if
it were presented to you by your instructor.
Although I cannot personally discuss with you my philosophy on learning discrete mathe
matics by solving exercises, let me include a few general words of advice. The best way to learn
mathematics is by solving problems, and it is crucial that you first try to work these exercises
independently. Consequently, do not use this Guide as a crutch. Do not look at the solution
(or even the answer) to a problem before you have worked on it yourself. Resist the temptation
to consult the solution as soon as the going gets rough. Make a real effort to work the problem
completely on your own-preferably to the point of writing down a complete solution-before
checking your work with the solutions presented here. If you have not been able to solve a prob
lem and have reached the point where you feel it necessary to look at the answer or solution,
try reading it only casually, looking for a hint as to how you might proceed; then try working
on the exercise again, armed with this added information. As a last resort, study the solution
in detail and make sure you could explain it to a fellow student.
I want to thank Jerry Grossman for his extensive advice and assistance in the preparation of
this entire Guide, Paul Lorczak, Suzanne Zeitman, and especially Georgia Mederer for double
checking the solutions, Ron Marash for preparing the advice on writing proofs, and students
at Monmouth College and Oakland University for their input on preliminary versions of these
solutions.
A tremendous amount of effort has been devoted to ensuring the accuracy of these solutions,
but it is possible that a few scattered errors remain. I would appreciate hearing about all that
you find, be they typographical or mathematical. You can reach me using the Reporting of
Errata link on the companion website's Information Center at www.mhhe.com/rosen.
One final note: In addition to this Guide, you will find the companion website created
for Discrete Mathematics and Its Applications an invaluable resource.
Included here are a
Web Resources Guide with links to external websites keyed to the textbook, numerous Extra
Examples to reinforce important topics, Interactive Demonstration Applets for exploring key
algorithms, Self Assessment question banks to gauge your understanding of core concepts, and
many other helpful resources. See the section titled "The Companion Website" on page xvi of
the textbook for more details. The address is www.mhhe.com/rosen.
Kenneth H. Rosen
iv
Contents
Preface
CHAPTER 1
The Foundations: Logic and Proofs
iii
1
1
11
1 7
Propositional Logic
Applications of Propositional Logic
Propositional Equivalences
Predicates and Quantifiers
Nested Quantifiers
Rules of Inference
36
Introduction to Proofs
Proof Methods and Strategy
1.1
1.2
1.3
1.4
1.5
1.6
1. 7
40
1.8
Guide to Review Questions for Chapter 1
Supplementary Exercises for Chapter 1
Writing Projects for Chapter 1
23
32
48
8
44
45
CHAPTER 2
Basic Structures: Sets, Functions,
Sequences, Sums, and Matrices
50
50
59
53
Sets
Set Operations
Functions
Sequences and Summations
Cardinality of Sets
Matrices
2.1
2.2
2 .3
2.4
2.5
2.6
Guide to Review Questions for Chapter 2
Supplementary Exercises for Chapter 2
Writing Projects for Chapter 2
87
79
68
75
CHAPTER 3
88
Algorithms
Algorithms
The Growth of Functions
Complexity of Algorithms
3.1
3.2
97
3.3
103
Guide to Review Questions for Chapter 3
Supplementary Exercises for Chapter 3
Writing Projects for Chapter 3
112
83
84
107
108
88
CHAPTER 4
Number Theory and Cryptography
113
113
116
122
Divisibility and Modular Arithmetic
Integer Representations and Algorithms
Primes and Greatest Common Divisors
130
Solving Congruences
Applications of Congruences
Cryptography
4.1
4.2
4.3
4.4
4.5
4.6
Guide to Review Questions for Chapter 4
Supplementary Exercises for Chapter 4
Writing Projects for Chapter 4
147
137
140
142
143
v
CHAPTER 5
Induction and Recursion
149
149
Mathematical Induction
Strong Induction and Well-Ordering
Recursive Definitions and Structural Induction
Recursive Algorithms
Program Correctness
5.1
5.2
5.3
5.4
5.5
Guide to Review Questions for Chapter 5
Supplementary Exercises for Chapter 5
Writing Projects for Chapter 5
195
183
185
176
182
161
167
CHAPTER 6
Counting
197
197
The Basics of Counting
The Pigeonhole Principle
206
Permutations and Combinations
Binomial Coefficients and Identities
Generalized Permutations and Combinations
Generating Permutations and Combinations
6.1
6.2
6.3
6.4
6.5
6.6
Guide to Review Questions for Chapter 6
Supplementary Exercises for Chapter 6
237
Writing Projects for Chapter 6
230
231
216
211
220
227
CHAPTER 7
Discrete Probability
239
242
An Introduction to Discrete Probability
Probability Theory
Bayes' Theorem
Expected Value and Variance
7.1
7.2
7.3
7.4
Guide to Review Questions for Chapter 7
Supplementary Exercises for Chapter 7
Writing Projects for Chapter 7
261
247
250
255
256
239
CHAPTER 8
Advanced Counting Techniques
262
262
272
Applications of Recurrence Relations
Solving Linear Recurrence Relations
Divide-and-Conquer Algorithms and Recurrence Relations
Generating Functions
Inclusion-Exclusion
Applications of Inclusion-Exclusion
8.1
8.2
8.3
8.4
8.5
8.6
Guide to Review Questions for Chapter 8
Supplementary Exercises for Chapter 8
Writing Projects for Chapter 8
310
304
305
286
298
300
282
CHAPTER 9
Relations
312
9.1
9.2
9.3
9.4
Relations and Their Properties
312
n-ary Relations and Their Applications
Representing Relations
Closures of Relations
322
325
320
Vl
Equivalence Relations
Partial Orderings
9.5
9.6
Guide to Review Questions for Chapter 9
Supplementary Exercises for Chapter 9
Writing Projects for Chapter 9
351
337
329
345
347
CHAPTER 10 Graphs
352
368
Graphs and Graph Models
Graph Terminology and Special Types of Graphs
Representing Graphs and Graph Isomorphism
Connectivity
Euler and Hamilton Paths
Shortest-Path Problems
Planar Graphs
Graph Coloring
10.1
10.2
10.3
10.4
10.5
10.6
10.7
10.8
Guide to Review Questions for Chapter 10
Supplementary Exercises for Chapter 10
Writing Projects for Chapter 10
401
385
389
375
381
CHAPTER 11
Trees
403
408
Introduction to Trees
Applications of Trees
417
Tree Traversal
421
Spanning Trees
Minimum Spanning Trees
11.1
11.2
11.3
11.4
11.5
427
Guide to Review Questions for Chapter 11
Supplementary Exercises for Chapter 11
434
Writing Projects for Chapter 11
CHAPTER 12
Boolean Algebra
436
Boolean Functions
Representing Boolean Functions
Logic Gates
Minimization of Circuits
12.1
12.2
12.3
12.4
Guide to Review Questions for Chapter 12
Supplementary Exercises for Chapter 12
Writing Projects for Chapter 12
456
443
445
CHAPTER 13 Modeling Computation
393
395
429
430
440
453
454
355
361
352
403
436
457
457
Languages and Grammars
Finite-State Machines with Output
Finite-State Machines with No Output
Language Recognition
Turing Machines
13.1
13.2
13.3
13.4
13.5
Guide to Review Questions for Chapter 13
Supplementary Exercises for Chapter 13
Writing Projects for Chapter 13
487
474
478
482
483
464
469
Vll
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
