离散数学（第七版）（英文版）

书名：
作者：
ISBN号：

《现代交换原理与技术（第2版）》

《Pro/ENGINEER机械设计与制造》

《数字与模拟通信系统（第七版）（英文版）》

《应用统计学》

《芯片制造——半导体工艺制程实用教程（第五版）》

《离散数学（第七版）（英文版）》

点击此处查看完整封面	著者：	Richard Johnsonbaugh sr
	作译者：
	ISBN号：	978-7-121-08534-5
	出版日期：	2009-04
	丛书名：	国外计算机教材系列
	字数：1267千字		定价：￥79.00元
	页码：792		会员价：￥63.20元
	开本：16		放入购物篮
	库存：有

内容简介

　　本书从算法分析和问题求解的角度，全面系统地介绍了离散数学的基础概念及相关知识，并在其前一版的基础上进行了修改与扩展。书中通过大量实例，深入浅出地讲解了数理逻辑、组合算法、图论、布尔代数、网络模型、形式语言与自动机理论等与计算机科学密切相关的前沿课题，既着重于各部分内容之间的紧密联系，又深入探讨了相关的概念、理论、算法和实际应用。本书内容叙述严谨、推演详尽，各章配有相当数量的习题与书后的提示和答案，为读者迅速掌握相关知识提供了有效的帮助。

图书目录

Preface 
1 Sets and Logic 
1.1 Sets 
1.2 Propositions 
1.3 Conditional Proposition sand Logical Equivalence 
1.4 Argument sand Rules of Inference 
1.5 Quantifiers 
1. 6 Nested Quantifiers 
Problem-Solving Corner: Quantifiers 
Notes 
Chapter Review 
Chapter Self-Test 
Computer Exercises 
2 Proofs 
2.1 Mathematical Systems, Direct Proofs, and Counterexamples 
2.2 More Methods of Proof 
Problem-Solving Corner: Proving Some Properties of Real Numbers 
2.3 Resolution Proofs 
2.4 Mathematical Induction 
Problem-Solving Corner: Mathematical Induction 
2.5StrongFormofInductionandtheWell-OrderingProperty 
Notes 
Chapter Review 
Chapter Self-Test 
Computer Exercises 
3Functions, Sequences, and Relations 
3.1Functions 
Problem-Solving Corner: Functions 
3.2SequencesandStrings 
3.3Relations 
3.4EquivalenceRelations 
Problem-Solving Corner: Equivalence Relations 
3.5 Matrices of Relations 
3.6 Relational Databases 
Notes 
Chapter Review 
Chapter Self-Test 
Computer Exercises 
4Algorithms 
4.1Introduction 
4.2ExamplesofAlgorithms 
4.3AnalysisofAlgorithms 
Problem-Solving Corner: Design and Analysis o fan Algorithm 
4.4RecursiveAlgorithms 
Notes 
Chapter Review 
Chapter Self-Test 
Computer Exercises 
5IntroductiontoNumberTheory 
5.1Divisors 
5.2RepresentationsofIntegersandIntegerAlgorithms 
5.3TheEuclideanAlgorithm 
Problem-Solving Corner: Making Postage 
5.4 The RSA Public-Key Cryp to system 
Notes 
Chapter Review 
Chapter Self-Test 
Computer Exercises 
6CountingMethodsandthePigeonholePrinciple 
6.1 BasicPrinciples265 
Problem-Solving Corner: Counting 
6.2 Permutations and Combinations 
Problem-Solving Crner:Combinations  
6.3 Generalized Permutations and Combinations 
6.4 Algorithms for Generating Permutations and Combinations  
6.5 Introduction to Discrete Probability 
6.6 Discrete Probability Theory 
6.7 Binomial Coefficients and Combinatorial Identities 6.8 The Pigeonhole Principle 
Notes 
7 Recurrence Relations 
8 Graph Theory 
9 Trees 
10 Network Models 
11Boolean Algebras and Combinatorial Circuits 
12 Automata, Grammars, and languages 
13 Computational Geometry 
A  Matrices 
B  Algebra Review 
C  Pseudo code 
References 
Hint sand Solutions to Selected Exercises 
Index

序言/前言

前    言

