1、離散數(shù)學,Discrete Mathematics,主講教師,王衛(wèi)蘋 電話：62332931 郵箱： 辦公地點：信息機電樓728室,課程簡介,現(xiàn)代數(shù)學重要分支 以研究離散量的結構和相互間的關系為主要目標。 信息類學科基礎理論的核心課程。 是數(shù)據(jù)結構、操作系統(tǒng)、編譯技術、人工智能、數(shù)據(jù)庫、算法設計與分析等課程必不可少的先行課程。 培養(yǎng)縝密思維，提高綜合素質。,主要內容,數(shù)理邏輯 命題邏輯、一階謂詞邏輯 集合論 集合及其運算、二元關系與函數(shù) 代數(shù)結構 代數(shù)系統(tǒng)的基本概念、群、環(huán)、域、格與布爾代數(shù) 圖論 圖的基本概念、歐拉圖與哈密頓圖、樹、平面圖,數(shù)理邏輯和集合論作為兩塊基石奠定了離散數(shù)學乃至整個數(shù)

2、學理論的基礎，在上面生長著代數(shù)結構、序結構、拓撲結構和混合結構，這四大結構涵蓋與生長出許多數(shù)學分支，同時各分支間交叉融合，又形成了許多新的數(shù)學分支，形成了龐大的數(shù)學體系。,教材介紹,教材名稱：離散數(shù)學 編著者：楊炳儒，謝永紅，劉宏嵐，洪源，羅熊. 高等教育出版社 教材特色： 本教材以認知結構教學論（亦稱KM教學論）基本內涵為貫穿，即“雙圖融合”的教學機制；“教學回路”的教學模式；“立體結構”的教學內容；“三段論式”的教學方法。 具有全新的模式與體例，其演繹鋪展的路徑如下： 全書概述-篇引論（樹形類化圖）-章粗概圖-章應用概圖-按節(jié)展開（核心知識點；嵌入思維形式注記圖；每節(jié)小結）-章習題類化（常

3、見題典型解析）-章知識邏輯結構圖-擴展閱讀-習題-篇知識邏輯結構圖。,參考資源,屈婉玲，耿素云離散數(shù)學高等教育出版社 左孝陵，劉永才離散數(shù)學上海科學技術文獻出版社 中國高校計算機課程網離散數(shù)學課程討論,成績評定,平時成績（30%）+考試成績（70%） 平時成績組成： 上課出勤 作業(yè),第一篇 數(shù)理邏輯,Mathematical Logic,什么是數(shù)理邏輯,數(shù)理邏輯是用數(shù)學方法來研究推理規(guī)律的數(shù)學學科。 主要研究內容：推理 著重于推理過程是否正確 著重于語句之間的關系 主要研究方法：數(shù)學的方法 引進一套符號體系的方法。 所以數(shù)理邏輯又稱符號邏輯。 與計算機科學的聯(lián)系 計算機及計算機科學與數(shù)理邏輯有

4、著十分密切的關系。人們說數(shù)字電子計算機是數(shù)理邏輯與電子學結合的產物。,Dijkstra算法及其它,Dijkstra(迪杰斯特拉)算法（最短路徑算法） 有向圖中任意兩個頂點之間的最短路徑問題。 1972圖靈獎（ Dijkstra的話 “我現(xiàn)在年紀大了，搞了這么多年軟件，錯誤不知犯了多少，現(xiàn)在覺悟了，我想，假如我早年在數(shù)理邏輯上好好下點功夫的話，我就不會犯這么多錯誤，不少東西邏輯學家早就說了，可我不知道。要是我能年輕20歲的話我要回去學邏輯?！?程序算法數(shù)據(jù)； 算法邏輯控制,數(shù)理邏輯的知識體系,第一章命題邏輯,引言,邏輯主要研究推理過程，而推理過程必須依靠命題來表述。 在命題邏輯中，“命題”被看作

