“离散数学”是计算机及其相关专业的专业基础课。全书共分四篇:第一篇是数理逻辑，包括命题逻辑和一阶逻辑；第二篇是集合论，包括集合、二元关系和函数；第三篇是图论基础，包括图的基本概念、特殊图和树；第四篇是代数系统，包括代数系统的基本概念和典型代数系统简介。本书用大量的实例将理论知识和计算机应用相结合，可作为应用型高校计算机科学与技术、网络工程、软件工程、电子与计算机工程等相关专业“离散数学”课程的教材，也可作为计算机及相关领域研究和应用开发人员的参考书。

第一篇数理逻辑
第1章命题逻辑2
1.1命题逻辑的基本概念2
1.1.1命题的概念2
1.1.2命题的表示3
1.1.3命题联结词4
1.1.4联结词完备集8
1.2命题公式及其赋值9
1.2.1命题公式的概念9
1.2.2命题公式的解释10
1.2.3命题公式的类型11
1.2.4真值表11
1.3命题公式的等值演算13
1.3.1等值式13
1.3.2等值演算法14
1.4命题公式的范式16
1.4.1析取范式与合取范式16
1.4.2主析取范式与主合取范式18
1.4.3主范式的应用22
1.5命题逻辑推理理论24
1.5.1推理的基本概念24
1.5.2推理定律和推理规则26
1.5.3命题逻辑推理方法27
1.6命题逻辑在计算机学科中的应用34
1.6.1命题逻辑公式在计算机中的表示34
1.6.2命题逻辑在计算机硬件电路设计中的应用35
1.6.3命题逻辑在程序设计中的应用38
1.6.4命题逻辑在系统规范说明中的应用39
1.6.5命题逻辑在布尔检索中的应用39
习题140
第2章一阶逻辑46
2.1一阶逻辑的基本概念46
2.1.1个体和谓词46
2.1.2量词47
2.1.3一阶逻辑的翻译(符号化)48
2.2一阶逻辑公式与解释50
2.2.1一阶逻辑合式公式50
2.2.2自由变元与约束变元51
2.2.3一阶逻辑公式的解释52
2.3一阶逻辑等值演算54
2.3.1一阶逻辑等值式54
2.3.2一阶逻辑等值演算55
2.4一阶逻辑公式范式57
2.4.1前束范式57
2.4.2斯科伦范式58
2.5一阶逻辑推理理论59
2.5.1一阶逻辑推理的基本概念59
2.5.2一阶逻辑的推理规则60
2.5.3一阶逻辑的推理方法61
2.6数理逻辑与专家系统64
2.6.1数理逻辑在专家系统中的应用64
2.6.2逻辑编程语言Prolog65
习题267
第二篇集合论
第3章集合72
3.1集合的基本概念与表示72
3.1.1集合的概念与表示72
3.1.2集合之间的关系74
3.1.3幂集的概念77
3.2集合的运算与性质78
3.2.1集合间的运算78
3.2.2集合运算定律81
3.2.3集合的证明方法84
3.3集合中元素的计数89
3.3.1文氏图法89
3.3.2包含排斥原理91
3.4集合在计算机中的表示93
3.4.1数组法93
3.4.2链表法94
3.4.3位串法95
习题396
第4章二元关系和函数98
4.1关系及其表示98
4.1.1二元关系概念98
4.1.2几种特殊的二元关系98
4.1.3关系的表示方法99
4.2关系的运算100
4.2.1关系的运算100
4.2.2关系运算的性质102
4.3关系的性质104
4.3.1性质的定义104
4.3.2性质的判定105
4.4关系的闭包107
4.4.1闭包的概念107
4.4.2闭包的求解方法107
4.4.3沃舍尔(Warshall)算法110
4.4.4闭包的性质111
4.5等价关系与划分112
4.5.1等价关系的概念112
4.5.2等价类的概念与性质112
4.5.3商集与划分的概念113
4.6偏序关系115
4.6.1概念115
4.6.2哈斯图116
4.6.3几种特殊元素117
4.7函数118
4.7.1函数的定义和性质118
4.7.2函数的复合和反函数120
4.8关系的应用121
4.8.1拓扑排序121
4.8.2数据库和关系122
习题4126
第三篇图论基础
第5章图的基本概念130
5.1无向图及有向图130
5.1.1无向图130
5.1.2有向图130
5.1.3相关概念131
5.1.4平行边、重数、多重图、简单图132
5.1.5基本定理(握手定理)133
5.1.6无向接近图、有向接近图134
5.1.7子图134
5.1.8补图135
5.1.9图的同构135
5.2通路、回路、图的连通性136
5.2.1通路和回路136
5.2.2图的连通性138
5.2.3割集139
5.3图的矩阵表示139
5.3.1无向图的关联矩阵139
5.3.2有向图的关联矩阵140
5.3.3有向图的邻接矩阵141
5.3.4有向图的可达矩阵142
5.4图的运算142
5.5图的应用144
5.5.1无向图的加权矩阵144
5.5.2最短路径算法144
习题5148
第6章特殊图152
6.1二部图152
6.1.1二部图的定义152
6.1.2二部图的判断定理152
6.1.3匹配154
6.1.4Hall定理155
6.2欧拉图160
6.2.1无向图的欧拉图及其判断161
6.2.2有向图的欧拉回路判定定理162
6.2.3中国邮递员问题163
6.3哈密尔顿图165
6.3.1概念166
6.3.2无向图的哈密尔顿图167
6.3.3货郎担(旅行商)问题167
6.4平面图171
6.4.1平面图的基本概念171
6.4.2欧拉公式173
6.4.3平面图的判断174
6.4.4对偶图176
6.4.5图的着色176
习题6179
第7章树184
7.1无向树及生成树184
7.1.1无向树184
7.1.2生成树的概念与性质186
7.1.3最小生成树188
7.2根树及其应用191
7.2.1根树的概念191
7.2.2二叉树192
7.2.3很优二叉树及其应用196
习题7199
第四篇代数系统
第8章代数系统的基本概念204
8.1二元运算及其性质204
8.1.1二元运算的基本概念204
8.1.2二元运算的性质205
8.1.3二元运算的特异元素207
8.2代数系统210
8.2.1代数系统的概念210
8.2.2代数系统的同态与同构211
习题8212
第9章典型代数系统简介215
9.1半群与群215
9.1.1半群与独异点215
9.1.2群和子群216
9.2环与域219
9.2.1环的概念219
9.2.2域的概念221
9.3格与布尔代数222
9.3.1格的概念与性质222
9.3.2布尔代数的概念与性质225
9.4代数系统应用简介226
9.4.1加密算法中的代数系统226
9.4.2群论在信息编码中的应用226
9.4.3布尔代数在逻辑线路中的应用229
9.4.4代数系统在计算机中的表示229
习题9229
参考文献231