淮陰工學(xué)院離散數(shù)學(xué)

《離散數(shù)學(xué)》期末復(fù)習(xí)提要一、命題邏輯[復(fù)習(xí)知識(shí)點(diǎn)]命題與聯(lián)結(jié)詞（否定、析取、合取、條件、等值），復(fù)合命題命題公式與賦值（成真、成假），真值表，公式類(lèi)型（重言、矛盾、可滿(mǎn)足），公式的基本等值式命題公式之間的關(guān)系：蘊(yùn)含、等價(jià)析取范式、合取范式，極?。ù螅╉?xiàng)，主析取范式、主合取范式公式類(lèi)型的判別方法（真值表法、等值演算法、主析取/合取范式法）命題邏輯的推理理論：真值表法、直接證明法、間接證明法本章重點(diǎn)內(nèi)容：命題與聯(lián)結(jié)詞、公式與解釋、（主）析取范式與（主）合取范式、公式類(lèi)型的判定、命題邏輯的推理[復(fù)習(xí)要求]理解命題的概念；了解命題聯(lián)結(jié)詞的概念；理解用聯(lián)結(jié)詞產(chǎn)生復(fù)合命題的方法。理解公式與賦值的概念；掌握求給定公式真值表的方法，用基本等值式化簡(jiǎn)其它公式，公式在解釋下的真值。了解析?。ê先。┓妒降母拍?；理解極大（?。╉?xiàng)的概念和主析?。ê先。┓妒降母拍?；掌握用基本等值式或真值表將公式化為主析?。ê先。┓妒降姆椒?。掌握利用真值表、等值演算法和主析取/合取范式的唯一性判別公式類(lèi)型和公式等價(jià)方法。掌握命題邏輯的推理理論。P規(guī)則、T規(guī)則、附加前提證明法、CP規(guī)則[疑難解析]1、公式類(lèi)型的判定判定公式的類(lèi)型，包括判定公式是重言的、矛盾的或是可滿(mǎn)足的。具體方法有兩種，一是真值表法，二是等值演算法。2、范式求范式，包括求析取范式、合取范式、主析取范式和主合取范式。關(guān)鍵有兩點(diǎn)：一是準(zhǔn)確理解掌握定義；另一是巧妙使用基本等值式中的分配律、同一律和互補(bǔ)律（排中律、矛盾律），結(jié)果的前一步適當(dāng)使用冪等律，使相同的短語(yǔ)（或子句）只保留一個(gè)。3、邏輯推理掌握邏輯推理時(shí)，要理解并掌握12個(gè)（除第10，11）推理規(guī)則和3種證明法（直接證明法、附加前提證明法和歸謬法）。二、謂詞邏輯（一階邏輯）[復(fù)習(xí)知識(shí)點(diǎn)]謂詞、量詞、個(gè)體詞（一階邏輯3要素）、個(gè)體域、變?cè)s束出現(xiàn)與自由出現(xiàn)）謂詞公式與解釋?zhuān)^詞公式的類(lèi)型（永真、永假、可滿(mǎn)足）謂詞公式的等值式（代換實(shí)例、消去量詞、量詞否定和量詞轄域收與擴(kuò)）和置換規(guī)則（置換規(guī)則、換名規(guī)則和代替規(guī)則）謂詞推理理論本章重點(diǎn)內(nèi)容：謂詞與量詞、公式與解釋、謂詞推理理論（US/UG、ES/EG規(guī)則）[復(fù)習(xí)要求]理解謂詞、量詞、個(gè)體詞、個(gè)體域、變?cè)母拍?；理解用謂詞、量詞、邏輯聯(lián)結(jié)詞描述一個(gè)簡(jiǎn)單命題；了解命題符號(hào)化。理解公式與解釋的概念；掌握在有限個(gè)體域下消去公式量詞，求公式在給定解釋下真值的方法；了解謂詞公式的類(lèi)型。[疑難解析]1、謂詞與量詞理解謂詞與量詞引入的意義，概念的含義及在謂詞與量詞作用下變量的自由性、約束性與改名規(guī)則（即換名規(guī)則和代替規(guī)則）。2、公式與解釋能將一階邏輯公式表達(dá)式中的量詞消除，寫(xiě)成與之等價(jià)的公式，然后將解釋中的數(shù)值代入公式，求出真值。三、集合[復(fù)習(xí)知識(shí)點(diǎn)]集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、冪集集合的交、并、差、補(bǔ)以及對(duì)稱(chēng)差等運(yùn)算及其運(yùn)算律（交換律、結(jié)合律、分配律、吸收律、德摩根律等），文氏（Venn）圖本章重點(diǎn)內(nèi)容：集合的概念、集合的運(yùn)算性質(zhì)、集合恒等式的證明。[復(fù)習(xí)要求]理解集合、元素、子集、空集、全集、集合的包含、相等、冪集等基本概念。掌握集合的表示法和集合的交、并、差、補(bǔ)、對(duì)稱(chēng)差等基本運(yùn)算。掌握集合運(yùn)算基本規(guī)律，證明集合等式的方法。[疑難解析]1、集合的概念重點(diǎn)對(duì)冪集加以掌握，一是掌握冪集的構(gòu)成，一是掌握冪集元數(shù)為2n。2、集合恒等式的證明對(duì)集合恒等式證明的練習(xí)，加深對(duì)集合性質(zhì)的理解與掌握。四、二元關(guān)系[復(fù)習(xí)知識(shí)點(diǎn)]序偶、迪卡爾積，迪卡爾積的運(yùn)算。關(guān)系表達(dá)式、關(guān)系矩陣與關(guān)系圖復(fù)合關(guān)系（右復(fù)合）與逆關(guān)系關(guān)系的性質(zhì)（自反性、反自反性、對(duì)稱(chēng)性、反對(duì)稱(chēng)性、傳遞性）關(guān)系的閉包（自反閉包、對(duì)稱(chēng)閉包、傳遞閉包）等價(jià)關(guān)系與等價(jià)類(lèi)偏序關(guān)系與哈斯圖、極大/小元、最大/小元函數(shù)及其性質(zhì)（單射、滿(mǎn)射、雙射）復(fù)合函數(shù)與反函數(shù)本章重點(diǎn)內(nèi)容：二元關(guān)系的概念、關(guān)系的性質(zhì)、關(guān)系的閉包、等價(jià)關(guān)系、偏序關(guān)系和映射的概念[復(fù)習(xí)要求]了解序偶與迪卡爾積的概念，掌握迪卡爾積的運(yùn)算。理解關(guān)系的概念：二元關(guān)系、空關(guān)系、全域關(guān)系、恒等關(guān)系；掌握關(guān)系的集合表示、關(guān)系矩陣和關(guān)系圖、關(guān)系的運(yùn)算。掌握求復(fù)合關(guān)系與逆關(guān)系的方法。理解關(guān)系的性質(zhì)（自反性、反自反性、對(duì)稱(chēng)性、反對(duì)稱(chēng)性、傳遞性），掌握其判別方法（定義、圖）。掌握求關(guān)系的閉包（自反閉包、對(duì)稱(chēng)閉包、傳遞閉包）的方法。理解等價(jià)關(guān)系和偏序關(guān)系的概念，掌握等價(jià)類(lèi)的求法和偏序關(guān)系做哈斯圖的方法，極大/小元、最大/小元的求法。理解函數(shù)概念：函數(shù)、函數(shù)相等、A到B的函數(shù)、復(fù)合函數(shù)和反函數(shù)。理解單射、滿(mǎn)射、雙射等概念，掌握其判別方法。[疑難解析]1、關(guān)系的概念熟練掌握二元關(guān)系的概念及關(guān)系矩陣、關(guān)系圖表示。2、關(guān)系的性質(zhì)及其判定關(guān)系的性質(zhì)既是對(duì)關(guān)系概念的加深理解與掌握，又是關(guān)系的閉包、等價(jià)關(guān)系、偏序關(guān)系的基礎(chǔ)。對(duì)于五種性質(zhì)的判定，可以依據(jù)教材上總結(jié)的規(guī)律。這其中對(duì)傳遞性的判定，難度稍大一點(diǎn)，這里要提及兩點(diǎn)：一是不破壞傳遞性定義，可認(rèn)為具有傳遞性。如空關(guān)系具有傳遞性，同時(shí)空關(guān)系具有對(duì)稱(chēng)性與反對(duì)稱(chēng)性，但是不具有自反性。3、關(guān)系的閉包在理解掌握關(guān)系閉包概念的基礎(chǔ)上，主要掌握閉包的求法。關(guān)鍵是熟記定理7.10和7.114、偏序關(guān)系及偏序集中特殊元素的確定理解與掌握偏序關(guān)系與偏序集概念的關(guān)鍵是哈斯圖。哈斯圖畫(huà)法掌握了，對(duì)于確定任一子集的最大（?。┰?，極大（?。┰簿腿菀琢?。這里要注意，最大（?。┰c極大（?。┰荒茉谧蛹瘍?nèi)確定。5、映射的概念與映射種類(lèi)的判定映射的種類(lèi)主要指單射、滿(mǎn)射、雙射與非單非滿(mǎn)射。判定的方法除定義外，可借助于關(guān)系圖，而實(shí)數(shù)集的子集上的映射也可以利用直角坐標(biāo)系表示進(jìn)行，尤其是對(duì)各種初等函數(shù)。五、圖論[復(fù)習(xí)知識(shí)點(diǎn)]圖的基本概念：無(wú)向圖與有向圖、頂點(diǎn)與邊的關(guān)聯(lián)關(guān)系、頂點(diǎn)（邊）與頂點(diǎn)（邊）之間鄰接關(guān)系、簡(jiǎn)單圖與多重圖、頂點(diǎn)度數(shù)（度）與握手定理、圖的同構(gòu)、完全圖、子（補(bǔ)）圖；路與回路、簡(jiǎn)單（回）路；連通圖與非連通圖、連通分支、強(qiáng)連通圖、單向連通圖與弱連通圖、點(diǎn)（邊）連通度；圖的矩陣表示：鄰接矩陣、關(guān)聯(lián)矩陣、可達(dá)矩陣；歐拉（回）路、（半）歐拉圖；哈密爾頓（回）路、（半）哈密爾頓圖；無(wú)向樹(shù)、生成樹(shù)、帶權(quán)樹(shù)、最小生成樹(shù)，基本回路、最小生成樹(shù)避圈法（Kruskal算法）；有向樹(shù)、樹(shù)根、有序樹(shù)、二叉樹(shù)、前綴碼、最佳前綴碼、哈夫曼（Huffman）算法、帶權(quán)圖的最優(yōu)二分樹(shù)、二叉樹(shù)的周游（即遍歷）；本章重點(diǎn)內(nèi)容：握手定理、特殊圖（歐拉圖與哈密頓圖、無(wú)（有）向樹(shù)）、最小生成樹(shù)、哈夫曼樹(shù)、哈夫曼編碼[復(fù)習(xí)要求]理解圖的有關(guān)概念：圖、完全圖、子圖、母圖、生成子圖、圖的同構(gòu)等。深刻理解握手定理及其推論的內(nèi)容，并能熟練地應(yīng)用它們。理解圖的矩陣表示（關(guān)聯(lián)矩陣、相鄰矩陣）和性質(zhì)以及熟練掌握用有向圖的鄰接矩陣及各次冪求圖中通路與回路數(shù)的方法。深刻理解歐拉圖、哈密頓圖的定義及判別定理，對(duì)于給定的圖，應(yīng)用各定理準(zhǔn)確判斷；會(huì)用破壞哈密頓圖應(yīng)滿(mǎn)足的某些必要條件的方法判斷某些圖不是哈密頓圖；會(huì)用滿(mǎn)足哈密頓的充分條件的方法判斷某些圖是哈密頓圖。深刻理解無(wú)向樹(shù)的定義，熟練掌握無(wú)向樹(shù)的主要性質(zhì)，并能靈活應(yīng)用它們。深刻理解生成樹(shù)的有關(guān)概念與性質(zhì)；理解基本回路、基本回路系統(tǒng)、用Kruskal算法求權(quán)圖中最小生成樹(shù)的方法。深刻理解有向樹(shù)、根樹(shù)、二叉樹(shù)和前綴碼的有關(guān)概念；掌握用霍夫曼（Huffman）算法求帶權(quán)圖的最優(yōu)二分樹(shù)，掌握求最佳前綴碼方法，二叉樹(shù)的中序和前序行遍法?？荚囌f(shuō)明考核方式1、期末筆試為120分鐘的閉卷考試，占總評(píng)成績(jī)的70％。2、平時(shí)成績(jī)根據(jù)作業(yè)完成情況、半期考成績(jī)、出勤情況和課堂表現(xiàn)確定，占總評(píng)成績(jī)30％。各章比例數(shù)理邏輯30分集合30分圖論40分考題類(lèi)型單項(xiàng)選擇題20分填空題20分證明題、計(jì)算題、分析題（包括綜合分析）60分大題詳細(xì)分析命題邏輯自然推理證明，綜合分析題或證明題；構(gòu)造命題的真值表，驗(yàn)證命題之間的關(guān)系（蘊(yùn)含、等價(jià)）。計(jì)算分析題；用等值演算法求解等價(jià)公式、主析取范式或主合取范式，計(jì)算分析題；命題邏輯推