5、最小單位。 命題邏輯是數(shù)理邏輯中最基本、最簡單的部分。,命題邏輯部分知識邏輯概圖,命題邏輯在計算機科學技術相關領域的應用概圖,1.1.命題的基本概念,命題：具有真假意義的陳述句。,1.1.1 命題,什么是命題 推理是數(shù)理邏輯研究的中心問題，推理的前提和結論都是表達判斷的陳述句，因而表達判斷的陳述句構成了推理的基本單位，稱具有真假意義的陳述句為命題。 真值 命題總是具有一個確定真或假的“值”，稱為真值。 真值只有“真”和“假”兩種，分別記為True（真）和False（假），用1和0表示。 真值為真的命題稱為真命題，真值為假的命題稱為假命題。 判斷給定的句子是否為命題的基本步驟 首先應是陳述句；

6、其次要有唯一的真值。,1.1.1 命題,1）該吃早飯了！ 祈使句，不是命題。 2）多漂亮的花呀！ 感嘆句，不是命題。 3）明天你有什么安排嗎？ 疑問句，不是命題。 4）我正在說謊。 不是命題。因為無法判定其真假值，若假設它為假即我正在說謊，則意味著它的反為真，即我正在說實話，二者相矛盾；若假定它為真即我正在說實話，則意味著它的反為假，我正在說謊，二者也相矛盾。這其實是一個語義上的悖論。悖論不是命題。,1.1.1 命題,5） x-y2。 不是命題。因為x, y的值不確定，某些x, y使xy2為真，某些x, y使xy2為假，即xy2的真假隨x, y的值的變化而變化。因此xy2的真假無法確定，所以x

7、y2不是命題。 6）不在同一直線上的三點確定一個平面。 是命題。 7）鄭州是河南省的省會。 是命題。 8）下一個星期天會下雪。 是命題。因為它的真值雖然目前無法確定，但它是有唯一真值的。,1.1.1 命題,9）這碗湯味太淡了。 是命題。它的真假似乎不能唯一的判定，因為它因人而異，但這個語句的真假取決于說話人的主觀判斷（即可以認為此語句是“我認為這碗湯味太淡了”的縮寫）。 10）1011+1000=10011。 是命題，雖然當它表示的數(shù)是十進制數(shù)或其他非二進制數(shù)時此語句是假的，當它表示的數(shù)為二進制數(shù)時，此命題是真的。但是，這個語句畢竟是處于一系列語句中的一個特定位置上，由前后文關系，立即可以確定

8、它所表示的數(shù)是二進制數(shù)還是非二進制數(shù)，并且一個數(shù)不可能既是二進制數(shù)，又是其他非二進制數(shù)。故此語句是能分辨真假的。,1.1.2 命題的分類,命題可以分為兩種類型： 一種命題是不能再分解為更簡單命題的，稱作原子命題，又可稱為簡單命題； 另一種命題是通過聯(lián)結詞、標點符號將原子命題聯(lián)結而成，稱作復合命題。例如： 1）玫瑰是紅的并且紫羅蘭是藍的。 2）如果明天是個好天氣，我們就去野炊。 復合命題的基本性質是：其真值可以由其原子命題的真值以及它們復合成該復合命題的聯(lián)結方式確定。,1.1.3 命題標識符,命題標識符 為了能用數(shù)學的方法來研究命題之間的邏輯關系和推理，需要將命題符號化。 通常使用大寫字母P,

9、Q, 或用帶下標的大寫字母或用數(shù)字，如Ai，12等表示命題。 例如：P：今天下雨 意味著P表示“今天下雨”這個命題的名。 也可用數(shù)字表示此命題 例如：12：今天下雨 表示命題的符號稱為命題標識符，P和12就是命題標識符。,1.1.3 命題標識符,命題常元 一個命題標識符如果表示確定的簡單命題，就稱為命題常元。 命題變元 如果一個命題標識符只表示任意簡單命題的位置標志，就稱它為命題變元。 因為命題變元可以表示任意簡單命題，所以它不能確定真值，故命題變元不是命題。 指派 當命題變元P用一個特定的簡單命題取代時，P才能確定真值，這時也稱對P進行指派。,小結,只有陳述句才有可能是命題，但并不是所有的陳

