計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)(上)離散數(shù)學(xué)部分

1、計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)(上)離散數(shù)學(xué)部分期末復(fù)習(xí)中央電大基礎(chǔ)部數(shù)理教研室計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)是中央廣播電視大學(xué)本科開放教育計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)學(xué)生必修的一門專業(yè)基礎(chǔ)課程，是學(xué)習(xí)專業(yè)理論必不可少的數(shù)學(xué)工具。 本課程分兩個(gè)學(xué)期學(xué)習(xí)，本學(xué)期的教學(xué)內(nèi)容是“計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)(上)¾¾離散數(shù)學(xué)”部分，共計(jì)72學(xué)時(shí)，4學(xué)分。本學(xué)期使用的教材是由任現(xiàn)淼主編、吳裕樹副主編的計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)(上)¾¾離散數(shù)學(xué)，由中央廣播電視大學(xué)出版社出版。一、期末考試題型試題類型及分?jǐn)?shù)分別為單項(xiàng)選擇題和填空題各有5題，分?jǐn)?shù)約占25；化簡解答題與計(jì)算題，分?jǐn)?shù)約占56；證明題，分?jǐn)?shù)約占19。各章分?jǐn)?shù)的比例大致與

2、其所用課時(shí)比例相同。單項(xiàng)選擇題和填空題主要涉及基本概念、基本理論、重要性質(zhì)和結(jié)論、公式及其簡單計(jì)算。單項(xiàng)選擇題給出四個(gè)備選答案，其一正確。填空題只需填寫正確結(jié)論，不寫計(jì)算、推論過程或理由?；喗獯痤}與計(jì)算題主要考核學(xué)員的基本運(yùn)算技能和速度，要求寫出計(jì)算過程。證明題主要考查應(yīng)用概念、性質(zhì)、定理及重要結(jié)論進(jìn)行邏輯推理的能力，要求寫出推理過程。 本學(xué)期期末復(fù)習(xí)應(yīng)以中央電大考試處編發(fā)的計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)(上)離散數(shù)學(xué)部分考核說明為依據(jù)。 二、各章復(fù)習(xí)要求和重點(diǎn)第1章 命題邏輯 復(fù)習(xí)要求1. 理解命題概念，掌握判斷語句是不是命題的方法。 判斷一個(gè)語句是否為命題，應(yīng)首先判斷它是否為陳述句。再判斷它是否有唯一的

3、真值。因此，命題必須具備二個(gè)條件：其一，語句是陳述句；其二，語句有唯一確定的真假意義。2. 了解六個(gè)聯(lián)結(jié)詞概念，掌握由它們構(gòu)成的公式及真值表：ØP(否定式); PÙQ(合取式);PÚQ(析取式);P® Q (蘊(yùn)含式);P« Q (等價(jià)式)；PÚ Q (不可兼析取式)。會將命題符號化。 熟練掌握求給定公式真值表的方法。3. 理解公式、公式解釋、永真式(重言式)、永假式(矛盾式)和可滿足式等概念。 掌握基本等值式以及用真值表法和等值演算法判別公式類型和公式等值的方法。判別公式類型的真值表法：對于任給一個(gè)公式，列出該公式的真值表，觀察真值表

4、的最后一列的情況。若真值表的最后一列全部為1，則該公式為永真式；若真值表的最后一列全部為0，則該公式是永假式；若真值表的最后一列既非全部為1，又非全部為0，則該公式是可滿足式。 判別公式類型的等值演算法：利用基本等值式(雙重否定律、冪等律、交換律、結(jié)合律、分配律、吸收律、摩根律、同一律、零律、否定律、蘊(yùn)含等值式、等價(jià)等值式、假言易位和等價(jià)否定等值式等)，對給定公式進(jìn)行等值推導(dǎo)，若該公式的真值為1，則該公式是永真式；若該公式的真值為0，則該公式為永假式。 4. 了解析取(合取)范式概念，理解極小(大)項(xiàng)的概念和主析取(合取)范式概念，熟練掌握用基本等值式或真值表將公式化為主析取(合取)范式的方法

