离散数学PDF电子书下载

第1章 离散数学基础 3

1.1 算法 3

1.1.1 算法的定义 3

1.1.2 算法的基本特征 4

1.1.3 算法设计方法 5

1.1.4 算法表示 12

1.1.5 算法的复杂度分析 17

1.2 可计算性问题 20

1.3 模和同余 22

1.4 递归 25

1.5 密码学初步 28

1.6 计数 29

小结 30

习题 31

第2章 命题逻辑 34

2.1 命题与联结词 35

2.1.1 命题及其表示 35

2.1.2 联结词 36

2.1.3 最小功能完备集 42

2.2 命题公式与重言式 44

2.2.1 命题公式 44

2.2.2 指派与真值表 44

2.2.3 重言式 46

2.3 范式 48

2.3.1 对偶原理 48

2.3.2 范式 49

2.3.3 主析取范式 51

2.3.4 主合取范式 54

2.4 基于命题的推理 57

2.4.1 推理理论 57

2.4.2 CP规则 61

2.4.3 归谬法 62

小结 64

习题 65

第3章 谓词逻辑 69

3.1 谓词 69

3.2 量词 70

3.2.1 全称量词 70

3.2.2 存在量词 70

3.2.3 量词分析 73

3.3 谓词公式 74

3.4 谓词演算 75

3.5 谓词演算中的推理规则 76

3.5.1 推理规则 76

3.5.2 含有量词的永真式 79

3.6 三元谓词向二元谓词的转换 80

3.7 基于谓词的知识表示 81

3.8 基于谓词演算的程序正确性证明 83

小结 85

习题 85

第4章 集合论 89

4.1 集合的基本概念 89

4.1.1 集合及其表示 89

4.1.2 子集 91

4.1.3 基数 93

4.1.4 幂集 93

4.1.5 悖论 94

4.2 集合的运算 97

4.2.1 集合的并与交 97

4.2.2 集合的差与补 98

4.2.3 环和与环积 99

4.2.4 集合的笛卡儿积 100

4.3 集合运算定律 102

4.4 集合计数 104

4.5 可列集与无限集 107

4.6 集合的计算机表示 109

4.7 自然数集合与数学归纳法 109

小结 111

习题 111

第5章 关系 116

5.1 关系的基本概念 116

5.2 二元关系 119

5.3 二元关系的表示 121

5.3.1 集合表示法 121

5.3.2 关系图 121

5.3.3 关系矩阵 122

5.3.4 表格法 124

5.4 关系的基本性质 124

5.4.1 自反性 124

5.4.2 反自反性 125

5.4.3 对称性 126

5.4.4 反对称性 126

5.4.5 传递性 128

5.5 等价关系与集合划分 132

5.5.1 等价关系 133

5.5.2 等价类 134

5.5.3 集合的划分 136

5.6 相容关系与集合覆盖 138

5.6.1 相容关系 138

5.6.2 相容类 138

5.6.3 覆盖 141

5.7 偏序关系与哈斯图 142

5.7.1 哈斯图与偏序集 142

5.7.2 偏序集中的特殊元素 144

5.8 关系运算 146

5.8.1 复合关系和逆关系 147

5.8.2 逆关系 148

5.8.3 限制与闭包 149

小结 150

习题 151

第6章 函数 155

6.1 函数的定义 156

6.2 特殊函数 158

6.3 函数的运算 160

6.3.1 函数合成 160

6.3.2 逆函数 162

小结 165

习题 165

第7章 图论 168

7.1 图的基本概念 168

7.1.1 图的基本概念 168

7.1.2 度 169

7.1.3 正则图与完全图 170

7.1.4 子图与补图 171

7.1.5 赋权图 172

7.1.6 同构图 172

7.2 图的存储 173

7.2.1 邻接矩阵 173

7.2.2 边目录表示法 175

7.2.3 邻接编目法 175

7.2.4 多重链表 176

7.2.5 十字链表 176

7.3 连通与回路 177

7.3.1 可达与连通 177

7.3.2 欧拉图 180

7.3.3 汉密尔顿图 182

7.4 平面图与对偶图 183

7.4.1 平面图 183

7.4.2 对偶图 186

7.5 二部图与匹配 188

7.6 网络规划 190

7.6.1 规划图 191

7.6.2 结构与优化 192

7.6.3 规划图的绘制 195

7.6.4 规划图参数 197

7.6.5 规划图的优化分析 201

7.7 最短路径模型 205

7.8 图的着色 210

7.9 自补图 210

小结 213

习题 214

第8章 树 218

8.1 无向树 218

8.2 生成树 219

8.3 有向树 221

8.4 二叉树 223

8.5 二叉树的遍历 225

8.6 代数表达式的波兰表示 227

8.7 前缀码与哈夫曼树 230

8.8 决策树 231

8.8.1 决策树实例分析 232

8.8.2 不确定事件的决策分析 234

8.8.3 逆推技术 235

8.8.4 临界值分析 237

8.9 树的存储 238

小结 240

习题 240

第9章 代数结构 245

9.1 代数运算 245

9.1.1 代数运算的基本概念 245

9.1.2 代数运算的表示 247

9.1.3 代数运算的性质 248

9.2 代数系统 250

9.2.1 代数系统的基本概念和表示 250

9.2.2 代数系统中的特殊元素 250

9.3 同构 255

小结 257

习题 257

第10章 群与环 259

10.1 群 260

10.1.1 半群 260

10.1.2 群 262

10.1.3 子群 265

10.1.4 元素的阶数 266

10.1.5 若干特殊群 267

10.2 环和域 272

10.2.1 环 272

10.2.2 域 273

小结 274

习题 275

第11章 格与布尔代数 277

11.1 格 277

11.2 布尔函数 280

11.2.1 布尔函数运算 280

11.2.2 布尔表达式 280

11.2.3 布尔代数中的恒等式 281

11.2.4 对偶性 283

11.2.5 布尔代数的研究意义 283

11.3 布尔函数的表示和构造 283

11.3.1 积之和展开式 283

11.3.2 函数的完备性 284

11.4 逻辑门电路设计 285

11.5 卡诺图 286

11.5.1 卡诺图概述 287

11.5.2 三变元卡诺图 288

11.5.3 四变元卡诺图 289

11.5.4 奎因·莫可拉斯基方法 291

小结 293

习题 293

第12章 附注 296

12.1 国外人物简介 296

12.1.1 欧几里得 296

12.1.2 斐波那契 297

12.1.3 笛卡儿 298

12.1.4 费马 298

12.1.5 欧拉 300

12.1.6 高斯 301

12.1.7 巴贝奇 303

12.1.8 汉密顿 306

12.1.9 黎曼 306

12.1.10 康托尔 307

12.1.11 希尔伯特 309

12.1.12 罗素 309

12.1.13 图灵 310

12.1.14 迪卡斯特拉 310

12.1.15 Ike Nassi 311

12.1.16 哈夫曼 311

12.1.17 刘维尔 312

12.1.18 香农 313

12.1.19 泊松 314

12.1.20 阿贝尔 315

12.1.21 拉格朗日 316

12.1.22 伽罗华 319

12.1.23 卡诺 320

12.2 国内人物简介 320

12.2.1 华罗庚 320

12.2.2 闵嗣鹤 322

12.2.3 柯召 323

12.2.4 王元 325

12.2.5 陈景润 326

12.2.6 潘承洞 327

12.2.7 管梅谷 328

12.3 名词解释 328

12.3.1 图灵机 328

12.3.2 图灵试验 328

12.3.3 图灵奖 329

12.3.4 希尔伯特的23个问题 329

12.3.5 哈斯图 332

参考文献 333