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

離散數(shù)學(xué) 復(fù)習(xí)提綱2012 11 第一章命題邏輯 命題符號化及聯(lián)結(jié)詞命題公式及分類等值演算會運用等值式 P9 證明兩個公式是否相等 判斷公式的類型 P33 34 7 9 對偶與范式求命題公式的 主 析取范式及用途 主 合取范式 P34 12 13 第一章命題邏輯 聯(lián)結(jié)詞全功能集復(fù)合聯(lián)結(jié)詞 N個命題變項可構(gòu)成的不等價的命題公式數(shù)推理理論推理的形式結(jié)構(gòu) 常用推理規(guī)則 P23 構(gòu)造證明法 直接證明法 附加前提證明法 反證法 P35 16 17 本章的應(yīng)用P11例11 P28例27 P35 15 第二章一階邏輯 一階邏輯基本概念 命題符號化一階邏輯公式 解釋及分類公式的解釋 代換實例 P54 5 13 一階邏輯等值式 前束范式量詞否定等值式 P46 量詞轄域收縮和擴張等值式 P47 量詞分配等值式 P47 48 第二章一階邏輯 一階邏輯推理理論有關(guān)量詞的推理規(guī)則 EI EG UI UG 及運用本章應(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 假言推理 涉及到命題的符號表示有關(guān)量詞的推理規(guī)則量詞的等值式 第三章集合的基本概念和運算 集合的基本概念集合之間的關(guān)系 E 冪集 文氏圖集合的基本運算會運用集合運算算律 P61 62 證明有關(guān)集合運算的命題成立與否 進行化簡集合中元素的計數(shù) 本章應(yīng)用 包含排斥原理 P64例9 10 P69例15 第四章二元關(guān)系與函數(shù) 集合的笛卡兒積與二元關(guān)系會計算和運用笛卡兒積的性質(zhì) P78 證明命題成立與否重要關(guān)系 E I L D 關(guān)系的運算dom ran fld R 1和合成R S 關(guān)系上的冪運算關(guān)系的性質(zhì) 判斷 證明 自反性 反自反性 對稱性 反對稱性 傳遞性關(guān)系運算與性質(zhì)的關(guān)系 P88 關(guān)系性質(zhì)的充要條件關(guān)系的閉包對稱閉包 自反閉包和傳遞閉包的定義和構(gòu)造方法 第四章二元關(guān)系與函數(shù) 等價關(guān)系和偏序關(guān)系等價類 商集 劃分及其關(guān)系哈斯圖 偏序集的特定元素及性質(zhì)函數(shù)的定義和性質(zhì)滿射 單射 雙射的性質(zhì) 判斷雙射函數(shù)的構(gòu)造函數(shù)的復(fù)合和反函數(shù)函數(shù)復(fù)合運算及性質(zhì) 反函數(shù)的計算本章應(yīng)用等價類及劃分 P117 24 構(gòu)造雙射函數(shù) P112例35 第七章圖的基本概念 無向圖及有向圖握手定理 推論及應(yīng)用圖的同構(gòu)條件及判斷完全圖 正則圖 生成子圖 自補圖通路 回路 圖的連通性無向圖和有向圖的連通性 點割集 邊割集圖的矩陣表示關(guān)聯(lián)矩陣 鄰接矩陣及性質(zhì)會計算圖中指定長度的通路和回路的個數(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 對偶圖的構(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 波蘭符號法與逆波蘭符號法 P198例9 4 第十章組合分析初步 加法法則和乘法法則基本排列組合的計數(shù)方法多重集的組合與排列公式 定理10 6 定理10 7 遞推方程的求解與應(yīng)用遞推方程的定義和求解過程 P213例13 14 算法的時間復(fù)雜度函數(shù)満足的遞推方程T n aT n b d n n bkT 1 1 第十章組合分析初步 當(dāng)d n c時 c為某個常數(shù) 代入上式得 當(dāng)d n cn時 c為某個常數(shù) 代入上式得 算法的時間復(fù)雜度函數(shù)満足的遞推方程T n aT n b d n n bkT 1 1 離散數(shù)學(xué) 試題結(jié)構(gòu) 卷面一 選擇題 10 二 填空題 15 三 計算題 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é) 試題舉例 三 運算題 25 1 用等值演算法判斷公式q p q 的類型解 q p q q p q q p q p q q p 0 0由最后一步可知 該式為矛盾式 2 計算集合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