《2022年完整word版,《離散數(shù)學(xué)》方世昌的期末復(fù)習(xí)知識(shí)點(diǎn)總結(jié)含例題》由會(huì)員分享，可在線閱讀，更多相關(guān)《2022年完整word版,《離散數(shù)學(xué)》方世昌的期末復(fù)習(xí)知識(shí)點(diǎn)總結(jié)含例題（25頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、1 離散數(shù)學(xué)（第三版）方世昌的期末復(fù)習(xí)知識(shí)點(diǎn)總結(jié)含例題一、各章復(fù)習(xí)要求與重點(diǎn)第一章集合復(fù)習(xí)知識(shí)點(diǎn) 1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、冪集2、集合的交、并、差、補(bǔ)等運(yùn)算及其運(yùn)算律（交換律、結(jié)合律、分配律、吸收律、De Morgan律等），文氏（Venn）圖3、序偶與迪卡爾積本章重點(diǎn)內(nèi)容：集合的概念、集合的運(yùn)算性質(zhì)、集合恒等式的證明復(fù)習(xí)要求 1、理解集合、元素、子集、空集、全集、集合的包含、相等、冪集等基本概念。2、掌握集合的表示法和集合的交、并、差、補(bǔ)等基本運(yùn)算。3、掌握集合運(yùn)算基本規(guī)律，證明集合等式的方法。4、了解序偶與迪卡爾積的概念，掌握迪卡爾積的運(yùn)算。疑難

2、解析 1、集合的概念因?yàn)榧系母拍顚W(xué)生在中學(xué)階段已經(jīng)學(xué)過(guò)，這里只多了一個(gè)冪集概念，重點(diǎn)對(duì)冪集加以掌握，一是掌握冪集的構(gòu)成，一是掌握冪集元數(shù)為2n。2、集合恒等式的證明通過(guò)對(duì)集合恒等式證明的練習(xí)，既可以加深對(duì)集合性質(zhì)的理解與掌握；又可以為第三章命題邏輯中公式的基本等價(jià)式的應(yīng)用打下良好的基礎(chǔ)。實(shí)際上，本章做題是一種基本功訓(xùn)練，尤其要求學(xué)生重視吸收律和重要等價(jià)式在BABA證明中的特殊作用。例題分析 例 1 設(shè) A，B 是兩個(gè)集合，A=1，2，3，B=1，2，則)()(BA。解3,2,1,3,2,3,1,2,1,3,2,1,)(A2,1,2,1,)(B精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 1 頁(yè)，共 25

3、 頁(yè)2 于是3,2,1,3,2,3,1,3)()(BA例 2 設(shè),babaA，試求：(1)baA,；(2)A；(3)A；(4)Aba,；(5)A；(6)A。解(1),babaA(2)AA(3)babaA,(4)Aba,(5)A(6)A例 3 試證明BABABABA證明BABABABABBBAABAABBAABABABA第二章二元關(guān)系復(fù)習(xí)知識(shí)點(diǎn) 1、關(guān)系、關(guān)系矩陣與關(guān)系圖2、復(fù)合關(guān)系與逆關(guān)系3、關(guān)系的性質(zhì)（自反性、對(duì)稱性、反對(duì)稱性、傳遞性）4、關(guān)系的閉包（自反閉包、對(duì)稱閉包、傳遞閉包）5、等價(jià)關(guān)系與等價(jià)類6、偏序關(guān)系與哈斯圖（Hasse）、極大/小元、最大/小元、上/下界、最小上界、最大下界7、

4、函數(shù)及其性質(zhì)（單射、滿射、雙射）8、復(fù)合函數(shù)與反函數(shù)本章重點(diǎn)內(nèi)容：二元關(guān)系的概念、關(guān)系的性質(zhì)、關(guān)系的閉包、等價(jià)關(guān)系、半序關(guān)系、映射的概念復(fù)習(xí)要求 1、理解關(guān)系的概念：二元關(guān)系、空關(guān)系、全關(guān)系、恒等關(guān)系；掌握關(guān)系的集合表示、關(guān)系矩陣和關(guān)系圖、關(guān)系的運(yùn)算。精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 2 頁(yè)，共 25 頁(yè)3 2、掌握求復(fù)合關(guān)系與逆關(guān)系的方法。3、理解關(guān)系的性質(zhì)（自反性、對(duì)稱性、反對(duì)稱性、傳遞性），掌握其判別方法（定義、矩陣、圖）。4、掌握求關(guān)系的閉包（自反閉包、對(duì)稱閉包、傳遞閉包）的方法。5、理解等價(jià)關(guān)系和偏序關(guān)系的概念，掌握等價(jià)類的求法和偏序關(guān)系做哈斯圖的方法，極大/小元、最大/小元、上/下

5、界、最小上界、最大下界的求法。6、理解函數(shù)概念：函數(shù)、函數(shù)相等、復(fù)合函數(shù)和反函數(shù)。7、理解單射、滿射、雙射等概念，掌握其判別方法。本章重點(diǎn)習(xí)題 P25，1；P3233，4，8，10；P43，2，3，5；P5152，5，6；P59，1，2；P64，3；P7475，2，4，6，7；P81，5，7；P86，1，2。疑難解析 1、關(guān)系的概念關(guān)系的概念是第二章全章的基礎(chǔ)，又是第一章集合概念的應(yīng)用。因此，學(xué)生應(yīng)該真正理解并熟練掌握二元關(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ù)教材中

6、P49 上總結(jié)的規(guī)律。這其中對(duì)傳遞性的判定，難度稍大一點(diǎn)，這里要提及兩點(diǎn)：一是不破壞傳遞性定義，可認(rèn)為具有傳遞性。如空關(guān)系具有傳遞性，同時(shí)空關(guān)系具有對(duì)稱性與反對(duì)稱性，但是不具有自反性。另一點(diǎn)是介紹一種判定傳遞性的“跟蹤法”，即若RaaRaaRaaii,13221，則Raai,1。如若RabRba,，則有Raa,，且Rbb,。、關(guān)系的閉包在理解掌握關(guān)系閉包概念的基礎(chǔ)上，主要掌握閉包的求法。關(guān)鍵是熟記三個(gè)定理的結(jié)論：定理2，AIRRr；定理 3，1RRRs；定理 4，推論niiRRt1。、半序關(guān)系及半序集中特殊元素的確定理解與掌握半序關(guān)系與半序集概念的關(guān)鍵是哈斯圖。哈斯圖畫(huà)法掌握了，對(duì)于確定任一子

7、集的最大（?。┰瑯O大（?。┰簿腿菀琢恕＿@里要注意，最大（?。┰c極大（?。┚x學(xué)習(xí)資料 -名師歸納總結(jié)-第 3 頁(yè)，共 25 頁(yè)4 元只能在子集內(nèi)確定，而上界與下界可在子集之外的全集中確定，最小上界為所有上界中最小者，最小上界再小也不小于子集中的任一元素，可以與某一元素相等，最大下界也同樣。、映射的概念與映射種類的判定映射的種類主要指單射、滿射、雙射與非單非滿射。判定的方法除定義外，可借助于關(guān)系圖，而實(shí)數(shù)集的子集上的映射也可以利用直角坐標(biāo)系表示進(jìn)行，尤其是對(duì)各種初等函數(shù)。例題分析 例 1 設(shè)集合dcbaA,，判定下列關(guān)系，哪些是自反的，對(duì)稱的，反對(duì)稱的和傳遞的：dbcaRccbbaaRdc

8、RadcbaaRabaaR,54321解：均不是自反的；R4是對(duì)稱的；R1,R2,R3,R4,R5是反對(duì)稱的；R1,R2,R3,R4,R5是傳遞的。例 2 設(shè)集合5,4,3,2,1A，A 上的二元關(guān)系R 為5,5,4,5,3,5,4,4,4,3,3,3,2,2,1,1R（）寫(xiě)出R 的關(guān)系矩陣，畫(huà)出R 的關(guān)系圖；（）證明R 是 A 上的半序關(guān)系，畫(huà)出其哈斯圖；（）若AB，且5,4,3,2B，求 B 的最大元，最小元，極大元，極小元，最小上界和最大下界。解（1）R 的關(guān)系矩陣為1110001000011000001000001RMR 的關(guān)系圖略（2）因?yàn)?R 是自反的，反對(duì)稱的和傳遞的，所以 R

