离散数学简介

离散数学南京大学信息管理学院杨建林什么叫离散数学？–离散：分离，分散（空间）；与连续相对–离散对象（量）：不连续的，可分离的，如自然数。不同于实数对象的集合，有限或可数–离散数学是以离散(即非连续)对象的数量和空间关系为研究内容的若干个数学分支的总称。–包括数理逻辑、近世代数、古典概率、组合学、图论、集合论、数论、自动机和形式语言、可计算性和可判定性、离散几何、代数结构等。简介“离散”和“连续”之间的对立与统一是数学发展的重要动力之一.古代数学主要讨论整数等离散与离散化了的数量关系，因而，那时数学被看成是研究上述数量关系的科学.但随着数学理论的发展，处理离散数量关系的数学工具在刻画和处理某类事务方面显得无能为力，因此出现了处理连续数量关系的数学工具：微积分.简介4离散数学的由来与发展离散数学是随着计算机科学与技术的产生发展和应用领域的不断发展而逐步形成和发展起来的一门新兴学科，作为一门课程开设于上世纪70年代初。数论举例：费马大定理勾股定理：特例32+42=52)3(nzyxnnn简介简介图论举例：欧拉的七桥问题–18世纪著名古典数学问题之一–东普鲁士的哥尼斯堡城，普雷格尔河流经此镇，奈发夫岛位于河中，共有7座桥横跨河上，把全镇连接起来–战争期间，破坏这七座桥。设想用一辆装载炸药的车，每过一桥便炸毁该桥，车无法从原桥驶回–设计一种行驶路线的方案，要将七座桥都这样炸毁，不许遗漏一座桥把这个问题转化为数学问题：把东、南、北及岛四区看成四个点，连接它们的七座桥看成七条通路，如东区与北区由桥3相连，则它们之间有一条通路，南区与北区没有桥直接相连，则它们之间就没有直接的通路。以A代表岛区，B，C，D分别代表北、东、南三区，把这四个点和连接它们的代表七座桥的通路在图上画出来，就得到图(2)．问题可以叙述为：以A，B，C，D这四点中的任一点为起点，能否不重复地用一笔便将上面的图形画出来一个图形要能一笔画完成必须符合两个条件，即图形是封闭联通的和图形中的奇点（与奇数条边相连的点）个数为0或2。离散数学与计算机科学的关系离散数学是计算机科学的理论基础计算机的理论模型是离散的图灵机本质上计算机只处理离散对象，但可通过近似和模拟等手段处理连续对象（如求极值问题）现代计算机越来越多地用于处理离散对象离散数学在计算机科学中直接有用，是计算机科学的工具离散数学与计算机科学的关系离散数学是后继课程的基础离散数学是实际应用的基础工具计算机科学和离散数学处理问题的方法、思维方式有相似之处离散数学可提供所需的思维训练，培养所需的分析问题和解决问题的能力离散数学是学习数据结构与算法、数据库、编译原理、算法设计与分析、计算机网络等课程的主要基础，对开发大型软件、研究信息安全和密码学、开展计算机理论研究以及开发新型计算机都提供了不可缺少的基础知识简介离散数学一命题逻辑二谓词逻辑三集合论四图论教材：耿素云，屈婉玲，离散数学，高教出版社，2004数理逻辑逻辑一词源于希腊文，意思指：词、思想、理性、规律等。逻辑学研究的是：判别一个推理过程是否正确的标准。数理逻辑也叫符号逻辑，即用人工符号来书写逻辑法则，它是一门涉及数学、逻辑学、哲学等学科的横向交叉学科。数理逻辑现代数理逻辑可分为–命题逻辑演算–谓词逻辑演算–证明论–模型论–递归函数论–公理化集合论等数理逻辑命题逻辑和一阶谓词逻辑是数理逻辑中最成熟的部分，在计算机科学中应用最为广泛–命题逻辑是数理逻辑的最基础部分–谓词逻辑在命题逻辑的基础上发展起来数理逻辑在数理逻辑的历史上，哥德尔的工作起着承前启后的作用他的不完全性定理，把人们引向一种完全不同的境界第一不完全性定理：一个包括初等数论的形式系统，如果是协调的，那就是不完全的。数理逻辑集合论的产生是近代数学发展的重大事件–集合论本来是论证很严格的一个分支，被公认为是数学的基础–在集合论的研究过程中，出现了一次称作数学史上的第三次大危机。这次危机是由于发现了集合论的悖论引起。（悖论就是逻辑矛盾）–罗素悖论的提出几乎动摇了整个数学基础。数理逻辑罗素悖论中有许多例子，其中一个很通俗也很有名的例子就是“理发师悖论”：–某乡村有一位理发师，有一天他宣布：只给不自己理发的人理发。那么就产生了一个问题：理发师究竟给不给自己理发？如果他给自己理发，他就是自己理发的人，按照他的原则，他又不该给自己理发；如果他不给自己理发，那么他就是不自己理发的人，按照他的原则，他又应该给自己理发。这就产生了矛盾。数理逻辑悖论的提出，促使许多数学家去研究集合论的无矛盾性问题，从而产生了数理逻辑的一个重要分支—公理集合论数理逻辑无理数的发现---第一次数学危机–毕达哥拉斯学派证明了勾股定理，由此发现一些直角三角形的斜边不能表示成整数或整数之比（不可通约）无穷小是零吗？---第二次数学危机–龟兔赛跑，“兔子永远追不上乌龟”数理逻辑非欧几何的产生和集合论的悖论的发现，说明数学本身还存在许多问题，为了研究数学系统的无矛盾性问题，产生了证明论数理逻辑证明论（prooftheory）–证明论是数学家D.希尔伯特于20世纪初期建立的，目的是要证明公理系统的无矛盾性–1931年，K.哥德尔证明：一个包含公理化的算术的系统中不能证明它自身的无矛盾性。这就是著名的哥德尔不完备性定理–1936年，G.根岑证明了算术公理系统的无矛盾性–20世纪60年代以后，证明论不再局限于无矛盾性的证明欧氏几何欧氏几何的五条公理是：–1、任意两个点可以通过一条直线连接。–2、任意线段能无限延伸成一条直线。–3、给定任意线段，可以以其一个端点作为圆心，该线段作为半径作一个圆。–4、所有直角都全等。–5、若两条直线都与第三条直线相交，并且在同一边的内角之和小于两个直角，则这两条直线在这一边必定相交。过直线外一点有且只有一条直线与已知直线平行第五条公理称为平行公理罗巴切夫斯基几何简称罗氏几何–罗氏几何的五条公理是：1、任意两个点可以通过一条直线连接。–2、任意线段能无限延伸成一条直线。–3、给定任意线段，可以以其一个端点作为圆心，该线段作为半径作一个圆。–4、所有直角都全等。–5、一个和欧式平行公理相矛盾的命题。过直线外一点至少存在两条直线和已知直线平行黎曼几何黎曼几何的五条公理是：–1、任意两个点可以通过一条直线连接。–2、任意线段能无限延伸成一条直线。–3、给定任意线段，可以以其一个端点作为圆心，该线段作为半径作一个圆。–4、所有直角都全等。–5、在同一平面内任何两条直线都有公共点(交点)。过直线外一点，不能做直线和已知直线平行三种几何的关系欧氏几何、罗氏几何、黎曼几何是三种各有区别的几何。这三中几何各自所有的命题都构成了一个严密的公理体系，各公理之间满足和谐性、完备性和独立性。因此这三种几何都是正确的。(相容性问题，解决的工具是证明论与模型论）在我们这个不大不小、不远不近的空间里，也就是在我们的日常生活中，欧式几何是适用的；在宇宙空间中或原子核世界，罗氏几何更符合客观实际；在地球表面研究航海、航空等实际问题中，黎曼几何更准确一些。爱因斯坦花了四年的时间，认真地学习黎曼几何，后来用黎曼几何的语言创立和表述了广义相对论。离散数学与信息管理专业关系离散数学在信息管理与信息系统专业中的应用或分散或隐藏，无处不在作为基础课程的离散数学的教学在内容与形式上缺乏对本专业的直接针对性将离散数学知识转为具体应用有时依赖于知识掌握人的悟性离散数学与信息管理专业关系离散数学的原理渗透于信息管理与信息系统专业的一些相关课程之中。如–《数据结构》中的“树”的结构与遍历；–《数据库原理》中的关系的定义与操作;–《程序设计》中的逻辑运算与检测;–《信息检索》中的“集合”的交并补运算（即检索的算法实现），等等。离散数学与信息管理专业关系目前迎合用户需求的智能代理、个性化服务机制中大量应用到了离散数学的原理与算法学习离散数学的方法彻底理解基本概念和方法（本质、实际背景、实际意义），多思考多做习题，灵活应用，举一反三