南京郵電大學(xué)《離散數(shù)學(xué)》考試復(fù)習(xí)重點(diǎn)精講.ppt

1、離散數(shù)學(xué)考試復(fù)習(xí)指南,南京郵電大學(xué) 計(jì)算機(jī)學(xué)院 離散數(shù)學(xué)課程組,1、填空題（ 10空，20分） 2、判斷題（10小題，20分） 3、簡(jiǎn)答題（5小題，40分） 4、證明題（2小題，20分,考試題型,命題的概念、命題的表示法 五個(gè)基本聯(lián)結(jié)詞的含義 命題公式與命題翻譯。 命題公式的真值表（萬(wàn)能的真值表?。?重言式與蘊(yùn)含式的證明 主析取范式/主合取范式 命題公式的推理（真值表法、直接證法、間接證法（反證法+CP規(guī)則,第一章 命題邏輯,典型例題1-1,求公式(PQ)(QR)的主析取范式,典型例題1-2,法二：真值表如下,所以主析取范式為： (PQR) (PQR) (PQR) (PQR,典型例題1-2,謂

2、詞的概念與表示 量詞的含義 謂詞公式與翻譯 判斷謂詞公式的真值 謂詞演算的等價(jià)式與蘊(yùn)含式證明 謂詞演算的推理,第二章 謂詞邏輯,第二章 作業(yè),符號(hào)化下列命題并推證其結(jié)論：任何人如果他喜歡步行，他就不喜歡乘汽車(chē)；每一個(gè)人或者喜歡乘汽車(chē)或者喜歡騎自行車(chē)；有的人不愛(ài)騎自行車(chē)。因而有的人不愛(ài)步行。（請(qǐng)假設(shè) P(x): x喜歡步行, Q(x): x喜歡乘汽車(chē)，R(x): x喜歡騎自行車(chē).,典型例題2-1,集合、關(guān)系、笛卡爾積、冪集的概念 集合的四種基本運(yùn)算（交、并、相對(duì)補(bǔ)與絕對(duì)補(bǔ)、對(duì)稱(chēng)差） 關(guān)系的表示方法（直積、關(guān)系矩陣、關(guān)系圖） 關(guān)系的五種基本性質(zhì)及其判定 關(guān)系的三種運(yùn)算（復(fù)合、逆、閉包、Warsha

3、ll算法） 等價(jià)關(guān)系的定義,第三章 集合與關(guān)系,第三章 集合與關(guān)系,等價(jià)類(lèi)、商集的概念 偏序關(guān)系 偏序關(guān)系的哈斯圖畫(huà)法 偏序集中一些元素的判別（最大最小元、極大極小元、上下確界,第三章 作業(yè),典型例題3-1,設(shè)A=-1,0,1,R=,是A上的二元關(guān)系，求關(guān)系的三種閉包運(yùn)算,自反閉包： r(R)=,，,； 對(duì)稱(chēng)閉包： s(R)= ,； 傳遞閉包： t(R)= ,第五章 代數(shù)系統(tǒng),代數(shù)系統(tǒng)的基本性質(zhì) 半群、獨(dú)異點(diǎn)、子群、群的概念 群的判定 循環(huán)群、交換群、有限循環(huán)群 同態(tài)、同構(gòu)、環(huán)與域 如何求解運(yùn)算的幺元、零元 代數(shù)系統(tǒng)中幺元與零元的關(guān)系,第五章 作業(yè),典型例題5-1,運(yùn)算*的單位元是 0，零元是

4、 -1，元素2的逆元是,則運(yùn)算*的單位元是 ？，零元是 ？，元素2的逆元是 ,第五章 作業(yè),典型例題5-2,設(shè)是一個(gè)代數(shù)系統(tǒng)，a*b=a+b+1，試證明是群,第六章 格和布爾代數(shù),格的定義 格同構(gòu) 子格的判別 分配格（五元及五元以上分配格的判別） 有界格、補(bǔ)元、有補(bǔ)格 布爾格、布爾代數(shù)的基本概念,第六章 格與布爾代數(shù),第六章 格與布爾代數(shù),第六章 作業(yè),典型例題6-1,第七章 圖論,圖的基本概念（如簡(jiǎn)單圖、完全圖、歐拉圖） 圖的基本性質(zhì)（如關(guān)于結(jié)點(diǎn)度數(shù)的三個(gè)基本定理） 圖的同構(gòu) 點(diǎn)割集、邊割集、點(diǎn)/邊連通度、距離 圖的連通性 圖的矩陣表示（鄰接矩陣、可達(dá)性矩陣） 歐拉圖（一筆畫(huà)問(wèn)題） 哈密爾頓圖的判定,第七章 作業(yè),典型例題7-1,設(shè)有向圖G=，如右圖所示，求： （1）的鄰接矩陣。 （2）的可