离散数学及其应用

Prefacefii

AbouttheAuthorxiv

TotheStudentxv

LISTOFSYMBOLSxviii

1TheFoundations:LogicandProofs

1.1PropositionalLogic

1.2PropositionalEquivalences

1.3PredicatesandQuantifiers

1.4NestedQuantifiers

1.5Rulesoflnference

1.6IntroductiontoProofs

1.7ProofMethodsandStrategy

End-of-ChapterMaterial

2BasicStructures:Sets,Functions,Sequences,andSums

2.1Sets

2.2SetOperations

2.3Functions

2.4SequencesandSummations

End-of-ChapterMaterial

3TheFundamentals:Algorithms,theIntegers,andMatrices

3.1Algorithms

3.2TheGrowthofFunctions

3.3ComplexityofAlgorithms

3.4TheIntegersandDivision

3.5PrimesandGreatestCommonDivisors

3.6IntegersandAlgorithms

3.7ApplicationsofNumberTheory

3.8Matrices

End-of-ChapterMaterial

4InductionandRecursion

4.1MathematicalInduction

4.2StrongInductionandWell-Ordering

4.3RecursiveDefinitionsandStructuralInduction

4.4RecursiveAlgorithms

4.5ProgramCorrectness

End-of-ChapterMaterial

5Counting

5.1TheBasicsofCounting

5.2ThePigeonholePrinciple

5.3PermutationsandCombinations

5.4BinomialCoefficients

5.5GeneralizedPermutationsandCombinations

5.6GeneratingPermutationsandCombinations

End-of-ChapterMaterial

6DiscreteProbability

6.1AnIntroductiontoDiscreteProbability

6.2ProbabilityTheory

6.3BayesTheorem

6.4ExpectedValueandVariance

End-of-ChapterMaterial

7AdvancedCountingTechniques

7.1RecurrenceRelations

7.2SolvingLinearRecurrenceRelations

7.3Divide-and-ConquerAlgorithmsandRecurrenceRelations

7.4GeneratingFunctions

7.5Inclusion-Exclusion

7.6ApplicationsofInclusion-Exclusion

End-of-ChapterMaterial

8Relations

8.1RelationsandTheirProperties

8.2n-aryRelationsandTheirApplications

8.3RepresentingRelations

8.4ClosuresofRelations

8.5EquivalenceRelations

8.6PartialOrderings

End-of-ChapterMaterial

9Graphs

9.1GraphsandGraphModels

9.2GraphTerminologyandSpecialTypesofGraphs

9.3RepresentingGraphsandGraphIsomorphism

9.4Connectivity

9.5EulerandHamiltonPaths

9.6Shortest-PathProblems

9.7PlanarGraphs

9.8GraphColoring

End-of-ChapterMaterial

10Trees

10.1IntroductiontoTrees

10.2ApplicationsofTrees

10.3TreeTraversal

10.4SpanningTrees

10.5MinimumSpanningTrees

End-of-ChapterMaterial

11BooleanAlgebra

11.1BooleanFunctions

11.2RepresentingBooleanFunctions

11.3LogicGates

11.4MinimizationofCircuits

End-of-ChapterMaterial

12ModelingComputation

12.1LanguagesandGrammars

12.2Finite-StateMachineswithOutput

12.3Finite-StateMachineswithNoOutput

12.4LanguageRecognition

12.5TuringMachines

End-of-ChapterMaterial

Appendixes

A-1AxiomsfortheRealNumbersandthePositiveIntegers

A-2ExponentialandLogarithmicFunctions

A-3Pseudocode

SuggestedReadingsB-1

AnswerstoOdd-NumberedExercises@S-1

IndexofBiographiesI-1

IndexI-2

　　本书是介绍离散数学理论和方法的经典教材，已经成为采用率最高的离散数学教材。仅在美国就被600多所高校用作教材，获得了极大的成功。中文版也已被国内大学广泛采用为教材。第6版在前五版的基础上做了大量的改进，使其成为更有效的教学工具。本书可作为1至2个学期的离散数学课入门教材，适用于数学、计算机科学、计算机工程、信息技术等专业的学生。【作者简介】　　KennethH．Rosen1972年获密歇根大学数学学士学位，1976年获麻省理工学院数学博士学位，1982年加入贝尔实验室，现为AT＆T实验室特别成员，国际知名的计算机数学专家，除本书外，还著有《初等数论及其应用》等书。