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

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

2、，11点11分，星期五孔子（前551-479）中国春秋末期伟大的思想家和教育家，儒家学派的创始人。孔子被尊为圣人，无法超越，后代的人们只有沿袭与膜拜。学而不思则罔思而不学则殆 第4页，共60页，2022年，5月20日，11点11分，星期五数理逻辑数学化的逻辑学在17世纪莱布尼兹（Leibniz）已经提出仿数学的方法发展逻辑的思想。1930年，Godel完全性定理的证明完善了数理逻辑基础，建立了逻辑演算，成为现代科学特别是计算机科学不可缺少的基础理论之一。第5页，共60页，2022年，5月20日，11点11分，星期五数理逻辑发展史中的代表人物德国G.W. Leibniz (1626-1716)把

3、数学引入形式逻辑，明确提出用数学方法研究推理。英国G. Boole (1815-1864)等创立了逻辑代数，1847年Boole实现了命题演算。德国G. Frege (1848-1925)在1879年建立了第一个谓词演算系统。英国B. Russell (1872-1970)等从逻辑学的基本法则建立了自然数理论、实数理论及解析几何学等。奥地利K. Godel (1906-1978)在1931年提出Godel不完全性定理。英国Alan M. Turing (1912-1954)在1936年提出一种抽象计算模型（数学逻辑机），引入图灵机一种理想的计算机。第6页，共60页，2022年，5月20日，11

4、点11分，星期五数理逻辑的学习“我现在年纪大了，搞了这么多年的软件，错误不知犯了多少，现在觉悟了。我想，假如我早年在数理逻辑上好好下点工夫的话，我就不会犯这么多的错误。不少东西逻辑学家早就说过了，可是我不知道。要是我能年轻二十岁的话，我就去学逻辑。” Edsger. W. Dijkstra 1972年Turing奖获得者 (1930-2002)带权图的最短通路算法第7页，共60页，2022年，5月20日，11点11分，星期五A. M. Turing Award 2010 LeslieGValiant 2009 Thacker,CharlesP2008 Barbara Lisko（女）2007

5、Clarke,EdmundM Emerson,EAllen Sifakis,Joseph2006 Allen,FrancesE（女）2005 Naur,Peter2004 Cerf,VintonG. Kahn,RobertE.2003 Kay,Alan2002 Adleman,LeonardM. Rivest,RonaldL. Shamir,Adi2001 Dahl,Ole-Johan Nygaard,Kristen2000 Yao,AndrewChi-Chih1999 Brooks,FrederickP.1998 Gray,Jim1997 Engelbart,Douglas1996 Pnue

6、li,Amir1995 Blum,Manuel 1994 Feigenbaum,Edward Reddy,Raj1993 Hartmanis,Juris Stearns,RichardE1992 Lampson,ButlerW.1991 Milner,AJ1990 Corbato,FernandoJ.1989 Kahan,William1988 Sutherland,Ivan1987 Cocke,John1986 Hopcroft,JohnE Tarjan,RobertE1985 Karp,RichardM.1984 Wirth,NiklausE1983 Ritchie,DennisM. Th

7、ompson,K。Lane1982 Cook,StephenA.1981 Codd,EdgarF.1980 Hoare,C. AntonyR. 1979 Iverson,KennethE.1978 Floyd,RobertW1977 Backus,John1976 Rabin,MichaelO. Scott,DanaS1975 Newell,Allen Simon,HerbertA.1974 Knuth,DonaldE.1973 Bachman,CharlesW.1972 Dijkstra,E.W.1971 McCarthy,John1970 Wilkinson,J.H.1969 Minsky

8、,Marvin1968 Hamming,Richard1967 Wilkes,MauriceV1966 Perlis,A.J. 姚期智Dijkstra第8页，共60页，2022年，5月20日，11点11分，星期五Leslie Valiant, Harvard University Valiants greatest single contribution may be his 1984 paper A Theory of the Learnable, which laid the foundations of computational learning theory. He introduc

