离散数学 修订版PDF电子书下载

目录 5

第一篇 数理逻辑 5

第一章 命题逻辑 5

§1.1 命题和联结词 5

§1.2 公式和真值赋值 8

§1.3 等值演算 12

§1.4 对偶定理 15

§1.5 联结词的完全集 17

§1.6 范式 19

§1.7 逻辑推论 23

习题一 24

第二章 谓词逻辑 29

§2.1 谓词和量词 29

§2.2 项和公式 33

§2.3 解释和赋值 36

§2.4 永真式 43

§2.5 等值演算 46

§2.6 逻辑推论 49

习题二 51

第三章 公理系统 54

§3.1 命题逻辑的公理系统 54

§3.2 谓词逻辑的公理系统 59

习题三 64

第四章 归结法原理 65

§4.1 命题逻辑的归结法 65

§4.2 前束范式与斯科伦范式 69

§4.3 谓词逻辑的归结法 70

习题四 78

参考文献 80

第二篇 集合论 83

第五章 集合的基本概念及其运算 83

§5.1 集合与元素 83

§5.2 集合间的相等和包含关系 85

§5.3 幂集 87

§5.4 集合的运算 89

§5.5 有穷集的计数原理 95

§5.6 集合的归纳定义法 97

§5.7 有序偶和笛卡儿乘积 101

习题五 103

第六章 关系 106

§6.1 关系及其性质 106

§6.2 关系的运算 110

§6.3 次序关系 115

§6.4 等价关系、划分及其他 119

习题六 123

第七章 函数 127

§7.1 基本概念 127

§7.2 函数的复合 131

§7.3 特殊性质的函数 134

§7.4 集合的特征函数 138

习题七 139

第八章 自然数和基数 142

§8.1 自然数及数学归纳法 142

§8.2 基数 145

习题八 151

参考文献 153

§9.1 有向图及无向图 157

第三篇 图论 157

第九章 基本概念 157

§9.2 图的基本结构 159

§9.3 子图 161

§9.4 连通性 164

§9.5 顶点基和强分图 169

习题九 173

第十章 通路问题 175

§10.1 最短通路 175

§10.2 关键通路 178

习题十 181

第十一章 图的矩阵表示 182

§11.1 邻接矩阵 182

§11.2 有向图的可达性矩阵 184

§11.3 关联矩阵 188

习题十一 189

第十二章 树 190

§12.1 树的一般定义 190

§12.2 根树与有序树 192

§12.3 二元树 193

§12.4 生成树 197

§12.5 割集 200

习题十二 201

第十三章 穿程问题 204

§13.1 欧拉图 204

§13.2 哈密顿图 207

习题十三 209

§14.1 基本概念 211

第十四章 二分图的匹配问题 211

§14.2 二分图的最大匹配 213

§14.3 从X到Y的匹配 215

习题十四 217

第十五章 平面图及色数 219

§15.1 平面图 219

§15.2 色数 224

习题十五 227

参考文献 229

§16.1 代数系统 233

第十六章 基本概念 233

第四篇 代数系统 233

§16.2 同态和同构 236

§16.3 子代数和商代数 237

习题十六 240

第十七章 半群和群 241

§17.1 半群的概念 241

§17.2 子半群和半群同态 242

§17.3 商半群和半群直积 243

§17.4 群的概念 245

§17.5 子群和群的同态 247

§17.6 变换群、置换群和循环群 249

§17.7 不变子群和商群 251

习题十七 255

第十八章 环和域 257

§18.1 环和域的概念 257

§18.2 子环和环的同态 259

§18.3 理想和商环 260

习题十八 262

§19.1 格的定义与基本性质 263

第十九章 格和布尔代数 263

§19.2 子格和格的同态 265

§19.3 布尔代数 265

§19.4 布尔代数的表示 267

习题十九 270

第二十章 抽象数据类型的代数 271

规范 271

§20.1 标记、项和代数规范 271

§20.2 ∑-代数和范畴 276

§20.3 代数规范的初始语义 278

习题二十 279

参考文献 281

第五篇 有限自动机理论 285

第二十一章 基本概念 285

§21.1 字符表、字符串及其集合的运算 285

§21.2 有限自动机的定义 286

§21.3 有限自动机的等价 290

§21.4 Mealy机与Moore机 292

习题二十一 295

§22.1 最小有限自动机的定义及性质 296

第二十二章 有限自动机的简化 296

§22.2 状态集的S划分和格LM 298

§22.3 有限自动机的最小化 304

习题二十二 311

第二十三章 有限自动机和正则表达式 313

§23.1 有限自动机的识别功能 313

§23.2 非确定有限自动机 315

§23.3 正则表达式 318

§23.4 由正则表达式构造FA的算法 320

§23.5 有限自动机和正则表达式的等价性 326

§23.6 正则集合及其性质 329

习题二十三 331

第二十四章 有限自动机的综合与应用 333

§24.1 有限自动机的综合 333

§24.2 FA理论在算法设计中的应用 336

§24.3 FA理论与形式语言理论的关系 341

习题二十四 344

参考文献 346

名词索引 347