離散數(shù)學(xué)期末復(fù)習(xí)要點(diǎn)與重點(diǎn)

離散數(shù)學(xué)期末復(fù)習(xí)要點(diǎn)與重點(diǎn)大綱（復(fù)習(xí)以課本和筆記為主。文中標(biāo)紅為需重點(diǎn)掌握的，祝大家都能取得好成績！）第1章 命題邏輯復(fù)習(xí)要點(diǎn)1理解命題概念，會判別語句是不是命題理解五個(gè)基本聯(lián)結(jié)詞：否定P、析取、合取、條件、和雙條件及其真值表，理解其他聯(lián)結(jié)詞的定義及基本等價(jià)式，會將簡單命題符號化具有確定真假意義的陳述句稱為命題命題必須具備：其一，語句是陳述句；其二，語句有唯一確定的真假意義.2理解公式的概念(公式、賦值、成真指派和成假指派)和公式真值表的構(gòu)造方法能熟練地作公式真值表理解永真式和永假式概念，掌握其判別方法判定命題公式類型的方法：其一是真值表法，其二是等價(jià)演算法.3了解公式等價(jià)概念，掌握公式的重要等價(jià)式和判斷兩個(gè)公式是否等價(jià)的有效方法：等價(jià)演算法、列真值表法和主范式方法4理解析取范式和合取范式、極大項(xiàng)和極小項(xiàng)、主析取范式和主合取范式的概念，熟練掌握它們的求法（真值表法和等價(jià)推導(dǎo)法）命題公式的范式不惟一，但主范式是惟一的 命題公式A有n個(gè)命題變元，A的主析取范式有k個(gè)小項(xiàng)，有m個(gè)大項(xiàng)，則于是有(1) A是永真式k=2n(m=0)； (2) A是永假式m2n(k=0)；5了解C是前提集合A1,A2,Am的有效結(jié)論或由A1, A2, , Am 邏輯地推出C的概念要理解并掌握推理理論的規(guī)則、重言蘊(yùn)含式和等價(jià)式，掌握命題公式的證明方法：真值表法、直接證法、間接證法重點(diǎn)：命題與聯(lián)結(jié)詞，真值表，主析取(合取)范式，命題演算的推理理論.第2章 謂詞邏輯復(fù)習(xí)要點(diǎn)1理解謂詞、量詞、個(gè)體詞、個(gè)體域，會將簡單命題符號化原子命題分成個(gè)體詞和謂詞，個(gè)體詞可以是具體事物或抽象的概念，分個(gè)體常項(xiàng)和個(gè)體變項(xiàng)謂詞用來刻劃個(gè)體詞的性質(zhì)或之間的關(guān)系量詞分全稱量詞，存在量詞$.命題符號化注意：使用全稱量詞，特性謂詞后用；使用存在量詞$，特性謂詞后用2了解原子公式、謂詞公式、變元(約束變元和自由變元)與轄域等概念掌握在有限個(gè)體域下消去公式的量詞和求公式在給定解釋下真值的方法由原子公式、聯(lián)結(jié)詞和量詞構(gòu)成謂詞公式謂詞公式具有真值時(shí)，才是命題在謂詞公式xA或$xA中，x是指導(dǎo)變元，A是量詞的轄域會區(qū)分約束變元和自由變元在非空集合D(個(gè)體域)上謂詞公式A的一個(gè)解釋或賦值有3個(gè)條件在任何解釋下，謂詞公式A取真值1，A為邏輯有效式(永真式)；公式A取真值0，A為永假式；至少有一個(gè)解釋使公式A取真值1，A稱為可滿足式在有限個(gè)體域下，消除量詞的規(guī)則為：設(shè)Da1, a2, , an，則會求謂詞公式的真值，量詞的轄域，自由變元、約束變元，以及換名規(guī)則、代入規(guī)則等掌握謂詞演算的等價(jià)式和重言蘊(yùn)含式并進(jìn)行謂詞公式的等價(jià)演算3理解前束范式的概念，掌握求公式的前束范式的方法.若一個(gè)謂詞公式F等價(jià)地轉(zhuǎn)化成，那么就是F的前束范式，其中Q1，Q2，Qk只能是或$，而x1, x2, , xk是個(gè)體變元，B是不含量詞的謂詞公式前束范式仍然是謂詞公式 重點(diǎn)：翻譯；前束范式第3章 集合與關(guān)系復(fù)習(xí)要點(diǎn)1理解集合、元素、集合的包含、子集、相等，以及全集、空集和冪集等概念，熟練掌握集合的表示方法集合的表示方法：列舉法和描述法. 注意：集合的表示中元素不能重復(fù)出現(xiàn)，集合中的元素?zé)o順序之分掌握集合包含(子集)、真子集、集合相等等概念注意：元素與集合，集合與子集，子集與冪集，與(),空集與所有集合等的關(guān)系.空集，是惟一的，它是任何集合的子集集合A的冪集P(A)， A的所有子集構(gòu)成的集合若An，則P(A)=2n2熟練掌握集合A和B的并AB，交AB，補(bǔ)集A(A補(bǔ)集總相對于一個(gè)全集).差集AB，對稱差，AB(AB)(BA)，或AB(AB)（AB）等運(yùn)算掌握集合運(yùn)算律(運(yùn)算的性質(zhì)).3掌握用集合運(yùn)算基本規(guī)律證明集合恒等式的方法集合的運(yùn)算問題：其一是進(jìn)行集合運(yùn)算；其二是運(yùn)算式的化簡；其三是恒等式證明證明方法有二：(1)要證明AB，只需證明AB，又AB；(2)通過運(yùn)算律進(jìn)行等式推導(dǎo)4了解有序?qū)偷芽柗e的概念，掌握笛卡爾積的運(yùn)算有序?qū)褪怯许樞蚨M，如，x, y 的位置是確定的，不能隨意放置 注意：有序?qū)?，以a, b為元素的集合a, b=b, a；有序?qū)?a, a)有意義，而集合a, a是單元素集合，應(yīng)記作a集合A，B的笛卡爾積AB是一個(gè)集合，規(guī)定ABxA,yB，是有序?qū)Φ募?笛卡爾積也可以多個(gè)集合合成，A1A2An 5理解關(guān)系的概念：二元關(guān)系、空關(guān)系、全關(guān)系、恒等關(guān)系.掌握關(guān)系的集合表示、關(guān)系矩陣和關(guān)系圖，掌握關(guān)系的集合運(yùn)算及復(fù)合關(guān)系、逆關(guān)系的性質(zhì)與求法二元關(guān)系是一個(gè)有序?qū)?，記作xRy 設(shè)A、B是兩個(gè)集合，且|A|m，|B|n，則從A到B可產(chǎn)生的不同的二元關(guān)系個(gè) 數(shù)為。 關(guān)系的表示方法有三種：集合表示法， 關(guān)系矩陣：RAB，R的矩陣. 關(guān)系圖：R是集合上的二元關(guān)系，若R，由結(jié)點(diǎn)ai畫有向弧到bj構(gòu)成的圖形空關(guān)系是唯一、是任何關(guān)系的子集的關(guān)系；全關(guān)系；恒等關(guān)系，恒等關(guān)系的矩陣MI是單位矩陣關(guān)系的集合運(yùn)算有并、交、補(bǔ)、差和對稱差復(fù)合關(guān)系；復(fù)合關(guān)系矩陣：(按邏輯運(yùn)算)； 有結(jié)合律：(RS)TR(ST)，一般不可交換逆關(guān)系；逆關(guān)系矩陣滿足：；復(fù)合關(guān)系與逆關(guān)系存在：(RS)1=S1R16理解關(guān)系的性質(zhì)(自反性和反自反性、對稱性和反對稱性、傳遞性的定義以及矩陣表示或關(guān)系圖表示)，掌握其判別方法(利用定義、矩陣或圖，充分條件)，知道關(guān)系閉包（自反，對稱，傳遞）的定義和求法注：(1)關(guān)系性質(zhì)的充分必要條件： R是自反的IAR；R是反自反的IAR；R是對稱的 RR1；R是反對稱的RR1IA；R是傳遞的RRR. (2) IA具有自反性，對稱性、反對稱性和傳遞性EA具有自反性，對稱性和傳遞性具有反自反性、對稱性、反對稱性和傳遞性重點(diǎn)：集合的運(yùn)算，笛卡爾積，關(guān)系的性質(zhì)，復(fù)合關(guān)系和逆關(guān)系，關(guān)系的閉包. 第4章 函數(shù)復(fù)習(xí)要點(diǎn)1理解函數(shù)概念：函數(shù)(映射)，函數(shù)相等，復(fù)合函數(shù)和反函數(shù)理解單射、滿射和雙射等概念，掌握其判別方法設(shè)f是集合A到B的二元關(guān)系，aA，存在惟一bB，使得f，且Dom(f)=A，f是一個(gè)函數(shù)(映射)函數(shù)是一種特殊的關(guān)系（設(shè)A、B是兩個(gè)集合，且|A|m，|B|n，則從A到B可產(chǎn)生的不同的函數(shù)關(guān)系個(gè)數(shù)為） 集合AB的任何子集都是關(guān)系，但不一定是函數(shù)函數(shù)要求對于定義域A中每一個(gè)元素a，B中有且僅有一個(gè)元素與a對應(yīng)，而關(guān)系沒有這個(gè)限制 二函數(shù)相等是指：定義域相同，對應(yīng)關(guān)系相同，且定義域內(nèi)的每個(gè)元素的對應(yīng)值都相同 函數(shù)有：單射若； 滿射f(A)=B或使得y=f(x)； 雙射單射且滿射 復(fù)合函數(shù) 即復(fù)合成立的條件：一般，但.反函數(shù)若f：AB是雙射，則有反函數(shù)f1：BA，重點(diǎn)：函數(shù). 第5章 代數(shù)結(jié)構(gòu)復(fù)習(xí)要點(diǎn)1掌握代數(shù)系統(tǒng)中運(yùn)算及其性質(zhì)（自反，對稱，傳遞，等冪），會判斷某代數(shù)系統(tǒng)具有哪種性質(zhì)。2. 掌握半群，獨(dú)異點(diǎn)，群，阿貝爾群，循環(huán)群的概念及判定方法。半群：封閉+可結(jié)合。獨(dú)異點(diǎn)：封閉+可結(jié)合+有幺元。群：封閉+可結(jié)合+有幺元+每個(gè)元素有逆元。阿貝爾群：群+可交換。循環(huán)群：群+有生成元。3. 掌握同態(tài)與同構(gòu)的概念，理解同態(tài)的相關(guān)性質(zhì)，并熟練掌握同態(tài)與同構(gòu)的證明方法。重點(diǎn)：代數(shù)系統(tǒng)的運(yùn)算性質(zhì)，群與循環(huán)群的證明方法，同構(gòu)與同態(tài)的證明方法。 第7章 圖的基本概念復(fù)習(xí)要點(diǎn)1理解圖的概念：結(jié)點(diǎn)、邊、有向圖，無向圖、簡單圖、完全圖、結(jié)點(diǎn)的度數(shù)、邊的重?cái)?shù)和平行邊等.理解握手定理圖是一個(gè)有序?qū)?，V是結(jié)點(diǎn)集，E是聯(lián)結(jié)結(jié)點(diǎn)的邊的集合掌握無向邊與無向圖，有向邊與有向圖，混合圖，零圖，平凡圖、自回路(環(huán))，無向平行邊，有向平行邊等概念簡單圖，不含平行邊和環(huán)(自回路)的圖、 在無向圖中，與結(jié)點(diǎn)v(V)關(guān)聯(lián)的邊數(shù)為結(jié)點(diǎn)度數(shù)(v)；在有向圖中，以v(V)為終點(diǎn)的邊的條數(shù)為入度(v)，以v(V)為起點(diǎn)的邊的條數(shù)為出度(v)，deg(v)=deg+(v) +deg(v)無向完全圖Kn及其邊數(shù)；有向完全圖及其邊數(shù)了解子圖、真子圖、補(bǔ)圖的概念 知道圖的同構(gòu)概念，更應(yīng)知道圖同構(gòu)的必要條件，用其判斷圖不同構(gòu).重要定理：(1) 握手定理 設(shè)G=，有；(2) 在有向圖D中，；(3) 奇數(shù)度結(jié)點(diǎn)的個(gè)數(shù)為偶數(shù)個(gè) 2了解路與回路概念會求路和回路的長度 了解無向圖的連通性，會求無向圖的連通分支了解點(diǎn)割集、邊割集、割點(diǎn)、割邊等概念了解有向圖的強(qiáng)連通強(qiáng)性；會判別其類型設(shè)圖G，結(jié)點(diǎn)與邊的交替序列為路路中邊的數(shù)目就是路的長度起點(diǎn)和終點(diǎn)重合的路為回路邊不重復(fù)的路是跡；結(jié)點(diǎn)不重復(fù)的路是通路. 無向圖G中，結(jié)點(diǎn)u, v存在通路，u, v是連通的，G中任意結(jié)點(diǎn)u, v連通，G是連通圖P(G)表示圖G連通分支的個(gè)數(shù) 要知道：強(qiáng)連通單側(cè)連通弱連通，反之不成立3掌握鄰接矩陣，可達(dá)矩陣和距離矩陣的概念，掌握其構(gòu)造方法及其應(yīng)用 4理解歐拉通路(回路)、歐拉圖的概念，掌握歐拉圖的判別方法通過連通圖G的每條邊一次且僅一次的路(回路)是歐拉路(回路)存在歐拉回路的圖是歐拉圖. 歐拉回路要求邊不能重復(fù)，結(jié)點(diǎn)可以重復(fù)筆不離開紙，不重復(fù)地走完所有的邊，走過所有結(jié)點(diǎn)，就是所謂的一筆畫歐拉圖或通路的判定定理(1) 無向連通圖G是歐拉圖G為連通圖且G不含奇數(shù)度結(jié)點(diǎn)(即G的所有結(jié)點(diǎn)為偶數(shù)度)；(2) 非平凡圖G含有歐拉路G為連通圖且G最多有兩個(gè)奇數(shù)度的結(jié)點(diǎn)；(3) 連通有向圖D含有有向歐拉回路D中每個(gè)結(jié)點(diǎn)的入度出度(4) 連通有向圖D含有有向歐拉路D中除兩個(gè)結(jié)點(diǎn)外，其余每個(gè)結(jié)點(diǎn)的入度出度，且此兩點(diǎn)滿足一個(gè)結(jié)點(diǎn)的入度比出度大1，另一個(gè)結(jié)點(diǎn)的出度比入度大15了解漢密爾頓路(回路)、漢密爾頓圖的概念，會做簡單判斷通過連通圖G的每個(gè)結(jié)點(diǎn)一次，且僅一次的路(回路)，是漢密爾頓路(回路)存在漢密爾頓回路的圖是漢密爾頓圖. 漢密爾頓圖的充分條件和必要條件 (1) 在無向簡單圖G=中，V3，任意不同結(jié)點(diǎn)，則G是漢密爾頓圖(充分條件)(2) 有向完全圖D, 若，則圖D是漢密爾頓圖. (充分條件)(3) 設(shè)無向圖G=，任意V1V，則W(GV1)V1(必要條件)若此條件不滿足，即存在V1V，使得P(GV!)V1,則G一定不是漢密爾頓圖(非漢密爾頓圖的充分條件)6了解樹、樹葉、生成樹和最小生成樹等概念，掌握求最小生成樹的方法連通無回路的無向圖是樹樹的判別可以用圖T是樹的充要條件(等價(jià)定義)注意：(1) 樹T是連通圖； (2)樹T滿足mn1（即邊數(shù)=頂點(diǎn)數(shù)-1）圖G的生成子圖是樹，該樹就是生成樹每邊指定一正數(shù)，稱為權(quán)，每邊帶權(quán)的圖稱為