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

第1章 命题逻辑 1

1.1 命题与逻辑联结词 2

1.1.1 命题的概念 2

1.1.2 逻辑联结词 3

1.1.3 原子命题和复合命题 6

1.1.4 应用 6

习题1.1 7

1.2 命题公式及公式分类 8

1.2.1 命题公式的概念 8

1.2.2 命题公式的分类 8

1.2.3 应用 10

习题1.2 10

1.3 等值式与等值演算 11

1.3.1 基本等值式 11

1.3.2 等值演算 12

1.3.3 应用 13

习题1.3 15

1.4 范式与主范式 16

1.4.1 范式 16

1.4.2 主范式 17

1.4.3 应用 20

习题1.4 21

1.5 推理理论 22

1.5.1 形式证明 23

1.5.2 应用 26

习题1.5 29

第2章 谓词逻辑 30

2.1 基本概念 30

2.1.1 个体与谓词 30

2.1.2 量词 32

习题2.1 33

2.2 谓词公式 34

2.2.1 谓词公式概述 34

2.2.2 谓词公式的类型 35

习题2.2 38

2.3 谓词逻辑蕴含式和等值式 38

2.3.1 谓词逻辑蕴含式和等值式 38

2.3.2 量词的收缩与扩张 39

2.3.3 常用的量词等值式 40

2.3.4 多个量词的使用 41

习题2.3 42

2.4 前束范式 42

2.4.1 前束范式 42

2.4.2 前束合取范式 43

2.4.3 前束析取范式 43

习题2.4 44

2.5 谓词逻辑推理理论 44

习题2.5 47

2.6 应用 48

2.6.1 人工智能中的归结演绎推理 48

2.6.2 基本思路 51

2.6.3 使用步骤 52

2.6.4 完备性 52

2.6.5 举例说明 52

第3章 关系 54

3.1 笛卡儿积 54

3.1.1 有序对 54

3.1.2 笛卡儿积 55

3.1.3 知识点：笛卡儿积与数据库 57

3.1.4 拓展 58

习题3.1 59

3.2 关系的概念与表示方法 60

3.2.1 关系的基本概念 60

3.2.2 拓展：n-ary关系与关系型数据库 61

3.2.3 关系矩阵与关系图 64

习题3.2 66

3.3 关系的运算 66

3.3.1 关系的逆运算 66

3.3.2 关系的复合运算 68

3.3.3 关系的幂 70

习题3.3 70

3.4 关系的性质 71

习题3.4 74

3.5 关系的闭包 76

3.5.1 关系闭包的概念 76

3.5.2 关系闭包的求法 76

3.5.3 拓展 79

习题3.5 80

3.6 关系等价与划分 80

3.6.1 等价关系 80

3.6.2 等价类 82

3.6.3 集合的划分 84

3.6.4 划分与等价关系 85

3.6.5 应用 86

习题3.6 88

3.7 偏序关系 89

3.7.1 偏序和拟序 89

3.7.2 哈斯图 90

3.7.3 偏序关系的应用 93

习题3.7 94

第4章 函数 96

4.1 函数的概念 97

4.1.1 函数的基本概念 97

4.1.2 拓展 99

习题4.1 101

4.2 特殊函数 101

习题4.2 103

4.3 逆函数与复合函数 103

4.3.1 逆函数 103

4.3.2 复合函数 104

习题4.3 107

4.4 几个重要的函数 108

4.4.1 取整函数 108

4.4.2 序列和字符串 109

4.4.3 拓展 110

4.5 函数的应用 111

4.5.1 数字图像的函数模型 111

4.5.2 函数在数字图像平滑处理中的应用 111

4.5.3 二维图像的梯度函数（算子）分析 113

第5章 代数系统 115

5.1 二元运算与代数系统 115

5.1.1 运算 115

5.1.2 二元运算的性质 116

5.1.3 二元运算的特殊元素 119

5.1.4 代数系统的定义 122

5.1.5 应用 122

习题5.1 123

5.2 子代数与积代数 124

5.2.1 子代数 124

5.2.2 积代数 125

习题5.2 126

5.3 代数系统的同态与同构 126

5.3.1 同态与同构的概念 126

5.3.2 满同态的性质 128

5.3.3 应用 129

习题5.3 132

第6章 几个特殊的代数系统 133

6.1 半群 133

6.1.1 半群 133

6.1.2 独异点 134

6.1.3 拓展 134

习题6.1 135

6.2 群与子群 135

6.2.1 群的定义 135

6.2.2 群的性质 137

6.2.3 子群 139

6.2.4 应用 141

习题6.2 143

6.3 循环群与置换群 143

6.3.1 循环群 143

6.3.2 置换群 144

6.3.3 应用：置换群与pólya定理 145

习题6.3 146

6.4 环和域 147

6.4.1 环的定义及其性质 147

6.4.2 域的定义 150

习题6.4 151

第7章 图论基础 152

7.1 图的定义及相关概念 153

7.1.1 图的定义 153

7.1.2 顶点的度数 154

7.1.3 补图和子图 156

7.1.4 同构 157

习题7.1 158

7.2 通路、回路与连通图 158

7.2.1 通路与回路 159

7.2.2 连通图 159

习题7.2 160

7.3 图的矩阵表示 161

7.3.1 邻接矩阵 162

7.3.2 关联矩阵 164

7.3.3 可达矩阵 165

习题7.3 166

7.4 欧拉图与哈密顿图 167

7.4.1 欧拉图 167

7.4.2 哈密顿图 169

7.4.3 哈密顿回路算法的实现 170

习题7.4 171

7.5 最短路径问题与货郎担问题 172

7.5.1 最短路径问题 172

7.5.2 货郎担问题（旅行商问题） 174

习题7.5 175

7.6 平面图和图的着色 175

7.6.1 基本概念 175

7.6.2 图的m着色问题算法的实现 178

习题7.6 179

7.7 应用 179

7.7.1 考试安排问题 179

7.7.2 ACM竞赛题 180

第8章 树 185

8.1 无向树及性质 185

8.1.1 树的定义 185

8.1.2 树的性质 186

习题8.1 188

8.2 根树 188

8.2.1 根树及相关概念 188

8.2.2 二叉树 189

8.2.3 二叉搜索树 193

8.2.4 应用：哈夫曼编码 194

习题8.2 196

8.3 生成树 197

8.3.1 生成树概念 197

8.3.2 最小生成树 199

8.3.3 Kruskal算法 199

8.3.4 Prim算法 201

习题8.3 202

8.4 树在ACM竞赛题中的应用 203

8.4.1 百岛湖问题 203

8.4.2 NTA问题 205

第9章 格与布尔代数 211

9.1 格 212

9.1.1 格的定义与性质 212

9.1.2 应用：信息流的格模型 215

习题9.1 215

9.2 特殊的格 215

9.2.1 分配格 215

9.2.2 有界格和有补格 217

习题9.2 218

9.3 布尔代数 218

9.3.1 基本概念 218

9.3.2 应用：逻辑门 219

习题9.3 221

专用术语汉英对照 222

参考文献 229