9、是 A 上的半序關(guān)系。(A,R)為半序集，(A,R)的哈斯圖如下精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 4 頁(yè)，共 25 頁(yè)5(3)當(dāng)5,4,3,2B，B 的極大元為2，4；極小元為2，5；B 無(wú)最大元與最小元；B也無(wú)上界與下界，更無(wú)最小上界與最大下界。第三章命題邏輯復(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é)詞、公式與解釋、析取范式

10、與合取范式、公式恒真性的判定、形式演繹復(fù)習(xí)要求 、理解命題的概念；了解命題聯(lián)結(jié)詞的概念；理解用聯(lián)結(jié)詞產(chǎn)生復(fù)合命題的方法。、理解公式與解釋的概念；掌握求給定公式真值表的方法，用基本等價(jià)式化簡(jiǎn)其他公式，公式在解釋下的真值。、了解析?。ê先。┓妒降母拍睿焕斫鈽O大（?。╉?xiàng)的概念和主析?。ê先。┓妒降母拍睿徽莆沼没镜葍r(jià)式或真值表將公式化為主析?。ê先。┓妒降姆椒?。、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判別公式類型和公式等價(jià)的方法。、理解公式蘊(yùn)涵與邏輯結(jié)果的概念，掌握基本蘊(yùn)涵式。6、掌握形式演繹的證明方法。本章重點(diǎn)習(xí)題 。4。1。3。2。5 精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 5 頁(yè)，共

