《离散数学及其应用》（Discrete Mathematics and Its Applications）是经典的离散数学教材，为全球500多所大学广为采用作为指定教材。本书全面而系统地介绍了离散数学的理论和方法，内容涉及数学推理、组合分析、离散结构和算法设计。全书取材广泛，除包括定义、定理的严密陈述外，还配备大量的实例和图表的说明，各种练习和题目，以及丰富的历史资料和网站资源。本书适用于数学、计算机科学、计算机工程等专业的学生。
目录
- preface iv
- about theauthor xiii
- the companion website xiv
- to the studentxvi
- list of symbols xix
- 1 the foundations：logic and proofs
- 1．1 propositional logic
- 1．2 applications of propositional logic
- 1．3 propositional equivalences
- 1．4 predicates andquantifiers
- 1．5 nested quantifiers
- 1．6 rules of inference
- 1．7 introduction to proofs
- 1．8 proofmethods and strategy
- end-of-chaptermaterial-
- 2 basic structures：sets，functions，sequences，sums，andmatrices
- 2．1 sets
- 2．2 set operations
- 2．3 functions
- .2．4 sequences and summations
- 2．5 cardinality of sets
- 2．6 matrices
- end-of-chaptermaterial
- 3 algorithms
- 3．1 algorithms
- 3．2 the growth of functions
- 3．3 complexity of algofithms
- end-of-chapter material
- 4 number theory and cryptography
- 4．1 divisibilitv andmodular arithmetic
- 4．2 integer representations andalgorithms
- 4．3 primesand greatest common divisors
- 4．4 solving congruences
- 4．5 applications of congruences
- 4．6 cryptography
- end-of-chapter material
- 5 induction and recursion
- 5．1 mathematical induction
- 5．2 strong induction and well-ordering
- 5．3 recursive definitions and structural induction
- 5．4 recursive algorithms
- 5．5 program correctness
- end-of-chapter material
- 6 counting
- 6．1 tlle basics of counting
- 6．2 the pigeonhole principle
- 6．3 permutations and combinations
- 6．4 binomial coefficients and identities
- 6．5 generalized permutations and combinations
- 6．6 generating permutations and combinations
- end-of-chapter material
- 7 discrete probability
- 7．1 an introduction to discrete probability
- 7．2 probability theory
- 7．3 bayes’theorem
- 7．4 expected value and variance
- end-of-chapter material
- 8 advanced counring technigues
- 8．1 applications of recurrence relations
- 8．2 solving linear recurrence relations
- 8．3 divide-and-conquer algorithms and recurrencerelations
- 8．4 generating functions
- 8．5 inclusion-exclusion
- 8．6 applications of inclusion-exclusion
- end—of-chapter material
- 9 relations
- 9．1 relations and their properties
- 9．2 n-ary relations and theirapplications
- 9．3 representing relations
- 9．4 closures of relations
- 9．5 equivalence relations
- 9．6 partial orderings
- end-of-chapter material
- 10 graphs
- 10．1 graphs andgraphmodels
- 10．2 graph terminology and special types of graphs
- 10．3 representing graphs and graph isomorphism
- 10．4 connectivity
- 10．5 eulerandhamiltonpaths
- 10．6 shortest．pathproblems
- 10．7 planargraphs
- 10．8 graphcoloring
- end-of-chapter material
- 11 trees
- 11．1 introduction to trees
- 11．2 applications of trees
- 11．3 tree travcrsal
- 11．4 spanning trees
- 11．5 minimum spanning trees
- end-of-chapter material
- 12 boolean algebra
- 12．1 boolean functions
- 12．2 representing boolean functions
- 12．3 logic gates
- 12．4 minimization of circuits
- end-of-chapter material
- 13 modeling cornputation
- 13．1 languagesand grammars
- 13．2 finite-state machines with output
- 13．3 finite-state machines with no output
- 13．4 languagerecognition
- 13．5 turing machines
- end-of-chapter material
