离散数学学习指导 科学版PDF电子书下载

第一篇 数理逻辑 3

第1章 命题逻辑 3

1.1 命题与联结词 3

1.1.1 基本知识 3

1.1.2 例题 5

1.1.3 习题 8

1.2 命题公式 9

1.2.1 基本知识 9

1.2.2 例题 10

1.2.3 习题 13

1.3 等值演算 14

1.3.1 基本知识 14

1.3.2 例题 16

1.3.3 习题 18

1.4 命题公式的范式 19

1.4.1 基本知识 19

1.4.2 例题 22

1.4.3 习题 25

1.5 联结词的功能完全集 25

1.5.1 基本知识 25

1.5.2 例题 27

1.5.3 习题 30

1.6 永真蕴涵式 30

1.6.1 基本知识 30

1.6.2 例题 32

1.6.3 习题 35

1.7 命题逻辑的推理理论 36

1.7.1 基本知识 36

1.7.2 例题 37

1.7.3 习题 39

1.8 命题逻辑推理的机械化方法 40

1.8.1 基本知识 40

1.8.2 例题 42

1.8.3 习题 46

第2章 一阶逻辑 47

2.1 一阶逻辑的基本概念 47

2.1.1 基本知识 47

2.1.2 例题 48

2.1.3 习题 50

2.2 一阶逻辑公式 52

2.2.1 基本知识 52

2.2.2 例题 54

2.2.3 习题 58

2.3 一阶逻辑的等值演算与前束范式 59

2.3.1 基本知识 59

2.3.2 例题 59

2.3.3 习题 62

2.4 一阶逻辑的推理理论 62

2.4.1 基本知识 62

2.4.2 例题 63

2.4.3 习题 69

第二篇 集合论 73

第3章 集合 73

3.1 集合的定义 73

3.1.1 基本知识 73

3.1.2 例题 74

3.1.3 习题 76

3.2 集合的基本运算 77

3.2.1 基本知识 77

3.2.2 例题 80

3.2.3 习题 84

3.3 有限集合的计数 86

3.3.1 基本知识 86

3.3.2 例题 87

3.3.3 习题 89

3.4 集合表达式的相等与包含 90

3.4.1 基本知识 90

3.4.2 例题 92

3.4.3 习题 95

3.5 集合的特征函数 96

3.5.1 基本知识 96

3.5.2 例题 97

3.5.3 习题 98

第4章 关系 99

4.1 二元关系 99

4.1.1 基本知识 99

4.1.2 例题 100

4.1.3 习题 101

4.2 二元关系的表示及按性质分类 102

4.2.1 基本知识 102

4.2.2 例题 104

4.2.3 习题 108

4.3 二元关系的运算 110

4.3.1 基本知识 110

4.3.2 例题 110

4.3.3 习题 113

4.4 二元关系的合成 114

4.4.1 基本知识 114

4.4.2 例题 115

4.4.3 习题 118

4.5 关系的闭包 119

4.5.1 基本知识 119

4.5.2 例题 120

4.5.3 习题 123

4.6 等价关系和偏序关系 124

4.6.1 基本知识 124

4.6.2 例题 126

4.6.3 习题 128

第5章 函数 130

5.1 函数的基本概念 130

5.1.1 基本知识 130

5.1.2 例题 130

5.1.3 习题 131

5.2 函数的性质 132

5.2.1 基本知识 132

5.2.2 例题 132

5.2.3 习题 135

5.3 函数的复合与反函数 136

5.3.1 基本知识 136

5.3.2 例题 137

5.3.3 习题 138

5.4 可逆函数集与置换 139

5.4.1 基本知识 139

5.4.2 例题 140

5.4.3 习题 141

5.5 二元运算 141

5.5.1 基本知识 141

5.5.2 例题 142

5.5.3 习题 144

5.6 基数 145

5.6.1 基本知识 145

5.6.2 例题 147

5.6.3 习题 148

第三篇 代数系统 153

第6章 半群、语言和自动机 153

6.1 半群与语言 153

6.1.1 基本知识 153

6.1.2 例题 155

6.1.3 习题 156

6.2 语言和文法 157

6.2.1 基本知识 157

6.2.2 例题 158

6.2.3 习题 160

6.3 有限状态机 161

6.3.1 基本知识 161

6.3.2 例题 162

6.3.3 习题 163

6.4 有限状态自动机 163

6.4.1 基本知识 163

6.4.2 例题 165

6.4.3 习题 167

6.5 语言与自动机的关系 169

6.5.1 基本知识 169

6.5.2 例题 170

6.5.3 习题 174

第7章 群、环和域 175

7.1 群的基本概念 175

7.1.1 基本知识 175

7.1.2 例题 177

7.1.3 习题 177

7.2 子群 177

7.2.1 基本知识 177

7.2.2 例题 178

7.2.3 习题 179

7.3 群的同态与同构 179

