離散數(shù)學(xué)復(fù)習(xí)提綱

《離散數(shù)學(xué)》復(fù)習(xí)提綱第一章命題邏輯

命題符號(hào)化及聯(lián)結(jié)詞命題公式及分類

真值函數(shù)、聯(lián)結(jié)詞全功能集的概念命題公式的等值、N個(gè)命題變項(xiàng)可構(gòu)成的不等值命題公式數(shù)、復(fù)合聯(lián)結(jié)詞等值演算會(huì)運(yùn)用等值式(P9)證明兩個(gè)公式是否相等、判斷公式的類型(P33:7-9)第一章命題邏輯

對(duì)偶與范式求命題公式的(主)析取范式及用途、(主)合取范式(P33：12，13)推理理論推理的形式結(jié)構(gòu)、常用推理規(guī)則(P23)構(gòu)造證明法（直接證明法、附加前提證明法、反證法）(P34-35：18,19)本章的應(yīng)用P11例11，P27例28，P34：15第二章一階邏輯一階邏輯基本概念、命題符號(hào)化

謂詞概念，掌握謂詞邏輯下符號(hào)化命題的要點(diǎn)一階邏輯公式、解釋的概念，公式分類公式的解釋、代換實(shí)例(P53-54：5，13)一階邏輯等值式、前束范式量詞否定等值式（P46）量詞轄域收縮和擴(kuò)張等值式(P47)量詞分配等值式(P47)第二章一階邏輯一階邏輯推理理論有關(guān)量詞的推理規(guī)則(EI,EG,UI,UG)及運(yùn)用本章應(yīng)用例：證明:“金屬都是導(dǎo)電體,銅是金屬，所以銅是導(dǎo)電體?！苯猓毫頕(x):x是金屬,G(x):x是導(dǎo)電體,a:銅前提：x(F(x)G(x))，F(xiàn)(a)

結(jié)論：G(a)

證明：①F(a)前提引入②x(F(x)G(x))前提引入③F(a)G(a)②UI④G(a)①③假言推理涉及到命題的符號(hào)表示有關(guān)量詞的推理規(guī)則量詞的等值式第三章集合的基本概念和運(yùn)算集合的基本概念集合之間的關(guān)系、、E、冪集，文氏圖集合的基本運(yùn)算會(huì)運(yùn)用集合運(yùn)算算律(P60-61)證明有關(guān)集合運(yùn)算的命題成立與否、進(jìn)行化簡(jiǎn)集合中元素的計(jì)數(shù)(本章應(yīng)用)包含排斥原理（P63例9，10，P65-67例11-13）第四章二元關(guān)系與函數(shù)集合的笛卡兒積與二元關(guān)系笛卡兒積的性質(zhì)(P83)和基本集合運(yùn)算規(guī)則及重要結(jié)論；重要關(guān)系(、E、I、L、D、)關(guān)系的運(yùn)算dom、ran、fld，R-1和合成R°S、關(guān)系的冪運(yùn)算關(guān)系的性質(zhì)(判斷、證明)自反性、反自反性、對(duì)稱性、反對(duì)稱性、傳遞性關(guān)系運(yùn)算與性質(zhì)的保持(P87)、關(guān)系性質(zhì)的判斷充要條件關(guān)系的閉包對(duì)稱閉包、自反閉包和傳遞閉包的概念和構(gòu)造方法第四章二元關(guān)系與函數(shù)等價(jià)關(guān)系和偏序關(guān)系等價(jià)關(guān)系定義、等價(jià)類，商集、劃分及其關(guān)系；偏序關(guān)系定義、可比、蓋住概念，哈斯圖，偏序集特殊元的辨別函數(shù)的定義和性質(zhì)滿射、單射、雙射的判斷和證明要領(lǐng)雙射函數(shù)的構(gòu)造函數(shù)的復(fù)合和反函數(shù)函數(shù)復(fù)合運(yùn)算及復(fù)合函數(shù)的性質(zhì)確定，反函數(shù)的計(jì)算本章應(yīng)用等價(jià)類及劃分,構(gòu)造雙射函數(shù)第五章圖的基本概念無向圖及有向圖頂點(diǎn)度的概念，握手定理、推論及應(yīng)用；圖的同構(gòu)條件及判斷；簡(jiǎn)單圖、完全圖、子圖、生成子圖、補(bǔ)圖自補(bǔ)圖等概念通路、回路、圖的連通性無向圖和有向圖的連通性概念；刪頂(集)操作、刪邊(集)操作的概念；點(diǎn)割集（割點(diǎn)）、邊割集（橋）的定義圖的矩陣表示關(guān)聯(lián)矩陣、有向圖的鄰接矩陣定義和性質(zhì)和應(yīng)用

