離散數(shù)學(xué)基礎(chǔ)ppt課件

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

2、提高學(xué)生的抽象思維、嚴(yán)格推理以及綜合歸納分析能力，培養(yǎng)出高素質(zhì)的人才。 44 三、如何學(xué)好離散數(shù)學(xué)？三、如何學(xué)好離散數(shù)學(xué)？ 1、熟讀教材。準(zhǔn)確理解各個概念和定理的含義（結(jié)合多個例子來理解），必要的推理過程要看懂、理解（它可以幫助你熟悉和深刻理解定理的含義）。 2、獨立思考，大量練習(xí)。僅靠熟讀教材并不能將書本上的知識變成你自己的知識，在熟讀教材的基礎(chǔ)上，必須通過大量練習(xí)，獨立思考來真正獲取知識。 3 、 注 重 抽 象 思 維 能 力 的 培 養(yǎng) 。 數(shù) 學(xué) 與 其 他 學(xué) 科 相 比 較 具 有較高的抽象性，而離散數(shù)學(xué)的抽象性特點更為顯著，它有著大量抽象的概念和抽象的推理，要學(xué)好這門課程必須具

3、有較好的抽象思維能力，才能深入地掌握課程內(nèi)容?！俺Ｋ伎?，多做題常思考，多做題”55第四部分 數(shù)理邏輯。包括命題邏輯和謂詞邏輯。四、離散數(shù)學(xué)的主要內(nèi)容有哪些？四、離散數(shù)學(xué)的主要內(nèi)容有哪些？離散數(shù)學(xué)的主要內(nèi)容可以分為四個部分：第一部分 集合論。包括集合、關(guān)系和函數(shù)。第二部分 代數(shù)系統(tǒng)。包括代數(shù)系統(tǒng)的一般概念，幾類典型的代數(shù)系統(tǒng)。第三部分 圖論。包括圖的基本概念，幾種特殊的圖。66第一部分第一部分 集合論集合論 集合論包括集合、二元關(guān)系和函數(shù)，它們之間的關(guān)系是：二元關(guān)系是一種特殊的集合，集合中的元素都是有序?qū)?；函?shù)是一種特殊的二元關(guān)系。一、內(nèi)容提要一、內(nèi)容提要1、集合的兩種表示方法：列舉法和描述法。

4、2、特殊的集合：空集、全集、子集和冪集。3、集合的運算：并、交、差和對稱差，各種運算的性質(zhì)。4、集合運算的基本定律：交換律，結(jié)合律，分配律，吸收律，德.摩根律等。5、有序n元組、n維笛卡爾積。6、關(guān)系的定義：笛卡爾積的子集。777、關(guān)系的表示方法：集合、矩陣和關(guān)系圖。8、關(guān)系的性質(zhì)：自反性、反自反性、對稱性、反對稱性和傳遞性。9、關(guān)系的運算：復(fù)合運算、逆運算和閉包運算。10、特殊的二元關(guān)系及其相關(guān)特性：等價關(guān)系（自反性、對稱性、傳遞性）、偏序關(guān)系（自反性、反對稱性、傳遞性）、等價類、偏序關(guān)系中的特殊元素（極大元、上界等）。11、函數(shù)的定義、函數(shù)的定義域和值域。12、函數(shù)的性質(zhì)：單射、滿射和雙射

5、。13、函數(shù)的運算：復(fù)合函數(shù)、逆函數(shù)。14、集合的基數(shù)。88二、重點和難點二、重點和難點1、掌握元素與集合之間的關(guān)系，集合與集合之間的關(guān)系。2、運用集合運算的基本定律去化簡集合表達(dá)式或證明集合等式。3、掌握二元關(guān)系的五個性質(zhì)和二元關(guān)系的運算。4、等價關(guān)系的證明、等價類的求解，偏序關(guān)系的特定元素的求解。5、函數(shù)的性質(zhì)，求復(fù)合函數(shù)和逆函數(shù)。99三、例題三、例題1、 這兩個關(guān)系是否正確？答：正確。在中表示元素；在中表示空集。2、求R=, , 的傳遞閉包。解：R的傳遞閉包=, , , , ,。注意：求傳遞閉包是一個不斷重復(fù)重復(fù)合并有序?qū)Φ倪^程。有序?qū)ν宦┑簟?、化簡集合表達(dá)式：(AB)A)(BB)

6、A(BB) 解： (AB)A)(BB)A(BB) (吸收律和零律) =A A U (同一律) = A A U (零律) = U = U10104、設(shè)集合Aa, b, c, d, e，偏序關(guān)系R的哈斯圖如圖所示，若A的子集B=c, d, e，求：（1）用列舉法寫出偏序關(guān)系R的集合表達(dá)式；（2）寫出集合B的極大元、極小元、最大元、最小元、上界、下界、上確界、下確界。 解：（1）R=IA, , , , , , （2）集合B的極大元：c，極小元：d、e，最大元：c，最小元：無，上界：c、a，上確界：c，下界：無，下確界：無。 11115、已知f：RR且f(x)=(x+4)3-2，已知g：RR且g(x)

