本书针对本科离散数学课程的要点和关键问题，深入浅出地介绍了数理逻辑、集合论、图论、代数结构和布尔代数、网络模型、组合数学理论和算法等与计算机科学密切相关的问题，既着重于各部分内容之间的紧密联系，又深入探讨各部分内容的概念、理论、算法和实际应用，本书叙述严谨，推演详尽。各章配有习题，可为读者迅速掌握有关知识提供有效的帮助。
无
离散数学是计算机及相关专业的重要数学基础之一，它是以离散型变量、离散数量关系和离散结构模型为研究对象，以研究离散型变量的结构和相互间的关系为主要目标的一门学科，内容包括数理逻辑、抽象代数、古典概率、组合学、图论、集合论、数论、自动机和形式语言、可计算性和可判定性、离散几何等.
18世纪以前，数学基本上是研究离散对象的数量和空间关系的科学.天文学、物理学的发展，如牛顿三大力学定律等的研究，极大地推动了连续数学的发展.在这个时期，除了抽象代数外，属于离散数学范围的组合学（包括图论）、数理逻辑等一直处于相对停滞的状态.但自20世纪30年代起，随着图灵提出计算机的理论模型——图灵机，以及电子计算机的迅猛发展，离散数学重新焕发青春.
由于电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型，以及如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机进行处理等问题.于是离散数学的地位不断攀升，成为近代数学的一个重要分支.
本书系统地介绍了离散数学各个分支的基本概念、基本理论和基本方法.这些概念、理论以及方法大量地应用在数字电路、编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、人工智能、计算机网络等专业课程中，为学生提高专业理论水平打下坚实的基础.同时，本书着重培养学生的抽象概括能力、逻辑思维能力、归纳构造能力，有益于培养学生严谨、规范的科学态度.
本书在构思、编写过程中参考了一些书籍和文献（已在本书的参考文献中列出），在此对这些文献的作者表示感谢.
本书共10章，内容包括：命题逻辑、谓词逻辑、集合及其运算、二元关系、函数、代数结构、格和布尔代数、图论、树、计数方法和分类原理.每章均有丰富的例题，帮助读者理解知识点；每章最后配有相关习题，可供读者巩固知识点.
本书第1、2、4、7、9、10章由邵秀丽完成，习题由邵秀丽和任明明完成，第3、5、6、8章由张瑞勋完成，任明明负责全书的最终统稿，全书经过三人共同讨论和修改完稿.
本书依据作者在南开大学一直使用的课程讲义整理而成，但由于作者经验所限，书中难免会有疏漏和错误之处，希望读者给予批评和指正.
作者
2020年于南开大学
计算机\离散数学
离散数学是研究离散对象以及它们之间各种关系的一个数学分支，是计算机及相关专业的重要基础课。随着计算机技术的发展，硬件和软件设计都离不开离散数学，尤其是在信息科学迅速发展的今天，离散数学的研究和应用更为重要。本书基于作者长期教授离散数学课程的经验编写而成，既培养学生严谨的思维方式，又能为后续专业课程的学习打下坚实的基础。
本书特点
系统地介绍了离散数学的各个分支的基本概念、理论和方法，包括命题逻辑、谓词逻辑、集合及其运算、二元关系、函数、代数结构、格和布尔代数、图论、树、计数方法和分类原理。这些内容对后续专业课程的学习有非常重要的作用。
推导过程严密、详细，并包括大量的实例，有助于培养学生的抽象概括能力、逻辑思维能力、归纳构造能力，以及培养学生严谨、规范的科学态度。
为了帮助学生理解和使用相关的理论及方法来解决问题，书中安排了类型多样的习题，鼓励学生学以致用。
前言
第1章 命题逻辑1
1.1 引言1
1.2 命题与命题联结词1
1.2.1 命题的概念1
1.2.2 命题标识符和命题分类3
1.2.3 命题联结词3
1.3 翻译、命题公式和真值表7
1.3.1 翻译7
1.3.2 命题公式9
1.3.3 真值情况和真值表10
1.4 永真式、永假式和等价关系12
1.5 等价式和蕴涵式14
1.5.1 等价公式14
1.5.2 等价定律公式14
1.5.3 子公式15
1.5.4 证明两个公式等价的方法16
1.5.5 蕴涵式19
1.5.6 永真蕴涵关系的判断20
1.6 其他联结词22
1.6.1 其他联结词的定义22
1.6.2 与非联结词↑的性质23
1.6.3 或非联结词↓的性质23
1.6.4 异或联结词的性质24
1.6.5 最小联结词组25
1.7 对偶与范式26
1.7.1 对偶27
1.7.2 范式29
1.7.3 主析取范式31
1.7.4 主合取范式35
1.7.5 主范式的应用37
1.8 命题演算的推理理论39
1.8.1 推理的基本概念39
1.8.2 判断有效结论的方法和规则41
本章习题48
第2章 谓词逻辑53
2.1 谓词的基本概念53
2.2 个体、谓词及表达式54
2.3 命题函数57
2.4 量词59
2.5 谓词公式与翻译62
2.5.1 谓词公式62
2.5.2 谓词逻辑的翻译63
2.6 变元的约束65
2.7 谓词公式的永真式、永假式、等价式和蕴涵式68
2.7.1 判定方法和基本公式69
2.7.2 谓词等价式和蕴涵式70
2.7.3 谓词公式的范式72
2.7.4 多个量词的使用74
2.8 谓词演算的推理理论76
2.8.1 4个与量词有关的推理规则76
2.8.2 谓词逻辑中推理的论证78
2.8.3 演算中常见的错误83
本章习题84
第3章 集合及其运算86
3.1 集合的概念与表示86
3.1.1 集合的概念86
3.1.2 集合的表示87
3.1.3 集合的相等或包含关系88
3.1.4 集合的基数90
3.2 集合的运算90
3.3 基本的集合运算律93
3.4 包含排斥原理99
本章习题103
第4章 二元关系105
4.1 序偶和笛卡儿乘积105
4.2 关系及其表示108
4.3 复合关系和逆关系112
4.4 关系的性质118
4.5 关系的闭包124
4.6 等价关系132
4.7 序关系135
本章习题139
第5章 函数141
5.1 函数的概念141
5.2 函数的类型143
5.3 复合函数147
5.4 逆函数149
本章习题153
第6章 代数结构155
6.1 代数系统的一般概念155
6.2 代数系统的运算性质157
6.3 代数系统的同态和同构164
6.4 半群和独异点168
6.5 子半群和子独异点172
6.6 群和子群173
6.7 交换群和循环群181
6.8 子群的陪集及拉格朗日定理184
6.9 置换群188
6.10 环和域190
本章习题196
第7章 格和布尔代数199
7.1 格的基本概念199
7.2 格的基本性质202
7.3 几种特殊的格207
7.4 有界格和有补格212
7.5 布尔代数214
本章习题216
第8章 图论219
8.1 图的基本定义及相关术语219
8.1.1 图的概念219
8.1.2 图的边点之间的关系221
8.1.3 图的分类222
8.2 结点的度数及其计算224
8.3 子图、补图和图的同构227
8.3.1 子图的概念227
8.3.2 补图的概念229
8.3.3 图的同构概念230
8.4 通路、回路和连通性232
8.4.1 通路和回路的概念232
8.4.2 简单有向图的连通性235
8.4.3 无向图的连通性238
8.5 图的矩阵表示241
8.5.1 无向图与有向图的关联矩阵241
8.5.2 图的邻接矩阵242
8.5.3 有向图的可达矩阵244
8.6 欧拉图与哈密顿图245
8.6.1 欧拉图245
8.6.2 哈密顿图251
8.7 最优路径和关键路径257
8.7.1 最优路径的概念257
8.7.2 最优路径在实际中的应用259
8.7.3 欧拉图的应用——中国邮路问题259
8.7.4 哈密顿回路和货郎担问题260
8.8 平面图262
8.8.1 平面图的概念262
8.8.2 平面图的面263
8.8.3 平面图的判定264
8.9 对偶与着色269
8.9.1 对偶的基本概念269
8.9.2 平面图的对偶图的做法269
8.9.3 对偶图的性质270
8.9.4 图的着色271
8.9.5 地图的着色与平面图的点着色272
本章习题273
第9章 树277
9.1 无向树及其性质277
9.1.1 树的基本概念277
9.1.2 无向树的性质277
9.2 生成树和最小生成树280
9.3 有向树、根树和二叉树285
9.3.1 有向树和根树的概念285
9.3.2 m叉树和二叉树286
9.4 树的遍历289
9.5 最优树与Huffman算法290
9.6 最佳前缀码291
本章习题293
第10章 计数方法和分类原理295
10.1 基本原理295
10.1.1 乘法原理295
10.1.2 加法原理296
10.2 排列与组合297
10.3 可重复的排列与组合301
10.4 鸽巢原理303
本章习题306
附录A 模拟试卷1308
附录B 模拟试卷2311
参考文献313