10、述句都能成為命題。 本小節(jié)的思維形式注記圖：,1.2 聯(lián) 結 詞,聯(lián)結詞：確定復合命題的邏輯形式。,原子命題和聯(lián)結詞可以組合成復合命題。 聯(lián)結詞確定復合命題的邏輯形式，它來源于自然語言中的聯(lián)結詞，但與自然語言中的聯(lián)結詞有一定的差別； 從本質上講，這里討論的聯(lián)結詞只注重“真值”，而不顧及具體內容，故亦稱“真值聯(lián)結詞”。,1.2.1 否定聯(lián)結詞,定義1.1 設P為任一命題，復合命題“非P”（或“P的否定”）稱為P的否定式，記作P，讀作“非P”。稱為否定聯(lián)結詞。 P的邏輯關系為P不成立，P為真當且僅當P為假。 命題P的真值與其否定P的真值之間的關系,1.2.1 否定聯(lián)結詞,例1.2 設 P：這是一個

11、三角形 P：這不是一個三角形 例1.3 設 P：雪是白色的 P：雪不是白色的 在此例中，不能將P認為是命題“雪是黑色的”。因為雪不是白色的情況中有藍色、紅色等許多種可能。 在日常語言中，還可以用“非”、“不”、“沒有”、“無”、“并不”等多種方式表示否定。,1.2.2 合取聯(lián)結詞,定義1.2 設P,Q為任意二命題，復合命題“P并且Q”（或“P與Q”）稱為P和Q的合取式，記作PQ，讀作“P與Q”，稱為合取聯(lián)結詞。 PQ的邏輯關系為P與Q同時成立。PQ為真當且僅當P與Q同時為真。 命題PQ的真值與命題P和命題Q的真值之間的關系如表所示。,1.2.2 合取聯(lián)結詞,在自然語言中，還可用“并且”、“同時

12、”、“以及”、“既又”、“不但而且”、“雖然但是”等多種方式表達合取。 例1.4 設 P：今天打雷 Q：今天下雨 則 PQ：今天打雷且下雨 例1.5 設 P：小李在看書 Q：小李在聽音樂 則 PQ：小李一邊在看書，一邊在聽音樂,1.2.3 析取聯(lián)結詞,定義1.3設P,Q為任意二命題，復合命題“P或Q”稱為P和Q的析取式。記作PQ，讀作“P或Q”，稱為析取聯(lián)結詞。 PQ的邏輯關系為P與Q中至少一個成立。PQ為真當且僅當P與Q中至少一個為真。 命題PQ的真值與命題P和命題Q的真值之間的關系如表所示。,1.2.3 析取聯(lián)結詞,聯(lián)結詞是可兼或，因為當命題P和Q的真值都為真時，其值也為真。但自然語言中的

13、“或”既可以是“排斥或”也可以是“可兼或”。 例1.6 晚上我們去教室學習或去電影院看電影。（排斥或） 例1.7 他可能數(shù)學考了100分或英語考了100分。（可兼或） 例1.8 劉靜今天跑了200米或300米遠。（既不表示“可兼或”也不表示“排斥或”，它只是表示劉靜所跑的大概路程，因此它不是命題聯(lián)結詞，故例1.8是原子命題。）,1.2.3 析取聯(lián)結詞,由以上例子可以看出聯(lián)結詞“”和自然語言中的“或”的意義不完全相同。 與“”聯(lián)結詞相似，在自然語言中，通常是具有某種關系的兩條語句之間使用析取“或”，但在數(shù)理邏輯中，任何兩個命題都可以通過用析取“”聯(lián)結起來得到一個新命題。 例1.9 設 P：今天打

