离散数学(第2版)

本书特色表现在以下四个方面。 第一，加深理论，注重实践。大多数离散数学的教材，只注重经典的数学理论和解题，没有联系生产实践，学习者感觉理论抽象、枯燥。本书结合计算机专业的学习特点，在相应章节的例题或课后习题中编排了将离散结构理论与实际工程问题相结合的题目，并给出解决方案。 第二，突破经典，勇于发现。根据多年的教学实践和体会，编者在书中中总结了一些共性问题和有争议性的问题，对这些问题做了个人观点的阐述，抛砖引玉鼓励学习者继续深入研究和探讨。 第三，明确关系，理清脉络。本书包括数理逻辑、集合论、图论、代数结构四大部分，这四部分内容既自成理论体系，又有密切的联系，在每部分内容的讲授之前，简明阐述理论的起源、发展以及和其他理论之间的相互关系，使学习者感觉脉络清晰。 第四，突出重点，圈定难点。具体到每一章都总结出本章学习的难点和重点，并指明应掌握的基本概念和解题的技巧。

本书介绍计算机相关专业必需的离散数学基础知识，包括离散数学4大分支的基础理论——数理逻辑、集合论、代数系统和图论。全书共9章，依次为命题逻辑、谓词逻辑、集合、关系、函数、代数结构、格与布尔代数、图论及其应用、树。本书包含较多的与计算机科学和工程有关的例题和习题。本书适合作为高等院校计算机科学与技术、软件工程等相关专业的教材。

郝晓燕，博士，副教授，硕士生导师。自1994年至今任职于太原理工大学信息与计算机学院，从事计算机科学与技术学科的教学工作及科研工作。主讲课程：《工程经济学》《离散数学》《数据结构》《面各对象程序设计C++》《数据库系统原理》《自然语言处理》。研究方向：计算语言学，自然语言处理，人工智能。社会兼职：中国计算机学会会员。

第1章 命题逻辑
§1-1 命题
§1-1-1 命题与真值
§1-1-2 原子命题与复合命题
§1-2 逻辑联结词
§1-2-1 否定联结词
§1-2-2 合取联结词
§1-2-3 析取联结词
§1-2-4 蕴含联结词
§1-2-5 等价联结词
§1-3 命题公式
§1-3-1 命题公式的概念
§1-3-2 命题符号化
§1-3-3 命题公式真值表
§1-3-4 命题公式的类型
§1-3-5 重言式的性质
§1-4 命题逻辑的等价关系
§1-4-1 等价
§1-4-2 基本等价式
§1-4-3 置换规则
§1-5 命题公式的标准化
§1-5-1 析取范式与合取范式
§1-5-2 主析取范式与主合取范式
§1-5-3 主范式的应用
§1-6 命题逻辑的蕴含关系
§1-6-1 蕴含
§1-6-2 证明蕴含关系的方法
§1-6-3 基本蕴含式
§1-7 命题逻辑的推理理论
§1-7-1 推理的有效性
§1-7-2 有效推理的判断方法
§1-7-3 自然推理系统
§1-7-4 自然推理系统中构造有效推理的方法
本章总结
习题
第2章 谓词逻辑
§2-1 谓词逻辑命题符号化
§2-1-1 命题逻辑的局限性
§2-1-2 谓词逻辑三要素
§2-1-3 谓词逻辑命题符号化
§2-2 谓词公式
§2-2-1 谓词逻辑的合式公式
§2-2-2 闭式
§2-2-3 谓词公式的解释
§2-2-4 谓词逻辑的公式类型
§2-3 谓词逻辑的等价关系
§2-3-1 等价关系
§2-3-2 基本等价式
§2-4 谓词公式的标准化
§2-5 谓词逻辑的蕴含关系
§2-5-1 蕴含关系
§2-5-2 基本蕴含式
§2-6 谓词逻辑的推理理论
本章总结
习题
第3章 集合
§3-1 集合的定义与表示方法
§3-1-1 集合的定义
§3-1-2 集合的表示方法
§3-2 集合之间的重要关系
§3-2-1 集合之间的重要关系
§3-2-2 特殊集合
§3-3 集合的运算
§3-3-1 集合的基本运算
§3-3-2 集合关系的证明方法
§3-3-3 笛卡儿积
本章总结
习题
第4章 关系
§4-1 关系的概念及表示
§4-1-1 关系的概念
§4-1-2 关系的表示方法
§4-2 关系的性质
§4-2-1 自反性与反自反性
§4-2-2 对称性与反对称性
§4-2-3 传递性
§4-3 关系的运算
§4-3-1 关系的复合运算
§4-3-2 关系的逆运算
§4-3-3 关系的闭包运算
§4-4 等价关系与划分
§4-4-1 等价关系的概念
§4-4-2 等价类
§4-4-3 划分
§4-5 次序关系
§4-5-1 偏序关系
§4-5-2 其他次序关系
本章总结
习题
第5章 函数
§5-1 函数的概念与性质
§5-1-1 函数的概念
§5-1-2 函数的性质
§5-2 函数的运算
§5-2-1 函数的复合运算
§5-2-2 函数的逆运算
§5-3 基数
§5-3-1 基数的概念
§5-3-2 基数的比较
本章总结
习题
第6章 代数结构
§6-1 代数系统的概念
§6-2 代数系统的运算及其性质
§6-2-1 二元运算的性质
§6-2-2 小结
§6-3 半群与含幺半群
§6-3-1 半群和子半群
§6-3-2 含幺半群和子含幺半群
§6-4 群与子群
§6-4-1 群
§6-4-2 子群
§6-5 交换群、循环群与置换群
§6-5-1 交换群
§6-5-2 循环群
§6-5-3 置换群
§6-6 陪集与拉格朗日定理
§6-6-1 陪集
§6-6-2 拉格朗日定理
§6-6-3 正规子群
§6-7 同态与同构
§6-7-1 同态
§6-7-2 同构
§6-7-3 同余关系
§6-8 环与域
§6-8-1 环
§6-8-2 域
本章总结
习题
第7章 格与布尔代数
§7-1 格
§7-1-1 格的概念
§7-1-2 格的性质
§7-2 分配格
§7-3 有补格
§7-4 布尔代数
本章总结
习题
第8章 图论及其应用
§8-1 图的基本概念
§8-1-1 图
§8-1-2 结点的度
§8-1-3 图的同构
§8-1-4 子图和补图
§8-2 图的连通性
§8-2-1 路径与回路
§8-2-2 连通图
§8-3 图的矩阵表示
§8-3-1 图的邻接矩阵
§8-3-2 图的可达矩阵
§8-4 特殊图
§8-4-1 欧拉图
§8-4-2 哈密顿图
§8-4-3 二部图
§8-4-4 平面图
§8-5 图的应用
§8-5-1 图的应用示例
§8-5-2 特殊图的应用
本章总结
习题
第9章 树
§9-1 无向树
§9-1-1 基本概念
§9-1-2 最小生成树及其应用
§9-2 有向树
§9-2-1 基本概念
§9-2-2 有序树
§9-2-3 m叉树
§9-3 二叉树
§9-3-1 基本概念
§9-3-2 很优树
本章总结
习题
附录 习题参考答案
参考文献