This updated edition is intended for a one-or two-term introductory course in discrete mathematics，based on my experience in teaching this course over many years and requests from users of previous editions.Formal mathematics prerequisites are minimal；calculus is not required.There are no computer science prerequisites.The book includes examples，exercises，figures，tables，sections On problem—solving，sections containing problem—solving tips，section reviews，notes，chapter reviews，self-tests，and computer exercises to help the reader master introductory discrete mathematics.In addition，an Instructor’s Guide and website are available.
    In the early 1980s there were few textbooks appropriate for an introductory course in discrete mathematics.However，there was a need for a course that extended students，mathematical maturity and ability to deal with abstraction.which also included useful topic s such as combinatoric s，algorithms，and graphs.The original edition of thi s book(1984)addressed this need and significantly influenced the development of discrete mathematics courses.Subsequently，discrete mathematics courses were endorsed by many groups for several difierent audiences.including mathematics and computer science majors.A panel of the Mathematical As sociation of America(MAA)endorsed a year—long course in discrete mathematics.The Educational Activities Board of the Institute of Electrical and Electronics Engineers(IEEE)recommended a freshman discrete mathematic s course.The As sociation for Computing Machinery(ACM)and IEEE accreditation guidelines mandated a discrete mathematics course.This edition，like its predecessors，includes topics such as algorithms，combinatorics，sets，functions，and mathematicalinduction endorsed by these groups.It also addresses understanding and constructing proofs and，generally，expanding mathematical maturity.
Logic and Proofs Changes
The changes in this book，the seventh edition，result from comments and requests from numerous users and reviewers of previous editions of the book.The biggest change from the sixth to the seventh edition occurs in Chapters 1-3.The first chapter in the sixth edition，Logic and Proofs，has been divided into two chapters in the seventh edition：
Sets and Logic(Chapter 1)and Proofs(Chapter 2).Except for the section on sets，Chapters 2(The Language of Mathematics)and 3(Relations)in the sixth edition have been combined into Chapter 3(Functions，Sequences，and Relations)in the seventh edition.Pre—publication reviews have been very enthusiastic about these changes.
    The section on sets i s now the first section of the book.Thi s change permits the use of set terminology throughout the book.It makes sets available for proofs in examples and exercises，thus providing more interesting examples earlier than in the previous editions.We can even use sets to introduce proofs(e og.，proving that two sets are equal，proving that one set is a subset of another)before fully discussing proofs and proof techniques.
    The discussion about how to construct proofs has been greatly expanded.Sections 2.1 and 2.2 are new extended sections on mathematical systems and proof techniques.In addition.there are expanded subsections on proofs of equivalence and existence proofs(including constructive and nonconstructive existence proofs).Nearly every proof is preceded by a Discussion section and/or accompanied by a figure.The Problem-Solving Tips sections include expanded advice，examples，and so on，on how to do proofs，how to write up proofs，and common errors in proofs.There are two new Problem—Solving Corners，one on quantifiers，the other on proofs(see Proving SomeProperties of Real Numbers).
    The discussion of arguments and rules of inference for propositions has been moved to fol low the discussion of propositions.The rules of inference for quantified statements are integrated within the quantifiers section.
    The number of examples and exercises has been vastly expanded.In the sixth edition.there were approximately 1370 worked examples and exercises in the first three chapters.In the seventh edition.there are approximately 1 640 worked example s and exercises in the first three chapters.Of course，not j ust the quantity of examples and exercises is important.it is also the quality.In most of the examples found in the sixth edition.the discussion has been expanded and additional motivation has been added.
