1、,離散數(shù)學總復習,一、什么是離散數(shù)學？,離散數(shù)學是現(xiàn)代數(shù)學的一個重要分支，是計算機專業(yè)的一門重要的專業(yè)基礎課程。它是以研究離散量的結(jié)構(gòu)和相互間的關系為主要目標，其研究對象一般是有限個或可數(shù)個元素，因此它充分描述了計算機科學離散性的特點。,概 述,二、為什么要學離散數(shù)學？,1、離散數(shù)學是計算機專業(yè)的一門核心基礎課程，離散數(shù)學為計算機專業(yè)的后繼課程如數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、數(shù)據(jù)庫、編譯原理、網(wǎng)絡和算法設計等課程提供必要的數(shù)學基礎。,2、為學生今后從事計算機科學和技術各方面的工作提供有力的工具。,3、離散數(shù)學是現(xiàn)代數(shù)學的一個重要分支，通過該課程的學習可以提高學生的抽象思維、嚴格推理以及綜合歸納分析能力，

2、培養(yǎng)出高素質(zhì)的人才。,三、如何學好離散數(shù)學？,1、熟讀教材。準確理解各個概念和定理的含義（結(jié)合多個例子來理解），必要的推理過程要看懂、理解（它可以幫助你熟悉和深刻理解定理的含義）。,2、獨立思考，大量練習。僅靠熟讀教材并不能將書本上的知識變成你自己的知識，在熟讀教材的基礎上，必須通過大量練習，獨立思考來真正獲取知識。,3、注重抽象思維能力的培養(yǎng)。數(shù)學與其他學科相比較具有較高的抽象性，而離散數(shù)學的抽象性特點更為顯著，它有著大量抽象的概念和抽象的推理，要學好這門課程必須具有較好的抽象思維能力，才能深入地掌握課程內(nèi)容。,“常思考，多做題”,第四部分 數(shù)理邏輯。包括命題邏輯和謂詞邏輯。,四、離散數(shù)學的

3、主要內(nèi)容有哪些？,離散數(shù)學的主要內(nèi)容可以分為四個部分：,第一部分 集合論。包括集合、關系和函數(shù)。,第二部分 代數(shù)系統(tǒng)。包括代數(shù)系統(tǒng)的一般概念，幾類典型的代數(shù)系統(tǒng)。,第三部分 圖論。包括圖的基本概念，幾種特殊的圖。,第一部分 集合論,集合論包括集合、二元關系和函數(shù)，它們之間的關系是：二元關系是一種特殊的集合，集合中的元素都是有序?qū)?；函?shù)是一種特殊的二元關系。,一、內(nèi)容提要 1、集合的兩種表示方法：列舉法和描述法。 2、特殊的集合：空集、全集、子集和冪集。 3、集合的運算：并、交、差和對稱差，各種運算的性質(zhì)。 4、集合運算的基本定律：交換律，結(jié)合律，分配律，吸收律，德.摩根律等。 5、有序n元組、

4、n維笛卡爾積。 6、關系的定義：笛卡爾積的子集。,7、關系的表示方法：集合、矩陣和關系圖。 8、關系的性質(zhì)：自反性、反自反性、對稱性、反對稱性和傳遞性。 9、關系的運算：復合運算、逆運算和閉包運算。 10、特殊的二元關系及其相關特性：等價關系（自反性、對稱性、傳遞性）、偏序關系（自反性、反對稱性、傳遞性）、等價類、偏序關系中的特殊元素（極大元、上界等）。 11、函數(shù)的定義、函數(shù)的定義域和值域。 12、函數(shù)的性質(zhì)：單射、滿射和雙射。 13、函數(shù)的運算：復合函數(shù)、逆函數(shù)。 14、集合的基數(shù)。,二、重點和難點 1、掌握元素與集合之間的關系，集合與集合之間的關系。 2、運用集合運算的基本定律去化簡集合

