离散数学简介

1、南京大学信息管理学院杨建林l什么叫离散数学？什么叫离散数学？离散：分离，分散（空间）；与连续相对离散：分离，分散（空间）；与连续相对离散对象（量）：不连续的，可分离的，如自然数。不同于离散对象（量）：不连续的，可分离的，如自然数。不同于实数对象的集合，有限或可数实数对象的集合，有限或可数离散数学是以离散离散数学是以离散( (即即非连续非连续) )对象的对象的数量和空间关系数量和空间关系为研究为研究内容的若干个数学分支的总称。内容的若干个数学分支的总称。包括包括数理逻辑数理逻辑、近世代数、古典概率、近世代数、古典概率、组合学组合学、图论、集合图论、集合论论、数论、自动机和形式语言、数论、自动机和

2、形式语言、可计算性和可判定性可计算性和可判定性、离散、离散几何、代数结构等。几何、代数结构等。l “离散离散”和和“连续连续”之间的对立与统一是数学发展的之间的对立与统一是数学发展的重要动力之一重要动力之一.l古代数学主要讨论整数等离散与离散化了的数量关系，古代数学主要讨论整数等离散与离散化了的数量关系，因而，那时数学被看成是研究上述数量关系的科学因而，那时数学被看成是研究上述数量关系的科学.l但随着数学理论的发展，处理离散数量关系的数学工但随着数学理论的发展，处理离散数量关系的数学工具在刻画和处理某类事务方面显得无能为力，因此出具在刻画和处理某类事务方面显得无能为力，因此出现了处理连续数量关