11、25 頁(yè)6 P93，1；P98，2，3；P104，2，3；P107，1，3；P112，5；P115，1，2，3。疑難解析 1、公式恒真性的判定判定公式的恒真性，包括判定公式是恒真的或是恒假的。具體方法有兩種，一是真值表法，對(duì)于任給一個(gè)公式，主要列出該公式的真值表，觀察真值表的最后一列是否全為1（或全為0），就可以判定該公式是否恒真（或恒假），若不全為0，則為可滿足的。二是推導(dǎo)法，即利用基本等價(jià)式推導(dǎo)出結(jié)果為1，或者利用恒真（恒假）判定定理：公式G 是恒真的（恒假的）當(dāng)且僅當(dāng)?shù)葍r(jià)于它的合取范式（析取范式）中，每個(gè)子句（短語(yǔ)）均至少包含一個(gè)原子及其否定。這里要求的析取范式中所含有的每個(gè)短語(yǔ)不是極小

12、項(xiàng)，一定要與求主析取范式相區(qū)別，對(duì)于合取范式也同樣。2、范式求范式，包括求析取范式、合取范式、主析取范式和主合取范式。關(guān)鍵有兩點(diǎn)：一是準(zhǔn)確理解掌握定義；另一是巧妙使用基本等價(jià)式中的分配律、同一律和互補(bǔ)律，結(jié)果的前一步適當(dāng)使用等冪律，使相同的短語(yǔ)（或子句）只保留一個(gè)。另外，由已經(jīng)得到的主析?。ê先。┓妒?，根據(jù)GGGG,1原理，參閱離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)書(shū)P71 例 15，可以求得主合取（析?。┓妒?。3、形式演繹法掌握形式演繹進(jìn)行邏輯推理時(shí)，一是要理解并掌握14 個(gè)基本蘊(yùn)涵式，二是會(huì)使用三個(gè)規(guī)則：規(guī)則P、規(guī)則 Q 和規(guī)則 D，需要進(jìn)行一定的練習(xí)。例題分析 例 1 求PRQPG的主析取范式與主合取范式。解

13、（1）求主析取范式，方法 1：利用真值表求解RQPQPRQPG 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 1 0 精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 6 頁(yè)，共 25 頁(yè)7 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 1 1 0 1 0 1 1 1 1 1 1 1 因此RQPRQPRQPRQPRQPRQPG方法 2：推導(dǎo)法RQPRQPRQPRQPRQPRQPRQPRQPRQPRQPRQPRQPRQPRQPRRQQPPPRQQQRPPRQRPPRQPPRQPPRRQPG（2）求主合取范式方法 1：利用上面的真值表PRQP為 0 的有兩行，它們對(duì)應(yīng)的

14、極大項(xiàng)分別為RQPRQP,因此，RQPRQPPRQP方法 2：利用已求出的主析取范式求主合取范式已用去 6 個(gè)極小項(xiàng)，尚有2 個(gè)極小項(xiàng)，即RQP與RQP于是RQPRQPRQPRQPGGRQPRQPG例 2 試證明公式RPRQQPG為恒真公式。證法一：見(jiàn)離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)書(shū)P60 例 6（4）的解答。（真值表法）證法二：精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 7 頁(yè)，共 25 頁(yè)8 G=（P Q）（Q R）（P R）=（PQ）（QR）P R=（P Q）（PR）（Q Q）（QR）P）R=（P QP）（PRP）（QRP）R=（1（QRP）R=QRP R=1 故 G 為恒真公式。例 3 利用形式演繹法證明 P

15、（QR），S P，Q 蘊(yùn)涵 SR。證明：（1）S P 規(guī)則 P（2）S 規(guī)則 D（3）P 規(guī)則 Q，根據(jù)（1），（2）（4）P（QR）規(guī)則 P（5）QR 規(guī)則 Q，根據(jù)（3），（4）（6）Q 規(guī)則 P（7）R 規(guī)則 Q，根據(jù)（5），（6）（8）SR 規(guī)則 D，根據(jù)（2），（7）第四章謂詞邏輯復(fù)習(xí)知識(shí)點(diǎn) 1、謂詞、量詞、個(gè)體詞、個(gè)體域、變?cè)s束變?cè)c自由變?cè)?、謂詞公式與解釋，謂詞公式的類型（恒真、恒假、可滿足）3、謂詞公式的等價(jià)和蘊(yùn)涵4、前束范式本章重點(diǎn)內(nèi)容：謂詞與量詞、公式與解釋、前束范式復(fù)習(xí)要求 1、理解謂詞、量詞、個(gè)體詞、個(gè)體域、變?cè)母拍?；理解用謂詞、量詞、邏輯聯(lián)結(jié)詞描述一個(gè)簡(jiǎn)單命

