离散数学(第2版)

第1章 命题逻辑　1
§1-1　命题　1
§1-1-1　命题与真值　1
§1-1-2　原子命题与复合命题　2
§1-2　逻辑联结词　3
§1-2-1　否定联结词　3
§1-2-2　合取联结词　3
§1-2-3　析取联结词　4
§1-2-4　蕴含联结词　4
§1-2-5　等价联结词　5
§1-3　命题公式　5
§1-3-1　命题公式的概念　5
§1-3-2　命题符号化　6
§1-3-3　命题公式真值表　7
§1-3-4　命题公式的类型　9
§1-3-5　重言式的性质　9
§1-4　命题逻辑的等价关系　9
§1-4-1　等价　10
§1-4-2　基本等价式　10
§1-4-3　置换规则　11
§1-5　命题公式的标准化　13
§1-5-1　析取范式与合取范式　13
§1-5-2　主析取范式与主合取范式　14
§1-5-3　主范式的应用　16
§1-6　命题逻辑的蕴含关系　17
§1-6-1　蕴含　17
§1-6-2　证明蕴含关系的方法　17
§1-6-3　基本蕴含式　18
§1-7　命题逻辑的推理理论　18
§1-7-1　推理的有效性　18
§1-7-2　有效推理的判断方法　18
§1-7-3　自然推理系统　19
§1-7-4　自然推理系统中构造有效推理的方法　21
本章总结　23
习题　23
第2章　谓词逻辑　25
§2-1　谓词逻辑命题符号化　25
§2-1-1　命题逻辑的局限性　25
§2-1-2　谓词逻辑三要素　25
§2-1-3　谓词逻辑命题符号化　27
§2-2　谓词公式　28
§2-2-1　谓词逻辑的合式公式　28
§2-2-2　闭式　28
§2-2-3　谓词公式的解释　29
§2-2-4　谓词逻辑的公式类型　30
§2-3　谓词逻辑的等价关系　31
§2-3-1　等价关系　31
§2-3-2　基本等价式　31
§2-4　谓词公式的标准化　32
§2-5　谓词逻辑的蕴含关系　33
§2-5-1　蕴含关系　33
§2-5-2　基本蕴含式　33
§2-6　谓词逻辑的推理理论　33
本章总结　35
习题　36
第3章　集合　38
§3-1　集合的定义与表示方法　38
§3-1-1　集合的定义　38
§3-1-2　集合的表示方法　39
§3-2　集合之间的重要关系　40
§3-2-1　集合之间的重要关系　40
§3-2-2　特殊集合　40
§3-3　集合的运算　41
§3-3-1　集合的基本运算　41
§3-3-2　集合关系的证明方法　42
§3-3-3　笛卡儿积　43
本章总结　43
习题　44
第4章　关系　46
§4-1　关系的概念及表示　46
§4-1-1　关系的概念　46
§4-1-2　关系的表示方法　47
§4-2　关系的性质　48
§4-2-1　自反性与反自反性　48
§4-2-2　对称性与反对称性　49
§4-2-3　传递性　50
§4-3　关系的运算　51
§4-3-1　关系的复合运算　51
§4-3-2　关系的逆运算　54
§4-3-3　关系的闭包运算　55
§4-4　等价关系与划分　56
§4-4-1　等价关系的概念　56
§4-4-2　等价类　57
§4-4-3　划分　58
§4-5　次序关系　58
§4-5-1　偏序关系　59
§4-5-2　其他次序关系　61
本章总结　61
习题　62
第5章　函数　64
§5-1　函数的概念与性质　64
§5-1-1　函数的概念　64
§5-1-2　函数的性质　65
§5-2　函数的运算　66
§5-2-1　函数的复合运算　66
§5-2-2　函数的逆运算　66
§5-3　基数　67
§5-3-1　基数的概念　67
§5-3-2　基数的比较　67
本章总结　69
习题　69
第6章　代数结构　71
§6-1　代数系统的概念　71
§6-2　代数系统的运算及其性质　72
§6-2-1　二元运算的性质　73
§6-2-2　小结　76
§6-3　半群与含幺半群　76
§6-3-1　半群和子半群　76
§6-3-2　含幺半群和子含幺半群　78
§6-4　群与子群　79
§6-4-1　群　80
§6-4-2　子群　82
§6-5　交换群、循环群与置换群　84
§6-5-1　交换群　84
§6-5-2　循环群　85
§6-5-3　置换群　86
§6-6　陪集与拉格朗日定理　88
§6-6-1　陪集　88
§6-6-2　拉格朗日定理　89
§6-6-3　正规子群　90
§6-7　同态与同构　90
§6-7-1　同态　91
§6-7-2　同构　91
§6-7-3　同余关系　94
§6-8　环与域　95
§6-8-1　环　96
§6-8-2　域　97
本章总结　99
习题　100
第7章　格与布尔代数　103
§7-1　格　103
§7-1-1　格的概念　103
§7-1-2　格的性质　105
§7-2　分配格　109
§7-3　有补格　110
§7-4　布尔代数　112
本章总结　114
习题　114
第8章　图论及其应用　117
§8-1　图的基本概念　117
§8-1-1　图　117
§8-1-2　结点的度　119
§8-1-3　图的同构　119
§8-1-4　子图和补图　121
§8-2　图的连通性　122
§8-2-1　路径与回路　122
§8-2-2　连通图　122
§8-3　图的矩阵表示　124
§8-3-1　图的邻接矩阵　124
§8-3-2　图的可达矩阵　126
§8-4　特殊图　128
§8-4-1　欧拉图　128
§8-4-2　哈密顿图　130
§8-4-3　二部图　132
§8-4-4　平面图　134
§8-5　图的应用　136
§8-5-1　图的应用示例　136
§8-5-2　特殊图的应用　138
本章总结　140
习题　140
第9章　树　144
§9-1　无向树　144
§9-1-1　基本概念　144
§9-1-2　*小生成树及其应用　146
§9-2　有向树　148
§9-2-1　基本概念　148
§9-2-2　有序树　149
§9-2-3　m叉树　151
§9-3　二叉树　153
§9-3-1　基本概念　153
§9-3-2　*优树　154
本章总结　156
习题　157
附录　习题参考答案　158
参考文献　192