東南大學薛暉hxueseueducn教學課件

東南大學薛暉hxueseueducn教學課件東南大學薛暉hxueseueducn教學課件經(jīng)典問題之一一邏輯學家誤入某部落，被囚于牢獄，酋長欲意放行，他對邏輯學家說：“今有兩門，一為自由，一為死亡，你可任意開啟一門?，F(xiàn)從兩個戰(zhàn)士中選擇一人負責解答你所提的任何一個問題（Y/N），其中一個天性誠實，一人說謊成性，今后生死任你選擇?！边壿媽W家沉思片刻，即向一戰(zhàn)士發(fā)問，然后開門從容離去。邏輯學家應如何發(fā)問？經(jīng)典問題之一一邏輯學家誤入某部落，被囚于牢獄，酋長欲意放行，經(jīng)典問題之二某汽車司機違章駕駛，交警向他宣布處理決定：“要么扣留駕駛執(zhí)照三個月，要么罰款1000元?！彼緳C說：“我不同意?！比绻緳C堅持己見，那么，以下哪項實際上是他必須同意的？A、扣照但不罰款。B、罰款但不扣照。

C、既不罰款也不扣照。

D、既罰款又扣照。

E、如果做不到既不罰款也不扣照，那么就必須接受既罰款又扣照。經(jīng)典問題之二某汽車司機違章駕駛，交警向他宣布處理決定：“要么經(jīng)典問題之二某汽車司機違章駕駛，交警向他宣布處理決定：“要么扣留駕駛執(zhí)照三個月，要么罰款1000元?！彼緳C說：“我不同意?！比绻緳C堅持己見，那么，以下哪項實際上是他必須同意的？A、扣照但不罰款。B、罰款但不扣照。

C、既不罰款也不扣照。

D、既罰款又扣照。

E、如果做不到既不罰款也不扣照，那么就必須接受既罰款又扣照。

經(jīng)典問題之二某汽車司機違章駕駛，交警向他宣布處理決定：“要么數(shù)理邏輯與計算機一切能用數(shù)理邏輯抽像出來的邏輯問題，全都可以用計算機程序來解決羅素和懷海德的巨著《數(shù)學原理》里給出了很多經(jīng)典數(shù)學定理的證明過程，在若干年以后，書中越來越多的定理已能夠用計算機程序自動證明出來數(shù)理邏輯與計算機一切能用數(shù)理邏輯抽像出來的邏輯問題，全都可以數(shù)理邏輯與計算機1959年，美籍華人王浩教授只用9分鐘的機器時間，就在計算機上證明了羅素和懷特?！稊?shù)學原理》一書中的一階邏輯部分的全部定理350多條，讓羅素驚嘆不已數(shù)理邏輯與計算機1959年，美籍華人王浩教授只用9分鐘的機器幻方據(jù)傳說，大禹在4000多年前就觀察到神龜背上的幻方1977年美國旅行者1號、2號宇宙飛船就帶上了幻方以作為人類智慧的信號幻方幻方幻方可以看作是一個3階方陣，其元素是1到9的正整數(shù)，每行、每列以及兩條對角線的和都方幻方可以看作是一個3階方陣，其元素是1到9的正整數(shù)，每行幻方一個n階幻方是由整數(shù)1，2，3，…，n2按下述方式組成的n×n方陣：該方陣每行上的整數(shù)的和、每列上的整數(shù)的和以及兩條對角線中每條對角線上的整數(shù)的和都等于同一個數(shù)s

