离散数学及应用PDF电子书下载

第一篇 数理逻辑 1

第一章 命题演算 2

1-1 命题及联结词 2

1-2 命题变元与命题公式 8

1-3 命题演算的关系式 10

1-3-1 命题之间的等价关系 10

1-3-2 命题的蕴函关系 14

1-3-3 对偶法则 16

1-4 其他联结词 18

1-5 范式 21

1-5-1 析取范式和合取范式 21

1-5-2 主析取范式和主合取范式 23

1-6 命题演算的推理 30

1-6-1 真值表技术 31

1-6-2 直接推演 33

1-6-3 间接推演 37

第二章 谓词演算 38

2-1 谓词演算的基本概念 38

2-1-1 谓词与个体 39

2-1-2 量词 41

2-1-3 谓词演算公式 42

2-1-4 自由变元与约束变元 43

2-2 谓词演算的关系式 46

2-2-1 基本定义 46

2-2-2 关系式 47

2-3 前束范式 53

2-4 谓词演算的推理 54

习题一 59

学习提要一 66

第二篇 集合论 79

第三章 集合 80

3-1 集合的基本概念 80

3-1-1 集合及其表示 80

3-1-2 集合间的关系 81

3-1-3 几种特殊集合 84

3-2 集合的运算及基本公式 85

3-3 幂集 93

3-4 包含排斥原理 95

3-5 集合的直积(笛卡儿乘积) 97

第四章 关系 101

4-1 关系及其运算 101

4-2 关系的有关性质 108

4-3 关系的闭包运算 111

4-4 等价关系和相容关系 115

4-4-1 集合的覆盖与划分 115

4-4-2 等价关系 116

4-4-3 相容关系 119

4-5 偏序关系 121

第五章 映射与无限集 129

5-1 映射 129

5-1-1 映射的基本概念 129

5-1-2 复合映射 134

5-1-3 逆映射 135

5-1-4 由映射产生的等价关系 137

5-2 无限集 141

5-2-1 自然数 141

5-2-2 等势 142

5-2-3 可列集 143

5-2-4 不可列无限集 145

5-2-5 势的比较 147

习题二 150

学习提要二 158

第三篇 图论 167

第六章 图论 168

6-1 图的基本概念 168

6-1-1 基本术语 168

6-1-2 路与回路 177

6-1-3 欧拉图与哈密顿图 183

6-2 树 190

6-2-1 树的特征 190

6-2-2 生成树与割集 192

6-2-3 有向树 197

6-3 图的矩阵表示 201

6-3-1 关联矩阵与基本关联矩阵 201

6-3-2 回路矩阵 203

6-3-3 割集矩阵 204

6-3-4 邻接矩阵 205

6-3-5 有向图的矩阵表示 207

6-4 平面图 212

6-4-1 平面图的概念 212

6-4-2 连通平面图的欧拉公式 214

6-4-3 库拉托斯基定理 215

6-4-4 对偶图与着色 217

6-5 二分图与匹配 219

6-5-1 二分图 219

6-5-2 匹配 221

习题三 226

学习提要三 233

第四篇 代数结构 241

第七章 代数结构的基本知识 242

7-1 代数系统的基本概念 242

7-2 同构与同态 249

第八章 半群与群 260

8-1 半群、循环半群与幺半群 260

8-2 群 264

8-3 置换群与对称群 267

8-4 循环群 271

8-5 陪集与拉格朗日定理 275

第九章 环与域 279

9-1 环与幺环 279

9-2 整环与除环 280

9-3 域 284

第十章 格与布尔代数 287

10-1 格与代数系统 287

10-2 布尔格与布尔代数 294

10-3 布尔代数的另一理论体系 299

10-4 布尔表达式与布尔函数 303

习题四 309

学习提要四 316

第五篇 离散数学在计算机科学技术中的应用 325

第十一章 用计算机化简逻辑函数 326

11-1 自动化简逻辑函数的算法 326

11-2 用对合法寻找逻辑函数基本项 327

11-3 用覆盖法寻找必需项 329

11-4 用(准)必需项选拔法选取基本项 330

11-5 逻辑函数化简实例 332

12-1-1 语言的表示 335

第十二章 形式语言与自动机 335

12-1 语言的概念及运算 335

12-1-2 字母表和串 336

12-1-3 语言的概念及运算 338

12-2 文法及语言 342

12-2-1 文法(语法) 342

12-2-2 文法的类型 347

12-2-3 上下文(前后文)有关文法及语言(1型) 348

12-2-4 上下文(前后文)无关文法及语言(2型) 349

12-2-5 有限状态文法及语言 356

12-3 有限自动机 359

12-3-1 自动机与形式文法的关系 359

12-3-2 有限自动机的基本概念 360

12-3-3 有限自动机及其表示法 362

12-3-4 有限自动机的等价 364

12-3-5 状态赋值自动机 365

12-3-6 有限自动机的简化 369

12-3-7 有限识别器 374

12-3-8 确定的有限识别器与不确定的有限识别器 375

12-3-9 有限识别器与有限状态文法 378

12-3-10 有限识别器的另一形式 379

12-4 下推自动机 381

12-4-1 下推自动机的概念 381

12-4-2 下推自动机的例子 383

12-5 线性有界自动机 385

12-5-1 线性有界自动机的概念 385

12-5-2 线性有界自动机的例子 386

12-6-1 五重组图灵机 390

12-6 图灵机 390

12-6-2 波斯特—图灵机 395

12-6-3 图灵机用于计算 401

12-6-4 图灵识别器 406

12-6-5 通用图灵机与图灵停机问题 409

习题五 410

学习提要五 414

习题答案与提示 420

符号表 445

参考文献 450