【正文】 例題分析]例1 設(shè)集合，判定下列關(guān)系，哪些是自反的，對(duì)稱的，反對(duì)稱的和傳遞的：解：均不是自反的；R4是對(duì)稱的；R1 ,R2 ,R3 , R4 ,R5是反對(duì)稱的；R1 ,R2 ,R3 , R4 ,R5是傳遞的。哈斯圖畫法掌握了，對(duì)于確定任一子集的最大（小）元，極大（小）元也就容易了。如若，則有，且。對(duì)于四種性質(zhì)的判定，可以依據(jù)教材中P49上總結(jié)的規(guī)律。[本章重點(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。掌握求關(guān)系的閉包 （自反閉包、對(duì)稱閉包、傳遞閉包）的方法。解 于是例2 設(shè)，試求： (1)； (2)； (3)； (4)； (5)； (6)。[疑難解析]集合的概念因?yàn)榧系母拍顚W(xué)生在中學(xué)階段已經(jīng)學(xué)過，這里只多了一個(gè)冪集概念，重點(diǎn)對(duì)冪集加以掌握，一是掌握冪集的構(gòu)成，一是掌握冪集元數(shù)為2n。掌握集合的表示法和集合的交、并、差、補(bǔ)等基本運(yùn)算。 學(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é)大綱，在原有離散數(shù)學(xué)課程的基礎(chǔ)上削減了教學(xué)內(nèi)容（主要是群與環(huán)、格與布爾代數(shù)這兩章及圖論的后三節(jié)內(nèi)容），使用的教材為中央電大出版的《離散數(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ǔ)。 教學(xué)要求的層次各章教學(xué)要求的層次為了解、理解和掌握。掌握集合運(yùn)算基本規(guī)律，證明集合等式的方法。集合恒等式的證明通過對(duì)集合恒等式證明的練習(xí)，既可以加深對(duì)集合性質(zhì)的理解與掌握；又可以為第三章命題邏輯中公式的基本等價(jià)式的應(yīng)用打下良好的基礎(chǔ)。解 (1) (2) (3) (4) (5) (6)例3 試證明 證明 第二章 二元關(guān)系[復(fù)習(xí)知識(shí)點(diǎn)]關(guān)系、關(guān)系矩陣與關(guān)系圖復(fù)合關(guān)系與逆關(guān)系 關(guān)系的性質(zhì)（自反性、對(duì)稱性、反對(duì)稱性、傳遞性） 關(guān)系的閉包（自反閉包、對(duì)稱閉包、傳遞閉包）等價(jià)關(guān)系與等價(jià)類偏序關(guān)系與哈斯圖（Hasse）、極大/小元、最大/小元、上/下界、最小上界、最大下界函數(shù)及其性質(zhì)（單射、滿射、雙射）復(fù)合函數(shù)與反函數(shù)本章重點(diǎn)內(nèi)容：二元關(guān)系的概念、關(guān)系的性質(zhì)、關(guān)系的閉包、等價(jià)關(guān)系、半序關(guān)系、映射的概念[復(fù)習(xí)要求]理解關(guān)系的概念：二元關(guān)系、空關(guān)系、全關(guān)系、恒等關(guān)系；掌握關(guān)系的集合表示、關(guān)系矩陣和關(guān)系圖、關(guān)系的運(yùn)算。理解等價(jià)關(guān)系和偏序關(guān)系的概念，掌握等價(jià)類的求法和偏序關(guān)系做哈斯圖的方法，極大/小元、最大/小元、上/下界、最小上界、最大下界的求法。[疑難解析] 關(guān)系的概念　　關(guān)系的概念是第二章全章的基礎(chǔ)，又是第一章集合概念的應(yīng)用。這其中對(duì)傳遞性的判定，難度稍大一點(diǎn)，這里要提及兩點(diǎn)：一是不破壞傳遞性定義，可認(rèn)為具有傳遞性。３、關(guān)系的閉包在理解掌握關(guān)系閉包概念的基礎(chǔ)上，主要掌握閉包的求法。這里要注意，最大（小）元與極大（?。┰荒茉谧蛹瘍?nèi)確定，而上界與下界可在子集之外的全集中確定，最小上界為所有上界中最小者，最小上界再小也不小于子集中的任一元素，可以與某一元素相等，最大下界也同樣。例2 設(shè)集合，A上的二元關(guān)系R為 （１）寫出R的關(guān)系矩陣，畫出R的關(guān)系圖；（２）證明R是A上的半序關(guān)系，畫出其哈斯圖；（３）若，且，求B的最大元，最小元，極大元，極小元，最小上界和最大下界。1 。 第三章　命題邏輯[復(fù)習(xí)知識(shí)點(diǎn)]１、命題與聯(lián)結(jié)詞（否定、析取、合取、蘊(yùn)涵、等價(jià)），復(fù)合命題２、命題公式與解釋，真值表，公式分類（恒真、恒假、可滿足），公式的等價(jià)３、析取范式、合取范式，極小（大）項(xiàng)，主析取范式、主合取范式 ４、公式類別的判別方法（真值表法、等值演算法、主析取/合取范式法）５、公式的蘊(yùn)涵與邏輯結(jié)果６、形式演繹本章重點(diǎn)內(nèi)容：命題與聯(lián)結(jié)詞、公式與解釋、析取范式與合取范式、公式恒真性的判定、形式演繹[復(fù)習(xí)要求]１、理解命題的概念；了解命題聯(lián)結(jié)詞的概念；理解用聯(lián)結(jié)詞產(chǎn)生復(fù)合命題的方法。５、理解公式蘊(yùn)涵與邏輯結(jié)果的概念，掌握基本蘊(yùn)涵式。具體方法有兩種，一是真值表法，對(duì)于任給一個(gè)公式，主要列出該公式的真值表，觀察真值表的最后一列是否全為1（或全為0），就可以判定該公式是否恒真（或恒假），若不全為0，則為可滿足的。關(guān)鍵有兩點(diǎn)：一是準(zhǔn)確理解掌握定義；另一是巧妙使用基本等價(jià)式中的分配律、同一律和互補(bǔ)律，結(jié)果的前一步適當(dāng)使用等冪律，使相同的短語(yǔ)（或子句）只保留一個(gè)。解 （1）求主析取范式， 方法1：利用真值表求解G0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1000000111010101101011111因此 方法2：推導(dǎo)法 （2）求主合取范式方法1：利用上面的真值表為0的有兩行，它們對(duì)應(yīng)的極大項(xiàng)分別為因此，方法2：利用已求出的主析取范式求主合取范式已用去6個(gè)極小項(xiàng)，尚有2個(gè)極小項(xiàng)，即 與 于是 例2 試證明公式為恒真公式。P218。R））218。216。R）218。Q）217。（216。Q218。P）218。P）217。216。216。R =（1217。R218。Q218。P218。R），216。證明：（1）216。R） 規(guī)則P （5）Q174。理解用解釋的方法證明等價(jià)式和蘊(yùn)涵式。公式與解釋能將一階邏輯公式表達(dá)式中的量詞消除，寫成與之等價(jià)的公式，然后將解釋I中的數(shù)值代入公式，求出真值。解 第五章 圖論[復(fù)習(xí)知識(shí)點(diǎn)]圖、完全圖、子圖、母圖、支撐子圖、圖的同構(gòu)關(guān)聯(lián)矩陣、相鄰矩陣權(quán)圖、路、最短路徑，迪克斯特拉算法（Dijkstra）樹、支撐樹、二叉樹 權(quán)圖中的最小樹，克魯斯卡爾算法（Kruskal）有向圖、有向樹本章重點(diǎn)內(nèi)容： 權(quán)圖的最短路、二叉樹的遍歷、權(quán)圖中的最優(yōu)支撐樹[復(fù)習(xí)要求]理解圖的有關(guān)概念：圖、完全圖、子圖、母圖、支撐子圖、圖的同構(gòu)。理解有向圖與有向樹的概念。權(quán)圖中的最優(yōu)支撐樹 權(quán)圖中的最優(yōu)支撐樹是圖中所帶權(quán)和最小的支撐樹，使用克魯斯卡爾（Kruskal）算法。（n2）/2例2 求下面有限圖中點(diǎn)u到各點(diǎn)間的最短路。 u2 , d(u, u2)=9, 路(u, u4, u3, u7, u2)u174。 u6 , d(u, u6)=13, 路(u, u1, u5, u6)u174。形成性考核占總成績(jī)的20%，以課程作業(yè)的形式進(jìn)行（共三次，由中央電大統(tǒng)一布置）；終結(jié)性考核即期末考試，占總成績(jī)的80%。試題類型試題類型有填空題（分?jǐn)?shù)約占20%）、單項(xiàng)選擇題（分?jǐn)?shù)約占14%）、計(jì)算題（分?jǐn)?shù)約占50%）和證明題（分?jǐn)?shù)約占16%）?？己嗽嚲眍}量分配試卷題量在各部分的分配是：集合論約占40%，數(shù)理邏輯約占40%，圖論約占20%。Q）174。3. 設(shè)G=（P，L）是圖，如果G是連通的，并且 ，則G是樹。X200。（（AB）199。（A199。Q）218。R）；（2）（P218。（216。（（P174。（P174。R }蘊(yùn)涵Q218。C）200。B199。（A199。B199。C） =（（A199。（（A199。~B）199。E） E為全集 =（A199。（~B200。（216。（P217。R））218。R）219。R）218。（216。 m6218。m6218。（Q218。（P217。（P217。（216。（P217。R）） 218。Q217。 Q 217。216。R） 218。R）218。（216。 m6218。m3219。Q）218。R）219。（Q218。[證明題]1. 證明： （（P174。（P174。Q）217。（216。（（216。Q218。R）219。（Q217。P218。Q）218。216。（216。（（Q218。Q218。R 219。216。216。R