离散数学逻辑L0绪论课件.ppt

Lu Chaojun, SJTU * Lu Chaojun, SJTU * 数理逻辑与计算机科学 计算机?图灵机 计算机能做什么,算法是什么?可计算性理论 计算机不能做什么? 算法不可解问题 逻辑程序设计(Prolog) ?谓词逻辑 程序设计语言的语义学?模型论 形式规格说明与程序验证?模型论 AI,知识表示,自动定理证明 ? 逻辑演算 从形式证明产生程序 ? 证明论(Gentzen) …… * Lu Chaojun, SJTU * Lu Chaojun, SJTU * 戴克斯特拉 Edsger Wybe Dijkstra (1930-2002) 最伟大的计算机科学家(之一?) “搞了这么多年软件,错误不知犯了多少,现在觉悟了.我想,假如我早年在数理逻辑上好好下点功夫的话,我就不会犯这么多的错误,不少东西逻辑学家早就说了,可我不知道.要是我能年轻二十岁的话,就要回去学逻辑.” 成就很多,如Dijkstra最短路径算法(见教材11.5) EWD手稿:/users/EWD/ * 图论 简介 Lu Chaojun, SJTU * Lu Chaojun, SJTU * 什么是图论? 图论(graph theory)研究图,即由顶点和边构成的数学结构. 不关心顶点位置和边的曲直长短,只关心有多少顶点以及边连接的是哪些顶点. * 图论起源 欧拉(Euler)于1736年解决K?nigsberg七桥问题标志着图论的开端. 四色问题 基希霍夫(Kirchhoff)对电路网络的研究 凯莱(Cayley)对有机化学中同分异构体个数的计算 许多数学游戏和谜题 Lu Chaojun, SJTU * Lu Chaojun, SJTU * Lu Chaojun, SJTU * 欧拉 Leonhard Paul Euler (1707-1783) K?nigsberg七桥问题 图论的第一个定理 * Lu Chaojun, SJTU * Lu Chaojun, SJTU * 四色问题 地图只需四种颜色即可保证相邻区域具有不同颜色. 1852年De Morgan的学生Guthrie提出的猜想,从而De Morgan成为最早研究此问题的数学家. De Morgan也是数理逻辑的大家. 1976年由Kenneth Appel和Wolfgang Haken证明,也是用计算机证明的第一个重要定理. * Lu Chaojun, SJTU * Lu Chaojun, SJTU * 图论研究的问题 枚举满足特定条件的图 寻找特定子图 图着色 路径问题 网络流 覆盖问题 …… * Lu Chaojun, SJTU * Lu Chaojun, SJTU * 图论的应用 是计算机科学的重要组成部分 图结构与图算法 其他领域的很多结构也都可用图表示 物理:电路及芯片设计 化学:化合物结构 科学与经济管理:道路交通网络 社会学:社交网络分析 …… * Lu Chaojun, SJTU * Lu Chaojun, SJTU * End * Lu Chaojun, SJTU Lu Chaojun, SJTU 离散数学 课程介绍 Lu Chaojun, SJTU * Lu Chaojun, SJTU * * 教师信息 主讲 陆朝俊(电信学院计算机科学与工程系) 电子邮箱: lu-cj@ 教学资料: :990/lu-cj 办公室: 电院楼群3-525 助教 Lu Chaojun, SJTU * Lu Chaojun, SJTU * 教材和参考书 教材 《离散数学》 董晓蕾,曹珍富编著 机械工业出版社,2009. 参考书 Discrete Mathematics and Its Applications,第5版 K. Rosen 机械工业出版社,2003. Lu Chaojun, SJTU Lu Chaojun, SJTU * Lu Chaojun, SJTU * * 讲授内容 第一篇:数理逻辑 第1章:命题逻辑 1.9不做要求 第2章:谓词逻辑 2.4.1不做要求 第五篇:图论 第11章:无向图 第12章:平面图与着色 第13章:有向图 第14章:树 离散数学精品课程网站 /dm/ Lu Chaojun, SJTU * Lu Chaojun, SJTU * * 什么是离散数学? 离散数学(discrete mathematics)是研究离散对象的数学分支. 离散:由分离的元素组成.如自然数集,学生集合. 相对应的是连续对象. 如实数集. 微积分就是研究连续函数的数学分支. 内容包括: 集合,关系,函数 见本教材第二篇,建议不熟悉的同学自己阅读 数理逻辑 图论 抽象代数 组合数学, …… Lu Chaojun, SJTU *