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

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

1、离散数学数理逻辑数理逻辑集合论集合论图论图论代数代数逻辑学逻辑学:研究推理的科学研究推理的科学早期创始人早期创始人亚里士多德亚里士多德(公元前公元前384322)柏拉图柏拉图(公元前公元前429348),首先把逻辑学的思首先把逻辑学的思想方法引入几何学想方法引入几何学苏格拉底苏格拉底（前（前470前前399年）年）亚里士多德（Aristotole，公元前384-322）亚里士多德有亚里士多德有170多部著作，留传于世的仅多部著作，留传于世的仅47种。他的科学著作构成当时的科学知识百种。他的科学著作构成当时的科学知识百科全书。科全书。世界古代史上最伟大的哲世界古代史上最伟大的哲学家、科学家和教育

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

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

4、演算系统。演算系统。英国英国B.Russell(1872-1970)等从逻辑学的基本法则建等从逻辑学的基本法则建立了自然数理论、实数理论及解析几何学等。立了自然数理论、实数理论及解析几何学等。奥地利奥地利K.Godel(1906-1978)在在1931年提出年提出Godel不完不完全性定理。全性定理。英国英国Alan M.Turing(1912-1954)在在1936年提出一种抽年提出一种抽象计算模型（数学逻辑机），引入图灵机象计算模型（数学逻辑机），引入图灵机一种理一种理想的计算机。想的计算机。数理逻辑的学习数理逻辑的学习“我现在年纪大了，搞了这么多年的我现在年纪大了，搞了这么多年的软件，错

5、误不知犯了多少，现在觉悟软件，错误不知犯了多少，现在觉悟了。我想，假如我早年在数理逻辑上了。我想，假如我早年在数理逻辑上好好下点工夫的话，我就不会犯这么好好下点工夫的话，我就不会犯这么多的错误。不少东西逻辑学家早就说多的错误。不少东西逻辑学家早就说过了，可是我不知道。要是我能年轻过了，可是我不知道。要是我能年轻二十岁的话，我就去学逻辑。二十岁的话，我就去学逻辑。”Edsger.W.Dijkstra 1972年年Turing奖获得者奖获得者 (1930-2002)带权图的最短通路算法A.M.Turing Award2010 LeslieGValiant 2009Thacker,CharlesP2

6、008 BarbaraLisko（女）2007Clarke,EdmundMEmerson,EAllenSifakis,Joseph2006Allen,FrancesE（女）2005Naur,Peter2004Cerf,VintonG.Kahn,RobertE.2003Kay,Alan2002Adleman,LeonardM.Rivest,RonaldL.Shamir,Adi2001Dahl,Ole-JohanNygaard,Kristen2000Yao,AndrewChi-Chih1999Brooks,FrederickP.1998Gray,Jim1997Engelbart,Douglas19

7、96Pnueli,Amir1995Blum,Manuel 1994Feigenbaum,EdwardReddy,Raj1993Hartmanis,JurisStearns,RichardE1992Lampson,ButlerW.1991Milner,AJ1990Corbato,FernandoJ.1989Kahan,William1988Sutherland,Ivan1987Cocke,John1986Hopcroft,JohnETarjan,RobertE1985Karp,RichardM.1984Wirth,NiklausE1983Ritchie,DennisM.Thompson,K。La

8、ne1982Cook,StephenA.1981Codd,EdgarF.1980Hoare,C.AntonyR.1979Iverson,KennethE.1978Floyd,RobertW1977Backus,John1976Rabin,MichaelO.Scott,DanaS1975Newell,AllenSimon,HerbertA.1974Knuth,DonaldE.1973Bachman,CharlesW.1972Dijkstra,E.W.1971McCarthy,John1970Wilkinson,J.H.1969Minsky,Marvin1968Hamming,Richard196

9、7Wilkes,MauriceV1966Perlis,A.J.姚期智DijkstraLeslieValiant,HarvardUniversity Valiantsgreatestsinglecontributionmaybehis1984paperATheoryoftheLearnable,whichlaidthefoundationsofcomputationallearningtheory.Heintroducedageneralframeworkaswellasconcretecomputationalmodelsforstudyingthelearningprocess,includ

10、ingthefamousprobablyapproximatelycorrect(PAC)modelofmachinelearning.Thishasdevelopedintoavibrantresearchareaandhashadenormousinfluenceonmachinelearning,artificialintelligence,andmanyareasofcomputingpractice,suchasnaturallanguageprocessing,handwritingrecognition,andcomputervision.ProfessorofComputerS

