1、離 散 數(shù) 學(xué) 簡 介,離散：反義詞？,連續(xù),與離散有關(guān)的課程 1、連續(xù)量離散化：如數(shù)值積分、微分 離散量連續(xù)化：如數(shù)值逼近,數(shù)值計(jì)算 計(jì)算方法,計(jì)算機(jī)存儲(chǔ)數(shù)值按字節(jié)不連續(xù),2、離散量之間關(guān)系、運(yùn)算：離散數(shù)學(xué),離散數(shù)學(xué)的特點(diǎn)：,顧名思義，內(nèi)容又離又散，概念繁多。 離散數(shù)學(xué)的內(nèi)容： 數(shù)理邏輯、集合論（關(guān)系、函數(shù)）、 代數(shù)結(jié)構(gòu)、 圖論,離散數(shù)學(xué)與計(jì)算機(jī)課程,培養(yǎng)抽象思維、縝密概括能力 現(xiàn)實(shí)問題抽象為數(shù)學(xué)模型概括為程序的機(jī)械操作 先行課程: 高等數(shù)學(xué)、線性代數(shù) 后繼的課程：數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫系統(tǒng)、操作系統(tǒng)、數(shù)字電路、編譯原理、算法的分析與設(shè)計(jì)、人工智能、計(jì)算機(jī)網(wǎng)絡(luò)等。,課程情況,課程開設(shè)一學(xué)期，教學(xué)總

2、學(xué)時(shí)數(shù)為80學(xué)時(shí)。 學(xué)分?jǐn)?shù)為4學(xué)分。 本課程采用筆試考核方式， 根據(jù)教學(xué)大綱命題。,離散數(shù)學(xué)的教與學(xué),1提問式教學(xué)為主 : 考勤、考查、（促進(jìn)）考慮 2學(xué)習(xí)方法（三步曲） 具體（現(xiàn)實(shí)“記憶實(shí)例”） 抽象（性質(zhì)、定理） 具體（計(jì)算機(jī)實(shí)現(xiàn)） 3學(xué)習(xí)態(tài)度： 積極. “有用” “無用”？,教材、筆記和參考書,教材：詳細(xì)、流式 筆記：結(jié)構(gòu)、典型實(shí)例 參考書： 一般參考： 離散數(shù)學(xué)左孝凌等 上?？萍汲霭嫔?離散數(shù)學(xué)李俊鋒等 清華大學(xué)出版社 離散數(shù)學(xué)李盤林等 高教出版社 深入學(xué)習(xí)： 數(shù)理邏輯、集合論、 圖論、近世代數(shù),引 入,思維形式結(jié)構(gòu)：,邏輯？,思維的規(guī)律,邏輯學(xué)：,思維規(guī)律、思維形式結(jié)構(gòu),思維：,概念

3、判斷推理,在表象、概念的基礎(chǔ)上進(jìn)行分析、綜合、推理等認(rèn)識(shí)活動(dòng)的過程。,思維的表示：,語言、文字,形式化？,數(shù)學(xué)方法？,代數(shù)化、公式化,枚舉、歸納、演繹 反證 統(tǒng)計(jì)推理 ,實(shí)驗(yàn)形式：公理化體系 語言形式：推理小說、算命 形式化+數(shù)學(xué)方法數(shù)理邏輯,推理方法：,第一章 命 題 邏 輯 基 本 概 念,數(shù)理邏輯是用數(shù)學(xué)方法研究思維規(guī)律的一門學(xué)科。 數(shù)學(xué)方法是指：用一套數(shù)學(xué)的符號(hào)系統(tǒng)來描述和處理思維的形式與規(guī)律。因此，數(shù)理邏輯又稱為符號(hào)邏輯。 本章介紹數(shù)理邏輯中最基本的內(nèi)容命題邏輯： 首先引入命題、命題公式等概念。然后，在此基礎(chǔ)上研究命題公式間的等值關(guān)系和蘊(yùn)含關(guān)系，并給出推理規(guī)則，進(jìn)行命題演繹。,1.1