s--幻和幻方一個n階幻方是由整數(shù)1，2，3，…，n2按下述方式組成的幻方81635749216321351011896712415141問題：哪些n存在幻方？如果有，則構造方法如何？幻方81635構造幻方構造奇數(shù)階幻方的方法：將1放在最上一行的中間，其后的整數(shù)沿著自左下到右上的這條對角線按照自然順序放置，同時作修正：在到達頂行時，下一個整數(shù)要放在底行，所放位置就是把底行當作頂行上邊一行時該數(shù)應該放置的位置當?shù)竭_最右邊的一列時，下一個整數(shù)要放在最左邊的一列上，所放位置就是把最左邊的一列當作最右邊那列的右邊的列時該數(shù)應該放置的位置當要放的位置上已經(jīng)填好了整數(shù)，或上一個整數(shù)已經(jīng)放在了幻方的右上角時，則當前要擺放的整數(shù)將放在緊挨上述位置的下方構造幻方構造奇數(shù)階幻方的方法：Konigsberg七橋問題在哥尼斯堡的一個公園里，有七座橋將普雷格爾河中兩個島及島與河岸連接起來。問是否可能從這四塊陸地中任一塊出發(fā)，恰好通過每座橋一次，再回到起點？Konigsberg七橋問題在哥尼斯堡的一個公園里，有七座橋一筆畫問題歐拉于1736年研究并解決了此問題，他把問題歸結為“一筆畫”問題，證明上述走法是不可能的連通圖可以一筆畫的充要條件是它們是連通的，且奇頂點(通過此點弧的條數(shù)是奇數(shù))的個數(shù)為0或2一筆畫問題歐拉于1736年研究并解決了此問題，他把問題歸結為中國郵遞員問題郵遞員從郵局出發(fā)送信，要求對轄區(qū)內每條街，都至少通過一次，再回郵局。在此條件下，怎樣選擇一條最短路線?中國郵遞員問題由管梅谷教授在1960年提出，美國國家標準和技術研究院（NIST）首先將此問題命名為中國郵遞員問題

中國郵遞員問題郵遞員從郵局出發(fā)送信，要求對轄區(qū)內每條街，都至中國郵遞員問題假設有一個鎮(zhèn)有14條路及9個路口（路口分別編號為1,2,…,9），如何找到一條最短路線?

中國郵遞員問題假設有一個鎮(zhèn)有14條路及9個路口（路口分別編號歐拉回路若圖中有歐拉回路（圖G的一個回路，若它恰通過G中每條邊一次），則任何一個歐拉回路即為此問題的解若圖中不存在歐拉回路，其中必存在有奇數(shù)個邊的端點，且這類的端點一定大于2個。因此有些邊需要再重復一次，使奇數(shù)邊的端點變?yōu)榕紨?shù)邊的端點歐拉回路若圖中有歐拉回路（圖G的一個回路，若它恰通過G中每條重復邊不存在歐拉回路，其中有4個路口（編號1,3,6及9）有奇數(shù)條路通過現(xiàn)在要做：在圖中使幾個邊重復，使圖中所有的端點均有偶數(shù)邊通過

問題：確定重復哪個邊可以使原圖的端點都有偶數(shù)邊通過，且增加長度最少？重復邊不存在歐拉回路，其中有4個路口（編號1,3,6選擇重復邊畫出所有奇數(shù)邊的端點的完全圖K4，邊上的數(shù)字是從一端點到另一端點的最短長度選擇邊{1,6}及{3,9}，所有端點都經(jīng)過一次，而總長度4+2=6最短選擇重復邊畫出所有奇數(shù)邊的端點的完全圖K4，邊上的數(shù)字是問題的解原來的圖中，連接端點1和6,端點3和9的邊再重復一次，所有端點均有偶數(shù)個邊通過任一個歐拉路徑即為此問題的解答，如以下的端點順序{1,2,3,4,9,3,1,8,7,3,9,7,6,9,5,6,7,8,1}即為一解。圖中紅色的部份即為重復的邊問題的解原來的圖中，連接端點1和6,端點3和9其它問題網(wǎng)頁推薦地鐵門控制通訊網(wǎng)絡的布局航空調度和航班的設定城市的交通管理和交通規(guī)劃。。。。。。其它問題網(wǎng)頁推薦離散數(shù)學

DiscreteMathematics

？離散數(shù)學

？什么是離散數(shù)學研究離散量的結構及相互關系的數(shù)學科學離散結構：集合、關系、圖等

離散量是指分散開來的、不存在中間值的量

