本书以“模型与应用”为核心线索，系统性地阐述离散数学的六大核心模型，包括二值模型、集合模型、关系模型、图模型、树模型及有限状态机模型。每一章节均遵循“理论阐述-习题解析-应用案例”的递进结构，既注重数学概念的严谨性，又强调其在现实场景中的落地价值。通过系统的学习，读者将全面掌握离散数学的重要模型及其在各个领域中的实际应用，奠定坚实的理论基础并提升解决复杂问题的能力。
本书的突出特色在于鲜明的实践与应用导向。每一理论章节后均设有“数学建模与应用”专题，通过48个真实案例，生动展现了离散数学破解实际应用难题的过程。这些案例不仅可加深读者对理论知识的理解，还能启发他们将数学工具应用于实际工程问题。
本书适合作为普通高等院校计算机科学、软件工程、人工智能等相关专业的本科生教材，也可供工程师与研究人员参考。

黄翰　博士，中山大学软件工程学院教授、博士生导师，国家级青年人才项目入选者。兼任国际学术期刊IEEE TEVC、IEEE TETCI与Complex & Intelligent Systems副编，广东省本科高校软件工程专业指导委员会主任（2021-2025），广东省计算机学会软件工程专业委员会主任，CCF杰出会员。获得国家示范性软件学院成立20周年全国优秀教师表彰称号。出版中文著作3部、教材2部，英文著作2部。以第一作者或通讯作者身份在IEEE TPARMI、IEEE TCYB、IEEE TSE、IEEE TEVC、IEEE TIP、IEEE TFS和《中国科学》等专业学术期刊发表论文80多篇。以第一发明人授权国家发明专利60项以及美国发明专利8项。以第一完成人获中国专利优秀奖、广东省科技进步二等奖，以主要完成人获广东省科技进步一等奖（第2）、广东省自然科学二等奖（第3）等。长期致力于智能算法理论、应用与产业生态的研究，发布6项公开使用的软件系统，完成算法落地应用案例近百项；设计并部署智能体+私域大模型近20项；实施的AI赋能千行百业计划已有300多例，受众覆盖600多家单位与20多万个人用户。
杨晓伟　博士，华南理工大学软件学院教授，博士生导师，广东省软件工程专委会副主任。分别于1991年、1996年和2000年在吉林大学数学系、数学所和工程力学系获得理论与应用力学专业学士、计算力学专业硕士和固体力学专业博士学位。研究领域为机器学习、模式识别和软件工程。承担新一代人工智能科技部重大项目和广东省科技厅重大项目，相关成果主要发表在TIP、TKDE、TNNLS、TEVC、TCYB、TFS、TGRS、TMI、TSE、TOSEM、PR、《计算机学报》《软件学报》等国内外人工智能、模式识别和软件工程主流期刊和国际学术会议上。基于在支持向量机和张量学习方面的多年研究基础，出版学术专著《支持向量机的算法设计与分析》和《张量学习理论及其应用》。
郝志峰 汕头大学校长、教授、博士生导师。2018-2022教育部大学数学教学指导委员会副主任委员，中国工业与应用数学学会大数据与人工智能专委会副主任，全国高校人工智能与大数据创新联盟常务副理事长，教育部智能制造技术重点实验室主任，中国发明协会会士。
长期关注数学建模与应用、数据科学、智慧城市等方面的研究。主持科技部重点研发计划、国家“新世纪人才支持计划”、国家自然科学基金、教育部霍英东基金等省部级以上项目30 余项；在TPAMI、TKDE、PR、BIOINFORMATICS、《中国科学》等国内外重要期刊上发表高质量论文逾200篇；获第十届国际发明展览会金奖、第二十一届中国专利奖优秀奖；以及中国产学研合作创新成果奖一等奖、广东省科学技术奖一等奖、二等奖、教育部自然科学奖二等奖各1次，第十届广东青年五四奖章、第九届广东省丁颖科技奖等奖项。2020年获“智慧城市先锋榜领军人物”荣誉称号，2021年获“当代发明家”称号。

目 录

前言