4、 命題與聯(lián)結(jié)詞 1.2 命題公式及其賦值,主要內(nèi)容,三、命題符號(hào)化,1.1 命題與聯(lián)結(jié)詞,一、命題的概念,二、命題聯(lián)結(jié)詞,例1 判斷下列語句是否是命題。 （1）空氣是人生存所必需的。 （2）請(qǐng)不要喧嘩! （3）南京是中國的首都。 （4）你吃飯了嗎？ （5）明年春節(jié)是個(gè)大晴天。 （6）啊，真美呀！,解 語句（1）,（3）,（5）是陳述句，也是命題 。,一個(gè)命題總是具有一個(gè)值，稱為“真值”。 “真值”只有“真”和“假”兩種， 記作：T（true）、F(false) 或 1、0,命題：能分辨真假的陳述句。,一、命題的概念,語句（2）、（4）、(6)不是陳述句，因此,不是命題 。,形式化： 命題用大或

5、小寫的字母p、q、或者帶下標(biāo)的字母來表示。本書采用小寫字母,例2 判斷下列陳述句是否是命題。 p：地球外的星球上也有人； q：小王是我的好朋友； r：101+1=110,解： p、q、r都是命題，因?yàn)槠湔嬷凳谴_定的。 只是p的真值現(xiàn)在不能確定； q的真值由時(shí)間、人物等因素確定； r的真值靠上下文確定，二進(jìn)制運(yùn)算為真否則為假。,所謂悖論, 是指對(duì)于命題q，如果從q為真, 可以推導(dǎo)出q為假, 又從q為非真推導(dǎo)出q為真, 我們就說命題q是一個(gè)悖論。 顯然如果從命題p可引出一個(gè)命題q, 而q是一個(gè)悖論, 那么p也是一個(gè)悖論。,一類特殊的陳述句 悖論,例：說謊悖論 有一個(gè)人斷言:“我正在說謊”。 我們要

6、問: 這個(gè)人是在說謊還是在講真話?,如果他在說謊，這表明他的斷言“我正在說謊”是謊話，也就是說他在講真話。即他說謊， 推出他是講真話(即沒有說謊)。,另一方面，如果他講真話， 這表明他的斷言“我正在說謊”是真話， 也就是說他正說謊話， 即他講真話, 推出他在說謊(即沒有講真話)。,理發(fā)師悖論 一個(gè)村上，有一個(gè)理發(fā)師公開宣布“他給而且只給村子中所有的自己不替自己理發(fā)的人理發(fā)”。 現(xiàn)在要問: 誰給這個(gè)理發(fā)師理發(fā)? 如果理發(fā)師的頭由別人給他理，也就是說理發(fā)師自己不替自己理發(fā)，那么按照規(guī)定，這位理發(fā)師應(yīng)該給自己理發(fā)。 另一方面,如果理發(fā)師的頭由自己理，那么按照規(guī)定， 理發(fā)師不能給自己理發(fā)。 也是一個(gè)悖

7、論：理發(fā)師的頭由別人來理, 不行；理發(fā)師的頭由自己理，也不行。,一、命題的概念,注意： 感嘆句、祈使句、疑問句都不是命題 陳述句中的悖論，判斷結(jié)果不惟一確定的不是命題,原子（簡單）命題 ：由簡單陳述句形成的命題。,復(fù)合命題：由一個(gè)或幾個(gè)原子命題(簡單陳述句)通過聯(lián)結(jié)詞聯(lián)接而構(gòu)成的命題。,例3 p：雪不是白的（并非雪是白的） q：李明既是三好學(xué)生又是足球隊(duì)員。 r：張平正在釣魚或者正在睡覺。 s：如果明天天氣晴朗，那么我們舉行運(yùn)動(dòng)會(huì)。,二、命題聯(lián)結(jié)詞,原始陳述符號(hào)化符號(hào)化陳述,定義五種聯(lián)結(jié)詞（或稱命題的五種運(yùn)算）,1. 否定“”,例4 設(shè)p：上海是一個(gè)城市； q：每個(gè)自然數(shù)都是偶數(shù)。 則有 p：

