離散數(shù)學(xué) 2

1、離散數(shù)學(xué) 講義(01),福州大學(xué)計算機系 程紅舉 博士cscheng@fzu.edu.cn,教材及參考書籍,教材： 離散數(shù)學(xué)（國家十五規(guī)劃教材），耿素云，屈婉玲，高教出版社，2004.參考書：[1]離散數(shù)學(xué)教程，耿素云，屈婉玲，王捍貧，北京大學(xué)出版社，2002.[2] 離散數(shù)學(xué)及其應(yīng)用（譯著），袁崇義，屈婉玲，王捍貧，劉田譯，機械工業(yè)出版社，2002.[3] 離散數(shù)學(xué)習(xí)題解，張立昂，北京大學(xué)出版社，1990.,教學(xué)進度安排

2、,第1-15周，每周6學(xué)時，共80學(xué)時數(shù)理邏輯 24集合論 16 代數(shù)論 12圖論 28第9、12、13、18章不講,成績評定,書面作業(yè)占30%，隨機選擇3次作業(yè)期末考試占70%考試方法：閉卷考試內(nèi)容：課后習(xí)題不少于40%，但不一定位于書面作業(yè)中。,作業(yè),時間：課前交上次作業(yè)講解：每次作業(yè)都有課上講解要求：正確、完全、簡潔、清楚 Correct，Complete，Concise，Clear提示：獨立完

3、成作業(yè)，可以討論，但要杜絕抄襲,引言,課程簡介數(shù)學(xué)發(fā)展的三個階段離散數(shù)學(xué)的特點離散數(shù)學(xué)與計算機科學(xué)教學(xué)目標(biāo),數(shù)學(xué)發(fā)展的三個階段,離散數(shù)學(xué)的特點,研究對象----離散個體及其結(jié)構(gòu)研究思想----以集合和映射為工具、體現(xiàn)公理化和結(jié)構(gòu)的思想研究內(nèi)容----包含不同的數(shù)學(xué)分支，模塊化結(jié)構(gòu)數(shù)理邏輯：推理、形式化方法集合論：離散結(jié)構(gòu)的表示、描述工具代數(shù)結(jié)構(gòu)：離散結(jié)構(gòu)的代數(shù)模型圖論：離散結(jié)構(gòu)的關(guān)系模型組合數(shù)學(xué)：離散結(jié)構(gòu)的存在性、

4、計數(shù)、枚舉、優(yōu)化、設(shè)計離散概率（概率統(tǒng)計課程）,離散數(shù)學(xué)與計算機科學(xué)的關(guān)系,數(shù)理邏輯：人工智能、程序正確性證明、程序驗證等集合論：關(guān)系數(shù)據(jù)庫模型圖論：數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫模型、網(wǎng)絡(luò)模型等代數(shù)結(jié)構(gòu)：軟件規(guī)范、形式語義、編譯系統(tǒng)、編碼理論、密碼學(xué)、數(shù)據(jù)倉庫組合數(shù)學(xué)：算法分析與設(shè)計、編碼理論、容錯,離散數(shù)學(xué)的知識結(jié)構(gòu),,課程教學(xué)目標(biāo),掌握離散結(jié)構(gòu)的描述語言和分析工具為其它專業(yè)課程的學(xué)習(xí)打基礎(chǔ) 為掌握軟硬件模型的建模

5、與分析方法準備必要的數(shù)學(xué)工具學(xué)習(xí)現(xiàn)代數(shù)學(xué)的思想方法 培養(yǎng)分析問題解決問題的能力,數(shù)理邏輯,邏輯學(xué)： 研究推理的一門學(xué)科數(shù)理邏輯： 用數(shù)學(xué)方法研究推理的一門數(shù)學(xué)學(xué)科數(shù)理邏輯的內(nèi)容： 古典數(shù)理邏輯： 命題邏輯、謂詞邏輯 現(xiàn)代數(shù)理邏輯： 公理化集合論、遞歸論、模型論、證明論,-------- 一套符號體系 + 一組

