第0章-离散数学简介.pptVIP

* 欧氏几何公理 五条几何公理 　　1.过相异两点，能作且只能作一直线（直线公理）。 　　2.线段(有限直线)可以任意地延长。 　　3.以任一点为圆心、任意长为半径，可作一圆(圆公理)。 　　4.凡是直角都相等(角公理)。 　　5.两直线被第三条直线所截，如果同侧两内角和小於两个直角， 则两直线作延长时在此侧会相交。 　　上述前三条公理是尺规作图公理，用来定直线与圆。在纸面上用尺规划出的任何直线与圆，按定义而言，都不是「真正」数学上的直线与圆。然而，欧氏似乎是说：我们可以用尺规作出近似的图形，以帮助我们想像真正的图形，再配合正确的推理就够了。 　　第四条公理比较不一样，它好像是一个未证明的定理。事实上，它宣称著：直角的不变性或空间的齐性 (the homogeneity of space)。它规范了直角，为第五公理铺路。 　　第五公理又叫做平行公理 (the parallel axiom)，因为它等价於： 　　在一平面内，过直线外一点，可作且只可作一直线跟此直线平行。 离 散 数 学 南京大学信息管理学院 杨建林 什么叫离散数学？ 离散：分离，分散（空间）；与连续相对 离散对象（量）：不连续的，可分离的，如自然数。不同于实数对象的集合，有限或可数 离散数学是以离散(即非连续)对象的数量和空间关系为研究内容的若干个数学分支的总称。 包括数理逻辑、近世代数、古典概率、组合学、图论、集合论、数论、自动机和形式语言、可计算性和可判定性、离散几何、代数结构等。 简介 “离散”和“连续”之间的对立与统一是数学发展的重要动力之一. 古代数学主要讨论整数等离散与离散化了的数量关系，因而，那时数学被看成是研究上述数量关系的科学. 但随着数学理论的发展，处理离散数量关系的数学工具在刻画和处理某类事务方面显得无能为力，因此出现了处理连续数量关系的数学工具：微积分. 简介 * 离散数学的由来与发展 离散数学是随着计算机科学与技术的产生发展和应用领域的不断发展而逐步形成和发展起来的一门新兴学科，作为一门课程开设于上世纪70年代初。 数论举例：费马大定理 勾股定理：特例32+42=52 简介 简介 图论举例： 欧拉的七桥问题 18世纪著名古典数学问题之一 东普鲁士的哥尼斯堡城，普雷格尔河流经此镇，奈发夫岛位于河中，共有7座桥横跨河上，把全镇连接起来 战争期间，破坏这七座桥。设想用一辆装载炸药的车，每过一桥便炸毁该桥，车无法从原桥驶回 设计一种行驶路线的方案，要将七座桥都这样炸毁，不许遗漏一座桥 把这个问题转化为数学问题：把东、南、北及岛四区看成四个点，连接它们的七座桥看成七条通路，如东区与北区由桥3相连，则它们之间有一条通路，南区与北区没有桥直接相连，则它们之间就没有直接的通路。 以A代表岛区，B，C，D分别代表北、东、南三区，把这四个点和连接它们的代表七座桥的通路在图上画出来，就得到图(2)． 问题可以叙述为：以A，B，C，D这四点中的任一点为起点，能否不重复地用一笔便将上面的图形画出来 一个图形要能一笔画完成必须符合两个条件，即图形是封闭联通的和图形中的奇点（与奇数条边相连的点）个数为0或2。 离散数学与计算机科学的关系 离散数学是计算机科学的理论基础 计算机的理论模型是离散的图灵机 本质上计算机只处理离散对象，但可通过近似和模拟等手段处理连续对象（如求极值问题） 现代计算机越来越多地用于处理离散对象 离散数学在计算机科学中直接有用，是计算机科学的工具 离散数学与计算机科学的关系 离散数学是后继课程的基础 离散数学是实际应用的基础工具 计算机科学和离散数学处理问题的方法、思维方式有相似之处 离散数学可提供所需的思维训练，培养所需的分析问题和解决问题的能力 离散数学是学习数据结构与算法、数据库、编译原理、算法设计与分析、计算机网络等课程的主要基础，对开发大型软件、研究信息安全和密码学、开展计算机理论研究以及开发新型计算机都提供了不可缺少的基础知识 简介 离散数学 一 命题逻辑 二 谓词逻辑 三 集合论 四 图论 教材：耿素云，屈婉玲，离散数学，高教出版社，2004 数理逻辑 逻辑一词源于希腊文，意思指：词、思想、理性、规律等。 逻辑学研究的是：判别一个推理过程是否正确的标准。 数理逻辑也叫符号逻辑，即用人工符号来书写逻辑法则，它是一门涉及数学、逻辑学、哲学等学科的横向交叉学科。 数理逻辑 现代数理逻辑可分为 命题逻辑演算 谓词逻辑演算 证明论 模型论 递归函数论 公理化集合论等 数理逻辑 命题逻辑和一阶谓词逻辑是数理逻辑中最成熟的部分，在计算机科学中应用最为广泛 命题逻辑是数理逻辑的最基础部分 谓词逻辑在命题逻辑的基础上发展起来 数理逻辑 在数理逻辑的历史上，哥德尔的工作起着承前启后的作用 他的不完全性定理，把人