“十二五”普通高等教育本科国家级规划教材 离散数学教程PDF电子书下载

第1章 逻辑代数（上）：命题演算 1

1.1 逻辑联结词与命题公式 1

1.1.1 命题 1

1.1.2 逻辑联结词 2

1.1.3 命题公式 6

1.1.4 语句形式化 8

练习1.1 9

1.2 命题演算永真式 12

1.2.1 重言式 12

1.2.2 逻辑等价式与逻辑蕴涵式 12

1.2.3 对偶原理 16

1.2.4 逻辑应用 18

练习1.2 20

1.3 范式 22

1.3.1 析取范式与合取范式 22

1.3.2 主析取范式与主合取范式 24

1.3.3 联结词的扩充与归约 26

练习1.3 29

1.4 命题演算消解原理 30

练习1.4 33

1.5 阅读材料：布尔代数 33

第2章 逻辑代数（下）：谓词演算 37

2.1 谓词演算基本概念 37

2.1.1 个体 38

2.1.2 谓词 38

2.1.3 量词 39

2.1.4 谓词公式及语句形式化 41

练习2.1 44

2.2 谓词演算永真式 47

2.2.1 谓词公式的语义 47

2.2.2 几组谓词演算永真式 49

2.2.3 谓词公式等价变换的几个基本原理 52

练习2.2 54

2.3 谓词演算消解原理 56

2.3.1 前束化与消去量词 56

2.3.2 谓词演算消解原理简介 59

练习2.3 60

2.4 阅读材料：形式推理与形式系统 62

2.4.1 一个形式系统的例子 62

2.4.2 自然推理形式系统ND 62

第3章 集合代数 67

3.1 集合的概念与表示 67

3.1.1 集合基本概念 67

3.1.2 集合的表示 69

3.1.3 外延性原理与子集合 70

练习3.1 71

3.2 集合运算 73

3.2.1 并、交、差、补运算 73

3.2.2 环和与环积运算 76

3.2.3 幂集与广义并、交运算 78

练习3.2 81

3.3 集合的笛卡儿积 83

练习3.3 85

3.4 集合的归纳定义 85

3.4.1 集合的归纳定义方法 85

3.4.2 集合定义的自然数 87

练习3.4 89

3.5 归纳法证明 89

3.5.1 结构归纳法 90

3.5.2 数学归纳法 91

练习3.5 95

3.6 阅读材料：公理化集合论简介 95

第4章 计数 99

4.1 计数基本原理 99

4.1.1 加法原理与乘法原理 99

4.1.2 包含排斥原理 100

练习4.1 103

4.2 鸽笼原理 104

4.2.1 鸽笼原理基本形式 104

4.2.2 鸽笼原理加强形式 106

练习4.2 107

4.3 排列与组合 108

4.3.1 排列的计数 108

4.3.2 组合的计数 109

练习4.3 112

4.4 重集的排列与组合 113

4.4.1 重集的排列 113

4.4.2 重集的组合 116

4.4.3 错置的计数 118

练习4.4 121

4.5 递归式及其应用 122

4.5.1 递归式建模 122

4.5.2 递归式求解 124

练习4.5 133

4.6 阅读材料：母函数 134

第5章 关系 139

5.1 关系 139

5.1.1 关系及二元关系 139

5.1.2 关系基本运算 143

5.1.3 关系数据库中的关系运算 148

5.1.4 关系的基本特性 149

5.1.5 关系的特性闭包 153

练习5.1 156

5.2 等价关系 159

5.2.1 等价关系及其等价类 159

5.2.2 等价关系与划分 161

5.2.3 等价关系的应用 162

练习5.2 163

5.3 相容关系 165

5.3.1 相容关系与相容类 165

5.3.2 相容关系与覆盖 166

练习5.3 169

5.4 序关系 170

5.4.1 序关系与有序集 170

5.4.2 全序集与良序集 174

5.4.3 有序集的应用 176

练习5.4 177

5.5 阅读材料：格 179

第6章 函数 183

6.1 函数及函数的合成 183

6.1.1 函数基本概念 183

6.1.2 函数的合成 186

6.1.3 函数的递归定义 188

练习6.1 190

6.2 特殊函数类 191

