南京郵電大學《離散數(shù)學》考試復習重點精講.ppt

離散數(shù)學考試復習指南,南京郵電大學 計算機學院 離散數(shù)學課程組,1、填空題（ 10空，20分） 2、判斷題（10小題，20分） 3、簡答題（5小題，40分） 4、證明題（2小題，20分）,考試題型,命題的概念、命題的表示法 五個基本聯(lián)結(jié)詞的含義 命題公式與命題翻譯。 命題公式的真值表（萬能的真值表！） 重言式與蘊含式的證明 主析取范式/主合取范式 命題公式的推理（真值表法、直接證法、間接證法（反證法+CP規(guī)則）,第一章 命題邏輯,典型例題1-1,求公式(PQ)(QR)的主析取范式,典型例題1-2,法二：真值表如下：,所以主析取范式為： (PQR) (PQR) (PQR) (PQR),典型例題1-2,謂詞的概念與表示 量詞的含義 謂詞公式與翻譯 判斷謂詞公式的真值 謂詞演算的等價式與蘊含式證明 謂詞演算的推理,第二章 謂詞邏輯,第二章 作業(yè),符號化下列命題并推證其結(jié)論：任何人如果他喜歡步行，他就不喜歡乘汽車；每一個人或者喜歡乘汽車或者喜歡騎自行車；有的人不愛騎自行車。因而有的人不愛步行。（請假設(shè) P(x): x喜歡步行, Q(x): x喜歡乘汽車，R(x): x喜歡騎自行車.）,典型例題2-1,集合、關(guān)系、笛卡爾積、冪集的概念 集合的四種基本運算（交、并、相對補與絕對補、對稱差） 關(guān)系的表示方法（直積、關(guān)系矩陣、關(guān)系圖） 關(guān)系的五種基本性質(zhì)及其判定 關(guān)系的三種運算（復合、逆、閉包、Warshall算法） 等價關(guān)系的定義,第三章 集合與關(guān)系,第三章 集合與關(guān)系,等價類、商集的概念 偏序關(guān)系 偏序關(guān)系的哈斯圖畫法 偏序集中一些元素的判別（最大最小元、極大極小元、上下確界）,第三章 作業(yè),典型例題3-1,設(shè)A=-1,0,1,R=,是A上的二元關(guān)系，求關(guān)系的三種閉包運算,自反閉包： r(R)=,，,； 對稱閉包： s(R)= ,； 傳遞閉包： t(R)= ,。,第五章 代數(shù)系統(tǒng),代數(shù)系統(tǒng)的基本性質(zhì) 半群、獨異點、子群、群的概念 群的判定 循環(huán)群、交換群、有限循環(huán)群 同態(tài)、同構(gòu)、環(huán)與域 如何求解運算的幺元、零元 代數(shù)系統(tǒng)中幺元與零元的關(guān)系,第五章 作業(yè),典型例題5-1,運算*的單位元是 0，零元是 -1，元素2的逆元是,則運算*的單位元是 ？，零元是 ？，元素2的逆元是 ？,第五章 作業(yè),典型例題5-2,設(shè)是一個代數(shù)系統(tǒng)，a*b=a+b+1，試證明是群,第六章 格和布爾代數(shù),格的定義 格同構(gòu) 子格的判別 分配格（五元及五元以上分配格的判別） 有界格、補元、有補格 布爾格、布爾代數(shù)的基本概念,第六章 格與布爾代數(shù),第六章 格與布爾代數(shù),第六章 作業(yè),典型例題6-1,第七章 圖論,圖的基本概念（如簡單圖、完全圖、歐拉圖） 圖的基本性質(zhì)（如關(guān)于結(jié)點度數(shù)的三個基本定理） 圖的同構(gòu) 點割集、邊割集、點/邊連通度、距離 圖的連通性 圖的矩陣表示（鄰接矩陣、可達性矩陣） 歐拉圖（一筆畫問題） 哈密爾頓圖的判定,第七章 作業(yè),典型例題7-1,設(shè)有向圖G=，如右圖所示，求： （1）的鄰接矩陣。 （2）的可達矩