离散数学-命题逻辑2013下

1、中国石油大学（华东）离散数学课程组中国石油大学（华东）离散数学课程组离离 散散 数数 学学中国石油大学中国石油大学（华东）（华东）计算机与通信工程学院计算机与通信工程学院计算机科学系计算机科学系2022年1月5日星期三2电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系离散数学离散数学课程学时：课程学时：8080裴振奎裴振奎计算机与通信工程学院计算机科学系计算机与

2、通信工程学院计算机科学系 离散数学是计算机科学中基础理论的核心课程。以研究离散量的结构和相互之间的关系为主要目标，其研究对象一般地是有限个或可数个元素，它充分描述了计算机科学离散性的特点。离散数学教程离散数学教程 耿素云 屈婉玲等编著 北京大学出版社 DISCRETE MATHEMATICS AND ITS APPLICATIONS(FIFTH EDITION)离散数学及其应用，机械工业出版社离散数学及其应用，机械工业出版社(4小时出库) (4小时出库) 15电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油

3、大学（华东）计算机与通信工程学院计算机科学系课程内容课程内容 本课程根据大纲的内容和相关独立性，本课程根据大纲的内容和相关独立性， 可分为四大部分可分为四大部分 第一部分第一部分 数理逻辑数理逻辑 包括命题逻辑包括命题逻辑; ;谓词逻辑谓词逻辑 第二部分第二部分 集合论集合论 包括集合与关系包括集合与关系; ;函数函数第三部分第三部分 代数系统代数系统 包括代数结构包括代数结构; ;格格与与布尔代数布尔代数第四部分第四部分 图论图论 16电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通

4、信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系学习方法学习方法定义、定理多。定义、定理多。 本课内容定义定理例题本课内容定义定理例题为了学好这门课，要求：为了学好这门课，要求： （）弄懂定义、定理，弄懂例题，加深对定义、（）弄懂定义、定理，弄懂例题，加深对定义、定理的理解；定理的理解； （）在复习基础上，做好课外作业。同学之间（）在复习基础上，做好课外作业。同学之间可以讨论，但要弄懂弄通。可以讨论，但要弄懂弄通。 （3 3）做好课堂笔记。）做好课堂笔记。17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精

5、品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系Lu Chaojun, SJTU 1717什么是逻辑什么是逻辑? ?逻辑逻辑( (logiclogic) )是关于推理的科学是关于推理的科学. .p或或: :关于思维形式规律的科学关于思维形式规律的科学. .p源自希腊文源自希腊文logoslogos( (言词言词, ,思想思想, ,理性等等理性等等) )p中文中文“逻辑逻辑”一词由严复首先译用一词由严复首先译用n过去又称

6、名理学过去又称名理学, ,名学名学, ,论理学论理学, ,理则学理则学, ,辩学等辩学等. .西方逻辑起源于古希腊西方逻辑起源于古希腊p主要贡献来自亚里士多德和斯多葛学派主要贡献来自亚里士多德和斯多葛学派古代东方逻辑古代东方逻辑p中国的名辩之学中国的名辩之学, ,散见于名墨儒道各家散见于名墨儒道各家p古印度的因明古印度的因明18电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学

7、院计算机科学系Lu Chaojun, SJTU 18为什么要学逻辑为什么要学逻辑? ?思维必须符合规律才不会导致谬妄思维必须符合规律才不会导致谬妄. .推理是获得知识的一种途径推理是获得知识的一种途径p逻辑研究怎样的推理是可靠的逻辑研究怎样的推理是可靠的. .p逻辑还研究一组知识是否协调逻辑还研究一组知识是否协调( (一致一致, ,相容相容).).各门科学都是在特殊领域的思维推理活动各门科学都是在特殊领域的思维推理活动, ,故逻辑故逻辑是一切科学的公共基础是一切科学的公共基础. .pGeoGeologylogy, , biobiologylogy, , physiophysiologylogy

8、, , 逻辑思维能力是学习、工作乃至日常生活中的重要逻辑思维能力是学习、工作乃至日常生活中的重要能力能力. .1819电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系Lu Chaojun, SJTU 19形式逻辑形式逻辑形式逻辑形式逻辑( (formal logicformal logic) )研究推理的形式研究推理的形式, ,推理有推理有效性由形式而非内容决定