16、題；了解命題符號(hào)化。2、理解公式與解釋的概念；掌握在有限個(gè)體域下消去公式量詞，求公式在給定解釋下真值精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 8 頁(yè)，共 25 頁(yè)9 的方法；了解謂詞公式的類型。3、理解用解釋的方法證明等價(jià)式和蘊(yùn)涵式。4、掌握求公式前束范式的方法。本章重點(diǎn)習(xí)題 P120，1，2；P125126，1，3；P137，1。疑難解析 1、謂詞與量詞反復(fù)理解謂詞與量詞引入的意義，概念的含義及在謂詞與量詞作用下變量的自由性、約束性與改名規(guī)則。2、公式與解釋能將一階邏輯公式表達(dá)式中的量詞消除，寫(xiě)成與之等價(jià)的公式，然后將解釋I 中的數(shù)值代入公式，求出真值。3、前束范式在充分理解掌握前束范式概念的基礎(chǔ)上

17、，利用改名規(guī)則、基本等價(jià)式與蘊(yùn)涵式（一階邏輯中），將給定公式中量詞提到母式之前稱為首標(biāo)。典型例題 例 1 設(shè) I 是如下一個(gè)解釋：3,2DF(2)F(3)P(2)P(3)Q(2,2)Q(2,3)Q(3,2)Q(3,3)3 2 0 1 1 1 0 1 求y,xFQxPyx的真值。解110111110003,3FQ3P2,3FQ3P3,2FQ2P2,2FQ2P3,xFQxP2,xFQxPxy,xFQxPyx例 2 試將一階邏輯公式化成前束范式。解精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 9 頁(yè)，共 25 頁(yè)10 xRzQyxPzyxxRzQzyxyPxxRyQyyxyPxxRyyQyxyPxG,第五章圖論

18、復(fù)習(xí)知識(shí)點(diǎn) 1、圖、完全圖、子圖、母圖、支撐子圖、圖的同構(gòu)2、關(guān)聯(lián)矩陣、相鄰矩陣3、權(quán)圖、路、最短路徑，迪克斯特拉算法（Dijkstra）4、樹(shù)、支撐樹(shù)、二叉樹(shù)5、權(quán)圖中的最小樹(shù)，克魯斯卡爾算法（Kruskal）6、有向圖、有向樹(shù)本章重點(diǎn)內(nèi)容：權(quán)圖的最短路、二叉樹(shù)的遍歷、權(quán)圖中的最優(yōu)支撐樹(shù)復(fù)習(xí)要求 1、理解圖的有關(guān)概念：圖、完全圖、子圖、母圖、支撐子圖、圖的同構(gòu)。2、掌握?qǐng)D的矩陣表示（關(guān)聯(lián)矩陣、相鄰矩陣）。3、理解權(quán)圖、路的概念，掌握用Dijkstra 算法求權(quán)圖中最短路的方法。4、理解樹(shù)、二叉樹(shù)與支撐樹(shù)的有關(guān)概念；掌握二叉樹(shù)的三種遍歷方法，用Kruskal 算法求權(quán)圖中最小樹(shù)的方法。5、理解

19、有向圖與有向樹(shù)的概念。本章重點(diǎn)習(xí)題 P221，2；P225，1；P231，2，3；P239，5；P242，1，2。疑難解析 1.本章的概念較多，學(xué)習(xí)時(shí)需要認(rèn)真比較各概念的含義，如：圖、子圖、有向圖、權(quán)圖；樹(shù)、支撐樹(shù)、二叉樹(shù)、有向樹(shù)；路、簡(jiǎn)單路、回路等，這些都是圖的基本概念，今后將在數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫(kù)、計(jì)算機(jī)網(wǎng)絡(luò)等課程中用到。2、權(quán)圖中的最短路嚴(yán)格執(zhí)行迪克斯特拉（Dijkstra）算法步驟，從起點(diǎn)起，到每一點(diǎn)求出最短路，然后進(jìn)行仔細(xì)比較，最后到達(dá)終點(diǎn)，算出最小權(quán)和。精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 10 頁(yè)，共 25 頁(yè)11 3、權(quán)圖中的最優(yōu)支撐樹(shù)權(quán)圖中的最優(yōu)支撐樹(shù)是圖中所帶權(quán)和最小的支撐樹(shù)，使用

20、克魯斯卡爾（Kruskal）算法。典型例題 例1在具有 n 個(gè)頂點(diǎn)的完全圖Kn中刪去多少條邊才能得到樹(shù)？解：n 個(gè)頂點(diǎn)的完全圖Kn中共有 n（n-1）/2 條邊，n 個(gè)頂點(diǎn)的樹(shù)應(yīng)有n-1 條邊，于是，刪去的邊有：n（n-1）/2-（n-1）=（n-1）（n-2）/2 例2求下面有限圖中點(diǎn)u 到各點(diǎn)間的最短路。（圖上數(shù)字見(jiàn)教材P231，第 3 題。）解uu1，d(u,u1)=1,路(u,u1)u u2,d(u,u2)=9,路(u,u4,u3,u7,u2)u u3,d(u,u3)=5,路(u,u4,u3,)u u4,d(u,u4)=3,路(u,u4)u u5,d(u,u5)=11,路(u,u1,u

21、5)或路(u,u4,u3,u7,u2,u5)u u6,d(u,u6)=13,路(u,u1,u5,u6)u u7,d(u,u7)=8,路(u,u4,u3,u7)u u8,d(u,u8)=11,路(u,u4,u8)uv,d(u,v)=15,路(u,u1,u5,u6,v)或路(u,u4,u3,u7,u6,v)二、考核說(shuō)明本課程的考核實(shí)行形成性考核和終結(jié)性考核的形式。形成性考核占總成績(jī)的20%，以課程作業(yè)的形式進(jìn)行（共三次，由中央電大統(tǒng)一布置）；終結(jié)性考核即期末考試，占總成績(jī)的 80%?？偝煽?jī)?yōu)?00 分，60 分及格。期末考試實(shí)行全國(guó)統(tǒng)一閉卷考核，試卷滿分為100。由中央電大統(tǒng)一命題，統(tǒng)一評(píng)分標(biāo)準(zhǔn)，

