本书特别关注与计算机科学密切相关的数学知识，既注重各部分内容之间的紧密联系，又注重理论、算法的实际应用。它首先介绍了基础知识，包括集合、序列、整数除法、矩阵、逻辑和计数等概念。接着描述了离散数学的主要知识体系，内容涉及集合论、数学结构、图论、关系、函数、格和布尔代数、树结构、图结构、半群和群等知识、包括整个体系的基础和多个分支。最后介绍了离散数学的应用，涉及形式语言和有限状态机、群和编码。

本书内容丰富、具体、结构清晰、注重实用。它既适用于高等院校计算机及相关专业的本科生和研究生的学习，又可作为工程技术人员的参考书。

2002年，中国计算机学会、全国高校计算机教育研究会、清华大学出版社共同组织专家和教授，提出了《中国计算机科学与技术学科教程2002》。该教程主要参考了IEEE和ACM推出的"Computing Curricula 2001"，提出了计算机学科的教学计划，包括课程设置、课程结构、课时内容、实验学时等内容。该教程把数学方法作为计算机学科的学科方法之一，要求用数学语言表示事物的状态、关系和过程，建立抽象而严谨的数学模型，通过推导进行解释和判断。

计算机学科的基础理论主要包括数学分析、高等代数、数值分析、概率与统计、集合与图论、近世代数、数理逻辑、形式语言与自动机、数学建模等。这些基础理论可以分为三部分：连续数学、离散数学、计算模型。连续数学部分的代表是数学分析，加之高等代数、概率与统计，这些都是公共基础理论，是所有理工学科的公共基础课。连续数学为物理学等众多学科提供了建模的数学工具，但是不能直接用于建模计算机内部的数据、功能和过程。计算模型部分包括数值分析和数学建模。它将连续数学模型与计算数学模型联系起来，为用计算机解决实际问题建起了桥梁。离散数学部分提供了在计算机内部建立数学模型的数学工具，包括集合论与图论、近世代数、数理逻辑、形式语言与自动机等分支。

由此可见，离散数学在计算机学科基础理论中占有重要地位。它的特点之一是实用性。离散数学是一门数学，但是作为计算机学科的一门基础课程，目的十分明确，就是应用于计算机领域。不仅用于计算机内部的数据，还用于算法和过程，用于系统结构，用于通信和网络；不仅用于硬件系统，还用于软件系统。因此，理论与实践的结合，是离散数学教学中的重点之一。它的另一个特点是综合性。离散数学包括多个彼此独立的数学分支，它们的知识点具有或多或少的联系，但是又自成体系。有机地组合这些数学知识，成为合理、完善的体系，这是离散数学课程在内容组织编排上的要点。课程内容的合理编排必定有助于教师的教学和学生的学习。

近年来，教育主管部门推荐了一批信息领域的英文原版教材，这些教材为我国相关学科的教材建设，提供了很好的参考和借鉴。其中有的教材包括了计算机学科需要的离散数学结构知识，并对多个数学分支的知识进行合理的组织。《中国计算机科学与技术学科教程2002》中，离散数学相关知识领域的名称也是“离散结构”。用这个名称代替常用的“离散数学”，自有一番用意。这或许表示，该课程不是注重数学知识的系统、完整、严谨，而是注重离散结构需要的数学，也就是计算机需要的数学。离散结构不仅涉及计算机中的数据结构，也涉及算法和程序结构、系统体系结构、通信系统和网络结构。随着信息技术的快速发展，这门课程的内容也在发展和更新。

上述背景知识是本教材编写的基础。本教材编著的基本思想是选取计算机学科需要的离散数学结构知识，并进行合理的组织。同时，本教材关注这些知识在计算机学科中的应用，注重理论与实践的结合。

本书采用了以关系和有向图为核心的知识体系。书中打破了集合论和图论的界限，把这两部分组合在一起，希望便于学生理解相关的知识。在关系和有向图的基础上，本书主要介绍了函数、偏序和格、无向图和树、代数结构等知识。本书在内容的组织上也打破了数学分支的界限，最有代表性的是偏序和格。偏序是一种关系，属于集合论。格和布尔代数是一种代数结构。本书在同一章内介绍这两方面内容，加强了两者的联系，学生更容易理解和掌握。此外，第2章加强了对数学归纳法等证明方法的介绍。计数知识是计算机领域的常用知识，本书将相关知识组织在同一章内，包括叠加原理、组合学基础、概率基础以及递归关系。如果教学计划中包括专门的概率与统计课程，教学内容可以省略概率部分。组合学一般安排为研究生课程，因此在本科教学中介绍组合学基础是必要的。本书在这方面介绍了排列和组合以及鸽巢原理。在第5章还专门介绍了排列函数。本书的第1章是全书的基础。

本书注重理论和实际的结合，提供了与计算机学科相关的大量例子和练习。同时，一些章节专门介绍理论知识的应用。第2章中，将数学归纳法应用于程序正确性的验证。第4章中专门介绍了关系和有向图在计算机中的表示，并举例比较了不同表示法的计算量。第5章中集中介绍了计算机中的函数表示，并以函数增长为题，介绍了计算复杂性的基础知识。第6章以布尔代数为工具讨论了逻辑电路的设计。第8章介绍了有应用价值的运输网问题。第10章介绍了半群在语言和自动机中的应用，第11章介绍群在通信编码和解码领域的应用。

本书的基本内容为前9章，预计学时约为100小时。后两章可以作为选修内容，预计学时20小时。

编者

王家廞

第1章  基础知识

1.1  集合与子集

1.2  序列

1.3  整数的除法

1.4  矩阵

1.5  数学结构

第2章  逻辑

2.1  命题和逻辑运算

2.2  条件命题

2.3  证明方法

2.4  数学归纳法

第3章  计数

3.1  叠加原理

3.2  排列

3.3  组合

3.4  鸽巢原理

3.5  概率基础

3.6  递归关系

第4章  关系

4.1  乘积集合

4.2  关系和有向图

4.3  关系和有向图中的路径

4.4  关系的性质

4.5  等价关系

4.6  关系的计算机表示

4.7  关系的运算

4.8  闭包 

第5章  函数

5.1  函数

5.2  计算机科学中的函数

5.3  函数的增长

5.4  排列函数

第6章  序关系和结构

6.1  偏序集合

6.2  偏序集合的极值元素

6.3  格

6.4  有限布尔代数

6.5  布尔代数上的函数

6.6  电路设计

第7章  树

7.1  树

7.2  标记树

7.3  树搜索

7.4  无向树

7.5  最小生成树

第8章  图论

8.1  图

8.2  欧拉路径和回路

8.3  哈密尔顿路径及回路

8.4  运输网

8.5  图着色

第9章  半群和群

9.1  二元运算回顾

9.2  半群

9.3  半群的积和商

9.4  群

9.5  群的积和商

第10章  语言和有限状态机器

10.1  语言

10.2  语法和语言的表示

10.3  有限状态机器

10.4  半群，机器和语言

10.5  机器和正则语言

10.6  机器简化

第11章  群和编码

11.1  二进编码和错误检测

11.2  解码和纠错  

附录1 符号

附录2 术语