9、效性由形式而非内容决定. .p例例:“:“所有所有A A是是B,B,所有所有B B是是C,C,故所有故所有A A是是C”C”是正确的推是正确的推理形式理形式, ,把把ABCABC换成任何具体对象都有效换成任何具体对象都有效. .p但但“我喜欢吃辣我喜欢吃辣, ,也喜欢吃鱼也喜欢吃鱼, ,故我喜欢吃辣子鱼故我喜欢吃辣子鱼”恐恐怕就不能得出一般的形式怕就不能得出一般的形式. .1920电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程

10、学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系Lu Chaojun, SJTU 20数理逻辑数理逻辑符号逻辑符号逻辑( (symbolic logicsymbolic logic):):对逻辑推理的形式特对逻辑推理的形式特征进行符号抽象征进行符号抽象. .p使用人工符号语言使用人工符号语言. .p分为命题逻辑和谓词逻辑分为命题逻辑和谓词逻辑. .数理逻辑数理逻辑( (mathematical logicmathematical logic):):是符号逻辑及其是符号逻辑及其在其他数学领域的扩展在其他数学领域的扩展. .p四论四论: :集合论集合论, ,模型论模型论, ,递

11、归论递归论, ,证明论证明论或说或说: :符号逻辑符号逻辑= =数理逻辑数理逻辑2021电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系Lu Chaojun, SJTU 21数理逻辑发展简史数理逻辑发展简史逻辑发展史中的里程碑人物逻辑发展史中的里程碑人物p亚里士多德亚里士多德p莱布尼茨莱布尼茨p布尔布尔p弗雷格弗雷格p希尔伯特希尔伯特p罗素罗素p哥德尔哥德尔21

12、22电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系Lu Chaojun, SJTU 22古典逻辑古典逻辑亚里士多德的亚里士多德的三段论三段论( (syllogismsyllogism) )p从两个前提推出一个结论的逻辑论证形式从两个前提推出一个结论的逻辑论证形式: :1.1.大前提大前提( (major premisemajor premise) ) 人都是两

13、足动物人都是两足动物2.2.小前提小前提( (minor premiseminor premise) ) 希腊人都是人希腊人都是人3.3.结论结论( (conclusionconclusion) ) 希腊人都是两足动希腊人都是两足动物物斯多葛学派斯多葛学派( (StoicsStoics) )的命题逻辑的命题逻辑p芝诺芝诺( (Zeno of Citium)Zeno of Citium)于于301BC301BC创立创立p克吕希波克吕希波( (Chrysippus)Chrysippus)大大发展了大大发展了Stoic logicStoic logic2223电子科技大学离散数学课程组电子科技大学离

14、散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系Lu Chaojun, SJTU 23亚里士多德亚里士多德Aristotle (384BC-322BC)Aristotle (384BC-322BC)p 形式逻辑的奠基人形式逻辑的奠基人p 第一个逻辑学家第一个逻辑学家p 第一个形式第一个形式演绎逻辑演绎逻辑系统系统: :三段论三段论n三段论是传统演绎推理的核心三段论是传统演绎推理的核心, ,在西方逻辑中

15、一直处于统治在西方逻辑中一直处于统治地位地位, ,直至直至1919世纪被数理逻辑世纪被数理逻辑( (一阶谓词逻辑一阶谓词逻辑) )所取代所取代. .附注附注: :欧几里德欧几里德( (Euclid,330BC-275BC)Euclid,330BC-275BC)的几何原本第一次以公理化的几何原本第一次以公理化方式演绎地处理数学方式演绎地处理数学. .2324电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大

16、学（华东）计算机与通信工程学院计算机科学系Lu Chaojun, SJTU 24莱布尼茨莱布尼茨Gottfried Wilhelm Leibniz (1646-1716)Gottfried Wilhelm Leibniz (1646-1716)p 数理逻辑的先驱数理逻辑的先驱n 首先使用首先使用“数理逻辑数理逻辑”这个术语这个术语Leibnizs Dream:Leibnizs Dream:推理归结为推理归结为( (符号符号) )计算计算. .p 两大思想两大思想:“:“普遍语言普遍语言”和和“思维演算思维演算”n 这正是数理逻辑的主导思想这正是数理逻辑的主导思想. .p “发生争论时我们可以简