6.2.1 单射、满射与双射 192

6.2.2 函数的逆 194

6.2.3 谓词、集合、函数的统一描述与模糊子集 197

练习6.2 198

6.3 有限集与无限集 200

6.3.1 有限集、可数集与不可数集 200

6.3.2 无限集的特性 204

练习6.3 205

6.4 阅读材料：集合基数与基数比较 206

第7章 可计算函数 210

7.1 函数概念的拓广 210

练习7.1 212

7.2 初等函数 212

7.2.1 初等函数集 212

7.2.2 初等谓词 216

练习7.2 219

7.3 原始递归函数 220

7.3.1 初等函数集的不足 220

7.3.2 原始递归式 221

7.3.3 原始递归函数集 222

练习7.3 225

7.4 递归函数 225

7.4.1 阿克曼函数及其性质 225

7.4.2 μ-递归式 227

7.4.3 递归函数集（μ-递归函数集） 229

练习7.4 230

7.5 阅读材料：图灵机 231

7.5.1 图灵机的组成 231

7.5.2 图灵可计算函数 234

第8章 图与树 237

8.1 图 238

8.1.1 图的基本概念 238

8.1.2 结点的度 240

8.1.3 子图、补图及图同构 241

8.1.4 图的应用 243

练习8.1 244

8.2 路径、回路及连通性 246

8.2.1 路径、通路与回路 246

8.2.2 连通性 247

8.2.3 连通度 250

练习8.2 251

8.3 图的矩阵表示 253

8.3.1 邻接矩阵 253

8.3.2 路径矩阵与可达性矩阵 255

练习8.3 257

8.4 树 257

8.4.1 树的基本概念 258

8.4.2 生成树 259

8.4.3 生成树的构造 262

8.4.4 最小生成树 264

练习8.4 266

8.5 阅读材料：图搜索算法 268

8.5.1 图搜索算法（A算法） 269

8.5.2 启发式图搜索算法（A算法） 271

第9章 特殊图 272

9.1 欧拉图与哈密顿图 272

9.1.1 欧拉图及欧拉路径 273

9.1.2 哈密顿图及哈密顿通路 275

9.1.3 欧拉图与哈密顿图的应用 279

练习9.1 280

9.2 二分图 282

9.2.1 二分图基本概念 282

9.2.2 二分图的匹配及其应用 284

练习9.2 287

9.3 平面图 288

9.3.1 平面图基本概念 288

9.3.2 欧拉公式与库拉托夫斯基定理 290

9.3.3 平面图的应用：着色问题 295

练习9.3 297

9.4 根树 298

9.4.1 根树的概念 298

9.4.2 二元树的性质及应用 300

9.4.3 最短路径问题 305

练习9.4 308

9.5 有向无环图 310

9.5.1 有向无环图基本概念 310

9.5.2 拓扑排序 312

9.5.3 关键路径 315

练习9.5 319

9.6 阅读材料：博弈树与智能博弈 320

第10章 代数结构通论 324

10.1 代数结构 324

10.1.1 代数结构的组成 324

10.1.2 代数结构的特殊元素 326

10.1.3 子代数 329

练习10.1 330

10.2 同态与同构 332

练习10.2 336

10.3 同余关系 337

10.3.1 同余关系的意义 337

10.3.2 同态与同余关系 338

10.3.3 同余关系的应用 339

练习10.3 342

10.4 阅读材料：正则语言及其代数性质 343

第11章 群、环、域 348

11.1 半群 348

11.1.1 半群及独异点 348

11.1.2 自由独异点 349

练习11.1 351

11.2 群 352

11.2.1 群及其基本性质 353

11.2.2 群的元素的阶 356

11.2.3 子群、陪集与拉格朗日定理 357

11.2.4 正规子群与商群 360

练习11.2 362

11.3 循环群与置换群 364

11.3.1 循环群 364

11.3.2 置换群 365

11.3.3 置换群的应用 368

练习11.3 372

11.4 环和域 373

11.4.1 环 373

11.4.2 域 377

练习11.4 380

11.5 阅读材料：有穷自动机 380

11.5.1 有穷自动机 380

11.5.2 状态迁移幺半群 383

11.5.3 语言同余关系 384

参考文献 387