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

第1章 命题逻辑 1

1.1 命题和逻辑连接词 2

1.1.1 命题 2

1.1.2 逻辑连接词与命题符号化 3

1.1.3 字位运算与布尔检索 7

习题1.1 8

1.2 命题公式及其等价演算 9

1.2.1 命题公式及其真值表 9

1.2.2 命题公式的等价演算 12

习题1.2 15

1.3.1 析取范式与合取范式 17

1.3 命题公式的范式 17

1.3.2 标准析取范式和标准合取范式 19

13.3 利用真值表求解标准范式 21

习题1.3 25

1.4 逻辑连接词完备集 26

习题1.4 28

1.5 命题公式的推理演算 29

1.5.1 基本概念与基本公式 29

1.5.2 演绎推理方法 31

1.5.3 附加前提法 32

习题1.5 34

1.6 对偶原理 36

习题1.6 38

第1章 上机练习 39

第2章 谓词逻辑 40

2.1 个体词、谓词与量词 40

2.1.1 个体词与谓词 40

2.1.2 量词 41

习题2.1 44

2.2 谓词公式及其解释 45

2.2.1 谓词公式 45

2.2.2 谓词公式的解释 47

习题2.2 50

2.3 谓词公式的等价演算与范式 51

2.3.1 基本概念与基本公式 51

2.3.2 等价演算 53

2.3.3 前束范式 53

习题2.3 54

2.4 谓词公式的推理演算 55

2.4.1 基本概念与基本公式 55

2.4.2 演绎推理方法 57

习题2.4 61

第2章 上机练习 63

3.1.1 集合的基本概念 64

第3章 集合与关系 64

3.1 集合及其运算 64

3.1.2 集合的运算 67

3.1.3集合的计算机表示 70

习题3.1 71

3.2 二元关系及其运算 73

3.2.1 笛卡儿积 73

3.2.2 二元关系及其表示 74

3.2.3 二元关系的运算 76

习题3.2 79

3.3.1 二元关系的性质 80

3.3 二元关系的性质与闭包 80

3.3.2 二元关系的闭包 83

习题3.3 86

3.4 等价关系与划分 88

习题3.4 91

3.5 函数 92

3.5.1 函数的基本概念 92

3.5.2 复合函数与逆函数 94

3.5.3 个重要的函数 96

习题3.5 98

3.6.1 集合的等势 100

3.6 集合的等势与基数 100

3.6.2 集合的基数 103

习题3.6 105

3.7 多元关系及其应用 105

3.7.1 多元关系 105

3.7.2 关系数据库 107

3.7.3 数据库的检索 108

3.7.4 插入、删除与修改 110

习题3.7 111

第3章 上机练习 112

4.1.1 基本概念 114

第4章 群、环、域 114

4.1 代数运算 114

4.1.2 二元运算的性质 115

习题4.1 118

4.2 半群与群 119

4.2.1 半群 119

4.2.2 群 121

习题4.2 123

4.3 群的性质、循环群 125

4.3.1 群的性质 125

4.3.2 循环群 128

习题4.3 129

4.4 子群、置换群 130

4.4.1 子群 130

4.4.2 对称群与置换群 132

习题4.4 134

4.5 陪集与商群 135

4.5.1 陪集 135

4.5.2 正规子群与商群 138

习题4.5 139

4.6 同态与同构 140

4.6.1 基本概念与基本性质 140

4.6.2 群同态基本定理 144

习题4.6 145

4.7 环与域 147

4.7.1 环 147

4.7.2 整环与域 149

习题4.7 151

第4章 上机练习 152

第5章 格与布尔代数 153

5.1 偏序关系与偏序集 153

5.1.1 基本概念 153

5.1.2 偏序集中的特殊元素 155

5.1.3 字典序与拓扑排序 157

习题5.1 159

5.2 格 162

5.2.1 基本概念与基本性质 162

5.2.2 子格与格同态 165

5.2.3 几种特殊的格 167

习题5.2 170

5.3 布尔代数 171

5.3.1 布尔代数及其性质 171

5.3.2 布尔函数与布尔表达式 174

习题5.3 176

5.4.1 门电路 177

5.4 逻辑门电路 177

5.4.2 逻辑电路设计 179

习题5.4 181

第5章 上机练习 181

第6章图论 183

6.1图的概念 183

6.1.1 基本概念 183

6.1.2 子图，图的同构 188

习题6.1 190

6.2 图的连通性 191

6.2.1 路 191

6.2.2 连通图 193

习题6.2 195

6.3 割点、割边、割集与连通度 196

6.3.1 割点、割边与割集 196

6.3.2 连通度 198

习题6.3 200

6.4 树与生成树 201

6.4.1 树 201

6.4.2 生成树 203

习题6.4 205

6.5.1 最短路问题 206

6.5 最短路与最小生成树 206

6.5.2 最小生成树 208

习题6.5 211

6.6 欧拉图与哈密尔顿图 213

6.6.1 欧拉图 213

6.6.2 中国邮递员问题与最短路问题 215

6.6.3 哈密尔顿图 216

6.6.4 旅行商问题 219

习题6.6 220

6.7 平面图及图的着色 221

6.7.1 平面图 221

6.7.2 图的点着色 226

习题6.7 230

6.8 图的矩阵表示 232

习题6.8 235

第6章 上机练习 236

第7章 有向图 237

7.1 有向图概述 237

7.1.1 基本概念 237

7.1.2 有向图的连通性 238

7.1.3 有向图的矩阵表示 240

习题7.1 242

7.2.1 基本概念 244

7.2 有向树 244

7.2.2 最优二叉树及其应用 247

习题7.2 251

7.3 有向网络模型 252

7.3.1 引言 252

7.3.2 最大流算法 254

7.3.3 最大流最小割定理 260

习题7.3 261

7.4 匹配 263

习题7.4 266

第7章 上机练习 267

参考文献 268