离散数学（修订版）

第一篇数理逻辑 第一章命题逻辑 §1.1命题和联结词 §1.2公式和真值赋值 §1.3等值演算 §1.4对偶定理 §1.5联结词的完全集 §1.6范式 §1.7逻辑推论 习题一 第二章谓词逻辑 §2.1谓词和量词 §2.2项和公式 §2.3解释和赋值 §2.4永真式 §2.5等值演算 §2.6逻辑推论 习题二 第三章公理系统 §3.1命题逻辑的公理系统 §3.2谓词逻辑的公理系统 习题三 第四章归结法原理 §4.1命题逻辑的归结法 §4.2前束范式与斯科伦范式 §4.3谓词逻辑的归结法 习题四 参考文献 第二篇集合论 第五章集合的基本概念及其运算 §5.1集合与元素 §5.2集合间的相等和包含关系 §5.3幂集 §5.4集合的运算 §5.5有穷集的计数原理 §5.6集合的归纳定义法 §5.7有序偶和笛卡儿乘积 习题五 第六章关系 §6.1关系及其性质 §6.2关系的运算 §6.3次序关系 §6.4等价关系.划分及其他 习题六 第七章函数 §7.1基本概念 §7.2函数的复合 §7.3特殊性质的函数 §7.4集合的特征函数 习题七 第八章自然数和基数 §8.1自然数及数学归纳法 §8.2基数 习题八 参考文献 第三篇图论 第九章基本概念 §9.1有向图及无向图 §9.2图的基本结构 §9.3子图 §9.4连通性 §9.5顶点基和强分图 习题九 第十章通路问题 §10.1最短通路 §10.2关键通路 习题十 第十一章图的矩阵表示 §11.1邻接矩阵 §11.2有向图的可达性矩阵 §11.3关联矩阵 习题十一 第十二章树 §12.1树的一般定义 §12.2根树与有序树 §12.3二元树 §12.4生成树 §12.5割集 习题十二 第十三章穿程问题 §13.1欧拉图 §13.2哈密顿图 习题十三 第十四章二分图的匹配问题 §14.1基本概念 §14.2二分图的最大匹配 §14.3从X到y的匹配 习题十四 第十五章平面图及色数 §15.1平面图 §15.2色数 习题十五 参考文献 第四篇代数系统 第十六章基本概念 §16.1代数系统 §16.2同态和同构 §16.3子代数和商代数 习题十六 第十七章半群和群 §17.1半群的概念 §17.2子半群和半群同态 §17.3商半群和半群直积 §17.4群的概念 §17.5子群和群的同态 §17.6变换群.置换群和循环群 §17.7不变子群和商群 习题十七 第十八章环和域 §18.1环和域的概念 §18.2子环和环的同态 §18.3理想和商环 习题十八 第十九章格和布尔代数 §19.1格的定义与基本性质 §19.2子格和格的同态 §19.3布尔代数 §19.4布尔代数的表示 习题十九 第二十章抽象数据类型的代数规范 §20.1标记.项和代数规范 §20.2代数和范畴 §20.3代数规范的初始语义 习题二十 参考文献 第五篇有限自动机理论 第二十一章基本概念 §21.1字符表.字符串及其集合的运算 §21.2有限自动机的定义 §21.3有限自动机的等价 §21.4Mealy机与Moore机 习题二十一 第二十二章有限自动机的简化 §22.1最小有限自动机的定义及性质 §22.2状态集的S划分和格LM §22.3有限自动机的最小化 习题二十二 第二十三章有限自动机和正则表达式 §23.1有限自动机的识别功能 §23.2非确定有限自动机名词索引 §23.3正则表达式 §23.4由正则表达式构造FA的算法 §23.5有限自动机和正则表达式的等价性 §23.6正则集合及其性质 习题二十三 第二十四章有限自动机的综合与应用 §24.1有限自动机的综合 §24.2FA理论在算法设计中的应用 §24.3FA理论与形式语言理论的关系 习题二十四 参考文献

