离散数学 课程介绍

教师信息 主讲 助教 陆朝俊(电信学院计算机科学与工程系) 电子邮箱: lu-cj@cs.sjtu.edu.cn 教学资料: ftp://ftp.cs.sjtu.edu.cn/lu-cj 办公室: 电院楼群3-525 助教 2 2 Lu Chaojun, SJTU Lu Chaojun, SJTU

教材和参考书 教材 参考书 《离散数学》 董晓蕾,曹珍富编著 机械工业出版社,2009. Discrete Mathematics and Its Applications,第5版 K. Rosen 机械工业出版社,2003. 3 Lu Chaojun, SJTU Lu Chaojun, SJTU Lu Chaojun, SJTU

讲授内容 第一篇:数理逻辑 第五篇:图论 第1章:命题逻辑 第2章:谓词逻辑 第11章:无向图 第12章:平面图与着色 第13章:有向图 1.9不做要求 第2章:谓词逻辑 2.4.1不做要求 第五篇:图论 第11章:无向图 第12章:平面图与着色 第13章:有向图 第14章:树 4 4 Lu Chaojun, SJTU Lu Chaojun, SJTU

离散数学精品课程网站 http://tdt.sjtu.edu.cn/dm/

什么是离散数学? 离散数学(discrete mathematics)是研究离散对象的数学分支. 内容包括: 离散:由分离的元素组成.如自然数集,学生集合. 相对应的是连续对象. 如实数集. 微积分就是研究连续函数的数学分支. 内容包括: 集合,关系,函数 见本教材第二篇,建议不熟悉的同学自己阅读 数理逻辑 图论 抽象代数 组合数学, …… 6 6 Lu Chaojun, SJTU Lu Chaojun, SJTU

为什么学离散数学? 提高数学论证和求解能力 培养抽象思维能力和逻辑推理能力 是计算机科学和技术的数学基础 数据结构,算法,数据库理论,自动机理论,形式语言,编译理论,计算机安全,操作系统,人工智能,数字电路 也是运筹学,化学,工程,生物学等很多领域的数学基础 7 7 Lu Chaojun, SJTU Lu Chaojun, SJTU

数理逻辑 简介

什么是逻辑? 逻辑(logic)是关于推理的科学. 西方逻辑起源于古希腊 古代东方逻辑 或:关于思维形式规律的科学. 源自希腊文logos(言词,思想,理性等等) 中文“逻辑”一词由严复首先译用 过去又称名理学,名学,论理学,理则学,辩学等. 西方逻辑起源于古希腊 主要贡献来自亚里士多德和斯多葛学派 古代东方逻辑 中国的名辩之学,散见于名墨儒道各家 古印度的因明 9 9 Lu Chaojun, SJTU Lu Chaojun, SJTU

为什么要学逻辑? 思维必须符合规律才不会导致谬妄. 推理是获得知识的一种途径 逻辑研究怎样的推理是可靠的. 逻辑还研究一组知识是否协调(一致,相容). 各门科学都是在特殊领域的思维推理活动,故逻辑是一切科学的公共基础. Geology, biology, physiology, … 逻辑思维能力是学习、工作乃至日常生活中的重要能力. 10 10 Lu Chaojun, SJTU Lu Chaojun, SJTU

形式逻辑 形式逻辑(formal logic)研究推理的形式,推理有效性由形式而非内容决定. 例:“所有A是B,所有B是C,故所有A是C”是正确的推理形式,把ABC换成任何具体对象都有效. 但“我喜欢吃辣,也喜欢吃鱼,故我喜欢吃辣子鱼”恐怕就不能得出一般的形式. 11 11 Lu Chaojun, SJTU Lu Chaojun, SJTU

数理逻辑 符号逻辑(symbolic logic):对逻辑推理的形式特征进行符号抽象. 使用人工符号语言. 分为命题逻辑和谓词逻辑. 数理逻辑(mathematical logic):是符号逻辑及其在其他数学领域的扩展. 四论:集合论,模型论,递归论,证明论 或说:符号逻辑=数理逻辑 12 12 Lu Chaojun, SJTU Lu Chaojun, SJTU

数理逻辑发展简史 逻辑发展史中的里程碑式的人物 亚里士多德 莱布尼茨 布尔 弗雷格 希尔伯特 罗素 哥德尔 13 13 Lu Chaojun, SJTU Lu Chaojun, SJTU

古典逻辑 亚里士多德的三段论(syllogism) 斯多葛学派(Stoics)的命题逻辑 从两个前提推出一个结论的逻辑论证形式: 1.大前提(major premise) 人都是两足动物 2.小前提(minor premise) 希腊人都是人 3.结论(conclusion) 希腊人都是两足动物 斯多葛学派(Stoics)的命题逻辑 Zeno of Citium于301BC创立的哲学派别 Chrysippus发展了Stoic logic 14 14 Lu Chaojun, SJTU Lu Chaojun, SJTU