14、雷 Q：今天打閃 則 PQ：今天打雷或今天打閃 例1.10 設 P：今天是星期一 Q：今天天氣很好 則 PQ：今天是星期一或天氣很好,1.2.4 蘊涵聯(lián)結詞,定義1.4 設P,Q為任意二命題，復合命題“如果P，則Q”稱為P和Q的蘊涵式，記為P Q，讀作“如果P則Q”。 稱為蘊涵聯(lián)結詞。稱P為前件，Q為后件。 P Q的邏輯關系為Q是P的必要條件。P Q為假當且僅當P為真Q為假。 命題P Q的真值與命題P和命題Q的真值之間的關系如表所示。,1.2.4 蘊涵聯(lián)結詞,說明： 1）蘊涵聯(lián)結詞也稱為條件聯(lián)結詞?！叭绻鸓，則Q”也稱為P與Q的條件式。 2）蘊涵式的真值關系不太符合自然語言中的習慣，這一點請讀

15、者務必注意。 3）給定命題公式PQ，命題公式QP稱為PQ的逆換式；PQ稱為PQ的反換式；QP稱為它的逆反式。逆換式類似于中學數(shù)學里所學的命題的逆命題；反換式類似于否命題；逆反式類似于逆否命題。,1.2.4 蘊涵聯(lián)結詞,例1.11 甲對乙說：“如果今晚我們班上不開會，則我就和你一起去玩。”請問：在什么情形下，乙認為甲的這句話是假？ 解：如果班上沒有開會，甲與乙一起去玩，則自然認為甲說的話為真； 如果班上開會了，甲沒有與乙一起去玩，則沒有理由認為甲的話為假； 如果班上沒開會，甲沒有與乙一起去玩，則顯然認為甲的話為假； 如果班上開會了，但甲未參加而與乙一起去玩了，則也不能認為甲的話為假。 在自然語言

16、中，對于“如果則”這樣的語句，當前提為假時，結論不管真假，這個語句的意義是無法判斷的。因此在條件命題中，當前提為假時無論結論真值如何，其取值都為真的情況稱為“善意的推定”。,1.2.4 蘊涵聯(lián)結詞,例1.12 設 P：明天天氣晴朗 Q：我們就去郊游 則 P Q：如果明天天氣晴朗，我們就去郊游。 例1.13 設 P：x4 Q：x216 則 PQ：如果x4，則x216。 對于“如果P則Q”在日常語言中有多種表達方式，諸如“只要P就Q”、“當P則Q”、“因為P所以Q”、“P僅當Q”、“只有Q才P”、“除非Q才P”、“除非Q，否則非P”等。盡管敘述的方式表面看起來不同，但只要表示Q是P的必要條件，都可

17、以符號化為PQ。,1.2.5 等價聯(lián)結詞,定義1.5 設P,Q為任意二命題，復合命題“P當且僅當Q”稱為命題P和Q的等價式。記為P Q，讀作“P當且僅當Q”， 稱作等價聯(lián)結詞。 P Q的邏輯關系為P與Q互為充分必要條件。P Q為真當且僅當P與Q同時為真或同時為假。 命題P Q的真值與命題P和命題Q的真值之間的關系如表所示。,1.2.5 等價聯(lián)結詞,說明： 1）等價聯(lián)結詞也稱為雙條件聯(lián)結詞。“P當且僅當Q”也稱為P與Q的雙條件式。 2）“P當且僅當Q”的含義與“若P則Q，并且若Q則P”的含義相同，即P Q與( PQ )(QP)邏輯關系完全一樣。,1.2.5 等價聯(lián)結詞,例1.14 設 P：四邊形

18、ABCD是平行四邊形 Q：ABCD的對邊平行 則 P Q ：四邊形ABCD是平行四邊形，當且僅當它的對邊平行。 例1.15 設 P：53 Q：530 則 P Q：53當且僅當530 與聯(lián)結詞“”、“”、“”一樣，等價式“P Q”的構成也不要求命題P和命題Q之間存在任何聯(lián)系，它的真值僅僅與P和Q的真值有關。,1.2.5 復合命題的真值,使用多個聯(lián)結詞可以組成更復雜的復合命題，并可使用圓括號（、），（、）必須成對出現(xiàn)。 聯(lián)結詞的運算優(yōu)先順序為：（），；同一優(yōu)先級的運算從左至右順序進行。 例1.16 設 P：53 Q：2+2=4 R：烏鴉是白色的 求下列復合命題的真值： 1）（PQ）（PQ）R 2）