研究對象:有限或可數(shù)個元素自然數(shù)、整數(shù)，真假值，有限節(jié)點等計算機技術的支撐科學：計算機只能處理離散的或離散化了的數(shù)量關系什么是離散數(shù)學研究離散量的結構及相互關系的數(shù)學科學與其他專業(yè)課關系數(shù)據(jù)結構基礎離散數(shù)學數(shù)據(jù)庫原理軟件工程操作系統(tǒng)編譯原理人工智能可計算性理論與其他專業(yè)課關系數(shù)據(jù)結構基礎離散數(shù)學數(shù)據(jù)庫原理軟件工程操作系離散數(shù)學的特點知識點集中，概念和定理多方法性強

--構造模型的能力；算法設計的能力；程序設計的能力學數(shù)學就要做數(shù)學離散數(shù)學的特點知識點集中，概念和定理多教材及參考書《離散數(shù)學》屈婉玲、耿素云、張立昂著，高等教育出版社，2008《DiscreteMathematicsandItsApplications（影印版）》K.H.Rosen著，機械工業(yè)出版社，2003《離散數(shù)學》孫吉貴、楊鳳杰、歐陽丹彤、李占山著，高等教育出版社，2002《離散數(shù)學》左孝凌、李為鑑、劉永才編著，上?？茖W技術文獻出版社，1994教材及參考書《離散數(shù)學》屈婉玲、耿素云、張立昂著，高等教育課程安排數(shù)理邏輯集合論代數(shù)結構圖論課程安排數(shù)理邏輯集合論代數(shù)結構圖論課程安排數(shù)理邏輯集合論代數(shù)結構圖論課程安排數(shù)理邏輯集合論代數(shù)結構圖論數(shù)理邏輯邏輯學分類辯證邏輯：是研究事物發(fā)展的客觀規(guī)律形式邏輯：是研究思維的概念、判斷和推理的問題數(shù)理邏輯…數(shù)理邏輯數(shù)學方法研究形式邏輯的一門科學一般認為由萊布尼茲（Leibnitz）率先提出最基本組成部分：命題演算、謂詞演算應用：邏輯電路、自動控制、人工智能等數(shù)理邏輯邏輯學分類主要內容命題邏輯基本概念命題邏輯等值演算命題邏輯推理理論一階邏輯基本概念一階邏輯等值演算第一部分數(shù)理邏輯主要內容第一部分數(shù)理邏輯第一章命題邏輯基本概念命題與聯(lián)結詞命題及其分類聯(lián)結詞與復合命題命題公式及其賦值第一章命題邏輯基本概念命題與聯(lián)結詞第一節(jié)：命題與聯(lián)結詞第一節(jié)：命題與聯(lián)結詞1.1命題與聯(lián)結詞命題：具有唯一真值的陳述句唯一性：或真或假但不能兩者都是的命題所用符號：常用小寫２６個英文字母例子十是整數(shù)2100年人類將在月球生活x=3現(xiàn)在是幾點？1+1=2我現(xiàn)在說假話我現(xiàn)在說真話悖論！1.1命題與聯(lián)結詞命題：具有唯一真值的陳述句悖論！1.1命題與聯(lián)結詞判斷下列語句是否為命題明天下雨加拿大是一個國家x+y>4注：命題是陳述句，陳述句不一定是命題命題有唯一真值，但真值可能受范圍、時空、環(huán)境、判斷標準、認識程度限制，一時無法確定1.1命題與聯(lián)結詞判斷下列語句是否為命題1.1命題與聯(lián)結詞命題分類簡單命題：不能被分解成更簡單的命題復合命題：簡單命題+聯(lián)結詞例子豆沙包是由面粉和紅豆做的今天沒有天晴王華的成績很好并且品德很好小李是學數(shù)學或者計算機科學如果天下雨，那么地下濕1.1命題與聯(lián)結詞命題分類1.1命題與聯(lián)結詞否定聯(lián)結詞符號?,讀作“非”，“否定”定義：命題pp的否定式：復合命題“p的否定”（“非p”）符號：

p(符號

稱作否定聯(lián)結詞)

p為真當且僅當p為假例子今天沒有天晴p：今天天晴p

pTFFT

p

