離散數(shù)學期末復習要點與重點

1、離散數(shù)學期末復習要點與重點離散數(shù)學是中央廣播電視大學開放教育本科電氣信息類計算機科學與技術專業(yè)的一門統(tǒng)設必修學位課程，共72 學時，開設一學期該課程的主要內容包括：集合論、圖論、數(shù)理邏輯等下面按章給出復習要點與重點第 1 章集合及其運算復習要點1理解集合、元素、集合的包含、子集、相等，以及全集、空集和冪集等概念，熟練掌握集合的表示方法具有確定的，可以區(qū)分的若干事物的全體稱為集合 ，其中的事物叫元素.集合的表示方法：列舉法和描述法. 注意：集合的表示中元素不能重復出現(xiàn)，集合中的元素無順序之分掌握集合包含(子集 )、真子集、集合相等等概念注意：元素與集合，集合與子集，子集與冪集，與(), 空集與所

2、有集合等的關系.空集，是惟一的，它是任何集合的子集集合 a 的冪集 p(a)axx， a 的所有子集構成的集合若a n，則p(a) =2n2熟練掌握集合a 和 b 的并 ab，交 ab，補集a( a 補集總相對于一個全集).差集ab，對稱差， a b(ab)(ba)，或 ab (ab)（ab）等運算，并會用文氏圖表示掌握集合運算律( 見教材第911 頁)( 運算的性質 ). 3掌握用集合運算基本規(guī)律證明集合恒等式的方法集合的運算問題：其一是進行集合運算；其二是運算式的化簡；其三是恒等式證明證明方法有二：(1)要證明 ab，只需證明ab，又 a b；(2)通過運算律進行等式推導重點 ：集合概念，

3、集合的運算，集合恒等式的證明第 2 章關系與函數(shù)復習要點1了解有序對和笛卡兒積的概念，掌握笛卡兒積的運算有序對就是有順序二元組，如， x, y 的位置是確定的，不能隨意放置注意：有序對 ，以 a, b 為元素的集合a, b= b, a；有序對 (a, a)有意義，而集合 a, a 是單元素集合，應記作 a集合 a，b 的笛卡兒積ab 是一個集合，規(guī)定ab x a,yb，是有序對的集合 . 笛卡兒積也可以多個集合合成，a1a2an2理解關系的概念：二元關系、空關系、全關系、恒等關系.掌握關系的集合表示、關系矩陣和關系圖，掌握關系的集合運算和求復合關系、逆關系的方法二元關系是一個有序對集合，,by

