离散数学PDF电子书下载

第一篇 数理逻辑 5

第一章 命题逻辑 5

1.1 命题和联结词 6

1.2 公式和真值赋值 10

1.3 等值演算 16

1.4 对偶定理 19

1.5 联结词的完全集 21

1.6 范式 25

1.7 逻辑推论 30

习题 32

第二章 谓词逻辑 39

2.1 谓词和量词 39

2.2 项和公式 45

2.3 解释和赋值 50

2.4 永真式 59

2.5 等值演算 64

2.6 逻辑推论 69

习题 71

第三章 公理系统 75

3.1 命题逻辑的公理系统 76

3.2 谓词逻辑的公理系统 82

习题 89

第四章 归结法原理 91

4.1 命题逻辑的归结法 91

4.2 前束范式与斯科伦范式 97

4.3 谓词逻辑的归结法 100

习题 110

参考文献 113

名词索引 114

第二篇 集合论 123

第五章 集合的基本概念及其运算 123

5.1 集合与元素 123

5.2 集合间的相等和包含关系 125

5.3 幂集 129

5.4 集合的运算 131

5.5 有穷集的计数原理 140

5.6 集合的归纳定义法 142

5.7 有序偶和笛卡儿乘积 148

习题 151

第六章 关系 154

6.1 关系及其性质 154

6.2 关系的运算 160

6.3 次序关系 169

6.4 等价关系、划分及其它 174

习题 181

第七章 函数 186

7.1 基本概念 186

7.2 函数的复合 192

7.3 特殊性质的函数 196

7.4 集合的特征函数 201

习题 203

第八章 自然数和基数 207

8.1 自然数及数学归纳法 207

8.2 基数 212

习题 221

名词索引 223

9.1 有向图及无向图 229

第九章 基本概念 229

第三篇 图论 229

9.2 图的基本结构 232

9.3 子图 236

9.4 连通性 239

9.5 顶点基和强分图 248

习题 253

第十章 通路问题 257

10.1 最短通路 257

10.2 关键通路 261

习题 266

第十一章 图的矩阵表示 268

11.1 邻接矩阵 268

11.2 有向图的可达性矩阵 272

11.3 关联矩阵 276

习题 277

第十二章 树 279

12.1 树的一般定义 279

12.2 根树与有序树 282

12.3 二元树 284

12.4 生成树 290

12.5 割集 294

习题 297

第十三章 穿程问题 300

13.1 欧拉图 300

13.2 哈密顿图 305

习题 309

第十四章 二分图的匹配问题 311

14.1 基本概念 311

14.2 二分图的最大匹配 314

14.3 从X到Y的匹配 317

习题 320

第十五章 平面图及色数 322

15.1 平面图 322

15.2 色数 330

习题 335

参考文献 337

名词索引 338

16.1 代数系统 343

第十六章 基本概念 343

第四篇 代数系统 343

16.2 同态和同构 347

16.3 子代数和商代数 349

习题 353

第十七章 半群和群 354

17.1 半群的概念 354

17.2 子半群和半群同态 356

17.3 商半群和半群直积 357

17.4 群的概念 359

17.5 子群和群的同态 362

17.6 变换群、置换群和循环群 365

17.7 不变子群和商群 367

习题 373

第十八章 环和域 375

18.1 环和域的概念 375

18.2 子环和环的同态 378

18.3 理想和商环 379

习题 382

19.1 格的定义与基本性质 384

第十九章 格和布尔代数 384

19.2 子格和格的同态 387

19.3 布尔代数 388

19.4 布尔代数的表示 391

习题 394

第二十章 抽象数据类型的代数规范 395

20.1 标记、项和代数规范 395

20.2 Σ--代数和范畴 402

20.3 代数规范的初始语义 404

习题 407

参考文献 409

名词索引 410

第五篇 有限自动机理论 415

第二十一章 基本概念 415

21.1 字符表、字符串及其集合的运算 415

21.2 有限自动机的定义 416

21.3 有限自动机的等价 423

21.4 Mealy机与Moore机 424

习题 429

22.1 最小有限自动机的定义及性质 431

第二十二章 有限自动机的简化 431

22.2 状态集的S划分和格LM 434

22.3 有限自动机的最小化 443

习题 451

第二十三章 有限自动机和正则表达式 453

23.1 有限自动机的识别功能 453

23.2 非确定有限自动机 455

23.3 正则表达式 460

23.4 由正则表达式构造FA的算法 463

23.5 有限自动机和正则表达式的等价性 472

23.6 正则集合及其性质 476

习题 478

第二十四章 有限自动机的综合与应用 481

24.1 有限自动机的综合 481

24.2 FA理论在算法设计中的应用 487

24.3 FA理论与形式语言理论的关系 492

习题 498

参考文献 499

名词索引 500