离散数学PDF电子书下载

第1章 集合、函数和矩阵 1

1.1 集合 1

1.1.1 集合的概念和表示 1

1.1.2 集合之间的关系 2

1.1.3 集合的运算 4

1.2 函数 10

1.2.1 函数的概念 10

1.2.2 函数的性质 14

1.2.3 复合函数和逆函数 15

1.3 矩阵 18

1.3.1 矩阵的概念 19

1.3.2 矩阵的运算 20

1.3.3 0-1矩阵 26

习题一 28

第2章 关系 35

2.1 关系的概念和表示 35

2.1.1 关系的定义 35

2.1.2 关系的表示 38

2.2.1 复合关系 41

2.2 复合关系和逆关系 41

2.2.2 逆关系 44

2.3 关系的性质 46

2.3.1 自反性 47

2.3.2 反自反性 48

2.3.3 对称性 49

2.3.4 反对称性 50

2.3.5 传递性 52

2.4.1 闭包的概念 54

2.4 关系的闭包 54

2.4.2 闭包的构造 55

2.4.3 Warshall算法 58

2.5 等价关系与划分 61

2.5.1 等价关系 61

2.5.2 集合的划分 63

2.6 序关系 64

2.6.1 偏序集的概念 64

2.6.2 哈瑟图 64

2.6.3 字典序 65

2.6.4 最大元和最小元 66

2.6.5 极大元和极小元 67

2.6.6 集合的界 67

2.6.7 全序关系 68

2.6.8 拓扑排序 68

习题二 69

第3章 命题逻辑 74

3.1 命题及其表示 74

3.2.2 析取词符号 76

3.2.1 否定词符号 76

3.2 连接词符号 76

3.2.3 合取词符号 77

3.2.4 蕴含词符号 77

3.2.5 等价词符号 78

3.3 合式公式 78

3.4 变元的指派与公式的真值 80

3.5 公式的可满足性 82

3.5.1 可满足性 82

3.5.3 逻辑蕴含和逻辑等价 83

3.5.2 重言式和矛盾式 83

3.6.1 连接词符号集的功能完备性 87

3.6 其他连接词符号 87

3.6.2 或非词符号 88

3.6.3 与非词符号 89

3.6.4 异或词符号 89

3.7 命题逻辑中的形式推理 89

3.7.1 公理化系统 90

3.7.2 自然推理系统 94

3.8.1 合取范式 97

3.8 归结方法 97

3.8.2 归结原理 100

3.8.3 狮头象游戏 102

习题三 103

第4章 谓词逻辑 108

4.1 个体词符号、谓词符号和量词符号 108

4.1.1 个体词符号 108

4.1.3 量词符号 109

4.1.2 谓词符号 109

4.2 项和公式 111

4.2.1 项 111

4.2.2 公式 112

4.3 语义 113

4.3.1 结构和指派 113

4.3.2 项和公式的值 114

4.4 自由变元和约束变元 116

4.4.1 变元的自由出现和约束出现 116

4.4.2 变元的换名和项的代入 117

4.5 公式的可满足性和有效性 119

4.5.1 可满足性和有效性 119

4.5.2 逻辑蕴含和逻辑等价 121

4.6 谓词逻辑中的形式推理 122

4.6.1 公理化系统 122

4.6.2 自然推理系统 126

4.7 前束范式 129

习题四 131

5.1.1 运算和代数的概念 136

5.1 运算与代数 136

第5章 代数系统 136

5.1.2 运算的性质 137

5.1.3 代数中的特殊元素 139

5.2 子代数和商代数 142

5.2.1 子代数 142

5.2.2 同余和商代数 142

5.2.3 同态 144

5.3.1 半群 146

5.3 半群和群 146

5.3.2 群 147

5.4 环与域 152

5.4.1 环 153

5.4.2 域 155

5.5 格与布尔代数 156

5.5.1 格 156

5.5.2 布尔代数 160

习题五 160

6.1.1 图的基本术语 165

第6章 图与有向图 165

6.1 图的概念 165

6.1.2 结点的度数 166

6.1.3 几种特殊的简单图 167

6.1.4 图之间的关系 168

6.2 图的连通性 168

6.2.1 路 169

6.2.2 无向图的连通性 170

6.2.3 有向图的连通性 170

6.3 欧拉图和哈密顿图 172

6.3.1 欧拉图 172

6.3.2 哈密顿图 174

6.4 平面图 176

6.5 图的矩阵表示 180

6.5.1 有向图的邻接矩阵 180

6.5.2 可达矩阵 181

6.6 最短路径问题 182

6.6.1 Dijkstra算法 182

6.5.3 无向图的矩阵表示 182

6.6.2 旅行商问题 185

习题六 186

第7章 树 190

7.1 树的基本知识 190

7.2 二叉树的遍历与表达式的计算 194

7.2.1 二叉树的遍历 194

7.2.2 表达式的二叉树表示 194

7.3.1 连通图与生成树 197

7.3 生成树 197

7.3.2 最小生成树 199

7.4 最优二叉树 202

7.4.1 Huffman算法 202

7.4.2 前缀码 203

习题七 205

附录A 模拟试卷 209

附录B 模拟试卷参考答案 211

参考文献 220

索引 222