本书主要介绍离散数学的基本理论及算法实现，分为两大部分，第一部分介绍计算机科学中广泛应用的离散结构基本概念和基本原理，包括以下内容：数理逻辑、集合论、二元关系、函数、代数系统和图论。第二部分给出了与各章内容密切相关的算法和程序，使理论在计算机上得到具体实现。附录部分给出了近年来考研试题的分析。
　　 本书条理清晰，阐述深入浅出，适合作为高等学校计算机及相关专业离散数学课程的本科生教材，也可供计算机科学工作者和科技人员阅读与参考。

封底
本书源于作者多年讲授“离散数学”课程的讲义，强调理论与算法和程序设计相结合。全书分两篇，第一篇介绍离散数学的基本理论，第二篇对离散数学中涉及的主要算法用程序进行了实现，使学习者在学习基本理论、建立抽象思维能力和逻辑思维能力的同时，有一个和实践结合的平台，使理论落到实处，同时也有助于提高学习者的程序设计能力。
第2版对于和密码学相关的群论部分进行了较详细的论述，并对第1版的印刷错误进行了订正。
本书特色
内容深入浅出，结构安排合理，每章开头的简短引言引出了内容提要，每章结尾的小结道出了精华，各节后均提供了难度适中的练习题来帮助读者理解基本理论。
基本理论与相关算法和程序相结合，变抽象思维为感性思维，帮助读者提高程序设计能力。
附录中对近年来考研的离散数学典型考题进行了精辟解析，帮助学生轻松应对考试。
为教师配有电子课件、习题答案和主要算法代码，需要的教师可登录华章网站（www.hzbook.com）下载。

第2版前言
　　本书自2007年出版以来已经过去6年的时间了，在这期间我们将其作为示范性软件学院本科生离散数学课程的教材，取得了丰富的教学经验，发现并挖掘出了很多和软件工程理论密切相关的实例。全书配有完整的课件，典型课件不仅具有动漫效果而且具有智能性，此外节后习题配上了解答，书中主要算法配有程序代码。这些对学习者都会有很大启发和帮助，对教材使用者也会提供很大方便。第2版对和密码学相关的群论部分进行了较详细的论述，并对第1版的印刷错误进行了订正。
　　我们希望给学习离散数学课程的学生提供一本比较全面的教材，而且也为从事离散数学课程教学的教师提供一本好的参考书。当然，由于我们的经验和理论水平有限，书中还会存在不少不足之处，恳请读者在阅读本书时给我们提出宝贵的建议和意见，以便在今后再版时加以改进。

编　者
2013年5月于大连




第1版前言
　　计算机科学发展迅速，应用广泛，已成为科学之林的佼佼者。计算机科学之所以能取得这样辉煌的成就，与其具有雄厚的理论基础——离散数学是分不开的。离散数学不仅是计算机科学基础理论的核心课程，也是人工智能的数学基础之一。
　　本书介绍离散数学的结构体系，包括：
　　●　数理逻辑
　　●　集合论
　　●　关系
　　●　函数
　　●　代数系统
　　●　图论
　　其中，数理逻辑是用数学方法研究判定和推理的一门学科，它使用特指的表意符号构成一套形式化语言。使用这套形式化语言可以准确地描述集合的并集、交集、笛卡儿乘积等概念。关系是笛卡儿乘积的子集，函数又是关系的子集。利用函数可以定义运算，利用集合和运算可以定义代数系统，半群与群、环和域、格与布尔代数则是代数系统的特例。图也是一个特殊的代数系统，而且是计算机科学应用领域中最活跃的一个分支。
　　从离散数学的结构体系不难看出，离散数学内容丰富，涉及的知识面广泛，各部分的内容既是独立的又是相关的。离散数学与计算机科学中的数据结构、数据库原理、操作系统、编译原理和软件工程等密切相关。
　　本书分为两大篇，第一篇介绍离散数学的基本理论，共七章，分别是命题逻辑、谓词逻辑、集合论、二元关系、函数、代数系统和图论。第二篇给出离散数学中涉及的主要算法的程序实现，使学习者在学习基本理论、建立抽象思维能力和逻辑思维能力的同时，有一个与实践结合的平台，使理论落到实处，同时对提高学习者的程序设计能力也有一定帮助。
　　附录中给出了近年来考研的例题解析，这对考研的学生会有很大帮助。
　　曹晓东主编了全书，原旭担任副主编并且实现了所有算法的程序设计，刘文杰和栾青对计算机辅助教学部分作出了极大的贡献。侯蕾对公式和图表的编辑做了大量工作。
　　本书不仅可以作为高等院校计算机科学与技术及相关专业的教材，也可作为考研及计算机工作者的参考书。
　　由于编者水平有限，书中错误和疏漏之处在所难免，恳请读者不吝指正。
　　最后，再一次感谢为本书出版作出积极贡献的同志们。

编　者
2007年6月

计算机\离散数学

本书源于作者多年讲授“离散数学”课程的讲义，强调理论与算法和程序设计相结合。全书分两大部分，第一部分介绍离散数学的基本理论，第二部分对离散数学中涉及的主要算法用程序进行了实现，使学习者在学习基本理论、建立抽象思维能力和逻辑思维能力的同时，有一个和实践结合的平台，使理论落到实处，同时也有助于提高学习者的程序设计能力。
第2版对于和密码学相关的群论部分进行了较详细的论述，并对第1版的印刷错误进行了订正。
本书特点
◆内容深入浅出，结构安排合理，每章开头的简短引言引出了内容提要，每章结尾的小结道出了精华，各节后均提供了难度适中的练习题来帮助读者理解基本理论。
◆基础理论与相关算法和程序相结合，变抽象思维为感性思维，帮助读者提高程序设计能力。
◆附录中对近年来考研的离散数学典型考题进行了精辟解析，帮助学生轻松应对考试。
◆为教师配有电子课件、习题答案和主要算法代码，需要的教师可登录华章网站下载。

