L0绪论-离散数学

1、离散数学,课程介绍,LuChaojun,SJTU,2,LuChaojun,SJTU,2,2,教师信息,主讲陆朝俊(电信学院计算机科学与工程系)电子邮箱:lu-cj教学资料:ftp:/:990/lu-cjftp:/用户/密码:lucj/public办公室:电院楼群3-525助教,LuChaojun,SJTU,3,LuChaojun,SJTU,3,教材和参考书,教材离散数学董晓蕾,曹珍富编著机械工业出版社,2009.参考书DiscreteMathematicsandItsApplications,第5版K.Rosen机械工业出版社,2003.,LuChaojun,SJTU,LuChaojun,SJ

2、TU,4,LuChaojun,SJTU,4,4,讲授内容,第一篇:数理逻辑第1章:命题逻辑1.9不做要求第2章:谓词逻辑2.4.1不做要求第五篇:图论第11章:无向图第12章:平面图与着色第13章:有向图第14章:树,离散数学精品课程网站,LuChaojun,SJTU,6,LuChaojun,SJTU,6,6,什么是离散数学?,离散数学(discretemathematics)是研究离散对象的数学分支.离散:由分离的元素组成.如自然数集,学生集合.相对应的是连续对象.如实数集.微积分就是研究连续函数的数学分支.内容包括:集合,关系,函数见本教材第二篇,建议不熟悉的同学自己阅读数理逻辑图论抽象代

3、数组合数学,LuChaojun,SJTU,7,LuChaojun,SJTU,7,为什么学离散数学?,提高数学论证和求解能力培养抽象思维能力和逻辑推理能力是计算机科学和技术的数学基础数据结构,算法,数据库理论,自动机理论,形式语言,编译理论,计算机安全,操作系统,人工智能,数字电路也是运筹学,化学,工程,生物学等很多领域的数学基础,7,数理逻辑,简介,LuChaojun,SJTU,9,LuChaojun,SJTU,9,9,什么是逻辑?,逻辑(logic)是关于推理的科学.或:关于思维形式规律的科学.源自希腊文logos(言词,思想,理性等等)中文“逻辑”一词由严复首先译用过去又称名理学,名学,论

4、理学,理则学,辩学等.西方逻辑起源于古希腊主要贡献来自亚里士多德和斯多葛学派古代东方逻辑中国的名辩之学,散见于名墨儒道各家古印度的因明,LuChaojun,SJTU,10,LuChaojun,SJTU,10,为什么要学逻辑?,思维必须符合规律才不会导致谬妄.推理是获得知识的一种途径逻辑研究怎样的推理是可靠的.逻辑还研究一组知识是否协调(一致,相容).各门科学都是在特殊领域的思维推理活动,故逻辑是一切科学的公共基础.Geology,biology,physiology,逻辑思维能力是学习、工作乃至日常生活中的重要能力.,10,LuChaojun,SJTU,11,LuChaojun,SJTU,11

5、,形式逻辑,形式逻辑(formallogic)研究推理的形式,推理有效性由形式而非内容决定.例:“所有A是B,所有B是C,故所有A是C”是正确的推理形式,把ABC换成任何具体对象都有效.但“我喜欢吃辣,也喜欢吃鱼,故我喜欢吃辣子鱼”恐怕就不能得出一般的形式.,11,LuChaojun,SJTU,12,LuChaojun,SJTU,12,数理逻辑,符号逻辑(symboliclogic):对逻辑推理的形式特征进行符号抽象.使用人工符号语言.分为命题逻辑和谓词逻辑.数理逻辑(mathematicallogic):是符号逻辑及其在其他数学领域的扩展.四论:集合论,模型论,递归论,证明论或说:符号逻辑=

