离散数学第一章命题演算基础命题和联结词精.ppt

《离散数学第一章命题演算基础命题和联结词精.ppt》由会员分享，可在线阅读，更多相关《离散数学第一章命题演算基础命题和联结词精.ppt（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学第一章命题演算基础命题和联结词第1页，本讲稿共60页逻辑学逻辑学:研究推理的科学研究推理的科学早期创始人早期创始人亚里士多德亚里士多德(公元前公元前384322)柏拉图柏拉图(公元前公元前429348),首先把逻辑学的思首先把逻辑学的思想方法引入几何学想方法引入几何学苏格拉底苏格拉底（前（前470前前399年）年）第2页，本讲稿共60页亚里士多德（Aristotole，公元前384-322）亚里士多德有亚里士多德有170多部著作，留传于世的仅多部著作，留传于世的仅47种。他的科学著作构成当时的科学知识百种。他的科学著作构成当时的科学知识百科全书。科全书。世界古代史上最伟大的哲学家、世界

2、古代史上最伟大的哲学家、科学家和教育家。他创立了科学家和教育家。他创立了形形式逻辑式逻辑学，丰富和发展了哲学学，丰富和发展了哲学的各个分支学科。的各个分支学科。第3页，本讲稿共60页孔子（前孔子（前551-479）中国春秋末期伟大的中国春秋末期伟大的思想家和教育家，儒思想家和教育家，儒家学派的创始人。家学派的创始人。孔子被尊为圣人，无孔子被尊为圣人，无法超越，后代的人们法超越，后代的人们只有沿袭与膜拜。只有沿袭与膜拜。学而不思则罔思而不学则殆 第4页，本讲稿共60页数理逻辑数理逻辑数学化的逻辑学数学化的逻辑学在在17世纪莱布尼兹（世纪莱布尼兹（Leibniz）已经提出仿数学）已经提出仿数学的方

3、法发展逻辑的思想。的方法发展逻辑的思想。1930年，年，Godel完全性定理完全性定理的证明完善了数理的证明完善了数理逻辑基础，建立了逻辑演算，成为现代科学特逻辑基础，建立了逻辑演算，成为现代科学特别是计算机科学不可缺少的基础理论之一。别是计算机科学不可缺少的基础理论之一。第5页，本讲稿共60页数理逻辑发展史中的代表人物德国德国G.W.Leibniz(1626-1716)把数学引入形式逻辑，明确提把数学引入形式逻辑，明确提出用数学方法研究推理。出用数学方法研究推理。英国英国G.Boole(1815-1864)等创立了逻辑代数，等创立了逻辑代数，1847年年Boole实现了命题演算。实现了命题演

4、算。德国德国G.Frege(1848-1925)在在1879年建立了第一个谓词演算年建立了第一个谓词演算系统。系统。英国英国B.Russell(1872-1970)等从逻辑学的基本法则建立等从逻辑学的基本法则建立了自然数理论、实数理论及解析几何学等。了自然数理论、实数理论及解析几何学等。奥地利奥地利K.Godel(1906-1978)在在1931年提出年提出Godel不完全性定不完全性定理。理。英国英国Alan M.Turing(1912-1954)在在1936年提出一种抽象计算年提出一种抽象计算模型（数学逻辑机），引入图灵机模型（数学逻辑机），引入图灵机一种理想的计算机。一种理想的计算机。第

5、6页，本讲稿共60页数理逻辑的学习数理逻辑的学习“我现在年纪大了，搞了这么多年的软件，我现在年纪大了，搞了这么多年的软件，错误不知犯了多少，现在觉悟了。我想，错误不知犯了多少，现在觉悟了。我想，假如我早年在数理逻辑上好好下点工夫假如我早年在数理逻辑上好好下点工夫的话，我就不会犯这么多的错误。不少的话，我就不会犯这么多的错误。不少东西逻辑学家早就说过了，可是我不知东西逻辑学家早就说过了，可是我不知道。要是我能年轻二十岁的话，我就去道。要是我能年轻二十岁的话，我就去学逻辑。学逻辑。”Edsger.W.Dijkstra 1972年年Turing奖获得者奖获得者 (1930-2002)带权图的最短通路