亚里士多德 Aristotle (384BC-322BC) 形式逻辑的奠基人 第一个逻辑学家 第一个形式演绎逻辑系统:三段论 三段论是传统演绎推理的核心,在西方逻辑中一直处于统治地位,直至19世纪被数理逻辑(一阶谓词逻辑)所取代. 附注:欧几里德(Euclid,330BC-275BC)的《几何原本》第一次以公理化方式演绎地处理数学. 15 15 Lu Chaojun, SJTU Lu Chaojun, SJTU

莱布尼茨 Gottfried Wilhelm Leibniz (1646-1716) Leibniz的梦想:推理归结为(符号)计算. 数理逻辑的先驱 首先使用“数理逻辑”这个术语 Leibniz的梦想:推理归结为(符号)计算. 两大思想:“普遍语言”和“思维演算” 这正是数理逻辑的主导思想. “发生争论时我们可以简单地说:让我们计算一下吧,看谁正确.” Russell说:Leibniz未发表手稿中发展的逻辑的水平只在200年后才重新达到. 16 16 Lu Chaojun, SJTU Lu Chaojun, SJTU

布尔 George Boole (1815-1864) 数理逻辑创始人之一 如1847年的论文:逻辑的数学分析:论演绎推理的演算法. 首次应用数学(代数)方法研究逻辑,发明了布尔代数(逻辑代数,命题代数,布尔逻辑) 初步实现了Leibniz梦想. 亦可解释成集合代数,开关代数 是计算机数字逻辑的基础 附注:Augustus de Morgan (1806-1871)几乎同时独立地做出重要贡献. Charles Sanders Peirce (1839-1914)发展了这两人的工作. Ernst Schröder (1841-1902)进一步总结发展前三人的工作. 17 17 Lu Chaojun, SJTU Lu Chaojun, SJTU

弗雷格 Friedrich Ludwig Gottlob Frege (1848-1925) 数理逻辑主要创始人 分析哲学,语言哲学创始人 重要著作:Begriffsschrift (1879) 《概念文字:一种模仿算术语言构造的纯思维的形式语言》. 第一个公理化谓词逻辑系统 自Aristotle以来逻辑的最重要进展 基本实现了Leibniz梦想 18 18 Lu Chaojun, SJTU Lu Chaojun, SJTU

数学基础危机(1) 19世纪早期发现数学一直存在缺陷.如: 非欧几何(Lobachevsky,Riemann) 分析(微积分及其扩展)的基础 19世纪后期的公理化运动:去除基于直觉或经验的朴素概念的模糊之处,使数学严密化.如: 算术公理化(Dedekind 1888, Peano 1889) 几何公理化(Hilbert 1899) 19 19 Lu Chaojun, SJTU Lu Chaojun, SJTU

数学基础危机(2) 1900年国际数学大会 随后发现了Cantor集合论中的一些悖论:如1901年的罗素悖论. Poincare:“借助集合论…可以建造数学大厦…今天我们可以宣称绝对的严密已经实现了!” 随后发现了Cantor集合论中的一些悖论:如1901年的罗素悖论. 弗雷格:当大厦竣工时基础却动摇了. 20 20 Lu Chaojun, SJTU Lu Chaojun, SJTU

解决危机的四大派别 逻辑主义:主张从逻辑推出数学. 形式主义:对全部数学进行形式化,并证明其协调性. 直觉主义:反对排中律,强调构造性. 代表人物Russell 形式主义:对全部数学进行形式化,并证明其协调性. 代表人物Hilbert 直觉主义:反对排中律,强调构造性. 代表人物Brouwer 公理化集合论 代表人物Zermelo 21 21 Lu Chaojun, SJTU Lu Chaojun, SJTU

罗素 Bertrand Arthur William Russell (1872-1970) 重要论著 逻辑主义创始人之一 主张从逻辑推出全部数学. 重要论著 Principia Mathematica,1910 与Whitehead合著 PM系统是完备的命题演算和谓词演算. 逻辑演算的经典系统. 22 22 Lu Chaojun, SJTU Lu Chaojun, SJTU

希尔伯特 David Hilbert (1862-1943) 数理逻辑中形式主义学派 证明论创始人之一 Hilbert’s program:将理论至于逻辑演算中加以形式化,重点研究系统中证明的逻辑性质,希望得出系统的协调性.强调证明要使用有穷方法. 23 23 Lu Chaojun, SJTU Lu Chaojun, SJTU

Gödel不完备性定理 Gödel于1931年发表的不完备性定理是对Hilbert’s program的致命一击. 大意:任何足够强的形式系统都有无法证明的真命题.且系统自己不能证明自己无矛盾. 显示了形式化方法的本质局限. 20世纪数理逻辑的顶峰. 也有评论说是20世纪最重要的数学定理 24 24 Lu Chaojun, SJTU Lu Chaojun, SJTU

