离散数学
2004-5
邮电大学
科尔曼
本书是作者参照国内外多种同类教材，结合多年的教学实践经验，在自编讲义的基础上整理而成的。全书覆盖了计算机专业和电子信息专业最需要的基本内容，它包括四大部分共14章。介绍了数理逻辑、集合论、代数系统和图论的基础知识以及这四个部分之间的内在联系，叙述详细、推演严密，注重基础，深入浅出，便于理解。
本书可作为高等院校计算机类、电子信息类等相关专业的教材，也可供计算机专业的自考人员、从事计算机研究的工作人员参考。
第一部分 数理逻辑
第一章 命题逻辑基本概念 （3）
§1.1 命题及其符号化 （3）
§1.1.1 命题 （3）
§1.1.2 命题符号化 （4）
§1.2 合式公式和真值赋值 （10）
§1.2.1 合式公式及层次 （10）
§1.2.2 真值赋值及公式分类 （12）
§1.3 真值表和真值函数 （14）
习题一 （16）
第二章 命题逻辑等值演算 （19）
§2.1 等值关系 （19）
§2.2 联结词的全功能集 （24）
§2.3 范式 （27）
*§2.4 数字逻辑电路初步 （34）
§2.4.1 门电路和触发器 （34）
§2.4.2 组合逻辑电路的设计 （36）
§2.4.3 时序逻辑电路的设计 （38）
习题二 （42）
第三章 命题逻辑自然推理 （44）
§3.1 推理的形式结构 （44）
§3.2 自然推理系统P （47）
§3.3 常见的证明方法 （49）
习题三 （53）
第四章 谓词逻辑的基本概念 （54）
§4.1 谓词和量词 （55）
§4.2 一阶语言 （59）
§4.2.1 一阶语言 （60）
§4.2.2 解释和赋值 （63）
§4.2.3 公式的分类 （66）
§4.3 一阶逻辑等值演算 （67）
§4.3.1 等值演算 （67）
§4.3.2 前束范式 （69）
§4.4 一阶逻辑形式推理 （71）
§4.4.1 推理定律 （71）
§4.4.2 推理规则 （72）
习题四 （75）
第二部分 集合论
第五章 集合代数 （79）
§5.1 集合的概念及表示 （79）
§5.2 集合运算 （85）
§5.3 集合定律 （89）
§5.4 有限集的计数问题 （90）
§5.5 有序对与卡氏积 （94）
习题五 （96）
第六章 二元关系 （99）
§6.1 二元关系及其表示 （99）
§6.2 二元关系的性质 （102）
§6.3 二元关系的运算 （104）
§6.3.1 关系的限制和像 （104）
§6.3.2 关系的逆 （106）
§6.3.3 关系的合成 （106）
§6.3.4 关系的闭包 （109）
§6.4 特殊关系及其性质 （117）
§6.4.1 等价关系及性质 （117）
§6.4.2 相容关系及性质 （120）
§6.4.3 序关系及性质 （123）
习题六 （127）
第七章 函数 （130）
§7.1 函数基本概念 （130）
§7.2 函数的合成 （134）
§7.3 反函数 （137）
§7.4 特殊函数 （140）
§7.4.1 特征函数 （140）
§7.4.2 变换函数和置换函数 （142）
§7.5 集合的基数 （146）
习题七 （150）
第三部分 代数系统
第八章 代数结构 （152）
§8.1 代数系统基本概念 （152）
§8.1.1 代数运算及其性质 （152）
§8.1.2 代数系统 （156）
§8.1.3 积代数和商代数 （157）
§8.2 半群和群 （159）
§8.2.1 半群 （159）
§8.2.2 群 （161）
§8.2.3 子群和陪集 （170）
§8.3 环和域 （174）
*§8.4 差错编码初步 （179）
*§8.5 差错解码初步 （185）
习题八 （188）
第九章 格与布尔代数 （191）
§9.1 格的定义和性质 （191）
§9.2 分配格与有补格 （197）
§9.3 布尔代数 （200）
习题九 （203）
第四部分 图 论
第十章 图 （207）
§10.1 图的基本概念 （207）
§10.1.1 有向图和无向图 （207）
§10.1.2 关联和相邻或邻接 （209）
§10.1.3 点的度数 （209）
§10.1.4 特殊图 （211）
§10.1.5 图的同构 （213）
§10.2 图的运算 （214）
§10.3 图的连通性 （218）
§10.3.1 通路和回路 （218）
§10.3.2 无向图的连通性 （219）
§10.3.3 有向图的连通性 （222）
§10.4 图的矩阵表示 （225）
§10.4.1 无向图的矩阵表示 （225）
§10.4.2 有向图的矩阵表示 （230）
习题十 （234）
第十一章 通路应用问题 （236）
§11.1 最短径问题 （236）
§11.2 关键路径问题 （240）
§11.3 网络最大流量问题 （242）
§11.4 穿程问题 （248）
§11.4.1 欧拉图 （248）
§11.4.2 哈密顿图 （250）
习题十一 （254）
第十二章 树 （256）
§12.1 无向树基本概念 （256）
§12.2 生成树 （258）
§12.2.1 生成树及其做法 （258）
§12.2.2 生成树的应用 （262）
§12.3 最小生成树 （266）
§12.4 根树 （269）
§12.5 二叉树应用 （275）
习题十二 （279）
第十三章 平面图 （281）
§13.1 平面图基本概念 （281）
§13.2 欧拉公式 （284）
§13.3 平面图的判断 （287）
§13.4 对偶图及着色 （289）
习题十三 （293）
第十四章 偶图与匹配 （295）
§14.1 偶图的判断 （295）
§14.2 匹配 （296）
习题十四 （300）
附录1 数学工具 （302）
附录2 习题答案或提示 （308）
参考文献 （348）
