本书是在**精品课程、**精品资源共享课程和**本科课程“离散数学”的基础上,结合**工程师教育培养计划和新工科建设编写而成的。全书共10章,系统介绍了数理逻辑、集合与关系、图论,以及代数系统与布尔代数中的基本概念、算法、定理及其证明方法。本书不仅注重基本概念的描述,还特别注重阐述有关离散数学的证明方法及离散数学问题求解的算法,并且举出大量的应用实例,充分展示了离散数学在软件工程和计算机科学与技术中的基础作用和强大应用。

第1章集合论 本章思维导图1 历史人物2 11集合的基本概念2 111集合的表示3 112集合与集合的关系4 113几个特殊集合6 12集合的运算7 13无限集9 131可数集9 132不可数集11 14与集合相关的应用12 141集合的计算机表示12 142计数问题13 15习题14 第2章命题逻辑 本章思维导图16 历史人物17 21命题与命题联结词17 211命题17 212命题联结词18 213自然语言的命题符号化23 22命题公式、解释与真值表25 221命题公式25 222命题公式的解释与真值表26 223命题公式的基本等价定律29 23公式的标准型——范式33 231命题联结词的完备集33 232析取范式和合取范式34 233主析取范式和主合取范式36 24命题逻辑的推理理论43 241推理的基本概念43 242推理有效性的判别方法44 25命题逻辑的应用51 251命题联结词的应用51 252命题公式的应用53 253范式的应用55 254命题逻辑推理的应用56 26习题58 第3章谓词逻辑 本章思维导图64 历史人物65 31自然语言的谓词符号化65 311谓词65 312量词67 32谓词公式与解释70 321谓词公式70 322自由变元和约束变元71 323谓词公式的解释73 324谓词公式的基本等价定律77 33谓词公式的标准型——前束范式79 331前束范式80 332Skolem范式*80 34谓词逻辑的推理理论81 341推理规则与推理定律81 342推理有效性的判别方法84 35谓词逻辑的应用87 36习题89 第4章二元关系 本章思维导图94 历史人物95 41二元关系及其表示96 411序偶和笛卡儿积96 412关系的定义98 413关系的表示法99 42关系的运算104 421关系的复合运算104 422关系的逆运算107 423关系的幂运算109 43关系的性质111 431关系性质的定义111 432关系性质的判定定理117 433关系性质的保守性119 44关系的闭包120 45关系的应用124 451二元关系及表示的应用124 452关系运算的应用126 46习题127 第5章特殊关系 本章思维导图131 历史人物132 51相容关系132 511相容关系的定义132 512集合的覆盖134 52等价关系134 521等价关系的定义135 522集合的划分137 523等价类与商集137 524等价关系与划分14053次序关系142 531拟序关系143 532偏序关系144 533全序关系149 534良序关系150 54函数151 541函数的基本概念151 542函数的运算157 543置换函数159 55特殊关系的应用160 551等价关系的应用160 552次序关系的应用161 553函数的应用162 554置换函数的应用165 56习题166 第6章图 本章思维导图171 历史人物172 61图的基本概念172 611图的定义172 612图的表示173 613图的操作175 614邻接点与邻接边176 615图的分类178 616子图与补图180 62握手定理183 63图的同构185 64通路与回路187 641通路与回路的概念187 642通路与回路的计算188 643可达与距离191 644无向赋权图的短通路194 65图的连通性196 651无向图的连通性196 652有向图的连通性198 66图的应用200 661网络的结构200 662渡河问题201 663均分问题202 67习题202 第7章特殊图 本章思维导图206 历史人物207 71树207 711树的基本概念及性质208 712生成树及算法210 72根树216 721根树的定义与分类216 722根树的遍历220 723树与哈夫曼算法222 73欧拉图224 731欧拉图的引入与定义224 732欧拉图的判定226 74哈密顿图228 741哈密顿图的引入与定义228 742哈密顿图的判定230 75偶图232 751偶图的定义232 752偶图的判定233 753匹配234 76平面图236 761平面图的定义236 762平面图的简单判定方法——观察法237 763欧拉公式238 764库拉托夫斯基定理241 77特殊图的应用242 771无向树的应用242 772根树的应用242 773欧拉图的应用247 774哈密顿图的应用250 775偶图的应用253 776平面图的应用253 78习题253 第8章代数系统 本章思维导图258 历史人物259 81代数系统259 811代数运算259 812代数系统与子代数261 82代数系统的基本运算性质263 821二元运算律263 822二元运算的特殊元266 83同态与同构272 831同态与同构的定义273 832同态的性质275 84代数系统的应用276 841代数系统的计算机表示276 842数据库与关系代数277 85习题277 第9章群、环、域 本章思维导图280 历史人物281 91群的基本概念281 911群的定义及基本性质281 912元素的阶285 913子群287 914群的同态和同构290 92特殊群292 921循环群292 922置换群295 93陪集与拉格朗日定理300 931陪集300 932拉格朗日定理303 94正规子群与商群304 941正规子群304 942商群306 95环和域308 951环和域的定义308 952子环、理想和商环310 953环的同态和同构312 96与群、环、域相关的应用313 961计数问题313 962多项式编码315 97习题317 第10章格与布尔代数 本章思维导图320 历史人物321 101格的定义和性质321 1011格的定义321 1012格的性质325 102子格与格同态326 1021子格和理想326 1022格同态327 103特殊格328 1031分配格与模格328 1032有界格与有补格330 104布尔代数332 105格与布尔代数的应用333 1051格与树形图结构333 1052布尔函数及其表示334 106习题335 参考文献337