(P126)最短路徑和工程網(wǎng)絡(luò)的關(guān)鍵路徑（本章應(yīng)用）P129例3，P130例4，P138：19，20第六章特殊的圖

二部圖:(完全)二部圖定義、匹配概念、Hall定理及應(yīng)用。歐拉圖：(半)歐拉圖的定義及判別方法（充要條件）哈密頓圖(半)哈密頓圖定義，區(qū)分哈密頓性的充分條件和必要條件。平面圖平面圖的面、邊、面次數(shù)間的關(guān)系；極大平面圖、極小非平面圖；歐拉公式及推廣(定理6.10,6.11)平面圖判定定理(定理6.13,6.14)對(duì)偶圖的構(gòu)造和性質(zhì)本章應(yīng)用二部圖(P154:5)，哈密頓回路(P154:15),平面圖第七章樹無向樹及生成樹樹、無向樹的定義及性質(zhì)（定理7.1-7.3）；圖的生成樹概念，基本回路系統(tǒng)和割集系統(tǒng)；帶權(quán)圖的最小生成樹（避圈法）根樹及其應(yīng)用（本章應(yīng)用）有向樹、根樹概念，根樹的分類最優(yōu)二叉樹哈夫曼算法，前綴碼與最佳前綴碼的產(chǎn)生（P164例7）第八章組合分析初步加法法則和乘法法則基本排列組合的計(jì)數(shù)方法多重集的組合與排列公式(定理8.6，定理8.7)遞推方程的求解與應(yīng)用遞推方程的定義和求解過程(P181-182例13，14)知識(shí)點(diǎn)掌握要求第一章命題邏輯（約10-15%）1.聯(lián)結(jié)詞的定義(含義及真值表定義)和聯(lián)結(jié)詞全功能集.2.會(huì)命題符號(hào)化.3.永真式的證明.4.永真和蘊(yùn)涵式的證明,記住并能熟練應(yīng)用常用公式.5.等值公式的證明,記住并能熟練應(yīng)用常用公式（P9基本等值式,等值演算、等值代換）.6.掌握對(duì)偶的定義、會(huì)求命題公式的（主）范式,能應(yīng)用（主）范式解決問題（極大項(xiàng)和極小項(xiàng)的概念）.7.熟練掌握命題邏輯推理方法(P23基本蘊(yùn)含式和P24常用推理規(guī)則).131314第二章謂詞邏輯（約10-15%）1.準(zhǔn)確掌握有關(guān)概念.2.會(huì)命題符號(hào)化（尤其注意特性謂詞的使用）.(如P38-41例2.1-2.5)3.掌握常用的等價(jià)公式和永真蘊(yùn)涵式.包括:

帶量詞的公式在論域內(nèi)展開式,量詞否定,量詞轄域擴(kuò)充,