9、ed a general framework as well as concrete computational models for studying the learning process, including the famous probably approximately correct (PAC) model of machine learning. This has developed into a vibrant research area and has had enormous influence on machine learning, artificial intel

10、ligence, and many areas of computing practice, such as natural language processing, handwriting recognition, and computer vision.Professor of Computer Science and Applied MathematicsSchool of Engineering and Applied Sciences第9页，共60页，2022年，5月20日，11点11分，星期五目录（数理逻辑）第一章 命题演算基础 （6学时）第二章 命题演算的推理理论（4学时）第三章

11、 谓词演算基础（5学时）第四章 谓词演算的推理理论（5学时）第五章 递归函数论（4学时）第10页，共60页，2022年，5月20日，11点11分，星期五第一章 命题演算基础1.1 命题和联结词 1.1.1 命题 1.1.2 联结词 1.1.3 合式公式1.2 真假性1.3 范式及其应用第11页，共60页，2022年，5月20日，11点11分，星期五(一) 命题定义定义1： 凡是可以判断真假的陈述句称为命题。命题真值 真: 用T(或1)表示假: 用F(或0)表示第12页，共60页，2022年，5月20日，11点11分，星期五命题可以判断真假的陈述句特征 陈述句 真假性: 可决定真或假，且真假不可

12、兼 非经典逻辑不接受排中律第13页，共60页，2022年，5月20日，11点11分，星期五例：下列句子都是命题吗？ 雪是白的。 雪是黑的。 好大的雪啊！ 8大于12。 1+101=110。 第14页，共60页，2022年，5月20日，11点11分，星期五例：下列句子都是命题吗？上海世博会开幕时天晴 21世纪末，人类将住在月球 大于2的偶数可表示成两个素数之和（哥德巴赫猜想） XB 如果x大于3，则x2大于9。 第15页，共60页，2022年，5月20日，11点11分，星期五例：下列句子都是命题吗？ 8大于12吗？ 请勿吸烟。 姚明很帅。 南京很美。 我正在说谎 。 这种自指谓的语句往往会产生自

13、相矛盾的结论，即所谓的悖论第16页，共60页，2022年，5月20日，11点11分，星期五具体命题的真假问题在数理逻辑的学习中，不能去纠缠各种具体命题的真假问题，而是将命题当成数学概念来处理，看成一个抽象的形式化的概念，把命题定义成非真必假的陈述句公説公有理婆説婆有理 第17页，共60页，2022年，5月20日，11点11分，星期五带联结词的命题 今晚我看书。 今晚我玩网络游戏。 今晚我不看书。 今晚我不玩网络游戏。 今晚我不看书， 我玩网络游戏。 今晚我看书，或者我玩网络游戏。否定并且或者第18页，共60页，2022年，5月20日，11点11分，星期五(二) 原子命题和复合命题 原子命题不可

14、剖开或分解为更简单命题的命题，也称为简单命题。本书约定用大写字母表示。复合命题由原子命题利用联结词构成的命题第19页，共60页，2022年，5月20日，11点11分，星期五复合命题例子下列命题都是复合命题，其中红字为逻辑联结词：（1）雪不是白的（并非雪是白的）（2）今晚我看书或者去看电影。（3）如果天气好，那么我去接你。（4）偶数a是质数，当且仅当a=2（a是常数）。（5） 2是偶数且3也是偶数。 （6）你去了学校，我去了工厂。 （省略了逻辑联结词“且”）第20页，共60页，2022年，5月20日，11点11分，星期五(三)命题变元定义2：如果当P表示任意命题时，P称为命题变元。字母P表示命题