6、規(guī)則,第一章 概要,學(xué)習(xí)目的本章首先要深刻理解命題的概念，理解原子命題和復(fù)合命題的關(guān)系，在此基礎(chǔ)之上理解邏輯聯(lián)結(jié)詞的定義，命題公式的定義和分類，最后熟練掌握并應(yīng)用真值表的構(gòu)造基本內(nèi)容：命題概念；邏輯聯(lián)結(jié)詞概念，復(fù)合命題和聯(lián)結(jié)詞的關(guān)系；命題符號化和翻譯合式公式概念及分類；構(gòu)造真值表判定公式類型,命題的概念,命題：能判斷真假的陳述句。作為命題的陳述句所表達的判斷結(jié)果稱為命題的真值，真值只取兩個值：真或假。真值為真的命題稱為

7、真命題，真值為假的命題稱為假命題。真命題表達的判斷正確，假命題表達的判斷錯誤。任何命題的真值都是唯一的。 判斷給定句子是否為命題，應(yīng)該分兩步：首先判定它是否為陳述句，其次判斷它是否有唯一的真值。 非命題語句：疑問句命令句感態(tài)句非命題陳述句,,例1.1：(1) 地球是圓的； 真的陳述句，是命題(2) 2+3=5； 真的陳述句，是命題(3) 你知道命題邏輯嗎？ 非陳述句，故非命題(4) 3-x=5； 陳述句,但真假隨x

8、 的變化而變化，非命題(5) 請安靜！ 非陳述句，故非命題(6) 火星表面的溫度是800°C；現(xiàn)時不知真假的陳述句，但只能要么真要么假，故是命題(7) 明天是晴天； 盡管要到第二天才能得知其真假，但的確是要么真要么假，故是命題(8) 我正在說謊； 無法得知其真假，這是悖論，故不是命題,,確定命題語句真值的幾點說明： 1、時間性 2、區(qū)域性 3、標(biāo)準性,命題抽象

9、,命題的符號表示：用小寫字母p,q,r,…,pi,qi,ri,…來表示命題。命題真值的表示：用1表示真，0表示假。,命題符號化,例：p: 4是素數(shù)。其真值為0.q: 4是無理數(shù)。其真值為0.r: 充分大的偶數(shù)是兩個素數(shù)之和。其真值為？.s: 2100年元旦是晴天。其真值為？.,復(fù)合命題的概念,有一些命題，它所有表達的不是簡單的命題，而是由簡單陳述句通過聯(lián)結(jié)詞聯(lián)結(jié)而成的陳述句。各種論述和推理中，出現(xiàn)的命題多數(shù)比例1.1中的命

10、題更加復(fù)雜。 例2是有理數(shù)是不對的.2是偶素數(shù).2或4是素數(shù).如果2是素數(shù)，則3也是素數(shù).2是素數(shù)當(dāng)且僅當(dāng)3也是素數(shù)。     上述命題都是通過諸如“或”，“如果……，則……”等連詞聯(lián)結(jié)而成，這樣命題，稱為復(fù)合命題。簡單命題（原子命題）：特點是不能分解為更簡單的陳述句。復(fù)合命題：原子命題或加上邏輯聯(lián)結(jié)詞組成的表達式成為復(fù)合命題（Compositional Proposition）

11、。數(shù)理邏輯中，通常通過“聯(lián)結(jié)詞”來構(gòu)成復(fù)合命題。,構(gòu)造復(fù)合命題的方式,例：2是素數(shù)。3是素數(shù)。2不是素數(shù)。2和3都是素數(shù)。2是素數(shù)或者3是素數(shù),p: 2是素數(shù)。,q: 3是素數(shù)。,非p,p且q,p或q,,例（繼）：如果2是素數(shù)，則3也是素數(shù)。2是素數(shù)當(dāng)且僅當(dāng)3也是素數(shù)。,P當(dāng)且僅當(dāng)q,如果p，則q.,否定“┐”,若p為命題,則p的否定"非p"也為命題，記為 ┐p,復(fù)合命題的真值可由其構(gòu)件命題的真