量詞分配公式(P472.3).4.會(huì)用等價(jià)公式求謂詞公式的真值.(代換實(shí)例、公式的解釋P50-53例題和章后相關(guān)習(xí)題)5.會(huì)化前束范式6.了解掌握謂詞邏輯推理.141515第三章集合的基本概念與運(yùn)算（約10-15%）1.集合的表示,冪集,全集,空集.2.集合的三種關(guān)系(包含,相等,真包含)的定義及證明.3.集合的五種運(yùn)算（交、并、相對(duì)補(bǔ)（差）、絕對(duì)補(bǔ)、對(duì)稱差）及相關(guān)性質(zhì).4.集合代數(shù)的算律（P61-62）5.集合中元素的計(jì)數(shù)、會(huì)應(yīng)用包含排斥原理.第四章二元關(guān)系和函數(shù)（約15-20%）1.關(guān)系的概念,表示方法（集合、關(guān)系矩陣、關(guān)系圖）.2.二元關(guān)系的性質(zhì)的定義,熟練掌握性質(zhì)的判斷及證明.3.關(guān)系的運(yùn)算：掌握定義域、值域和域的概念、掌握關(guān)系的復(fù)合（注意：教材中定義的復(fù)合為左復(fù)合）,求逆及閉包運(yùn)算(計(jì)算的方法及有關(guān)性質(zhì))4.掌握等價(jià)關(guān)系的判斷、證明以及求等價(jià)類和商集.5.偏序關(guān)系的判斷,會(huì)畫Hasse圖,會(huì)求一個(gè)子集的極小(大)元,最小(大)元,上界與下界,最小上界及最大下界.6.函數(shù)的定義和性質(zhì)（判斷單、滿、雙射）.7.會(huì)計(jì)算函數(shù)的復(fù)合(左復(fù)合),求反函數(shù).知道有關(guān)性質(zhì).161617第五~七章圖論（約25-35%）1.掌握?qǐng)D的基本概念（無向圖、有向圖、有限圖、頂點(diǎn)、無向邊、有向邊、n階圖、零圖、平凡圖、關(guān)聯(lián)、相鄰等）。2.熟練掌握?qǐng)D中關(guān)于頂點(diǎn)度數(shù)的概念和握手定理

(會(huì)應(yīng)用)3.掌握通路、回路及其相關(guān)概念和定理（P160-161）。4.掌握連通、強(qiáng)連通、距離、連通分支及連通分支數(shù)的概念和點(diǎn)、邊割集的概念.5.會(huì)求圖的矩陣（有向、無向圖的關(guān)聯(lián)矩陣和有向圖的鄰接矩陣、有向圖的可達(dá)矩陣）.利用鄰接矩陣計(jì)算圖中指定長度的通路和回路的個(gè)數(shù).6.掌握二部圖及相關(guān)概念（二部圖充要條件、匹配、極大匹配、最大匹配、完備匹配、完美匹配等）、會(huì)使用相異性條件和t條件判定完備匹配的存在性。17187.會(huì)判定歐拉圖和漢密爾頓圖.8.會(huì)判定平面圖,掌握歐拉公式.9.會(huì)畫平面嵌入的對(duì)偶圖.第8章組合分析初步（共約10-15%）1.不允許重復(fù)的排列和組合2.允許重復(fù)（多重集）的排列和組合（重點(diǎn)）3.遞推關(guān)系和遞推方程的求解18《離散數(shù)學(xué)》試題結(jié)構(gòu)卷面一.選擇題（20%）二.填空題（20%）三.計(jì)算題（20%）四.證明題（20%）五.應(yīng)用題（20%）各部分分?jǐn)?shù)比例第一部分?jǐn)?shù)理邏輯(約25%)第二部分集合論(約30%)第三部分圖論(約30%)第四部分組合分析(約15%)《離散數(shù)學(xué)》試題舉例一.選擇題（20%）1．設(shè)A、B、C為任意集合，則下列命題中，命題真值是真的是

。A．若AB=AC，則B=CB.

若A－B=

，則A=B

C．若AB=AC，則B=C

D.

二.填空題：（20%）1、公式

(pq)r的成真賦值是_____________《離散數(shù)學(xué)》試題舉例三.計(jì)算題：（20%）

1.用等值演算法判斷公式q(pq)的類型解:

q(pq)

q(pq)

q(pq)

p(qq)

p0

0由最后一步可知，該式為矛盾式.2.計(jì)算集合A={

，{}}的冪集解：P(A)=P({,{}})={,{},{{}},{,{}}}《離散數(shù)學(xué)》試題舉例四.證明題（20%）

證明A=BC=DAC=BD

證：任取<x,y><x,y>AC

xAyC

xByD

<x,y>BD

《離散數(shù)學(xué)》試題舉例五.應(yīng)用題：（20%）證明:“金屬都是導(dǎo)電體,銅是金屬，所以銅是導(dǎo)電體?！苯猓毫頕(x):x是金屬,G(x):x是導(dǎo)電體,a:銅前提：