離散數(shù)學本科期末復習提要

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

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

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

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

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

6、概念：函數(shù)、函數(shù)相等、復合函數(shù)和反函數(shù)。7、理解單射、滿射、雙射等概念，掌握其判別方法。[本章重點習題]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、關系的概念關系的概念是第二章全章的基礎，又是第一章集合概念的應用。因此，學生應該真正理解并熟練掌握二元關系的概念及關系矩陣、關系圖表示。2、關系的性

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

8、ai?1????RabRba????Raa???Rbb?３、關系的閉包在理解掌握關系閉包概念的基礎上，主要掌握閉包的求法。關鍵是熟記三個定理的結論：定理2，；定理3，；定理4，推論。??AIRRr????1???RRRs???niiRRt1??４、半序關系及半序集中特殊元素的確定理解與掌握半序關系與半序集概念的關鍵是哈斯圖。哈斯圖畫法掌握了，對于確定任一子集的最大（小）元，極大（小）元也就容易了。這里要注意，最大（?。┰c極大（?。┰?/p>