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

1 離散數(shù)學(xué) 2 課程簡介 離散數(shù)學(xué)課程是計(jì)算機(jī)專業(yè)和一些信息專業(yè)的必修課程 也是IEEE的教育委員會(huì)建議的計(jì)算機(jī)專業(yè)本科必修的課程 3 體系 4 簡介 離散數(shù)學(xué) DiscreteMathematics 是計(jì)算機(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)圖論組合分析初步形式語言和自動(dòng)機(jī)初步 6 教材與教學(xué)參考書 教材 耿素云 屈婉玲 張立昂 離散數(shù)學(xué) 第四版 清華大學(xué)出版社 2008 教學(xué)參考書 屈婉玲 耿素云 張立昂 離散數(shù)學(xué)題解 第三版 清華大學(xué)出版社 2008 7 如何學(xué)好離散數(shù)學(xué) 要學(xué)好這門課程 首先必須充分認(rèn)識(shí)到這門課程的上述特點(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分 期末成績 平時(shí) 30 期末考試 70 9 祝同學(xué)們愉快地學(xué)習(xí)離散數(shù)學(xué) 并能在今后的學(xué)習(xí)和工作中有一定的應(yīng)用 10 數(shù)理邏輯部分 第1章命題邏輯第2章一階邏輯 11 第1章命題邏輯 1 1命題符號(hào)化及聯(lián)結(jié)詞1 2命題公式及分類1 3等值演算1 4聯(lián)結(jié)詞全功能集1 5對偶與范式1 6推理理論 12 1 1命題符號(hào)化及聯(lián)結(jié)詞 命題與真值原子命題復(fù)合命題命題常項(xiàng)命題變項(xiàng)聯(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 簡單命題符號(hào)化 用小寫英文字母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 符號(hào) 稱作否定聯(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同時(shí)為真注意 描述合取式的靈活性與多樣性分清簡單命題與復(fù)合命題 20 例將下列命題符號(hào)化 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é)的是兩個(gè)名詞 整個(gè)句子是一個(gè)簡單命題 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同時(shí)為假 例將下列命題符號(hào)化 1 2或4是素?cái)?shù) 2 2或3是素?cái)?shù) 3 4或6是素?cái)?shù) 4 小元元只能拿一個(gè)蘋果或一個(gè)梨 5 王曉紅生于1975年或1976年 3 析取式與析取聯(lián)結(jié)詞 23 解令p 2是素?cái)?shù) q 3是素?cái)?shù) r 4是素?cái)?shù) s 6是素?cái)?shù) 則 1 2 3 均為相容或 分別符號(hào)化為 p r p q r s 它們的真值分別為1 1 0 而 4 5 為排斥或 令t 小元元拿一個(gè)蘋果 u 小元元拿一個(gè)梨 則 4 符號(hào)化為 t u t u 令v 王曉紅生于1975年 w 王曉紅生于1976年 則 5 既可符號(hào)化為 v w v w 又可符號(hào)化為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為假時(shí) p q為真常出現(xiàn)的錯(cuò)誤 不分充分與必要條件 聯(lián)結(jié)詞與復(fù)合命題 續(xù) 26 例設(shè)p 天冷 q 小王穿羽絨服 將下列命題符號(hào)化 1 只要天冷 小王就穿羽絨服 2 因?yàn)樘炖?所以小王穿羽絨服 3 若小王不穿羽絨服 則天不冷 4 只有天冷 小王才穿羽絨服 5 除非天冷 小王才穿羽絨服 6 除非小王穿羽絨服 否則天不冷 7 如果天不冷 則小王不穿羽絨服 8 小王穿羽絨服僅當(dāng)天冷的時(shí)候 注意 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的等價(jià)式 記作p q 稱作等價(jià)聯(lián)結(jié)詞 并規(guī)定p q為真當(dāng)且僅當(dāng)p與q同時(shí)為真或同時(shí)為假 說明 1 p q的邏輯關(guān)系 p與q互為充分必要條件 2 p q為真當(dāng)且僅當(dāng)p與q同真或同假 5 等價(jià)式與等價(jià)聯(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個(gè)聯(lián)結(jié)詞 組成一個(gè)聯(lián)結(jié)詞集合 聯(lián)結(jié)詞的優(yōu)先順序?yàn)?如果出現(xiàn)的聯(lián)結(jié)詞同級 又無括號(hào)時(shí) 則按從左到右的順序運(yùn)算 若遇有括號(hào)時(shí) 應(yīng)該先進(jìn)行括號(hào)中的運(yùn)算 注意 本書中使用的括號(hào)全為園括號(hào) 31 1 2命題公式及分類 命題變項(xiàng)與合式公式公式的賦值真值表命題的分類重言式矛盾式可滿足式 32 命題變項(xiàng)與合式公式 命題常項(xiàng) 簡單命題命題變項(xiàng) 真值不確定的陳述句定義合式公式 命題公式 公式 遞歸定義如下 1 單個(gè)命題常項(xiàng)或變項(xiàng)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 形成的符號(hào)串才是合式公式說明 元語言與對象語言 外層括號(hào)可以省去 33 合式公式的層次 定義 1 若公式A是單個(gè)的命題變項(xiàng) 則稱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中的命題變項(xiàng)p1 p2 pn指定一組真值稱為對A的一個(gè)賦值或解釋成真賦值 使公式為真的賦值成假賦值 使公式為假的賦值說明 賦值 1 2 n之間不加標(biāo)點(diǎn)符號(hào) 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個(gè)變項(xiàng)的公式有2n個(gè)賦值 36 真值表 真值表 公式A在所有賦值下的取值情況列成的表例給出公式的真值表A q p q p的真值表 37 例