國家開放大學(xué)《離散數(shù)學(xué)》課程復(fù)習(xí)提綱

國家開放大學(xué)《離散數(shù)學(xué)》山東廣播電視大學(xué)開放教育課程復(fù)習(xí)提綱（2011年3月啟用）離散數(shù)學(xué)是中央廣播電視大學(xué)開放教育本科電氣信息類計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門統(tǒng)設(shè)必修學(xué)位課程．該課程的主要內(nèi)容包括：集合論、圖論、數(shù)理邏輯等．基礎(chǔ)核心課程．通過本課程的學(xué)習(xí)，使學(xué)生具有現(xiàn)同時，也要培養(yǎng)素質(zhì)和使用所學(xué)知識分基礎(chǔ)理論與專業(yè)課程打下良好的任務(wù)的同時，通過適當(dāng)?shù)膶?shí)離散數(shù)學(xué)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的代數(shù)學(xué)的觀點(diǎn)和方法，并初步掌握處理離散結(jié)構(gòu)所必須的描述工具和方法．學(xué)生抽象思維和慎密概括的能力，使學(xué)生具有良好的開拓專業(yè)理論的析和解決實(shí)際問題的能力，為學(xué)生以后學(xué)習(xí)計(jì)算機(jī)基礎(chǔ)．本課程是一門理論性較強(qiáng)的課程，要求在完成基礎(chǔ)知識教學(xué)際應(yīng)用的介紹，提高學(xué)生的實(shí)際應(yīng)用能力的培養(yǎng)．Ⅰ．關(guān)于課程考核說明與實(shí)施要求1．考核對象：本課程考核說明適用于中央廣播電視大學(xué)開放教育本科電氣信息類計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的學(xué)生．2．考核依據(jù)材為依據(jù)制定《離散數(shù)學(xué)》．3．考核方式：本課程的考核實(shí)行形成性考核和終結(jié)性考核相結(jié)合的4．課程綜合成績的記分方法：形成性考核占課程考核成績的30%，即形成性考核的成績滿分為30分；終結(jié)性考核成績占課程考核成績的70%，即終結(jié)性考核成績滿分70分．課程考核成績滿分100分，60分以上為合格，可以獲得課程學(xué)分．5．形成性考核的說明：見附件一。6．終結(jié)性考試的說明：終結(jié)性考核實(shí)行全國統(tǒng)一考核，根據(jù)本課程考試說明，由中央命題，統(tǒng)一評分標(biāo)準(zhǔn)，統(tǒng)一考核時間．：本考核說明是以本課程的教學(xué)大綱（2007年6月審定）和指定的參考教的．本課程指定的參考教材是李偉生主編的、中央廣播電視大學(xué)出版社出版的方式．電大統(tǒng)一(1)考核要求：本課程考核要求分三個層次，有關(guān)概念、性質(zhì)和定理等理論方面的要求從高到低為理解，了解和知道；有關(guān)方法、公式和法則等的要求從高到低為熟練掌握，掌握和會．(2)組卷原則：終結(jié)性考原理和基本運(yùn)算．命題覆蓋面可適當(dāng)寬些，但試題難度要適中，題量要適當(dāng)．易、中、較難題目在試卷中分配為4：4：2．(3)試題類型及結(jié)構(gòu)：單項(xiàng)選擇題的分?jǐn)?shù)的分?jǐn)?shù)占12％，判斷說明題的分?jǐn)?shù)占14％，計(jì)算題的分?jǐn)?shù)項(xiàng)選擇題和填空題主要涉及基本概念、基本理論、重要性質(zhì)和結(jié)論、公式及其簡單計(jì)算．項(xiàng)選擇題給出四個備選答案，其一是正確選項(xiàng)．填空題只需填寫正確結(jié)論，不寫計(jì)算、推論核的考核內(nèi)容和要求以本考核說明為準(zhǔn)，要求考核基本概念、基本占15％，填空題的分?jǐn)?shù)占15％，公式翻譯題占8％．單占36％；證明題的分?jǐn)?shù)單

