目录


第1章基础知识/1
1.1集合与序列2
1.1.1内容提要2
1.1.2主教材习题参考解答4
1.2数论基础10
1.2.1内容提要10
1.2.2主教材习题参考解答12
1.3计数基础16
1.3.1内容提要16
1.3.2主教材习题参考解答19
1.4布尔矩阵及其运算28
1.4.1内容提要28
1.4.2主教材习题参考解答29
1.5补充习题及参考解答30
第2章命题逻辑/55
2.1命题逻辑的基本概念56
2.1.1内容提要56
2.1.2主教材习题参考解答56
2.2命题公式及其分类58
2.2.1内容提要58
2.2.2主教材习题参考解答59
2.3命题逻辑的等值演算61
2.3.1内容提要61
2.3.2主教材习题参考解答62
2.4对偶与范式62
2.4.1内容提要62
2.4.2主教材习题参考解答65
2.5命题联结词的完备集67
2.5.1内容提要67
2.5.2主教材习题参考解答68
2.6命题逻辑的推理69
2.6.1内容提要69
2.6.2主教材习题参考解答70
2.7补充习题及参考解答75
〖1〗离散数学及应用学习指导与习题解析目录〖3〗〖3〗第3章谓词逻辑/91
3.1谓词与量词92
3.1.1内容提要92
3.1.2主教材习题参考解答93
3.2谓词公式及分类94
3.2.1内容提要94
3.2.2主教材习题参考解答95
3.3自然语言形式化96
3.3.1内容提要96
3.3.2主教材习题参考解答96
3.4谓词逻辑的等值演算98
3.4.1内容提要98
3.4.2主教材习题参考解答99
3.5前束范式101
3.5.1内容提要101
3.5.2主教材习题参考解答101
3.6谓词逻辑的推理102
3.6.1内容提要102
3.6.2主教材习题参考解答103
3.7补充习题及参考解答107
第4章二元关系/115
4.1关系及其表示116
4.1.1内容提要116
4.1.2主教材习题参考解答117
4.2关系的运算120
4.2.1内容提要120
4.2.2主教材习题参考解答122
4.3关系的性质124
4.3.1内容提要124
4.3.2主教材习题参考解答125
4.4关系的闭包128
4.4.1内容提要128
4.4.2主教材习题参考解答130
4.5等价关系和集合的划分131
4.5.1内容提要131
4.5.2主教材习题参考解答132
4.6相容关系与集合的覆盖135
4.6.1内容提要135
4.6.2主教材习题参考解答135
4.7补充习题及参考解答136
第5章函数/151
5.1函数的定义151
5.1.1内容提要151
5.1.2主教材习题参考解答152
5.2函数的性质153
5.2.1内容提要153
5.2.2主教材习题参考解答153
5.3函数的复合156
5.3.1内容提要156
5.3.2主教材习题参考解答156
5.4逆函数157
5.4.1内容提要157
5.4.2主教材习题参考解答157
5.5计算机科学中的常用函数158
5.5.1内容提要158
5.5.2主教材习题参考解答160
5.6双射函数及集合的势163
5.6.1内容提要163
5.6.2主教材习题参考解答164
5.7补充习题及参考解答165
第6章偏序关系、偏序集与格/178
6.1偏序关系和偏序集179
6.1.1内容提要179
6.1.2主教材习题参考解答181
6.2偏序集中的特殊元素183
6.2.1内容提要183
6.2.2主教材习题参考解答185
6.3格与布尔代数187
6.3.1内容提要187
6.3.2主教材习题参考解答189
6.4补充习题及参考解答194
第7章代数结构/204
7.1运算与代数结构205
7.1.1内容提要205
7.1.2主教材习题参考解答206
7.2群209
7.2.1内容提要209
7.2.2主教材习题参考解答213
7.3环与域224
7.3.1内容提要224
7.3.2主教材习题参考解答225
7.4作为代数结构的格与布尔代数228
7.4.1内容提要228
7.4.2主教材习题参考解答229
7.5补充习题及参考解答231
第8章图论/258
8.1基本概念259
8.1.1内容提要259
8.1.2主教材习题参考解答262
8.2欧拉图272
8.2.1内容提要272
8.2.2主教材习题参考解答273
8.3哈密顿图275
8.3.1内容提要275
8.3.2主教材习题参考解答276
8.4平面图278
8.4.1内容提要278
8.4.2主教材习题参考解答279
8.5顶点支配、独立与覆盖284
8.5.1内容提要284
8.5.2主教材习题参考解答284
8.6匹配286
8.6.1内容提要286
8.6.2主教材习题参考解答289
8.7图的着色298
8.7.1内容提要298
8.7.2主教材习题参考解答299
8.8网络与流307
8.8.1内容提要307
8.8.2主教材习题参考解答310
8.9图的连通度315
8.9.1内容提要315
8.9.2主教材习题参考解答315
8.10补充习题及参考解答316
第9章树及其应用/392
9.1无向树393
9.1.1内容提要393
9.1.2主教材习题参考解答393
9.2支撑树及其应用396
9.2.1内容提要396
9.2.2主教材习题参考解答397
9.3最短道路树404
9.3.1内容提要404
9.3.2主教材习题参考解答405
9.4根树及其应用408
9.4.1内容提要408
9.4.2主教材习题参考解答410
9.5补充习题及参考解答418
第10章形式语言、自动机与正则表达式/439
10.1语言439
10.1.1内容提要439
10.1.2主教材习题参考解答441
10.2文法442
10.2.1内容提要442
10.2.2主教材习题参考解答444
10.3巴科斯诺尔范式和语法图447
10.3.1内容提要447
10.3.2主教材习题参考解答447
10.4有限状态自动机449
10.4.1内容提要449
10.4.2主教材习题参考解答450
10.5语言与自动机的关系456
10.5.1内容提要456
10.5.2主教材习题参考解答457
10.6正则表达式459
10.6.1内容提要459
10.6.2主教材习题参考解答459
10.7图灵机461
10.7.1内容提要461
10.7.2主教材习题参考解答462
10.8补充习题及参考解答463
附录A参考教学内容与课时安排/476
A.164课时的参考教学内容与课时安排476
A.2128课时的参考教学内容与课时安排478
附录B课程综合实验/481
B.1实验一: 汉诺塔问题的变体481
B.1.1实验内容481
B.1.2实验要求482
B.1.3扩展阅读483
B.2实验二: 命题演算的计算机实现483
B.3实验三: 二元关系及其应用484
B.3.1准备工作484
B.3.2等价关系及其应用484
B.3.3偏序关系及其应用485
B.3.4连通性和欧拉道路/回路487
B.4实验四: 村庄引水问题488
B.4.1实验内容一488
B.4.2实验内容二490
B.4.3讨论与思考491
B.5实验五: 考场安排问题492
B.5.1实验内容492
B.5.2实验要求493
B.6实验六: 交通灯相位设计493
B.7实验七: 展览馆的参观与维护线路494
B.8实验八: 研究生的自动分配495
B.9实验九: 绿色健康城市规划496
B.10实验十: 羽毛球友谊邀请赛496
B.11实验十一: 最优数据存储方案497
B.12实验十二: 字符串匹配的自动机算法498
B.12.1实验内容及要求498
B.12.2讨论与思考498
B.13实验十三: 过河问题499
B.13.1渡河问题499
B.13.2过桥问题500
参考文献/501