8、上海不是一個(gè)城市; q：并非每個(gè)自然數(shù)都是偶數(shù)。,定義1.1 設(shè) p為命題，復(fù)合命題“非p”(或“p的否定”)稱為p的否定式，記作p，符號(hào)稱作否定聯(lián)結(jié)詞. 規(guī)定p 為真當(dāng)且僅當(dāng)p為假.,2合取“”,規(guī)定： pq為真當(dāng)且僅當(dāng)命題p與q同時(shí)為真。,例5 設(shè)p：我們學(xué)習(xí)好。q：我們身體好。 則pq表示“我們學(xué)習(xí)好并且身體好?！?定義1.2 設(shè)p,q為兩個(gè)命題，復(fù)合命題“p并且q”(或“p與 q”)稱為p與q的合取式，記作pq，稱作合取聯(lián)結(jié)詞.,3. 析取“”,由定義可知， pq取值為真當(dāng)且僅當(dāng)p和q至少有一個(gè)取值為真。,定義1.3 設(shè)p, q為兩個(gè)命題，復(fù)合命題“p或q”稱作p與q的析取式，記作pq

9、，稱作析取聯(lián)結(jié)詞. 規(guī)定pq為假當(dāng)且僅當(dāng)p與q同時(shí)為假.,例6,將命題“他可能是100米或400米賽跑的冠軍?！狈?hào)化。,解令 p：他可能是100米賽跑冠軍； q：他可能是400米賽跑冠軍。,則命題可表示為pq。,注意：這是一種可兼（相容性）或。 將命題“他可能是海軍，也可能是空軍?！狈?hào)化。 解令 p：他可能是海軍； q：他可能是空軍。 則命題可以表示為pq嗎？,（pq）(pq),設(shè)p、q是兩個(gè)命題，p異或q是一個(gè)復(fù)合命題，記作pq。,4. 蘊(yùn)含（條件）“” 定義1.4 設(shè)p, q為兩個(gè)命題，復(fù)合命題“如果p, 則q”稱作p與q的蘊(yùn)涵式，記作pq，并稱p是蘊(yùn)涵式的前件，q為蘊(yùn)涵式的后件，稱作

10、蘊(yùn)涵聯(lián)結(jié)詞. 規(guī)定： pq為假當(dāng)且僅當(dāng)p為真q為假,當(dāng)p為真: q為假時(shí)，pq為假； q為真時(shí)，pq為真， 當(dāng)p為假: pq為真（善意推斷）。（不論q為真還假）,例8 將命題“如果我得到這本小說，那么我今夜就讀完它?！狈?hào)化。,解 令p：我得到這本小說； q：我今夜就讀完它。 于是上述命題可表示為pq。,例9 如果用p表示“我有車”，q表示“我去接你”，那么pq表示命題“如果我有車，那么我去接你”。注意：當(dāng)我有車時(shí)，若我去接了你，這時(shí)諾言pq 為真；若我沒去接你，則諾言pq為假。 當(dāng)我沒有車時(shí)，我無論去或不去接你均未食言，此時(shí)認(rèn)定pq為真。 當(dāng)p為假: pq為真，我們稱為善意推斷。,例“如果下

11、雨，那么我去接你”，這句話用p表示“天下雨”, q表示“我去接你”，那么pq表示命題就不確切了，因?yàn)檫@句話的潛臺(tái)詞是“如果不下雨，那么我就不去接你了”；而用p（pq）表示命題更確切。.,使用聯(lián)接詞，注意以下幾點(diǎn)：,自然語言 (1) pq 的邏輯關(guān)系：q為 p 的必要條件 (2) “如果 p, 則 q” 有很多不同的表述方法： 若p，就q ； 只要p，就q ； p僅當(dāng)q； 只有q 才p 除非q, 才p 或 除非q，否則非p， (3) 當(dāng) p 為假時(shí)，pq恒為真，稱為空證明 (4) 常出現(xiàn)的錯(cuò)誤：不分充分與必要條件, 自然語言，“如果p,則q”，前件和后件具有某種內(nèi)在聯(lián)系 ，在數(shù)理邏輯中，p與q可