12、值表示，一般我們用所謂的真值表表示。否定聯(lián)結(jié)詞的真值表如下：,合取 “∧”,若p,q為命題，則p與q的合取“p且q”也為命題，記為p∧q。真值表如下：問題：“既……又……”、“不但……而且……”、“雖然……但是……”、“一面……一面……”等聯(lián)結(jié)而成地復(fù)合命題是否仍為合取式？還有哪些“合取詞”？,,例1.3 將下列命題符號化。   (1) 吳穎既用功又聰明。     

13、;(2) 吳穎不僅用功而且聰明。     (3) 吳穎雖然聰明，但不用功。     (4) 張輝和王麗都是三好學(xué)生。     (5) 張輝與王麗是同學(xué)。    解 首先將原子命題符號化：        

14、 p: 吳穎用功。         q: 吳穎聰明。         r: 張輝是三好學(xué)生。         s: 王麗是三好學(xué)生。     

15、    t: 張輝與王麗是同學(xué)。     (1)到(4)都是復(fù)合命題，它們使用的聯(lián)結(jié)詞表面看來各不相同，但都是合取聯(lián)結(jié)詞，都應(yīng)符號化為∧，(1)到(4)分別符號化為p∧q，p∧q，q∧┐p，r∧s.在(5)中，雖然也使用了聯(lián)結(jié)詞“與”，但這個聯(lián)結(jié)詞“與”是聯(lián)結(jié)該句主語的，而整個句子仍是簡單陳述句，所以(5)是原子命題，符號化為t.,析取“∨”,若p,q為命

16、題，則p,q的析取“p或q”也是命題，記為p∨q。真值表如下：注意：按定義在析取式p∨q中，若p，q都為真，則p∨q為真。 “或”還有另外一種用法：當(dāng)p，q都為真時，析取起來為假。前者稱為相容或，后者稱為排斥或(排異或)。,,例1.4 將下列命題符號化。     (1) 張曉靜愛唱歌或愛聽音樂。  解 在解題時，先將原子命題符號化。   

17、60; p：張曉靜愛唱歌。        q：張曉靜愛聽音樂。     顯然(1)中“或”為相容或，即p與q可以同時為真，符號化為p∨q.,,例1.4 將下列命題符號化。        (2) 張曉靜是江西人或安徽人。解 r

18、：張曉靜是江西人。        s：張曉靜是安徽人。      易知，(2)中“或”應(yīng)為排斥或，但r與s不能同時為真，因而也可以符號化為r∨s.,,例1.4 將下列命題符號化。     (3) 張曉靜只能挑選202或203房間。 解 t：張曉靜挑選202房

19、間。        u：張曉靜挑選203房間。    由題意可知，(3)中“或”應(yīng)為排斥或。t，u的聯(lián)合取值情況有四種：同真，同假，一真一假(兩種情況)。如果也符號化為t∨u，張曉靜就可能同時得到兩個房間，這違背題意。因而不能符號化為t∨u.如何達到只能挑一個房間的要求呢？可以使用多個聯(lián)結(jié)詞，符號化為 

20、;       (t∧┐u)∨(┐t∧u)此復(fù)合命題為真當(dāng)且僅當(dāng)t，u中一個為真，一個為假，它準確地表達了(3)的要求。當(dāng)t為真u為假時，張曉靜得到202房間，t為假u為真時，張曉靜得到203房間，其它情況下，她得不到任何房間。    可見，相斥或可由相容或表示出來。,蘊涵“→”,若p,q為命題，則“p與q的蘊涵式” “若p則q”

21、亦為命題，記為p→q。并稱p為蘊涵式的前件，q為蘊涵式的后件。其真值表如下：p→q的邏輯關(guān)系表示q是p的必要條件。,,例1.5 將下列命題符號化，并指出各復(fù)合命題的真值：     (1) 如果3+3＝6，則雪是白的。     (2) 如果3+3≠6，則雪是白的。     (3) 如果3+3＝6，則雪不是白

22、的。     (4) 如果3+3≠6，則雪不是白的。 解 令p：3+3＝6，p的真值為1。         q：雪是白色的，q的真值也為1。     (1)到(4)的符號化形式分別為p→q，┐p→q，p→┐q，┐p→┐q.這四個復(fù)合命題的真值分別為

