本书共分 12章，内容包含矩阵知识初步、组合数学与数论初步、命题逻辑、谓词逻辑、集合论基础、关系、特殊关系、图论基础、特殊图、代数系统、群论和其他代数系统。本书以训练学生的思维能力为核心，以培养计算机类专业的应用型人才为目的，将计算机数学与算法设计进行有效结合，全面提高学生的程序设计能力和应用创新能力。通过对典型的例题进行分析，培养学生分析问题和解决问题的能力。同时，对一些内容进行延伸，将计算机数学基础与后续的专业知识进行完美结合。

    本书可以作为数学类、计算机类的本科教材，也可以作为程序设计大赛培训的参考用书。

离散数学是现代数学的一个重要分支，是计算机科学与技术的重要理论基础。 1977年，离散数学被 IEEE确定为计算机专业核心主干课程，2004年在计算机 5个相关专业的培养计划中，离散数学是计算机工程（Computer Engineering，CE）、计算机科学（Computer Science，CS）和系统工程（ System Engineering，SE）3个专业的重要核心课程。作为数据结构、编译原理、数据库原理、操作系统、人工智能等专业课程的前导课程，离散数学不仅需要提供必要的基础知识，更重要的是通过离散数学的学习，培养学生的抽象思维能力和逻辑思维能力，进一步强化学生的程序设计能力。

对于学生而言，单纯的理论知识是枯燥的。因此，增加必要的工程应用，与后续的专业课程进行有效衔接，将提高学生的学习兴趣。在设计具体内容时，本教材借鉴了目前主流教材的特点，除必要的基础知识外，增加了相关知识点的工程应用，突出离散数学在程序设计、算法分析以及相关专业课程中的应用。 

1. 特点 

1）针对性强，适用范围广

本书针对单学期、短学时的离散数学或计算机数学课程而设计，除必要的基础知识外，增加了学习本课程所需要的矩阵基础知识、组合数学以及数论基础知识。本教材适合高等学校计算机类、数学类等专业的学生使用。 

2）授之以渔，注重对解题方法和解题思路的培养

本书针对每一个例题，在给出完整的解题过程之前，尽可能给出详细的分析过程和必要的证明思路。通过对例题的分析，注重对学生解题方法和解题思路的培养，达到“授之以渔”的目的。 

3）注重数学的工程应用，培养学生的程序设计思维

本书在设计教学内容时，注重知识点在程序设计、算法分析以及后续专业课程中的应用，让学生了解知识点的应用价值。同时，选取了程序设计大赛中的典型赛题，基于相关的知识点对赛题进行分析，设计巧妙的程序。 

2. 内容安排

第 1章矩阵知识初步。对本书中需要的矩阵知识进行简要的介绍，包括矩阵的基本概念、矩阵的运算以及布尔矩阵等。

第 2章组合数学与数论初步。对组合数学及数论的基本知识进行介绍，包括基本计数原则、排列组合、鸽笼原理、素数、最大公约数与最小公倍数、数的进制转换等。

第 3章命题逻辑。对命题逻辑的相关知识进行介绍，包括命题及命题联结词、命题公式、命题公式的等值演算、联结词的完备集、命题公式的范式、命题逻辑的推理等。

第 4章谓词逻辑。对谓词逻辑的相关知识进行介绍，包括谓词逻辑的基本知识、谓词公式的等价及蕴含、谓词逻辑的推理等。

第 5章集合论基础。对集合论的基础知识进行介绍，包括集合的基本表示、集合的基本运算、容斥原理等。

第 6章关系。对关系的相关知识进行介绍，包括关系的定义与表示、关系的运算、关系的性质等。

第 7章特殊关系。介绍了 3类特殊的关系：等价关系、偏序关系和函数。

第 8章图论基础。对图论的基础知识进行介绍，包括图论的基本概念、通路与回路、无向图和有向图的连通性等。

第 9章特殊图。介绍 3种常用的图：欧拉图、汉密尔顿图、树。

第 10章代数系统。对代数系统的基本概念进行介绍，包括运算与代数系统的基本定义、运算的性质及特殊元素、代数系统的同态、代数系统与子代数系统等。

第 11章群论。对半群、独异点、群的基本概念进行介绍，此外，对置换群、循环群、正规子群等也进行了介绍。

第 12章其他代数系统。介绍了环、域、布尔代数等其他代数系统。

本书具体编写分工如下：第 1章、第 7章由李秀芳编写，第 8章、第 9章由杨洪勇编写，第 10章、第 12章由赵永升编写，其余章节由张小峰编写，全书的策划和定稿工作由张小峰负责。

作为鲁东大学软件工程专业、计算机科学与技术专业应用型人才培养的系列教材之一，本书曾作为校内讲义在校内多次印刷，在软件工程、计算机科学与技术、网络工程、信息管理与信息系统等专业中使用。在清华大学出版社正式出版之际，在原讲义的基础上，结合多年的教学实践与改革，进行了较大的修改，使其既能适合在校学生学习，又能适合其他读者阅读。

在本书的规划和写作过程中，山东大学张彩明教授、西安电子科技大学李兴华教授、鲁东大学邹海林教授等对书稿进行了审阅，提出许多建设性的建议，在此深表感谢。清华大学出版社的广大员工也为教材的出版付出了大量的心血，使本书得以及时出版，在此一并致以衷心的感谢。