17、单地说发生争论时我们可以简单地说: :让我们计算一下吧让我们计算一下吧, ,看谁正确看谁正确.”.”罗素评价说罗素评价说:Leibniz:Leibniz未发表手稿中发展的逻辑的水平只在未发表手稿中发展的逻辑的水平只在200200年后才重新达到年后才重新达到. .2425电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系Lu Chaojun, SJTU 25布尔布尔

18、George Boole (1815-1864)George Boole (1815-1864)p数理逻辑创始人之一数理逻辑创始人之一n如如18471847年的论文年的论文: :逻辑的数学分析逻辑的数学分析: :论演绎推理的演算法论演绎推理的演算法. .p应用数学应用数学( (代数代数) )方法研究逻辑方法研究逻辑, ,发明了发明了布尔代数布尔代数( (逻辑逻辑代数代数, ,命题代数命题代数, ,布尔逻辑布尔逻辑) )n初步实现了初步实现了LeibnizLeibniz梦想梦想. .n亦可解释成集合代数亦可解释成集合代数, ,开关代数开关代数n是计算机数字逻辑的基础是计算机数字逻辑的基础附注附注

19、:Augustus de Morgan (1806-1871):Augustus de Morgan (1806-1871)几乎同时独立地做出重要贡献几乎同时独立地做出重要贡献. . Charles Sanders Peirce (1839-1914) Charles Sanders Peirce (1839-1914)发展了这两人的工作发展了这两人的工作. . Ernst Schr Ernst Schrder (1841-1902)der (1841-1902)进一步总结发展前三人的工作进一步总结发展前三人的工作. .2526电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国

20、家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系Lu Chaojun, SJTU 26弗雷格弗雷格Friedrich Ludwig Gottlob Frege (1848-1925)Friedrich Ludwig Gottlob Frege (1848-1925)p 数理逻辑主要创始人数理逻辑主要创始人p 分析哲学分析哲学, ,语言哲学创始人语言哲学创始人重要著作重要著作: :Begriffsschrift Begriffs

21、schrift (1879)(1879)p 概念文字概念文字: :一种模仿算术语言构造的纯思维的形一种模仿算术语言构造的纯思维的形式语言式语言. .p 第一个公理化谓词逻辑系统第一个公理化谓词逻辑系统p 自自AristotleAristotle以来逻辑的最重要进展以来逻辑的最重要进展p 基本实现了基本实现了LeibnizLeibniz梦想梦想2627电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华

22、东）计算机与通信工程学院计算机科学系Lu Chaojun, SJTU 27数学基础危机数学基础危机(1)(1)1919世纪早期发现数学一直存在缺陷世纪早期发现数学一直存在缺陷. .如如: :p非欧几何非欧几何(Lobachevsky,Riemann)(Lobachevsky,Riemann)p分析分析( (微积分及其扩展微积分及其扩展) )的基础的基础1919世纪后期的世纪后期的公理化公理化运动运动: :去除基于直觉或经验的去除基于直觉或经验的朴素概念的模糊之处朴素概念的模糊之处, ,使数学严密化使数学严密化. .如如: :p算术公理化算术公理化(Dedekind 1888, Peano 18

23、89)(Dedekind 1888, Peano 1889)p几何公理化几何公理化(Hilbert 1899)(Hilbert 1899)2728电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系Lu Chaojun, SJTU 28数学基础危机数学基础危机(2)(2)19001900年国际数学大会年国际数学大会p Poincare:“Poincare:“借助集合

24、论借助集合论可以建造数学大厦可以建造数学大厦今天我们可以宣今天我们可以宣称绝对的严密已经实现了称绝对的严密已经实现了!”!”随后发现了随后发现了CantorCantor集合论中的一些悖论集合论中的一些悖论: :如如19011901年的罗素悖论年的罗素悖论. .弗雷格弗雷格: :当大厦竣工时基础却动摇了当大厦竣工时基础却动摇了. .2829电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与

25、通信工程学院计算机科学系Lu Chaojun, SJTU 29解决危机的四大派别解决危机的四大派别逻辑主义逻辑主义: :主张从逻辑推出数学主张从逻辑推出数学. .p代表人物代表人物RussellRussell形式主义形式主义: :对全部数学进行形式化对全部数学进行形式化, ,并证明其协调性并证明其协调性. .p代表人物代表人物HilbertHilbert直觉主义直觉主义: :反对排中律反对排中律, ,强调构造性强调构造性. .p代表人物代表人物BrouwerBrouwer公理化集合论公理化集合论p代表人物代表人物ZermeloZermelo2930电子科技大学离散数学课程组电子科技大学离散数学