1.1命題與聯(lián)結詞否定聯(lián)結詞ppTFFTp1.1命題與聯(lián)結詞合取聯(lián)結詞符號

,讀作“合取”定義：命題p，qp與q的合取式：復合命題“p并且q”符號：p

q(符號

稱作合取聯(lián)結詞)p

q為真當且僅當p和q同時為真例子王華的成績很好并且品德很好p

qp：王華的成績很好q：王華的品德很好pqp

qFFFFTFTFFTTT1.1命題與聯(lián)結詞合取聯(lián)結詞pqpqFFFFTFTFFT1.1命題與聯(lián)結詞析取聯(lián)結詞符號

,讀作“析取”定義：命題p，qp與q的析取式：復合命題“p或q”符號：p

q(符號

稱作析取聯(lián)結詞)p

q為假當且僅當p和q同時為假例子小李是學數(shù)學或者計算機科學p

qp：小李是學數(shù)學q：小李是學計算機科學pqp

qFFFFTTTFTTTT1.1命題與聯(lián)結詞析取聯(lián)結詞pqpqFFFFTTTFTT1.1命題與聯(lián)結詞析取聯(lián)結詞（相容或）≠

“排斥或”排斥或：符號定義：命題p，q符號：p

q等價于(p

q)(p

q)p

q為假當且僅當p和q同時為假或

同時為真例子：小李在教室看書或在圖書館上網(wǎng)小李在看書或者聽音樂pqp

qFFFFTTTFTTTF1.1命題與聯(lián)結詞析取聯(lián)結詞（相容或）≠1.1命題與聯(lián)結詞例子2或3是素數(shù)小元元只能拿一個蘋果或一個梨王小紅生于1988年或1989年1.1命題與聯(lián)結詞例子1.1命題與聯(lián)結詞蘊涵聯(lián)結詞符號

,讀作“如果…則…”、“蘊涵”定義：命題p，qp與q的蘊涵式：復合命題“如果p，則q”符號：p

q(符號

稱作蘊涵聯(lián)結詞)p

q為假當且僅當p為真，q為假例子如果天下雨，那么地下濕p

qp：天下雨q：地下濕pqp

qFFTFTTTFFTTT1.1命題與聯(lián)結詞蘊涵聯(lián)結詞pqpqFFTFTTTFFT1.1命題與聯(lián)結詞更多關于蘊含聯(lián)結詞…p

q：q是p的必要條件其他：p

q的敘述方式：“只要p，就q”，“因為p，所以q”等p為假，p

q永遠為真

如果給我一個支點，我能把

地球撬起來區(qū)別于自然語言的“如果p,則q”p和q有內在聯(lián)系pqp

qFFTFTTTFFTTT1.1命題與聯(lián)結詞更多關于蘊含聯(lián)結詞…pqpqFFTFT1.1命題與聯(lián)結詞更多例子如果天晴，則雪是白的如果不天晴，則雪是不是白的由于交通阻塞，他遲到了如果交通不阻塞，他就不會遲到他沒遲到，所以交通沒阻塞除非交通阻塞，否則他不會遲到除非他遲到，否則交通沒有阻塞他遲到僅當交通阻塞1.1命題與聯(lián)結詞更多例子1.1命題與聯(lián)結詞給定命題p

q它的逆命題q

p它的反命題

p

q它的逆反命題

q

p各種命題關系p

q

q

pq

p

p

q1.1命題與聯(lián)結詞給定命題pq1.1命題與聯(lián)結詞等價式符號

,讀作“當且僅當”定義：命題p，qp與q的等價式：復合命題“p當且僅當q”符號：p

q(符號

稱作等價聯(lián)結詞)p

q為真當且僅當p與q真值相同例子當且僅當2+3=5，才有2是素數(shù)

p

qp：2+3=5q：2是素數(shù)pqp

qFFTFTFTFFTTT1.1命題與聯(lián)結詞等價式pqpqFFTFTFTFFTTT1.1命題與聯(lián)結詞聯(lián)結詞的定義總結pq

pp

qp

qp

qp

