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