离散数学PDF电子书下载

第1章 命题逻辑 1

1.1 命题及联结词 1

1.1.1 命题的概念 1

1.1.2 原子命题和复合命题 3

1.1.3 联结词 3

1.2 命题的合式公式和翻译 6

1.2.1 命题公式 6

1.2.2 命题公式的翻译 7

1.2.3 真值表 8

1.3 公式的等价和蕴含 10

1.3.1 永真式、永假式和可满足式 10

1.3.2 等价式和常用的等价式 10

1.4 全功能联结词集合 13

1.5 对偶与范式 14

1.5.1 对偶定义 14

1.5.2 对偶定理 14

1.5.3 析取范式和合取范式 15

1.5.4 主析取范式和主合取范式 16

1.6 推理理论 20

1.6.1 蕴含式 20

1.6.2 有效结论 21

1.6.3 证明方法 21

本章小结 26

习题 26

第2章 谓词逻辑 31

2.1 谓词的概念与表示 31

2.1.1 谓词 31

2.1.2 命题函数 32

2.1.3 量词 33

2.2 谓词公式与翻译 34

2.2.1 谓词的合式公式 34

2.2.2 谓词的翻译 34

2.2.3 自由变元和约束变元 35

2.3 谓词演算的等价式和蕴含式 36

2.4 前束范式 39

2.5 谓词演算的推理理论 39

本章小结 42

习题 43

第3章 集合与关系 45

3.1 集合的概念和表示 45

3.1.1 集合与元素 45

3.1.2 集合的表示 46

3.1.3 集合与集合的关系 47

3.2 集合的运算 50

3.2.1 交运算 50

3.2.2 并运算 51

3.2.3 相对补与绝对补 51

3.2.4 对称差 52

3.2.5 集合运算中的恒等式 52

3.2.6 包含排斥原理 54

3.3 序偶与笛卡儿积 56

3.3.1 序偶 56

3.3.2 笛卡儿积 57

3.4 关系及其表示 59

3.4.1 关系的引入 59

3.4.2 关系的定义 59

3.4.3 二元关系 59

3.4.4 关系的表示法 60

3.5 关系的性质 62

3.5.1 自反性与反自反性 62

3.5.2 对称性与反对称性 64

3.5.3 传递性 65

3.6 关系的运算 66

3.6.1 关系的交、并、补、差运算 66

3.6.2 关系的复合运算 67

3.6.3 关系的逆运算 69

3.7 关系的闭包运算 71

3.8 等价关系 74

3.8.1 等价关系的定义 74

3.8.2 等价类与商集 75

3.8.3 集合的划分 76

3.8.4 等价关系与划分 77

3.9 偏序关系 78

3.9.1 偏序关系的定义 78

3.9.2 偏序关系的哈斯图 78

3.9.3 偏序集中的特殊元素 80

3.9.4 全序与良序 80

本章小结 81

习题 81

第4章 函数 91

4.1 函数的概念 91

4.2 函数的性质 94

4.3 函数的运算 95

4.3.1 函数的复合运算 95

4.3.2 函数的逆运算 96

本章小结 96

习题 97

第5章 代数系统 99

5.1 代数系统概述 99

5.1.1 代数运算及其性质 99

5.1.2 代数系统的定义 103

5.2 半群和独异点 104

5.2.1 半群 104

5.2.2 独异点 105

5.2.3 可交换半群和循环半群 106

5.3 群 107

5.3.1 群的定义 107

5.3.2 群的性质 108

5.3.3 子群 108

5.4 特殊的群 109

5.4.1 交换群 109

5.4.2 循环群 110

5.5 陪集和拉格朗日定理 110

5.5.1 陪集 110

5.5.2 拉格朗日定理 112

5.6 同态和同构 113

5.6.1 同态 113

5.6.2 同构 114

5.6.3 群的同态和同构 115

5.7 环和域 116

5.7.1 环 116

5.7.2 子环和理想 117

5.7.3 域 118

本章小结 119

习题 120

第6章 格与布尔代数 122

6.1 格的概念 122

6.2 特殊格 127

6.3 布尔代数 131

6.4 本章小结 135

习题 136

第7章 图论 138

7.1 图的基本概念 138

7.1.1 图的定义 138

7.1.2 无向图和有向图 139

7.1.3 顶点度数和握手定理 141

7.1.4 子图和补图 143

7.1.5 图的同构 144

7.2 通路与回路 145

7.2.1 通路与回路的定义 145

7.2.2 无向连通图 146

7.2.3 点割集和割点 147

7.2.4 边割集和割边 147

7.2.5 连通分图 147

7.3 图的矩阵表示 150

7.3.1 邻接矩阵和关联矩阵 150

7.3.2 可达矩阵 153

7.4 特殊图 155

7.4.1 欧拉图 155

7.4.2 哈密尔顿图 158

7.5 平面图 160

7.5.1 平面图的定义 161

7.5.2 欧拉公式 162

7.5.3 平面图的判断 165

7.6 对偶图与着色 166

7.6.1 对偶图 166

7.6.2 点着色 168

7.7 树与生成树 170

7.7.1 无向树的概念 170

7.7.2 生成树与最小生成树 172

7.8 有向树及其应用 175

7.8.1 有向树的概念 175

7.8.2 最优树 177

7.8.3 前缀码 179

7.9 本章小结 182

习题 182

第8章 离散数学在计算机科学中的应用 189

8.1 谓词逻辑在计算机科学中的应用 189

8.1.1 谓词逻辑在程序设计中的应用 189

8.1.2 谓词逻辑与数据子语言 191

8.1.3 谓词逻辑与逻辑程序设计语言 192

8.1.4 谓词逻辑在人工智能中的应用 193

8.2 集合论在计算机科学中的应用 194

8.2.1 关系在关系数据库中的应用 194

8.2.2 关系代数与数据子语言 196

8.2.3 等价关系在计算机中的应用 197

8.2.4 序关系在项目管理中的应用 197

8.3 代数系统在计算机科学中的应用 198

8.3.1 布尔代数与逻辑电路设计 198

8.3.2 半群与形式语言 201

8.3.3 纠错码 202

8.4 图论在计算机科学中的应用 207

8.4.1 二叉树在搜索算法中的应用 207

8.4.2 图论在形式语言的应用 209

8.4.3 图论在有限状态自动机中的应用 210

习题 211