11、cienceandAppliedMathematicsSchool of Engineering and Applied Sciences目录（数理逻辑）数理逻辑）第一章第一章 命题演算基础命题演算基础（6学时）学时）第二章第二章 命题演算的推理理论（命题演算的推理理论（4学时）学时）第三章第三章 谓词演算基础（谓词演算基础（5学时）学时）第四章第四章 谓词演算的推理理论（谓词演算的推理理论（5学时）学时）第五章第五章 递归函数论（递归函数论（4学时）学时）第一章第一章 命题演算基础命题演算基础1.11.1 命题和联结词命题和联结词 1.1.1 命题命题 1.1.2 联结词联结词 1.1.3

12、合式公式合式公式1.2 1.2 真假性真假性1.3 1.3 范式及其应用范式及其应用(一一)命题定义命题定义定义定义1：凡是可以判断凡是可以判断真假真假的的陈述句陈述句称为命题。称为命题。命题真值命题真值 真真:用用T(或或1)表示表示假假:用用F(或或0)表示表示命题命题可以判断真假的陈述句可以判断真假的陈述句特征特征陈述句陈述句 真假性真假性:可决定真或假，且真假不可兼可决定真或假，且真假不可兼非经典逻辑非经典逻辑不接受不接受排中律排中律例：下列句子都是命题吗？雪是白的。雪是白的。雪是黑的。雪是黑的。好大的雪啊！好大的雪啊！8大于大于12。1+101=110。例：下列句子都是命题吗？上海世

13、博会开幕时天晴上海世博会开幕时天晴 21世纪末，人类将住在月球世纪末，人类将住在月球 大于大于2的偶数可表示成两个素数之和的偶数可表示成两个素数之和（哥德巴赫猜想）（哥德巴赫猜想）XB 如果如果x大于大于3，则，则x2大于大于9。例：下列句子都是命题吗？8大于大于12吗？吗？请勿吸烟。请勿吸烟。姚明很帅。姚明很帅。南京很美。南京很美。我正在说谎我正在说谎。这种自指谓的语句往往会产这种自指谓的语句往往会产生自相矛盾的结论，即所谓生自相矛盾的结论，即所谓的悖论的悖论具体命题的真假问题在数理逻辑的学习中，在数理逻辑的学习中，不能去纠缠各种具体命题的真假问题不能去纠缠各种具体命题的真假问题，而是将命题

14、当成数学概念来处理，看成一个抽而是将命题当成数学概念来处理，看成一个抽象的形式化的概念，把命题定义成非真必假的象的形式化的概念，把命题定义成非真必假的陈述句陈述句公説公有理婆説婆有理 带联结词的命题 今晚我看书。今晚我看书。今晚我玩网络游戏。今晚我玩网络游戏。今晚我今晚我不不看书。看书。今晚我今晚我不不玩网络游戏。玩网络游戏。今晚我今晚我不不看书，看书，我玩网络游戏。我玩网络游戏。今晚我看书，今晚我看书，或者或者我玩网络游戏。我玩网络游戏。否定并且或者(二)原子命题和复合命题原子命题原子命题不可剖开或分解为更简单命题的不可剖开或分解为更简单命题的命题，也称为简单命题。本书命题，也称为简单命题。

15、本书约定用大写字母表示。约定用大写字母表示。复合命题复合命题由原子命题利用联结词构成的命由原子命题利用联结词构成的命题题复合命题例子复合命题例子下列命题都是复合命题，其中红字为逻辑联结词：下列命题都是复合命题，其中红字为逻辑联结词：（1）雪）雪不不是白的（并非雪是白的）是白的（并非雪是白的）（2）今晚我看书）今晚我看书或者或者去看电影。去看电影。（3）如果如果天气好，天气好，那么那么我去接你。我去接你。（4）偶数）偶数a是质数，是质数，当且仅当当且仅当a=2（a是常数）。是常数）。（5）2是偶数是偶数且且3也是偶数。也是偶数。（6）你去了学校，我去了工厂。）你去了学校，我去了工厂。（省略了逻辑

16、联结词（省略了逻辑联结词“且且”）(三)命题变元定义定义2：如果当：如果当P表示任意命题时，表示任意命题时，P称为命题变元称为命题变元。字母字母P表示表示命题命题具体的、特定的命题，有确定的真值具体的、特定的命题，有确定的真值命题变元命题变元任意命题，没有确定的真值任意命题，没有确定的真值第一章第一章 命题演算基础命题演算基础1.11.1 命题和联结词命题和联结词 1.1.1 命题命题 1.1.2 联结词联结词 1.1.3 合式公式合式公式1.2 1.2 真假性真假性1.3 1.3 范式及其应用范式及其应用五种常用的联结词五种常用的联结词 否定词否定词 合取词合取词 析取词析取词 蕴含词蕴含词