23、1，1，0，1。以上四個蘊涵式的前件p與后件q沒有什么內(nèi)在的聯(lián)系。,,注意： 在使用聯(lián)結(jié)詞→時，要特別注意以下幾點：     1．在自然語言里，特別是在數(shù)學(xué)中，q是p的必要條件有許多不同的敘述方式。例如，“只要p，就q”，“因為p，所以q”，“p僅當(dāng)q”，“只有q才p”，“除非q才p”，“除非q，否則非p”等等。以上各種敘述方式表面看來有所不同，但都表達的是q是p的必要條件，因而所用聯(lián)結(jié)詞均應(yīng)

24、符號化為→，上述各種敘述方式都應(yīng)符號化為p→q.     2．在自然語言中，“如果p，則q”中的前件p與后件q往往具有某種內(nèi)在聯(lián)系。而在數(shù)理邏輯中，p與q可以無任何內(nèi)在聯(lián)系。     3．在數(shù)學(xué)或其它自然科學(xué)中，“如果p，則q”往往表達的是前件p為真，后件q也為真的推理關(guān)系。但在數(shù)理邏輯中，作為一種規(guī)定，當(dāng)p為假時，無論q是真是假，p→q均為真。也就是說

25、，只有p為真q為假這一種情況使得復(fù)合命題p→q為假。,等價“?”,若p,q為命題，則p與q的等價式 “p等價于q”亦為命題，記為p?q。真值表如下：p?q的邏輯關(guān)系為p與q互為充分必要條件。,,例1.6 將下列命題符號化，并討論它們的真值。     (3) 若兩圓A，B的面積相等，則它們的半徑相等；反之亦然。     (4) 當(dāng)王小紅心情愉快時，她

26、就唱歌；反之，當(dāng)她唱歌時，一定心情愉快。 解 令s：兩圓A，B面積相等，       t：兩圓A，B的半徑相等，     則將(3)符號化為s ? t，雖然不知道s，t的真值，但由s與t的內(nèi)在聯(lián)系可知，st的真值為1.     令u：王小紅心情愉快，   

27、0;   v：王小紅唱歌，     則將(4)符號化為u ? v.其真值要由具體情況而定。,,以上定義了五種最基本、最常用、也是最重要的聯(lián)結(jié)詞┐，∧，∨，→，?，將它們組成一個集合{┐，∧，∨，→，}，稱為一個聯(lián)結(jié)詞集。其中┐為一元聯(lián)結(jié)詞，其余的都是二元聯(lián)結(jié)詞。,聯(lián)結(jié)符小結(jié),,,,,p,,,,,p,,更復(fù)雜的復(fù)合命題,多次使用聯(lián)結(jié)符運算規(guī)則：優(yōu)先級順序（），┐

28、 ， ∧，∨ ，→ ， ?,復(fù)合命題符號化步驟,􀁺 1) 找出各個原子命題，并逐個符號化；􀁺 2) 找出各個連接詞，符號成相應(yīng)聯(lián)結(jié)詞；􀁺 3) 用聯(lián)結(jié)詞將各原子命題逐個聯(lián)結(jié)起來；,,例1.7 將下列命題符號化：(1) 李明是計算機系的學(xué)生，他住在312 室或313 室．解 (1)首先用字母表示簡單命題．p：李明是計算機系的學(xué)生．q：李明住在312 室．r：李明住在31

29、3 室．該復(fù)合命題可表示為p∧((q∧┐r)∨(┐q∧r)) 。,,例1.8 令 p：北京比天津人口多。              q：2+2＝4.         r：烏鴉是白色的。    

30、60;求下列復(fù)合命題的真值：    (1) ((┐p∧q)∨(p∧┐q))→r     (2) (q∨r)→(p→┐r)     (3) (┐p∨r)(p∧┐r)    解 p，q，r的真值分別為1，1，0，容易算出(1)，(2)，(3)的真值分別為1，1，0。,小結(jié)：,命