离散数学与计算机科学之应用PDF电子书下载

第1章 离散数学之导论 1

1.1 何谓离散数学？ 2

1.2 工具、技术与方法论 3

1.3 演算语言 7

1.3.1 虚拟码 8

1.3.2 指派叙述 9

1.3.3 控制叙述 10

1.3.4 有关演算法之注释 17

1.4 总结 18

1.5 复习问题 19

第2章 逻辑与集合 23

2.1.1 命题 24

2.1 逻辑与命题 24

2.1.2 逻辑运算 25

2.2 述语逻辑 33

2.3 证明 36

2.3.1 直接证法 37

2.3.2 对偶证法 37

2.3.3 矛盾证法 38

2.3.4 存在证法 38

2.3.5 反例 39

2.4 数学归纳法 40

2.4.1 数学归纳法之原则 40

2.4.2 归纳式的定义 43

2.5.1 确证 46

2.5 演算法之正确性（选修教材） 46

2.5.2 顺序叙述 47

2.5.3 条件叙述 48

2.5.4 反覆 51

2.6 集合之基本性质 55

2.6.1 集合之定义 55

2.6.2 一些特别的集合 56

2.6.3 集合的运算 57

2.6.4 性质与恒等式 60

2.7 再谈集合 64

2.7.1 幂集合 64

2.7.2 积集合 65

2.7.3 集合之分割 68

2.8 应用：浅谈以知识为基础的系统 70

2.8.1 一个范例：有关家庭的事实 71

2.8.2 推论规则 71

2.8.3 查询 72

2.9 总结 73

2.10 复习问题 76

2.11 自我评量解答 82

第3章 关系与函数 85

3.1 关系 86

3.1.1 二元关系 86

3.1.2 关系之图形表示法 87

3.1.3 关系之矩阵表示法 90

3.2 关系之性质 93

3.2.1 相等关系与分割 96

3.2.2 有序关系 99

3.2.3 递移封闭 101

3.3 关系之合成 104

3.3.1 逻辑矩阵乘积 105

3.3.2 自等关系 108

3.3.3 相反关系 109

3.4 函数 111

3.4.1 单射与全射 113

3.4.2 函数与基数 114

3.4.3 可逆函数 116

3.4.4 二元运算 118

3.4.5 在电脑语言上之函数 119

3.5 应用：资料库管理系统 122

3.5.1 n元关系之运算 123

3.6 总结 126

3.7 复习问题 128

3.8 自我评量解答 134

第4章 组合数学 139

4.1 自一集合中选择元素 141

4.1.1 定义 142

4.1.2 计数公式 144

4.2 型样与分割 154

4.2.1 型样 155

4.2.2 分割 157

4.3 演算法分析（选修教材） 161

4.3.1 次方的种类 162

4.3.2 常见的次方种类 164

4.3.3 综合讨论 166

4.4 应用：我们可以排序多快？ 168

4.5 总结 170

4.6 复习问题 172

4.7 自我评量解答 176

第5章 无向图形 181

5.1 简单图形 183

5.1.1 路径、循环与连通 186

5.1.2 尤拉路径 189

5.1.3 汉米顿循环 191

5.1.4 同构关系 194

5.2 树 199

5.2.1 最小展开树 203

5.2.2 有根树 205

5.2.3 排序与搜寻 207

5.3 应用：语言的语法 213

5.3.1 文法 214

5.3.2 衍生 215

5.3.3 Bacus-Naur形式 216

5.3.4 语法图 218

5.4 总结 221

5.5 复习问题 222

5.6 自我评量解答 225

第6章 有向图 229

6.1 有向图 230

6.1.1 分支度、路径与循环 231

6.1.2 一致性标记 235

6.2 有向图的路径问题 242

6.2.1 路径的存在性 242

6.2.2 瓦谢勒演算法 246

6.2.3 最短路径 249

6.2.4 路径个数 254

6.3.1 计算机网路的用途 257

6.3 应用：通信网路的路线 257

6.3.2 网路与图形模式 258

6.3.3 路线问题 259

6.3.4 动态路径程序 259

6.4 总结 261

6.5 复习问题 263

6.6 自我评量解答 268

第7章 布耳代数 271

7.1 布耳陈式 272

7.1.1 陈式 273

7.1.2 第摩根定律 276

7.2 陈式的表示法 278

7.2.1 全及项 281

7.2.2 正规形式 283

7.2.3 运算子的完整集合 285

7.3 布耳陈式的极小化法 288

7.3.1 卡诺图 288

7.3.2 四个变数的卡诺图 292

7.4 开关理论 296

7.4.1 电路图 296

7.4.2 逻辑闸之完整集合 300

7.4.3 控制开关的例子 301

7.5 应用：设计一个两位元加法器 307

7.6 总结 310

7.7 复习问题 312

7.8 自我评量解答 322

第8章 代数系统 327

8.1 半群、单群与群 328

8.1.1 半群 328

8.1.2 单群 332

8.1.3 群 335

8.1.4 子群 337

8.2 建立新的代数 342

8.2.1 积代数 342

8.2.2 商代数 343

8.2.3 傍系 348

8.2.4 拉格朗治定理 350

8.3.1 单群间之同态 353

8.3 代数结构的映型 353

8.3.2 单群之同构 357

8.3.3 对於单群同态之基本定理 358

8.3.4 群同态 361

8.3.5 对於群同态之基本定理 363

8.4 应用：群码 364

8.4.1 错误侦测码 365

8.4.2 错误更正码 366

8.4.3 群码 367

8.4.4 解码 368

8.5 总结 370

8.6 复习问题 373

8.7 自我评量解答 379

第9章 机器与计算 383

9.1 自动机模型 384

9.2 不具输出之有限状态自动机 385

9.2.1 有限状态自动机之定义 387

9.2.2 有限状态自动机当作语言辨识机 388

9.2.3 有限状态自动机当作语言辨识机的限制 396

9.2.4 具有输出之有限状态自动机 400

9.2.5 莫尔机器 400

9.2.6 米利机器 405

9.3 杜林机器（选修教材） 410

9.3.1 有效程序 410

9.3.2 杜林计算模型 411

9.3.3 杜林机器当作语言辨识机 415

9.3.4 杜林机器当作函数计算机 417

9.3.5 邱吉－杜林命题 419

9.4 应用：解决问题 421

9.4.1 有限状态自动机当作解决问题模型 421

9.5 总结 423

9.6 复习问题 425

9.7 自我评量解答 429

第10章 机率 433

10.1 机率的基本特性 434

10.1.1 均匀机率空间 436

10.2 条件机率 440

10.2.1 贝氏定理 444

10.2.2 独立事件 445

10.3 重复试验及期望值 449

10.3.1 二项式分布 451

10.3.2 随机变数及分布 454

10.3.3 期望值 456

10.4 应用：一个平均数个案分析 463

10.4.1 选择法排序 463

10.4.2 插入法排序 464

10.5 总结 467

10.6 复习问题 470

10.7 自我评量解答 472

辞汇解释 475

解答 483