qFFTFFTTFTTFTTFTFFFTFFTTFTTTT1.1命題與聯(lián)結詞聯(lián)結詞的定義總結pqppqpqp1.1命題與聯(lián)結詞聯(lián)結詞的優(yōu)先級、、、、括號最優(yōu)先同一優(yōu)先級：從左到右例子：求于命題

p

q

r含義相同的命題((

p)

q)

r(

(p

q))

r

p

(q

r)

(p

q

r)1.1命題與聯(lián)結詞聯(lián)結詞的優(yōu)先級1.1命題與聯(lián)結詞例：p：北京比天津人口多q：2＋2＝4r：烏鴉是白色的求下列命題真值((?p∧q)∨(p∧?q))→r(q∨r)→(p→?r)(?p∨r)

(p∧?r)

TTF1.1命題與聯(lián)結詞例：TTF1.1命題與聯(lián)結詞課堂練習：符號化下面命題小強雖然不聰明，但很用功小李學過英語或者法語小李是上海人或者蘇州人金無足赤，人無完人得道多助，失道寡助

p

qp

q

p

q(p

q)

(

p

q)p

q1.1命題與聯(lián)結詞課堂練習：符號化下面命題pqpq1.1命題與聯(lián)結詞課堂練習：p：2+3=5q：大熊貓產(chǎn)在中國r：太陽從西方升起求下列命題真值(r(p

q))(p

r)TFTFF1.1命題與聯(lián)結詞課堂練習：TFTFF第二節(jié)：命題公式及其賦值第二節(jié)：命題公式及其賦值1.2命題公式及其賦值命題常項：簡單命題命題變項：表示命題的變量真值可以變化的陳述句命題變項不是命題命題變項用確定命題代入才能確定真值命題所用符號：常用小寫２６個英文字母命題變量不同于代數(shù)式的變量x+y>4的x，y不是命題變量1.2命題公式及其賦值命題常項：簡單命題1.2命題公式及其賦值合式公式（命題公式）的遞歸定義：單個命題常項或命題變項是合式公式（原子命題公式）

A為合式公式，則

A是合式公式

A，B為合式公式,則（A

B），（A

B），（A

B），（A

B）為合式公式4.有限次應用1-3形成的符號串為合式公式子公式B：給定合式公式AB是A的一部分B是合式公式1.2命題公式及其賦值合式公式（命題公式）的遞歸定義：1.2命題公式及其賦值符號說明大寫字母A，B表示合式公式公式簡寫法則：公式最外層括號可以省略（

A）的括號可以省略根據(jù)運算符優(yōu)先級省略括號省略括號不能影響公式解釋1.2命題公式及其賦值符號說明1.2命題公式及其賦值合式公式的樹狀展開(AB)((C)(DC))ABAB(C)(DC)(C)DCCDC1.2命題公式及其賦值合式公式的樹狀展開ABAB1.2命題公式及其賦值例子(A

B)C(p

q)(q

r)(B)pq

r1.2命題公式及其賦值例子1.2命題公式及其賦值公式層次若公式A是單個的命題變元，則稱A為0層合式稱公式A是n+1(n≥0)層公式是指下面情況之一：A＝?B，B是n層公式A＝B

C，其中B，C分別為i層和j層公式，且n＝max(i,j)A＝B∨C，其中B，C的層次及n同(b)A＝B

C，其中B，C的層次及n同(b)A＝B

?

C，其中B，C的層次及n同(b)若公式A的層次為k，則稱A是k層公式層次≠聯(lián)結詞數(shù)1.2命題公式及其賦值公式層次1.2命題公式及其賦值例子：p,q,r,s為命題變元((p

q)r)s(p

q)(q

r)(p

q

r)s

(p

q

r)4351.2命題公式及其賦值例子：p,q,r,s為命題變元4351.2命題公式及其賦值命題公式的真值命題變項的常量化：常項替換（解釋）例子：公式p

q