22、統(tǒng)一考試時(shí)間（考試時(shí)間為120 分鐘）。精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 11 頁(yè)，共 25 頁(yè)12 1、試題類型試題類型有填空題（分?jǐn)?shù)約占20%）、單項(xiàng)選擇題（分?jǐn)?shù)約占14%）、計(jì)算題（分?jǐn)?shù)約占 50%）和證明題（分?jǐn)?shù)約占16%）。填空題和單項(xiàng)選擇題主要涉及基本概念、基本理論，重要性質(zhì)和結(jié)論、公式及其簡(jiǎn)單計(jì)算。計(jì)算題主要考核學(xué)生的基本運(yùn)算技能，要求書(shū)寫(xiě)計(jì)算、推論過(guò)程或理由。證明題主要考查應(yīng)用概念、性質(zhì)、定理及主要結(jié)論進(jìn)行邏輯推理的能力，要求寫(xiě)出推理過(guò)程。2、考核試卷題量分配試卷題量在各部分的分配是：集合論約占40%，數(shù)理邏輯約占40%，圖論約占20%。具體課程考核情況見(jiàn)課程考核說(shuō)明。附錄：試

23、題類型及規(guī)范解答舉例填空題 1.設(shè) R 是集合 A 上的二元關(guān)系，如果關(guān)系R 同時(shí)具有性、對(duì)稱性和性，則稱 R 是等價(jià)關(guān)系。2.命題公式G=（P Q）R，則 G 共有個(gè)不同的解釋；把G 在其所有解釋下所取真值列成一個(gè)表，稱為G 的；解釋（P，Q，R）或（0，1，0）使 G 的真值為。3.設(shè) G=（P，L）是圖，如果G 是連通的，并且，則 G 是樹(shù)。如果根樹(shù)T的每個(gè)點(diǎn) v 最多有兩棵子樹(shù)，則稱T 為。單項(xiàng)選擇題（選擇一個(gè)正確答案的代號(hào)，填入括號(hào)中）1.由集合運(yùn)算定義，下列各式正確的有（）。A XXY B.XXY C.XXY D.YXY 2.設(shè) R1，R2是集合 A=a，b，c，d上的兩個(gè)關(guān)系，其

24、中R1=（a，a），（b，b），（b，c），（d，d），R2=（a，a），（b，b），（b，c），（c，b），（d，d），則R2是 R1的（）閉包。A自反B對(duì)稱C傳遞D以上都不是3.設(shè) G 是由 5 個(gè)頂點(diǎn)組成的完全圖，則從G 中刪去（）條邊可以得到樹(shù)。A4 B5 C6 D10 計(jì)算題 1.化簡(jiǎn)下式：精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 12 頁(yè)，共 25 頁(yè)13（A B C）（A B）C）（AB C）（ABC）2.通過(guò)求主析取范式判斷下列命題公式是否等值。（1）（P Q）（P Q R）；（2）（P（Q R）（Q（P R）；3.求圖中 A 到其余各頂點(diǎn)的最短路徑，并寫(xiě)出它們的權(quán)。證明題 1.利用基

25、本等價(jià)式證明下面命題公式為恒真公式。（PQ）（QR）（PR）2.用形式演繹法證明：PQ，RS，P R 蘊(yùn)涵 Q S。試題答案及評(píng)分標(biāo)準(zhǔn)填空題 1、自反；傳遞2、8；真值表；1 3、無(wú)回路；二叉樹(shù)單項(xiàng)選擇題（選擇一個(gè)正確答案的代號(hào)，填入括號(hào)中）1、A 2、B 3、C 計(jì)算題 1.解：（A B C）（A B）C）（AB C）（ABC）=（ABC）（ABC）（ABC）（ABC）=（AB）（CC）（AB）（CC）=（AB）E）（AB）E）E 為全集B 7 C 1 2 A 2 5 3 D 46 E 1 F 精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 13 頁(yè)，共 25 頁(yè)14=（AB）（AB）=A（BB）=AE=