3、系的数学工具：微积分现了处理连续数量关系的数学工具：微积分.4l离散数学是随着计算机科学与技术的产生发展和应用领域的不断发展而逐步形成和发展起来的一门新兴学科，作为一门课程开设于上世纪70年代初。l数论举例：费马大定理数论举例：费马大定理l勾股定理：特例勾股定理：特例3 32 2+4+42 2=5=52 2)3(nzyxnnnl图论举例：图论举例：l欧拉的七桥问题欧拉的七桥问题18世纪著名古典数学问题之一世纪著名古典数学问题之一东普鲁士的哥尼斯堡城，东普鲁士的哥尼斯堡城，普雷格尔河流经此镇，奈发夫岛位普雷格尔河流经此镇，奈发夫岛位于河中，共有于河中，共有7座桥横跨河上，把全镇连接起来座桥横跨河

4、上，把全镇连接起来 战争期间，破坏这七座桥。设想用一辆装载炸药的车，每过战争期间，破坏这七座桥。设想用一辆装载炸药的车，每过一桥便炸毁该桥，车无法从原桥驶回一桥便炸毁该桥，车无法从原桥驶回设计一种行驶路线的方案，要将七座桥都这样炸毁，不许遗设计一种行驶路线的方案，要将七座桥都这样炸毁，不许遗漏一座桥漏一座桥l把这个问题转化为数学问题：把东、南、北及岛四区看成四个点，连接它们的七把这个问题转化为数学问题：把东、南、北及岛四区看成四个点，连接它们的七座桥看成七条通路，如东区与北区由桥座桥看成七条通路，如东区与北区由桥3 3相连，则它们之间有一条通路，南区与相连，则它们之间有一条通路，南区与北区没有

5、桥直接相连，则它们之间就没有直接的通路。北区没有桥直接相连，则它们之间就没有直接的通路。l以以A A代表岛区，代表岛区，B B，C C，D D分别代表北、东、南三区，把这四个点和连接它们的代表分别代表北、东、南三区，把这四个点和连接它们的代表七座桥的通路在图上画出来，就得到图七座桥的通路在图上画出来，就得到图(2)(2)l问题可以叙述为：以问题可以叙述为：以A A，B B，C C，D D这四点中的任一点为起点，能否不重复地用一笔这四点中的任一点为起点，能否不重复地用一笔便将上面的图形画出来便将上面的图形画出来l一个图形要能一笔画完成必须符合两个条件，即图形是封闭联通的和图形中的奇一个图形要能一

6、笔画完成必须符合两个条件，即图形是封闭联通的和图形中的奇点（与奇数条边相连的点）个数为点（与奇数条边相连的点）个数为0或或2。l离散数学是计算机科学的理论基础离散数学是计算机科学的理论基础l计算机的理论模型是离散的图灵机计算机的理论模型是离散的图灵机l本质上计算机只处理离散对象，但可通过近似和模拟本质上计算机只处理离散对象，但可通过近似和模拟等手段处理连续对象（如求极值问题）等手段处理连续对象（如求极值问题）l现代计算机越来越多地用于处理离散对象现代计算机越来越多地用于处理离散对象l离散数学在计算机科学中直接有用，是计算机科学的离散数学在计算机科学中直接有用，是计算机科学的工具工具l离散数学是

7、后继课程的基础离散数学是后继课程的基础l离散数学是实际应用的基础工具离散数学是实际应用的基础工具l计算机科学和离散数学处理问题的方法、思维计算机科学和离散数学处理问题的方法、思维方式有相似之处方式有相似之处l离散数学可提供所需的思维训练，培养所需的离散数学可提供所需的思维训练，培养所需的分析问题和解决问题的能力分析问题和解决问题的能力l离散数学是学习数据结构与算法、离散数学是学习数据结构与算法、数据库数据库、编编译原理译原理、算法设计与分析、算法设计与分析、计算机网络计算机网络等课程等课程的主要基础，对的主要基础，对开发大型软件开发大型软件、研究信息安全研究信息安全和密码学和密码学、开展计算机

8、理论研究以及开发新型、开展计算机理论研究以及开发新型计算机都提供了不可缺少的基础知识计算机都提供了不可缺少的基础知识l一一 命题逻辑命题逻辑l二二 谓词逻辑谓词逻辑l三三 集合论集合论l四四 图论图论l教材：耿素云，屈婉玲，离散数学，高教出版社，教材：耿素云，屈婉玲，离散数学，高教出版社，2004 l逻辑一词源于希腊文，意思指：词、思想、理逻辑一词源于希腊文，意思指：词、思想、理性、规律等。性、规律等。l逻辑学研究的是：判别一个推理过程是否正确逻辑学研究的是：判别一个推理过程是否正确的标准。的标准。l数理逻辑也叫符号逻辑，即用人工符号来书写数理逻辑也叫符号逻辑，即用人工符号来书写逻辑法则，它是

9、一门涉及数学、逻辑学、逻辑法则，它是一门涉及数学、逻辑学、哲学哲学等学科的横向交叉学科。等学科的横向交叉学科。l现代数理逻辑可分为现代数理逻辑可分为命题逻辑演算命题逻辑演算谓词逻辑演算谓词逻辑演算证明论证明论模型论模型论递归函数论递归函数论公理化集合论等公理化集合论等l命题逻辑和一阶谓词逻辑是数理逻辑中命题逻辑和一阶谓词逻辑是数理逻辑中最成熟的部分，在计算机科学中应用最最成熟的部分，在计算机科学中应用最为广泛为广泛命题逻辑是数理逻辑的最基础部分命题逻辑是数理逻辑的最基础部分谓词逻辑在命题逻辑的基础上发展起来谓词逻辑在命题逻辑的基础上发展起来l在数理逻辑的历史上，哥德尔的工作起着承前在数理逻辑的

10、历史上，哥德尔的工作起着承前启后的作用启后的作用l他的不完全性定理，把人们引向一种完全不同他的不完全性定理，把人们引向一种完全不同的境界的境界 l第一不完全性定理：一个包括初等数论的形式第一不完全性定理：一个包括初等数论的形式系统，如果是协调的，那就是不完全的。系统，如果是协调的，那就是不完全的。l集合论的产生是近代数学发展的重大事件集合论的产生是近代数学发展的重大事件集合论本来是论证很严格的一个分支，被公认为是集合论本来是论证很严格的一个分支，被公认为是数学的基础数学的基础在集合论的研究过程中，出现了一次称作数学史上在集合论的研究过程中，出现了一次称作数学史上的第三次大危机。这次危机是由于发

11、现了集合论的的第三次大危机。这次危机是由于发现了集合论的悖论引起。（悖论就是逻辑矛盾）悖论引起。（悖论就是逻辑矛盾） 罗素悖论的提出几乎动摇了整个数学基础。罗素悖论的提出几乎动摇了整个数学基础。l罗素悖论中有许多例子，其中一个很通俗也很罗素悖论中有许多例子，其中一个很通俗也很有名的例子就是有名的例子就是“理发师悖论理发师悖论”：某乡村有一位理发师，有一天他宣布：只给不自己某乡村有一位理发师，有一天他宣布：只给不自己理发的人理发。那么就产生了一个问题：理发师究理发的人理发。那么就产生了一个问题：理发师究竟给不给自己理发？如果他给自己理发，他就是自竟给不给自己理发？如果他给自己理发，他就是自己理发

12、的人，按照他的原则，他又不该给自己理发；己理发的人，按照他的原则，他又不该给自己理发；如果他不给自己理发，那么他就是不自己理发的人，如果他不给自己理发，那么他就是不自己理发的人，按照他的原则，他又应该给自己理发。这就产生了按照他的原则，他又应该给自己理发。这就产生了矛盾。矛盾。l悖论的提出，促使许多数学家去研究集悖论的提出，促使许多数学家去研究集合论的无矛盾性问题，从而产生了数理合论的无矛盾性问题，从而产生了数理逻辑的一个重要分支逻辑的一个重要分支公理集合论公理集合论l无理数的发现无理数的发现-第一次数学危机第一次数学危机毕达哥拉斯学派证明了勾股定理，由此发现毕达哥拉斯学派证明了勾股定理，由此

13、发现一些直角三角形的斜边不能表示成整数或整一些直角三角形的斜边不能表示成整数或整数之比（不可通约）数之比（不可通约）l无穷小是零吗？无穷小是零吗？-第二次数学危机第二次数学危机龟兔赛跑，龟兔赛跑，“兔子永远追不上乌龟兔子永远追不上乌龟”l非欧几何的产生和集合论的悖论的发现，非欧几何的产生和集合论的悖论的发现，说明数学本身还存在许多问题，为了研说明数学本身还存在许多问题，为了研究数学系统的无矛盾性问题，产生了证究数学系统的无矛盾性问题，产生了证明论明论l证明论（证明论（proof theory）证明论是数学家证明论是数学家D.希尔伯特于希尔伯特于20世纪初期建立的，目的是要世纪初期建立的，目的是

14、要证明公理系统的无矛盾性证明公理系统的无矛盾性1931年，年，K.哥德尔证明：一个包含公理化的算术的系统中不哥德尔证明：一个包含公理化的算术的系统中不能证明它自身的无矛盾性。这就是著名的哥德尔不完备性定能证明它自身的无矛盾性。这就是著名的哥德尔不完备性定理理1936年，年，G.根岑证明了算术公理系统的无矛盾性根岑证明了算术公理系统的无矛盾性20世纪世纪60年代以后，证明论不再局限于无矛盾性的证明年代以后，证明论不再局限于无矛盾性的证明l欧氏几何的五条公理是：欧氏几何的五条公理是：1、任意两个点可以通过一条直线连接。、任意两个点可以通过一条直线连接。 2、任意线段能无限延伸成一条直线。、任意线段

15、能无限延伸成一条直线。 3、给定任意线段，可以以其一个端点作为圆心，该线段作为半径作、给定任意线段，可以以其一个端点作为圆心，该线段作为半径作一个圆。一个圆。 4、所有直角都全等。、所有直角都全等。 5、若两条直线都与第三条直线相交，并且在同一边的内角之和小于、若两条直线都与第三条直线相交，并且在同一边的内角之和小于两个直角，则这两条直线在这一边必定相交。两个直角，则这两条直线在这一边必定相交。l过直线外一点有且只有一条直线与已知直线平行过直线外一点有且只有一条直线与已知直线平行 l第五条公理称为平行公理第五条公理称为平行公理 罗氏几何的五条公理是：罗氏几何的五条公理是：1、任意两个点可以通过

16、一条直线连接。、任意两个点可以通过一条直线连接。 2、任意线段能无限延伸成一条直线。、任意线段能无限延伸成一条直线。 3、给定任意线段，可以以其一个端点作为圆心，该线段作为半径作、给定任意线段，可以以其一个端点作为圆心，该线段作为半径作一个圆。一个圆。 4、所有直角都全等。、所有直角都全等。 5、一个和欧式平行公理相矛盾的命题、一个和欧式平行公理相矛盾的命题 。 l过直线外一点至少存在两条直线和已知直线平行过直线外一点至少存在两条直线和已知直线平行 l黎曼几何的五条公理是：黎曼几何的五条公理是：1、任意两个点可以通过一条直线连接。、任意两个点可以通过一条直线连接。 2、任意线段能无限延伸成一条

17、直线。、任意线段能无限延伸成一条直线。 3、给定任意线段，可以以其一个端点作为圆心，该线段作为半径作、给定任意线段，可以以其一个端点作为圆心，该线段作为半径作一个圆。一个圆。 4、所有直角都全等。、所有直角都全等。 5、在同一平面内任何两条直线都有公共点、在同一平面内任何两条直线都有公共点(交点交点)。 l过直线外一点，不能做直线和已知直线平行过直线外一点，不能做直线和已知直线平行l欧氏几何、罗氏几何、黎曼几何是三种各有区别的几何。这三中欧氏几何、罗氏几何、黎曼几何是三种各有区别的几何。这三中几何各自所有的命题都构成了一个严密的公理体系，各公理之间几何各自所有的命题都构成了一个严密的公理体系，

18、各公理之间满足和谐性、完备性和独立性。因此这三种几何都是正确的。满足和谐性、完备性和独立性。因此这三种几何都是正确的。(相相容性问题，解决的工具是证明论与模型论）容性问题，解决的工具是证明论与模型论）l在我们这个不大不小、不远不近的空间里，也就是在我们的日常在我们这个不大不小、不远不近的空间里，也就是在我们的日常生活中，欧式几何是适用的；在宇宙空间中或原子核世界，罗氏生活中，欧式几何是适用的；在宇宙空间中或原子核世界，罗氏几何更符合客观实际；在地球表面研究航海、航空等实际问题中，几何更符合客观实际；在地球表面研究航海、航空等实际问题中，黎曼几何更准确一些。黎曼几何更准确一些。l爱因斯坦花了四年的时间，认真地学习黎曼几何，后来用黎曼几爱因斯坦花了四年的时间，认真地学习黎曼几何，后来用黎曼几何的语言创立和表述了广义相对论。何的语言创立和表述了广义相对论。 l离散数学在信息管理与信息系统专业中离散数学在信息管理与信息系统专业中的应用或分散或隐藏，无处不在的应用或分散或隐藏，无处不在l作为基础课程的离散数学的教学在内容作为基