12、以無聯(lián)系。, 在數(shù)學(xué)和其它科學(xué)中，“如果p,則q”，往往表達(dá)的是前件為真，后件也為真的推理關(guān)系。但在數(shù)理邏輯中，作為一種規(guī)定，當(dāng)p為假時(shí)，無論q是真還是假，p q均為真。,例10 設(shè) p：天冷，q：小王穿羽絨服，將下列命題符號(hào)化 (1) 只要天冷，小王就穿羽絨服. (2) 因?yàn)樘炖?，所以小王穿羽絨服. (3) 若小王不穿羽絨服，則天不冷. (4) 只有天冷，小王才穿羽絨服. (5) 除非天冷，小王才穿羽絨服. (6) 除非小王穿羽絨服，否則天不冷. (7) 如果天不冷，則小王不穿羽絨服. (8) 小王穿羽絨服僅當(dāng)天冷的時(shí)候.,蘊(yùn)涵聯(lián)結(jié)詞的實(shí)例,pq,注意： pq 與 qp 等值（真值相同） 總

13、結(jié)：肯定的推出不肯定的,pq,pq,qp,qp,pq,qp,qp,5等價(jià)（雙條件）“”,例11 非本倉庫工作人員，一律不得入內(nèi)。,解 令p：某人是倉庫工作人員；q：某人可以進(jìn)入倉庫。,則上述命題可表示為pq。,定義1.5 設(shè) p, q為兩個(gè)命題，復(fù)合命題“p當(dāng)且僅當(dāng)q”稱作p與q的等價(jià)式，記作pq，稱作等價(jià)聯(lián)結(jié)詞. 規(guī)定pq為真當(dāng)且僅當(dāng)p與q同時(shí)為真或同時(shí)為假. pq 的邏輯關(guān)系：p與q互為充分必要條件,例12 黃山比喜馬拉雅山高，當(dāng)且僅當(dāng)3是素?cái)?shù) 令p：黃山比喜馬拉雅山高；q：3是素?cái)?shù) 本例可符號(hào)化為pq,從漢語的語義看，p與q之間并無聯(lián)系，但就聯(lián)結(jié)詞的定義來看，因?yàn)镻的真值為假，q的真值為

14、真，所以pq的真值為假。,對(duì)于上述五種聯(lián)結(jié)詞“、 、 、” ，應(yīng)注意到： 復(fù)合命題的真值只取決于構(gòu)成它的各原子命題的真 值，而與這些原子命題的內(nèi)容含義無關(guān)。,三、命題符號(hào)化,利用聯(lián)結(jié)詞可以把許多日常語句符號(hào)化?；静襟E如下：,（1）從語句中分析出各原子命題，將它們符號(hào)化； （2）使用合適的命題聯(lián)結(jié)詞，把原子命題逐個(gè)聯(lián)結(jié)起來，組成復(fù)合命題的符號(hào)化表示。,聯(lián)結(jié)詞的優(yōu)先順序?yàn)椋?( )、 “ ”、 “” 、“” 、 “” 、 “” 對(duì)于同一優(yōu)先級(jí)的連接詞，先出現(xiàn)者先運(yùn)算。,命題符號(hào)化，無法表示“程度” P=“我一定去上學(xué)”， P是什么意思？,例13 將下列語句形式化。（1）我和他既是弟兄又是同學(xué)。（

15、2）如果我和他都不是學(xué)生，那么我們倆都不會(huì)去。,（1） p：我和他是弟兄，q：我和他是同學(xué)； 命題表示為pq。 （2） p:我是學(xué)生, q:他是學(xué)生, r:我會(huì)去, s:他會(huì)去。 命題表示為（p q）(rs) 要善于確定原子命題，不要把一個(gè)概念硬拆成幾個(gè)概念，或倒過來。,（3）我和你之間至少有一個(gè)要去海南島。 （4）我和你之間有一個(gè)要去海南島。,（3） p：我去海南島，q：你去海南島； 命題表示為pq。 （4） p：我去海南島，q：你去海南島； 命題表示為(pq)(pq)。 將語句形式化時(shí)，一定要注意形式化了的語句與原來的漢語語句有相同的語義。,（5）狗急跳墻。 （6）風(fēng)雨無阻，我去上學(xué)。,（