26、课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系Lu Chaojun, SJTU 30罗素罗素Bertrand Arthur William Russell Bertrand Arthur William Russell (1872-1970)(1872-1970)p逻辑主义创始人之一逻辑主义创始人之一p主张从逻辑推出全部数学主张从逻辑推出全部数学. .重要论著重要论著pPrincipia Mathemat

27、icaPrincipia Mathematica,1910,1910n与与WhiteheadWhitehead合著合著nPMPM系统是完备的命题演算和谓词演算系统是完备的命题演算和谓词演算. .n逻辑演算的经典系统逻辑演算的经典系统. .3031电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系Lu Chaojun, SJTU 31希尔伯特希尔伯特David Hi

28、lbert (1862-1943)David Hilbert (1862-1943)p 数理逻辑中形式主义学派数理逻辑中形式主义学派p 证明论创始人之一证明论创始人之一Hilberts program:Hilberts program:将理论至于逻辑演算中加以形式化将理论至于逻辑演算中加以形式化, ,重点研究系重点研究系统中证明的逻辑性质统中证明的逻辑性质, ,希望得出系统的协调性希望得出系统的协调性. .强调证明要使用有穷强调证明要使用有穷方法方法. .3132电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国

29、石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系Lu Chaojun, SJTU 32G Gdeldel不完备性定理不完备性定理G Gdeldel于于19311931年发表的不完备性定理是对年发表的不完备性定理是对Hilberts programHilberts program的致命一击的致命一击. .大意大意: :任何足够强的形式系统都有无法证明的真命任何足够强的形式系统都有无法证明的真命题题. .且系统自己不能证明自己无矛盾且系统自己不能证明自己无矛盾. . 显示了形式化方法的本质局限显

30、示了形式化方法的本质局限. .2020世纪数理逻辑的顶峰世纪数理逻辑的顶峰. .p也有评论说是也有评论说是2020世纪最重要的数学定理世纪最重要的数学定理3233电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系Lu Chaojun, SJTU 33哥德尔哥德尔Kurt GKurt Gdel (1906-1978)del (1906-1978)证明了一阶谓词演算的

31、完备性证明了一阶谓词演算的完备性. .p实现了实现了LeibnizLeibniz梦想梦想. .证明了更加重要的成果证明了更加重要的成果: :不完备性定理不完备性定理. .EinsteinEinstein说说: :自己的工作不再要紧自己的工作不再要紧, ,来研究来研究院只是为了享有和院只是为了享有和G Gdeldel一起步行回家的一起步行回家的特权特权. .3334电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中

32、国石油大学（华东）计算机与通信工程学院计算机科学系34数理逻辑的分支数理逻辑的分支基础的逻辑演算（命题逻辑，谓词逻辑）基础的逻辑演算（命题逻辑，谓词逻辑）公理集合论公理集合论模型论模型论递归论递归论证明论证明论3435电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系Lu Chaojun, SJTU 35公理集合论公理集合论研究公理集合论研究公理集合论, ,是整个

33、数学的基础是整个数学的基础. .CantorCantor的朴素集合论有缺陷的朴素集合论有缺陷p Burali-FortiBurali-Forti悖论悖论, ,罗素悖论罗素悖论,Richard,Richard悖论悖论,Ernst Zermelo:Ernst Zermelo:第一个公理化集合论第一个公理化集合论(1908)(1908)p 经经Fraenkel(1922)Fraenkel(1922)改进成为经典的改进成为经典的ZFZF集合论集合论p 避免了罗素悖论避免了罗素悖论G Gdeldel和和Paul Cohen(1963)Paul Cohen(1963)在在CHCH方面的工作方面的工作p C

34、HCH在在ZFZF系统中不可判定系统中不可判定p CohenCohen的新方法的新方法( (力迫法力迫法) )让人们证明了许多不可判定的问题让人们证明了许多不可判定的问题. .数数学绝不是学绝不是“非真即假非真即假”那么单纯那么单纯! !3536电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系Lu Chaojun, SJTU 36模型论模型论建立形式理论的模型建

