目　录

第 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　等价　9
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　基本蕴含式　17
1-7　命题逻辑的推理理论　18
1-7-1　论证的有效性　18
1-7-2　有效论证的判断方法　18
1-7-3　自然推理系统　19
1-7-4　自然推理系统中构造有效论证的方法　20
本章总结　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　谓词逻辑的蕴含关系　32
2-5-1　蕴含关系　32
2-5-2　基本蕴含式　33
2-6　谓词逻辑的推理理论　33
本章总结　35
习题　35

第3章　集合　37
3-1　集合的概念与表示　37
3-1-1　集合的定义　37
3-1-2　集合的表示方法　38
3-2　集合之间的关系　39
3-2-1　集合之间的关系　39
3-2-2　特殊集合　39
3-3　集合的运算　40
3-3-1　集合的基本运算　40
3-3-2　集合关系的证明方法　41
3-3-3　笛卡儿积　42
本章总结　42
习题　42

第4章　关系　45
4-1　关系的概念及表示　45
4-1-1　关系的概念　45
4-1-2　关系的表示方法　46
4-2　关系的性质　47
4-2-1　自反性与反自反性　47
4-2-2　对称性与反对称性　48
4-2-3　传递性　49
4-3　关系的运算　50
4-3-1　关系的复合运算　50
4-3-2　关系的逆运算　53
4-3-3　关系的闭包运算　54
4-4　等价关系与划分　55
4-4-1　等价关系的概念　55
4-4-2　等价类　56
4-4-3　划分　57
4-5　次序关系　57
4-5-1　偏序关系　58
4-5-2　其他次序关系　59
本章总结　60
习题　60

第5章　函数　63
5-1　函数的概念与性质　63
5-1-1　函数的概念　63
5-1-2　函数的性质　64
5-2　函数的运算　65
5-2-1　函数的复合运算　65
5-2-2　函数的逆运算　65
5-3　基数　66
5-3-1　基数的概念　66
5-3-2　基数的比较　67
本章总结　68
习题　68

第6章　代数结构　70
6-1　代数系统的概念　70
6-2　代数系统的运算及其性质　71
6-2-1　二元运算的性质　72
6-2-2　小结　75
6-3　半群与含幺半群　75
6-3-1　半群和子半群　76
6-3-2　含幺半群和子含幺半群　77
6-4　群与子群　79
6-4-1　群　79
6-4-2　子群　82
6-5　交换群、循环群与置换群　83
6-5-1　交换群　83
6-5-2　循环群　84
6-5-3　置换群　85
6-6　陪集与拉格朗日定理　86
6-6-1　陪集　86
6-6-2　拉格朗日定理　88
6-7　同态与同构　89
6-7-1　同态　89
6-7-2　同构　90
6-7-3　同余关系　92
6-8　环与域　94
6-8-1　环　94
6-8-2　域　96
本章总结　98
习题　99

第7章　格与布尔代数　102
7-1　格　102
7-1-1　格的概念　102
7-1-2　格的性质　104
7-2　分配格　108
7-3　有补格　109
7-4　布尔代数　111
本章总结　113
习题　113

第8章　图论及其应用　116
8-1　图的基本概念　116
8-1-1　图　116
8-1-2　结点的度　118
8-1-3　图的同构　118
8-1-4　子图和补图　119
8-2　图的连通性　121
8-2-1　路径与回路　121
8-2-2　连通图　121
8-3　图的矩阵表示　123
8-3-1　图的邻接矩阵　123
8-3-2　图的可达矩阵　125
8-4　**短路径与关键路径　127
8-4-1　**短路径　127
8-4-2　评审图与关键路径　128
8-5　树　129
8-5-1　无向树　129
8-5-2　有向树　132
本章总结　136
习题　136

附录　习题答案及提示　139
第 1章　习题参考答案　139
第 2章　习题参考答案　144
第3章　习题参考答案　150
第4章　习题参考答案　153
第5章　习题参考答案　158
第6章　习题参考答案　161
第7章　习题参考答案　164
第8章　习题参考答案　166

参考文献　167