第一篇数理逻辑

第一章命题逻辑

§1.1命题和联结词

§1.2公式和真值赋值

§1.3等值演算

§1.4对偶定理

§1.5联结词的完全集

§1.6范式

§1.7逻辑推论

习题一

第二章谓词逻辑

§2.1谓词和量词

§2.2项和公式

§2.3解释和赋值

§2.4永真式

§2.5等值演算

§2.6逻辑推论

习题二

第三章公理系统

§3.1命题逻辑的公理系统

§3.2谓词逻辑的公理系统

习题三

第四章归结法原理

§4.1命题逻辑的归结法

§4.2前束范式与斯科伦范式

§4.3谓词逻辑的归结法

习题四

参考文献

第二篇集合论

第五章集合的基本概念及其运算

§5.1集合与元素

§5.2集合间的相等和包含关系

§5.3幂集

§5.4集合的运算

§5.5有穷集的计数原理

§5.6集合的归纳定义法

§5.7有序偶和笛卡儿乘积

习题五

第六章关系

§6.1关系及其性质

§6.2关系的运算

§6.3次序关系

§6.4等价关系.划分及其他

习题六

第七章函数

§7.1基本概念

§7.2函数的复合

§7.3特殊性质的函数

§7.4集合的特征函数

习题七

第八章自然数和基数

§8.1自然数及数学归纳法

§8.2基数

习题八

参考文献

第三篇图论

第九章基本概念

§9.1有向图及无向图

§9.2图的基本结构

§9.3子图

§9.4连通性

§9.5顶点基和强分图

习题九

第十章通路问题

§10.1最短通路

§10.2关键通路

习题十

第十一章图的矩阵表示

§11.1邻接矩阵

§11.2有向图的可达性矩阵

§11.3关联矩阵

习题十一

第十二章树

§12.1树的一般定义

§12.2根树与有序树

§12.3二元树

§12.4生成树

§12.5割集

习题十二

第十三章穿程问题

§13.1欧拉图

§13.2哈密顿图

习题十三

第十四章二分图的匹配问题

§14.1基本概念

§14.2二分图的最大匹配

§14.3从X到y的匹配

习题十四

第十五章平面图及色数

§15.1平面图

§15.2色数

习题十五

参考文献

第四篇代数系统

第十六章基本概念

§16.1代数系统

§16.2同态和同构

§16.3子代数和商代数

习题十六

第十七章半群和群

§17.1半群的概念

§17.2子半群和半群同态

§17.3商半群和半群直积

§17.4群的概念

§17.5子群和群的同态

§17.6变换群.置换群和循环群

§17.7不变子群和商群

习题十七

第十八章环和域

§18.1环和域的概念

§18.2子环和环的同态

§18.3理想和商环

习题十八

第十九章格和布尔代数

§19.1格的定义与基本性质

§19.2子格和格的同态

§19.3布尔代数

§19.4布尔代数的表示

习题十九

第二十章抽象数据类型的代数规范

§20.1标记.项和代数规范

§20.2代数和范畴

§20.3代数规范的初始语义

习题二十

参考文献

第五篇有限自动机理论

第二十一章基本概念

§21.1字符表.字符串及其集合的运算

§21.2有限自动机的定义

§21.3有限自动机的等价

§21.4Mealy机与Moore机

习题二十一

第二十二章有限自动机的简化

§22.1最小有限自动机的定义及性质

§22.2状态集的S划分和格LM

§22.3有限自动机的最小化

习题二十二

第二十三章有限自动机和正则表达式

§23.1有限自动机的识别功能

§23.2非确定有限自动机名词索引

§23.3正则表达式

§23.4由正则表达式构造FA的算法

§23.5有限自动机和正则表达式的等价性

§23.6正则集合及其性质

习题二十三

第二十四章有限自动机的综合与应用

§24.1有限自动机的综合

§24.2FA理论在算法设计中的应用

§24.3FA理论与形式语言理论的关系

习题二十四

参考文献