第 1 章 二值模型　　　　1
1.1 命题逻辑　　　　 1
1.1.1 命题　　　　　2
1.1.2 逻辑运算符的优先级　　 7
1.1.3 逻辑运算与位运算　　　9
1.1.4 习题　　　　　9
1.2 命题等价式　　　　13
1.2.1 永真式与矛盾式　　　13
1.2.2 逻辑等价证明　　　 14
1.2.3 命题可满足性建模与求解　 20
1.2.4 习题　　　　 20
1.3 谓词与量词　　　　21
1.3.1 谓词　　　　 22
1.3.2 量词　　　　 23
1.3.3 约束论域的量词　　　24
1.3.4 语句到逻辑表达式的翻译　 27
1.3.5 逻辑程序设计　　　 29
1.3.6 霍尔逻辑　　　　29
1.3.7 习题　　　　 31
1.4 嵌套量词　　　　33
1.4.1 嵌套量词到自然语言的翻译　33
1.4.2 涉及嵌套量词的语句到逻辑表达式的翻译　　　　 34
1.4.3 嵌套量词逻辑表达式的否定　35
1.4.4 量词的顺序　　　 36
1.4.5 习题　　　　 36
1.5 推理规则　　　　38
1.5.1 命题逻辑的推理规则　 38
1.5.2 使用推理规则建立有效论证　39
1.5.3 量词陈述的推理规则　 43
1.5.4 定理的证明方法　　　44
1.5.5 习题　　　　 44
1.6 布尔代数　　　　45
1.6.1 布尔函数　　　　45
1.6.2 对偶性　　　　 46
1.6.3 布尔代数的抽象定义　 46
1.6.4 布尔函数的表示　　　47
1.6.5 函数完备性、可逆布尔函数和量子逻辑　　　　 47
1.6.6 习题　　　　 47
1.7 本章应用题　　　　48
1.8 数学建模与应用　　　52
1.8.1 软件产品线配置　　　52
1.8.2 软件测试　　　　54
1.8.3 视频烟雾检测　　　 56
1.8.4 视频人物蒙面检测　　59
1.8.5 视频监控的安全带检测　　61
1.8.6 逻辑门电路设计　　　63#12;1.8.7 知识推理　　　　65
1.8.8 自动定理证明　　　 66
1.8.9 智能合约　　　　67
1.8.10 传染病防控　　　 68

第 2 章 集合模型　　　　70
2.1 集合与集合运算　　　70
2.1.1 集合简介　　　　70
2.1.2 幂集合　　　　 73
2.1.3 基本集合运算　　　 73
2.1.4 习题　　　　 76
2.2 函数的集合表示及其性质　 78
2.2.1 函数简介　　　　78
2.2.2 函数类型与运算　　　80
2.2.3 取整函数　　　　82
2.2.4 函数的阶　　　　83
2.2.5 时间复杂度　　　 86
2.2.6 算法时间复杂度　　　89
2.2.7 习题　　　　 89
2.3 本章应用题　　　　91
2.4 数学建模与应用　　　93
2.4.1 数字图像的生成与表示　　93
2.4.2 点云的表示与配准　　95
2.4.3 哈希表　　　　 97
2.4.4 有限状态机　　　 98
2.4.5 公钥加密系统　　100
2.4.6 病毒检测的真阳性率　　101

第 3 章 关系模型　　　 103
3.1 关系及其性质　　　 103
3.1.1 集合上的函数与关系　　104
3.1.2 关系的性质　　　 105
3.1.3 关系的复合　　　 108
3.1.4 习题　　　　 110
3.2 n 元关系及其应用　　 112
3.2.1 n 元关系与数据库　　 112
3.2.2 n 元关系的运算　　　112
3.2.3 SQL　　　　 113
3.2.4 习题　　　　 114
3.3 关系的表示　　　 114
3.3.1 用矩阵表示关系　　114
3.3.2 用有向图表示关系　　 116
3.3.3 关系的布尔运算　　118
3.3.4 习题　　　　 120
3.4 关系的闭包　　　 125
3.4.1 闭包　　　　 125
3.4.2 传递闭包的计算　　126
3.4.3 Warshall 算法　　128
3.4.4 习题　　　　 132
3.5 等价关系　　　134
3.5.1 等价关系的定义　　134
3.5.2 等价类　　　　136
3.5.3 等价关系与划分　　136
3.5.4 习题　　　　 138
3.6 偏序关系　　　139
3.6.1 偏序关系介绍　　139
3.6.2 词典序和哈塞图　　140
3.6.3 极大元与极小元　　142
3.6.4 格与拓扑排序　　143
3.6.5 习题　　　　 145
3.7 本章应用题　　　 148#12;3.8 数学建模与应用　　　149
3.8.1 关系在数据库中的应用——关系数据库　　 149
3.8.2 关系在疫情防控中的应用——隔离管控　　　150
3.8.3 关系在销售推荐中的应用——推荐系统　　　152
3.8.4 关系在软件测试中的应用——等价类划分　　 153
3.8.5 关系在优化问题中的应用——调度问题　　　154
3.8.6 关系在静态分析中的应用——数据流分析理论　　 156