7、=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(x)=3*(x+4)3-2)+5=3*(x+4)3-1fg(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 1212第二部分第二部分 圖論圖論一、內(nèi)容提要一、內(nèi)容提要1、圖

8、的基本概念：無向圖、有向圖、簡單圖、結(jié)點的度數(shù)、子圖、補(bǔ)圖、圖的同構(gòu)。2、握手定理：所有結(jié)點的度數(shù)之和等于邊數(shù)的2倍。3、圖的連通性：割邊、割點、邊割集、點割集。通路、回路、連通分支。4、圖的矩陣表示：鄰接矩陣、關(guān)聯(lián)矩陣。5、歐拉圖和哈密爾頓圖的定義和判定條件。6、樹的定義、性質(zhì)、判定條件和遍歷。7、二部圖和平面圖的定義、性質(zhì)和判定條件1313二、重點和難點二、重點和難點1、掌握圖的基本概念。2、運用握手定理解題。3、利用圖的矩陣求兩個結(jié)點間的通路條數(shù)。4、歐拉圖和哈密爾頓圖的判定。5、樹的遍歷方法。1414三、例題三、例題1、設(shè)T是2叉正則樹，有t片樹葉，i個分支點，證明T的邊數(shù)m=2t-2

9、 。證：設(shè)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)階簡單圖，G有m條邊，則G的補(bǔ)圖有_個結(jié)點，有_條邊。 答： G的補(bǔ)圖的結(jié)點個數(shù)等于G的結(jié)點個數(shù)，等于n。 G的補(bǔ)圖的邊數(shù)等于n階完全圖的邊數(shù)減去G的邊數(shù)，等于n(n-1)/2-m。 15153、下列命題正確的是（ ）（a）G為n階無向連通圖，如果G的邊數(shù)mn-1，則G中必有圈（b）二部圖的頂點個數(shù)一定是偶數(shù)（c）若無向圖G的任何兩個不相同的頂點均相鄰，則G為哈密爾頓圖（d）

10、3-正則圖的頂點個數(shù)可以是奇數(shù)，也可以是偶數(shù) 解：c正確，因為無向圖G為完全圖。a不正確，當(dāng)G是無向樹時，m=n-1，但G中沒有圈。b不正確，二部圖要求結(jié)點能夠分成兩部分，每部分中的任何兩個結(jié)點無邊，并沒有要求二部圖的頂點個數(shù)是偶數(shù).d不正確，3-正則圖的所有結(jié)點的度數(shù)均為3，根據(jù)握手定理可得，所有頂點的度數(shù)之和是偶數(shù)。所以3-正則圖的頂點個數(shù)必為偶數(shù)。16164、已知有向圖D的頂點集合V(D)=v1,v2,v3,v4，其鄰接矩陣如右圖所示。求從v1到v3長度小于等于3的通路個數(shù)。 2030010111021010從v1到v3長度小于等于3的通路個數(shù)= =0+1+4=5 20300101110

11、210102030010111021010736611114151313273661111415131322030010111021010269271542431461311114117) 3(13)2(13) 1 (13aaaA2=A3=解：17175、設(shè)n階無向樹G=中有m條邊，證明m=n-1。 證：用數(shù)學(xué)歸納法進(jìn)行證明。(1)初始化：當(dāng)n=1時，無向樹G是平凡樹，即G為平凡圖。則m=0=n-1。(2)假設(shè)歸納：假設(shè)當(dāng)nk時，結(jié)論成立，即m=n-1。 當(dāng)n=k+1時，從無向樹G中刪除某個結(jié)點v，如果結(jié)點v的度數(shù)為i，則有i條邊與結(jié)點v相關(guān)聯(lián)，且每條邊均為橋。因此，從無向樹G中刪除結(jié)點v后得

12、到i顆無向樹，分別為：G1、G2、Gi，且對于所有的j(1ji)，均有|Gj|k。根據(jù)假設(shè)可得：無向樹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。因此，當(dāng)n=k+1時，結(jié)論也成立。綜合(1)、(2)可得：若n階無向樹G=中有m條邊，則m=n-1。 1818第三部分第三部分 數(shù)理邏輯數(shù)理邏輯一、內(nèi)容提要一、內(nèi)容提要1、命題及其聯(lián)結(jié)詞（非、與、或、蘊(yùn)含、等價）。2、命題公式的析取范式和合取范式。3、命題公式間的等價關(guān)系和蘊(yùn)含關(guān)系。4、命題演算的推理理論。5、謂

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