5、表達式或證明集合等式。 3、掌握二元關系的五個性質(zhì)和二元關系的運算。 4、等價關系的證明、等價類的求解，偏序關系的特定元素的求解。 5、函數(shù)的性質(zhì)，求復合函數(shù)和逆函數(shù)。,三、例題 1、 這兩個關系是否正確？ 答：正確。在中表示元素；在中表示空集。 2、求R=, , 的傳遞閉包。 解：R的傳遞閉包=, , , , ,。 注意：求傳遞閉包是一個不斷重復合并有序?qū)Φ倪^程。有序?qū)ν宦┑簟?3、化簡集合表達式：(AB)A)(BB)A(BB) 解： (AB)A)(BB)A(BB) (吸收律和零律) =AAU (同一律) = AAU (零律) = U = U,4、設集合Aa, b, c, d, e，偏序

6、關系R的哈斯圖如圖所示，若A的子集B=c, d, e，求：（1）用列舉法寫出偏序關系R的集合表達式；（2）寫出集合B的極大元、極小元、最大元、最小元、上界、下界、上確界、下確界。,解：（1）R=IA, , , , , , （2）集合B的極大元：c，極小元：d、e，最大元：c，最小元：無，上界：c、a，上確界：c，下界：無，下確界：無。,5、已知f：RR且f(x)=(x+4)3-2，已知g：RR且g(x)=3*x+5，求:(1)f與g的合成函數(shù)，并求3在f與g的合成函數(shù)下的函數(shù)值。(2)g與f的合成函數(shù)是否存在逆函數(shù)？為什么？如果有，求它的逆函數(shù)。 解: (1)fg: RR，且fg(x)=g(f

7、(x)=3*(x+4)3-2)+5=3*(x+4)3-1 fg(3)=3*(3+4)3-1=1028 (2)因為g與f都是雙射函數(shù)；那么，g與f的合成函數(shù)也是雙射函數(shù)。故g與f的合成函數(shù)存在逆函數(shù)。 gf: RR，且gf(x)=f(g(x)=3*(3*x+5)3-2 (gf)-1: RR，且(gf)-1(x)=(x+2)/3)(1/3)-5)/3,第二部分 圖論,一、內(nèi)容提要 1、圖的基本概念：無向圖、有向圖、簡單圖、結(jié)點的度數(shù)、子圖、補圖、圖的同構(gòu)。 2、握手定理：所有結(jié)點的度數(shù)之和等于邊數(shù)的2倍。 3、圖的連通性：割邊、割點、邊割集、點割集。通路、回路、連通分支。 4、圖的矩陣表示：鄰接矩

8、陣、關聯(lián)矩陣。 5、歐拉圖和哈密爾頓圖的定義和判定條件。 6、樹的定義、性質(zhì)、判定條件和遍歷。 7、二部圖和平面圖的定義、性質(zhì)和判定條件,二、重點和難點 1、掌握圖的基本概念。 2、運用握手定理解題。 3、利用圖的矩陣求兩個結(jié)點間的通路條數(shù)。 4、歐拉圖和哈密爾頓圖的判定。 5、樹的遍歷方法。,三、例題 1、設T是2叉正則樹，有t片樹葉，i個分支點，證明T的邊數(shù)m=2t-2 。 證：設T有m條邊，根據(jù)握手定理可得： t+3i-1=2m(1) 因為T是2叉正則樹，根據(jù)樹的性質(zhì)可得： m=t+i-1.(2) 解由(1)，(2)構(gòu)成的方程組得：m=2t-2。故結(jié)論成立。 2、已知無向圖G為n(n2)