哥德尔 Kurt Gödel (1906-1978) 证明了一阶谓词演算的完备性. 证明了更加重要的成果:不完备性定理. 实现了Leibniz梦想. 证明了更加重要的成果:不完备性定理. Einstein说:自己的工作不再要紧,来研究院只是为了享有和Gödel一起步行回家的特权. 25 25 Lu Chaojun, SJTU Lu Chaojun, SJTU

数理逻辑的分支 基础的逻辑演算 公理集合论 模型论 递归论 证明论 26 26 Lu Chaojun, SJTU

公理集合论 研究公理集合论,是整个数学的基础. Cantor的朴素集合论有缺陷 Ernst Zermelo:第一个公理化集合论(1908) Burali-Forti悖论,罗素悖论,Richard悖论,… Ernst Zermelo:第一个公理化集合论(1908) 经Fraenkel(1922)改进成为经典的ZF集合论 避免了罗素悖论 Gödel和Paul Cohen(1963)在CH方面的工作 CH在ZF系统中不可判定 Cohen的新方法(力迫法)让人们证明了许多不可判定的问题.数学绝不是“非真即假”那么单纯! 27 27 Lu Chaojun, SJTU Lu Chaojun, SJTU

模型论 建立形式理论的模型,研究模型之间的关系等. Alfred Tarski奠定了模型论的基础 模型是对形式理论进行具体解释的一种结构. 语法与语义的关系 Alfred Tarski奠定了模型论的基础 28 28 Lu Chaojun, SJTU Lu Chaojun, SJTU

递归论 亦称(能行)可计算性理论,研究能行可计算的函数. 代表人物 从递归函数和图灵机的等价产生可计算函数的概念 Gödel:递归函数 Alonzo Church(丘奇):演算 Alan Turing(图灵):图灵机 现代计算机设计思想的创始人之一 29 29 Lu Chaojun, SJTU Lu Chaojun, SJTU

证明论 研究数学理论系统的形式证明问题,即以证明为研究对象,用数学方法分析之.主要关注系统的协调性. 代表人物 Hilbert:首先提出 Gerhard Gentzen:发展了证明论的重要成果. 证明了算术形式系统的协调性. 是在系统外证明,且不是有穷主义的.与Gödel的结果不矛盾. 30 30 Lu Chaojun, SJTU Lu Chaojun, SJTU

数理逻辑与计算机科学 计算机图灵机 计算机能做什么,算法是什么可计算性理论 计算机不能做什么 算法不可解问题 逻辑程序设计(Prolog) 谓词逻辑 程序设计语言的语义学模型论 形式规格说明与程序验证模型论 AI,知识表示,自动定理证明  逻辑演算 从形式证明产生程序  证明论(Gentzen) …… 31 31 Lu Chaojun, SJTU Lu Chaojun, SJTU

戴克斯特拉 Edsger Wybe Dijkstra (1930-2002) 最伟大的计算机科学家(之一?) “搞了这么多年软件,错误不知犯了多少,现在觉悟了.我想,假如我早年在数理逻辑上好好下点功夫的话,我就不会犯这么多的错误,不少东西逻辑学家早就说了,可我不知道.要是我能年轻二十岁的话,就要回去学逻辑.” 成就很多,例如图论中的Dijkstra最短路径算法(见教材11.5) 32 32 Lu Chaojun, SJTU Lu Chaojun, SJTU

图论 简介

什么是图论? 图论(graph theory)研究图,即由顶点和边构成的数学结构. 不关心顶点位置和边的曲直长短,只关心有多少顶点以及边连接的是哪些顶点. 34 34 Lu Chaojun, SJTU Lu Chaojun, SJTU

图论起源 欧拉(Euler)于1736年解决Königsberg七桥问题标志着图论的开端. 四色问题 基希霍夫(Kirchhoff)对电路网络的研究 凯莱(Cayley)对有机化学中同分异构体个数的计算 许多数学游戏和谜题 Lu Chaojun, SJTU

欧拉 Leonhard Paul Euler (1707-1783) Königsberg七桥问题 图论的第一个定理 36 36 Lu Chaojun, SJTU Lu Chaojun, SJTU

四色问题 地图只需四种颜色即可保证相邻区域具有不同颜色. 1852年De Morgan的学生Guthrie提出的猜想,从而De Morgan成为最早研究此问题的数学家. De Morgan也是数理逻辑的大家. 1976年由Kenneth Appel和Wolfgang Haken证明,也是用计算机证明的第一个重要定理. 37 37 Lu Chaojun, SJTU Lu Chaojun, SJTU

图论研究的问题 枚举满足特定条件的图 寻找特定子图 图着色 路径问题 网络流 覆盖问题 …… 38 38 Lu Chaojun, SJTU

图论的应用 是计算机科学的重要组成部分 其他领域的很多结构也都可用图表示 图结构与图算法 物理:电路及芯片设计 化学:化合物结构 科学与经济管理:道路交通网络 社会学:社交网络分析 …… 39 39 Lu Chaojun, SJTU Lu Chaojun, SJTU

End 40 Lu Chaojun, SJTU Lu Chaojun, SJTU