16、5） p：狗急了，q：狗跳墻，命題表示為 pq。 （6） p：天刮風(fēng)，q：天下雨，r：我去上學(xué)。命題表示為 (pqr) (pqr) (pqr) (pqr) 要善于識(shí)別自然語言中的聯(lián)結(jié)詞（有時(shí)它們被省略）。例如“狗急跳墻”一句，可理解為“如果狗急了，它就會(huì)跳墻”?！帮L(fēng)雨無阻，我去上學(xué)”一句，可理解為“不管是否刮風(fēng)、是否下雨我都去上學(xué)”。,（1）（pq） r；,例14 用符號(hào)形式表示下列命題 （1）如果明天早上下雨或下雪，那么我不去學(xué)校 （2）如果明天早上不下雨且不下雪，那么我去學(xué)校。 （3）如果明天早上不是雨夾雪，那么我去學(xué)校。 （4）只有當(dāng)明天早上不下雨且不下雪時(shí)，我才去學(xué)校。,解 令p：明天

17、早上下雨； q：明天早上下雪； r：我去學(xué)校。,（2）（p q）r；,（3）(pq）r；,（4）r（p q）（必要）,否定詞的位置要放準(zhǔn)確。 注意充分必要條件的區(qū)別。,例15 將下列命題符號(hào)化 （1）派小王或小李出差； （2）我們不能既劃船又跑步； （3） 如果你來了，那么他唱不唱歌將看你是否伴奏而定； （4） 如果李明是體育愛好者，但不是文藝愛好者，那么 李明不是文體愛好者；,（2） 令p：我們劃船；q：我們跑步。 則命題可 表示為 (pq）,（3） 令p：你來了；q：他唱歌；r：你伴奏。 則命題可表示為 p（qr）,（4） 令p：李明是體育愛好者；q：李明是文藝愛好者。 則命題可表示為（p

18、 q）（p q）,（1） 令p：派小王出差；q：派小李出差。 則 命題符號(hào)化為 pq,例16 如果晚上做完了作業(yè)并且沒有其它的事，他就會(huì)看電視或聽音樂。,解 令 p：他晚上做完了作業(yè)；q：他晚上有其它的事； r：他看電視； s：他聽音樂。,則該命題可表示為（pq）（rs）,解： 令p：上午下雨；q：我去看電影；r：我在家讀書。 則命題可表示為（p q）（pr）。,思考：假如上午不下雨，我去看電影，否則就在家里看書。,命題表示為（p q） （pr）為什么不行？,因?yàn)槭巧埔馔茢?，若下雨我不讀書也是真，反之亦然。,以后我們可以證明（5）還可以等價(jià)的表示為： ( p q) (p r) 或（p （p q

19、） （ p （pr）,本小節(jié)中p, q, r, 均表示命題.,聯(lián)結(jié)詞集為, , , , ，p, pq, pq, pq, pq為基本復(fù)合命題. 其中要特別注意理解pq的涵義. 反復(fù)使用, , , , 中的聯(lián)結(jié)詞組成更為復(fù)雜的復(fù)合命題. 設(shè) p : 是無理數(shù)，q:3是奇數(shù)， r: 蘋果是方的， s: 太陽繞地球轉(zhuǎn) 則復(fù)合命題 (pq) (rs) p) 是假命題.,小結(jié),聯(lián)結(jié)詞的運(yùn)算順序：, , , , , 同級(jí)按先出現(xiàn)者先運(yùn)算.,1.2 命題公式及其賦值,一 、 命題公式的概念,1. 命題常元 一個(gè)表示確定命題的小寫字母。,2命題變?cè)?一個(gè)沒有指定具體內(nèi)容的命題符號(hào)。也用小寫字母表示。,一個(gè)命題變

