南京郵電大學(xué)《離散數(shù)學(xué)》考試復(fù)習(xí)重點精講.ppt
離散數(shù)學(xué)考試復(fù)習(xí)指南,南京郵電大學(xué) 計算機(jī)學(xué)院 離散數(shù)學(xué)課程組,1、填空題( 10空,20分) 2、判斷題(10小題,20分) 3、簡答題(5小題,40分) 4、證明題(2小題,20分),考試題型,命題的概念、命題的表示法 五個基本聯(lián)結(jié)詞的含義 命題公式與命題翻譯。 命題公式的真值表(萬能的真值表?。?重言式與蘊(yùn)含式的證明 主析取范式/主合取范式 命題公式的推理(真值表法、直接證法、間接證法(反證法+CP規(guī)則),第一章 命題邏輯,典型例題1-1,求公式(PQ)(QR)的主析取范式,典型例題1-2,法二:真值表如下:,所以主析取范式為: (PQR) (PQR) (PQR) (PQR),典型例題1-2,謂詞的概念與表示 量詞的含義 謂詞公式與翻譯 判斷謂詞公式的真值 謂詞演算的等價式與蘊(yùn)含式證明 謂詞演算的推理,第二章 謂詞邏輯,第二章 作業(yè),符號化下列命題并推證其結(jié)論:任何人如果他喜歡步行,他就不喜歡乘汽車;每一個人或者喜歡乘汽車或者喜歡騎自行車;有的人不愛騎自行車。因而有的人不愛步行。(請假設(shè) P(x): x喜歡步行, Q(x): x喜歡乘汽車,R(x): x喜歡騎自行車.),典型例題2-1,集合、關(guān)系、笛卡爾積、冪集的概念 集合的四種基本運算(交、并、相對補(bǔ)與絕對補(bǔ)、對稱差) 關(guān)系的表示方法(直積、關(guān)系矩陣、關(guān)系圖) 關(guān)系的五種基本性質(zhì)及其判定 關(guān)系的三種運算(復(fù)合、逆、閉包、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) 子格的判別 分配格(五元及五元以上分配格的判別) 有界格、補(bǔ)元、有補(bǔ)格 布爾格、布爾代數(shù)的基本概念,第六章 格與布爾代數(shù),第六章 格與布爾代數(shù),第六章 作業(yè),典型例題6-1,第七章 圖論,圖的基本概念(如簡單圖、完全圖、歐拉圖) 圖的基本性質(zhì)(如關(guān)于結(jié)點度數(shù)的三個基本定理) 圖的同構(gòu) 點割集、邊割集、點/邊連通度、距離 圖的連通性 圖的矩陣表示(鄰接矩陣、可達(dá)性矩陣) 歐拉圖(一筆畫問題) 哈密爾頓圖的判定,第七章 作業(yè),典型例題7-1,設(shè)有向圖G=,如右圖所示,求: (1)的鄰接矩陣。 (2)的可達(dá)矩陣。,答疑時間安排,答疑時間:元月10號中午12:00-13:20 答疑地點:行政南樓432計科系辦公室,??荚図樌?新年快樂!,