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

第1章 基础知识 1

1.1集合与序列 1

1.1.1集合的基本概念 1

1.1.2集合的运算及性质 3

1.1.3序列 6

1.2数论基础 6

1.3计数基础 10

1.3.1加法法则与乘法法则 10

1.3.2排列与组合 11

1.3.3鸽巢原理 16

1.3.4有限集的计数——容斥原理 18

1.3.5递推关系 20

1.4布尔矩阵及其运算 23

习题一 25

第2章 命题逻辑 33

2.1命题逻辑的基本概念 33

2.2命题公式及其分类 37

2.3命题逻辑的等值演算 40

2.4对偶与范式 45

2.4.1对偶 45

2.4.2析取范式和合取范式 46

2.4.3主范式 48

2.5命题联结词的完备集 54

2.6命题逻辑的推理 56

习题二 62

第3章 谓词逻辑 70

3.1谓词、量词与自然语句形式化 70

3.1.1谓词 70

3.1.2量词 71

3.1.3自然语句形式化 72

3.2谓词公式及分类 74

3.3谓词逻辑的等值演算 77

3.4前束范式 81

3.5谓词逻辑的推理 82

习题三 89

第4章 二元关系 94

4.1关系及其表示 94

4.1.1有序对与笛卡儿积 94

4.1.2二元关系的定义 96

4.1.3二元关系的表示 98

4.2关系的运算 100

4.2.1关系的基本运算 100

4.2.2关系的幂和道路 103

4.3关系的性质 106

4.3.1关系性质的定义和判断 106

4.3.2关系运算对性质的保持 110

4.4关系的闭包 111

4.5等价关系和集合的划分 116

4.5.1等价关系、等价类和商集 117

4.5.2集合的划分 118

4.5.3等价关系与划分的一一对应 119

4.6关系在计算机中的表示方法 120

习题四 121

第5章 函数 128

5.1函数的定义 128

5.2函数的性质 129

5.3函数的复合 131

5.4逆函数 133

5.5计算机科学中的常用函数 134

5.6双射函数及集合的势 138

习题五 141

第6章 偏序关系 145

6.1偏序关系和偏序集 145

6.1.1偏序关系和偏序集的定义与性质 145

6.1.2积偏序和字典序 147

6.1.3哈斯图 148

6.2偏序集中的特殊元素 149

6.2.1偏序集中的特殊元素的定义 149

6.2.2拓扑排序 152

6.3格与布尔代数 154

6.3.1格的定义 154

6.3.2特殊的格 157

6.3.3布尔代数 160

习题六 161

第7章 代数结构 165

7.1代数结构运算及其性质 165

7.1.1运算与代数结构的定义 165

7.1.2二元运算的性质 167

7.2群 170

7.2.1半群与亚群 170

7.2.2群的概念 171

7.2.3群的性质 174

7.2.4子群 175

7.2.5循环群与置换群 176

7.2.6陪集与拉格朗日定理 178

7.3环与域 180

7.3.1环 180

7.3.2域 182

7.4作为代数结构的格与布尔代数 183

习题七 185

第8章 图论 193

8.1基本概念 193

8.1.1无向图、有向图和握手定理 193

8.1.2图的同构与子图 197

8.1.3道路、回路与连通性 200

8.1.4图的矩阵表示 201

8.2欧拉图 202

8.3哈密尔顿图 206

8.4平面图 210

8.5图的着色 215

习题八 219

第9章 树及其应用 227

9.1无向树 227

9.2支撑树及其应用 230

9.3最短道路树 239

9.4根树及其应用 243

9.4.1根树的定义和基本概念 243

9.4.2二叉树的遍历 246

9.4.3最优二叉树与霍夫曼编码 249

习题九 252

附录A课程综合实验 256

A.1实验一：汉诺塔问题的变体 256

A.1.1实验内容 256

A.1.2实验要求 256

A.2实验二：命题演算的计算机实现 257

A.3实验三：二元关系及其应用 258

A.3.1准备工作 258

A.3.2等价关系及其应用 259

A.3.3偏序关系及其应用 259

A.3.4连通性、欧拉道路和欧拉回路 261

A.4实验四：村庄修引水渠问题 262

A.4.1实验内容（一） 263

A.4.2实验内容（二） 263

A.4.3讨论与思考 264

A.5实验五：考场安排问题 265

A.5.1实验内容 265

A.5.2实验内容 266

A.6实验六：展览馆的参观与维护 266

附录B名词英汉对照表 267

附录C使用Mathernatica学习离散数学 276

C.1集合、序列与矩阵 276

C.2排列、组合、递推关系与划分 279

C.3关系与有向图 280

C.4图 285

C.5树 288

参考文献 290