19、（QR）（PR) 解：P，Q，R的真值分別為1，1，0，根據(jù)運算規(guī)則算出1），2）的真值分別是0，1。,小結,在命題邏輯中，否定聯(lián)結詞、合取聯(lián)結詞和析取聯(lián)結詞這三個聯(lián)結詞就足夠了，但為了方便，還定義了其他的聯(lián)結詞。 析取聯(lián)結詞是可兼的也可稱為是相容的。 象初等代數(shù)的運算一樣，析取聯(lián)結詞和合取聯(lián)結詞也都滿足交換律和結合律。,小結,本小節(jié)的思維形式注記圖：,作業(yè),擴展閱讀：1.A,1.B 掌握聯(lián)結詞的定義 習題： 1：第一問,1.3 命題公式,命題公式：由命題變元、聯(lián)結詞和括號按照一定的規(guī)則 組成的字符串。,1.3.1 命題公式的定義,定義1.6 命題演算的合式公式，又稱命題公式（簡稱公式），是如

20、下遞歸定義的： 1）單個命題變元是合式公式，并簡稱為原子命題公式； 2）如果A是合式公式，那么(A)也是合式公式； 3）如果A, B都是合式公式，那么(AB ), (AB ), (A B ), (A B )都是合式公式； 4）當且僅當有限次地應用1), 2), 3)所得到的包含命題變元、聯(lián)結詞和括號的字符串是合式公式。 根據(jù)定義1.6可知，P, (P ), (P (PQ ), (PQ )P ), (P Q ) R )都是命題公式。而 (P ), (P Q, (P Q ) R )都不是命題公式。,1.3.1 命題公式的定義,注意： 這個合式公式的定義，是以遞歸形式給出的，其中1）稱為基礎，2）3

21、）稱為歸納，4）稱為界限。 命題公式本身不是命題，只有對公式中的每一個命題變元指派真值后它才是一個命題。 由命題變元、聯(lián)結詞和圓括號組成的字符串可構成命題公式，但并不是由這三類字符組成的每一個字符串都可以成為命題公式。,1.3.1 命題公式的定義,定義1.7 如果一個命題公式中總共包含有n個不同的命題變元，則稱其為n元命題公式。 例1.17 (PQ ) ( (QR )是三元命題公式 (P )是一元命題公式。 按照如下原則，可以減少公式中括號的數(shù)量： 1）省去最外層括號，如(P ), (P Q)可以分別寫為P和P Q； 2）規(guī)定5個聯(lián)結詞運算的優(yōu)先級順序為：, , ； 3）同級的聯(lián)結詞，按其出現(xiàn)

22、的先后次序（從左到右）。 例1.18 ( P1 (Q(R )S) P2 ) 可簡化為 P1 QRS P2 (P1Q)(R)S ) P2 ) 可簡化為 (P1Q)R S P2,1.3.2 命題公式的層次,定義1.8 1）若公式A是單個的命題變元，則稱A為0層公式。 2）稱A是n+1（n0）層公式是指下面情況之一： （1）A=B, B是n層公式； （2）A=BC,其中B, C分別為i層和j層公式，且n=max(i,j); （3）A=BC,其中B, C的層次同（2）; （4）A=BC,其中B, C的層次同（2）; （5）A=BC,其中B, C的層次同（2）; 3）若公式A的層次為k,則稱A是k層公式