在本书编写的过程中，作者参考了国内外诸多版本的《离散数学》、《计算机数学基础》等相关教材，同时参考了相关计算机程序设计大赛的相关资料，这里不再一一列举，在此一并感谢。

限于作者学识水平，教材在内容的取舍、教学体系的设计、知识点的构造、程序设计思想的培养等方面肯定存在不足之处，恳请专家、同行和读者提出批评指正。

作者 

2015年 9月于烟台

第 1章矩阵知识初步 /1 

  1.0本章导引  /1

  1.1矩阵的概念  /1

  1.2矩阵的运算  /3

  1.3布尔矩阵  /5习题 1 /6 第 2章组合数学与数论初步  /7

  2.0本章导引  /7

  2.1基本计数原则 /7 

2.1.1  加法原则  /7 

2.1.2  乘法原则  /8

  2.2排列组合  /8

  2.3鸽笼原理  /11

  2.4素数  /12 

  2.5最大公约数与最小公倍数 /14 

  2.6数制  /17 

2.6.1  进位记数制  /17 

2.6.2  不同进位制数的转换  /19 习题 2 /25 第 3章命题逻辑  /26

  3.0本章导引  /26

  3.1命题与命题联结词  /26 

3.1.1  命题 /26 

3.1.2  命题联结词  /27

  3.2命题公式  /30

  3.3命题公式的等值演算  /33

  3.4命题联结词的完备集  /37

  3.5范式  /39 

3.5.1  析取范式和合取范式  /40 

3.5.2  主析取范式和主合取范式  /41 

3.5.3  范式的应用  /45 

  3.6命题逻辑的推理  /49 

3.6.1  推理的基本概念 /49 

3.6.2  推理的基本方法 /50 习题 3 /57 第 4章谓词逻辑  /60

  4.0本章导引  /60

  4.1谓词逻辑的基本概念  /60

  4.2谓词公式  /63

  4.3谓词公式的等价与蕴涵  /66

  4.4范式  /71 

  4.5谓词逻辑的蕴涵推理  /73习题 4 /78 第 5章集合论基础  /81

  5.0本章导引  /81

  5.1集合的概念与表示  /81 

  5.2集合之间的关系  /82 

  5.3集合的运算  /84

  5.4序偶与笛卡儿积  /87 

  5.5容斥原理  /89习题 5 /92 第 6章关系  /94 

  6.0本章导引  /94

  6.1关系的定义  /94

  6.2关系的表示  /95

  6.3关系的运算  /96 

6.3.1  关系的集合运算 /96 

6.3.2  关系的复合运算 /97 

6.3.3  关系的幂运算  /106 

6.3.4  关系的逆运算  /107 

  6.4关系的性质  /109 

6.4.1  自反性与反自反性  /109 

6.4.2  对称性与反对称性  /110 

6.4.3  传递性  /113 

  6.5关系的闭包  /115 习题 6 /118 第 7章特殊关系  /120 

  7.0本章导引  /120 

  7.1等价关系  /120 

  7.2偏序关系  /126 

  7.3函数的定义  /129 

  7.4函数的性质  /130 

  7.5函数的运算  /131 

7.5.1  函数的复合运算 /131 

7.5.2  函数的逆运算  /132 习题 7 /132第 8章图论基础  /134 

  8.0本章导引  /134 

  8.1图的基本概念 /134 

8.1.1  图  /134 

8.1.2  图的表示  /137 

8.1.3  图的同构  /138 

8.1.4  图的操作  /139

  8.2通路与回路  /141 

  8.3图的连通性  /145 

8.3.1  无向图的连通性 /145 

8.3.2  有向图的连通性 /147 习题 8 /151第 9章特殊图  /153

  9.0本章导引  /153 

  9.1欧拉图  /153

  9.2汉密尔顿图  /157 

  9.3树 /160 

9.3.1  树的定义  /160 

9.3.2  生成树与最小生成树  /163 

V 

  9.4根树  /166 

9.4.1  有向树与根树  /167 

9.4.2  根树的遍历  /168 

9.4.3  Huffman树  /171习题 9 /174第 10章代数系统  /176 

  10.0 本章导引  /176 

  10.1 代数运算  /176 

  10.2 运算的性质与特殊元素  /177 

10.2.1  运算的性质  /177 

10.2.2  特殊元素  /179

  10.3 代数系统的同态与同构  /182 

  10.4 子代数  /184习题 10 /185 第 11章群论  /186

  11.0本章导引  /186 

  11.1半群  /186

  11.2群  /188 

11.2.1  群的基本概念  /189 

11.2.2  阿贝尔群  /191 

11.2.3  群同态与群同构 /191 

  11.3元素的周期与循环群  /192 

11.3.1  元素的周期  /193 

11.3.2  循环群  /193

  11.4子群  /195

  11.5置换群  /198

  11.6陪集与拉格朗日定理  /199 

  11.7正规子群与商群  /202习题 11 /205 第 12章其他代数系统 /207 

  12.0 本章导引  /207 

  12.1 环  /207 

  12.2 域  /209

  12.3 格  /209 

12.3.1  格的定义  /210 

12.3.2  格的另一种定义 /211 

12.3.3  分配格、有界格与布尔格  /213 

  12.4 布尔代数  /213 习题 12 /218 参考文献  /219 

VII