9、階簡單圖，G有m條邊，則G的補圖有_個結(jié)點，有_條邊。 答： G的補圖的結(jié)點個數(shù)等于G的結(jié)點個數(shù)，等于n。 G的補圖的邊數(shù)等于n階完全圖的邊數(shù)減去G的邊數(shù)，等于n(n-1)/2-m。,3、下列命題正確的是（ ） （a）G為n階無向連通圖，如果G的邊數(shù)mn-1，則G中必有圈 （b）二部圖的頂點個數(shù)一定是偶數(shù) （c）若無向圖G的任何兩個不相同的頂點均相鄰，則G為哈密爾頓圖 （d）3-正則圖的頂點個數(shù)可以是奇數(shù)，也可以是偶數(shù) 解：c正確，因為無向圖G為完全圖。 a不正確，當G是無向樹時，m=n-1，但G中沒有圈。 b不正確，二部圖要求結(jié)點能夠分成兩部分，每部分中的任何兩個結(jié)點無邊，并沒有要求二部圖的

10、頂點個數(shù)是偶數(shù). d不正確，3-正則圖的所有結(jié)點的度數(shù)均為3，根據(jù)握手定理可得，所有頂點的度數(shù)之和是偶數(shù)。所以3-正則圖的頂點個數(shù)必為偶數(shù)。,4、已知有向圖D的頂點集合V(D)=v1,v2,v3,v4，其鄰接矩陣如右圖所示。求從v1到v3長度小于等于3的通路個數(shù)。,從v1到v3長度小于等于3的通路個數(shù)= =0+1+4=5,A2=,=,A3=,=,解：,5、設n階無向樹G=中有m條邊，證明m=n-1。 證：用數(shù)學歸納法進行證明。 (1)初始化：當n=1時，無向樹G是平凡樹，即G為平凡圖。則m=0=n-1。 (2)假設歸納：假設當nk時，結(jié)論成立，即m=n-1。 當n=k+1時，從無向樹G中刪除某

11、個結(jié)點v，如果結(jié)點v的度數(shù)為i，則有i條邊與結(jié)點v相關聯(lián)，且每條邊均為橋。因此，從無向樹G中刪除結(jié)點v后得到i顆無向樹，分別為：G1、G2、Gi，且對于所有的j(1ji)，均有|Gj|k。根據(jù)假設可得：無向樹Gj的邊mj=nj-1。無向樹G的結(jié)點個數(shù)n=n1+n2+ni+1，無向樹G的邊數(shù)m=m1+m2+mi+i=(n1-1)+(n2-1)+(ni-1)+i= n1+n2+ni= n-1。因此，當n=k+1時，結(jié)論也成立。 綜合(1)、(2)可得：若n階無向樹G=中有m條邊，則m=n-1。,第三部分 數(shù)理邏輯,一、內(nèi)容提要 1、命題及其聯(lián)結(jié)詞（非、與、或、蘊含、等價）。 2、命題公式的析取范式

12、和合取范式。 3、命題公式間的等價關系和蘊含關系。 4、命題演算的推理理論。 5、謂詞公式的有關概念（量詞、謂詞、變元、指派等） 6、謂詞公式間的等價關系和蘊含關系。 7、謂詞演算的推理理論。,二、重點和難點 1、命題公式間的等價關系和蘊含關系。 2、命題演算的推理理論。 3、謂詞公式間的等價關系和蘊含關系。 4、謂詞演算的推理理論。,三、例題 1、下列語句為命題的是（ ） （a）看球賽去 （b）離散數(shù)學是計算機系的一門必修課 （c）計算機有空嗎？ （d）今天天氣多好??！ 解：命題是可以判定真假的陳述句，故b正確。 2、對于公式(x)(P(x)(y)Q(x,y)，下列說法正確的是（ ） （a）x和y都是自由變元 （b）x和y都不是自由變元 （c）x是自由變元，y不是自由變元 （d）x不是自由變元，y是自由變元 解：b正確。,3、證明推理： (x)(P(x) (Q(x)R(x), (x)P(x)(x)(P(x)R(x) 證： (x)P(x) P P(c) ES, (x)(P(x)