23、。 例1.19 （PQ）R為3層公式。 (PQ）(RS) P) 為4層公式。,1.3.3 命題公式的賦值與真值表,定義1.9 設P1, P2, ,Pn是出現(xiàn)在公式A中的所有命題變元，給P1, P2, ,Pn各指派一個真值，稱為對A的一個賦值或解釋。若指派的一組值使A的值為1，則稱這組值為A的成真賦值。若使A的值為0，則稱這組值為A的成假賦值。 例1.20 給出公式：（PQ）R的兩種賦值，使公式的值分別為真和假。 解：1）將P解釋為：2是偶數(shù)，Q為3是偶數(shù)，R解釋為：2+3是偶數(shù)。顯然P,Q,R的真值分別是1，0，0，故（PQ）R的真值為0。 2）將P解釋為：2是偶數(shù)，Q解釋為3是偶數(shù)，R解釋為

24、2*3是偶數(shù)。顯然P,Q,R的真值分別是1，0，1，故（PQ）R的真值為1。,1.3.3 命題公式的賦值與真值表,本書中，含n個命題變元的命題公式的賦值形式作如下規(guī)定： 1）設A中含的命題變元為P1, P2, ,Pn，賦值12n(i為0或1)是指P1=1, P2=2Pn=n。 2）設A中含的命題變元為P, Q, R ，賦值12n(i為0或1)是指P=1, Q=2, ，即按字典順序賦值。,1.3.3 命題公式的賦值與真值表,定義1.10 設P1, P2, ,Pn是出現(xiàn)在公式A中的所有命題變元，將公式A在所有2n個賦值下的取值情況列成表，稱為A的真值表。 構造真值表的具體步驟： 1）找出公式中所含

25、的全體命題變元P1, P2, ,Pn(若無下標就按字典順序排列)，列出所有可能2n個賦值； 建議：賦值從000開始，然后按二進制加法依次寫出各賦值，直到111為止。 2）按從低到高的順序寫出公式的各個層次； 3）對應各個賦值，計算出各層次的真值，直到最后計算出公式的真值。,1.3.3 命題公式的賦值與真值表,例1.21 試構造(PQ) R的真值表。 解：第一步：列出全體命題變元P, Q, R及其所有的可能賦值；,例1.21 試構造(PQ) R的真值表。,第二步：從低到高的順序寫出公式的各個層次；,例1.21 試構造(PQ) R的真值表。,第三步：對應各個賦值計算出各層次的真值，直到最后計算出公

26、式的真值。,1.3.3 命題公式的賦值與真值表,例1.22 試構造(PP)(QQ)的真值表。 解：,1.3.3 命題公式的賦值與真值表,例1.23 試構造(PQ)QR的真值表。 解：,1.3.3 命題公式的賦值與真值表,定義1.11 設A為任一命題公式， 1）若A在它的所有賦值下取值均為真，則稱A是重言式或永真式； 2）若A在它的所有賦值下取值均為假，則稱A是矛盾式或永假式； 3）若A不是矛盾式，則稱A是可滿足式。 從定義1.11不難看出以下幾點： 1）A是可滿足式的邏輯等價定義是：A至少存在一個成真賦值。 2）重言式一定是可滿足式，但反之未必。因而，若公式A是可滿足式，且它至少存在一個成假賦

27、值，則稱A為非重言式的可滿足式。 3）重言式的否定是矛盾式，矛盾式的否定是重言式。,1.3.3 命題公式的賦值與真值表,真值表可用來判斷公式的類型： 1）若真值表最后一列（即命題公式對應的真值）全為1，則公式為重言式； 2）若真值表最后一列全為0，則公式為矛盾式； 3）若真值表最后一列中至少有一個1，則公式為可滿足式。 但當公式中命題變元較多時，真值表的方法計算量大，后面我們會介紹其他的方法。,1.3.4 命題的符號化,將一個用文字敘述的命題寫成由命題標識符、聯(lián)結詞和括號表示的命題公式的過程，稱為命題的符號化，或稱為命題的翻譯。 在數(shù)理邏輯中，進行推理的第一步就是將命題符號化。其大概步驟如下： 1）找出命題中所包含的原子命題并用命題符號表示； 2）確定命題中的連詞對應的聯(lián)結詞； 3）用正確的語法將原命