Other Changes from the Sixth Edition 
Other changes from the sixth edition are as follows：
-The description and notation for integers(Z，Z+，Z-，Z)，rational numbers (with Z replaced by Q)，and real numbers(with Z replaced by R)are introduced early(in Section 1.1，Sets).
-Proofs.rather than sketches of proofs as in the sixth edition，are provided for Theorems 5.1.17 and 5.1.22 which give the greatest common divisor and least common multiple of two integers given their prime factorizations.
-Recursive algorithms are given(Algorithms 5.3.9 and 5.3.10)to compute the greatest common divisor of two integers a and b，gcd(a，b)，and to compute integers and satisfying gcd(a，b)=sa+tb.
-The Inclusion—Exclusion Principle has been added to Section 6.1.
-Internet addressing is now included in Section 6.1.
-Several practice exercises have been added to Section 6.1 that specifically say to use either the Multiplication Principle or the Addition Principle.These exercises precede other exercises that require the reader to figure out which Principle to use or require using both Principles.
-The section on Generalized Permutations and Combinations(Section 6.6 in the sixth edition)now follows Sections 6.1 and 6.2(B asic Principles，Permutations and Combinations)since generalized permutations and combinations are so closely related to the material in Sections 6.1 and 6.2.
-Several relatively straightforward “warm—up” exercises have been added before the main pigeonhole exercises(Section 6.8).
-More exercises on graph isomorphism have been added(Section 8.6).The exercises have been divided into those that ask for a proof that two given graphs are isomorphic，those that ask for a proof that two given graphs are not isomorphic，and those that ask the reader to determine，with a proof,whether two given graphs are isomorphic.
-In Section 9.3，there are several new backtracking exercises including the popular Sudoku puzzle.
-More examples and exercises are included to highlight common errors(for example，the subsection Some Common Errors that precedes the Section 2.1 Review Exercises discusses some common errors in proofs.and Example 6.2.24 illustrates a common counting error).
-A number of recent books and articles have been added to the list of references. Several book references have been updated to current editions.
-The number of worked examples has been increased to over 650.(There were approximately 600 in the sixth edition.)
_The number of exercises has been increased to nearly 4200.(There were approximately 4000 in the sixth edition.)
Contents and Structure
This book includes
-Sets and logic(including quantifiers).Practical examples such as using the Google search engine are included(Example 1.2.1 3).Translating between Engli sh and symbolic expressions is discussed as is logic in programming languages.A logic game，which of.fers an alternative way to determine whether a quantified propositional function is true or false.is discussed in Example 1.6.1 5.
-Proofs(Chapter 2).Proof techniques discussed include direct proofs.counter examples，proof by contradiction，proof by contrapositive，proofs by cases，proofs of equivalence，existence proofs(constructive and nonconstructive)，and mathematical induction.Loop invariants are presented as a practl。cal application of mathematical induction.We also include a brief.optional section on resolution proofs(a proof technique that can be automated).
-Functions，sequences，sum and product notations，strings，and relations(Chapter 3)，including motivating examples such as the new 1-3 character international standard book number(ISBN)，an introduction to hash functions，and pseudo random number generators(S ection 3.1)：an application of partial orders to task scheduling(Section 3.3)：and relational databases(Section 3.6).
-A thorough discussion of algorithms，recursive algorithms，and the analysis of algorithms(Chapter 4).A number of examples of algorithms are presented before getting into big—oh and related notations(Sections 4.1 and 4.2)，thus providin a gentle introduction and motivating the formalism that follows.An algorithmic approach i s taken throughout thi s book.W-e mention that many modern algorithms do not have all the properties of clas sical algorithms(e o g.，many modern algorithms are not general，deterministic，or even finite).To illustrate the point，an example is given of a randomized algorithm(Example 4.2.4).The algorithms are written in a flexible form of pseudocode.which resembles currently popular languages such as C，C++，and Java.(The book does not assume any computer science prereq u1 SlteS；the description or-the pseudocode used is given 1n Appendix C.) Among the algorithms presented are tiling(Section 4.4)，the Euclidean algorithm for finding the greatest common divisor(Section 5.3)，the RSA public—key encryption algorithm(Section 5.4)，generating combinations and permutations(Section 6.4)，merge sort(Section 7.3)，Dijkstra’s shortest—path algorithm(Section 8.4)，backtracking algorithms(Section 9.3)，breadth—first and depth—first search(Section 9.3)，tree traversals(Section 9.6)，evaluating a game tree(Section 9.9)，finding a maximal flow in a network(Section 10.2)，finding a closest pair of points(Section 13.1)，and computing the convex hull(Section 132).
-A full discussion of the“big oh，”omega，and theta notations for the growth of functions(Section 4.3).Having all of these notations available makes it possible to make precise statements about the growth of functions and the time and space required by algorithms.
-An introduction to number theory(Chapter 5).This chapter includes clas sical results(e.g.，divi sibility，the infinitude of primes，fundamental theorem of arithmetic)，as well as algorithmic number theory(e.g.，the Euclidean algorithm to find the greatest common divi sor，exponenti ation using repeated squaring，computings and于such that gcd(a，b)=sa+tb，computing an inverse modulo an integer).The major application is the RSA public—key cryptosystem(Section 5.4).The calculations required by the RSA public--key cryptosystem can be performed using the algorithms previously developed in the chapter.
_Combinations，permutations，discrete probability，and the Pigeonhole Principle(Chapter 6).Two optional sections(Sections 6.5 and 6.6)treat discrete probability.
_Recurrence relations and their use in the analysis of algorithms(Chapter 7).
_Graphs，including coverage of graph models of parallel computers，the knight’s tour，Hamiltonian cycles，graph isomorphisms，and planar graphs(Chapter 8).Theorem 8.4.3 gives a simple，short，elegant proof of the correctness of Dijkstra，salgorithm.
_Trees，including binary trees，tree traversals，minimal spanning trees，deci sion trees，the minimum time for sorting，and tree isomorphisms(Chapter 9).Networks，the maximal flow algorithm，and matching(Chapter 1 0).
_A treatment of B oolean algebras that emphasizes the relation of B oolean algebras to combinatorial circuits(Chapter 11).
_An approach to automata emphasizing modeling and applications(Chapter 1 2). The SR flip—flop circuit is discussed in Example 1 2.1.11.Fractals.including the vonKoch snowflake，are described by special kinds of grammars(Example 1 2.3.1 9).
_An introduction to computational geometry(Chapter 1 3).
_Appendixes on matrices，basic algebra，and pseudocode.
-A strong emphasis on the interplay among the various topics.As examples.mathematical induction is closely tied to recursive algorithms(Section 4.4)；the Fibonacci sequence is used in the analysis of the Euclidean algorithm(Section 5.3)；many exercises throughout the book req uire mathemati cal induction；we show how tocharacterize the components of a graph by defining an equivalence relation on the set of vertices(see the discussion following Example 8.2.1 3)；and we count the number of nonisomorphic vertex binary trees(Theorem 9.8.1 2).
-A strong emphasis On reading and doing proofs.Most proofs of theorems are illustrated with annotated figures and／or motivated by special Discussion sections.Separate sections(Problem—Solving Corners)show students how to attack and solve problems and how to do proofs.Special end—of-section Problem—Solving Tips hi ghlight the mai n problem—solving techniques of the section.
-A large number of applications.especially applications to computer science.
-Figures and tables to illustrate concepts，to show how algorithms work，to elucidate proofs.and to motivate the material.Several figures illustrate proofs of theorems. The captions of these figures provide additional explanation and insight into the proofs.
-Section review exercises．
-Notes sections with suggestions for further reading．
-Chapter reviews．
-Chapter self-tests．
-Computer exercises．
-A reference secti on containing more than 160 references．
-Front and back endpapers that summarize the mathematical and algorithm notation used in the book．
Each chapter is organized as follow s：
Overview
Section
Section Review Exerci ses
Section Exerci ses
Section
Section Review Exercises
Section Exercises
Notes
Chapter Review
Chapter Self-Test
Computer Exercises
  Acknowledgemengts

