离散数学及其应用（原书第8版）

本书是经典的离散数学教材，被全球数百所大学广为采用。书中全面而系统地介绍了离散数学的理论和方法，主要包括：逻辑和证明，集合、函数、序列、求和与矩阵，算法，数论和密码学，归纳与递归，计数，离散概率，关系，图，树，布尔代数，计算模型。全书取材广泛，除包括定义、定理的严格陈述外，还配备大量的例题、图表、应用实例和练习。第8版做了与时俱进的更新，成为更加实用的教学工具。本书可作为高等院校数学、计算机科学和计算机工程等专业的教材，也可作为科技领域从业人员的参考书。

出版者的话 译者序 前言 在线资源 致学生 作者简介 符号表 第1章 基础：逻辑和证明 1 1.1 命题逻辑 1 1.1.1 引言 1 1.1.2 命题 1 1.1.3 条件语句 4 1.1.4 复合命题的真值表 7 1.1.5 逻辑运算符的优先级 8 1.1.6 逻辑运算和比特运算 8 练习 9 1.2 命题逻辑的应用 15 1.2.1 引言 15 1.2.2 语句翻译 15 1.2.3 系统规范说明 16 1.2.4 布尔搜索 16 1.2.5 逻辑谜题 17 1.2.6 逻辑电路 18 练习 20 1.3 命题等价式 23 1.3.1 引言 23 1.3.2 逻辑等价式 23 1.3.3 德·摩根律的运用 25 1.3.4 构造新的逻辑等价式 26 1.3.5 可满足性 28 1.3.6 可满足性的应用 28 1.3.7 可满足性问题求解 30 练习 31 1.4 谓词和量词 34 1.4.1 引言 34 1.4.2 谓词 34 1.4.3 量词 37 1.4.4 有限域上的量词 39 1.4.5 受限域的量词 39 1.4.6 量词的优先级 40 1.4.7 变量绑定 40 1.4.8 涉及量词的逻辑等价式 40 1.4.9 量化表达式的否定 41 1.4.10 语句到逻辑表达式的翻译 42 1.4.11 系统规范说明中量词的使用 43 1.4.12 选自路易斯·卡罗尔的例子 44 1.4.13 逻辑程序设计 45 练习 46 1.5 嵌套量词 51 1.5.1 引言 51 1.5.2 理解涉及嵌套量词的语句 51 1.5.3 量词的顺序 52 1.5.4 数学语句到嵌套量词语句的翻译 53 1.5.5 嵌套量词到自然语言的翻译 54 1.5.6 汉语语句到逻辑表达式的翻译 54 1.5.7 嵌套量词的否定 55 练习 56 1.6 推理规则 62 1.6.1 引言 62 1.6.2 命题逻辑的有效论证 62 1.6.3 命题逻辑的推理规则 63 1.6.4 使用推理规则建立论证 65 1.6.5 消解律 66 1.6.6 谬误 66 1.6.7 量化命题的推理规则 67 1.6.8 命题和量化命题推理规则的组合使用 68 练习 69 1.7 证明导论 72 1.7.1 引言 72 1.7.2 一些专用术语 72 1.7.3 理解定理是如何陈述的 73 1.7.4 证明定理的方法 73 1.7.5 直接证明法 73 1.7.6 反证法 74 1.7.7 归谬证明法 76 1.7.8 证明中的错误 78 1.7.9 良好的开端 79 练习 80 1.8 证明的方法和策略 81 1.8.1 引言 81 1.8.2 穷举证明法和分情形证明法 81 1.8.3 存在性证明 84 1.8.4 唯一性证明 86 1.8.5 证明策略 87 1.8.6 寻找反例 89 1.8.7 证明策略实践 90 1.8.8 拼接 90 1.8.9 开放问题的作用 92 1.8.10 其他证明方法 93 练习 94 关键术语和结论 96 复习题 97 补充练习 98 计算机课题 100 计算和探索 101 写作课题 101 第2章 基本结构：集合、函数、序列、求和与矩阵 102 2.1 集合 102 2.1.1 引言 102 2.1.2 文氏图 104 2.1.3 子集 105 2.1.4 集合的大小 106 2.1.5 幂集 107 2.1.6 笛卡儿积 107 2.1.7 使用带量词的集合符号 109 2.1.8 真值集和量词 109 练习 109 2.2 集合运算 112 2.2.1 引言 112 2.2.2 集合恒等式 114 2.2.3 扩展的并集和交集 116 2.2.4 集合的计算机表示 117 2.2.5 多重集 118 练习 119 2.3 函数 123 2.3.1 引言 123 2.3.2 一对一函数和映上函数 125 2.3.3 反函数和函数合成 128 2.3.4 函数的图 130 2.3.5 一些重要的函数 130 2.3.6 部分函数 133 练习 133 2.4 序列与求和 138 2.4.1 引言 138 2.4.2 序列 138 2.4.3 递推关系 139 2.4.4 特殊的整数序列 141 2.4.5 求和 144 练习 147 2.5 集合的基数 150 2.5.1 引言 150 2.5.2 可数集合 151 2.5.3 不可数集合 153 练习 155 2.6 矩阵 157 2.6.1 引言 157 2.6.2 矩阵算术 158 2.6.3 矩阵的转置和幂 159 2.6.4 0-1矩阵 160 练习 161 关键术语和结论 164 复习题 166 补充练习 166 计算机课题 168 计算和探索 169 写作课题 169 第3章 算法 170 3.1 算法 170 3.1.1 引言 170 3.1.2 搜索算法 172 3.1.3 排序 174 3.1.4 字符串匹配 176 3.1.5 贪婪算法 177 3.1.6 停机问题 179 练习 180 3.2 函数的增长 183 3.2.1 引言 183 3.2.2 大O记号 184 3.2.3 一些重要函数的大O估算 187 3.2.4 函数组合的增长 190 3.2.5 大Ω与大Θ记号 191 练习 192 3.3 算法的复杂度 196 3.3.1 引言 196 3.3.2 时间复杂度 196 3.3.3 矩阵乘法的复杂度 198 3.3.4 算法范型 199 3.3.5 理解算法的复杂度 201 练习 203 关键术语和结论 207 复习题 208 补充练习 209 计算机课题 211 计算和探索 211 写作课题 212 第4章 数论和密码学 213 4.1 整除性和模算术 213 4.1.1 引言 213 4.1.2 除法 213 4.1.3 除法算法 214 4.1.4 模算术 215 4.1.5 模m算术 217 练习 218 4.2 整数表示和算法 220 4.2.1 引言 220 4.2.2 整数表示 220 4.2.3 整数运算算法 223 4.2.4 模指数运算 225 练习 226 4.3 素数和最大公约数 229 4.3.1 引言 229 4.3.2 素数 229 4.3.3 试除法 230 4.3.4 埃拉托斯特尼筛法 231 4.3.5 关于素数的猜想和开放问题 235 4.3.6 最大公约数和最小公倍数 236 4.3.7 欧几里得算法 238 4.3.8 gcd的线性组合表示 239 练习 242 4.4 求解同余方程 245 4.4.1 引言 245 4.4.2 线性同余方程 245 4.4.3 中国剩余定理 247 4.4.4 大整数的计算机算术 248 4.4.5 费马小定理 249 4.4.6 伪素数 250 4.4.7 原根和离散对数 251 练习 252 4.5 同余的应用 255 4.5.1 散列函数 255 4.5.2 伪随机数 256 4.5.3 校验码 257 练习 259 4.6 密码学 260 4.6.1 引言 260 4.6.2 古典密码学 261 4.6.3 公钥密码学 263 4.6.4 RSA密码系统 265 4.6.5 RSA加密 265 4.6.6 RSA解密 266 4.6.7 用RSA作为公钥系统 266 4.6.8 密码协议 267 4.6.9 同态加密 268 练习 269 关键术语和结论 271 复习题 273 补充练习 273 计算机课题 275 计算和探索 276 写作课题 276 第5章 归纳与递归 278 5.1 数学归纳法 278 5.1.1 引言 278 5.1.2 数学归纳法 279 5.1.3 为什么数学归纳法是有效的 280 5.1.4 选择正确的基础步骤 280 5.1.5 运用数学归纳法进行证明的原则 281 5.1.6 数学归纳法的优点与缺点 281 5.1.7 利用数学归纳法证明的例子 281 5.1.8 使用数学归纳法时犯的错误 290 练习 291 5.2 强归纳法与良序性 296 5.2.1 引言 296 5.2.2 强归纳法 296 5.2.3 利用强归纳法证明的例子 298 5.2.4 计算几何学中使用强归纳法 300 5.2.5 利用良序性证明 302 练习 302 5.3 递归定义与结构归纳法 306 5.3.1 引言 306 5.3.2 递归地定义函数 307 5.3.3 递归地定义集合与结构 309 5.3.4 结构归纳法 312 5.3.5 广义归纳法 315 练习 315 5.4 递归算法 320 5.4.1 引言 320 5.4.2 证明递归算法的正确性 322 5.4.3 递归与迭代 323 5.4.4 归并排序 324 练习 327 5.5 程序正确性 329 5.5.1 引言 329 5.5.2 程序验证 329 5.5.3 推理规则 330 5.5.4 条件语句 330 5.5.5 循环不变量 332 练习 333 关键术语和结论 334 复习题 335 补充练习 336 计算机课题 340 计算和探索 341 写作课题 341 第6章 计数 342 6.1 计数的基础 342 6.1.1 引言 342 6.1.2 基本的计数原则 342 6.1.3 比较复杂的计数问题 346 6.1.4 减法法则（两个集合的容斥原理） 347 6.1.5 除法法则 349 6.1.6 树图 349 练习 350 6.2 鸽巢原理 354 6.2.1 引言 354 6.2.2 广义鸽巢原理 355 6.2.3 鸽巢原理的几个简单应用 357 练习 359 6.3 排列与组合 361 6.3.1 引言 361 6.3.2 排列 361 6.3.3 组合 362 练习 365 6.4 二项式系数和恒等式 367 6.4.1 二项式定理 368 6.4.2 帕斯卡恒等式和三角形 370 6.4.3 其他的二项式系数 恒等式 371 练习 372 6.5 排列与组合的推广 375 6.5.1 引言 375 6.5.2 有重复的排列 375 6.5.3 有重复的组合 375 6.5.4 具有不可区别物体的集合的排列 378 6.5.5 把物体放入盒子 379 练习 382 6.6 生成排列和组合 385 6.6.1 引言 385 6.6.2 生成排列 385 6.6.3 生成组合 386 练习 387 关键术语和结论 388 复习题 389 补充练习 390 计算机课题 393 计算和探索 394 写作课题 394 第7章 离散概率 395 7.1 离散概率引论 395 7.1.1 引言 395 7.1.2 有限概率 395 7.1.3 事件组合的概率 398 7.1.4 概率的推理 399 练习 399 7.2 概率论 402 7.2.1 引言 402 7.2.2 概率指派 402 7.2.3 事件的组合 403 7.2.4 条件概率 404 7.2.5 独立性 405 7.2.6 伯努利试验与二项分布 406 7.2.7 随机变量 407 7.2.8 生日问题 408 7.2.9 蒙特卡罗算法 409 7.2.10 概率方法 411 练习 412 7.3 贝叶斯定理 414 7.3.1 引言 414 7.3.2 贝叶斯定理 415 7.3.3 贝叶斯垃圾邮件过滤器 417 练习 420 7.4 期望值和方差 422 7.4.1 引言 422 7.4.2 期望值 422 7.4.3 期望的线性性质 424 7.4.4 平均情形下的计算复杂度 425 7.4.5 几何分布 427 7.4.6 独立随机变量 428 7.4.7 方差 429 7.4.8 切比雪夫不等式 431 练习 433 关键术语和结论 435 复习题 436 补充练习 437 计算机课题 440 计算和探索 441 写作课题 441 第8章 高级计数技术 442 8.1 递推关系的应用 442 8.1.1 引言 442 8.1.2 用递推关系构造模型 443 8.1.3 算法与递推关系 447 练习 450 8.2 求解线性递推关系 453 8.2.1 引言 453 8.2.2 求解常系数线性齐次递推关系 454 8.2.3 求解常系数线性非齐次递推关系 458 练习 460 8.3 分治算法和递推关系 463 8.3.1 引言 463 8.3.2 分治递推关系 463 练习 469 8.4 生成函数 471 8.4.1 引言 471 8.4.2 关于幂级数的有用事实 471 8.4.3 计数问题与生成函数 474 8.4.4 使用生成函数求解递推关系 477 8.4.5 使用生成函数证明恒等式 478 练习 479 8.5 容斥 484 8.5.1 引言 484 8.5.2 容斥原理 484 练习 487 8.6 容斥原理的应用 488 8.6.1 引言 488 8.6.2 容斥原理的另一种形式 488 8.6.3 埃拉托色尼筛 489 8.6.4 映上函数的个数 490 8.6.5 错位排列 490 练习 492 关键术语和结论 493 复习题 494 补充练习 495 计算机课题 497 计算和探索 498 写作课题 498 第9章 关系500 9. 1 关系及其性质 500 9.1.1 引言 500 9.1.2 函数作为关系 501 9.1.3 集合的关系 501 9.1.4 关系的性质 502 9.1.5 关系的组合 504 练习 506 9.2 n元关系及其应用 510 9.2.1 引言 510 9.2.2 n元关系 510 9.2.3 数据库和关系 511 9.2.4 n元关系的运算 512 9.2.5 SQL 514 9.2.6 数据挖掘中的关联规则 514 练习 516 9.3 关系的表示 518 9.3.1 引言 518 9.3.2 用矩阵表示关系 518 9.3.3 用图表示关系 521 练习 522 9.4 关系的闭包 524 9.4.1 引言 524 9.4.2 不同类型的闭包 524 9.4.3 有向图中的路径 525 9.4.4 传递闭包 526 9.4.5 沃舍尔算法 529 练习 531 9.5 等价关系 533 9.5.1 引言 533 9.5.2 等价关系 533 9.5.3 等价类 534 9.5.4 等价类与划分 536 练习 538 9.6 偏序 542 9.6.1 引言 542 9.6.2 字典顺序 544 9.6.3 哈塞图 545 9.6.4 极大元与极小元 546 9.6.5 格 548 9.6.6 拓扑排序 550 练习 551 关键术语和结论 556 复习题 557 补充练习 558 计算机课题 561 计算和探索 562 写作课题 562 第10章 图 563 10.1 图和图模型 563 10.1.1 图模型 565 练习 570 10.2 图的术语和几种特殊的图 573 10.2.1 引言 573 10.2.2 基本术语 573 10.2.3 一些特殊的简单图 575 10.2.4 二分图 576 10.2.5 二分图和匹配 577 10.2.6 特殊类型图的一些应用 580 10.2.7 从旧图构造新图 582 练习 584 10.3 图的表示和图的同构 587 10.3.1 引言 587 10.3.2 图的表示 588 10.3.3 邻接矩阵 588 10.3.4 关联矩阵 590 10.3.5 图的同构 590 10.3.6 判定两个简单图是否同构 591 练习 593 10.4 连通性 598 10.4.1 引言 598 10.4.2 通路 598 10.4.3 无向图的连通性 600 10.4.4 图是如何连通的 601 10.4.5 有向图的连通性 603 10.4.6 通路与同构 604 10.4.7 计算顶点之间的通路数 605 练习 606 10.5 欧拉通路与哈密顿通路 611 10.5.1 引言 611 10.5.2 欧拉通路与欧拉回路 611 10.5.3 哈密顿通路与哈密顿回路 615 10.5.4 哈密顿回路的应用 618 练习 619 10.6 最短通路问题 623 10.6.1 引言 623 10.6.2 最短通路算法 625 10.6.3 旅行商问题 629 练习 630 10.7 平面图 633 10.7.1 引言 633 10.7.2 欧拉公式 634 10.7.3 库拉图斯基定理 637 练习 638 10.8 图着色 640 10.8.1 引言 640 10.8.2 图着色的应用 644 练习 645 关键术语和结论 648 复习题 650 补充练习 651 计算机课题 656 计算和探索 656 写作课题 657 第11章 树 658 11.1 树的概述 658 11.1.1 有根树 659 11.1.2 树作为模型 662 11.1.3 树的性质 663 练习 666 11.2 树的应用 668 11.2.1 引言 668 11.2.2 二叉搜索树 668 11.2.3 决策树 671 11.2.4 前缀码 672 11.2.5 博弈树 674 练习 678 11.3 树的遍历 681 11.3.1 引言 681 11.3.2 通用地址系统 681 11.3.3 遍历算法 682 11.3.4 中缀、前缀和后缀记法 688 练习 690 11.4 生成树 693 11.4.1 引言 693 11.4.2 深度优先搜索 694 11.4.3 宽度优先搜索 696 11.4.4 回溯的应用 698 11.4.5 有向图中的深度优先搜索 700 练习 701 11.5 最小生成树 704 11.5.1 引言 704 11.5.2 最小生成树算法 704 练习 707 关键术语和结论 709 复习题 710 补充练习 711 计算机课题 714 计算和探索 714 写作课题 715 第12章 布尔代数 716 12.1 布尔函数 716 12.1.1 引言 716 12.1.2 布尔表达式和布尔函数 717 12.1.3 布尔代数恒等式 718 12.1.4 对偶性 720 12.1.5 布尔代数的抽象定义 720 练习 721 12.2 布尔函数的表示 722 12.2.1 积之和展开式 723 12.2.2 函数完备性 724 练习 724 12.3 逻辑门电路 725 12.3.1 引言 725 12.3.2 门的组合 726 12.3.3 电路的例子 726 12.3.4 加法器 728 练习 729 12.4 电路的极小化 731 12.4.1 引言 731 12.4.2 卡诺图 732 12.4.3 无须在意的条件 737 12.4.4 奎因-莫可拉斯基方法 737 练习 741 关键术语和结论 743 复习题 744 补充练习 744 计算机课题 746 计算和探索 746 写作课题 747 第13章 计算模型 748 13.1 语言和文法 748 13.1.1 引言 748 13.1.2 短语结构文法 749 13.1.3 短语结构文法的类型 751 13.1.4 派生树 752 13.1.5 巴克斯-诺尔范式 754 练习 755 13.2 带输出的有限状态机 758 13.2.1 引言 758 13.2.2 带输出的有限状态机 759 练习 762 13.3 不带输出的有限状态机 764 13.3.1 引言 764 13.3.2 串的集合 764 13.3.3 有限状态自动机 765 13.3.4 有限状态机的语言识别 766 13.3.5 非确定性的有限状态自动机 771 练习 773 13.4 语言的识别 777 13.4.1 引言 777 13.4.2 克莱因定理 778 13.4.3 正则集合和正则文法 781 13.4.4 一个不能由有限状态自动机识别的集合 783 13.4.5 一些更强大的机器 783 练习 784 13.5 图灵机 786 13.5.1 引言 786 13.5.2 图灵机的定义 787 13.5.3 用图灵机识别集合 789 13.5.4 用图灵机计算函数 790 13.5.5 不同类型的图灵机 790 13.5.6 丘奇-图灵论题 791 13.5.7 计算复杂度、可计算性和可判定性 791 练习 794 关键术语和结论 796 复习题 797 补充练习 798 计算机课题 800 计算和探索 800 写作课题 800 附录A 实数和正整数的公理 802 附录B 指数与对数函数 807 附录C 伪代码 809 推荐读物 813 参考文献 817 奇数编号练习答案

Kenneth H. Rosen，作为位于新泽西州蒙茅斯县的 AT＆T 实验室杰出技术会员，已经拥有一段很长的职业生涯。目前他在蒙茅斯大学任访问研究教授，为研究生讲授计算机科学课程。 Rosen 博士于1972年获得位于安娜堡的密歇根大学数学学士学位，1976年获得麻省理工学院数学博士学 位，在 Harold Stark 的指导下他撰写了数论方面的博士论文。1982年加入贝尔实验室之前，他曾就职于科罗拉多大学博尔德分校；哥伦布市的俄亥俄州立大学；在欧洛诺市的缅因大学任数学副教授。在 AT&T 工作时，他在蒙茅斯大学任教，教授离散数学、编码理论和数据安全方面的课程。他目前教授算法设计以及计算机安全和密码学方面的课程。

暂无其它内容！

• 国外离散数学教材普遍没有代数结构内容

  来源：豆瓣 发布时间：2025-04-28 21:31:34

• 时间充裕值得细读

  来源：豆瓣 发布时间：2025-04-28 21:31:34

• 不推荐已经接受过本科教育的人去读

  来源：豆瓣 发布时间：2025-04-28 21:31:34