17、 等价词等价词 P，非非P设设P是一个命题。显然，如下这句话也是命题：是一个命题。显然，如下这句话也是命题：“P是不对的是不对的”称之为称之为P的否定。的否定。P PT FF T日常日常语语句中有：句中有：非，非，不，并非，不，并非，真值表真值表否定词的否定词的例子例例 P：上海是中国的城市。：上海是中国的城市。P：上海不是中国的城市。：上海不是中国的城市。例例 P：雪是黑色的。：雪是黑色的。P：雪不是黑色的。：雪不是黑色的。否定联结词使用的原则将真命题变成假命题，将假命题变成真命题。但这将真命题变成假命题，将假命题变成真命题。但这并不是简单的随意加个不字就能完成的。并不是简单的随意加个不字就

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

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

20、：今天下雨。P Q：今天刮风或者今天下雨。：今天刮风或者今天下雨。可兼的可兼的“或或”PQP QTTTTFTFTTFFF他会英语或法语。他会英语或法语。今天刮风或者今天下雨。今天刮风或者今天下雨。不可兼的不可兼的“或或”PQP Q(P Q)(P Q)TTTFTFTTFTTTFFFF人固有一死，或重于泰山，或轻于鸿毛。人固有一死，或重于泰山，或轻于鸿毛。今天晚上我去看电影，或去看球赛。今天晚上我去看电影，或去看球赛。异或异或XORPQ,P蕴含蕴含Q设设P,Q是两个命题。显然，如下这句话也是命题：是两个命题。显然，如下这句话也是命题：“如果如果P则则Q”称之为称之为P蕴含蕴含Q。日常语言中有：日常

21、语言中有：如果如果则则,只要只要就就，P Q P QT T TT F FF T TF F T蕴含词的例子 P：236 Q：(23)+1=6+2 PQ:如果如果236，则（，则（23）16+2 P:天气不好天气不好 Q：我去接你：我去接你 PQ:如果天气不好，那么我去接你。如果天气不好，那么我去接你。注1.前件为假时，命题为真前件为假时，命题为真如果蕴含前件如果蕴含前件P是假命题，那么不管是假命题，那么不管Q是什么命是什么命题，命题题，命题 “如果如果P则则Q”在逻辑中都被认为是真命题。在逻辑中都被认为是真命题。例：例：如果张三能及格，那太阳从西边升起。如果张三能及格，那太阳从西边升起。注2.前

22、件、后件可以毫不相关前件、后件可以毫不相关在日常语言中在日常语言中“如果如果则则”所联结的句子之所联结的句子之间表现的是一种因果关系，但在数理逻辑中，间表现的是一种因果关系，但在数理逻辑中，尽管说前件蕴涵后件，但两个命题可以是毫不尽管说前件蕴涵后件，但两个命题可以是毫不相关的。相关的。例：例：P：235 Q：雪是黑色的：雪是黑色的 PQ：如果：如果235，则雪是黑色的，则雪是黑色的注3.充分条件、必要条件pq为真命题的逻辑关系是：为真命题的逻辑关系是：p是是q的的充分充分条件，条件，q是是p的的必要必要条件。条件。“q是是p的必要条件的必要条件”的叙述方式还有：的叙述方式还有：p仅当仅当q（仅

23、当（仅当q，则，则p）只有只有q才才p 只要只要p就就q 除非除非q，否则非，否则非p（非（非p，除非，除非q）蕴含词的例子用用表示下列命题：表示下列命题：（1）只要天下雨，我就回家。）只要天下雨，我就回家。（2）只有天下雨，我才回家。）只有天下雨，我才回家。（3）除非天下雨，否则我不回家。）除非天下雨，否则我不回家。（4）仅当天下雨，我才回家。）仅当天下雨，我才回家。解解 设设p：天下雨。：天下雨。q：我回家。：我回家。则（则（1）符号化为）符号化为 pq。（2）符号化为）符号化为 qp，或：或：pq （3）符号化为）符号化为 qp，或：或：pq （4）符号化为）符号化为 qp，或：或：pq

