离散数学及其应用 原书第6版 本科教学版PDF电子书下载

第1章 基础：逻辑和证明 1

1.1命题逻辑 1

1.1.1引言 1

1.1.2命题 1

1.1.3条件语句 3

1.1.4复合命题的真值表 6

1.1.5逻辑运算符的优先级 7

1.1.6翻译语句 7

1.1.7系统规范说明 8

1.1.8布尔检索 8

1.1.9逻辑难题 9

1.1.10逻辑运算和位运算 9

练习 10

1.2命题等价 13

1.2.1引言 13

1.2.2逻辑等价 14

1.2.3德摩根律的运用 16

1.2.4构建新的逻辑等价式 16

练习 18

1.3谓词和量词 20

1.3.1引言 20

1.3.2谓词 20

1.3.3量词 21

1.3.4其他量词 24

1.3.5约束论域量词 24

1.3.6量词的优先级 24

1.3.7绑定变量 24

1.3.8涉及量词的逻辑等价 24

1.3.9否定量化表达式 25

1.3.10翻译语句为逻辑表达式 26

1.3.11在系统说明中运用量词 28

1.3.12选自Lewis Carroll的例子 28

1.3.13逻辑程序设计 29

练习 30

1.4嵌套量词 32

1.4.1引言 32

1.4.2量词的顺序 33

1.4.3将数学语句翻译成涉及嵌套量词的语句 34

1.4.4将嵌套量词翻译为汉语 35

1.4.5将汉语语句翻译成逻辑表达式 35

1.4.6否定嵌套量词 36

练习 36

1.5推理规则 39

1.5.1引言 39

1.5.2命题逻辑的有效论证 39

1.5.3命题逻辑的推理规则 40

1.5.4用推理规则建立论证 42

1.5.5消解 43

1.5.6谬误 43

1.5.7带量词命题的推理规则 44

1.5.8命题推理和量化语句推理规则的结合 45

练习 45

1.6证明导论 47

1.6.1引言 47

1.6.2一些专用术语 47

1.6.3定理陈述的理解 47

1.6.4证明定理的方法 48

1.6.5直接证明 48

1.6.6反证法 49

1.6.7归谬证明 50

1.6.8证明中的错误 52

1.6.9仅仅是开始 53

练习 53

1.7证明的方法和策略 54

1.7.1引言 54

1.7.2穷举证明和分情形证明 54

1.7.3存在性证明 57

1.7.4唯一性证明 58

1.7.5证明策略 58

1.7.6寻找反例 60

1.7.7行动证明策略 60

1.7.8填充 60

1.7.9未解决问题的作用 63

1.7.10其他证明方法 63

练习 64

关键术语和结果 65

复习题 66

补充练习 67

计算机题目 68

计算和研究 69

写作题目 69

第2章 基本结构：集合、函数、数列与求和 70

2.1集合 70

2.1.1引言 70

2.1.2幂集合 72

2.1.3笛卡儿积 73

2.1.4使用带量词的集合符号 74

2.1.5量词的真值集合 74

练习 74

2.2集合运算 75

2.2.1引言 75

2.2.2集合恒等式 77

2.2.3扩展的并集和交集 79

2.2.4计算机表示集合的方式 80

练习 81

2.3函数 83

2.3.1引言 83

2.3.2一对一函数和映上函数 85

2.3.3反函数和函数组合 86

2.3.4函数的图像 88

2.3.5几个重要的函数 89

练习 91

2.4序列与求和 93

2.4.1引言 93

2.4.2序列 93

2.4.3特殊的整数序列 94

2.4.4求和 96

2.4.5基数 98

练习 100

关键术语和结果 101

复习题 103

补充练习 103

计算机题目 105

计算和研究 105

写作题目 105

第3章 计数 106

3.1计数基础 106

3.1.1引言 106

3.1.2基本的计数原则 106

3.1.3比较复杂的计数问题 109

3.1.4容斥原理 110

3.1.5树图 111

练习 112

3.2鸽巢原理 114

3.2.1引言 114

3.2.2广义鸽巢原理 115

3.2.3巧妙使用鸽巢原理 116

练习 117

3.3排列与组合 118

3.3.1引言 118

3.3.2排列 118

3.3.3组合 120

练习 122

3.4二项式系数 123

3.4.1二项式定理 123

3.4.2帕斯卡恒等式和三角形 125

3.4.3其他的二项式系数恒等式 126

练习 127

3.5排列与组合的推广 129

3.5.1引言 129

3.5.2有重复的排列 129

3.5.3有重复的组合 129

3.5.4具有不可区别物体的集合的排列 132

3.5.5把物体放入盒子 132

练习 135

3.6生成排列和组合 136

3.6.1引言 136

3.6.2生成排列 137

3.6.3生成组合 138

练习 139

关键术语和结果 139

复习题 140

补充练习 141

计算机题目 144