5、。求析取(合取)范式的步驟： 將公式中的聯(lián)結(jié)詞都化成Ø，Ù，Ú，在析取(合取)范式中不能有聯(lián)結(jié)詞®，«，Ú； 將否定聯(lián)結(jié)詞Ø消去或移到各命題變項(xiàng)之前； 利用分配律、結(jié)合律等，將公式化為析取(合取)范式。求命題公式A的主析取(合取)范式的步驟 求公式A的析取(合取)范式； “消去”析取(合取)范式中所有永假式(永真式)的析取項(xiàng)(合取項(xiàng))，如PÙØP(PÚØP)用0(1)替代。用冪等律將析取(合取)范式中重復(fù)出現(xiàn)的合取項(xiàng)(析取項(xiàng))或相同的變項(xiàng)合并，如P Ù P (P Ú

6、 P)用P替代，miÚ mi (Mi Ù Mi)用mi (Mi)替代。 若析取(合取)范式的某個(gè)合取項(xiàng)(析取項(xiàng))B不含有命題變項(xiàng)Pi或Ø Pi ，則添加Pi ÚØ Pi (Pi ÙØ Pi )，再利用分配律展開，使得每個(gè)合取項(xiàng)(析取項(xiàng))的命題變項(xiàng)齊全； 將極小(極大)項(xiàng)按由小到大的順序排列，用S(P)表示。5. 了解有效結(jié)論(邏輯結(jié)果)的概念，掌握判斷重言蘊(yùn)含式(推理是否有效)的五種方法 (1) 真值表法；(2) 等值演算法(記住基本等值式)；(3) 主析取(合取)范式法；(4) 直接證法：掌握P規(guī)則和T規(guī)則，及常用重言蘊(yùn)含

7、式、等值式。 (5) 間接證法(反證法)：掌握CP規(guī)則。本章重點(diǎn)：命題與聯(lián)結(jié)詞，公式與解釋，真值表，(主)析取(合取)范式，重言式的判定。第2章謂詞邏輯 復(fù)習(xí)要求1. 理解謂詞、量詞、個(gè)體詞、個(gè)體域、原子公式、謂詞公式和變元等概念。會將命題符號化。在謂詞邏輯，使用量詞應(yīng)注意以下幾點(diǎn)：(1) 在不同個(gè)體域中，命題符號化的形式可能不同，命題的真值也可能會改變。(2) 在考慮命題符號化時(shí)，如果對個(gè)體域未作說明，一律使用全個(gè)體域。 (3) 多個(gè)量詞出現(xiàn)時(shí)，不能隨意顛倒它們的順序，否則可能會改變命題的涵義。 2. 掌握在有限個(gè)體域下消去公式的量詞和求公式在給定解釋下真值的方法。 謂詞公式只是一個(gè)符號串，

8、沒有什么意義，但我們給這個(gè)符號串一個(gè)解釋，使它具有真值，就變成一個(gè)命題。所謂解釋就是使公式中的每一個(gè)變項(xiàng)都有個(gè)體域中的元素相對應(yīng)。解釋有四部分組成：(1) 非空個(gè)體域D；(2) D中有一部分特定元素，用來解釋個(gè)體常項(xiàng)；(3) D上一些特定函數(shù)，用來解釋出現(xiàn)的函數(shù)變項(xiàng)； (4) D上一些特定謂詞，用來解釋謂詞變項(xiàng)。 3. 掌握謂詞演算的等值式和重言蘊(yùn)含式，并進(jìn)行謂詞公式的等值演算。 謂詞演算的等值式和重言蘊(yùn)含式的六種情況：(1) 命題公式的推廣；(2) 量詞否定式的等值式；(3) 量詞轄域擴(kuò)張和收縮的等值式；(4) 量詞與聯(lián)結(jié)詞Ú，Ù，®的等值式；(5) 量詞與聯(lián)結(jié)

