离散数学（第2版）

本书经过两年的使用,又根据广大读者的意见,做了本次改版,将上一版中比较难以理解的知识点加以备注,如逻辑连接词蕴涵号、主析取范式、主合取范式、等价关系、偏序关系、图论部分概念等,同时对学生容易混淆的知识点进行了详细讲解。

在第2章、第3章、第5章中增加了导论,引出本章需要解决的问题,在本书出现的一些核心知识点和人名,添加了一些注释,增加数学文化的介绍,希望给读者带来正能量,积极探索科学知识,加强课程思政建设。另外,每章后面的习题增加了一些应用题,顺其自然将线性代数和数学建模融入离散数学中,目的是在实践中理解和掌握知识。为了让更多读者自学使用,本次改版特意在书后附加习题详细解答,方便自学。

同时本书是产学合作协同育人项目2020 年度第二批立项项目———中医药院校数学建模创新人才培养模式的构建与实践的研究成果;本书还得到了国家自然科学基金青年项目的资助。

后,本次改版得到了学校和学院领导的大力支持,本教研室同仁鼎力相助,感谢许可、张帅、高晓苑、仇静静、吴日新、王皓阳等同学协助输入修改。

其中,第1、2章由杨文国、石莹修订,第3、4章由沈晓婧、吕佳萍修订,第5章由黄鑫海、袁建军修订,课后习题及附录部分由蔡云、张倩、石仁祥、胡婷婷、张寒苏修订。

杨文国

2021 年6月

离散数学是数学中一门有着实际应用的理论应用数学,正是由于它的发展才推动了数字计算机和图论的发展。现实生活中电子电路的设计、列车线路的调度、城市结点间的主干路径的设计、地图着色等问题都是离散数学着力解决的内容。

为了适应高校教学的不断改革,强化应用,体现特色,我们结合中医药大学专业特点编写了本书,力图让学生看懂、学明白,抛开了大量专业的晦涩难懂的描述,结合实际应用和教学实践,用通俗化的语言进行描述。我们对本书的章节进行了精心安排,理论结合实际应用,将全书分为5章:命题逻辑、谓词逻辑、集合论、二元关系和图论,删除了晦涩难懂的数论部分。每章后配有大量习题。

本书第1、5章由高华编写,第2~4章由杨文国编写,书后习题由石莹、吕佳萍、沈晓婧编写,全书由蔡云、张倩、胡婷婷校对,由黄鑫海、袁建军、石仁祥完成统稿。

本书适合3学分的离散数学教学计划使用,也可供有兴趣的科技工作者自学或参考。

全书图形由Insap公式由LTX编写,1标准,aekce作图, ae图形执行SVG1.LTX执行v3.0标准。

本书是江苏省教育科学“十三五”规划2018 年度课题:基于任务驱动下分块化的大学数学教学改革,项目编号为D/2018/01/76 。本书也是全国高等院校计算机基础教育研究会计算机基础教育教学研究项目,项目编号为2019-AFCEC-221 。同时,本书还是产学合作协同育人项目,项目编号为201802271035。

后感谢南京中医药大学信息技术学院领导和数学教研室同仁的大力支持。感谢南京林业大学高华博士的技术支持。

限于作者水平,书中难免有错误,希望读者不吝赐教。

杨文国高华

2019 年7月

本书主要介绍了离散数学的基本内容和一些简单应用。全书共分5章,分别介绍命题逻辑、谓词逻 辑、集合论、二元关系和图论。本书整体结构清晰,概念清楚,重点突出。为了方便学生理解、掌握所学 知识,本书配有大量习题,分别以判断题、单项选择题、不定项选择题、解答题等形式呈现,题目通俗易 懂,做题灵活,方便学生随堂测试。本书是江苏省教育科学“十三五”规划研究课题的专项成果。 本书可作为本科院校计算机科学与技术、软件工程、医学信息学以及其他理工科专业的教材,也可 供喜爱离散数学的有关人员阅读。

杨文国，副教授，南京中医药大学数学教研室主任，主持省部级课题2项，校级课题3项，行业协会课题2项，以作者或通讯作者共发表了论文29篇，SCI论文3篇，中文核心10篇。主编教材1部，副主编规划教材3部，参编规划教材2部。

第1章命题逻辑1
1.1命题与表示1
1.2联结词3
1.3命题公式与真值表示6
1.4对偶与范式10
1.5推理15
1.6联结词功能集19
1.7习题21

第2章谓词逻辑25
2.1谓词与命题函数25
2.2谓词公式与翻译27
2.3前束范式31
2.4谓词推理33
2.5习题34

第3章集合论37
3.1集合与表示37
3.2集合运算39
3.3集合的计数与划分44
3.4集合的基数47
3.5习题49

第4章二元关系53
4.1关系及其表示53
4.2关系的性质57
4.3关系的等价63
4.4序关系65
4.5函数67
4.6习题71

第5章图论75
5.1图的概念75
5.2路与回路80
5.3图的矩阵形式83
5.4欧拉图与哈密顿图87
5.5平面图与着色89
5.6无向树与生成树93
5.7有向树与应用95
5.8习题100

附录习题解答105
第1章命题逻辑105
第2章谓词逻辑110
第3章集合论112
第4章二元关系115
第5章图论118