6、算法第7页，本讲稿共60页A.M.Turing Award2010 LeslieGValiant 2009Thacker,CharlesP2008 BarbaraLisko（女）2007Clarke,EdmundMEmerson,EAllenSifakis,Joseph2006Allen,FrancesE（女）2005Naur,Peter2004Cerf,VintonG.Kahn,RobertE.2003Kay,Alan2002Adleman,LeonardM.Rivest,RonaldL.Shamir,Adi2001Dahl,Ole-JohanNygaard,Kristen2000Yao,A

7、ndrewChi-Chih1999Brooks,FrederickP.1998Gray,Jim1997Engelbart,Douglas1996Pnueli,Amir1995Blum,Manuel 1994Feigenbaum,EdwardReddy,Raj1993Hartmanis,JurisStearns,RichardE1992Lampson,ButlerW.1991Milner,AJ1990Corbato,FernandoJ.1989Kahan,William1988Sutherland,Ivan1987Cocke,John1986Hopcroft,JohnETarjan,Robert

8、E1985Karp,RichardM.1984Wirth,NiklausE1983Ritchie,DennisM.Thompson,K。Lane1982Cook,StephenA.1981Codd,EdgarF.1980Hoare,C.AntonyR.1979Iverson,KennethE.1978Floyd,RobertW1977Backus,John1976Rabin,MichaelO.Scott,DanaS1975Newell,AllenSimon,HerbertA.1974Knuth,DonaldE.1973Bachman,CharlesW.1972Dijkstra,E.W.1971

9、McCarthy,John1970Wilkinson,J.H.1969Minsky,Marvin1968Hamming,Richard1967Wilkes,MauriceV1966Perlis,A.J.姚期智Dijkstra第8页，本讲稿共60页LeslieValiant,HarvardUniversity Valiantsgreatestsinglecontributionmaybehis1984paperATheoryoftheLearnable,whichlaidthefoundationsofcomputationallearningtheory.Heintroducedagenera

10、lframeworkaswellasconcretecomputationalmodelsforstudyingthelearningprocess,includingthefamousprobablyapproximatelycorrect(PAC)modelofmachinelearning.Thishasdevelopedintoavibrantresearchareaandhashadenormousinfluenceonmachinelearning,artificialintelligence,andmanyareasofcomputingpractice,suchasnatura

11、llanguageprocessing,handwritingrecognition,andcomputervision.ProfessorofComputerScienceandAppliedMathematicsSchool of Engineering and Applied Sciences第9页，本讲稿共60页目录（数理逻辑）数理逻辑）第一章第一章 命题演算基础命题演算基础（6学时）学时）第二章第二章 命题演算的推理理论（命题演算的推理理论（4学时）学时）第三章第三章 谓词演算基础（谓词演算基础（5学时）学时）第四章第四章 谓词演算的推理理论（谓词演算的推理理论（5学时）学时）第五章

12、第五章 递归函数论（递归函数论（4学时）学时）第10页，本讲稿共60页第一章第一章 命题演算基础命题演算基础1.1 1.1 命题和联结词命题和联结词 1.1.1 命题命题 1.1.2 联结词联结词 1.1.3 合式公式合式公式1.2 1.2 真假性真假性1.3 1.3 范式及其应用范式及其应用第11页，本讲稿共60页(一一)命题定义命题定义定义定义1：凡是可以判断凡是可以判断真假真假的的陈述句陈述句称为命题。称为命题。命题真值命题真值 真真:用用T(或或1)表示表示假假:用用F(或或0)表示表示第12页，本讲稿共60页命题命题可以判断真假的陈述句可以判断真假的陈述句特征特征陈述句陈述句 真假性

13、真假性:可决定真或假，且真假不可兼可决定真或假，且真假不可兼非经典逻辑非经典逻辑不接受不接受排中律排中律第13页，本讲稿共60页例：下列句子都是命题吗？雪是白的。雪是白的。雪是黑的。雪是黑的。好大的雪啊！好大的雪啊！8大于大于12。1+101=110。第14页，本讲稿共60页例：下列句子都是命题吗？上海世博会开幕时天晴上海世博会开幕时天晴 21世纪末，人类将住在月球世纪末，人类将住在月球 大于大于2的偶数可表示成两个素数之和的偶数可表示成两个素数之和（哥德巴赫猜想）（哥德巴赫猜想）XB 如果如果x大于大于3，则，则x2大于大于9。第15页，本讲稿共60页例：下列句子都是命题吗？8大于大于12吗

