本书共5篇12章,将离散数学按总论、主要内容及应用的顺序进行讲解，其中离散数学主要内容部分讲述离散数学中的四个核心内容(集合论、代数系统、图论与数理逻辑)，在应用部分在国内首先系统引入并介绍了离散建模的相关内容，将离散数学与计算机以及IT领域应用相结合，从而使离散数学这门课程真正融入计算机及信息技术领域中。
本书凝聚了作者多年的研究成果和实践经验，是一本优秀的离散数学入门教材。全书共五篇12章，将离散数学按总论、主要内容及应用的顺序进行讲解，其中主要内容部分讲述离散数学中的4个核心内容（集合论、代数系统、图论与数理逻辑），应用部分在国内首次系统引入和介绍了离散建模的相关内容，并将离散数学与计算机以及IT领域应用相结合，从而使离散数学这门课程真正融入计算机及信息技术领域中。
本书特点
少而精原则：内容选材坚持少而精，选取具有代表性的核心内容，通过精讲精练达到举一反三的效果；同时减少过于繁琐的证明环节，因而做到篇幅短小，适合目前精简学时的教学需要。
释义清楚：对基本概念与性质给出详细的释义，不但介绍了数学的抽象表示，而且更注重其形式语义，使学生掌握它们的精髓并能灵活应用。
学以致用：增设离散建模内容，介绍离散建模的一般原理，并精选5个著名实例，使学生初步掌握运用离散数学作为工具来解决实际问题的能力。
适合教学：配有大量习题及思考题，同时每章都有学习小结，每篇有学习总结；全书配有电子教案，可供教师教学之用。
作者简介
徐洁磐 南京大学计算机科学与技术系教授，长期从事计算机理论和离散数学的教学与研究，曾任中国离散数学学会理事长，主持制订我国第一部离散数学教学大纲，编写了我国第一部原创离散数学教材《离散数学导论》（国家级规划教材），还著有《离散数学及其在计算机科学中的应用》《数据库系统实用教程》（国家级精品教材）等20余本专著和教材。
数学
离散数学教学改革探索的体会
离散数学是数学的一大门类，由于它的离散性，使得它在计算机及信息技术应用领域有重要作用，因此离散数学作为一门课程已在该领域相关专业大量开设，自20世纪70年代开始至今已有30余年历史。随着科学技术不断发展、改革开放不断深入，我们对离散数学课程的改革也不断有新的认识。特别是近年来的变化，促使我们对离散数学课程的教学改革产生一个新的认识，从而能做出新的调整。
离散数学课程的变化
1．离散数学课程教学环境的变化
近年来离散数学教学环境产生了重大的变化，这主要表现为：
（1）离散数学课程设置由计算机专业扩展至信息技术领域的多个专业。
（2）离散数学课程内容由少量数学分支领域（数理逻辑、集合论、代数系统及图论等）扩展至多种数学分支领域（如组合数学、数论、有限自动机等）。
（3）离散数学课程教学课时数出现了由多到少的倾向，据2008年的不完全统计，离散数学课时数由以前的平均90学时下降至平均78学时。
（4）由于高等教育由精英化逐渐走向大众化，因此离散数学参学学生人数越来越多但起点逐年降低。
以上四点可归结成下面的一句话：“离散数学课程参学人数及专业数越来越多；要求越来越高；但教学课时数越来越少，参学学生起点越来越低。这就形成了当前离散数学教学中的巨大的矛盾与差异，而设法解决这些问题就成为离散数学课程教学改革的当务之急。
2．离散数学课程教学对象的变化
由离散数学课程教学环境的变化而引起了教学对象的变化。从广度看，离散数学课程的教学对象已由仅对计算机相关专业学生而扩充到计算机及信息技术领域的各专业（如自动化、通信、电子信息安全等专业）学生。而从所学层次看，离散数学课程的教学对象又可分为研究型本科、工程型本科、应用型本科以及高职高专等多个层次。
离散数学课程教学对象的变化反映了对离散数学课程需求的变化是引发课程改革的原因。
3．离散数学课程开设目标的变化
除了上述两点变化之外，经过数十年的探索与实践，对开设离散数学课程的目标也有了新的认识。
（1）培养离散思维与抽象思维能力。
（2）为学生所学后续课程（如数据结构、数据库、人工智能、编译原理、软件工程、数据通信、数字逻辑电路）提供支撑，也为学生进一步的理论需求（如论文撰写及理论研究）提供基础。
（3）培养学生离散建模能力，为学生以后在工作中用离散数学作工具应用于本专业的研究与开发提供相应能力。
根据以上的目标，离散数学目前已成为计算机及IT相关专业的必修课程及核心课程。
根据以上三点变化，我们必须对离散数学课程改革提出新的思想与方案，即下面所介绍的一、二、三原则。
离散数学课程教学改革的一、二、三原则
1．离散数学课程的两层结构体系
由于离散数学参学人群的专业不一、需求不一以及开设课时不一，因此在教学中存在一定差异，特别是在教学内容要求上并不一致，为此需对其教学内容作分析：
首先，离散数学课程有一个基本的、共同的内容要求。它们是离散数学的基本的、必需的部分。一般认为，它们是集合论、代数系统、图论及数理逻辑。（详细原因可参见本书第一篇。）
其次，离散数学课程内容允许有差异性，即允许存在不同要求的内容。它们是离散数学的可选择部分，包括组合数学、数论、离散概率、有限自动机理论、递归函数论等。
离散数学的必需部分与可选部分构成了一个完整的课程体系，即两层结构体系。它既保证了离散数学的基本要求，同时也满足离散数学的不同要求。根据不同专业与学生的不同层次，可以选取不同的内容以满足不同的要求。
2．离散数学课程的三种分类教学方法
在离散数学课程中的教学内容涉及多个不同方面，它包括：
? 内容的深与浅。
? 范围的宽与窄。
? 释义的多与少。
对以上三个离散数学教学的不同方面，建议采用三级分类制（它类似于高等数学的四级分类制）：
（1）分类1：对离散数学分类1，可采用内容深、范围宽但释义少，它的适合范围以研究型学校为主。
（2）分类2：对离散数学分类2，可采用内容、范围及释义均适中为宜，它的适合范围以工程型学校为主。
（3）分类3：对离散数学分类3，可采用内容浅、范围狭但释义多，它的适合范围以应用型学校为主。
三级分类制有助于适应不同专业、不同层次、不同需求以及不同学生的要求，增强离散数学课程教学的灵活性与适应性，避免一刀切的现象。
3．离散数学课程教学的一项新任务——离散建模
离散数学是一门工具，它为计算机及IT专业日后研究与开发提供理论支撑。计算机及信息技术领域各专业学生对它的学习与数学专业学生有不同之处，它不是以研究与发展数学本身为目的，而是以研究与开发计算机及IT领域的应用为目的，因此在离散数学课程教学中必须增加离散建模内容，这是科学技术发展对离散数学教学提出的新任务。
离散建模一般包括在研究中建立理论模型以及在开发应用中建立应用模型，因此这种建模对三种分类方法都是必需的。
上面所给出的一（一项新任务：离散建模）、二（二层结构体系）、三（三种分类方法）原则为离散数学课程教学改革提供了新的方法与手段。它可以改变目前离散数学课程教学中死板、僵化的格局，促进离散数学课程教学中的多样化与灵活性，以期回归离散数学教学需求的真实面目。
离散数学教材的编写
1．教材定位
以上面所述的离散数学课程教学改革的一、二、三原则为指导，在离散数学教材的建设方面，也应注重多样化和多品种，以适应不同层次及不同分类的需要，而在多种需要面前，目前最为迫切建设的是以基本必需部分为主的分类3型教材，这主要是由于修读此类的学生人数比例较大，
约占所学人数2/3左右，而目前市场上此类教材所占比例又很少。因此，本教材编写定位即以分类3为准。其内容与范围以少而精为原则，而释义则以讲透、讲深为原则。适用对象以应用型本科学生为主。
2．教材编写内容
编写内容包括必需的四个部分：集合论、代数系统、图论及数理逻辑，还包括离散建模。
3．教材编写的基本原则
在本教材的具体编写中，则坚持以下五项基本原则：
（1）内容少而精：在内容选材上坚持少而精，选取具有代表性的核心内容，通过精讲精练达到举一反三的效果。
（2）释义清楚：教材是面向学生的，为使学生接受离散数学抽象思维与离散思维内容、培养相应能力，在教材中必须对离散数学的基本概念与性质作详细的释义，即不但要了解数学的抽象表示，更要注重其形式语义，使学生能掌握它们的精髓并能灵活应用。
（3）学以致用：在本教材中增设离散建模内容，介绍离散建模的一般原理，并精选五个著名实例，通过此部分内容学习使学生能初步掌握运用离散数学作工具来解决实际问题的能力。
（4）篇幅短小：在本教材中由于内容精练且减少了过于复杂、繁琐的证明环节，因而做到了篇幅短小，一般适合70学时左右的教学需要。
（5）适合教学：本教材配有大量习题及思考题，同时每章都有学习小结、每篇都有学习总结，全书还配有电子教案供教师教学之用。同时，本书还会配套相关辅助教材。
4．教材特色
（1）本教材在国内首先系统引入并介绍了离散建模，将离散数学与计算机以及IT领域应用相结合，从而使离散数学这门课程真正融入计算机及信息技术领域中。
（2）本教材在突出重点、压缩内容上也取得突破，达到了少而精的目的，同时也能充分适应国内课时减少的需要。
（3）本教材的四个核心内容（集合论、代数系统、图论及数理逻辑）坚持其独立性与关联性。所谓独立性，即每部分内容具有各自特色，它们之间不存在依赖关系，每个部分内容不以其他部分内容为先导；所谓关联性，即要强调各部分内容间的共性。教材中的独立性与关联性两者不可缺一，它们的有机结合构成了教材的完整与统一的体系。
5．教材组织结构
本教材共五篇12章，内容顺序包括绪言、集合论（共三章）、代数系统（共三章）、图论（共二章）、数理逻辑（共二章）以及离散建模（共二章）等，其重点为集合论与数理逻辑，书中标有“?”的章节不是必需的，仅供参考选择之用。
致谢
最后，在本书付梓之际，感谢南京航天航空大学吕义忠教授为审阅本书所作出的辛勤劳动，同时感谢南京大学计算机系及计算机软件新技术国家重点实验室的费翔林教授、徐永森教授、朱怀宏副教授及柏文阳副教授为本书所提供的支持。
由于作者水平有限，书中难免存在不足之处，恳请读者不吝赐教。
徐洁磐
南京大学计算机科学与技术系
南京大学计算机软件新技术国家重点实验室
2009年3月
徐洁磐：暂无
序
绪 言
第一篇 集合论
第1章 集合论基础 2
1.1 集合的基本概念 2
1.2 集合的表示方法 3
1.2.1 枚举法 3
1.2.2 特性刻划法 3
1.3 集合概念间的关系 3
1.3.1 集合与元素间的关系 4
1.3.2 集合与集合间的关系 4
1.3.3 集合相交中的两个特殊关系 5
1.4 集合概念的基本性质 5
1.5 集合运算 6
1.6 集合运算的应用 9
1.7 扩充的集合运算之一——差运算
1.7 与对称差运算 10
1.8 扩充的集合运算之二——幂运算 11
1.9 扩充的集合运算之三——笛卡儿乘 11
1.9.1 序偶 12
1.9.2 笛卡儿乘 13
1.9.3 n元有序组与n阶笛卡儿乘积 13
本章小结 14
习题一 15
第2章 关系 17
2.1 关系的基本概念 17
2.2 关系的表示 18
2.2.1 枚举法 18
2.2.2 特性刻划法 18
2.2.3 矩阵表示法 18
2.2.4 图示法 19
2.3 关系的性质 20
2.4 关系运算 22
2.4.1 关系的并、交、补运算 22
2.4.2 关系的复合运算与逆运算 22
2.4.3 关系上的闭包运算 25
2.5 两种常用的关系 28
2.5.1 次序关系 28
2.5.2 等价关系 33
2.6 n元关系 36
本章小结 36
习题二 37
第3章 函数与无限集 40
3.1 函数的基本概念 40
3.2 函数的表示 40
3.3 函数的分类 42
3.4 函数运算 44
3.4.1 函数的复合运算 44
3.4.2 函数的逆运算 46
3.5 几种常用函数 48
3.6 多元函数 48
3.7 有限集与无限集 49
本章小结 50
习题三 50
第一篇总结 51
第一篇附录 53
第二篇 代数系统
第4章 代数系统概论 58
4.1 代数系统介绍 58
4.2 代数运算中的常见性质 60
4.3 代数系统的同态与同构 62
4.4 代数系统的分类 65
本章小结 67
习题四 68
第5章 群论 70
5.1 半群 70
5.2 群 71
5.2.1 群及其性质 71
5.2.2 群同态与变换群 72
5.2.3 有限群 74
5.2.4 循环群 76
5.2.5 子群与正规子群 77
本章小结 81
习题五 82
第6章 环论与格论 84
6.1 环 84
6.2 整环 85
6.3 域 85
6.4 格 86
6.5 偏序格 86
6.6 分配格、有界格与有补格 88
6.7 布尔代数 88
本章小结 90
习题六 91
第二篇附录 93
第三篇 图论
第7章 图论原理 100
7.1 图的基本概念 100
7.2 通路、回路与连通图 107
7.3 欧拉图 109
7.4 哈密顿图 111
7.5 图的矩阵表示法 112
本章小结 119
习题七 120
第8章 树 122
8.1 树的基本性质 122
8.2 有向树 123
8.3 二元树 125
8.4 生成树 127
本章小结 129
习题八 130
第三篇附录 131
第四篇 数理逻辑
第9章 命题逻辑 136
9.1 命题 136
9.2 命题联结词 137
9.3 命题公式 141
9.4 命题公式的真值表与重言式 144
9.5 命题逻辑的等式推理 146
9.5.1 基本等式 146
9.5.2 推理规则 147
9.5.3 等式推理过程 148
9.6 命题逻辑的蕴含推理 151
9.6.1 推理规则 151
9.6.2 推理方法 153
9.7 范式 155
9.7.1 析取范式与主析取范式 155
9.7.2 合取范式与主合取范式 158
本章小结 160
习题九 161
第10章 谓词逻辑 163
10.1 谓词逻辑的三个基本概念——个体、
10.1 谓词与量词 163
10.2 谓词逻辑中的两个补充概念——
10.1 自由变元/约束变元与函数 165
10.3 谓词公式 167
10.4 谓词逻辑的永真公式 170
10.5 谓词逻辑的等式推理 172
10.6 谓词逻辑的蕴含推理 173
10.7 谓词逻辑范式 176
本章小结 177
习题十 179
第四篇附录 181
第五篇 离散建模
第11章 离散建模概念与方法 188
11.1 离散建模概念 188
11.2 离散建模方法 188
11.3 离散建模的步骤 190
本章小结 191
习题十一 192
第12章 离散建模应用实例 193
12.1 操作系统中死锁检测的离散建模 193
12.2 人工智能机器人规划的离散建模 195
12.3 数据库中关系数据模型的离散建模 200
12.4 数据通信中纠错码的离散建模 209
12.5 软件工程中程序正确性证明的
12 离散建模 218
本章小结 223
习题十二 224
第五篇附录 225
附录 中英文名词对照表 226
参考文献 230