26、A 2.解：（P Q）（P Q R）（P Q（R R）（P Q R）（P QR）（P Q R）（P Q R）m6m7m3 m3m6m7（P（Q R）（Q（P R）（P Q）（Q R）（PP R）（P Q R）（分配律）（P Q（R R）（P P）Q R）（P Q R）（P QR）（P Q R）（P Q R）（P Q R）（P Q R）m6m7m3m7m3 m3m6m7 由此可見(jiàn)（P Q）（P Q R）（P（Q R）（Q（P R）3.解：A 到 B 的最短路徑為AB，權(quán)為 1；A 到 E 的最短路徑為ABE，權(quán)為 3；A 到 F 的最短路徑為ABEF，權(quán)為 4；A 到 C 的最短路徑為ABEFC

27、，權(quán)為 7；A 到 D 的最短路徑為ABEFCD，權(quán)為 9。證明題 1.證明：（PQ）（QR）（PR）（P Q）（Q R）（P R）（P Q）（Q R）（P R）（PQ）（QR）P R（PQ）P）（QR）R）精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 14 頁(yè)，共 25 頁(yè)15（1（QP）（Q R）1）QP Q R（Q Q）P R 1 P R 1 2.證明：（1）P R 規(guī)則 P（2）RP 規(guī)則 Q，根據(jù)（1）（3）PQ 規(guī)則 P（4）R Q 規(guī)則 Q，根據(jù)（2）（3）（5）QR 規(guī)則 Q，根據(jù)（4）（6）RS 規(guī)則 P（7）QS 規(guī)則 Q，根據(jù)（5）（6）（8）Q S 規(guī)則 Q，根據(jù)（7）三、綜合練習(xí)