9、詞的重言蘊(yùn)含式；(6) 兩個(gè)量詞公式間的等值式與重言蘊(yùn)含式。4. 了解前束范式的概念，掌握求公式的前束范式的方法。每個(gè)謂詞公式F都可以變換成與它等值的前束范式。其步驟如下： 消去聯(lián)結(jié)詞®，«，Ú； 將聯(lián)結(jié)詞Ø向內(nèi)深入，使之只作用于原子謂詞公式； 利用換名或代入規(guī)則使所有約束變元的符號均不同，并且自由變元與約束變元的符號也不同； 利用量詞轄域的擴(kuò)張和收縮律，擴(kuò)大量詞的轄域至整個(gè)公式； 利用分配律將公式化為前束范式。 5. 了解謂詞邏輯推理的規(guī)則：全量詞消去規(guī)則(US規(guī)則)；全量詞附加規(guī)則(UG規(guī)則)；存在量詞消去規(guī)則(ES規(guī)則)；存在量詞附加規(guī)則(EG規(guī)則

10、)，會給出推理證明。 謂詞演算的推理是命題演算推理的推廣和擴(kuò)充，命題演算中的一些規(guī)則，如基本等值公式，重言蘊(yùn)含式以及P，T，CP規(guī)則在謂詞演算中仍然使用。但是在謂詞演算推理中，某些前提和結(jié)論可能受到量詞的限制，為了使用這些推理，必須在推理過程中，有消去和附加量詞的規(guī)則，即US規(guī)則(全稱量詞消去規(guī)則)，UG規(guī)則(全稱量詞附加規(guī)則)，ES規(guī)則(存在量詞消去規(guī)則)，EG規(guī)則(存在量詞附加規(guī)則)等，以便使謂詞演算公式的推理過程可類似于命題演算的推理進(jìn)行。本章重點(diǎn)：謂詞與量詞，公式與解釋，前束范式，謂詞邏輯推理證明。第3章 集合及其運(yùn)算 復(fù)習(xí)要求1. 理解集合、元素、全集、空集等概念。2. 理解集合的包

11、含、子集、相等和冪集等概念，熟練掌握集合的表示方法和集合的并、交、補(bǔ)、差和對稱差等運(yùn)算，會用文氏圖表示集合的各種運(yùn)算。 3. 掌握用集合運(yùn)算基本規(guī)律證明集合恒等式的方法。 集合的運(yùn)算主要有集合的運(yùn)算、集合運(yùn)算式的化簡和集合恒等式的推理證明等三個(gè)方面的問題。集合恒等式證明的目的有兩個(gè)，其一是通過證明的練習(xí)，加深對集合性質(zhì)和第1章命題公式基本等值式的理解和掌握；其二是為第8章學(xué)習(xí)布爾代數(shù)中部分性質(zhì)的應(yīng)用打下良好的基礎(chǔ)。集合恒等式的證明方法通常有兩種：其一，要證明AB，就需要證明AÍ B；在證明A Ê B 。其二，通過運(yùn)算律進(jìn)行等式推導(dǎo)。 4. 了解有序?qū)偷芽▋悍e的概念，掌握笛

12、卡兒積的運(yùn)算。 本章重點(diǎn)：集合概念，集合的運(yùn)算，集合恒等式的證明。笛卡兒積。第4章 關(guān)系與函數(shù) 復(fù)習(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ì)，掌握其判別方法(定義、矩陣或圖)。 關(guān)系的性質(zhì)及判別方法 自反性：；矩陣的主對角線元素全為1；關(guān)系圖的每個(gè)結(jié)點(diǎn)都有自回路。 反自反性：；矩陣的主對角線元素全為0；關(guān)系圖的每個(gè)結(jié)點(diǎn)都沒有自回路。 對稱性：若，則；矩陣是對稱矩陣，即；有向關(guān)系圖中有向弧成對出現(xiàn)。 反對稱性：若，則x = y或若，則；矩陣不出現(xiàn)對稱元素；關(guān)系圖