第2版前言
第1版前言
教学建议
第一篇　计算机科学中的离散结构
第1章　命题逻辑2
　1.1　引言2
　1.2　命题及命题逻辑联结词2
1.2.1　命题2
1.2.2　逻辑联结词3
　1.3　命题变元和合式的公式8
　1.4　重言式(或永真式)和永真蕴涵式10
1.4.1　有关重言式的讨论10
1.4.2　重言式与恒等式10
1.4.3　永真蕴涵式的定义和常用永真蕴涵式11
1.4.4　代入规则和替换规则13
　1.5　对偶原理14
　1.6　范式和判定问题17
1.6.1　析取范式和合取范式17
1.6.2　主析取范式和主合取范式19
　1.7　命题演算的推理理论23
　小结28
第2章　谓词逻辑29
　2.1　谓词演算29
2.1.1　谓词和个体29
2.1.2　量词30
2.1.3　合式公式32
2.1.4　自由变元和约束变元32
2.1.5　谓词公式的解释33
2.1.6　含有量词的等价式和永真蕴涵式33
　2.2　谓词逻辑中的推理理论36
2.2.1　谓词公式的翻译36
2.2.2　推理规则38
　2.3　谓词公式的范式44
2.3.1　前束范式44
2.3.2　斯柯林范式45
　小结47
第3章　集合论48
　3.1　集合的概念及其表示48
　3.2　集合的运算51
　3.3　集合定律58
　3.4　包含排斥原理60
　3.5　多重序元与笛卡儿乘积63
3.5.1　序偶和多重序元64
3.5.2　笛卡儿乘积64
　小结66
第4章　二元关系67
　4.1　关系的基本概念67
　4.2　关系的性质68
　4.3　关系的表示70
　4.4　关系的运算72
4.4.1　关系的合成73
4.4.2　合成关系的矩阵表达和图解76
4.4.3　关系的求逆运算79
4.4.4　关系的闭包运算82
　4.5　特殊关系87
4.5.1　集合的划分和覆盖87
4.5.2　等价关系89
4.5.3　相容关系93
4.5.4　次序关系98
4.5.5　偏序集合与哈斯图100
　小结104
第5章　函数105
　5.1　函数的基本概念和性质105
　5.2　函数的合成与合成函数的性质108
　5.3　特殊函数111
　5.4　反函数114
　5.5　特征函数116
　5.6　基数118
　小结122
第6章　代数系统123
　6.1　二元运算及其性质123
6.1.1　运算的概念123
6.1.2　二元运算的性质124
　6.2　代数系统的概念129
6.2.1　代数系统的基本概念129
6.2.2　子代数系统130
　6.3　同态与同构131
　6.4　同余关系和商代数138
6.4.1　同余关系138
6.4.2　商代数139
　6.5　积代数142
　6.6　特殊代数系统——半群与群143
6.6.1　半群143
6.6.2　群的概念与性质145
6.6.3　子群与陪集148
6.6.4　循环群和置换群152
　6.7　特殊代数系统——环与域156
　6.8　特殊代数系统——格与布尔代数157
　小结160
第7章　图论161
　7.1　图的基本概念161
　7.2　子图和图的运算165
　7.3　路径、回路和连通性168
　7.4　图的矩阵表示174
7.4.1　邻接矩阵174
7.4.2　可达性矩阵178
　7.5　欧拉图182
　7.6　特殊图184
7.6.1　二部图184
7.6.2　平面图187
　7.7　树192
　7.8　网络205
7.8.1　网络流与最大流205
7.8.2　割集207
7.8.3　标号法209
7.8.4　开关网络211
　小结219
第二篇　离散数学中的算法
第8章　数理逻辑中的算法222
　8.1　逻辑联结词的定义方法222
　8.2　合式公式的表示方法224
　8.3　构造合式公式的真值表225
第9章　集合论中的算法227
　9.1　求并集227
　9.2　求交集228
　9.3　求差集229
　9.4　求笛卡儿乘积231
第10章　关系中的算法233
　10.1　判断关系R是否为自反关系及对称关系233
　10.2　判断关系R是否为可传递关系234
　10.3　判断关系R是否为等价关系236
　10.4　求等价类236
　10.5　求极大相容类237
　10.6　关系的合成运算238
　10.7　关系的闭包运算（1）239
　10.8　关系的闭包运算(2)241
　10.9　m个字符串按字典顺序分类算法242
第11章　函数中的算法244
第12章　代数系统中的算法246
　12.1　判断是否为代数系统的算法246
　12.2　判断是否为同余关系的算法247
　12.3　判断是否为群的算法249
第13章　图论中的算法252
　13.1　道路矩阵的Warshall算法252
　13.2　二叉树的遍历253
　13.3　构造最优二叉树算法256
　13.4　最小生成树的Kruskal算法258
　13.5　求最短距离的Dijkstra算法260
　13.6　判别连通性的算法265
附录A　考研例题解析269
附录B　离散数学名词中英文对照表279
参考文献283