離散數(shù)學(xué)本科期末復(fù)習(xí)提要

1、1《離散數(shù)學(xué)離散數(shù)學(xué)》本科期末復(fù)習(xí)提要本科期末復(fù)習(xí)提要四川電大孫繼榮2004年5月《離散數(shù)學(xué)》使用的教材為中央電大出版的《離散數(shù)學(xué)》（劉敘華等編）和《離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)書》（虞恩蔚等編）。離散數(shù)學(xué)主要研究離散量結(jié)構(gòu)及相互關(guān)系，使學(xué)生得到良好的數(shù)學(xué)訓(xùn)練，提高學(xué)生抽象思維和邏輯推理能力，為從事計(jì)算機(jī)的應(yīng)用提供必要的描述工具和理論基礎(chǔ)。其先修課程為：高等數(shù)學(xué)、線性代數(shù)；后續(xù)課程為：數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫、操作系統(tǒng)、計(jì)算機(jī)網(wǎng)絡(luò)等。課程的主要內(nèi)容課程的主

2、要內(nèi)容1、集合論部分（集合的基本概念和運(yùn)算、關(guān)系及其性質(zhì)）；2、數(shù)理邏輯部分（命題邏輯、謂詞邏輯）；3、圖論部分（圖的基本概念、樹及其性質(zhì)）。4、布爾代數(shù)學(xué)習(xí)建議學(xué)習(xí)建議離散數(shù)學(xué)是理論性較強(qiáng)的學(xué)科，學(xué)習(xí)離散數(shù)學(xué)的關(guān)鍵是對(duì)離散數(shù)學(xué)（集合論、數(shù)理邏輯和圖論）有關(guān)基本概念的準(zhǔn)確掌握，對(duì)基本原理及基本運(yùn)算的運(yùn)用，并要多做練習(xí)。教學(xué)要求的層次教學(xué)要求的層次各章教學(xué)要求的層次為了解、理解和掌握。了解即能正確判別有關(guān)概念和方法；理解是能正確表達(dá)有關(guān)概

3、念和方法的含義；掌握是在理解的基礎(chǔ)上加以靈活應(yīng)用。一、各章復(fù)習(xí)要求與重點(diǎn)一、各章復(fù)習(xí)要求與重點(diǎn)第一章第一章集合[復(fù)習(xí)知識(shí)點(diǎn)]1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、冪集2、集合的交、并、差、補(bǔ)等運(yùn)算及其運(yùn)算律（交換律、結(jié)合律、分配律、吸收律、DeMgan律等），文氏（Venn）圖3、序偶與迪卡爾積本章重點(diǎn)內(nèi)容：集合的概念、集合的運(yùn)算性質(zhì)、集合恒等式的證明[復(fù)習(xí)要求]1、理解集合、元素、子集、空集、全集、集合的

4、包含、相等、冪集等基本概念。2、掌握集合的表示法和集合的交、并、差、補(bǔ)等基本運(yùn)算。3、掌握集合運(yùn)算基本規(guī)律，證明集合等式的方法。4、了解序偶與迪卡爾積的概念，掌握迪卡爾積的運(yùn)算。[本章重點(diǎn)習(xí)題]P5~6，4、6；P14~15，3、6、7；P20，5、7。[疑難解析]1、集合的概念因?yàn)榧系母拍顚W(xué)生在中學(xué)階段已經(jīng)學(xué)過，這里只多了一個(gè)冪集概念，重點(diǎn)對(duì)冪集加以掌握，一是掌握冪集的構(gòu)成，一是掌握冪集元數(shù)為2n。2、集合恒等式的證明3射的概念[復(fù)

5、習(xí)要求]1、理解關(guān)系的概念：二元關(guān)系、空關(guān)系、全關(guān)系、恒等關(guān)系；掌握關(guān)系的集合表示、關(guān)系矩陣和關(guān)系圖、關(guān)系的運(yùn)算。2、掌握求復(fù)合關(guān)系與逆關(guān)系的方法。3、理解關(guān)系的性質(zhì)（自反性、對(duì)稱性、反對(duì)稱性、傳遞性），掌握其判別方法（定義、矩陣、圖）。4、掌握求關(guān)系的閉包（自反閉包、對(duì)稱閉包、傳遞閉包）的方法。5、理解等價(jià)關(guān)系和偏序關(guān)系的概念，掌握等價(jià)類的求法和偏序關(guān)系做哈斯圖的方法，極大小元、最大小元、上下界、最小上界、最大下界的求法。6、理解函數(shù)

6、概念：函數(shù)、函數(shù)相等、復(fù)合函數(shù)和反函數(shù)。7、理解單射、滿射、雙射等概念，掌握其判別方法。[本章重點(diǎn)習(xí)題]P25，1；P32~33，4，8，10；P43，2，3，5；P51~52，5，6；P59，1，2；P64，3；P74~75，2，4，6，7；P81，5，7；P86，1，2。[疑難解析]1、關(guān)系的概念關(guān)系的概念是第二章全章的基礎(chǔ)，又是第一章集合概念的應(yīng)用。因此，學(xué)生應(yīng)該真正理解并熟練掌握二元關(guān)系的概念及關(guān)系矩陣、關(guān)系圖表示。2、關(guān)系的性

7、質(zhì)及其判定關(guān)系的性質(zhì)既是對(duì)關(guān)系概念的加深理解與掌握，又是關(guān)系的閉包、等價(jià)關(guān)系、半序關(guān)系的基礎(chǔ)。對(duì)于四種性質(zhì)的判定，可以依據(jù)教材中P49上總結(jié)的規(guī)律。這其中對(duì)傳遞性的判定，難度稍大一點(diǎn)，這里要提及兩點(diǎn)：一是不破壞傳遞性定義，可認(rèn)為具有傳遞性。如空關(guān)系具有傳遞性，同時(shí)空關(guān)系具有對(duì)稱性與反對(duì)稱性，但是不具有自反性。另一點(diǎn)是介紹一種判定傳遞性的“跟蹤法”，即若，??????RaaRaaRaaii????13221??則。如若，則有，且。??Ra

8、ai?1????RabRba????Raa???Rbb?３、關(guān)系的閉包在理解掌握關(guān)系閉包概念的基礎(chǔ)上，主要掌握閉包的求法。關(guān)鍵是熟記三個(gè)定理的結(jié)論：定理2，；定理3，；定理4，推論。??AIRRr????1???RRRs???niiRRt1??４、半序關(guān)系及半序集中特殊元素的確定理解與掌握半序關(guān)系與半序集概念的關(guān)鍵是哈斯圖。哈斯圖畫法掌握了，對(duì)于確定任一子集的最大（?。┰瑯O大（?。┰簿腿菀琢恕＿@里要注意，最大（?。┰c極大（小）元只