《離散數(shù)學(xué)》期末復(fù)習(xí)大綱(完整版) (含例題和考試說(shuō)明)

《離散數(shù)學(xué)》期末復(fù)習(xí)大綱(完整版)(含例題和考試說(shuō)明)2、命題公式與賦值(成真、成假)，真值表，公式類(lèi)型(重言、矛盾、可滿足)，公式的基本等值式3、范式：析取范式、合取范式，極大(小)項(xiàng)，主析取范式、主合取范式4、公式類(lèi)型的判別方法(真值表法、等值演算法、主析取/合取范式法)本章重點(diǎn)內(nèi)容：命題與聯(lián)結(jié)詞、公式與解釋、(主)析取范式與(主)合取范式、公式類(lèi)型的判定、理給定公式真值表的方法，用基本等值式化簡(jiǎn)其它公式，公式在解釋下3、了解析取(合取)范式的概念；理解極大(小)項(xiàng)的概念和主析取(合取)范式的概念；掌握用基本等值式或真值表將公式化為主析取(合取)范式的方法。判別公式類(lèi)型和公式等價(jià)方法。包括判定公式是重言的、矛盾的或是可滿足的。具體方法有兩種，一是真值表法，二另一是巧妙使用基本等值式中的分配律、同一律和互補(bǔ)律(排中律、矛盾律)，結(jié)果的前一步適當(dāng)使用冪等律，使相同的短語(yǔ)(或子句)只保留一個(gè)。掌握邏輯推理時(shí)，要理解并掌握12個(gè)(除第10，11)推理規(guī)則和3種證明法(直接證明法、附加前提(1)P((PQ)^(QP))；(2)P(P(QQR)))PQP(PQ)^(PP)=PQ(1)(P^P)一Q(2)(PQ)^Q(3)((PQ)^(QR))(PR)(1)真值表PQPP^P(P^P)一Q010100001000因此公式(1)為可滿足。(2)真值表PQPQ(PQ)(PQ)^Q00010001000因此公式(2)為恒假。(3)真值表PQRPQQRPR((PQ)^(QR))(PR)111100111111011011111101010111因此公式(3)為恒真。3．┐Q^(P→Q)蘊(yùn)涵┐P①若Q為真，則┐Qù(P→Q)為假Q(mào)PQQPQ假((PQ)^(QR))(PR)(1、證明：((PQ)^(QR))(PR)=(P^Q)(Q^R)PR=((P^Q)P)((Q^R)R)R=1PR=1RPQRP(Q^R))(1)PQ(2)PQ(3)QR(4)QR(5)PR(6)RS(7)PS6．用形式演繹法證明：(AB)(C^D),(DF)E蘊(yùn)涵AE證明：(改(A^B)為(AB),(D^F)為(DF))(1)A規(guī)則D(2)A∨B規(guī)則Q()1(3)(AB)(C^D)規(guī)則P(4)C^D規(guī)則Q(2)()3(5)D規(guī)則Q()4(6)DF規(guī)則Q()5(7)(DF)E規(guī)則P (8)E規(guī)則Q(6)()7 (9)AE規(guī)則Q(1)(8))(1)┐Q∨R(2)┐R(3)┐Q(4)┐(P∧┐Q)(5)┐P∨Q(6)┐P)(1)若甲、乙均未作案，則丙、丁也均未作案；(2)若丙、丁均未作案，則甲、乙也均未作案；(3)若甲與乙同時(shí)作案，則丙與丁有一人且只有一人作案；(4)若乙與丙同時(shí)作案，則甲與丁同時(shí)作案或同未作案。結(jié)論是錯(cuò)誤的)1、謂詞、量詞、個(gè)體詞(一階邏輯3要素)、個(gè)體域、變?cè)?約束出現(xiàn)與自由出現(xiàn))2、謂詞公式與解釋?zhuān)^詞公式的類(lèi)型(永真、永假、可滿足)3、謂詞公式的等值式(代換實(shí)例、消去量詞、量詞否定和量詞轄域收與擴(kuò))和置換規(guī)則(置換規(guī)則、換詞與量詞、公式與解釋題；念；掌握在有限個(gè)體域下消去公式量詞，求公式在給定解釋下真值的方法；了解意義，概念的含義及在謂詞與量詞作用下變量的自由性、約束性與改名規(guī)則(即換名規(guī)則和代替規(guī)則)。消除，寫(xiě)成與之等價(jià)的公式，然后將解釋中的數(shù)值代入公式，求出包含、相等、冪集及其運(yùn)算律(交換律、結(jié)合律、分配律、吸收律、德摩根律等)，文氏(Venn)圖3、復(fù)合關(guān)系(右復(fù)合)與逆關(guān)系3、關(guān)系的性質(zhì)(自反性、反自反性、對(duì)稱(chēng)性、反對(duì)稱(chēng)性、傳遞性)4、關(guān)系的閉包(自反閉包、對(duì)稱(chēng)閉包、傳遞閉包)7、函數(shù)及其性質(zhì)(單射、滿射、雙射)元關(guān)系的概念、關(guān)系的性質(zhì)、關(guān)系的閉包、等價(jià)關(guān)系、偏序關(guān)系和映射的概念關(guān)系、恒等關(guān)系；掌握關(guān)系的集合表示、關(guān)系矩陣和關(guān)系4、理解關(guān)系的性質(zhì)(自反性、反自反性、對(duì)稱(chēng)性、反對(duì)稱(chēng)性、傳遞性)，掌握其判別方法(定義、圖)。4、掌握求關(guān)系的閉包(自反閉包、對(duì)稱(chēng)閉包、傳遞閉包)的方法。等價(jià)關(guān)系和偏序關(guān)系的概念，掌握等價(jià)類(lèi)的求法和偏序關(guān)系做哈斯圖的方法，極大/小元、最大/小概念的加深理解與掌握，又是關(guān)系的閉包、等價(jià)關(guān)系、偏序關(guān)系的基礎(chǔ)。對(duì)于五，的確定理解與掌握偏序關(guān)系與偏序集概念的關(guān)鍵是哈斯圖。哈斯圖畫(huà)法掌握了，對(duì)于確定任一子集的最大(小)元，極大(小)元也就容易了。這里要注意，最大(小)元與極大(小)元只能在子集內(nèi)確定。非單非滿射。判定的方法除定義外，可借助于關(guān)系圖，而實(shí)數(shù)集1、圖的基本概念：無(wú)向圖與有向圖、頂點(diǎn)與邊的關(guān)聯(lián)關(guān)系、頂點(diǎn)(邊)與頂點(diǎn)(邊)之間鄰接關(guān)系、簡(jiǎn)單圖與多重圖、頂點(diǎn)度數(shù)(度)與握手定理、圖的同構(gòu)、完全圖、子(補(bǔ))圖；2、通路與回路、簡(jiǎn)單通(回)路與初級(jí)通(回)路；連通圖與非連通圖、連通分支、強(qiáng)連通圖、單向連通圖與弱連通圖、二部圖；點(diǎn)割集、邊割集、點(diǎn)(邊)連通度；4、歐拉通(回)路、(半)歐拉圖；哈密爾頓通(回)路、(半)哈密爾頓圖；法(Kruskal算法)；6、有向樹(shù)、樹(shù)根、有序樹(shù)、二叉樹(shù)、前綴碼、最佳前綴碼、霍夫曼(Huffman)算法、帶權(quán)圖的最優(yōu)二本章重點(diǎn)內(nèi)容：握手定理、點(diǎn)(邊)割集、特殊圖(歐拉圖與哈密頓圖、無(wú)(有)向樹(shù))3、理解圖的矩陣表示(關(guān)聯(lián)矩陣、相鄰矩陣)和性質(zhì)以及熟練掌握用有向圖的鄰接矩陣及各次冪求圖中