過程或理由．邏輯公式翻譯題主要是利用命題邏輯和謂詞邏輯的基本概念及命題聯(lián)結(jié)詞、謂詞量詞，將一個陳述句翻譯一個命題或結(jié)論速度，要求成命題公式或謂詞公式．判斷說明題是對給定的作出對與錯的判斷，并給出簡單的說明．計(jì)算題主要考核學(xué)生的基本運(yùn)算技能和寫出化簡、計(jì)算過程．證明題主要考查應(yīng)用概念、性質(zhì)、定理及重要結(jié)論進(jìn)行邏輯推理的能力，要求寫出推理過程．(4)考核形式：采用半開卷、筆試方式，試卷滿分100分．半開卷考試允許考生攜帶指定的一張專用A4紙（統(tǒng)一印制），考生可以將自己對全課程學(xué)習(xí)內(nèi)容的總結(jié)歸納寫在這張A4紙上帶入考場，作為答卷時參考．(5)考核時間：90分鐘．Ⅱ．考核內(nèi)容與考核要求第1章集及合其運(yùn)算考核知識點(diǎn)1．集，合元素，集的合表示，全集，空集2．集的合包含、相等，子集，冪集3．集的合并、交、補(bǔ)、差、對稱差等運(yùn)算及其運(yùn)算律4．容斥原理考核要求1．理解集的合概念，容斥原理．2．理解集的合包含、子集、相等和冪集等概念交、補(bǔ)、差和對稱差等運(yùn)算，會用文氏圖表示集的合各種3．掌握用集運(yùn)合算基本規(guī)律證明集合恒等式的方法．，熟練掌握集的合表示方法和集的合并、運(yùn)算．4．掌握利用容斥原理進(jìn)行計(jì)數(shù)的方法．第2章關(guān)系與函數(shù)考核知識點(diǎn)1．有序?qū)偷芽▋悍e2．關(guān)系及其運(yùn)算性質(zhì)3．二元關(guān)系的矩陣與圖4．復(fù)合關(guān)系與逆關(guān)系5．二元關(guān)系的性質(zhì)6．等價關(guān)系與等價類7．偏序關(guān)系、復(fù)蓋集與哈斯圖，極大(小)元，最大(小)元，上(下)界，最小上界，最大下界8．函數(shù)反函數(shù)復(fù)合函數(shù)單射滿射和雙射考核要求1．了解有序?qū)偷芽▋悍e的概念，掌握笛卡兒積的運(yùn)算．2．理解關(guān)系的概念：包括二元關(guān)系、空關(guān)系、全關(guān)系、恒等關(guān)系．掌握關(guān)系的集合表示、關(guān)系矩陣和關(guān)系圖，掌握關(guān)系的運(yùn)算．3．掌握求復(fù)合關(guān)系和逆關(guān)系的方法．4．理解關(guān)系的性質(zhì)(自反性和反自反性、對稱性和反對稱性、傳遞性)，掌握其判別方法．5．理解等價關(guān)系和偏序關(guān)系概念，掌握等價關(guān)系、偏序關(guān)系的判定，掌握等價類、復(fù)蓋集的求法和作偏序關(guān)系哈斯圖的方法．知道極大(小)元，最大(小)元的概念，會求極大(小)元、最大(小)元、最小上界和6．理解函數(shù)概念：函數(shù)(映射)，函數(shù)相等，最大下界．復(fù)合函數(shù)和反函數(shù)．7．理解單射、滿射和雙射等概念，掌握其判別方法．第3章圖的基本概念與性質(zhì)考核知識點(diǎn)1．圖的概念與表示，有向圖，無向圖，簡單圖，完全圖，結(jié)點(diǎn)的度數(shù)，圖的同構(gòu)，子圖、補(bǔ)圖2．通路，通路的長度，初級通路，簡單通路，回路，初級回路，簡單回路3．圖的4．圖的連通性與連通度概念、判定，點(diǎn)割集與割點(diǎn)，邊割集與割邊矩陣表示、鄰接矩陣、可達(dá)性矩陣及其計(jì)算5．最短路徑考核要求1．理解圖的基本概念：結(jié)點(diǎn)、邊、有向圖，無向圖、簡單圖、完全圖、結(jié)點(diǎn)的度數(shù)、圖的同構(gòu)子圖等，理解握手定理．2．了解通路與回路的概念：簡單通路、初級通路和復(fù)雜通路，簡單回路、初級回路和復(fù)雜回路，會求通路和回路的長度．3．了解無向圖的連通性，會求無向圖的連通分支．了解點(diǎn)割集、割點(diǎn)、邊割集、割邊、點(diǎn)連通度、邊連通度等概念．4．了解有向圖的強(qiáng)連通性、單向連通性、弱連通性；會判別有向圖連通性的類型．5．理解圖的矩陣表示法、鄰接矩陣、可達(dá)性矩陣的概念，掌握鄰接矩陣、可達(dá)性矩陣的有關(guān)計(jì)算．6．知道最短路徑的概念，會最短路徑的算法．第4章幾種特殊圖考核知識點(diǎn)1．歐拉通路(回路)，歐拉圖2．哈密通頓路(回路)，哈密圖頓

