数理逻辑与集合论.pptVIP

* 递归论 亦称(能行)可计算性理论,研究能行可计算的函数. 从递归函数和图灵机的等价产生可计算函数的概念 代表人物 G?del:递归函数 Alonzo Church(丘奇):?演算 Alan Turing(图灵):图灵机 现代计算机设计思想的创始人之一 * * 证明论 研究数学理论系统的形式证明问题,即以证明为研究对象,用数学方法分析之.主要关注系统的协调性. 代表人物 Hilbert:首先提出 Gerhard Gentzen:发展了证明论的重要成果. 证明了算术形式系统的协调性. 系统外证明,且不是有穷主义的.与G?del的结果不矛盾. * * 数理逻辑与计算机科学 计算机?图灵机 计算机能做什么,算法是什么?可计算性理论 计算机不能做什么? 算法不可解问题 逻辑程序设计(Prolog) ?谓词逻辑 程序设计语言的语义学?模型论 形式规格说明与程序验证?模型论 AI,知识表示,自动定理证明 ? 逻辑演算 从形式证明产生程序 ? 证明论(Gentzen) …… * * 离散数学 计算机系 陈玉泉 * 联系方式 陈玉泉： chen-yq@cs.sjtu.edu.cn cc.sjtu.edu.cn(课程网站)离散数学1 (从教师陈玉泉检索进入) TelO) 电院楼群3-525 助教：张晨 chase.zhang@sjtu.edu.cn 电院楼群3-508 教材和参考书 1、教材： 数理逻辑与集合论：石纯一，清华大学出版社 图论与代数结构：戴一奇，清华大学出版社 2、参考书： 数理逻辑：莫绍揆，科学文献出版社 Discrete Mathematics and Its Applications, 第5版,K. Rosen,机械工业出版社,2003. 图论及其应用，J.A.Bondy * 课程说明 讲授内容： 数理逻辑 图论 作业： 每周三交作业 * * * 什么是离散数学? 离散数学(discrete mathematics)是研究离散对象的数学分支. 离散:由分离的元素组成.如自然数集. 相对应的是连续对象. 如实数集. 微积分就是研究连续函数的数学分支. 内容包括: 集合,关系,函数 数理逻辑 图论 抽象代数 组合数学 数论, …… * 为什么学离散数学? 提高数学论证和求解能力 培养抽象思维能力和逻辑推理能力 是计算机科学和技术的数学基础 数据结构,算法,数据库理论,自动机理论,形式语言,编译理论,计算机安全,操作系统,人工智能,数字电路 也是运筹学,化学,工程,生物学等很多领域的数学基础 * * 数理逻辑与计算机科学 1946年，德国数学家Von Neumann提出计算机模型 计算机模型根植于数理逻辑、图林机与布尔代数。 Turing机：数字电子计算机的抽象雏形 布尔代数：设计数字电子计算机的数学工具 * 数理逻辑与计算机科学 计算机科学的核心算法 程序设计语言 程序设计方法学 计算复杂性理论 均涉及到数理逻辑的知识和理论 * 戴克斯特拉 Edsger Wybe Dijkstra (1930-2002) 最伟大的计算机科学家(之一?) “搞了这么多年软件,错误不知犯了多少,现在觉悟了.我想,假如我早年在数理逻辑上好好下点功夫的话,我就不会犯这么多的错误,不少东西逻辑学家早就说了,可我不知道.要是我能年轻二十岁的话,就要回去学逻辑.” 成就很多,例如图论中的Dijkstra最短路径算法 * * 什么是数理逻辑？ 逻辑：是对人类推理过程的研究。 数理逻辑：是用数学的方法对人类推理过程作研究。 数学研究方法：使用符号 * 数理逻辑史 数理逻辑前史时期——古典形式逻辑时期 数理逻辑初创时期——逻辑代数时期 数理逻辑奠基时期 数理逻辑发展初期 数理逻辑现代发展时期 * 古典形式逻辑时期 亚里士多德 三段论 斯多阿学派的命题逻辑 中世纪的形式逻辑 * 古典逻辑 亚里士多德的三段论(syllogism) 从两个前提推出一个结论的逻辑论证形式: 1.大前提(major premise) 凡是人都是要死的 2.小前提(minor premise) 苏格拉底是人 3.结论(conclusion) 苏格拉底是要死的 斯多葛学派(Stoics)的命题逻辑 Zeno of Citium于301BC创立的哲学派别 Chrysippus发展了Stoic logic * * 亚里士多德 Aristotle (384BC-322BC) 形式逻辑的奠基人 第一个逻辑学家 三段论:第一个形式演绎逻辑系统 三段论是传统演绎推理的