28、及解答（一）填空題1、集合的表示方法有兩種：法和法。請(qǐng)把“大于3而 小 于 或 等 于7的 整 數(shù) 集 合”用 任 一 種 集 合 的 表 示 方 法 表 示 出 來(lái)A=。2、A，B 是兩個(gè)集合，A=1，2，3，4，B=2，3，5，則 B-A=，（B）（A）=，（B）的元素個(gè)數(shù)為。3、設(shè) 2,1,BbaA，則從 A 到 B 的所有映射是。4、設(shè)命題公式)(RQPG，則使公式G 為假的解釋是、和。5、設(shè) G 是完全二叉樹(shù)，G 有 15 個(gè)點(diǎn)，其中8個(gè)葉結(jié)點(diǎn)，則G 的總度數(shù)為，分枝點(diǎn)數(shù)為。6、全集 E=1，2，3，4，5，A=1，5，B=1，2，3，4，C=2，5，求 AB=精選學(xué)習(xí)資料 -名師歸

29、納總結(jié)-第 15 頁(yè)，共 25 頁(yè)16，（A）（C）=，C=。7、設(shè) A 和 B 是任意兩個(gè)集合，若序偶的第一個(gè)元素是A 的一個(gè)元素，第二個(gè)元素是B 的一個(gè)元素，則所有這樣的序偶集合稱為集合A 和 B 的，記作 AB，即 A B=。A B 的子集 R 稱為 A，B 上的。8、將幾個(gè)命題聯(lián)結(jié)起來(lái)，形成一個(gè)復(fù)合命題的邏輯聯(lián)結(jié)詞主要有否定、和等值。9、表達(dá)式x yL（x，y）中謂詞的定義域是a，b，c，將其中的量詞消除，寫(xiě)成與之等價(jià)的命題公式為。10、一個(gè)無(wú)向圖表示為G=（P，L），其中P 是的集合，L 是的集合，并且要求。（二）單項(xiàng)選擇題（選擇一個(gè)正確答案的代號(hào)，填入括號(hào)中）1.設(shè)命題公式)()(

30、PRQPPG，則 G 是（）。A.恒真的B.恒假的C.可滿足的D.析取范式2、設(shè)集合,cbaA，A 上的關(guān)系),(),(),(cbbaaaR，則2R=（）。).,(),(),()();,(),(),()();,(),(),()();,(),(),()(ccbaaaDbbcabaCcbcabaBcabaaaA3、一個(gè)公式在等價(jià)意義下，下面哪個(gè)寫(xiě)法是唯一的（）。A析取范式B合取范式C主析取范式D以上答案都不對(duì)4、設(shè)命題公式G=（PQ），H=P（QP），則 G 與 H 的關(guān)系是（）。AGH BHG CG=H D以上都不是5、已知圖G 的相鄰矩陣為0111110101110001000111010，則

31、 G 有（）。A.5 點(diǎn)，8 邊B.6 點(diǎn)，7 邊C.5 點(diǎn)，7 邊D.6 點(diǎn)，8 邊精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 16 頁(yè)，共 25 頁(yè)17 6、下列命題正確的是（）。A=B=C aa，b，c Da，b，c 7、設(shè)集合A=a，b，c，A 上的關(guān)系R=（a，b），（a，c），（b，a），（b，c），（c，a），（c，b），（c，c），則 R 具有關(guān)系的（）性質(zhì)。A自反B對(duì)稱C傳遞D反對(duì)稱8、設(shè) R 為實(shí)數(shù)集，映射=RR，（x）=-x2+2x-1，則是（）。A單射而非滿射B滿射而非單射C雙射D既不是單射，也不是滿射9、下列語(yǔ)句中，（）是命題。A下午有會(huì)嗎？B這朵花多好看呀！C2 是常數(shù)。D請(qǐng)

32、把門(mén)關(guān)上。10、下面給出的一階邏輯等價(jià)式中，（）是錯(cuò)的。Ax（A（x）B（x）=xA（x）xB（x）B AxB（x）=x（AB（x）Cx（A（x）B（x）=xA（x）xB（x）DxA（x）=x（A（x）（三）計(jì)算題1、設(shè) R 和 S 是集合4,3,2,1A上的關(guān)系，其中)4,4(),4,2(),3,2(),2,1()4,3(),3,2(),3,1(),1,1(SR，試求：（1）寫(xiě)出 R 和 S 的關(guān)系矩陣；（2）計(jì)算111,RSRSRSR。2、設(shè) A=a，b，c，d，R1，R2是 A 上的關(guān)系，其中R1=（a，a），（a，b），（b，a），（b，b），（c，c），（c，d），（d，c），（d，

33、d），R2=（a，b），（b，a），（a，c），（c，a），（b，c），（c，b），（a，a），（b，b），（c，c）。（1）畫(huà)出 R1和 R2的關(guān)系圖；（2）判斷它們是否為等價(jià)關(guān)系，是等價(jià)關(guān)系的求A 中各元素的等價(jià)類。3、用真值表判斷下列公式是恒真？恒假？可滿足？（1）（PP）Q（2）（PQ）Q（3）（PQ）（QR）（PR）4、設(shè)解釋 I 為：精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 17 頁(yè)，共 25 頁(yè)18（1）定義域D=-2，3，6；（2）F（x）：x 3；G（x）：x 5。在解釋 I 下求公式x（F（x）G（x）的真值。5、求下圖所示權(quán)圖中從u 到 v 的最短路，畫(huà)出最短路并計(jì)算它們的權(quán)值。

34、6、化簡(jiǎn)下式：（ABC）（AB）（A（B C）A）7、已知 A=1，2，3，4，5，B=1，2，3，R 是 A 到 B 的二元關(guān)系，并且R=（x，y）|xA 且 yB 且 2 x+y 4，畫(huà)出 R 的關(guān)系圖，并寫(xiě)出關(guān)系矩陣。8、畫(huà)出下面偏序集（A，）的哈斯圖，并指出集合A 的最小元、最大元、極大元和極小元。其中A=a，b，c，d，e，=（a，b），（a，c），（a，d），（a，e），（b，e），（c，e），（d，e）IA。9、求命題公式（P Q）（P Q）的析取范式與合取范式。10、給定解釋I 如下：定義域 D=2，3；f（2）f（3）F（2，2）F（2，3）F（3，2）F（3，3）3 2 0

35、 0 1 1 求xy（F（x，y）F（f（x），f（y）。11、設(shè)有 5 個(gè)城市 v1，v2，v3，v4，v5，任意兩城市之間鐵路造價(jià)如下：（以百萬(wàn)元為單位）w（v1，v2）=4，w（v1，v3）=7，w（v1，v4）=16，w（v1，v5）=10，w（v2，v3）=13，w（v2，v4）=8，w（v2，v5）=17，w（v3，v4）=3，w（v3，v5，）=10，w（v4，v5）=12 V17 V3 12 U 2 5 3 V 46 V21 V4 精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 18 頁(yè)，共 25 頁(yè)19 試求出連接5 個(gè)城市的且造價(jià)最低的鐵路網(wǎng)。（四）證明題1、證明等價(jià)式RRPRQRQP)

