本书源于作者多年讲授“离散数学”课程的讲义，强调理论与算法和程序设计相结合。全书分两大部分，第一部分介绍离散数学的基本理论，第二部分对离散数学中涉及的主要算法用程序进行了实现，使学习者在学习基本理论、建立抽象思维能力和逻辑思维能力的同时，有一个和实践结合的平台，使理论落到实处，同时也有助于提高学习者的程序设计能力。
　　本书适合作为高等院校计算机及相关专业的离散数学教材，也可作为考研及计算机工作者的专业参考书。

　　本书的特点如下：
　　◆内容深入浅出，结构安排合理，练习难度适中，讲解通俗易懂。
　　◆基础理论与相关算法和程序相结合，变抽象思维为感性思维，帮助提高程序设计能力。
　　◆附录中对近年来考研的离散数学典型考题进行了精辟解析，帮助学生轻松应对考试。
　　◆为教师配有电子课件，需要的教师可登录华章网站下载。

无

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

　　编者
　　2007年6月

前言
第一篇计算机科学中的离散结构
第1章命题逻辑2
1.1引言2
1.2命题及命题逻辑联结词 2
1.2.1命题2
1.2.2逻辑联结词3
1.3命题变元和合式的公式7
1.4重言式(或永真式)和永真
蕴涵式9
1.4.1有关重言式的讨论9
1.4.2重言式与恒等式9
1.4.3永真蕴涵式的定义和常用永真
蕴涵式11
1.4.4代入规则和替换规则12
1.5对偶原理13
1.6范式和判定问题16
1.6.1析取范式和合取范式16
1.6.2主析取范式和主合取范式18
1.7命题演算的推理理论21
小结26
第2章谓词逻辑27
2.1 谓词演算27
2.1.1谓词和量词27
2.1.2谓词和个体27
2.1.3量词28
2.1.4合式公式29
2.1.5自由变元和约束变元30
2.1.6谓词公式的解释31
2.1.7含有量词的等价式和永真
蕴涵式31
2.2 谓词逻辑中的推理理论33
2.2.1谓词公式的翻译33
2.2.2推理规则34
2.3谓词公式的范式40
2.3.1前束范式40
2.3.2斯柯林范式41
小结42
第3章集合论43
3.1集合的概念及其表示43
3.2集合的运算46
3.3集合定律53
3.4包含排斥原理54
3.5多重序元与笛卡儿乘积57
3.5.1序偶和多重序元57
3.5.2笛卡儿乘积58
小结60
第4章二元关系61
4.1 关系的基本概念61
4.2关系的性质62
4.3关系的表示63
4.4关系的运算66
4.4.1关系的合成66
4.4.2合成关系的矩阵表达和图解70
4.4.3关系的求逆运算72
4.4.4关系的闭包运算75
4.5特殊关系80
4.5.1集合的划分和覆盖80
4.5.2等价关系81
4.5.3相容关系86
4.5.4次序关系90
4.5.5偏序集合与哈斯图93
小结96
第5章函数97
5.1函数的基本概念和性质97
5.2函数的合成与合成函数的性质100
5.3特殊函数103
5.4反函数105
5.5特征函数108
5.6基数110
5.7 二元运算112
小结116
第6章代数系统117
6.1代数系统的一般概念117
6.2同态与同构118
6.3同余关系121
6.4商代数和积代数123
6.5典型代数系统126
小结130
第7章图论132
7.1图的基本概念132
7.2子图和图的运算136
7.3路径、回路和连通性139
7.4图的矩阵表示145
7.4.1邻接矩阵145
7.4.2可达性矩阵149
7.5欧拉图153
7.6特殊图155
7.6.1二部图155
7.6.2平面图158
7.7树163
7.8 网络176
7.8.1网络流与最大流177
7.8.2割集178
7.8.3标号法180
7.8.4开关网络182
小结190
第二篇离散数学中的算法
第8章数理逻辑中的算法192
8.1逻辑联结词的定义方法192
8.2合式公式的表示方法194
8.3 构造任意合式公式的真值表196
第9章集合论中的算法198
9.1求并集198
9.2求交集199
9.3求差集201
9.4求笛卡儿乘积202
第10章关系中的算法204
10.1判断关系R是否为自反关系及对称
关系204
10.2 判断关系R是否为可传递关系205
10.3判断关系R是否为等价关系207
10.4求等价类210
10.5求极大相容类211
10.6关系的合成运算212
10.7关系的闭包运算（1）214
10.8关系的闭包运算(2)216
10.9 m个字符串按字典顺序分类
算法217
第11章函数中的算法219
第12章代数系统中的算法221
12.1判断是否为代数系统的算法221
12.2判断是否为同余关系223
12.3判断是否为群的算法224
第13章图论中的算法227
13.1道路矩阵的Warshall算法227
13.2二叉树的遍历228
13.3构造最优二叉树算法235
13.4最小生成树的Kruskal算法 237
13.5求最短距离的Dijkstra算法240
13.6判别连通性的算法244
附录考研例题解析249
参考文献259