离散数学(第3版高等学校计算机教育规划教材)

\\\"离散数学是计算机科学与技术专业的一门重要基础课。全书共10章，主要包含数理逻辑、集合与关系、函数、组合计数、图和树、代数系统、自动机和初等数论等内容。新增应用案例，阐明相应章节的知识可以解决什么样的典型应用问题。本书“历史注记”可以帮助读者理解数学，洞察内在本质。 本书体系严谨，选材精炼，讲解翔实，例题丰富，注重理论与计算机科学技术的实际问题相结合，并选配了大量难度适当的习题，并给出奇数题的答案，适合教学。本书适合作为计算机类和相关专业本科生“离散数学”的教学用书。 \\\"

贲可荣，海军工程大学教授、博导，CCF理论计算机科学专委副主任，《计算机科学与探索》执行编委，获军队育才奖金奖，评为教育部骨干教师，主编《人工智能》入选普通高等教育“十二五”国家级规划教材。

第1章命题逻辑1 1.1现代逻辑学的基本研究 方法1 1.2命题及其表示法3 1.2.1命题的概念3 1.2.2联结词4 1.3命题公式与语句形式化8 1.3.1命题公式的定义8 1.3.2公式的层次8 1.3.3语句形式化9 1.3.4复合命题真假值9 1.3.5真值表11 1.4重言式12 1.4.1重言式概述12 1.4.2逻辑等价式13 1.4.3等值演算16 1.5对偶与范式16 1.5.1对偶16 1.5.2简单合取式和简单 析取式17 1.5.3范式18 1.5.4范式的唯一性—— 主范式20 1.6其他联结词24 1.6.1n元真值函数24 1.6.2真值函数与命题 公式的关系25 1.6.3联结词完备集25 1.6.4单元素联结词构成 的联结词完备集26 1.7命题演算的推理理论27 1.7.1有效推理27 1.7.2有效推理的等价 定理29 1.7.3重言蕴涵式30 1.7.4形式推理系统31 1.7.5自然推理系统P234 1.8命题演算中的归结推理38 1.8.1归结推理规则38 1.8.2归结反演40 1.8.3命题逻辑归结反演的 合理性和完备性41 1.9应用案例41 1.9.1克雷格探长案卷录41 1.9.2忘却林中的艾丽丝 （狮子与独角兽）43 习题44 计算机编程题52 第2章谓词逻辑53 2.1谓词逻辑的基本概念53 2.1.1个体词54 2.1.2谓词54 2.1.3量词55 2.2谓词逻辑公式与翻译56 2.2.1一阶语言56 2.2.2自由与约束57 2.2.3闭公式58 2.2.4谓词逻辑公式的 解释59 2.2.5谓词逻辑命题符 号化60 2.2.6一阶公式的分类63 2.3谓词逻辑等值演算64 2.3.1基本等价式与置换 规则64 2.3.2谓词逻辑前束 范式67 2.4谓词演算的推理理论68 2.4.1推理定律69 2.4.2量词消去与引入 规则69 2.4.3一阶谓词演算公理 系统F170 2.4.4自然推理系统F271 2.5谓词演算中的归结推理73 2.5.1子句型73 2.5.2置换和合一75 2.5.3合一算法77 2.5.4归结式77 2.5.5归结反演及其完 备性78 2.6应用案例79 2.6.1电路领域的知识 工程79 2.6.2基于逻辑的财务 顾问80 2.7逻辑在计算机科学中的 作用80 2.7.1逻辑与计算80 2.7.2逻辑与计算机的 起源81 2.7.3逻辑与程序设计81 习题81 计算机编程题86 离散数学（第3版）目录第3章集合与关系88 3.1集合的概念和表示法88 3.1.1集合的表示88 3.1.2基本概念89 3.2集合的运算91 3.2.1集合的基本运算91 3.2.2有穷计数集92 3.2.3包含排斥原理93 3.2.4广义交和广义并94 3.3有序对与笛卡儿积96 3.4关系及其表示98 3.4.1基本概念98 3.4.2关系表示法99 3.5关系的运算101 3.5.1基本概念101 3.5.2复合关系102 3.5.3逆关系103 3.5.4关系幂105 3.5.5幂运算的性质106 3.6关系的性质108 3.6.1关系的5种基本 性质108 3.6.2关系性质的等价 描述109 3.7关系的闭包112 3.7.1基本概念112 3.7.2闭包的性质116 3.8集合的划分与覆盖118 3.9等价关系和等价类119 3.9.1等价关系119 3.9.2等价类的性质120 3.9.3商集与划分121 3.10相容关系和相容类122 3.11偏序关系124 3.12偏序集与哈斯图125 3.13应用案例128 3.13.1同余关系在出版 业中的应用128 3.13.2拓扑排序在建筑 工序中的应用128 3.13.3等价关系在软件 测试等价类划分 中的应用129 习题129 计算机编程题135 第4章函数136 4.1函数的定义136 4.1.1函数和像136 4.1.2函数的性质138 4.1.3常用函数139 4.2复合函数和反函数140 4.2.1复合函数140 4.2.2反函数142 4.3特征函数与模糊子集144 4.4基数的概念146 4.4.1后继与归纳集146 4.4.2自然数，有穷集， 无穷集147 4.4.3基数152 4.5可数集与不可数集153 4.6数学归纳法154 4.7应用案例157 4.7.1逢黑必反魔术157 4.7.2生成函数在解决汉诺塔 问题中的应用158 习题158 计算机编程题162 第5章组合计数163 5.1基本原理163 5.1.1加法原理163 5.1.2乘法原理164 5.2排列与组合165 5.2.1排列165 5.2.2组合165 5.3排列组合生成算法166 5.3.1排列生成算法166 5.3.2组合生成算法168 5.4广义的排列和组合170 5.5二项式系数和组合恒 等式171 5.5.1二项式定理171 5.5.2组合恒等式173 5.6鸽笼原理174 5.6.1鸽笼原理的简单 形式174 5.6.2鸽笼原理的一般 形式174 5.7递推关系及应用176 5.7.1递推定义函数176 5.7.2递推定义集合177 5.7.3递推关系模型178 5.7.4求解递推关系180 5.7.5递推在算法分析中的 应用181 5.7.6生成函数183 5.8应用案例186 5.8.1大使馆通信的码 字数186 5.8.2条条道路通罗马186 习题187 计算机编程题188 第6章图论189 6.1图的基本概念189 6.1.1图的定义和表示189 6.1.2图的同构194 6.1.3完全图与正则图195 6.1.4子图与补图195 6.1.5通路与回路198 6.2图的连通性199 6.2.1无向图的连通性199 6.2.2有向图的连通性201 6.3图的矩阵表示202 6.3.1关联矩阵202 6.3.2有向图的邻接 矩阵203 6.3.3有向图的可达 矩阵204 6.4欧拉图204 6.5哈密顿图207 6.6二部图210 6.6.1二部图及判别 定理210 6.6.2完备匹配211 6.7平面图213 6.7.1平面图及其判定 定理213 6.7.2平面图的对偶图219 6.8带权图220 6.9应用案例221 6.9.1网络爬虫221 6.9.2读心术魔术222 6.9.3高度互联世界的 行为原理222 习题222 计算机编程题229 第7章树及其应用230 7.1概述230 7.1.1树的定义及相关 术语230 7.1.2树的性质232 7.2生成树233 7.3最小生成树237 7.4树的遍历239 7.5二叉树241 7.5.1二叉树的性质241 7.5.2二叉搜索树242 7.5.3哈夫曼树242 7.6决策树244 7.6.1决策树的定义245 7.6.2最短时间排序246 7.7树的同构247 7.8博弈树251 7.8.1博弈树的概念251 7.8.2极大极小分析法252 7.9应用案例254 7.9.1哈夫曼压缩算法的 基本原理254 7.9.2决策树在风险决策 中的应用254 7.9.3一字棋博弈的极大 极小过程255 习题255 计算机编程题257 第8章代数系统259 8.1二元运算及其性质259 8.1.1定义和表示259 8.1.2二元运算的性质261 8.2代数系统263 8.2.1定义和实例263 8.2.2子代数系统265 8.2.3代数系统的同态 与同构266 8.3半群与独异点266 8.3.1定义与性质266 8.3.2子系统与直积268 8.4群269 8.4.1群的定义269 8.4.2群的性质271 8.4.3子群的定义273 8.4.4特殊的群274 8.4.5陪集与拉格朗日 定理277 8.4.6正规子群与商群278 8.4.7群的同态与同构 实例280 8.5环与域282 8.5.1环282 8.5.2域284 8.6格与布尔代数284 8.6.1格284 8.6.2布尔代数288 8.7应用案例291 8.7.1组合电路291 8.7.2物理世界中群的 应用292 8.7.3群码及纠错能力292 习题292 计算机编程题299 第9章自动机、文法和语言300 9.1串和语言300 9.2形式文法301 9.3有限状态机304 9.4有限状态自动机306 9.5不确定有限状态自动机310 9.6语言和自动机之间的 关系313 9.7应用案例314 9.7.1奇偶校验机314 9.7.2识别地址的有限 状态机314 9.7.3语音识别315 习题315 计算机编程题318 第10章数论与密码学319 10.1素数319 10.2最大公约数与最小公 倍数320 10.3同余323 10.4一次同余方程和中国 剩余定理325 10.4.1一次同余方程325 10.4.2中国剩余定理326 10.5欧拉定理和费马小 定理327 10.6数论在密码学中的 应用328 10.6.1公钥密码学328 10.6.2RSA密码328 10.7应用案例330 10.7.1密码系统与公开 密钥330 10.7.2单向陷门函数在 公开密钥密码系 统中的应用330 习题331 计算机编程题331 附录历史注记332 参考文献334