13、中沒有成對弧出現(xiàn)。 傳遞性：若，則；在關(guān)系圖中，有從A到B的弧，有從B到c的弧，則有從A到c的弧。 4. 理解等價(jià)關(guān)系和偏序關(guān)系概念，掌握等價(jià)類的求法和作偏序關(guān)系哈斯圖的方法。知道極大(小)元，最大(小)元的概念，會求極大(小)元、最大(小)元、最小上界和最大下界。 等價(jià)關(guān)系和偏序關(guān)系是兩種最重要的關(guān)系。它們具有不同的性質(zhì)。等價(jià)關(guān)系圖的特點(diǎn)是：每一個(gè)結(jié)點(diǎn)都有一個(gè)自回路，兩個(gè)結(jié)點(diǎn)間如有有向弧線，則一定是雙向弧線，如果從A到B，從B到c各有一條有向弧線，則從A到c一定有有向弧線。若R是等價(jià)關(guān)系，與R中的某個(gè)元素等價(jià)的所有元素作為整體，就是一個(gè)等價(jià)類。就可以把R分成若干個(gè)等價(jià)類(子集)。偏序關(guān)系是第

14、8章偏序格的基礎(chǔ)，理解和掌握偏序關(guān)系和偏序集概念的關(guān)鍵是哈斯圖。哈斯圖的畫法掌握了，對于確定任一子集的最大(小)元，極大(小)元也就容易了。這里要注意，最大(小)元與極大(小)元只能在子集內(nèi)確定。而上界與下界可在子集之外的全集中確定，最小上界是所有上界中最小者，最小上界再小也不會小于子集中的任一元素；可以與某一元素相等，最大下界也是同樣。 5. 理解函數(shù)概念：函數(shù)(映射)，函數(shù)相等，復(fù)合函數(shù)和反函數(shù)。 函數(shù)是一種特殊的關(guān)系，集合A×B的任何子集都是關(guān)系，但不一定是函數(shù)。函數(shù)要求對于定義域A中每一個(gè)元素A，B中有且僅有一個(gè)元素與A對應(yīng)，而關(guān)系沒有這個(gè)限制。二函數(shù)相等是指：定義域相同，對

15、應(yīng)關(guān)系相同，而且定義域內(nèi)每個(gè)對應(yīng)值都相同。 6. 理解單射、滿射和雙射等概念，掌握其判別方法。 函數(shù)的類型（單射、滿射、雙射）：判定的方法除定義外，還可借助于關(guān)系圖。而實(shí)數(shù)集的子集上的函數(shù)，也可以用直角坐標(biāo)表示，尤其是初等函數(shù)。本章重點(diǎn)：關(guān)系概念與其性質(zhì)，等價(jià)關(guān)系和偏序關(guān)系，函數(shù)。第5章 圖的基本概念 復(fù)習(xí)要求1. 理解圖的概念：結(jié)點(diǎn)、邊、有向圖，無向圖、圖的同構(gòu)、簡單圖、完全圖、結(jié)點(diǎn)的度數(shù)、子圖、邊的重?cái)?shù)和平行邊等理解握手定理：。2. 了解通路與回路概念：通路(簡單通路、初級通路和復(fù)雜通路)，回路(簡單回路、初級回路和復(fù)雜回路) 會求通路和回路的長度。3. 了解無向圖的連通性，會求無向圖的連通分支。了解點(diǎn)割集、割點(diǎn)、邊割集、割邊、點(diǎn)連通度、邊連通度等概念。4. 了解有向圖的強(qiáng)連通強(qiáng)性；會判別其類型5. 了解(