《离散数学及应用》

第一篇数理逻辑1

第一章 命题演算2

1-1 命题及联结词2

1-2 命题变元与命题公式8

1-3 命题演算的关系式10

1-3-1 命题之间的等价关系10

1-3-2 命题的蕴函关系14

1-3-3 对偶法则16

1-4 其他联结词18

1-5 范式21

1-5-1 析取范式和合取范式21

1-5-2 主析取范式和主合取范式23

1-6 命题演算的推理30

1-6-1 真值表技术31

1-6-2 直接推演33

1-6-3 间接推演37

第二章 谓词演算38

2-1 谓词演算的基本概念38

2-1-1 谓词与个体39

2-1-2 量词41

2-1-3 谓词演算公式42

2-1-4 自由变元与约束变元43

2-2 谓词演算的关系式46

2-2-1 基本定义46

2-2-2 关系式47

2-3 前束范式53

2-4 谓词演算的推理54

习题一59

学习提要一66

第二篇集合论79

第三章 集合80

3-1 集合的基本概念80

3-1-1 集合及其表示80

3-1-2 集合间的关系81

3-1-3 几种特殊集合84

3-2 集合的运算及基本公式85

3-3 幂集93

3-4 包含排斥原理95

3-5 集合的直积(笛卡儿乘积)97

第四章 关系101

4-1 关系及其运算101

4-2 关系的有关性质108

4-3 关系的闭包运算111

4-4 等价关系和相容关系115

4-4-1 集合的覆盖与划分115

4-4-2 等价关系116

4-4-3 相容关系119

4-5 偏序关系121

第五章 映射与无限集129

5-1 映射129

5-1-1 映射的基本概念129

5-1-2 复合映射134

5-1-3 逆映射135

5-1-4 由映射产生的等价关系137

5-2 无限集141

5-2-1 自然数141

5-2-2 等势142

5-2-3 可列集143

5-2-4 不可列无限集145

5-2-5 势的比较147

习题二150

学习提要二158

第三篇图论167

第六章 图论168

6-1 图的基本概念168

6-1-1 基本术语168

6-1-2 路与回路177

6-1-3 欧拉图与哈密顿图183

6-2 树190

6-2-1 树的特征190

6-2-2 生成树与割集192

6-2-3 有向树197

6-3 图的矩阵表示201

6-3-1 关联矩阵与基本关联矩阵201

6-3-2 回路矩阵203

6-3-3 割集矩阵204

6-3-4 邻接矩阵205

6-3-5 有向图的矩阵表示207

6-4 平面图212

6-4-1 平面图的概念212

6-4-2 连通平面图的欧拉公式214

6-4-3 库拉托斯基定理215

6-4-4 对偶图与着色217

6-5 二分图与匹配219

6-5-1 二分图219

6-5-2 匹配221

习题三226

学习提要三233

第四篇代数结构241

第七章 代数结构的基本知识242

7-1 代数系统的基本概念242

7-2 同构与同态249

第八章 半群与群260

8-1 半群、循环半群与幺半群260

8-2 群264

8-3 置换群与对称群267

8-4 循环群271

8-5 陪集与拉格朗日定理275

第九章 环与域279

9-1 环与幺环279

9-2 整环与除环280

9-3 域284

第十章 格与布尔代数287

10-1 格与代数系统287

10-2 布尔格与布尔代数294

10-3 布尔代数的另一理论体系299

10-4 布尔表达式与布尔函数303

习题四309

学习提要四316

第五篇离散数学在计算机科学技术中的应用325

第十一章 用计算机化简逻辑函数326

11-1 自动化简逻辑函数的算法326

11-2 用对合法寻找逻辑函数基本项327

11-3 用覆盖法寻找必需项329

11-4 用(准)必需项选拔法选取基本项330

11-5 逻辑函数化简实例332

12-1-1 语言的表示335

第十二章 形式语言与自动机335

12-1 语言的概念及运算335

12-1-2 字母表和串336

12-1-3 语言的概念及运算338

12-2 文法及语言342

12-2-1 文法(语法)342

12-2-2 文法的类型347

12-2-3 上下文(前后文)有关文法及语言(1型)348

12-2-4 上下文(前后文)无关文法及语言(2型)349

12-2-5 有限状态文法及语言356

12-3 有限自动机359

12-3-1 自动机与形式文法的关系359

12-3-2 有限自动机的基本概念360

12-3-3 有限自动机及其表示法362

12-3-4 有限自动机的等价364

12-3-5 状态赋值自动机365

12-3-6 有限自动机的简化369

12-3-7 有限识别器374

12-3-8 确定的有限识别器与不确定的有限识别器375

12-3-9 有限识别器与有限状态文法378

12-3-10 有限识别器的另一形式379

12-4 下推自动机381

12-4-1 下推自动机的概念381

12-4-2 下推自动机的例子383

12-5 线性有界自动机385

12-5-1 线性有界自动机的概念385

12-5-2 线性有界自动机的例子386

12-6-1 五重组图灵机390

12-6 图灵机390

12-6-2 波斯特—图灵机395

12-6-3 图灵机用于计算401

12-6-4 图灵识别器406

12-6-5 通用图灵机与图灵停机问题409

习题五410

学习提要五414

习题答案与提示420

符号表445

参考文献450