離散數(shù)學(xué)1.1-2.ppt

1 離散數(shù)學(xué) 2 課程簡介 離散數(shù)學(xué)課程是計算機(jī)專業(yè)和一些信息專業(yè)的必修課程 也是IEEE的教育委員會建議的計算機(jī)專業(yè)本科必修的課程 3 體系 4 簡介 離散數(shù)學(xué) DiscreteMathematics 是計算機(jī)專業(yè)的一門重要基礎(chǔ)課 它所研究的對象是離散數(shù)量關(guān)系和離散結(jié)構(gòu)數(shù)學(xué)結(jié)構(gòu)模型 5 主要內(nèi)容 數(shù)理邏輯 命題邏輯 一階邏輯 集合論 關(guān)系和函數(shù) 代數(shù)結(jié)構(gòu)圖論組合分析初步形式語言和自動機(jī)初步 6 教材與教學(xué)參考書 教材 耿素云 屈婉玲 張立昂 離散數(shù)學(xué) 第四版 清華大學(xué)出版社 2008 教學(xué)參考書 屈婉玲 耿素云 張立昂 離散數(shù)學(xué)題解 第三版 清華大學(xué)出版社 2008 7 如何學(xué)好離散數(shù)學(xué) 要學(xué)好這門課程 首先必須充分認(rèn)識到這門課程的上述特點(diǎn) 需要做到以下幾點(diǎn) 1認(rèn)真聽課 注意概念的理解 2獨(dú)立思考 大量練習(xí) 獨(dú)立完成教師布置的作業(yè) 3注重抽象思維能力的培養(yǎng) 數(shù)學(xué)與其他學(xué)科相比較具有較高的抽象性 而離散數(shù)學(xué)的抽象性特點(diǎn)更為顯著 它有著大量抽象的概念和抽象的推理 要學(xué)好這門課程必須具有較好的抽象思維能力 才能深入地掌握課程內(nèi)容 8 要求 認(rèn)真聽課 做好筆記曠課一次扣5分 遲到一次扣2分 3次曠課者取消本門課程的考試資格 獨(dú)立完成作業(yè) 作業(yè)缺交一次扣3分 期末成績 平時 30 期末考試 70 9 祝同學(xué)們愉快地學(xué)習(xí)離散數(shù)學(xué) 并能在今后的學(xué)習(xí)和工作中有一定的應(yīng)用 10 數(shù)理邏輯部分 第1章命題邏輯第2章一階邏輯 11 第1章命題邏輯 1 1命題符號化及聯(lián)結(jié)詞1 2命題公式及分類1 3等值演算1 4聯(lián)結(jié)詞全功能集1 5對偶與范式1 6推理理論 12 1 1命題符號化及聯(lián)結(jié)詞 命題與真值原子命題復(fù)合命題命題常項命題變項聯(lián)結(jié)詞 13 命題與真值 命題 判斷結(jié)果惟一的陳述句命題的真值 判斷的結(jié)果真值的取值 真與假真命題 真值為真的命題假命題 真值為假的命題注意 感嘆句 祈使句 疑問句都不是命題陳述句中的悖論以及判斷結(jié)果不惟一確定的也不是命題 14 例下列句子中那些是命題 1 是無理數(shù) 2 2 5 8 3 x 5 3 4 你有鉛筆嗎 5 這只兔子跑得真快呀 6 請不要講話 7 我正在說謊話 真命題 假命題 真值不確定 疑問句 感嘆句 祈使句 悖論 3 7 都不是命題 15 命題的分類 簡單命題 原子命題 簡單陳述句構(gòu)成的命題復(fù)合命題 由簡單命題與聯(lián)結(jié)詞按一定規(guī)則復(fù)合而成的命題 16 簡單命題符號化 用小寫英文字母p q r pi qi ri i 1 表示簡單命題用 1 表示真 用 0 表示假例如 令p 是有理數(shù) 則p的真值為0q 2 5 7 則q的真值為1 17 聯(lián)結(jié)詞與復(fù)合命題 續(xù) 聯(lián)結(jié)詞優(yōu)先級 同級按從左到右的順序進(jìn)行 18 聯(lián)結(jié)詞與復(fù)合命題 1 否定式與否定聯(lián)結(jié)詞 定義設(shè)p為命題 復(fù)合命題 非p 或 p的否定 稱為p的否定式 記作 p 符號 稱作否定聯(lián)結(jié)詞 并規(guī)定 p為真當(dāng)且僅當(dāng)p為假 19 聯(lián)結(jié)詞與復(fù)合命題 2 合取式與合取聯(lián)結(jié)詞 定義設(shè)p q為二命題 復(fù)合命題 p并且q 或 p與q 稱為p與q的合取式 記作p q 稱作合取聯(lián)結(jié)詞 并規(guī)定p q為真當(dāng)且僅當(dāng)p與q同時為真注意 描述合取式的靈活性與多樣性分清簡單命題與復(fù)合命題 20 例將下列命題符號化 1 王曉既用功又聰明 2 王曉不僅聰明 而且用功 3 王曉雖然聰明 但不用功 4 張輝與王麗都是三好生 5 張輝與王麗是同學(xué) 解令p 王曉用功 q 王曉聰明 則 1 p q 2 p q 3 p q 21 例 續(xù) 令r 張輝是三好學(xué)生 s 王麗是三好學(xué)生 4 r s 5 令t 張輝與王麗是同學(xué) t是簡單命題 說明 1 4 說明描述合取式的靈活性與多樣性 5 中 與 聯(lián)結(jié)的是兩個名詞 整個句子是一個簡單命題 22 聯(lián)結(jié)詞與復(fù)合命題 續(xù) 定義設(shè)p q為二命題 復(fù)合命題 p或q 稱作p與q的析取式 記作p q 稱作析取聯(lián)結(jié)詞 并規(guī)定p q為假當(dāng)且僅當(dāng)p與q同時為假 例將下列命題符號化 1 2或4是素數(shù) 2 2或3是素數(shù) 3 4或6是素數(shù) 4 小元元只能拿一個蘋果或一個梨 5 王曉紅生于1975年或1976年 3 析取式與析取聯(lián)結(jié)詞 23 解令p 2是素數(shù) q 3是素數(shù) r 4是素數(shù) s 6是素數(shù) 則 1 2 3 均為相容或 分別符號化為 p r p q r s 它們的真值分別為1 1 0 而 4 5 為排斥或 令t 小元元拿一個蘋果 u 小元元拿一個梨 則 4 符號化為 t u t u 令v 王曉紅生于1975年 w 王曉紅生于1976年 則 5 既可符號化為 v w v w 又可符號化為v w 為什么 24 聯(lián)結(jié)詞與復(fù)合命題 續(xù) 定義設(shè)p q為二命題 復(fù)合命題 如果p 則q 稱作p與q的蘊(yùn)涵式 記作p q 并稱p是蘊(yùn)涵式的前件 q為蘊(yùn)涵式的后件 稱作蘊(yùn)涵聯(lián)結(jié)詞 并規(guī)定 p q為假當(dāng)且僅當(dāng)p為真q為假 4 蘊(yùn)涵式與蘊(yùn)涵聯(lián)結(jié)詞 25 p q的邏輯關(guān)系 q為p的必要條件 如果p 則q 的不同表述法很多 若p 就q只要p 就qp僅當(dāng)q只有q才p除非q 才p或除非q 否則非p 當(dāng)p為假時 p q為真常出現(xiàn)的錯誤 不分充分與必要條件 聯(lián)結(jié)詞與復(fù)合命題 續(xù) 26 例設(shè)p 天冷 q 小王穿羽絨服 將下列命題符號化 1 只要天冷 小王就穿羽絨服 2 因為天冷 所以小王穿羽絨服 3 若小王不穿羽絨服 則天不冷 4 只有天冷 小王才穿羽絨服 5 除非天冷 小王才穿羽絨服 6 除非小王穿羽絨服 否則天不冷 7 如果天不冷 則小王不穿羽絨服 8 小王穿羽絨服僅當(dāng)天冷的時候 注意 p q與 q p等值 真值相同 p q p q q p p q q p q p p q q p 27 聯(lián)結(jié)詞與復(fù)合命題 續(xù) 定義設(shè)p q為二命題 復(fù)合命題 p當(dāng)且僅當(dāng)q 稱作p與q的等價式 記作p q 稱作等價聯(lián)結(jié)詞 并規(guī)定p q為真當(dāng)且僅當(dāng)p與q同時為真或同時為假 說明 1 p q的邏輯關(guān)系 p與q互為充分必要條件 2 p q為真當(dāng)且僅當(dāng)p與q同真或同假 5 等價式與等價聯(lián)結(jié)詞 28 例求下列復(fù)合命題的真值 1 2 2 4當(dāng)且僅當(dāng)3 3 6 2 2 2 4當(dāng)且僅當(dāng)3是偶數(shù) 3 2 2 4當(dāng)且僅當(dāng)太陽從東方升起 4 2 2 4當(dāng)且僅當(dāng)美國位于非洲 5 兩圓的面積相等的充要條件是它們的半徑相等 它們的真值分別為1 0 1 0 1 29 聯(lián)結(jié)詞與復(fù)合命題 續(xù) 聯(lián)結(jié)詞優(yōu)先級 同級按從左到右的順序進(jìn)行 30 聯(lián)結(jié)詞與復(fù)合命題 續(xù) 以上給出了5個聯(lián)結(jié)詞 組成一個聯(lián)結(jié)詞集合 聯(lián)結(jié)詞的優(yōu)先順序為 如果出現(xiàn)的聯(lián)結(jié)詞同級 又無括號時 則按從左到右的順序運(yùn)算 若遇有括號時 應(yīng)該先進(jìn)行括號中的運(yùn)算 注意 本書中使用的括號全為園括號 31 1 2命題公式及分類 命題變項與合式公式公式的賦值真值表命題的分類重言式矛盾式可滿足式 32 命題變項與合式公式 命題常項 簡單命題命題變項 真值不確定的陳述句定義合式公式 命題公式 公式 遞歸定義如下 1 單個命題常項或變項p q r pi qi ri 0 1是合式公式 2 若A是合式公式 則 A 也是合式公式 3 若A B是合式公式 則 A B A B A B A B 也是合式公式 4 只有有限次地應(yīng)用 1 3 形成的符號串才是合式公式說明 元語言與對象語言 外層括號可以省去 33 合式公式的層次 定義 1 若公式A是單個的命題變項 則稱A為0層公式 2 稱A是n 1 n 0 層公式是指下面情況之一 a A B B是n層公式 b A B C 其中B C分別為i層和j層公式 且n max i j c A B C 其中B C的層次及n同 b d A B C 其中B C的層次及n同 b e A B C 其中B C的層次及n同 b 34 合式公式的層次 續(xù) 例如公式p0層 p1層 p q2層 p q r3層 p q r r s 4層 35 公式的賦值 定義給公式A中的命題變項p1 p2 pn指定一組真值稱為對A的一個賦值或解釋成真賦值 使公式為真的賦值成假賦值 使公式為假的賦值說明 賦值 1 2 n之間不加標(biāo)點(diǎn)符號 i 0或1 A中僅出現(xiàn)p1 p2 pn 給A賦值 1 2 n是指p1 1 p2 2 pn nA中僅出現(xiàn)p q r 給A賦值 1 2 3 是指p 1 q 2 r 3 含n個變項的公式有2n個賦值 36 真值表 真值表 公式A在所有賦值下的取值情況列成的表例給出公式的真值表A q p q p的真值表 37 例