20、元當(dāng)沒有對(duì)其賦予內(nèi)容時(shí)，它的真值不能確定，一旦用一個(gè)具體的命題代入，它的真值就確定了。,3. 命題公式 命題公式（或合式公式也簡稱公式）是由0、1和命題變?cè)约懊}聯(lián)結(jié)詞按一定的規(guī)則產(chǎn)生的符號(hào)串。,定義（命題公式的遞歸定義。） （1） 0，1是命題公式； （2） 命題變?cè)敲}公式； （3） 如果A是命題公式，則A是命題公式； （4） 如果A和B是命題公式，則（AB）， （AB）,(AB）,(A B）也是命題公式； 有限次地利用上述（1）（4）而產(chǎn)生的符號(hào)串是命題公式。,例1 下列符號(hào)串是否為命題公式。 （1） p(qpr）； （2）（pq）（qr）,解 （1） 不是命題公式。 （2） 是命題

21、公式。,合式公式,定義1.6 合式公式（簡稱公式）的遞歸定義： (1) 單個(gè)命題變項(xiàng)和命題常項(xiàng)是合式公式, 稱作原子命題公式 (2) 若A是合式公式，則 (A)也是 (3) 若A, B是合式公式，則(AB),(AB),(AB),(AB)也是 (4) 只有有限次地應(yīng)用(1)(3) 形成的符號(hào)串才是合式公式,幾點(diǎn)說明： 歸納或遞歸定義, 元語言與對(duì)象語言, 外層括號(hào)可以省去,命題公式代表一個(gè)命題，但只有當(dāng)公式中的每一個(gè)命題變?cè)加靡粋€(gè)確定的命題代入時(shí)，命題公式才有確定的真值，成為命題。,定義設(shè)F為含有命題變?cè)猵1，p2，,pn的命題公式，對(duì)p1，p2，,pn分別指定一個(gè)真值,稱為對(duì)公式F的一組真值

22、指派（解釋、賦值）。,公式與其命題變?cè)g的真值關(guān)系，可以用真值表的方法表示出來。,n個(gè)命題變?cè)牡恼嬷抵概蓭追N ？,共2n,二、真值指派,例2 給出公式 F=(（pq）（qr）) (pr）的真值表。,解 公式F的真值表如下：,定義1.9 將命題公式A在所有賦值下取值的情況列成表, 稱作 A的真值表. 構(gòu)造真值表的步驟: (1) 找出公式中所含的全部命題變項(xiàng)p1, p2, , pn(若無下角標(biāo)則按字母順序排列), 列出2n個(gè)全部賦值, 從000開始, 按二進(jìn)制加法, 每次加1, 直至111為止. (2) 按從低到高的順序?qū)懗龉降母鱾€(gè)層次. (3) 對(duì)每個(gè)賦值依次計(jì)算各層次的真值, 直到最后計(jì)

23、算出公式 的真值為止.,真值表,(1) A = (pq) r,成真賦值:000,001,010,100,110; 成假賦值:011,101,111,真值表1,(2) B(qp)qp,成真賦值:00,01,10,11; 無成假賦值,真值表2,(3) C (pq)q的真值表,成假賦值:00,01,10,11; 無成真賦值,真值表3,定義 如果對(duì)于命題公式F所包含的命題變?cè)娜魏我唤M真值指派，F(xiàn)的真值恒為真，則稱公式F為重言式（或永真公式）。 相反地，若對(duì)于F所包含的命題變?cè)娜魏我唤M真值指派，F(xiàn)的真值恒為假，則稱公式F為矛盾式（或永假公式）。 如果至少有一組真值指派使公式F的真值為真，則稱F為可滿足公式 。,簡單的例子： P Q是可滿足公式 ， P P是重言式， P P是矛盾式,三、公式類型,例3 構(gòu)造下列命題公式的真值表，并判斷它們是何種類型的公式 （1）（ p q） （pq）； （2）（qp）（pq）；,解 令F1=（pq）（p q）， F2=（qp）（ pq） F1和F2的真值表如下：,判定性問題、計(jì)算問題、最優(yōu)化問題和構(gòu)造性問題,由上可知： F1是重言式 , F2是矛盾式。,(1) 豆沙包是由面粉和紅小豆做成的.