离散数学及其应用(原书第8版本科教学版)/计算机科学丛书

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

肯尼思·H. 罗森（Kenneth H. Rosen） 于1972年获密歇根大学安娜堡分校数学学士学位，1976年获麻省理工学院数学博士学位。Rosen曾就职于科罗拉多大学、俄亥俄州立大学、缅因大学和蒙茅斯大学，教授离散数学、算法设计和计算机安全方面的课程；他还曾加盟贝尔实验室，并且是AT&T贝尔实验室的杰出技术人员。他的著作《初等数论及其应用》和《离散数学及其应用》均被翻译成多种语言，在全球数百所大学中广为采用。

出版者的话 改编者序 译者序 前言 在线资源 致学生 作者简介 符号表 第1章基础：逻辑和证明1 11命题逻辑1 111引言1 112命题1 113条件语句4 114复合命题的真值表6 115逻辑运算符的优先级7 116逻辑运算和比特运算7 奇数编号练习8 12命题逻辑的应用11 121引言11 122语句翻译11 123系统规范说明12 124布尔搜索12 125逻辑谜题13 126逻辑电路14 奇数编号练习15 13命题等价式17 131引言17 132逻辑等价式17 133德·摩根律的运用20 134构造新的逻辑等价式20 135可满足性21 136可满足性的应用21 137可满足性问题求解24 奇数编号练习24 14谓词和量词26 141引言26 142谓词26 143量词27 144有限域上的量词30 145受限域的量词30 146量词的优先级31 147变量绑定31 148涉及量词的逻辑等价式31 149量化表达式的否定32 1410语句到逻辑表达式的翻译33 1411系统规范说明中量词的使用34 1412选自路易斯·卡罗尔的例子35 1413逻辑程序设计35 奇数编号练习36 15嵌套量词39 151引言39 152理解涉及嵌套量词的语句39 153量词的顺序40 154数学语句到嵌套量词语句的翻译41 155嵌套量词到自然语言的翻译42 156汉语语句到逻辑表达式的翻译43 157嵌套量词的否定43 奇数编号练习44 16推理规则47 161引言47 162命题逻辑的有效论证47 163命题逻辑的推理规则48 164使用推理规则建立论证50 165消解律51 166谬误51 167量化命题的推理规则52 168命题和量化命题推理规则的组合使用53 奇数编号练习54 17证明导论56 171引言56 172一些专用术语56 173理解定理是如何陈述的56 174证明定理的方法56 175直接证明法57 176反证法58 177归谬证明法60 178证明中的错误62 179良好的开端63 奇数编号练习63 18证明的方法和策略64 181引言64 182穷举证明法和分情形证明法64 183存在性证明67 184唯一性证明69 185证明策略69 186寻找反例71 187证明策略实践71 188拼接72 189开放问题的作用74 1810其他证明方法74 奇数编号练习75 章末资料（在线） 标注“在线”的章节，请访问华章网站（wwwhzbookcom）下载。——编辑注 第2章基本结构：集合、函数、序列、求和与矩阵77 21集合77 211引言77 212文氏图79 213子集79 214集合的大小80 215幂集81 216笛卡儿积81 217使用带量词的集合符号83 218真值集和量词83 奇数编号练习83 22集合运算84 221引言84 222集合恒等式87 223扩展的并集和交集89 224集合的计算机表示90 225多重集91 奇数编号练习92 23函数94 231引言94 232一对一函数和映上函数96 233反函数和函数合成98 234函数的图101 235一些重要的函数101 236部分函数103 奇数编号练习104 24序列与求和106 241引言106 242序列106 243递推关系107 244特殊的整数序列109 245求和111 奇数编号练习114 25集合的基数116 251引言116 252可数集合117 253不可数集合119 奇数编号练习121 26矩阵122 261引言122 262矩阵算术123 263矩阵的转置和幂124 26401矩阵125 奇数编号练习126 章末资料（在线） 第3章计数128 31计数的基础128 311引言128 312基本的计数原则128 313比较复杂的计数问题132 314减法法则（两个集合的容斥原理）133 315除法法则135 316树图135 奇数编号练习136 32鸽巢原理138 321引言138 322广义鸽巢原理139 323鸽巢原理的几个简单应用141 奇数编号练习142 33排列与组合143 331引言143 332排列143 333组合145 奇数编号练习147 34二项式系数和恒等式149 341二项式定理149 342帕斯卡恒等式和三角形151 343其他的二项式系数恒等式152 奇数编号练习153 35排列与组合的推广155 351引言155 352有重复的排列155 353有重复的组合155 354具有不可区别物体的集合的排列158 355把物体放入盒子159 奇数编号练习161 36生成排列和组合163 361引言163 362生成排列163 363生成组合165 奇数编号练习166 章末资料（在线） 第4章高级计数技术167 41递推关系的应用167 411引言167 412用递推关系构造模型168 413算法与递推关系172 奇数编号练习174 42求解线性递推关系176 421引言176 422求解常系数线性齐次递推关系176 423求解常系数线性非齐次递推关系180 奇数编号练习182 43分治算法和递推关系184 431引言184 432分治递推关系184 奇数编号练习189 44生成函数191 441引言191 442关于幂级数的有用事实191 443计数问题与生成函数194 444使用生成函数求解递推关系197 445使用生成函数证明恒等式198 奇数编号练习199 45容斥201 451引言201 452容斥原理202 奇数编号练习205 46容斥原理的应用205 461引言205 462容斥原理的另一种形式206 463埃拉托斯特尼筛法206 464映上函数的个数207 465错位排列208 奇数编号练习209 章末资料（在线） 第5章关系211 51关系及其性质211 511引言211 512函数作为关系212 513集合的关系212 514关系的性质213 515关系的组合215 奇数编号练习217 52n元关系及其应用219 521引言219 522n元关系220 523数据库和关系220 524n元关系的运算221 525SQL223 526数据挖掘中的关联规则224 奇数编号练习226 53关系的表示227 531引言227 532用矩阵表示关系227 533用图表示关系229 奇数编号练习231 54关系的闭包232 541引言232 542不同类型的闭包232 543有向图中的路径233 544传递闭包234 545沃舍尔算法236 奇数编号练习239 55等价关系239 551引言239 552等价关系240 553等价类241 554等价类与划分243 奇数编号练习245 56偏序247 561引言247 562字典顺序249 563哈塞图250 564极大元与极小元251 565格253 566拓扑排序254 奇数编号练习256 章末资料（在线） 第6章图259 61图和图模型259 611图模型261 奇数编号练习266 62图的术语和几种特殊的图268 621引言268 622基本术语268 623一些特殊的简单图270 624二分图271 625二分图和匹配273 626特殊类型图的一些应用276 627从旧图构造新图277 奇数编号练习279 63图的表示和图的同构281 631引言281 632图的表示281 633邻接矩阵282 634关联矩阵283 635图的同构284 636判定两个简单图是否同构284 奇数编号练习287 64连通性290 641引言290 642通路290 643无向图的连通性292 644图是如何连通的293 645有向图的连通性295 646通路与同构296 647计算顶点之间的通路数297 奇数编号练习298 65欧拉通路与哈密顿通路300 651引言300 652欧拉通路与欧拉回路300 653哈密顿通路与哈密顿回路304 654哈密顿回路的应用306 奇数编号练习307 66最短通路问题309 661引言309 662最短通路算法311 663旅行商问题315 奇数编号练习316 67平面图318 671引言318 672欧拉公式319 673库拉图斯基定理321 奇数编号练习323 68图着色324 681引言324 682图着色的应用327 奇数编号练习328 章末资料（在线） 第7章树331 71树的概述331 711有根树332 712树作为模型335 713树的性质336 奇数编号练习338 72树的应用340 721引言340 722二叉搜索树340 723决策树342 724前缀码344 725博弈树346 奇数编号练习349 73树的遍历351 731引言351 732通用地址系统352 733遍历算法352 734中缀、前缀和后缀记法358 奇数编号练习360 74生成树362 741引言362 742深度优先搜索363 743宽度优先搜索365 744回溯的应用367 745有向图中的深度优先搜索369 奇数编号练习370 75最小生成树371 751引言371 752最小生成树算法372 奇数编号练习375 章末资料（在线） 第8章布尔代数377 81布尔函数377 811引言377 812布尔表达式和布尔函数378 813布尔代数恒等式379 814对偶性380 815布尔代数的抽象定义381 奇数编号练习382 82布尔函数的表示382 821积之和展开式383 822函数完备性384 奇数编号练习384 83逻辑门电路385 831引言385 832门的组合385 833电路的例子386 834加法器388 奇数编号练习389 84电路的极小化390 841引言390 842卡诺图391 843无须在意的条件396 844奎因莫可拉斯基方法396 奇数编号练习399 章末资料（在线） 推荐读物（在线） 参考文献（在线） 奇数编号练习答案（在线） 请访问华章网站www.hzbook.com下载。