離散數學基礎

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

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

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

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

5、表達式或證明集合等式。 3、掌握二元關系的五個性質和二元關系的運算。 4、等價關系的證明、等價類的求解，偏序關系的特定元素的求解。 5、函數的性質，求復合函數和逆函數。,三、例題 1、 這兩個關系是否正確？ 答：正確。在中表示元素；在中表示空集。 2、求R=, , 的傳遞閉包。 解：R的傳遞閉包=, , , , ,。 注意：求傳遞閉包是一個不斷重復合并有序對的過程。有序對往往被漏掉。 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的合成函數，并求3在f與g的合成函數下的函數值。(2)g與f的合成函數是否存在逆函數？為什么？如果有，求它的逆函數。 解: (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都是雙射函數；那么，g與f的合成函數也是雙射函數。故g與f的合成函數存在逆函數。 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,第二部分 圖論,一、內容提要 1、圖的基本概念：無向圖、有向圖、簡單圖、結點的度數、子圖、補圖、圖的同構。 2、握手定理：所有結點的度數之和等于邊數的2倍。 3、圖的連通性：割邊、割點、邊割集、點割集。通路、回路、連通分支。 4、圖的矩陣表示：鄰接矩

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

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

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

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

12、和合取范式。 3、命題公式間的等價關系和蘊含關系。 4、命題演算的推理理論。 5、謂詞公式的有關概念（量詞、謂詞、變元、指派等） 6、謂詞公式間的等價關系和蘊含關系。 7、謂詞演算的推理理論。,二、重點和難點 1、命題公式間的等價關系和蘊含關系。 2、命題演算的推理理論。 3、謂詞公式間的等價關系和蘊含關系。 4、謂詞演算的推理理論。,三、例題 1、下列語句為命題的是（ ） （a）看球賽去 （b）離散數學是計算機系的一門必修課 （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)