《应用离散数学（第二版）》课后习题答案

《应用离散数学(第2版)》是2020年1月人民邮电出版社出版的图书，作者是方景龙、周丽。

本书从应用的角度介绍离散数学。全书共分6章，分别是命题逻辑、谓词逻辑、集合与关系、代数结构、图和有向图。全书体系严谨，叙述深入浅出，并配有大量与计算机科学相关的有实际背景的例题和习题。在每章最后增加了上机作业，可增强学生对课堂教学内容的理解和掌握，提高学生的学习兴趣和动手能力。这对于学生学习、理解和应用离散数学理论有很大的帮助。

本书可作为普通高等学校计算机科学与技术或相关专业的本科生教材。

目录

• 第 1章　命题逻辑　1
• 1.1　命题和逻辑连接词　2
• 1.1.1　命题　2
• 1.1.2　逻辑连接词与命题符号化　4
• 习题1.1　7
• 1.2　命题公式及其真值表　8
• 1.2.1　命题公式　8
• 1.2.2　真值表　8
• 习题1.2　11
• 1.3　命题公式的等价演算　12
• 习题1.3　15
• 1.4　命题公式的范式　15
• 1.4.1　析取范式与合取范式　15
• 1.4.2　标准析取范式和标准合取范式　18
• 1.4.3　利用真值表求解标准范式　20
• 1.4.4　标准析取范式和标准合取范式的关系　22
• 习题1.4　23
• 1.5　命题公式的推理演算　25
• 1.5.1　基本概念　25
• 1.5.2　演绎推理方法　27
• 1.5.3　附加前提法　28
• 习题1.5　30
• 1.6　逻辑门电路　32
• 1.6.1　门电路　32
• 1.6.2　逻辑电路设计　33
• 习题1.6　35
• 第 1章上机练习　35
• 第 2章　谓词逻辑　37
• 2.1　个体词、谓词与量词　37
• 2.1.1　个体词与谓词　37
• 2.1.2　量词　38
• 习题2.1　40
• 2.2　谓词公式及其解释　42
• 2.2.1　谓词公式　42
• 2.2.2　谓词公式的解释　43
• 习题2.2　46
• 2.3　谓词公式的等价演算　47
• 习题2.3　49
• 2.4　谓词公式的推理演算　50
• 2.4.1　基本概念　50
• 2.4.2　演绎推理方法　51
• 习题2.4　55
• 第 2章上机练习　56
• 第3章　集合与关系　58
• 3.1　集合及其运算　58
• 3.1.1　基本概念　58
• 3.1.2　集合的运算　60
• 3.1.3　集合的计算机表示　62
• 习题3.1　63
• 3.2　二元关系及其运算　65
• 3.2.1　笛卡尔积　65
• 3.2.2　二元关系及其表示　66
• 3.2.3　二元关系的运算　67
• 习题3.2　70
• 3.3　二元关系的性质与闭包　71
• 3.3.1　二元关系的性质　71
• 3.3.2　二元关系的闭包　73
• 习题3.3　75
• 3.4　等价关系与划分　77
• 习题3.4　80
• 3.5　偏序关系与拓扑排序　80
• 3.5.1　偏序关系　80
• 3.5.2　偏序集中的特殊元　82
• 3.5.3　拓扑排序　84
• 习题3.5　85
• 3.6　函数　87
• 3.6.1　基本概念　87
• 3.6.2　复合函数　88
• 3.6.3　逆函数　90
• 习题3.6　91
• 3.7　集合的等势与基数　92
• 习题3.7　93
• 3.8　多元关系及其应用　93
• 3.8.1　多元关系　93
• 3.8.2　关系数据库　94
• 3.8.3　数据库的检索　95
• 3.8.4　插入、删除与修改　96
• 习题3.8　97
• 第3章上机练习　98
• 第4章　代数结构　99
• 4.1　代数运算　99
• 4.1.1　基本概念　99
• 4.1.2　二元运算的性质　100
• 4.1.3　二元运算中的特殊元　101
• 习题4.1　103
• 4.2　代数系统　104
• 习题4.2　106
• 4.3　群　107
• 4.3.1　基本概念　107
• 4.3.2　幂运算　109
• 4.3.3　群的性质　110
• 习题4.3　113
• 4.4　子群与陪集　114
• 4.4.1　子群　114
• 4.4.2　陪集　116
• 4.4.3　正规子群与商群　118
• 4.4.4　群同态与同构　119
• 习题4.4　120
• 4.5　循环群、置换群　121
• 4.5.1　循环群　121
• 4.5.2　置换群　122
• 习题4.5　125
• 4.6　环与域　125
• 4.6.1　环　126
• 4.6.2　整环与域　127
• 习题4.6　128
• 4.7　格与布尔代数　129
• 4.7.1　格　129
• 4.7.2　几种特殊的格　130
• 4.7.3　布尔代数　132
• 习题4.7　133
• 第4章上机练习　134
• 第5章　图　135
• 5.1　基本概念　135
• 5.1.1　图的定义　135
• 5.1.2　顶点的度　137
• 习题5.1　139
• 5.2　图的连通性　139
• 5.2.1　通路　139
• 5.2.2　连通图　141
• 5.2.3　图的矩阵表示　144
• 习题5.2　147
• 5.3　欧拉图与哈密尔顿图　148
• 5.3.1　欧拉图　148
• 5.3.2　哈密尔顿图　150
• 5.3.3　旅行商问题　151
• 习题5.3　152
• 5.4　最短通路　153
• 5.4.1　广义优先搜索　153
• 5.4.2　Dijkstra算法　156
• 5.4.3　中国邮递员问题　158
• 习题5.4　159
• 5.5　树　160
• 5.5.1　基本概念　160
• 5.5.2　生成树　163
• 5.5.3　深度优先搜索　165
• 5.5.4　最小生成树　168
• 习题5.5　171
• 5.6　平面图及图的着色　173
• 5.6.1　平面图　173
• 5.6.2　图的着色　176
• 习题5.6　179
• 第5章上机练习　180
• 第6章　有向图　181
• 6.1　有向图概述　181
• 6.1.1　基本概念　181
• 6.1.2　有向图的连通性　182
• 6.1.3　有向图的矩阵表示　184
• 习题6.1　186
• 6.2　根　树　187
• 6.2.1　基本概念　187
• 6.2.2　二叉搜索树　188
• 6.2.3　最优二叉树　190
• 习题6.2　193
• 6.3　网络流　194
• 6.3.1　基本概念　194
• 6.3.2　最大流算法　196
• 6.3.3　最大流最小割定理　202
• 习题6.3　203
• 6.4　匹配　205
• 习题6.4　207
• 第6章上机练习　208
• 参考文献　209