【正文】 {,}，f5={,}，f6={,}，f7={,}.令f : A→B，f(198。)=f0, f({1})=f1, f({2})=f2, f({3})=f3，f({1,2})=f4, f({1,3})=f5, f({2,3})=f6, f({1,2,3})=f7 例4A=[0,1]B=[1/4,1/2] 構(gòu)造雙射 f : A→B解令f : [0,1]→[1/4,1/2]f(x)=(x+1)/4例5A=Z, B=N，構(gòu)造雙射 f : A→B將Z中元素以下列順序排列并與N中元素對應(yīng)： Z：0112233 …   ↓↓↓↓↓↓↓ N：0 1 2 4 5 6 … 則這種對應(yīng)所表示的函數(shù)是： x179。0236。2xf:Z174。N,f(x)=237。238。2x1x0例1 設(shè) f : R→R, g : R→R 236。x2x179。3f(x)=237。 x3238。2 g(x)=x+2求f °g, g° f 和 g 存在反函數(shù), fog:R174。R236。x2+2x179。3fog(x)=237。x3238。0gof:R174。R236。(x+2)2gof(x)=237。238。2x179。1x1 f : R→R不存在反函數(shù)；g : R→R的反函數(shù)是 g1: R→R, g1(x)=x2第6章 圖例1 下述2組數(shù)能成為無向圖的度數(shù)列嗎?(1)3,3,3,4。(2)1,2,2,3解(1).(2)能例2 已知圖G有10條邊, 4個(gè)3度頂點(diǎn), 其余頂點(diǎn)的度數(shù)均小 于等于2, 問G至少有多少個(gè)頂點(diǎn)? 解 ，4180。3+2180。(n4)179。2180。10 解得n179。8 例3 已知5階有向圖的度數(shù)列和出度列分別為3,3,2,3,3和 1,2,1,2,1, 求它的入度列 解2,1,1,1,2 例4 證明不存在具有奇數(shù)個(gè)面且每個(gè)面都具有奇數(shù)條棱的 , 作無向圖G=, 其中 V={v | v為多面體的面}，E={(u,v)| u,v206。V 217。 u與v有公共的棱 217。 u185。v}.根據(jù)假設(shè), |V|為奇數(shù)且v206。V, d(v) 設(shè)9階無向圖的每個(gè)頂點(diǎn)的度數(shù)為5或6, 證明它至少有 (1)a=0, b=9。(2)a=2, b=7。(3)a=4, b=5。(4)a=6, b=3。(5)a=8, b=1(1)~(3)至少5個(gè)6度頂點(diǎn),(4)和(5)至少6個(gè)5度頂點(diǎn)方法二假設(shè)b95=, a 179。 6 例6 畫出4階3條邊的所有非同構(gòu)的無向簡單圖解 總度數(shù)為6, 分配給4個(gè)頂點(diǎn), 最大度為3, 且奇度頂點(diǎn)數(shù) 為偶數(shù), 有下述3個(gè)度數(shù)列:(1)1,1,1,3。(2)1,1,2,2。(3)0,2,2,1,1,3 1,1,2,2例7 畫出3個(gè)以1,1,1,2,2,3為度數(shù)列的非同構(gòu)的無向簡單圖 0,2,2,2例1 右圖有 個(gè)面 R1的邊界:a R2的邊界:bce R3的邊界:fgR0的邊界:abcdde, fgdeg(R1)=1 deg(R2)=3 deg(R3)=2 deg(R0)=8 例2 (1)中是外部面, 在(2)中是內(nèi)部面。R2在(1)中是內(nèi)部面, 在(2) R1 R3 R2(1)R2R1(2)說明:(1)一個(gè)平面圖可以有多個(gè)不同形式的平面嵌入, 它們都同構(gòu).(2)可以通過變換(測地投影法)把平面圖的任何一面作為外部面 例3 證明 K5 和 K3,3不是平面圖證 K5 : n=5, m=10, l=3K3,3 : n=6, m=9, l=4例,3同胚也可收縮到K3,3與K5同胚也可收縮到K5 例6 畫出所有非同構(gòu)的6階11條邊的簡單連通非平面圖 解在K5(5階10條邊)上加一個(gè)頂點(diǎn)和一條邊在K3,3(6階9條邊)上加2條邊例1 某中學(xué)有3個(gè)課外活動(dòng)小組:數(shù)學(xué)組, ,錢,孫,李,周5名學(xué)生, 問分別在下述3種情況下, 能否選出3人各任一個(gè)組的組長?(1)趙, 錢為數(shù)學(xué)組成員, 趙,孫,李為計(jì)算機(jī)組成員, 孫,李,周為生物組成員.(2)趙為數(shù)學(xué)組成員, 錢,孫,李為計(jì)算機(jī)組成員, 錢,孫,李,周為生物組成員.(3)趙為數(shù)學(xué)組和計(jì)算機(jī)組成員, 錢,孫,李,數(shù) 計(jì) 生 數(shù) 計(jì) 生趙 錢 孫 李 周 趙 錢 孫 李 周(1(數(shù) 計(jì) 生趙 錢 孫 李 周(3(1),(2)有多種方案,(3)不可能 例2 證明下述各圖不是哈密頓圖:(a(b(c)(c)中存在哈密頓通路例3 證明右圖不是哈密頓圖證假設(shè)存在一條哈密頓回路, a,f,g是2度頂點(diǎn), 邊(a,c),(f,c)和(g,c)必在這條哈密頓回路上,從而點(diǎn)c出現(xiàn)3次, b c f deg此外, , 這表明此條件是必要、, 有7個(gè)人, A會(huì)講英語, B會(huì)講英語和漢語, C會(huì)講英語、意大利語和俄語, D會(huì)講日語和漢語, E會(huì)講德語和意大利語, F會(huì)講法語、日語和俄語, , 使得每個(gè)人都能與兩旁的人交談? 解作無向圖, 每人是一個(gè)頂點(diǎn), F E DA B CACEGFDBA是一條哈密頓回路,按此順序就坐即可.第四篇：離散數(shù)學(xué)自學(xué)學(xué)習(xí)體會(huì)專業(yè)：計(jì)算機(jī) 姓名：范文芳 學(xué)號(hào)： 成績： 院校：離散數(shù)學(xué)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的基礎(chǔ)核心課程。通過本課程的學(xué)習(xí)，使學(xué)生具有現(xiàn)代數(shù)學(xué)的觀點(diǎn)和方法，并初步掌握處理離散結(jié)構(gòu)所必須的描述工具和方法。同時(shí)，也要培養(yǎng)學(xué)生抽象思維和慎密概括的能力，使學(xué)生具有良好的開拓專業(yè)理論的素質(zhì)和使用所學(xué)知識(shí)，分析和解決實(shí)際問題的能力，為學(xué)生以后學(xué)習(xí)計(jì)算機(jī)基礎(chǔ)理論與專業(yè)課程打下良好的基礎(chǔ)。學(xué)習(xí)離散數(shù)學(xué)有兩項(xiàng)最基本的任務(wù)：其一是通過學(xué)習(xí)離散數(shù)學(xué)，使學(xué)生了解和掌握在后續(xù)課程中要直接用到的一些數(shù)學(xué)概念和基本原理，掌握計(jì)算機(jī)中常用的科學(xué)論證方法，為后續(xù)課程的學(xué)習(xí)奠定一個(gè)良好的數(shù)學(xué)基礎(chǔ)；其二是在離散數(shù)學(xué)的學(xué)習(xí)過程中，培訓(xùn)自學(xué)能力、抽象思維能力和邏輯推理能力，以提高專業(yè)理論水平。因此學(xué)習(xí)離散數(shù)學(xué)對于計(jì)算機(jī)、通信等專業(yè)后續(xù)課程的學(xué)習(xí)和今后從事計(jì)算機(jī)科學(xué)等工作是至關(guān)重要的。但是由于離散數(shù)學(xué)的離散性、知識(shí)的分散性和處理問題的特殊性，使部分學(xué)生在剛剛接觸離散數(shù)學(xué)時(shí)，對其中的一些概念和處理問題的方法往往感到困惑，特別是在做證明題時(shí)感到無從下手，找不到正確的解題思路。因此，對離散數(shù)學(xué)的學(xué)習(xí)方法給予適當(dāng)?shù)闹笇?dǎo)和對學(xué)習(xí)過程中遇到的一些問題分析是十分必要的。一、認(rèn)知離散數(shù)學(xué)離散數(shù)學(xué)是計(jì)算機(jī)科學(xué)基礎(chǔ)理論的核心課程之一，是計(jì)算機(jī)及應(yīng)用、通信等專業(yè)的一門重要的基礎(chǔ)課。它以研究量的結(jié)構(gòu)和相互關(guān)系為主要目標(biāo)，其研究對象一般是有限個(gè)或可數(shù)個(gè)元素，充分體現(xiàn)了計(jì)算機(jī)科學(xué)離散性的特點(diǎn)。學(xué)習(xí)離散數(shù)學(xué)的目的是為學(xué)習(xí)計(jì)算機(jī)、通信等專業(yè)各后續(xù)課程做好必要的知識(shí)準(zhǔn)備，進(jìn)一步提高抽象思維和邏輯推理的能力，為計(jì)算機(jī)的應(yīng)用提供必要的描述工具和理論基礎(chǔ)。1．定義和定理多離散數(shù)學(xué)是建立在大量定義、定理之上的邏輯推理學(xué)科，因此對概念的理解是學(xué)習(xí)這門課程的核心。在學(xué)習(xí)這些概念的基礎(chǔ)上，要特別注意概念之間的聯(lián)系，而描述這些聯(lián)系的實(shí)體則是大量的定理和性質(zhì)。在考試中有一部分內(nèi)容是考查學(xué)生對定義和定理的識(shí)記、理解和運(yùn)用，因此要真正理解離散數(shù)學(xué)中所給出的每個(gè)基本概念的真正的含義。比如，命題的定義、五個(gè)基本聯(lián)結(jié)詞、公式的主析取范式和主合取范式、三個(gè)推理規(guī)則以及反證法；集合的五種運(yùn)算的定義；關(guān)系的定義和關(guān)系的四個(gè)性質(zhì)；函數(shù)（映射）和幾種特殊函數(shù)（映射）的定義；圖、完全圖、簡單圖、子圖、補(bǔ)圖的定義；圖中簡單路、基本路的定義以及兩個(gè)圖同構(gòu)的定義；樹與最小生成樹的定義。掌握和理解這些概念對于學(xué)好離散數(shù)學(xué)是至關(guān)重要的。在離散數(shù)學(xué)的學(xué)習(xí)過程中，一定要注重和掌握離散數(shù)學(xué)處理問題的方法，在做題時(shí)，找到一個(gè)合適的解題思路和方法是極為重要的。如果知道了一道題用怎樣的方法去做或證明，就能很容易地做或證出來。反之，則事倍功半。在離散數(shù)學(xué)中，雖然各種各樣的題種類繁多，但每類題的解法均有規(guī)律可循。所以在聽課和平時(shí)的復(fù)習(xí)中，要善于總結(jié)和歸納具有規(guī)律性的內(nèi)容。在平時(shí)的講課和復(fù)習(xí)中，老師會(huì)總結(jié)各類解題思路和方法。作為學(xué)生，首先應(yīng)該熟悉并且會(huì)用這些方法，同時(shí)，還要勤于思考，對于一道題，進(jìn)可能地多探討幾種解法。離散數(shù)學(xué)的特點(diǎn)是知識(shí)點(diǎn)集中，對抽象思維能力的要求較高。由于這些定義的抽象性，使初學(xué)者往往不能在腦海中直接建立起它們與現(xiàn)實(shí)世界中客觀事物的聯(lián)系。不管是哪本離散數(shù)學(xué)教材，都會(huì)在每一章中首先列出若干個(gè)定義和定理，接著就是這些定義和定理的直接應(yīng)用，如果沒有較好的抽象思維能力，學(xué)習(xí)離散數(shù)學(xué)確實(shí)具有一定的困難。因此，在離散數(shù)學(xué)的學(xué)習(xí)中，要注重抽象思維能力、邏輯推理能力的培養(yǎng)和訓(xùn)練，這種能力的培養(yǎng)對今后從事各種工作都是極其重要的。在學(xué)習(xí)離散數(shù)學(xué)中所遇到的這些困難，可以通過多學(xué)、多看、認(rèn)真分析講課中所給出的典型例題的解題過程，再加上多練，從而逐步得到解決。在此特別強(qiáng)調(diào)一點(diǎn)：深入地理解和掌握離散數(shù)學(xué)的基本概念、基本定理和結(jié)論，是學(xué)好離散數(shù)學(xué)的重要前提之一。所以，同學(xué)們要準(zhǔn)確、全面、完整地記憶和理解所有這些基本定義和定理。離散數(shù)學(xué)的三大體系雖然來自于不同的學(xué)科，但是這三大體系前后貫通，形成一個(gè)有機(jī)的整體。通過認(rèn)真的分析可尋找出三大部分之間知識(shí)的內(nèi)在聯(lián)系性和規(guī)律性。如：集合論、函數(shù)、關(guān)系和圖論，其解題思路和證明方法均有相同或相似之處。二、認(rèn)知解題規(guī)范一般來說，離散數(shù)學(xué)的考試要求分為：了解、理解和掌握。了解是能正確判別有關(guān)概念和方法；理解是能正確表達(dá)有關(guān)概念和方法的含義；掌握是在理解的基礎(chǔ)上加以靈活應(yīng)用。為了考核學(xué)生對這三部分的理解和掌握的程度，試題類型一般可分為：判斷題、填空題、選擇題、計(jì)算題和證明題。判斷題、填空題、選擇題主要涉及基本概念、基本理論、重要性質(zhì)和結(jié)論、公式及其簡單計(jì)算；計(jì)算題主要考核學(xué)生的基本運(yùn)用技能和速度，要求寫出完整的計(jì)算過程和步驟；證明題主要考查應(yīng)用概念、性質(zhì)、定理及重要結(jié)論進(jìn)行邏輯推理的能力，要求寫出嚴(yán)格的推理和論證過程。學(xué)習(xí)離散數(shù)學(xué)的最大困難是它的抽象性和邏輯推理的嚴(yán)密性。在離散數(shù)學(xué)中，假設(shè)讓你解一道題或證明一個(gè)命題，你應(yīng)首先讀懂題意，然后尋找解題或證明的思路和方法，當(dāng)你相信已找到了解題或證明的思路和方法，你必須把它嚴(yán)格地寫出來。一個(gè)寫得很好的解題過程或證明是一系列的陳述，其中每一條陳述都是前面的陳述經(jīng)過簡單的推理而得到的。仔細(xì)地寫解題過程或證明是很重要的，既能讓讀者理解它，又能保證解題過程或證明準(zhǔn)確無誤。一個(gè)好的解題過程或證明應(yīng)該是條理清楚、論據(jù)充分、表述簡潔的。針對這一要求，在講課中老師會(huì)提供大量的典型例題供同學(xué)們參考和學(xué)習(xí)。通過離散數(shù)學(xué)的學(xué)習(xí)和訓(xùn)練，能使同學(xué)們學(xué)會(huì)在離散數(shù)學(xué)中處理問題的一般性的規(guī)律和方法，一旦掌握了離散數(shù)學(xué)中這種處理問題的思想方法，學(xué)習(xí)和掌握離散數(shù)學(xué)的知識(shí)就不再是一件難事了。復(fù)習(xí)離散數(shù)學(xué)的整個(gè)過程可大致分為三個(gè)階段。第一階段，大量進(jìn)行知識(shí)儲(chǔ)備的階段。離散數(shù)學(xué)是建立在大量定義上面的邏輯推理學(xué)科。因而對概念的理解是我們學(xué)習(xí)這門學(xué)科的核心。由于這些定義非常抽象，初學(xué)者往往不能在腦海中建立起它們與現(xiàn)實(shí)世界中客觀事物的聯(lián)系。對于跨專業(yè)自學(xué)的朋友來說更是如此。這是離散數(shù)學(xué)學(xué)習(xí)中的第一個(gè)困難。因此，對于第一遍復(fù)習(xí)，我們提出一個(gè)最為重要的要求，即準(zhǔn)確、全面、完整地記憶所有的定義和定理。具體做法可以是：在進(jìn)行完一章的學(xué)習(xí)后，用專門的時(shí)間對該章包括的定義與定理實(shí)施強(qiáng)記，直到能夠全部正確地默寫出來為止。無須強(qiáng)求一定要理解，記住并能準(zhǔn)確復(fù)述 各定義定理是此階段的最高要求。也不需做太多的題（甚至不做課后習(xí)題也是可以的，把例題看懂就行），重心要放在對定義和定理的記憶上。請牢記，這是為未來的向廣度和深度擴(kuò)張作必要的準(zhǔn)備。這一過程視各人情況不同耗時(shí)約在一到兩個(gè)月內(nèi)。第二階段，深入學(xué)習(xí)，并大量做課后習(xí)題的階段。這是最漫長的一個(gè)階段，耗時(shí)也很難估計(jì)，一般來說，若能熟練解出某一章75%以上的課后習(xí)題，可以考慮結(jié)束該章。解離散數(shù)學(xué)的題，方法非常重要，如果拿到一道題，立即能夠看出它所屬的類型及關(guān)聯(lián)的知識(shí)點(diǎn)，就不難選用正確的方法將其解決，反之則事倍功半。例如在命題邏輯部分，無非是這么幾種題目：將自然語言表述的命題符號(hào)化，等價(jià)命題的相互轉(zhuǎn)化（包括化為主合取范式與主析取范式），以給出的若干命題為前提進(jìn)行推理和證明。相應(yīng)的對策也馬上就可以提出來。以推理題為例，主要是利用P、T規(guī)則，加上蘊(yùn)涵和等價(jià)公式表，由給定的前提出發(fā)進(jìn)行推演，或根據(jù)題目特點(diǎn)采用真值表法、CP規(guī)則和反證法。由此可見，在平常復(fù)習(xí)中，要善于總結(jié)和歸納，仔細(xì)體會(huì)題目類型和此類題目的解題套路。如此多作練習(xí)，則即使遇到比較陌生的題也可以較快地領(lǐng)悟其本質(zhì)，從而輕松解出?！笆熳x唐詩三百首，不會(huì)做詩也會(huì)吟?！币悄玫揭槐玖?xí)題集，從頭到尾做過，甚至背會(huì)的話。那么，在考場上就會(huì)發(fā)現(xiàn)絕大多數(shù)題見過或似曾相識(shí)。這時(shí)，要取得較好的成績也就不是太難的事情了。這一情況具有普遍性，對許多院校的考試都適用。第三階段，進(jìn)行真題模擬訓(xùn)練，提高整體水平和綜合能力的階段。這一階段從第二階段結(jié)束一直持續(xù)到考試。除了我們使用的課本外，應(yīng)盡可能地弄到報(bào)考院校的專業(yè)課歷年試題。因?yàn)槊總€(gè)單位對該科目的側(cè)重點(diǎn)畢竟有不同，從歷年試題中可以獲取許多有用的信息。這些歷年試題此時(shí)就有了巨大的作用。第五篇：離散數(shù)學(xué)第三章第三章部分課后習(xí)題參考答案：(2)前提：p174。q,216。(q217。r),r 結(jié)論：216。p(4)前提：q174。p,q171。s,s171。t,t217。r 結(jié)論：p217。q證明：（2）①216。(q217。r)前提引入 ②216。q218。216。r ①置換 ③q174。216。r ②蘊(yùn)含等值式 ④r 前提引入 ⑤216。q ③④拒取式 ⑥p174。q 前提引入 ⑦￢p ⑤⑥拒取式證明（4）：①t217。r 前提引入 ②t ①化簡律 ③q171。s 前提引入 ④s171。t 前提引入⑤q171。t ③④等價(jià)三段論 ⑥（q174。t）217。(t174。q)⑤ 置換 ⑦（q174。t）⑥化簡 ⑧q ②⑥ 假言推理 ⑨q174。p 前提引入 ⑩p ⑧⑨假言推理(11)p217。q ⑧⑩合取15在自然推理系統(tǒng)P中用附加前提法證明下面各推理：(1)前提：p174。(q174。r),s174。p,q 結(jié)論：s174。r 證明①s 附加前提引入 ②s174。p 前提引入 ③p ①②假言推理 ④p174。(q174。r)前提引入 ⑤q174。r ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理16在自然推理系統(tǒng)P中用歸謬法證明下面各推理：(1)前提：p174。216。q,216。r218。q,r217。216。s 結(jié)論：216。p 證明：①p 結(jié)論的否定引入 ②p174。﹁q 前提引入 ③﹁q ①②假言推理 ④￢r218。q 前提引入 ⑤￢r ④化簡律 ⑥r(nóng)217。￢s 前提引入 ⑦r ⑥化簡律 ⑧r217。﹁r ⑤⑦ 合取由于最后一步r217。﹁r 是矛盾式,所以推理正確.