本书三位作者都曾获得美国著名大学数学系博士学位，在美国Drexel大学和Georgia Permeter学院执教多年，是数学界和计算机科学界享有很高声望的教授。他们不仅在数学方面，如数值分析、离散数学、李代数、概率论等领域有很高的学术造诣和丰富的教学经验，而且在计算机应用方面也有很高的水平，编写过许多数学与计算机应用方面的教材。

本书选材广泛且适当，覆盖面广，叙述深入浅出，推理严谨，习题丰富，书中许多例子将数学与计算机应用融为一体。正因如此，本书被译成多种语言，在世界各国广为流传。

Preface   viii

        VIII

A Word to Students xii

1 Fundamentals  1

   1.1  Sets and Subsets  2

   1.2  Operations on Sets  5

   1.3  Sequences  13

   1.4  Division in the Integers  20

   1.5  Matrices  32

   1.6  Mathematical Structures  41

2 Logic 50

   2.1  Propositions and Logical Operations  51

   2.2  Conditional Statements  57

   2.3  Methods of Proof  62

   2.4  Mathematical Induction  67

    Counting  78

   3.1  Permutations  79

   3.2  Combinations  83

   3.3  Pigeonhole Principle  88

   3.4 Elements of Probability  91

   3.5  Recurrence Relations  100

4 Relations and Digraphs 110

   4.1  Product Sets and Partitions  111

   4.2  Relations and Digraphs  115

   4.3  Paths in Relations and Digraphs  123

   4.4  Properties of Relations  129

   4.5  Equivalence Relations  136

   4.6  Computer Representation of Relations and Digraphs  140

   4.7  Operations on Relations  147

   4.8  Transitive Closure and Warshall's Algorithm  157

5 Functions 168

   5.1  Functions  169

   5.2  Functions for Computer Science  178

   5.3  Growth of Functions  183

   5.4  Permutation Functions  188

6 Order Relations and Structures  200

   6.1  Partially Ordered Sets  201

   6.2  Extremal Elements of Partially Ordered Sets  211

   6.3  Lattices  216

   6.4 Finite Boolean Algebras  226

   6.5  Functions on Boolean Algebras  233

   6.6 Circuit Design  237

7 Trees  254

   7.1  Trees  254

   7.2  Labeled Trees  259

   7.3  Tree Searching  264

   7.4  Undirected Trees  273

   7.5  Minimal Spanning Trees  280

8 Topics in Graph Theory  290

   8.1  Graphs  291

   8.2  Euler Paths and Circuits  296

   8.3  Hamiltonian Paths and Circuits  304

   8.4  Transport Networks  307

   8.5  Matching Problems  315

   8.6  Coloring Graphs  320

9 Semigroups and Groups  329

   9.1  Binary Operations Revisited 330

   9.2  Semigroups  334

   9.3  Products and Quotients of Semigroups  341

   9.4  Groups  347

   9.5  Products and Quotients of Groups  358

   9.6  Other Mathematical Structures 363

10 Languages and Finite-State Machines 372

   10.1  Languages  373

   10.2  Representations of Special Grammars and Languages  381

   10.3  Finite-State Machines  390

   10.4  Monoids, Machines, and Languages  396

   10.5  Machines and Regular Languages  401

   10.6  Simplification of Machines  407

11 Groups and Coding 416

   11.1  Coding of Binary Information and Error Detection  417

   11.2 Decoding and Error Correction  428

   11.3  Public Key Cryptology  436

Appendix A: Algorithms and Pseudocode  443

Appendix B: Additional Experiments in

       Discrete Mathematics  454

Answers to Odd-Numbered Exercises  459

Answers to Chapter Self-Tests  497

Glossary  G-1

Index  I-1

Photo Credits  P-1