35、立形式理论的模型, ,研究模型之间的关系等研究模型之间的关系等. .p模型是对形式理论进行具体解释的一种结构模型是对形式理论进行具体解释的一种结构. .p语法与语义的关系语法与语义的关系Alfred TarskiAlfred Tarski奠定了模型论的基础奠定了模型论的基础3637电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系Lu Chaojun, SJTU

36、37递归论递归论亦称亦称( (能行能行) )可计算性理论可计算性理论, ,研究能行可计算的函数研究能行可计算的函数. .p从递归函数和图灵机的等价产生可计算函数的概念从递归函数和图灵机的等价产生可计算函数的概念代表人物代表人物pG Gdel:del:递归函数递归函数pAlonzo Church(Alonzo Church(丘奇丘奇):): 演算演算pAlan Turing(Alan Turing(图灵图灵):):图灵机图灵机n现代计算机设计思想的创始人之一现代计算机设计思想的创始人之一3738电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机

37、与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系38证明论证明论研究数学理论系统的形式证明问题研究数学理论系统的形式证明问题, ,即以证明为研究即以证明为研究对象对象, ,用数学方法分析之用数学方法分析之. .主要关注系统的协调性主要关注系统的协调性. .代表人物代表人物pHilbert:Hilbert:首先提出首先提出pGerhard Gentzen:Gerhard Gentzen:发展了证明论的重要成果发展了证明论的重要成果. .n证明了算术形式系统的协调性

38、证明了算术形式系统的协调性. .是在系统外证明是在系统外证明, ,且不是有穷主义的且不是有穷主义的. .与与G Gdeldel的结果不矛盾的结果不矛盾. .3839电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系39数理逻辑与计算机科学数理逻辑与计算机科学计算机计算机图灵机图灵机计算机能做什么计算机能做什么, ,算法是什么算法是什么可计算性理论可计算性理论计算机

39、不能做什么计算机不能做什么 算法不可解问题算法不可解问题逻辑程序设计逻辑程序设计(Prolog)(Prolog) 谓词逻辑谓词逻辑程序设计语言的语义学程序设计语言的语义学模型论模型论形式规格说明与程序验证形式规格说明与程序验证模型论模型论AI,AI,知识表示知识表示, ,自动定理证明自动定理证明 逻辑演算逻辑演算从形式证明产生程序从形式证明产生程序 证明论证明论(Gentzen)(Gentzen)3940电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学

40、（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系Lu Chaojun, SJTU 40戴克斯特拉戴克斯特拉Edsger Wybe Dijkstra (1930-2002)Edsger Wybe Dijkstra (1930-2002)p最伟大的计算机科学家最伟大的计算机科学家( (之一之一?)?)p“搞了这么多年软件搞了这么多年软件, ,错误不知犯了多少错误不知犯了多少, ,现在觉悟了现在觉悟了. .我想我想, ,假如我早年在数理逻辑上好好下点功夫的话假如我早年在数理逻辑上好好下点功夫的话, ,我就不会犯这么多的错误我就不会犯这么多的错误, ,不少东

41、西逻辑学家早就说不少东西逻辑学家早就说了了, ,可我不知道可我不知道. .要是我能年轻二十岁的话要是我能年轻二十岁的话, ,就要回去就要回去学逻辑学逻辑.”.”p成就很多成就很多, ,如如DijkstraDijkstra最短路径算法最短路径算法( (见教材见教材11.5)11.5)pEWDEWD手稿手稿: :/users/EWD//users/EWD/4041电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计

42、算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系第一篇第一篇 数理逻辑数理逻辑 逻辑学逻辑学: :研究思维形式及思维规律的科学。研究思维形式及思维规律的科学。逻辑学分为二类：逻辑学分为二类：辩证逻辑辩证逻辑: :是研究事物发展的客观规律。是研究事物发展的客观规律。形式逻辑形式逻辑: :对思维的形式结构和规律进行研究。对思维的形式结构和规律进行研究。数理逻辑数理逻辑：是用数学的方法研究概念、：是用数学的方法研究概念、 判断和推理的科学，属于形式逻辑。判断和推理的科学，属于形式逻辑。 研究推理的方法很多，用数学方法来研究推理研究推理