14、？吗？请勿吸烟。请勿吸烟。姚明很帅。姚明很帅。南京很美。南京很美。我正在说谎我正在说谎。这种自指谓的语句往往会产生自这种自指谓的语句往往会产生自相矛盾的结论，即所谓的悖论相矛盾的结论，即所谓的悖论第16页，本讲稿共60页具体命题的真假问题在数理逻辑的学习中，在数理逻辑的学习中，不能去纠缠各种具体命题的真假问题不能去纠缠各种具体命题的真假问题，而是将命题当成数学概念来处理，看成一个抽而是将命题当成数学概念来处理，看成一个抽象的形式化的概念，把命题定义成非真必假的象的形式化的概念，把命题定义成非真必假的陈述句陈述句公説公有理婆説婆有理 第17页，本讲稿共60页带联结词的命题 今晚我看书。今晚我看书

15、。今晚我玩网络游戏。今晚我玩网络游戏。今晚我今晚我不不看书。看书。今晚我今晚我不不玩网络游戏。玩网络游戏。今晚我今晚我不不看书，看书，我玩网络游戏。我玩网络游戏。今晚我看书，今晚我看书，或者或者我玩网络游戏。我玩网络游戏。否定并且或者第18页，本讲稿共60页(二)原子命题和复合命题原子命题原子命题不可剖开或分解为更简单命题的不可剖开或分解为更简单命题的命题，也称为简单命题。本书命题，也称为简单命题。本书约定用大写字母表示。约定用大写字母表示。复合命题复合命题由原子命题利用联结词构成的命由原子命题利用联结词构成的命题题第19页，本讲稿共60页复合命题例子复合命题例子下列命题都是复合命题，其中红字

16、为逻辑联结词：下列命题都是复合命题，其中红字为逻辑联结词：（1）雪）雪不不是白的（并非雪是白的）是白的（并非雪是白的）（2）今晚我看书）今晚我看书或者或者去看电影。去看电影。（3）如果如果天气好，天气好，那么那么我去接你。我去接你。（4）偶数）偶数a是质数，是质数，当且仅当当且仅当a=2（a是常数）。是常数）。（5）2是偶数是偶数且且3也是偶数。也是偶数。（6）你去了学校，我去了工厂。）你去了学校，我去了工厂。（省略了逻辑联结词（省略了逻辑联结词“且且”）第20页，本讲稿共60页(三)命题变元定义定义2：如果当：如果当P表示任意命题时，表示任意命题时，P称为命题变元称为命题变元。字母字母P表示

17、表示命题命题具体的、特定的命题，有确定的真值具体的、特定的命题，有确定的真值命题变元命题变元任意命题，没有确定的真值任意命题，没有确定的真值第21页，本讲稿共60页第一章第一章 命题演算基础命题演算基础1.1 1.1 命题和联结词命题和联结词 1.1.1 命题命题 1.1.2 联结词联结词 1.1.3 合式公式合式公式1.2 1.2 真假性真假性1.3 1.3 范式及其应用范式及其应用第22页，本讲稿共60页五种常用的联结词五种常用的联结词 否定词否定词 合取词合取词 析取词析取词 蕴含词蕴含词 等价词等价词 第23页，本讲稿共60页P，非非P设设P是一个命题。显然，如下这句话也是命题：是一个

18、命题。显然，如下这句话也是命题：“P是不对的是不对的”称之为称之为P的否定。的否定。P PT FF T日常日常语语句中有：句中有：非，非，不，并非，不，并非，真值表真值表第24页，本讲稿共60页否定词的否定词的例子例例 P：上海是中国的城市。：上海是中国的城市。P：上海不是中国的城市。：上海不是中国的城市。例例 P：雪是黑色的。：雪是黑色的。P：雪不是黑色的。：雪不是黑色的。第25页，本讲稿共60页否定联结词使用的原则将真命题变成假命题，将假命题变成真命题。但这并将真命题变成假命题，将假命题变成真命题。但这并不是简单的随意加个不字就能完成的。不是简单的随意加个不字就能完成的。例例P:这些都是学