I received helpful comments from many persons，including Gary Andrus，Kendall Atkinson，Greg Bachelis，André Berthiaume，Gregory Brewster，Robert Busby，David G.Cantor，Tim Carroll，Joseph R Chan，Hon.Wing Cheng，I-Ping Chu，Robert Crawford，Henry D，Angelo，Jerry Delazzer，B r.Michael Driscoll，Carl E.Eckberg，HerbertEnderton，Susanna Epp，Bob Fisher,Brendan Frey，Dennis Garity，Gerald Gordon，JerroldGrossman，Reino Hakala，Mark Herbster，Craig Jensen，Steve Jost，Martin Kalin，Aaron Keen，NicholasⅫer，Warren Krueger,Glenn Lancaster，Miguel Lerma，Donald E.G.Maim，Nick Meshes，TmC Nguyen，Suely Oliveira，Kevin Phelps，Jenni Piane，Randall Pruim，Mansur Samadzadeh，Sigrid(Anne)Settle，David Stewart，James H.Stoddard，Chaim Goodman Strauss，Bogdan Suceava，Michael Sullivan，Edward J.Williams，Anthony S.Woj cik，and Hanyi Zhang.Thanks also to aU of the users of my book
for their helpful letters and e—mail.
    Special thanks for this edition go to Greg Brewster，my DePaul colleague，for consulting about Internet addressing.
    For reviewing the manuscript for this edition，thanks go to Scott Annin，Califomia State University，Fullerton；Natacha Fontes—Merz，W.estminster College；Ronald I.Greenberg，Loyola University；John Greiner，Rice University；Eitan Grinspun，Columbia University；Wu Jing.Fayetteville State University；Harold Reiter,UNC Charlotte；and Christopher N.Swanson，Ashland University.
    I am grateful to my friendly copy editor，Patricia Johnsonbaugh，for her careful reading of the entire manuscript，improving the exposition，catching miscues 1 wrote but should not have，and help with the index.
    I have received consistent support from the staff at Prentice Hall.Special thanks flor their help go to Dee Bernhard，Associate Editor；Scott Disanno，Senior Managing Editor；Marcia Horton，Editorial Director；Jennifer Lonschein，Editorial Assistant；Holly Stark，Senior Editor：；and Irwin Zucker，Production Editor.

Richard Johnsonbaugh

读者书评

欢迎您对我社的图书发表您的高见！