43、的方法很多，用数学方法来研究推理的规律就称为数理逻辑的规律就称为数理逻辑42电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系第一篇第一篇 数理逻辑数理逻辑 在数理逻辑中，用数学的方法是指引进一套在数理逻辑中，用数学的方法是指引进一套符号体系的方法来研究概念、判断和推理。即对符号体系的方法来研究概念、判断和推理。即对符号进行判断和推理。符号进行判断和推理。数理逻辑

44、分为四大分支：证明论、模型论、递归论数理逻辑分为四大分支：证明论、模型论、递归论和公理集合论。我们这里介绍的是属于四大分支和公理集合论。我们这里介绍的是属于四大分支的共同基础的共同基础古典数理逻辑古典数理逻辑( (命题逻辑和谓词逻命题逻辑和谓词逻辑辑) )。 43电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系第一章第一章 命题逻辑命题逻辑1.1 1.1 命题命

45、题1.2 1.2 命题联结词命题联结词1.3 1.3 命题公式与翻译命题公式与翻译1.4 1.4 真值表与等价式真值表与等价式1.5 1.5 重言式与蕴含式重言式与蕴含式1.6 1.6 其他命题联结词其他命题联结词1.7 1.7 对偶与范式对偶与范式 1.8 1.8 推论理论推论理论44电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系第一章第一章 命题逻辑命题逻

46、辑 教学目的及要求教学目的及要求： 深刻理解和掌握命题逻辑中基本概念和基本方法。深刻理解和掌握命题逻辑中基本概念和基本方法。 教学内容教学内容：命题及表示、联结词、命题公式与翻译、：命题及表示、联结词、命题公式与翻译、真值表与等价公式、重言式与蕴涵式、对偶与范式、真值表与等价公式、重言式与蕴涵式、对偶与范式、推理理论。推理理论。 教学重点教学重点：命题逻辑中的基本概念和基本推理方法。：命题逻辑中的基本概念和基本推理方法。 教学难点教学难点：推理理论。：推理理论。45电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中

47、国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系1.1 1.1 命题命题定义定义： 客观上具有确定真假值的陈述句叫命题。客观上具有确定真假值的陈述句叫命题。 讨论定义：讨论定义： （1 1）命题可以是真的，或者是假的，但不能命题可以是真的，或者是假的，但不能 同时为真又为假。同时为真又为假。 （2 2）命题分类：）命题分类： )原子命题（基本命题、本原命题）：原子命题（基本命题、本原命题）： 不能分解成为更简单的命题。不能分解成为更简单的命题。 例：例：5 5是自然数。是自然数。46电子科

48、技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系1.1 1.1 命题命题 ) )分子命题（复合命题）：若干个原子命题使用分子命题（复合命题）：若干个原子命题使用适当的联结词所组成的新命题适当的联结词所组成的新命题 例：例：2 2是偶数并且是偶数并且2 2也是素数。也是素数。（3 3）命题标识符：命题标识符：用来表示命题的符号。用来表示命题的符号。 常用大写个英文字母常

49、用大写个英文字母 ( (可以带下标可以带下标) )表示命题。表示命题。（4 4）命题中所有的命题中所有的“真真”用用“”( (或或1)1)表示表示， 命题中所有的命题中所有的“假假”用用“”( (或或0)0)表示表示。47电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系1.1 1.1 命题命题例：判断下列语句是否为命题。例：判断下列语句是否为命题。（1 1）十是

50、整数。）十是整数。 （）（）（2 2）上海是一个村庄。（）上海是一个村庄。（）（3 3）火星上有生命存在。）火星上有生命存在。（4 4）加拿大是一个国家。（）加拿大是一个国家。（）（5 5）是偶数而是奇数。（）是偶数而是奇数。（T T）（6 6）20162016年巴西奥运会上中国的金牌数超过美国。年巴西奥运会上中国的金牌数超过美国。（7 7）在十进制中）在十进制中 （）（）（8 8）今天是星期天。）今天是星期天。 （）（）48电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计

51、算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系1.1 1.1 命题命题命令句，感叹句，疑问句均不是命题命令句，感叹句，疑问句均不是命题。 （1 1）把门关上！）把门关上！ （2 2）你到哪里去？）你到哪里去？ 语句既为真，同时又为假的陈述句不是命题，这语句既为真，同时又为假的陈述句不是命题，这样的句子称为样的句子称为“悖论悖论”。 （3 3）日本首相安倍正在说谎。）日本首相安倍正在说谎。 （在命题逻辑中不讨论这类问题）（在命题逻辑中不讨论这类问题）49电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程

