离散数学及其应用

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

目 录
*篇 数 理 逻 辑

第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
 习题1 40
第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 逻辑编程语言Prolog 65
 习题2 67
第二篇 集 合 论
第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
 习题3 96
第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
 习题4 126
第三篇 图 论 基 础
第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
 习题5 148
第6章 特殊图 152
 6.1 二部图 152
 6.1.1 二部图的定义 152
 6.1.2 二部图的判断定理 152
 6.1.3 匹配 154
 6.1.4 Hall定理 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
 习题6 179
第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
 习题7 199
第四篇 代 数 系 统
第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
 习题8 212
第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
 习题9 229
参考文献 231