数理逻辑与图论

课程简介

 

本课程主要为对数学和计算机科学/工程有兴趣的学生介绍数学逻辑与图论的原理。主要内容分为两部分：数理逻辑和图论。第一部分主要介绍数学语言的定义（命题和谓词逻辑）、递归概念和关系理论。第二部分讨论图论的主要结论并介绍本课程所涉及的方法和术语。图的数学理论是重点。涉及的主题有：顶点、边、度、平面图、有向图、偶图、连通性、路径、欧拉回路、哈密顿回路、树、独立集、平面化和着色等。着重强调了现代数理逻辑与图论中已经被证明是非常有成效的各种方法。

 

This course is an introduction to the theory of mathematical logic and graphs intended for students interested in mathematics and computer science/engineering theory. The content of this course is divided into two parts: mathematical logic and graph theory. The first part gives will meet precise definitions of the language of mathematics (propositional and predicate logic), and basic notions of recursion and relation theory. The second part discusses some of the major results of graph theory, and provides an introduction to the methods and terminology of the subject. Emphasis will be given to mathematical theory of graphs. The topics include: vertex, edge, degrees, planar graphs, directed graphs, bipartite graphs, connectivity, paths, Eulerian tours, Hamiltonian cycles, trees, independent sets, planarity, and colorings, etc. Special emphasis is on various approaches that has proved fruitful in modern mathematical logic and graph theory.

 

 

课本

 

《离散数学及其应用（原书第8版）本科教学版》（美）Kenneth H. Rosen 著，徐六通 杨娟 吴斌 译，机械工业出版社

《离散数学及其应用》（原书第8版）（美）Kenneth H. Rosen 著，徐六通 杨娟 吴斌 译，机械工业出版社（pdf版本下载）

参考书

 

《Discrete Mathematics and its Application (Eighth Edition)》 Kenneth H. Rosen 著，机械工业出版社

原版教材主页

《离散数学教程》耿素云　屈婉玲　王焊贫 　著，北京大学出版社

 

 

课程安排

 

学时：40学时（1-10周），32学时上课，6学时习题课、复习和答疑，2学时考试

课后作业：每周二放至教室最后一排，等助教来收取，下周二前发回

评分标准：

期末考试：60分

课后作业：32分，共8次(或更多)作业，每次满分4分

平时表现：8分

备注：抄作业，该次作业按0分计；迟交作业，该次作业满分2分

重要通知比如考试和习题课安排会及时放在主页上，请同学们多多关注！

 

 

作业布置

 

第一周第一次作业：1.1节（13，19，35，43）

第一周第二次作业：1.2节（11，29，39）；1.3节（19，29，33，45，55）

第二周第一次作业：1.4节（7，27，63）；1.5节（7，11，21，35）

第二周第二次作业：1.6节（11，23，29，35）；1.7节（15，19，41）

注意：1.6.23题论证第一行的析取应为合取；1.6.35题倒数第二句应为“如果超人存在，则他既不是无能的也不是恶意的。”

第三周第一次作业：1.8节（5，13，27，51）；2.1节（11，27，41，43，49）；2.2节（19，35，47）

第三周第二次作业：2.3节（3，21，37）；2.4节（27）；2.5节（11，17，31）

第四周第一次作业：3.1节（41，53，77）；3.2节（13，15，25，49）

第五周第一次作业：3.3节（23，31）；4.1节（17，27，29，35）；4.5节（17）；4.6节（15，17）

注意：4.1.35题，J(n)是指最后生存者的编号；4.5.17题，题目应为“有多少个以3个数字987开始，或者在第5和第6位包含数字45，或者最后3位是123？”；4.6.15题，100封信应对应100个不同的信袋；

第五周第二次作业：5.1节（5，9，49，57）；5.2节（23）

第七周第一次作业：5.3节（15，31）

第七周第二次作业：5.4节（13，23，29）；5.5节（7，21，47，59，63）

第八周第一次作业：5.6节（3，33，43，49，67）；6.1节（11，13，29）

第八周第二次作业：6.2节（5，27，33，47，51，63）；6.3节（21，33，47，49，59）

第九周第一次作业：6.4节（15，23，37，45，47，53）

第十周第一次作业：6.5节（9，23，45，47，67）

第十周第二次作业：6.6节（3，27，31）

第十一周第一次作业：6.7节（9，17，19，25，29）；6.8节（15，19，25，35，37）

第十一周第二次作业：7.1节（13，25，31，43）；7.2节（13，35）

 

 

作业缺交名单

 

 

 

重要通知

 

通知：2022年9月22日（星期四）停课一次，课程往后顺延。

通知：2022年10月1日-2022年10月7日放假，10月8日上周一的课，10月9日上周五的课。本课程国庆后的课程10月11日（星期二）开始。

通知：2022年10月27日（星期四）上习题课，线下上课，请各位同学按时到教室。