第 4 章 图模型　　　158
4.1 图模型的介绍　　　 158
4.1.1 关于图模型　　　 158
4.1.2 图模型的定义　　159
4.1.3 图模型的案例　　162
4.1.4 习题　　　　 165
4.2 图的术语　　　166
4.2.1 基本术语　　　　166
4.2.2 特殊的简单图　　168
4.2.3 二部图　　　　170
4.2.4 二部图及其匹配　　170
4.2.5 特殊类型图的应用　　 172
4.2.6 习题　　　　 173
4.3 图的表示及图的同构　176
4.3.1 图的表示　　　　176
4.3.2 邻接矩阵　　　　177
4.3.3 关联矩阵　　　　180
4.3.4 图的同构　　　　181
4.3.5 简单图同构的判断　　 182
4.3.6 习题　　　　 184
4.4 图的连通性　　　 187
4.4.1 通路　　　　 188
4.4.2 无向图的连通性　　188
4.4.3 图是如何连通的　　190
4.4.4 有向图的连通性　　190
4.4.5 通路与同构　　　 191
4.4.6 图顶点之间通路数的计算问题　192
4.4.7 习题　　　　 193
4.5 欧拉路与哈密顿路　　 195
4.5.1 欧拉通路与欧拉回路　　195
4.5.2 哈密顿通路与哈密顿回路　 198
4.5.3 习题　　　　 201
4.6 最短通路　　　205
4.6.1 最短通路算法　　206
4.6.2 最小哈密顿回路问题　　208
4.6.3 习题　　　　 209
4.7 平面图　　　　 209
4.7.1 欧拉公式　　　　211
4.7.2 库拉图斯基定理　　214
4.7.3 习题　　　　 216
4.8 图着色　　　　 219
4.8.1 图着色问题的介绍　　 219
4.8.2 简单图着色　　　 220
4.8.3 图着色的应用　　223
4.8.4 习题　　　　 224
4.9 本章应用题　　　 225#12;4.10 数学建模与应用　　 232
4.10.1 CPU 多核连接拓扑　 232
4.10.2 计算机网络路由算法　　235
4.10.3 物流运输——双层次车辆路径问题　　　　 238
4.10.4 电路板布线问题　 240
4.10.5 期末考试安排　　243
4.10.6 频率分配　　　 245
4.10.7 变址寄存器　　　 246
4.10.8 高效并行计算任务分配　 248

第 5 章 树模型　　　250
5.1 关于树模型　　　 250
5.1.1 树的定义　　　　251
5.1.2 树模型的应用举例　　 255
5.1.3 树的性质　　　　257
5.1.4 习题　　　　 259
5.2 树的应用　　　262
5.2.1 二分搜索树　　　 262
5.2.2 决策树　　　　262
5.2.3 博弈树　　　　264
5.2.4 习题　　　　 266
5.3 树的遍历　　　267
5.3.1 有序有根树　　　 267
5.3.2 树的遍历算法　　268
5.3.3 树的中缀、前缀和后缀表示法　　　 270
5.3.4 孩子兄弟法　　　 273
5.3.5 习题　　　　 274
5.4 生成树　　　　 275
5.4.1 生成树的定义　　275
5.4.2 构建生成树的深度优先搜索方法　　　　 277
5.4.3 构建生成树的广度优先搜索方法　　　　 279
5.4.4 生成树中回溯法的应用　 280
5.4.5 习题　　　　 283
5.5 最小生成树　　　 284
5.5.1 最小生成树的定义　　 284
5.5.2 Prim 算法　　　 284
5.5.3 Kruskal 算法　　　285
5.5.4 最小生成树的应用　　 286
5.5.5 习题　　　　 288
5.6 本章应用题　　　 290
5.7 数学建模与应用　　　296
5.7.1 树在疫情防控中的作用——病毒变异演化树　　 296
5.7.2 树在机器学习中的应用——决策树　　　　　298
5.7.3 树的遍历与编码应用——区块链智能合约脚本　　　300
5.7.4 树在数据库索引中的应用——使用 B+树实现高效搜索　 301
5.7.5 树在动作游戏 AI 中的应用——行为树　　　　 303
5.7.6 树在编译器中的应用——语法分析树　　　　 304
5.7.7 最小生成树在计算机网络中的应用——路由选择　　306
5.7.8 博弈树在围棋 AI 中的应用——蒙特卡罗树　　 308
5.7.9 树在数据压缩中的应用——哈夫曼树　　　　 309
5.7.10 树在网页设计中的应用——HTML网页的 DOM 树　　 311

第 6 章 有限状态机模型　　 314
6.1 关于有限状态机模型　314
6.1.1 有限状态机的组成　　 315
6.1.2 有限状态机的定义　　 315
6.1.3 有限状态机的案例　　 316
6.1.4 习题　　　　 318
6.2 图灵机　　　　 318
6.2.1 图灵机的原理　　319
6.2.2 图灵机的组成　　319
6.2.3 图灵机的抽象模型　　 321
6.2.4 图灵机的问题举例　　 322
6.2.5 习题　　　　 327
6.3 图灵命题　　　328
6.3.1 图灵命题及其意义　　 328
6.3.2 不可解问题　　　 329
6.3.3 图灵命题的影响　　330
6.3.4 习题　　　　 331
6.4 NP、NPC 与 NP-hard　　332
6.4.1 归约与问题求解难度　　332
6.4.2 NP 问题　　　　332
6.4.3 NPC 与 NP-hard 问题　　332
6.4.4 P 与 NP 问题的未解之谜　 334
6.4.5 习题　　　　 334
6.5 本章应用题　　　 335
6.6 数学建模与应用　　　341
6.6.1 有限状态机在自动售货机中的应用　　　　 341
6.6.2 有限状态机在文本处理中的应用　342
6.6.3 图灵机在算法分析中的应用　344
6.6.4 图灵机在不可解问题中的应用　346
6.6.5 图灵命题在停机问题中的应用　348
6.6.6 NP 问题的数学建模与应用——最大流问题　　 350
6.6.7 NP 完全问题的数学建模与应用——最大团问题　　351
6.6.8 NP-hard 问题的数学建模与应用——旅行商问题　　353

参考文献　　　　　 355