离散数学导学PDF电子书下载

第1章 导论 1

1.1 学习动机 1

1.2 教材内容 1

1.3 组织结构 2

第2章 数 5

2.1 自然数 5

2.2 Peano算术 7

2.3 其他类型的数 8

2.4 附加练习 8

2.5 练习解答 8

第3章 命题逻辑 11

3.1 原子命题 11

3.2 真值 11

3.3 否定运算符 12

3.4 合取运算符 13

3.5 析取运算符 14

3.6 蕴含运算符 16

3.7 等值运算符 17

3.8 运算的优先级 18

3.9 重言式、矛盾式和不定式 18

3.10 真值表 19

3.11 等值推理 20

3.12 自然演绎 21

3.13 附加练习 24

3.14 练习解答 25

第4章 集合论 33

4.1 集合 33

4.2 单集 34

4.3 空集 34

4.4 集合成员 34

4.5 子集 35

4.6 超集 37

4.7 集合的并集 38

4.8 集合的交集 39

4.9 集合的差集 40

4.10 有关集合的推理 41

4.11 集合的势 42

4.12 有穷集合和无穷集合 42

4.13 集合的幂集 43

4.14 集合的广义运算 44

4.15 附加练习 45

4.16 练习解答 46

第5章 布尔代数 51

5.1 简介 51

5.2 命题逻辑回顾 51

5.3 集合论回顾 51

5.4 布尔代数基础 52

5.5 简写规定 54

5.6 优先级 54

5.7 集合的布尔代数 54

5.8 命题的布尔代数 54

5.9 布尔代数的同构 54

5.10 对偶性 55

5.11 附加练习 55

5.12 练习解答 56

第6章 类型集合论 61

6.1 类型的需要 61

6.2 再论空集 63

6.3 集合描述 64

6.4 特征组 65

6.5 缩写 66

6.6 笛卡儿积 66

6.7 公理定义 70

6.8 附加练习 71

6.9 练习解答 72

第7章 谓词逻辑 77

7.1 量词的需要 77

7.2 全称量词 77

7.3 存在量词 78

7.4 可满足性和有效性 80

7.5 量词的否定 80

7.6 自由变元和约束变元 81

7.7 替换 82

7.8 限制 84

7.9 唯一存在量词 86

7.10 等值推理 87

7.11 自然演绎 89

7.12 one-point规则 91

7.13 附加练习 92

7.14 练习解答 93

第8章 关系 101

8.1 二元关系 101

8.2 关系的推理 102

8.3 定义域和值域 102

8.4 关系的逆 103

8.5 关系上的运算 104

8.6 关系的合成 107

8.7 同类关系和异类关系 109

8.8 关系的性质 109

8.8.1 自反性 109

8.8.2 传递性 110

8.8.3 对称性 111

8.8.4 非对称性 112

8.8.5 反对称性 112

8.8.6 完全性 113

8.9 顺序与等价 113

8.9.1 偏序 113

8.9.2 全序 114

8.9.3 等价关系 114

8.10 闭包 114

8.10.1 自反闭包 114

8.10.2 传递闭包 115

8.10.3 自反传递闭包 116

8.10.4 对称闭包 116

8.11 n元关系 117

8.12 附加练习 117

8.13 练习解答 119

第9章 函数 127

9.1 一种特殊的关系 127

9.2 全函数 128

9.3 函数的作用 129

9.4 覆盖 130

9.5 函数的性质 131

9.5.1 单射 131

9.5.2 满射 132

9.5.3 双射 133

9.6 递归函数 133

9.7 附加练习 135

9.8 练习解答 136

第10章 序列 141

10.1 元包 141

10.2 顺序的需要 142

10.3 建模序列 142

10.4 空序列 143

10.5 长度 143

10.6 连接 144

10.7 头和尾 144

10.8 限制 145

10.9 逆置 147

10.10 单射序列 148

10.11 再论递归函数 148

10.12 附加练习 149

10.13 练习解答 151

第11章 归纳法 155

11.1 数学归纳法 155

11.2 结构归纳法 157

11.3 附加练习 158

11.4 练习解答 158

第12章 图论 163

12.1 图 163

12.2 图的集合和元包表示 167

12.3 图的矩阵表示 168

12.4 图的同构 170

12.5 路径 171

12.6 循环 173

12.7 树 174

12.8 带权图 175

12.9 有向图 177

12.10 二叉树 178

12.11 附加练习 180

12.12 练习解答 181

第13章 组合数学 187

13.1 阶乘函数 187

13.2 二项式系数 188

13.3 计数 190

13.4 排列 190

13.5 组合 192

13.6 树形图 193

13.7 取样 193

13.8 附加练习 195

13.9 练习解答 195

第14章 应用实例 203

14.1 程序变量的建模 203

14.2 元搜索引擎 204

14.2.1 使用集合建模 204

14.2.2 使用序列建模 205

14.2.3 使用关系建模 205

14.2.4 继续讨论 206

14.3 用于栈和队列的序列 208

14.4 数字电路 210

14.5 学校数据库 212

14.6 知识库系统 214

14.7 练习解答 216

参考文献 227