52、中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系下列陈述句是否为命题？下列陈述句是否为命题？（1 1）赵本山很帅。）赵本山很帅。（2 2）刘翔是高个子。）刘翔是高个子。（3 3）章子怡很漂亮。）章子怡很漂亮。（4 4）姚明很富有。）姚明很富有。50电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学

53、（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系1.2 1.2 命题联结词命题联结词在命题演算中也有类似的日常生活中的联结词称做：在命题演算中也有类似的日常生活中的联结词称做： “ “命题联结词命题联结词”, ,下面先介绍五个常用的命题联结词。下面先介绍五个常用的命题联结词。否定词否定词：（否定运算、非运算）：（否定运算、非运算） （）符号（）符号 , ,读作读作“非非”，“否定否定” 设命题为，则在的前面加否定词设命题为，则在的前面加否定词 ，变成，变成 ， 读做读做“的否定的否定”或或“非非”51电子科技大学离散数学课程组电子科技大学离散数学课程

54、组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系1.2 1.2 命题联结词命题联结词（）定义（）定义 P P的真值表：的真值表：（）举例：（）举例： ：每一种生物均是动物。：每一种生物均是动物。F F ：有一些有一些生物生物不是不是动物。动物。T T 这里这里 不能讲成不能讲成“每一种生物都不是动物每一种生物都不是动物”。对量化命题的否定，除对动词进行否定外，同时对量对量化命题的否定，除对动词进行否定外，同时对

55、量化词也要加以否定。化词也要加以否定。T TF FF FT T P PP P52电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系1.2 1.2 命题联结词命题联结词合取词合取词（“合取合取”、“积积”、“与与”运算）运算） (1)(1)符号符号“” 设，为两个命题，则设，为两个命题，则称与的合称与的合 取，读作：取，读作：“与与”、“与的合取与的合取”、“并并

56、且且”等。等。 (2)(2)定义（由真值表给出）：定义（由真值表给出）：53电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系1.2 1.2 命题联结词命题联结词T TT TT TT TF FF FF FT TF FF FT TF FF FF FF FF FQPQPP QP QQ QP P的真值表的真值表 ：54电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与

57、通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系1.2 1.2 命题联结词命题联结词当且仅当和的真值均为当且仅当和的真值均为“”，则（，则（） 的真值为的真值为“”。否则，其真值为。否则，其真值为“”。注意：和是互为独立的；地位是平等的，和注意：和是互为独立的；地位是平等的，和的位置可以交换而不会影响的位置可以交换而不会影响的结果。的结果。55电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机

58、科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系1.2 1.2 命题联结词命题联结词(3)(3)举例：举例： (a) P(a) P：王华是党员。：王华是党员。 Q Q：王华是三好学生。：王华是三好学生。 则则：王华是党员并且也是三好学生。：王华是党员并且也是三好学生。 (b)P(b)P：我们去种树：我们去种树 Q Q：房间里有一台电视机：房间里有一台电视机 则则：我们去种树且房间里有一台电视机。：我们去种树且房间里有一台电视机。56电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机

59、与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系1.2 1.2 命题联结词命题联结词 (c) P (c) P：今天下雪：今天下雪 Q Q：3+3=63+3=6 则则：今天下雪和：今天下雪和3+3=63+3=6由例由例(b)(c)(b)(c)可见，在日常生活中，合取词应用在二可见，在日常生活中，合取词应用在二个有关系的命题之间。而在逻辑学中，合取词可个有关系的命题之间。而在逻辑学中，合取词可以用在二个毫不相干的命题之间。以用在二个毫不相干的命题之间。57电子科技大

60、学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系中国石油大学（华东）计算机与通信工程学院计算机科学系1.2 1.2 命题联结词命题联结词 (d)P: (d)P: 王大和王二是亲兄弟。王大和王二是亲兄弟。 Q: Q: 他打开箱子然后拿出一件衣服来。他打开箱子然后拿出一件衣服来。 该语句不是合取联结词组成的命题。该语句不是合取联结词组成的命题。 58电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程中