19、生。这些都是学生。P：这些不都是学生：这些不都是学生这些都不是学生这些都不是学生第26页，本讲稿共60页阿契贝难题阿契贝难题例例下述两命题都是真命题：下述两命题都是真命题：A:“本句是六字句本句是六字句”B:“本句本句不不是六字句是六字句”看似矛盾的根本原因，在于两个命题的前提条件是否统一看似矛盾的根本原因，在于两个命题的前提条件是否统一的问题。的问题。第27页，本讲稿共60页P Q，P合取合取Q设设P，Q是两个命题。显然，如下这句话也是命题：是两个命题。显然，如下这句话也是命题：“P并且并且Q”称之为称之为P和和Q的的合取合取。P Q P QT T TT F FF T FF F F日常语句中

20、有：日常语句中有：且，与，且，与，第28页，本讲稿共60页合取词的例子 P:225 Q：雪是白的。：雪是白的。P Q：225并且雪是白的。并且雪是白的。lP:今天刮风。今天刮风。Q：今天下雨。：今天下雨。P Q：今天刮风并且今天下雨。：今天刮风并且今天下雨。第29页，本讲稿共60页P Q，P析取析取Q设设P,Q是两个命题。显然，如下这句话也是命题：是两个命题。显然，如下这句话也是命题：“P或者或者Q”称之为称之为P和和Q的析取。的析取。P Q P QT T TT F TF T TF F F日常语言中有：日常语言中有：或，或，第30页，本讲稿共60页析取词的例子 P:225 Q：雪是白的。：雪是

21、白的。P Q：225或者雪是白的。或者雪是白的。lP:今天刮风。今天刮风。Q：今天下雨。：今天下雨。P Q：今天刮风或者今天下雨。：今天刮风或者今天下雨。第31页，本讲稿共60页可兼的可兼的“或或”PQP QTTTTFTFTTFFF他会英语或法语。他会英语或法语。今天刮风或者今天下雨。今天刮风或者今天下雨。第32页，本讲稿共60页不可兼的不可兼的“或或”PQP Q(P Q)(P Q)TTTFTFTTFTTTFFFF人固有一死，或重于泰山，或轻于鸿毛。人固有一死，或重于泰山，或轻于鸿毛。今天晚上我去看电影，或去看球赛。今天晚上我去看电影，或去看球赛。异或异或XOR第33页，本讲稿共60页PQ,P

22、蕴含蕴含Q设设P,Q是两个命题。显然，如下这句话也是命题：是两个命题。显然，如下这句话也是命题：“如果如果P则则Q”称之为称之为P蕴含蕴含Q。日常语言中有：日常语言中有：如果如果则则,只要只要就就，P Q P QT T TT F FF T TF F T第34页，本讲稿共60页蕴含词的例子 P：236 Q：(23)+1=6+2 PQ:如果如果236，则（，则（23）16+2 P:天气不好天气不好 Q：我去接你：我去接你 PQ:如果天气不好，那么我去接你。如果天气不好，那么我去接你。第35页，本讲稿共60页注1.前件为假时，命题为真前件为假时，命题为真如果蕴含前件如果蕴含前件P是假命题，那么不管是

23、假命题，那么不管Q是什么命是什么命题，命题题，命题 “如果如果P则则Q”在逻辑中都被认为是真命题。在逻辑中都被认为是真命题。例：例：如果张三能及格，那太阳从西边升起。如果张三能及格，那太阳从西边升起。第36页，本讲稿共60页注2.前件、后件可以毫不相关前件、后件可以毫不相关在日常语言中在日常语言中“如果如果则则”所联结的句子之所联结的句子之间表现的是一种因果关系，但在数理逻辑中，间表现的是一种因果关系，但在数理逻辑中，尽管说前件蕴涵后件，但两个命题可以是毫不尽管说前件蕴涵后件，但两个命题可以是毫不相关的。相关的。例：例：P：235 Q：雪是黑色的：雪是黑色的 PQ：如果：如果235，则雪是黑色