6、数理逻辑,12,LuChaojun,SJTU,13,LuChaojun,SJTU,13,数理逻辑发展简史,逻辑发展史中的里程碑人物亚里士多德莱布尼茨布尔弗雷格希尔伯特罗素哥德尔,13,LuChaojun,SJTU,14,LuChaojun,SJTU,14,古典逻辑,亚里士多德的三段论(syllogism)从两个前提推出一个结论的逻辑论证形式:1.大前提(majorpremise)人都是两足动物2.小前提(minorpremise)希腊人都是人3.结论(conclusion)希腊人都是两足动物斯多葛学派(Stoics)的命题逻辑芝诺(ZenoofCitium)于301BC创立克吕希波(Chrys

7、ippus)大大发展了Stoiclogic,14,LuChaojun,SJTU,15,LuChaojun,SJTU,15,亚里士多德,Aristotle(384BC-322BC)形式逻辑的奠基人第一个逻辑学家第一个形式演绎逻辑系统:三段论三段论是传统演绎推理的核心,在西方逻辑中一直处于统治地位,直至19世纪被数理逻辑(一阶谓词逻辑)所取代.附注:欧几里德(Euclid,330BC-275BC)的几何原本第一次以公理化方式演绎地处理数学.,15,LuChaojun,SJTU,16,LuChaojun,SJTU,16,莱布尼茨,GottfriedWilhelmLeibniz(1646-1716)数

8、理逻辑的先驱首先使用“数理逻辑”这个术语LeibnizsDream:推理归结为(符号)计算.两大思想:“普遍语言”和“思维演算”这正是数理逻辑的主导思想.“发生争论时我们可以简单地说:让我们计算一下吧,看谁正确.”罗素评价说:Leibniz未发表手稿中发展的逻辑的水平只在200年后才重新达到.,16,LuChaojun,SJTU,17,LuChaojun,SJTU,17,布尔,GeorgeBoole(1815-1864)数理逻辑创始人之一如1847年的论文:逻辑的数学分析:论演绎推理的演算法.应用数学(代数)方法研究逻辑,发明了布尔代数(逻辑代数,命题代数,布尔逻辑)初步实现了Leibniz梦

9、想.亦可解释成集合代数,开关代数是计算机数字逻辑的基础附注:AugustusdeMorgan(1806-1871)几乎同时独立地做出重要贡献.CharlesSandersPeirce(1839-1914)发展了这两人的工作.ErnstSchrder(1841-1902)进一步总结发展前三人的工作.,17,LuChaojun,SJTU,18,LuChaojun,SJTU,18,弗雷格,FriedrichLudwigGottlobFrege(1848-1925)数理逻辑主要创始人分析哲学,语言哲学创始人重要著作:Begriffsschrift(1879)概念文字:一种模仿算术语言构造的纯思维的形式

10、语言.第一个公理化谓词逻辑系统自Aristotle以来逻辑的最重要进展基本实现了Leibniz梦想,18,LuChaojun,SJTU,19,LuChaojun,SJTU,19,数学基础危机(1),19世纪早期发现数学一直存在缺陷.如:非欧几何(Lobachevsky,Riemann)分析(微积分及其扩展)的基础19世纪后期的公理化运动:去除基于直觉或经验的朴素概念的模糊之处,使数学严密化.如:算术公理化(Dedekind1888,Peano1889)几何公理化(Hilbert1899),19,LuChaojun,SJTU,20,LuChaojun,SJTU,20,数学基础危机(2),1900

11、年国际数学大会Poincare:“借助集合论可以建造数学大厦今天我们可以宣称绝对的严密已经实现了!”随后发现了Cantor集合论中的一些悖论:如1901年的罗素悖论.弗雷格:当大厦竣工时基础却动摇了.,20,LuChaojun,SJTU,21,LuChaojun,SJTU,21,解决危机的四大派别,逻辑主义:主张从逻辑推出数学.代表人物Russell形式主义:对全部数学进行形式化,并证明其协调性.代表人物Hilbert直觉主义:反对排中律,强调构造性.代表人物Brouwer公理化集合论代表人物Zermelo,21,LuChaojun,SJTU,22,LuChaojun,SJTU,22,罗素,B

12、ertrandArthurWilliamRussell(1872-1970)逻辑主义创始人之一主张从逻辑推出全部数学.重要论著PrincipiaMathematica,1910与Whitehead合著PM系统是完备的命题演算和谓词演算.逻辑演算的经典系统.,22,LuChaojun,SJTU,23,LuChaojun,SJTU,23,希尔伯特,DavidHilbert(1862-1943)数理逻辑中形式主义学派证明论创始人之一Hilbertsprogram:将理论至于逻辑演算中加以形式化,重点研究系统中证明的逻辑性质,希望得出系统的协调性.强调证明要使用有穷方法.,23,LuChaojun,S