15、具体的、特定的命题，有确定的真值 命题变元任意命题，没有确定的真值 第21页，共60页，2022年，5月20日，11点11分，星期五第一章 命题演算基础1.1 命题和联结词 1.1.1 命题 1.1.2 联结词 1.1.3 合式公式1.2 真假性1.3 范式及其应用第22页，共60页，2022年，5月20日，11点11分，星期五五种常用的联结词 否定词 合取词 析取词 蕴含词 等价词 第23页，共60页，2022年，5月20日，11点11分，星期五P， 非P设P是一个命题。显然，如下这句话也是命题：“P是不对的”称之为P的否定。P PT FF T日常语句中有： 非， 不，并非， 真值表第24页

16、，共60页，2022年，5月20日，11点11分，星期五否定词的例子例 P：上海是中国的城市。 P：上海不是中国的城市。 例 P：雪是黑色的。 P：雪不是黑色的。 第25页，共60页，2022年，5月20日，11点11分，星期五否定联结词使用的原则将真命题变成假命题，将假命题变成真命题。但这并不是简单的随意加个不字就能完成的。例 P: 这些都是学生。 P：这些不都是学生 这些都不是学生第26页，共60页，2022年，5月20日，11点11分，星期五阿契贝难题例 下述两命题都是真命题：A: “本句是六字句”B: “本句不是六字句”看似矛盾的根本原因，在于两个命题的前提条件是否统一的问题。第27页

17、，共60页，2022年，5月20日，11点11分，星期五PQ， P合取Q设P，Q是两个命题。显然，如下这句话也是命题：“P并且Q”称之为P和Q的合取。P Q P QT T TT F FF T FF F F日常语句中有： 且，与，第28页，共60页，2022年，5月20日，11点11分，星期五合取词的例子 P: 225 Q：雪是白的。 PQ：225并且雪是白的。 P:今天刮风。 Q：今天下雨。 PQ：今天刮风并且今天下雨。 第29页，共60页，2022年，5月20日，11点11分，星期五PQ， P析取Q设P,Q是两个命题。显然，如下这句话也是命题：“P或者Q”称之为P和Q的析取。P Q P QT

18、 T TT F TF T TF F F日常语言中有： 或， 第30页，共60页，2022年，5月20日，11点11分，星期五析取词的例子 P: 225 Q：雪是白的。 PQ：225或者雪是白的。 P:今天刮风。 Q：今天下雨。 PQ ：今天刮风或者今天下雨。 第31页，共60页，2022年，5月20日，11点11分，星期五可兼的“或”P Q PQT T TT F TF T TF F F 他会英语或法语。 今天刮风或者今天下雨。第32页，共60页，2022年，5月20日，11点11分，星期五不可兼的“或”P Q PQ (P Q)(PQ)T T T F T F T TF T T TF F F F

19、人固有一死，或重于泰山，或轻于鸿毛。 今天晚上我去看电影，或去看球赛。异或XOR第33页，共60页，2022年，5月20日，11点11分，星期五PQ, P蕴含Q设P,Q是两个命题。显然，如下这句话也是命题：“如果P则Q”称之为P蕴含Q 。日常语言中有： 如果则, 只要就， P Q P QT T TT F FF T TF F T第34页，共60页，2022年，5月20日，11点11分，星期五蕴含词的例子 P：236 Q：(23)+1=6+2 PQ: 如果236，则（23）16+2 P: 天气不好 Q：我去接你 PQ: 如果天气不好，那么我去接你。第35页，共60页，2022年，5月20日，11点

20、11分，星期五注1. 前件为假时，命题为真如果蕴含前件P是假命题，那么不管Q是什么命题，命题 “如果P则Q”在逻辑中都被认为是真命题。例： 如果张三能及格，那太阳从西边升起。第36页，共60页，2022年，5月20日，11点11分，星期五注2. 前件、后件可以毫不相关在日常语言中“如果则”所联结的句子之间表现的是一种因果关系，但在数理逻辑中，尽管说前件蕴涵后件，但两个命题可以是毫不相关的。 例： P：235 Q：雪是黑色的 PQ：如果235，则雪是黑色的第37页，共60页，2022年，5月20日，11点11分，星期五注3. 充分条件、必要条件pq为真命题的逻辑关系是： p是q的充分条件， q是