计算和研究 144

写作题目 144

第4章 高级计数技术 145

4.1递推关系基础 145

4.1.1引言 145

4.1.2递推关系 145

4.1.3用递推关系构造模型 146

练习 150

4.2求解线性递推关系 152

4.2.1引言 152

4.2.2求解常系数线性齐次递推关系 153

4.2.3常系数线性非齐次的递推关系 156

练习 159

4.3分治算法和递推关系 160

4.3.1引言 160

4.3.2分治递推关系 160

练习 165

4.4生成函数 166

4.4.1引言 166

4.4.2关于幂级数的有用事实 167

4.4.3计数问题与生成函数 170

4.4.4使用生成函数求解递推关系 172

4.4.5使用生成函数证明恒等式 174

练习 174

4.5容斥 176

4.5.1引言 176

4.5.2容斥原理 176

练习 179

4.6容斥原理的应用 180

4.6.1引言 180

4.6.2容斥原理的另一种形式 180

4.6.3埃拉托色尼筛 181

4.6.4映上函数的个数 182

4.6.5错位排列 183

练习 184

关键术语和结果 185

复习题 186

补充练习 186

计算机题目 188

计算和研究 189

写作题目 189

第5章 关系 190

5.1关系及其性质 190

5.1.1引言 190

5.1.2函数作为关系 191

5.1.3集合的关系 191

5.1.4关系的性质 192

5.1.5关系的组合 194

练习 195

5.2 n元关系及其应用 197

5.2.1引言 197

5.2.2 n元关系 197

5.2.3数据库和关系 197

5.2.4 n元关系的运算 199

5.2.5 SQL 200

练习 201

5.3关系的表示 202

5.3.1引言 202

5.3.2用矩阵表示关系 202

5.3.3用图表示关系 204

练习 206

5.4关系的闭包 207

5.4.1引言 207

5.4.2闭包 207

5.4.3有向图的路径 208

5.4.4传递闭包 209

5.4.5沃舍尔算法 211

练习 213

5.5等价关系基础 214

5.5.1引言 214

5.5.2等价关系 214

5.5.3等价类 216

5.5.4等价类与划分 217

练习 219

5.6偏序 221

5.6.1引言 221

5.6.2字典顺序 222

5.6.3哈塞图 224

5.6.4极大元素与极小元素 225

5.6.5格 226

5.6.6拓扑排序 227

练习 229

关键术语和结果 231

复习题 233

补充练习 234

计算机题目 236

计算和研究 237

写作题目 237

第6章图 238

6.1图和图模型 238

练习 243

6.2图的术语和几种特殊的图 244

6.2.1引言 244

6.2.2基本术语 244

6.2.3一些特殊的简单图 246

6.2.4偶图 247

6.2.5特殊类型的图的一些应用 249

6.2.6从旧图到新图 251

练习 252

6.3图的表示和图的同构 253

6.3.1引言 253

6.3.2图的表示 253

6.3.3邻接矩阵 254

6.3.4关联矩阵 256

6.3.5图的同构 256

练习 259

6.4连通性 261

6.4.1引言 261

6.4.2通路 261

6.4.3无向图的连通性 263

6.4.4有向图的连通性 264

6.4.5通路与同构 265

6.4.6计算顶点之间的通路数 265

练习 266

6.5欧拉通路与哈密顿通路 268

6.5.1引言 268

6.5.2欧拉通路与欧拉回路 268

6.5.3哈密顿通路与哈密顿回路 272

练习 274

6.6最短通路问题 276

6.6.1引言 276

6.6.2最短通路算法 278

6.6.3旅行商问题 281

练习 283

6.7可平面图 284

6.7.1引言 284

6.7.2欧拉公式 286

6.7.3库拉图斯基定理 288

练习 289

6.8图着色 291

6.8.1引言 291

6.8.2图着色的应用 294

练习 295

关键术语和结果 297

复习题 298

补充练习 299

计算机题目 303

计算和研究 303

写作题目 304

第7章树 305

7.1概述 305

7.1.1树作为模型 309

7.1.2树的性质 310

练习 312

7.2树的应用 313

7.2.1引言 313

7.2.2二叉搜索树 313

7.2.3决策树 316

7.2.4前缀码 317

7.2.5博弈树 320

练习 323

7.3树的遍历 324

7.3.1引言 324

7.3.2通用地址系统 325

7.3.3遍历算法 325

7.3.4中缀、前缀和后缀记法 331

练习 333

7.4生成树 334

7.4.1引言 334

7.4.2深度优先搜索 337

7.4.3宽度优先搜索 338

7.4.4回溯 340

7.4.5有向图中的深度优先搜索 341

练习 342

7.5最小生成树 344

7.5.1引言 344

7.5.2最小生成树算法 344

练习 347

关键术语和结果 348

复习题 349

补充练习 350

计算机题目 353

计算和研究 353

写作题目 353