13、JTU,24,LuChaojun,SJTU,24,Gdel不完备性定理,Gdel于1931年发表的不完备性定理是对Hilbertsprogram的致命一击.大意:任何足够强的形式系统都有无法证明的真命题.且系统自己不能证明自己无矛盾.显示了形式化方法的本质局限.20世纪数理逻辑的顶峰.也有评论说是20世纪最重要的数学定理,24,LuChaojun,SJTU,25,LuChaojun,SJTU,25,哥德尔,KurtGdel(1906-1978)证明了一阶谓词演算的完备性.实现了Leibniz梦想.证明了更加重要的成果:不完备性定理.Einstein说:自己的工作不再要紧,来研究院只是为了享有和

14、Gdel一起步行回家的特权.,25,LuChaojun,SJTU,26,LuChaojun,SJTU,26,数理逻辑的分支,基础的逻辑演算公理集合论模型论递归论证明论,26,LuChaojun,SJTU,27,LuChaojun,SJTU,27,公理集合论,研究公理集合论,是整个数学的基础.Cantor的朴素集合论有缺陷Burali-Forti悖论,罗素悖论,Richard悖论,ErnstZermelo:第一个公理化集合论(1908)经Fraenkel(1922)改进成为经典的ZF集合论避免了罗素悖论Gdel和PaulCohen(1963)在CH方面的工作CH在ZF系统中不可判定Cohen的新

15、方法(力迫法)让人们证明了许多不可判定的问题.数学绝不是“非真即假”那么单纯!,27,LuChaojun,SJTU,28,LuChaojun,SJTU,28,模型论,建立形式理论的模型,研究模型之间的关系等.模型是对形式理论进行具体解释的一种结构.语法与语义的关系AlfredTarski奠定了模型论的基础,28,LuChaojun,SJTU,29,LuChaojun,SJTU,29,递归论,亦称(能行)可计算性理论,研究能行可计算的函数.从递归函数和图灵机的等价产生可计算函数的概念代表人物Gdel:递归函数AlonzoChurch(丘奇):演算AlanTuring(图灵):图灵机现代计算机设计

16、思想的创始人之一,29,LuChaojun,SJTU,30,LuChaojun,SJTU,30,证明论,研究数学理论系统的形式证明问题,即以证明为研究对象,用数学方法分析之.主要关注系统的协调性.代表人物Hilbert:首先提出GerhardGentzen:发展了证明论的重要成果.证明了算术形式系统的协调性.是在系统外证明,且不是有穷主义的.与Gdel的结果不矛盾.,30,LuChaojun,SJTU,31,LuChaojun,SJTU,31,数理逻辑与计算机科学,计算机图灵机计算机能做什么,算法是什么可计算性理论计算机不能做什么算法不可解问题逻辑程序设计(Prolog)谓词逻辑程序设计语言的

17、语义学模型论形式规格说明与程序验证模型论AI,知识表示,自动定理证明逻辑演算从形式证明产生程序证明论(Gentzen),31,LuChaojun,SJTU,32,LuChaojun,SJTU,32,戴克斯特拉,EdsgerWybeDijkstra(1930-2002)最伟大的计算机科学家(之一?)“搞了这么多年软件,错误不知犯了多少,现在觉悟了.我想,假如我早年在数理逻辑上好好下点功夫的话,我就不会犯这么多的错误,不少东西逻辑学家早就说了,可我不知道.要是我能年轻二十岁的话,就要回去学逻辑.”成就很多,如Dijkstra最短路径算法(见教材11.5)EWD手稿:www.cs.utexas.ed

18、u/users/EWD/,32,图论,简介,LuChaojun,SJTU,34,LuChaojun,SJTU,34,什么是图论?,图论(graphtheory)研究图,即由顶点和边构成的数学结构.不关心顶点位置和边的曲直长短,只关心有多少顶点以及边连接的是哪些顶点.,34,图论起源,欧拉(Euler)于1736年解决Knigsberg七桥问题标志着图论的开端.四色问题基希霍夫(Kirchhoff)对电路网络的研究凯莱(Cayley)对有机化学中同分异构体个数的计算许多数学游戏和谜题,LuChaojun,SJTU,35,LuChaojun,SJTU,36,LuChaojun,SJTU,36,欧拉,LeonhardPaulEuler(1707-1783)Knigsberg七桥问题图论的第一个定理,36,LuChaojun,SJTU,37,LuChaojun,SJTU,37,四色问题,地图只需四种颜色即可保证相邻区域具有不同颜色.1852年DeMorgan的学生Guthrie提出的猜想,从而DeMorgan成为最早研究此问题的数学家.DeMorgan也是数理逻辑的大家.1976