離散數(shù)學(xué),數(shù)理邏輯 集合論 圖論 代數(shù),,邏輯學(xué):研究推理的科學(xué),早期創(chuàng)始人 亞里士多德(公元前384322) 柏拉圖(公元前429348), 首先把邏輯學(xué)的思想方法引入幾何學(xué) 蘇格拉底（前470前399年）,亞里士多德（Aristotole，公元前384-322）,亞里士多德有170多部著作，留傳于世的僅47種。他的科學(xué)著作構(gòu)成當(dāng)時(shí)的科學(xué)知識(shí)百科全書(shū)。,世界古代史上最偉大的哲學(xué)家、科學(xué)家和教育家。他創(chuàng)立了形式邏輯學(xué)，豐富和發(fā)展了哲學(xué)的各個(gè)分支學(xué)科。,孔子（前551-479）,中國(guó)春秋末期偉大的思想家和教育家，儒家學(xué)派的創(chuàng)始人。 孔子被尊為圣人，無(wú)法超越，后代的人們只有沿襲與膜拜。,學(xué)而不思則罔 思而不學(xué)則殆,數(shù)理邏輯數(shù)學(xué)化的邏輯學(xué),在17世紀(jì)萊布尼茲（Leibniz）已經(jīng)提出仿數(shù)學(xué)的方法發(fā)展邏輯的思想。 1930年，Godel完全性定理的證明完善了數(shù)理邏輯基礎(chǔ)，建立了邏輯演算，成為現(xiàn)代科學(xué)特別是計(jì)算機(jī)科學(xué)不可缺少的基礎(chǔ)理論之一。,數(shù)理邏輯發(fā)展史中的代表人物,德國(guó)G.W. Leibniz (1626-1716)把數(shù)學(xué)引入形式邏輯，明確提出用數(shù)學(xué)方法研究推理。 英國(guó)G. Boole (1815-1864)等創(chuàng)立了邏輯代數(shù)，1847年Boole實(shí)現(xiàn)了命題演算。 德國(guó)G. Frege (1848-1925)在1879年建立了第一個(gè)謂詞演算系統(tǒng)。 英國(guó)B. Russell (1872-1970)等從邏輯學(xué)的基本法則建立了自然數(shù)理論、實(shí)數(shù)理論及解析幾何學(xué)等。 奧地利K. Godel (1906-1978)在1931年提出Godel不完全性定理。 英國(guó)Alan M. Turing (1912-1954)在1936年提出一種抽象計(jì)算模型（數(shù)學(xué)邏輯機(jī)），引入圖靈機(jī)一種理想的計(jì)算機(jī)。,數(shù)理邏輯的學(xué)習(xí),“我現(xiàn)在年紀(jì)大了，搞了這么多年的軟件，錯(cuò)誤不知犯了多少，現(xiàn)在覺(jué)悟了。我想，假如我早年在數(shù)理邏輯上好好下點(diǎn)工夫的話，我就不會(huì)犯這么多的錯(cuò)誤。不少東西邏輯學(xué)家早就說(shuō)過(guò)了，可是我不知道。要是我能年輕二十歲的話，我就去學(xué)邏輯。” Edsger. W. Dijkstra 1972年Turing獎(jiǎng)獲得者 (1930-2002),帶權(quán)圖的最短通路算法,A. M. Turing Award,姚期智,Dijkstra,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 introduced 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 intelligence, and many areas of computing practice, such as natural language processing, handwriting recognition, and computer vision.,Professor of Computer Science and Applied Mathematics School of Engineering and Applied Sciences,目錄（數(shù)理邏輯）,第一章 命題演算基礎(chǔ) （6學(xué)時(shí)） 第二章 命題演算的推理理論（4學(xué)時(shí)） 第三章 謂詞演算基礎(chǔ)（5學(xué)時(shí)） 第四章 謂詞演算的推理理論（5學(xué)時(shí)） 第五章 遞歸函數(shù)論（4學(xué)時(shí)）,第一章 命題演算基礎(chǔ),1.1 命題和聯(lián)結(jié)詞 1.1.1 命題 1.1.2 聯(lián)結(jié)詞 1.1.3 合式公式 1.2 真假性 1.3 范式及其應(yīng)用,,(一) 命題定義,定義1： 凡是可以判斷真假的陳述句稱為命題。,,命題可以判斷真假的陳述句,非經(jīng)典邏輯 不接受 排中律,例：下列句子都是命題嗎？,雪是白的。 雪是黑的。 好大的雪??！ 8大于12。 1+101=110。 ,例：下列句子都是命題嗎？,上海世博會(huì)開(kāi)幕時(shí)天晴 21世紀(jì)末，人類將住在月球 大于2的偶數(shù)可表示成兩個(gè)素?cái)?shù)之和（哥德巴赫猜想） XB 如果x大于3，則x2大于9。 ,例：下列句子都是命題嗎？,8大于12嗎？ 請(qǐng)勿吸煙。 姚明很帥。 南京很美。 我正在說(shuō)謊 。 ,這種自指謂的語(yǔ)句往往會(huì)產(chǎn)生自相矛盾的結(jié)論，即所謂的悖論,具體命題的真假問(wèn)題,在數(shù)理邏輯的學(xué)習(xí)中， 不能去糾纏各種具體命題的真假問(wèn)題， 而是將命題當(dāng)成數(shù)學(xué)概念來(lái)處理，看成一個(gè)抽象的形式化的概念，把命題定義成非真必假的陳述句,公説公有理 婆説婆有理,帶聯(lián)結(jié)詞的命題,今晚我看書(shū)。 今晚我玩網(wǎng)絡(luò)游戲。 今晚我不看書(shū)。 今晚我不玩網(wǎng)絡(luò)游戲。 今晚我不看書(shū)， 我玩網(wǎng)絡(luò)游戲。 今晚我看書(shū)，或者我玩網(wǎng)絡(luò)游戲。,否定,并且,或者,(二) 原子命題和復(fù)合命題,原子命題不可剖開(kāi)或分解為更簡(jiǎn)單命題的命題，也稱為簡(jiǎn)單命題。本書(shū)約定用大寫(xiě)字母表示。 復(fù)合命題由原子命題利用聯(lián)結(jié)詞構(gòu)成的命題,復(fù)合命題例子,下列命題都是復(fù)合命題，其中紅字為邏輯聯(lián)結(jié)詞： （1）雪不是白的（并非雪是白的） （2）今晚我看書(shū)或者去看電影。 （3）如果天氣好，那么我去接你。 （4）偶數(shù)a是質(zhì)數(shù)，當(dāng)且僅當(dāng)a=2（a是常數(shù)）。 （5） 2是偶數(shù)且3也是偶數(shù)。 （6）你去了學(xué)校，我去了工廠。 （省略了邏輯聯(lián)結(jié)詞“且”）,(三)命題變?cè)?定義2：如果當(dāng)P表示任意命題時(shí)，P稱為命題變?cè)?字母P表示,,命題具體的、特定的命題，有確定的真值,命題變?cè)我饷}，沒(méi)有確定的真值,,第一章 命題演算基礎(chǔ),1.1 命題和聯(lián)結(jié)詞 1.1.1 命題 1.1.2 聯(lián)結(jié)詞 1.1.3 合式公式 1.2 真假性 1.3 范式及其應(yīng)用,,五種常用的聯(lián)結(jié)詞,否定詞 合取詞 析取詞 蘊(yùn)含詞 等價(jià)詞 ,P， 非P,設(shè)P是一個(gè)命題。顯然，如下這句話也是命題： “P是不對(duì)的” 稱之為P的否定。,P P T F F T,,,,日常語(yǔ)句中有： 非， 不，并非， ,真值表,,否定詞的例子,例 P：上海是中國(guó)的城市。 P：上海不是中國(guó)的城市。 例 P：雪是黑色的。 P：雪不是黑色的。,否定聯(lián)結(jié)詞使用的原則,將真命題變成假命題，將假命題變成真命題。但這并不是簡(jiǎn)單的隨意加個(gè)不字就能完成的。,例 P: 這些都是學(xué)生。 P：這些不都是學(xué)生 這些都不是學(xué)生,阿契貝難題,例 下述兩命題都是真命題： A: “本句是六字句” B: “本句不是六字句”,看似矛盾的根本原因，在于兩個(gè)命題的前提條件是否統(tǒng)一的問(wèn)題。,PQ， P合取Q,設(shè)P，Q是兩個(gè)命題。顯然，如下這句話也是命題： “P并且Q” 稱之為P和Q的合取。,日常語(yǔ)句中有： 且，與，,,合取詞的例子,P: 225 Q：雪是白的。 PQ：225并且雪是白的。,P:今天刮風(fēng)。 Q：今天下雨。 PQ：今天刮風(fēng)并且今天下雨。,PQ， P析取Q,設(shè)P,Q是兩個(gè)命題。顯然，如下這句話也是命題： “P或者Q” 稱之為P和Q的析取。,P Q P Q T T T T F T F T T F F F,,,日常語(yǔ)言中有： 或，,,析取詞的例子,P: 225 Q：雪是白的。 PQ：225或者雪是白的。,P:今天刮風(fēng)。 Q：今天下雨。 PQ ：今天刮風(fēng)或者今天下雨。,可兼的“或”,P Q PQ T T T T F T F T T F F F,,,他會(huì)英語(yǔ)或法語(yǔ)。 今天刮風(fēng)或者今天下雨。,不可兼的“或”,P Q PQ (P Q)(PQ) T T T F T F T T F T T T F F F F,,,人固有一死，或重于泰山，或輕于鴻毛。 今天晚上我去看電影，或去看球賽。,,異或 XOR,PQ, P蘊(yùn)含Q,設(shè)P,Q是兩個(gè)命題。顯然，如下這句話也是命題： “如果P則Q” 稱之為P蘊(yùn)含Q 。,日常語(yǔ)言中有： 如果則, 只要就，,P Q P Q T T T T F F F T T F F T,,,蘊(yùn)含詞的例子,P：236 Q：(23)+1=6+2 PQ: 如果236，則（23）16+2,P: 天氣不好 Q：我去接你 PQ: 如果天氣不好，那么我去接你。,,注1. 前件為假時(shí)，命題為真,如果蘊(yùn)含前件P是假命題，那么不管Q是什么命題，命題 “如果P則Q” 在邏輯中都被認(rèn)為是真命題。 例： 如果張三能及格，那太陽(yáng)從西邊升起。,,注2. 前件、后件可以毫不相關(guān),在日常語(yǔ)言中“如果則”所聯(lián)結(jié)的句子之間表現(xiàn)的是一種因果關(guān)系，但在數(shù)理邏輯中，盡管說(shuō)前件蘊(yùn)涵后件，但兩個(gè)命題可以是毫不相關(guān)的。 例： P：235 Q：雪是黑色的 PQ：如果235，則雪是黑色的,,注3. 充分條件、必要條件,pq為真命題的邏輯關(guān)系是： p是q的充分條件， q是p的必要條件。 “q是p的必要條件”的敘述方式還有： p僅當(dāng)q（僅當(dāng)q，則p） 只有q才p 只要p就q 除非q，否則非p（非p，除非q）,蘊(yùn)含詞的例子,用表示下列命題： （1）只要天下雨，我就回家。 （2）只有天下雨，我才回家。 （3）除非天下雨，否則我不回家。 （4）僅當(dāng)天下雨，我才回家。 解 設(shè)p：天下雨。 q：我回家。 則（1）符號(hào)化為 pq。 （2）符號(hào)化為 qp，或： pq （3）符號(hào)化為 qp，或： pq （4）符號(hào)化為 qp，或： pq,PQ， P等價(jià)于Q,設(shè)P，Q是兩個(gè)命題。顯然，如下這句話也是命題： “P當(dāng)且僅當(dāng)Q” 稱之為P等價(jià)于Q。,P Q P Q T T T T F F F T F F F T,,,,日常語(yǔ)言中有： 當(dāng)且僅當(dāng)，,等價(jià)詞的例子,P: 224 Q：雪是白色的。 P Q：224當(dāng)且僅當(dāng)雪是白色的。,P: 225 Q：雪是黑色的。 P Q：225當(dāng)且僅當(dāng)雪是黑色。,等價(jià)詞的例子,三角形ABC為等腰三角形當(dāng)且僅當(dāng)三角形ABC有兩條邊相等。,非復(fù)合命題的例子,（1）Tom和John是兄弟。 （2）如果x0， 則 x20。 （3）如果兩個(gè)三角形全等，則它們的面積相等。 （4）一個(gè)三角形為等腰三角形當(dāng)且僅當(dāng)三角形有兩條邊相等。,未指定,注4. 充要條件,p q為真命題的邏輯關(guān)系是： p是q的充分條件， p是q的必要條件。,中學(xué)數(shù)學(xué)選修2-1：四種命題,,中學(xué)數(shù)學(xué)選修2-1：充分、必要,,真值函項(xiàng),定義：以真假為定義域并以真假為值域的函數(shù) 稱為真值函項(xiàng)。,需要集合與映射的知識(shí)才能夠講透!,,T, F,T, F,T, F,(T, T), (T,F),(F,T), (F,F),一元聯(lián)結(jié)詞的真值表,一元聯(lián)結(jié)詞有一個(gè)命題變項(xiàng)P，它取真和假兩種，可定義四個(gè)不同的一元聯(lián)結(jié)詞f0，f1，f2，f3，或稱為真值函項(xiàng)。 其真假關(guān)系可用下圖表示：,P f0(P) f1(P) f2(P) f3(P) T T T F F F T F T F,,,永真,恒等,否定P,永假,二元聯(lián)結(jié)詞,P Q f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 T T T F T T T F F F T T T T F F F F T F T T F T T F T T F F T F T F F F F T T T T F T T F T F T F F F T F F F F T T T T F T T F T F F F F F T F,,,f2為 蘊(yùn)含,f4為 析取,f8為 等價(jià),f11為合取,三元聯(lián)結(jié)詞共有多少個(gè)？,28,第一章 命題演算基礎(chǔ),1.1 命題和聯(lián)結(jié)詞 1.1.1 命題 1.1.2 聯(lián)結(jié)詞 1.1.3 合式公式 1.2 真假性 1.3 范式及其應(yīng)用,,合式公式(Well formed formulae),合式公式為如下定義的式子，簡(jiǎn)稱為公式： 任何命題變?cè)枪剑?如果P為公式，則P為公式； 如果為P，Q為公式，則 PQ, PQ, PQ, PQ 為公式； 當(dāng)且僅當(dāng)經(jīng)過(guò)有限次使用、、所組成的符號(hào)串才是公式，否則不為公式 。,n 元公式,若公式中有n個(gè)不同的命題變?cè)?就說(shuō)為n 元公式。,例 一個(gè)3元公式： （（PQ）R）（PQ）,,命題符號(hào)化,將復(fù)合命題符號(hào)化的步驟是 分析出簡(jiǎn)單命題，符號(hào)化 用聯(lián)結(jié)詞聯(lián)結(jié)簡(jiǎn)單命題,提示：根據(jù)命題的實(shí)際含義，不拘泥于原句形式地確定原子命題和選用聯(lián)結(jié)詞。,例1(p5) 將下列各命題符號(hào)化: 只有努力學(xué)習(xí)、認(rèn)真復(fù)習(xí)，才能取得好成績(jī)。,解：令P表示“努力學(xué)習(xí)”； Q表示“認(rèn)真復(fù)習(xí)”； R表示“取得好成績(jī)”。 則原句譯為 R（PQ）,該語(yǔ)句能不能譯為（PQ） R？,,例4(p5)已知三個(gè)命題： P：今晚我在家上網(wǎng)；Q：今晚我去球場(chǎng)看足球比賽；R：今晚我在家上網(wǎng)或去球場(chǎng)看足球比賽。試問(wèn)PQ和R是否表達(dá)同一命題？請(qǐng)用真值表說(shuō)明之。,R=(PQ)(PQ),不可兼 或,例 將下列語(yǔ)句形式化，并表示為命題公式：,（1）狗急跳墻。 令 p：狗急了， q：狗跳墻。 則可表示為 pq,例 將下列語(yǔ)句形式化，并表示為命題公式：,（2）如果他不來(lái)， 那么他或者是生病了，或者是不在本地。 記 p：他來(lái)， q：他生病， r：他在本地。 則可表示為 p(qr),例 將下列語(yǔ)句形式化，并表示為命題公式：,（3）如果你和他不都是傻子， 那么你們倆都不會(huì)去自討沒(méi)趣。 令 p：你是傻子， q：他是傻子， r：你會(huì)去自討沒(méi)趣， s：他會(huì)去自討沒(méi)趣。 則 可表示為 (pq)(rs),(p q)(rs) ?,第一章 命題演算基礎(chǔ),1.1 命題和聯(lián)結(jié)詞 1.1.1 命題 1.1.2 聯(lián)結(jié)詞 1.1.3 合式公式 1.2 真假性 1.3 范式及其應(yīng)用,,