r真值為T的解釋p:3是奇數(shù)；q:7是奇數(shù)；r:3乘7是奇數(shù)真值為F的解釋p:3是奇數(shù)；q:7是奇數(shù)；r:3乘7是偶數(shù)賦值命題變項賦真命題命題變項的真值為T命題變項賦假命題命題變項的真值為F1.2命題公式及其賦值命題公式的真值1.2命題公式及其賦值命題變項賦值A中命題變項：p1,…pn對p1,…pn賦值v：v(pi)=i，i{T,F}對A的真值遞歸定義v(B)=Tiffv(B)=Fv(BC)=Tiffv(B)=v(C)=Tv(BC)=Fiffv(B)=v(C)=Fv(BC)=Fiffv(B)=T，v(C)=Fv(BC)=Tiffv(B)=v(C)賦值（解釋）簡寫：1,

2…,

nn個變項的公式，共有2n個不同賦值1.2命題公式及其賦值命題變項賦值1.2命題公式及其賦值命題變項賦值成真賦值：v(A)=T成假賦值：v(A)=F例子：公式(p

q)rFFF(p=F,q=F,r=F)TFF?(p

q)rFFF1.2命題公式及其賦值命題變項賦值(pq)rFFF1.2命題公式及其賦值真值表：A所有賦值列成表真值表構造：找出A中命題變項：p1,…pn列出2n個賦值（2進制加法形式）從低到高寫成公式各個層次各個賦值：計算各層的真值1.2命題公式及其賦值真值表：A所有賦值列成表1.2命題公式及其賦值例：?((p

q)

p)pqp

q(p

q)

p?((p

q)

p)000010110110110111101.2命題公式及其賦值例：?((pq)p)pqpq(1.2命題公式及其賦值例：(p

?

q)

?(p

q

?p

?q)p

q?p?qp

?

qp

q

?p

?q公式00111110110001100100111001111.2命題公式及其賦值例：(p?q)?(pq?p1.2命題公式及其賦值命題公式分類：A重言式(永真式)：v(A)=T，對任意v矛盾式(永假式)：v(A)=F，對任意v可滿足式：v(A)=T，對某個v關系重言式是可滿足式，反之不一定成立真值表判斷重言式：真值表最后一列全為T矛盾式：真值表最后一列全為F可滿足式：真值表最后一列至少一個T1.2命題公式及其賦值命題公式分類：A1.2命題公式及其賦值真值表有限性：給定n個命題變項共有22n個真值表例題：下列哪些具有相同真值？pqqp(pq)(pq)p1.2命題公式及其賦值真值表有限性：給定n個命題變項1.2命題公式及其賦值例題p

qp

qq

p(p

q)(p

q)p0011100110111001001111101.2命題公式及其賦值例題pqpqqp(pq)1.2命題公式及其賦值例題：下列哪些具有相同真值？pqp(qr)(pq)((pr)p)1.2命題公式及其賦值例題：下列哪些具有相同真值？1.2命題公式及其賦值例題pqrp

qp(q

r)(p

q)((p

r)p)0001010011010101010111011000101010101101011111111.2命題公式及其賦值例題pqrpqp(qr)(第一章習題課主要內容命題、真值、簡單命題與復合命題、命題符號化聯(lián)結詞

,

,

,

,

及復合命題符號化命題公式及層次公式的類型真值表及應用基本要求深刻理解各聯(lián)結詞的邏輯關系,熟練地將命題符號化會求復合命題的真值深刻理解合式公式及重言式、矛盾式、可滿足式等熟練地求公式的真值表，并用它求公式的成真賦值與成假賦值及判斷公式類型第一章習題課主要內容1.將下列命題符號化(1)蘋果樹和梨樹都是落葉喬木(2)王小紅和李大明組成一個物理小組(3)王小紅或李大明是物理組成員(4)王小紅或李大明中的一人是物理組成員(5)只要天冷，小王就穿羽絨服(6)因為天冷，所以小王穿羽絨服(7)若小王不穿羽絨服，則天不冷(8)只有天冷，小王才穿羽絨服

(9)除非天冷，小王才穿羽絨服(10)除非小王穿羽絨服，否則天不冷(11)如果天不冷，則小王不穿羽絨服(12)小王穿羽絨服當且僅當天冷的時候練習11.將下列命題符號化練