21、p的必要条件。“q是p的必要条件”的叙述方式还有： p仅当q（仅当q，则p） 只有q才p 只要p就q 除非q，否则非p（非p，除非q）第38页，共60页，2022年，5月20日，11点11分，星期五蕴含词的例子用表示下列命题：（1）只要天下雨，我就回家。（2）只有天下雨，我才回家。（3）除非天下雨，否则我不回家。（4）仅当天下雨，我才回家。解 设p：天下雨。 q：我回家。 则（1）符号化为 pq。 （2）符号化为 qp，或： pq （3）符号化为 qp，或： pq （4）符号化为 qp，或： pq第39页，共60页，2022年，5月20日，11点11分，星期五PQ， P等价于Q设P，Q是两个命

22、题。显然，如下这句话也是命题：“P当且仅当Q”称之为P等价于Q。 P Q P QT T TT F FF T FF F T日常语言中有： 当且仅当，第40页，共60页，2022年，5月20日，11点11分，星期五等价词的例子 P: 224 Q：雪是白色的。 P Q：224当且仅当雪是白色的。 P: 225 Q：雪是黑色的。 P Q：225当且仅当雪是黑色。 第41页，共60页，2022年，5月20日，11点11分，星期五等价词的例子三角形ABC为等腰三角形当且仅当三角形ABC有两条边相等。ABC第42页，共60页，2022年，5月20日，11点11分，星期五非复合命题的例子（1）Tom和John

23、是兄弟。（2）如果x0， 则 x20。（3）如果两个三角形全等，则它们的面积相等。（4）一个三角形为等腰三角形当且仅当三角形有两条边相等。未指定第43页，共60页，2022年，5月20日，11点11分，星期五注4. 充要条件p q为真命题的逻辑关系是： p是q的充分条件， p是q的必要条件。第44页，共60页，2022年，5月20日，11点11分，星期五中学数学选修2-1：四种命题第45页，共60页，2022年，5月20日，11点11分，星期五中学数学选修2-1：充分、必要第46页，共60页，2022年，5月20日，11点11分，星期五真值函项定义：以真假为定义域并以真假为值域的函数 称为真值

24、函项。需要集合与映射的知识才能够讲透!T, FT, FT, F(T, T), (T,F),(F,T), (F,F)第47页，共60页，2022年，5月20日，11点11分，星期五一元联结词的真值表一元联结词有一个命题变项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页，2022年，5月20日，11点11分，星期五f1为与非：PQ=（PQ）f7为异或：PQ=（PQ）f14为或非：PQ=（PQ）二元联结词 P Q

25、f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15T 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为合取第49页，共60页，2022年，5月20日，11点11分，星期五三元联结词共有多少个？28f0f1f2f?(0,0,0)0101(0,0,1)0011(0,1,0)0001

26、(0,1,1)0001(1,0,0)0001(1,0,1)0001(1,1,0)0001(1,1,1)0001第50页，共60页，2022年，5月20日，11点11分，星期五第一章 命题演算基础1.1 命题和联结词 1.1.1 命题 1.1.2 联结词 1.1.3 合式公式 1.2 真假性1.3 范式及其应用第51页，共60页，2022年，5月20日，11点11分，星期五合式公式(Well formed formulae) 合式公式为如下定义的式子，简称为公式： 任何命题变元均是公式； 如果P为公式，则P为公式； 如果为P，Q为公式，则 PQ, PQ, PQ, PQ 为公式；当且仅当经过有限次使用、所组成的符号串才是公式，否则不为公式 。第52页，共60页，2022年，5月20日，11点11分，星期五n 元公式 若公式中有n个不同的命题变元，就说为n 元公式。例 一个3元公式： （PQ）R）（PQ）第53页，共60页，2