24、的，则雪是黑色的第37页，本讲稿共60页注3.充分条件、必要条件pq为真命题的逻辑关系是：为真命题的逻辑关系是：p是是q的的充分充分条件，条件，q是是p的的必要必要条件。条件。“q是是p的必要条件的必要条件”的叙述方式还有：的叙述方式还有：p仅当仅当q（仅当（仅当q，则，则p）只有只有q才才p 只要只要p就就q 除非除非q，否则非，否则非p（非（非p，除非，除非q）第38页，本讲稿共60页蕴含词的例子用用表示下列命题：表示下列命题：（1）只要天下雨，我就回家。）只要天下雨，我就回家。（2）只有天下雨，我才回家。）只有天下雨，我才回家。（3）除非天下雨，否则我不回家。）除非天下雨，否则我不回家。

25、（4）仅当天下雨，我才回家。）仅当天下雨，我才回家。解解 设设p：天下雨。：天下雨。q：我回家。：我回家。则（则（1）符号化为）符号化为 pq。（2）符号化为）符号化为 qp，或：或：pq （3）符号化为）符号化为 qp，或：或：pq （4）符号化为）符号化为 qp，或：或：pq第39页，本讲稿共60页PQ，P等价于等价于Q设设P，Q是两个命题。显然，如下这句话也是命题：是两个命题。显然，如下这句话也是命题：“P当且仅当当且仅当Q”称之为称之为P等价于等价于Q。P Q P QT T TT F FF T FF F T日常语言中有：日常语言中有：当且仅当，当且仅当，第40页，本讲稿共60页等价词的

26、例子 P:224 Q：雪是白色的。：雪是白色的。P Q：224当且仅当雪是白色的。当且仅当雪是白色的。P:225 Q：雪是黑色的。：雪是黑色的。P Q：225当且仅当雪是黑色。当且仅当雪是黑色。第41页，本讲稿共60页等价词的例子三角形三角形 ABC为等腰三角形为等腰三角形当且仅当当且仅当三角形三角形 ABC有两条边相等。有两条边相等。ABC第42页，本讲稿共60页非复合命题的例子非复合命题的例子（1）Tom和和John是兄弟。是兄弟。（2）如果）如果x0，则则 x20。（3）如果两个三角形全等，则它们的面积相等。）如果两个三角形全等，则它们的面积相等。（4）一个三角形为等腰三角形当且仅当三角

27、形有两条边相）一个三角形为等腰三角形当且仅当三角形有两条边相等。等。未指定未指定第43页，本讲稿共60页注4.充要条件p q为真命题的逻辑关系是：为真命题的逻辑关系是：p是是q的的充分充分条件，条件，p是是q的的必要必要条件。条件。第44页，本讲稿共60页中学数学选修2-1：四种命题第45页，本讲稿共60页中学数学选修2-1：充分、必要第46页，本讲稿共60页真值函项定义：以真假为定义域并以真假为值域的函数定义：以真假为定义域并以真假为值域的函数称为称为真值函项真值函项。需要集合与映射的知识才能够讲透!T,FT,FT,F(T,T),(T,F),(F,T),(F,F)第47页，本讲稿共60页一元

28、联结词的真值表一元联结词有一个命题变项一元联结词有一个命题变项P，它取真和假两种，可定义，它取真和假两种，可定义四个不同的一元联结词四个不同的一元联结词f0，f1，f2，f3，或称为真值函项。，或称为真值函项。其真假关系可用下图表示：其真假关系可用下图表示：P f0(P)f1(P)f2(P)f3(P)T T T F FF T F T F永真恒等否定否定 P永假第48页，本讲稿共60页f1为与非：PQ=（PQ）f7为异或：PQ=（PQ）f14为或非：PQ=（PQ）二元联结词P Q f0f1f2f3f4f5f6f7f8f9f10f11f12f13f14f15T T T F T T T F F F

29、T T T T F F F FT F T T F T T F T T F F T F T F F FF T T T T F T T F T F T F F F T F FF F T T T T F T T F T F F F F F T Ff2为蕴含f4为析取f8为等价f11为合取第49页，本讲稿共60页三元联结词共有多少个？28f0f1f2f?(0,0,0)0101(0,0,1)0011(0,1,0)0001(0,1,1)0001(1,0,0)0001(1,0,1)0001(1,1,0)0001(1,1,1)0001第50页，本讲稿共60页第一章第一章 命题演算基础命题演算基础1.1 1.1