3．平面圖，歐拉公式4．對偶圖及著色考核要求1．了解歐拉回路2．了解3．了解平面圖、歐拉圖的概念及性質(zhì)，掌握歐拉圖的判別方法．漢密爾頓回路、漢密爾頓圖的概念及性質(zhì)，掌握漢密爾頓圖的判別方法．的概念：平面圖、面、邊界、面的次數(shù)和非平面圖，掌握平面圖的判別方法，掌握歐拉公式的應(yīng)用．4．理解平面圖與對偶圖的關(guān)系、對偶圖在圖著色中的作用，掌握著色算法；5．掌握圖論中常用的證明方法．第5章樹及其應(yīng)用考核知識點(diǎn)1．樹的定義及性質(zhì)2．生成樹與最小生成樹的概念，最小生成樹的Kruskal算法3．根樹的概念及性質(zhì)4．最優(yōu)樹的概念，最優(yōu)樹的Huffman算法，前綴碼的求法考核要求1．了解小生成樹的Kruskal算法．2．了解無向樹、樹葉、分支點(diǎn)、平凡樹、生成樹和最小生成樹等概念及性質(zhì)，掌握最有向樹、根樹、有序樹、最優(yōu)二元（叉）樹等概念及性質(zhì)，掌握最優(yōu)樹的Huffman算法．3．掌握利用最優(yōu)樹產(chǎn)生前綴碼的方法．第6章命題邏輯考核知識點(diǎn)1．命題與聯(lián)結(jié)詞(否定、析取、合取、蘊(yùn)含、等價)，真值與真值表2．命題公式3．命題公式4．析取范式、合取范式、極小(大)項(xiàng)，、主合取范式的概念與求法的解釋的等值式與蘊(yùn)涵式，等值演算主析取范式5．命題邏輯的推理理論考核要求1．理解命題聯(lián)結(jié)詞概念，掌握命題公式的翻譯（命題符號化）及判斷語句是不是命題的方法．2．熟練掌握求給定公式真值表的方法．3．掌握基本等值式以及用真值表法和等值演算法判別公式類型和公式等值的方法．4．了解析取(合取)范式概念，理解極小(大)項(xiàng)的概念和主析取(合取)范式概念，熟練掌(合取)范式的方法．5．掌握命題公式的的直接證明方法與間接證明方法．握用基本等值式或真值表將公式化為主析取第7章謂詞邏輯考核知識點(diǎn)1．謂詞，量詞，個體詞，個體域，變元2．謂詞公式的解釋3．前束范式的概念與求法4．謂詞公式的等值式與蘊(yùn)涵式5．謂詞邏輯的推理理論考核要求1．理解謂詞、量詞、個體詞、個體域、全域、原子公式、謂詞公式和變元等概念．掌握謂詞公式的翻譯．2．掌握在有限個體域下消去公式的量詞和求公式在給定解釋下真值的方法．3．掌握謂詞演算的等值式和重言蘊(yùn)含式．4．了解前束范式的概念，會求謂詞公式的前束范式的方法．5．了解謂詞邏輯推理的規(guī)則，掌握謂詞公式的證明與推導(dǎo)方法．Ⅲ．試題類型及規(guī)范解答舉例一、單項(xiàng)選擇題1．設(shè)a是集合A的元素，則以下正確的是()．A．{a}aB．{a}A{a}AD．a(chǎn)AC．選項(xiàng)B正確，填寫答案：“B”．（容易題）2．有圖D＝<V，E>，則圖D的邊數(shù)是A．E(E－1)/2B．V(V－1)/2C．E(E－1)D正確，填寫答案：“D”．（中等題）二、填空題3．含有填寫答案：“(PQR)(PQR)”．（較難題）4．設(shè)集合A={1,2,3,4}，B={6,8,12}，A到B的二元關(guān)系向完全()．D．V(V－1)選項(xiàng)三個命題變項(xiàng)P，Q，R的命題公式PQ的主析取范式是．R＝{x,yy2x,xA,yB}R－1＝填寫答案：{<6,3>,<8,4>}．（容易題）三、公式翻譯題5．將請語句“除非你去，否則我不去”翻譯成命題公式．解：設(shè)命題P：你去；Q→P或者┐P→┐Q．6．請將語句P（x）：x是人；則謂詞公式：(x)(P(x)∧Q(x))∧┐((x)(P(x)→Q(x)))Q：我去．則命題公式為：（中等題）“盡管有人努力工作了，但未必一切人都努力工作．”翻譯成謂詞公式．解：設(shè)Q（x）：x努力工作．（較難題）四、判斷說明題R，S是集合A上傳遞的關(guān)系，判斷RS是否具有傳遞性，并說明理由．7．設(shè)解：RS不一定是傳遞的關(guān)系．例如集合A={1,2,3}上的關(guān)系R={<1,2>}，S={<2,3>}，都是A上傳遞的關(guān)系．但是，RS={<1,2>，<2,3>}不是A上傳遞的．（中等題）8．用真值表判斷命題公式(PQ)((PQ)P)的類型．解：命題公式(PQ)((PQ)P)的真值表如下PQPQPQ(PQ)P(PQ)((PQ)P)001101011101000100110011（容易題）原式為可滿足式.五、計(jì)算題9．設(shè)E{,,,,},A{,},B{,,},C{,}，求：（1）(AB)~C；（2）P(A)－P(C)；（3）AB．1）(AB)~C={1}{1,3,5}{1,3,5}（2）P(A)P(C){,{1},{4},{1,4}}{,{2},{4},{2,4}}解：（{{1},{1,4}}（3）AB=(AB)－（AB）={1,2,4,5}{1}{2,4,5}（容易題）10．（1）求命題公式(PQ)(PQ)的主析取范式；（2）求該命題公式的成假賦值．(PQ)(PQ)(PQ)(PQ)1）解：（PQ（2）因?yàn)樵撁}公式的成真賦值是（1，0），所以成假賦值為（0，0），（0，1），（1，1）（中等題）六、證明題11．設(shè)G是連通簡單平面圖，則它一定有一個度數(shù)不超過5的結(jié)點(diǎn)．（提示：用反證法）證：因?yàn)镚是連通簡單平面圖，它的每個面至少有3條，邊所以有3r2e，即r23e（其中r，e分別為圖G的面數(shù)和邊數(shù)）假設(shè)結(jié)論不成立，則每個結(jié)點(diǎn)的度數(shù)都大于等于6．則有e6v2ev，即有（其中v是圖G的結(jié)點(diǎn)數(shù)）3e2evree=02=由歐拉公式：33矛盾．所以G中至少有一個結(jié)點(diǎn)的度數(shù)小于或等于5．（較難題）IV．樣卷（一）一、單項(xiàng)選擇題（每小題3分，本題共15分）1．若集合A＝{2，a，{3}，4}，則下列表述正確的是(A．{a}AB．{3}AC．{3}A)．D．A2．設(shè)集合A={a,b}，則A上的二元關(guān)系R={<a,a>,<b,b>}是A上的(A．是等價關(guān)系但不是偏序關(guān)系B．是偏序關(guān)系但不是等價關(guān)系C．既是等價關(guān)系又是偏序關(guān)系A(chǔ)．不是等價關(guān)系也不是偏序關(guān)系3．設(shè)圖G的鄰接矩陣為)關(guān)系．0010000011100000100101010則G的邊數(shù)為(A．5)．B．6C．3)．D．44．無向圖G存在歐拉通路，當(dāng)且僅當(dāng)(A．G中所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)B．G中至多有兩個奇數(shù)度結(jié)點(diǎn)C．G連通且所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)D．G連通且至多有兩個奇數(shù)度結(jié)點(diǎn)5．下列命題公式是等值的為(A．PQ，PQ)．B．A(BA)，A(AB)D．A(AB)，BC．Q(PQ)，Q(PQ)二、填空題（每小題3分，本題共15分）6．設(shè)A,B為任意集合，命題AB的條件是．7．設(shè)集合A＝{a,b,c}，R是A上的二元關(guān)系，其關(guān)系圖如圖一所示：acb圖一那么R的關(guān)系矩陣為：MR＝．8．設(shè)G是連通平面圖，v,e,r分別表示G的結(jié)點(diǎn)數(shù)，邊數(shù)和面數(shù)，則v,e和r滿足的關(guān)系式是．9．設(shè)G＝<V,E>是有p個結(jié)點(diǎn)，s條邊的連通圖，則從G中刪去條邊，才能確定圖G的一棵生成樹．D＝{1,2},那么謂詞公式xA(x)yB(y)消去量詞后的等值式10．設(shè)個體域?yàn)椋?、公式翻譯題（每小題6分，本題共12分）11．請將語句“今天不是天晴”翻譯成命題公式．12．請將語句“如果天不下雪，我有時間，那么我就去市里”翻譯成命題公式．四、判斷說明題（每小題7分，本題共14分）13．如果R1和R2是A上的自反關(guān)系，判斷結(jié)論：“R1∪R2是自反的”是否成立？并說明v5v4ndeg理由．v1cfh14．圖G(如圖二所示)能否一筆畫出？說明a理由．若能畫出，請寫出一條通路或回路．v2bv3圖二五．計(jì)算題（每小題12分，本題共36分）15．設(shè)謂詞公式x(P(x,y)zQ(y,x,z))yR(y,z)F(y)．（1）試寫出量詞的轄域；（2）指出該公式的自由變元和約束變元．16．設(shè)G=<V，E>，V={v1，v2，v3，v4，v5}，E={(v1,v2)，(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)}．（1）試給出G的圖形表示；（2）寫出其鄰接矩陣；（3）求出每個結(jié)點(diǎn)的度數(shù)．17．設(shè)集合A＝{a,b,c,d}上的二元關(guān)系R的關(guān)系圖如圖三所示．da（1）寫出R的表達(dá)式；（2）寫出R的關(guān)系矩陣；（3）求出R2．cb六、證明題（本題共8分）圖三19．試證明集合等式：A(BC)=(AB)(AC)．樣卷（二）一、單項(xiàng)選擇題（每小題3分，本題共15分）1．非空集合A上的二元關(guān)系R，滿足()，則稱R是等價關(guān)系．A．自反性，對稱性和傳遞性B．反自反性，對稱性和傳遞性C．反自反性，反對稱性和傳遞性D．自反性，反對稱性和傳遞性2．下列數(shù)組中，能A．(1,1,2,3)B．(1,2,3,4,5)構(gòu)成無向圖的度數(shù)列的數(shù)組是()．C．(2,2,2,2)D．(1,3,3)3．設(shè)G是有n個結(jié)點(diǎn)，m條邊的連通圖，必須刪去G的()條邊，才能確定G的一棵生成樹．A．mn1B．mn4．命題公式(PQ)的主析取范式是(BPQC．mn1)．C．PQD．nm1D．PQA．PQ5．表達(dá)式x(P(x,y)Q(z))y(R(x,y)zQ(z))中x的轄域是()．A．P(x,y)二、填空題（每小題3分，本題共15分）6．設(shè)集合A＝{b，c}，那么集合A的冪集合P(A)=B．P(x,y)Q(z)C．R(x,y)D．P(x,y)R(x,y)．7．設(shè)A，B為有限集，且m,n,那末A與B間存在雙射，當(dāng)且僅當(dāng)．8．已知圖G中有1個1度結(jié)點(diǎn)，2個2度結(jié)點(diǎn)，3個3度