離散數(shù)學(xué)復(fù)習(xí)提綱.ppt

離散數(shù)學(xué) 復(fù)習(xí)提綱2012 11 第一章命題邏輯 命題符號(hào)化及聯(lián)結(jié)詞命題公式及分類等值演算會(huì)運(yùn)用等值式 P9 證明兩個(gè)公式是否相等 判斷公式的類型 P33 34 7 9 對(duì)偶與范式求命題公式的 主 析取范式及用途 主 合取范式 P34 12 13 第一章命題邏輯 聯(lián)結(jié)詞全功能集復(fù)合聯(lián)結(jié)詞 N個(gè)命題變項(xiàng)可構(gòu)成的不等價(jià)的命題公式數(shù)推理理論推理的形式結(jié)構(gòu) 常用推理規(guī)則 P23 構(gòu)造證明法 直接證明法 附加前提證明法 反證法 P35 16 17 本章的應(yīng)用P11例11 P28例27 P35 15 第二章一階邏輯 一階邏輯基本概念 命題符號(hào)化一階邏輯公式 解釋及分類公式的解釋 代換實(shí)例 P54 5 13 一階邏輯等值式 前束范式量詞否定等值式 P46 量詞轄域收縮和擴(kuò)張等值式 P47 量詞分配等值式 P47 48 第二章一階邏輯 一階邏輯推理理論有關(guān)量詞的推理規(guī)則 EI EG UI UG 及運(yùn)用本章應(yīng)用例 證明 金屬都是導(dǎo)電體 銅是金屬 所以銅是導(dǎo)電體 解 令F x x是金屬 G x x是導(dǎo)電體 a 銅前提 x F x G x F a 結(jié)論 G a 證明 F a 前提引入 x F x G x 前提引入 F a G a UI G a 假言推理 涉及到命題的符號(hào)表示有關(guān)量詞的推理規(guī)則量詞的等值式 第三章集合的基本概念和運(yùn)算 集合的基本概念集合之間的關(guān)系 E 冪集 文氏圖集合的基本運(yùn)算會(huì)運(yùn)用集合運(yùn)算算律 P61 62 證明有關(guān)集合運(yùn)算的命題成立與否 進(jìn)行化簡(jiǎn)集合中元素的計(jì)數(shù) 本章應(yīng)用 包含排斥原理 P64例9 10 P69例15 第四章二元關(guān)系與函數(shù) 集合的笛卡兒積與二元關(guān)系會(huì)計(jì)算和運(yùn)用笛卡兒積的性質(zhì) P78 證明命題成立與否重要關(guān)系 E I L D 關(guān)系的運(yùn)算dom ran fld R 1和合成R S 關(guān)系上的冪運(yùn)算關(guān)系的性質(zhì) 判斷 證明 自反性 反自反性 對(duì)稱性 反對(duì)稱性 傳遞性關(guān)系運(yùn)算與性質(zhì)的關(guān)系 P88 關(guān)系性質(zhì)的充要條件關(guān)系的閉包對(duì)稱閉包 自反閉包和傳遞閉包的定義和構(gòu)造方法 第四章二元關(guān)系與函數(shù) 等價(jià)關(guān)系和偏序關(guān)系等價(jià)類 商集 劃分及其關(guān)系哈斯圖 偏序集的特定元素及性質(zhì)函數(shù)的定義和性質(zhì)滿射 單射 雙射的性質(zhì) 判斷雙射函數(shù)的構(gòu)造函數(shù)的復(fù)合和反函數(shù)函數(shù)復(fù)合運(yùn)算及性質(zhì) 反函數(shù)的計(jì)算本章應(yīng)用等價(jià)類及劃分 P117 24 構(gòu)造雙射函數(shù) P112例35 第七章圖的基本概念 無向圖及有向圖握手定理 推論及應(yīng)用圖的同構(gòu)條件及判斷完全圖 正則圖 生成子圖 自補(bǔ)圖通路 回路 圖的連通性無向圖和有向圖的連通性 點(diǎn)割集 邊割集圖的矩陣表示關(guān)聯(lián)矩陣 鄰接矩陣及性質(zhì)會(huì)計(jì)算圖中指定長(zhǎng)度的通路和回路的個(gè)數(shù) P165 最短路徑和關(guān)鍵路徑 本章應(yīng)用 P166例3 P168例4 P175 23 24 第八章一些特殊的圖 二部圖 完全二部圖 匹配 Hall定理及應(yīng)用 歐拉圖 半 歐拉圖的定義及判別方法 哈密頓圖 半 哈密頓圖的定義及存在性的充分條件和必要條件 平面圖平面圖的面 次數(shù)及它們之間的關(guān)系極大平面圖 極小非平面圖歐拉公式及推廣 定理8 10 8 11 平面圖判定定理 定理8 13 8 14 對(duì)偶圖的構(gòu)造和性質(zhì)本章應(yīng)用二部圖 P177例1 哈密頓回路 P189 13 平面圖 第九章樹 無向樹及生成樹無向樹 最小 生成樹基本回路系統(tǒng) 基本割集系統(tǒng)樹的性質(zhì)及有關(guān)定理 定理9 1 9 3 根樹及其應(yīng)用 本章應(yīng)用 有向樹及根樹 根樹的分類最優(yōu)樹 前綴碼與最佳前綴碼 P196例9 3 波蘭符號(hào)法與逆波蘭符號(hào)法 P198例9 4 第十章組合分析初步 加法法則和乘法法則基本排列組合的計(jì)數(shù)方法多重集的組合與排列公式 定理10 6 定理10 7 遞推方程的求解與應(yīng)用遞推方程的定義和求解過程 P213例13 14 算法的時(shí)間復(fù)雜度函數(shù)満足的遞推方程T n aT n b d n n bkT 1 1 第十章組合分析初步 當(dāng)d n c時(shí) c為某個(gè)常數(shù) 代入上式得 當(dāng)d n cn時(shí) c為某個(gè)常數(shù) 代入上式得 算法的時(shí)間復(fù)雜度函數(shù)満足的遞推方程T n aT n b d n n bkT 1 1 離散數(shù)學(xué) 試題結(jié)構(gòu) 卷面一 選擇題 10 二 填空題 15 三 計(jì)算題 25 四 證明題 20 五 應(yīng)用題 30 各章內(nèi)容比例第一章命題邏輯 15 第二章一階邏輯 10 第三章集合 10 第四章關(guān)系 函數(shù) 20 第七章圖論 15 第八章特殊圖 10 第九章樹 10 第十章組合分析 10 離散數(shù)學(xué) 試題舉例 一 選擇題 10 1 設(shè)S T M為任意集合 則下列命題中 命題真值是真的是 A 若S T S M 則T MB 若S T 則S TC 若 S T E 則S T D 是 的子集二 填空題 15 1 公式 p q r的成真賦值是 離散數(shù)學(xué) 試題舉例 三 運(yùn)算題 25 1 用等值演算法判斷公式q p q 的類型解 q p q q p q q p q p q q p 0 0由最后一步可知 該式為矛盾式 2 計(jì)算集合A 的冪集解 P A P 離散數(shù)學(xué) 試題舉例 四 證明題 20 證明A B C D A C B D證 任取 A C x A y C x B y D B D 離散數(shù)學(xué) 試題舉例 五 應(yīng)用題 30 證明 金屬都是導(dǎo)電體 銅是金屬 所以銅是導(dǎo)電體 解 令F x x是金屬 G x x是導(dǎo)電體 a 銅前提 x F x G x F a 結(jié)論 G a 證明 F a 前提引入 x F x G x