36、()()(。2、利用形式演繹法證明：,TRSTSRPQP蘊(yùn)涵 Q。3、A，B，C 為任意的集合，證明：（A B）C=A（BC）4、利用一階邏輯的基本等價(jià)式，證明：xy（F（x）G（y）=xF（x）yG（y）練習(xí)解答（一）填空題1、列舉；描述；A=4，5，6，7 或 A=x|3x 7 2、5；5，2，5，3，5，2，3，5；8 3、1=（a，1），（b，1）；2=（a，2），（b，2）；3=（a，1），（b，2）；4=（a，2），（b，1）4、（1，0，1）；（1，1，1）；（1，0，0）5、28；7 6、5；，5；1，3，4 7、笛卡爾積（或直乘積）；（x，y）|x A 且 yB；二元關(guān)系8、

37、并且（或合?。?；或者（或析?。惶N(yùn)涵9、（L（a，a）L（a，b）L（a，c）（L（b，a）L（b，b）L（b，c）（L（c，a）L（c，b）L（c，c）10、點(diǎn)；連接某些不同點(diǎn)對(duì)的邊；一對(duì)不同點(diǎn)之間最多有一條邊（二）單項(xiàng)選擇題（選擇一個(gè)正確答案的代號(hào)，填入括號(hào)中）1、C 2、A 3、C 4、A 5、C 6、A 7、B 8、D 9、C 10、A（三）計(jì)算題1、解：（1）精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 19 頁(yè)，共 25 頁(yè)20 1000000011000010,0000100001000101SRMM（2）SR=（1，2），（3，4）SR=（1，1），（1，2），（1，3），（2，3），（2

38、，4），（3，4），（4，4）1R=（1，1），（3，1），（3，2），（4，3）11RS=（2，1），（4，3）2、解：R1和 R2的關(guān)系圖略。由關(guān)系圖可知，R1是等價(jià)關(guān)系。R1不同的等價(jià)類有兩個(gè)，即a，b 和c，d。由于 R2不是自反的，所以R2不是等價(jià)關(guān)系。3、解：（1）真值表P Q P PP（PP）Q 0 0 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 0 0 0 因此公式（1）為可滿足。（2）真值表P Q PQ（PQ）（PQ）Q 0 0 1 0 0 0 1 1 0 0 1 0 0 1 0 1 1 1 0 0 因此公式（2）為恒假。（3）真值表精選學(xué)習(xí)資料 -名師歸納總

39、結(jié)-第 20 頁(yè)，共 25 頁(yè)21 P Q R PQ QR PR（PQ）（QR）（PR）0 0 0 1 1 1 1 0 0 1 1 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 1 1 因此公式（3）為恒真。4.解：x（F（x）G（x）（F（-2）G（-2）（F（3）G（3）（F（6）G（6）（1 0）（1 0）（0 1）1 5.解：從 U到 V的最短路為UV1V2V4V3V。最短路權(quán)值為9。圖中圓圈中的數(shù)字為使用迪克斯特拉算法添加邊的次序。6、解：（ABC）（AB）（

40、A（B C）A）=（AB）A（利用兩次吸收律）=（AB）A=（A A）（B A）=（B A）=B A V1V3 12 U 2 3 V V2 1 V4精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 21 頁(yè)，共 25 頁(yè)22 7、解：R=（1，1），（1，2），（1，3），（2，1），（2，2），（3，1）R 的關(guān)系圖為關(guān)系矩陣 MR=1 1 1 11 0 10 0 0 0 0 0 0 0 1、解：（A，）的哈斯圖為：a為 A 的極小元，也是最小元；e為 A 的極大元，也是最大元。9、解：1 1 2 2 33 4 5 e b c d a 精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 22 頁(yè)，共 25 頁(yè)23（P Q）（

41、P Q）（P Q）（P Q）（P Q）（P Q）（P Q）（P Q）（PQ）（PQ）（P Q）（PQ）上面結(jié)果為合取范式。利用對(duì) 分配得：（P Q）（PQ）（PP）（PQ）（QP）（QQ）（PQ）（QP）上面結(jié)果為析取范式。10、解：xy（F（x，y）F（f（x），f（y）x（F（x，2）F（f（x），f（2）（F（x，3）F（f（x），f（3）（F（2，2）F（f（2），f（2）（F（2，3）F（f（2），f（3）（F（3，2）F（f（3），f（2）（F（3，3）F（f（3），f（3）（01）（01）（10）（10）0 11、解：首先將本題用權(quán)圖來(lái)描述，于是求解此題便成為求權(quán)圖中的最優(yōu)支撐樹(shù)

42、問(wèn)題，按克魯斯卡爾算法，下圖為求解最優(yōu)支撐樹(shù)的過(guò)程：（a）（b）精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 23 頁(yè)，共 25 頁(yè)24（c）（d）（e）連接 5個(gè)城市的造價(jià)最低的鐵路網(wǎng)總造價(jià)為24（百萬(wàn)元）。（四）證明題1、證明：RRRQPQPRPQQPRPQRQPRPQRQPRPRQRQP1)()()()()()()()()()()(2、證明：（1）TS規(guī)則 P（2）T規(guī)則 P（3）S規(guī)則 Q，根據(jù)（1）、（2）和基本蘊(yùn)涵式（12）（4）RS規(guī)則 P（5）R規(guī)則 Q，根據(jù)（3）、（4）和基本蘊(yùn)涵式（11）（6）RP規(guī)則 P（7）P規(guī)則 Q，根據(jù)（5）、（6）和基本蘊(yùn)涵式（12）（8）QP規(guī)則 P（9）Q規(guī)則 Q，根據(jù)（7）、（8）和基本蘊(yùn)涵式（10）3、證明：（A B）C=（AB）C=A（BC）=A（BC）=A（BC）精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 24 頁(yè)，共 25 頁(yè)25 4、證明：xy（F（x）G（y）=x（F（x）y G（y）=x（F（x）y G（y）=x（F（x）y G（y）=xF（x）y G（y）=xF（x）yG（y）精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 25 頁(yè)，共 25 頁(yè)