7.3.1 基本知识 179

7.3.2 例题 180

7.3.3 习题 181

7.4 子群的陪集 181

7.4.1 基本知识 181

7.4.2 例题 183

7.4.3 习题 183

7.5 对称群、置换群、正规性与商群 183

7.5.1 基本知识 183

7.5.2 例题 185

7.5.3 习题 186

7.6 群在集合上的作用 186

7.6.1 基本知识 186

7.6.2 例题 187

7.6.3 习题 189

7.7 同态基本定理与同构定理 190

7.7.1 基本知识 190

7.7.2 例题 190

7.7.3 习题 191

7.8 环的基本概念 191

7.8.1 基本知识 191

7.8.2 例题 192

7.8.3 习题 193

7.9 子环、理想与商环 194

7.9.1 基本知识 194

7.9.2 例题 195

7.9.3 习题 196

7.10 交换环中的因子分解 197

7.10.1 基本知识 197

7.10.2 例题 198

7.10.3 习题 199

7.11 多项式环 200

7.11.1 基本知识 200

7.11.2 例题 200

7.11.3 习题 201

7.12 多项式环的因子分解 202

7.12.1 基本知识 202

7.12.2 例题 203

7.12.3 习题 203

7.13 域的基本概念 204

7.13.1 基本知识 204

7.13.2 例题 205

7.13.3 习题 206

7.14 分裂域 206

7.14.1 基本知识 206

7.14.2 例题 207

7.14.3 习题 208

7.15 有限域 208

7.15.1 基本知识 208

7.15.2 例题 209

7.15.3 习题 210

第8章 格与布尔代数 211

8.1 格的概念 211

8.1.1 基本知识 211

8.1.2 例题 213

8.1.3 习题 214

8.2 分配格 215

8.2.1 基本知识 215

8.2.2 例题 216

8.2.3 习题 217

8.3 有补格 217

8.3.1 基本知识 217

8.3.2 例题 218

8.3.3 习题 218

8.4 布尔代数 219

8.4.1 基本知识 219

8.4.2 例题 220

8.4.3 习题 220

8.5 布尔表达式 221

8.5.1 基本知识 221

8.5.2 例题 222

8.5.3 习题 222

8.6 数字电路与最小化 223

8.6.1 基本知识 223

8.6.2 例题 225

8.6.3 习题 226

第四篇 组合分析与算法数论 229

第9章 组合分析 229

9.1 计数 229

9.1.1 基本知识 229

9.1.2 例题 229

9.1.3 习题 230

9.2 排列与组合 231

9.2.1 基本知识 231

9.2.2 例题 232

9.2.3 习题 235

9.3 递推序列 235

9.3.1 基本知识 235

9.3.2 例题 236

9.3.3 习题 241

9.4 抽屉原理 242

9.4.1 基本知识 242

9.4.2 例题 242

9.4.3 习题 245

9.5 生成函数 246

9.5.1 基本知识 246

9.5.2 例题 247

9.5.3 习题 250

第10章 算法数论 252

10.1 算法 252

10.1.1 基本知识 252

10.1.2 例题 257

10.1.3 习题 258

10.2 整数论 259

10.2.1 基本知识 259

10.2.2 例题 263

10.2.3 习题 264

10.3 与整数有关的典型算法 266

10.3.1 基本知识 266

10.3.2 例题 268

10.3.3 习题 269

10.4 素性测试、因数分解与公钥密码学 270

10.4.1 基本知识 270

10.4.2 例题 277

10.4.3 习题 280

10.5 有限域上的椭圆曲线算术和ECC 281

10.5.1 基本知识 281

10.5.2 例题 284

10.5.3 习题 286

10.6 配对和基于身份的公钥密码体制 287

10.6.1 双线性配对 287

10.6.2 基于身份的密码 291

第五篇 图论 297

第11章 图 297

11.1 图的基本概念 297

11.1.1 基本知识 297

11.1.2 例题 299

11.1.3 习题 302

11.2 连通性 303

11.2.1 基本知识 303

11.2.2 例题 304

11.2.3 习题 305

11.3 平面图 306

11.3.1 基本知识 306

11.3.2 例题 307

11.3.3 习题 308

11.4 欧拉道路与哈密顿道路 309

11.4.1 基本知识 309

11.4.2 例题 310

11.4.3 习题 312

第12章 有向图和树 314

12.1 有向图的基本概念 314

12.1.1 基本知识 314

12.1.2 例题 315

12.1.3 习题 317

12.2 有向图的连通性 317

12.2.1 基本知识 317

12.2.2 例题 318

12.2.3 习题 319

12.3 树 320

12.3.1 基本知识 320

12.3.2 例题 321

12.3.3 习题 323

12.4 二元树和Huffman树 323

12.4.1 基本知识 323

12.4.2 例题 324

12.4.3 习题 325

参考文献 327