30、 命题和联结词命题和联结词 1.1.1 命题命题 1.1.2 联结词联结词 1.1.3 合式公式合式公式 1.2 1.2 真假性真假性1.3 1.3 范式及其应用范式及其应用第51页，本讲稿共60页合式公式(Well formed formulae)合式公式为如下定义的式子，简称为公式：合式公式为如下定义的式子，简称为公式：任何命题变元均是公式；任何命题变元均是公式；如果如果P为公式，则为公式，则 P为公式；为公式；如果为如果为P，Q为公式，则为公式，则 P Q,P Q,PQ,PQ 为公式；为公式；当且仅当经过有限次使用当且仅当经过有限次使用、所组成所组成的符号串才是公式，否则不为公式的符号串

31、才是公式，否则不为公式。第52页，本讲稿共60页n元公式若公式若公式 中有中有n n个不同的命题变元，个不同的命题变元，就说就说 为为n n 元公式。元公式。例例一个一个3元公式：元公式：（P Q）R）（P Q）第53页，本讲稿共60页命题符号化将复合命题符号化的步骤是将复合命题符号化的步骤是分析出简单命题，符号化分析出简单命题，符号化用联结词联结简单命题用联结词联结简单命题提示：根据命题的实际含义，不拘泥于原句形式地确定原子命提示：根据命题的实际含义，不拘泥于原句形式地确定原子命题和选用联结词。题和选用联结词。第54页，本讲稿共60页例1(p5)将下列各命题符号化将下列各命题符号化:只有努力

32、学习、认真复习，才能取得好成绩。只有努力学习、认真复习，才能取得好成绩。解：令解：令P表示表示“努力学习努力学习”；Q表示表示“认真复习认真复习”；R表示表示“取得好成绩取得好成绩”。则原句译为则原句译为 R（P Q）该语句能不能译为（该语句能不能译为（P Q）R？第55页，本讲稿共60页例4(p5)已知三个命题：已知三个命题：P：今晚我在家上网；：今晚我在家上网；Q：今晚我去球场看足球比赛；：今晚我去球场看足球比赛；R：今晚我在家上网或去球场看足球比赛。：今晚我在家上网或去球场看足球比赛。试问试问P Q和和R是否表达同一命题？是否表达同一命题？请用真值表说明之。请用真值表说明之。R=(P Q

33、)(PQ)P Q PQ R T T T F T F T T F T T T F F F F不可兼 或或 第56页，本讲稿共60页例将下列语句形式化，并表示为命题公式：将下列语句形式化，并表示为命题公式：（1）狗急跳墙。）狗急跳墙。令令 p：狗急了，：狗急了，q：狗跳墙。：狗跳墙。则可表示为则可表示为 pq第57页，本讲稿共60页例将下列语句形式化，并表示为命题公式：将下列语句形式化，并表示为命题公式：（2）如果他不来，）如果他不来，那么他或者是生病了，或者是不在本地。那么他或者是生病了，或者是不在本地。记记 p：他来，：他来，q：他生病，：他生病，r：他在本地。：他在本地。则可表示为则可表示为

34、 p(q r)第58页，本讲稿共60页例将下列语句形式化，并表示为命题公式：将下列语句形式化，并表示为命题公式：（3）如果你和他不都是傻子，）如果你和他不都是傻子，那么你们俩都不会去自讨没趣。那么你们俩都不会去自讨没趣。令令 p：你是傻子，：你是傻子，q：他是傻子，：他是傻子，r：你会去自讨没趣，：你会去自讨没趣，s：他会去自讨没趣。：他会去自讨没趣。则则 可表示为可表示为 (p q)(r s)(p q)(r s)?第59页，本讲稿共60页第一章第一章 命题演算基础命题演算基础1.1 1.1 命题和联结词命题和联结词 1.1.1 命题命题 1.1.2 联结词联结词 1.1.3 合式公式合式公式 1.2 1.2 真假性真假性1.3 1.3 范式及其应用范式及其应用第60页，本讲稿共60页