4、axyxr，記作 xry關系的表示方法有三種：集合表示法，關系矩陣： rab，r 的矩陣njmibrarbarrmjijiijnmijr,.,2, 1,.,2, 101,)(. 關系圖： r 是集合上的二元關系，若r，由結點ai畫有向弧到bj構成的圖形空關系是唯一、是任何關系的子集的關系；全關系,ababaeaaa；恒等關系,aaaaia，恒等關系的矩陣mi是單位矩陣關系的集合運算有并、交、補、差和對稱差復合關系 ),(,2121rcbrbabcarrr?；復合關系矩陣：21rrrmmm(按布爾運算 )；有結合律： (r?s)?tr?(s?t)，一般不可交換逆關系,1ryxxyr；逆關系矩陣滿

5、足：trrmm1；復合關系與逆關系存在：(r?s)1=s1?r13理解關系的性質(自反性和反自反性、對稱性和反對稱性、傳遞性的定義以及矩陣表示或關系圖表示)，掌握其判別方法(利用定義、 矩陣或圖， 充分條件 )，知道關系閉包的定義和求法注：(1)關系性質的充分必要條件： r 是自反的iar；r 是反自反的iar；r 是對稱的rr1；r 是反對稱的rr1ia；r 是傳遞的r?r r. (2)ia具有自反性，對稱性、反對稱性和傳遞性ea具有自反性，對稱性和傳遞性故ia，ea是等價關系具有反自反性、對稱性、反對稱性和傳遞性ia也是偏序關系4理解等價關系和偏序關系概念，掌握等價類的求法和作偏序集哈斯圖

6、的方法知道極大 (小)元，最大 (小)元的概念，會求極大(小)元、最大 (小)元、最小上界和最大下界等價關系和偏序關系是具有不同性質的兩個關系. 偏序關系等價關系傳遞性反對稱性對稱性自反性知道等價關系圖的特點和等價類定義，會求等價類一個子集的極大( 小) 元可以有多個，而最大( 小) 元若有，則惟一. 且極元、最元只在該子集內；而上界與下界可以在子集之外由哈斯圖便于確定任一子集的最大( 小) 元， 極大 ( 小)元5理解函數(shù)概念：函數(shù)(映射 )，函數(shù)相等，復合函數(shù)和反函數(shù)理解單射、滿射和雙射等概念，掌握其判別方法設 f 是集合 a 到 b 的二元關系，aa，存在惟一b b，使得 f，且 dom

7、( f)=a，f 是一個函數(shù) (映射 )函數(shù)是一種特殊的關系集合 a b 的任何子集都是關系，但不一定是函數(shù)函數(shù)要求對于定義域a 中每一個元素 a，b 中有且僅有一個元素與a 對應，而關系沒有這個限制二函數(shù)相等是指：定義域相同， 對應關系相同， 而且定義域內的每個元素的對應值都相同函數(shù)有：單射若)()(2121afafaa；滿射 f(a)=b 或,axby使得 y=f(x)；雙射單射且滿射復合函數(shù),:,:,:cafgcbgbaf則即)()(xfgxfg復合成立的條件 是：)(dom)(rangf一般gffg，但fghfgh)()(. 反函數(shù)若f：ab 是雙射，則有反函數(shù)f1：ba，,)(,1a

8、abafbbabf，ffgffg11111)(,)(重點 ：關系概念與其性質，等價關系和偏序關系，函數(shù). 第 3 章圖的基本概念復習要點1理解圖的概念：結點、邊、有向圖，無向圖、簡單圖、完全圖、結點的度數(shù)、邊的重數(shù)和平行邊等.理解握手定理圖是一個有序對，v 是結點集， e 是聯(lián)結結點的邊的集合掌握無向邊與無向圖，有向邊與有向圖，混合圖，零圖，平凡圖、自回路(環(huán))，無向平行邊，有向平行邊等概念簡單圖，不含平行邊和環(huán)(自回路 )的圖、在無向圖中，與結點v(v)關聯(lián)的邊數(shù)為結點度數(shù)deg(v)；在有向圖中，以v(v)為終點的邊的條數(shù)為入度deg(v)，以v(v)為起點的邊的條數(shù)為出度deg(v)，d

9、eg(v)=deg+(v) +deg(v)無向完全圖kn以其邊數(shù)) 1(21nne；有向完全圖以其邊數(shù)) 1(nne了解子圖、真子圖、補圖和生成子圖的概念生成子圖設圖g，若 ee，則圖 是 的生成子圖知道圖的同構概念，更應知道圖同構的必要條件，用其判斷圖不同構.重要定理 ：(1) 握手定理設 g=，有vvev2)deg(；(2) 在有向圖d中，vvvvvv)(deg)(deg；(3) 奇數(shù)度結點的個數(shù)為偶數(shù)個2了解通路與回路概念：通路(簡單通路、基本通路和復雜通路)，回路 (簡單回路、基本回路和復雜回路)會求通路和回路的長度基本通路(回路 )必是簡單通路(回路 )了解無向圖的連通性，會求無向圖

10、的連通分支了解點割集、邊割集、割點、割邊等概念了解有向圖的強連通強性；會判別其類型設圖 g，結點與邊的交替序列為通路 通路中邊的數(shù)目就是通路的長度 起點和終點重合的通路為回路邊不重復的通路(回路 )是簡單通路 (回路 )；結點不重復的通路(回路 )是基本通路 (回路 ). 無向圖 g 中， 結點 u, v存在通路，u, v是連通的，g 中任意結點u, v連通， g 是連通圖p(g)表示圖 g 連通分支的個數(shù)在無向圖中， 結點集 vv，使得 p(gv )p(g)，而任意 vv ,有 p （ gv ）p(g)，v 為點割集 . 若 v 是單元集，該結點v 叫割點；邊集ee，使得p(gv )p(g)

11、，而任意ee ，有 p（ge ） p(g)， e 為邊割集若e 是單元集，該邊e 叫割邊 (橋)要知道：強連通必是單側連通必是弱連通，反之不成立3了解鄰接矩陣和可達矩陣的概念，掌握其構造方法及其應用重點 ：圖的概念，握手定理，通路、回路以及圖的矩陣表示第 4 章幾種特殊圖復習要點1理解歐拉通路(回路 )、歐拉圖的概念，掌握歐拉圖的判別方法通過連通圖g 的每條邊一次且僅一次的通路(回路 )是歐拉通路 (回路 )存在歐拉回路的圖是歐拉圖 . 歐拉回路要求邊不能重復，結點可以重復筆不離開紙，不重復地走完所有的邊，走過所有結點，就是所謂的一筆畫歐拉圖或通路的判定定理(1) 無向連通圖g 是歐拉圖g 不

12、含奇數(shù)度結點(即 g 的所有結點為偶數(shù)度)；(2) 非平凡連通圖g 含有歐拉通路g 最多有兩個奇數(shù)度的結點；(3) 連通有向圖d 含有有向歐拉回路d 中每個結點的入度出度連通有向圖d 含有有向歐拉通路d 中除兩個結點外，其余每個結點的入度出度，且此兩點滿足deg(u)deg(v) 12理解漢密爾頓通路(回路 )、漢密爾頓圖的概念，會做簡單判斷通過連通圖g 的每個結點一次，且僅一次的通路(回路 )，是漢密爾頓通路(回路 )存在漢密爾頓回路的圖是漢密爾頓圖. 漢密爾頓圖的充分條件和必要條件(1) 在無向簡單圖g=中，v3，任意不同結點vvugvu)deg()deg(,，則g 是漢密爾頓圖(充分條件

13、 ) (2) 有向完全圖d , 若3v，則圖 d 是漢密爾頓圖 . (充分條件 ) (3) 設無向圖 g=，任意 v1v，則 w(gv1)v1(必要條件 ) 若此條件不滿足，即存在v1v，使得p(gv!) v1,則 g 一定不是漢密爾頓圖(非漢密爾頓圖的充分條件)3了解平面圖概念，平面圖、面、邊界、面的次數(shù)和非平面圖掌握歐拉公式的應用平面圖是指一個圖能畫在平面上，除結點之外，再沒有邊與邊相交面、邊界和面的次數(shù))deg(r等概念重要結論 ：(1)平面圖ereevvevgrii2)deg(,1則(2)歐拉公式：平面圖,eevvevg面數(shù)為r，則2rev(結點數(shù)與面數(shù)之和邊數(shù)2) (3)平面圖633

14、,veveevvevg，則若會用定義判定一個圖是不是平面圖4理解平面圖與對偶圖的關系、對偶圖在圖著色中的作用，掌握求對偶圖的方法給定平面圖 g v，e，它有面 f1，f2， fn，若有圖 g* v* ， e*滿足下述條件：對于圖 g的任一個面 fi，內部有且僅有一個結點vi* v* ；對于圖 g的面 fi，fj的公共邊 ek，存在且僅存在一條邊ek*e* ，使 ek* (vi* ，vj*) ，且ek* 和ek相交；當且僅當 ek只是一個面 fi的邊界時， vi*存在一個環(huán) ek*和ek相交；則圖 g*是圖 g的對偶圖 若g*是g的對偶圖，則g也是 g* 的對偶圖一個連通平面圖的對偶圖也必是平面

15、圖5掌握圖論中常用的證明方法重點 ：歐拉圖和哈密頓圖、平面圖的基本概念及判別第 5 章樹及其應用復習要點1了解樹、樹葉、分支點、平凡樹、生成樹和最小生成樹等概念，掌握求最小生成樹的方法連通無回路的無向圖是樹樹的判別可以用圖t 是樹的充要條件(等價定義 )注意： (1) 樹 t 是連通圖；(2)樹 t 滿足 mn 1（即邊數(shù) =頂點數(shù) - 1）圖 g 的生成子圖是樹，該樹就是生成樹每邊指定一正數(shù)，稱為權， 每邊帶權的圖稱為帶權圖g 的生成樹t 的所有邊的權之和是生成樹 t 的權，記作w(t)最小生成樹是帶權最小的生成樹2了解有向樹、根樹、有序樹、二叉樹、二叉完全樹、正則二叉樹和最優(yōu)二叉樹等概念了

16、解帶權二叉樹、最優(yōu)二叉樹的概念，掌握用哈夫曼算法求最優(yōu)二叉樹的方法有向圖刪去邊的方向為樹，該圖為有向樹對非平凡有向樹，恰有一個結點的入度為0(該結點為 樹根 )，其余結點的入度為1，該樹為 根樹 每個結點的出度小于或等于2 的根樹為二叉樹； 每個結點的出度等于0 或 2 的根樹為二叉完全樹；每個結點的出度等于2 的根樹稱為正則二叉樹有關樹的求法 ：(1)生成樹的破圈法和避圈法求法；(2)最小生成樹的克魯斯克爾求法；(3) 最優(yōu)二叉樹的哈夫曼求法重點 ：樹與根樹的基本概念，最小生成樹與最優(yōu)二叉樹的求法. 第 6 章命題邏輯復習要點1理解命題概念，會判別語句是不是命題理解五個聯(lián)結詞：否定p、析取、

17、合取、條件、和雙條件及其真值表，會將簡單命題符號化具有確定真假意義的陳述句稱為命題命題必須具備：其一，語句是陳述句；其二，語句有唯一確定的真假意義. 2了解公式的概念(公式、賦值、成真指派和成假指派)和公式真值表的構造方法能熟練地作公式真值表理解永真式和永假式概念，掌握其判別方法判定命題公式類型的方法：其一是真值表法，其二是等價演算法. 3了解公式等價概念，掌握公式的重要等價式和判斷兩個公式是否等價的有效方法：等價演算法、列真值表法和主范式方法4理解析取范式和合取范式、極大項和極小項、主析取范式和主合取范式的概念，熟練掌握它們的求法命題公式的范式不惟一，但主范式是惟一的命題公式 a 有 n 個

18、命題變元， a 的主析取范式有k 個極小項，有m 個極大項，則nmk2于是有(1) a 是永真式k=2n(m=0)；(2) a 是永假式m2n(k=0)；求命題公式a 的析取 (合取 )范式的步驟：見教材第174 頁求命題公式a 的主析取 (合取 )范式的步驟：見教材第177 和 178頁5了解 c 是前提集合 a1,a2,am的有效結論或由a1, a2, , am邏輯地推出c 的概念要理解并掌握推理理論的規(guī)則、重言蘊含式和等價式，掌握命題公式的證明方法：真值表法、直接證法、間接證法重點 ：命題與聯(lián)結詞，公式與解釋，真值表，公式的類型及判定，主析取(合取 )范式，命題演算的推理理論. 第 7 章謂詞邏輯復習要點1理解謂詞、量詞、個體詞、個體域，會將簡單命題符號化原子命題分成個體詞和謂詞，個體詞可以是具體事物或抽象的概念，分個體常項和個體變項謂詞用來刻劃個體詞的性質或之間的關系量詞分全稱量詞，存在量詞. 命題符號化注意：使用全稱量詞，特性謂詞后用；使用存在量詞，特性謂詞后用2了解原子公式、謂詞公式、變元(約束變元和自由變元)與轄域等概念掌握在有限個體域下消去公式的量詞和求公式在給定解釋下真值的方法由原子公式、聯(lián)結詞和量詞構成謂詞公式謂詞公式具有真值時，才是