24、PQ，P等价于等价于Q设设P，Q是两个命题。显然，如下这句话也是命题：是两个命题。显然，如下这句话也是命题：“P当且仅当当且仅当Q”称之为称之为P等价于等价于Q。P Q P QT T TT F FF T FF F T日常语言中有：日常语言中有：当且仅当，当且仅当，等价词的例子 P:224 Q：雪是白色的。：雪是白色的。P Q：224当且仅当雪是白色的。当且仅当雪是白色的。P:225 Q：雪是黑色的。：雪是黑色的。P Q：225当且仅当雪是黑色。当且仅当雪是黑色。等价词的例子三角形三角形ABC为等腰三角形为等腰三角形当且仅当当且仅当三角形三角形ABC有两条边相等。有两条边相等。ABC非复合命题的

25、例子非复合命题的例子（1）Tom和和John是兄弟。是兄弟。（2）如果）如果x0，则则 x20。（3）如果两个三角形全等，则它们的面积相等。）如果两个三角形全等，则它们的面积相等。（4）一个三角形为等腰三角形当且仅当三角形有两条）一个三角形为等腰三角形当且仅当三角形有两条边相等。边相等。未指定未指定注4.充要条件p q为真命题的逻辑关系是：为真命题的逻辑关系是：p是是q的的充分充分条件，条件，p是是q的的必要必要条件。条件。中学数学选修2-1：四种命题中学数学选修2-1：充分、必要真值函项定义：以真假为定义域并以真假为值域的函数定义：以真假为定义域并以真假为值域的函数称为称为真值函项真值函项。

26、需要集合与映射的知识才能够讲透!T,FT,FT,F(T,T),(T,F),(F,T),(F,F)一元联结词的真值表一元联结词有一个命题变项一元联结词有一个命题变项P，它取真和假两种，可，它取真和假两种，可定义四个不同的一元联结词定义四个不同的一元联结词f0，f1，f2，f3，或称为真，或称为真值函项。值函项。其真假关系可用下图表示：其真假关系可用下图表示：P f0(P)f1(P)f2(P)f3(P)T T T F FF T F T F永真恒等否定否定 P永假f1为与非：PQ=（PQ）f7为异或：PQ=（PQ）f14为或非：PQ=（PQ）二元联结词P Q f0f1f2f3f4f5f6f7f8f9

27、f10f11f12f13f14f15T T T F T T T F F F 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为合取三元联结词共有多少个？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第一章第一章 命题演算基

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

29、串才是公式，否则不为公式。n元公式若公式若公式 中有中有n n个不同的命题变元，个不同的命题变元，就说就说 为为n n 元公式。元公式。例例一个一个3元公式：元公式：（P Q）R）（P Q）命题符号化将复合命题符号化的步骤是将复合命题符号化的步骤是分析出简单命题，符号化分析出简单命题，符号化用联结词联结简单命题用联结词联结简单命题提示：根据命题的实际含义，不拘泥于原句形式地确提示：根据命题的实际含义，不拘泥于原句形式地确定原子命题和选用联结词。定原子命题和选用联结词。例1(p5)将下列各命题符号化将下列各命题符号化:只有努力学习、认真复习，才能取得好成绩。只有努力学习、认真复习，才能取得好成绩

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

31、兼 或或 例将下列语句形式化，并表示为命题公式：将下列语句形式化，并表示为命题公式：（1）狗急跳墙。）狗急跳墙。令令 p：狗急了，：狗急了，q：狗跳墙。：狗跳墙。则可表示为则可表示为 pq例将下列语句形式化，并表示为命题公式：将下列语句形式化，并表示为命题公式：（2）如果他不来，）如果他不来，那么他或者是生病了，或者是不在本地。那么他或者是生病了，或者是不在本地。记记 p：他来，：他来，q：他生病，：他生病，r：他在本地。：他在本地。则可表示为则可表示为 p(q r)例将下列语句形式化，并表示为命题公式：将下列语句形式化，并表示为命题公式：（3）如果你和他不都是傻子，）如果你和他不都是傻子，那么你们俩都不会去自讨没趣。那么你们俩都不会去自讨没趣。令令 p：你是傻子，：你是傻子，q：他是傻子，：他是傻子，r：你会去自讨没趣，：你会去自讨没趣，s：他会去自讨没趣。：他会去自讨没趣。则则 可表示为可表示为 (p q)(r s)(p q)(r s)?第一章第一章 命题演算基础命题演算基础1.11.1 命题和联结词命题和联结词 1.1.1 命题命题 1.1.2 联结词联结词 1.1.3 合式公式合式公式 1.2 1.2 真假性真假性1.3 1.3 范式及其应用范式及其应用