《離散數學（第三版）》方世昌的期末復習知識點總結含例題一、各章復習要求與重點第一章集合[復習知識點]1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、冪集2、集合的交、并、差、補等運算及其運算律（交換律、結合律、分配律、吸收律、DeMorgan律等），文氏（Venn）圖3、序偶與迪卡爾積本章重點內容：集合的概念、集合的運算性質、集合恒等式的證明[復習要求]1、理解集合、元素、子集、空集、全集、集合的包含、相等、冪集等基本概念。2、掌握集合的表示法和集合的交、并、差、補等基本運算。3、掌握集合運算基本規律，證明集合等式的方法。4、了解序偶與迪卡爾積的概念，掌握迪卡爾積的運算。[疑難解析]1、集合的概念因為集合的概念學生在中學階段已經學過，這里只多了一個冪集概念，重點對冪集加以掌握，一是掌握冪集的構成，一是掌握冪集元數為2n。2、集合恒等式的證明通過對集合恒等式證明的練習，既可以加深對集合性質的理解與掌握；又可以為第三章命題邏輯中公式的基本等價式的應用打下良好的基礎。實際上，本章做題是一種基本功訓練，尤其要求學生重視吸收律和重要等價式在證明中的特殊作用。[例題分析]例1設A，B是兩個集合，A={1，2，3}，B={1，2}，則。解于是例2設(1)，試求：；(2)；(5)；(3)；(6)；(4)。解(1)(2)(3)(4)(5)(6)例3試證明證明第二章二元關系[復習知識點]1、關系、關系矩陣與關系圖2、復合關系與逆關系3、關系的性質（自反性、對稱性、反對稱性、傳遞性）4、關系的閉包（自反閉包、對稱閉包、傳遞閉包）5、等價關系與等價類6、偏序關系與哈斯圖（Hasse）、極大/小元、最大/小元、上/下界、最小上界、最大下界7、函數及其性質（單射、滿射、雙射）8、復合函數與反函數本章重點內容：二元關系的概念、關系的性質、關系的閉包、等價關系、半序關系、映射的概念[復習要求]1、理解關系的概念：二元關系、空關系、全關系、恒等關系；掌握關系的集合表示、關系矩陣和關系圖、關系的運算。2、掌握求復合關系與逆關系的方法。3、理解關系的性質（自反性、對稱性、反對稱性、傳遞性），掌握其判別方法（定義、矩陣、圖）。4、掌握求關系的閉包（自反閉包、對稱閉包、傳遞閉包）的方法。5、理解等價關系和偏序關系的概念，掌握等價類的求法和偏序關系做哈斯圖的方法，極大/小元、最大/小元、上/下界、最小上界、最大下界的求法。6、理解函數概念：函數、函數相等、復合函數和反函數。7、理解單射、滿射、雙射等概念，掌握其判別方法。[本章重點習題]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。[疑難解析]1、關系的概念關系的概念是第二章全章的基礎，又是第一章集合概念的應用。因此，學生應該真正理解并熟練掌握二元關系的概念及關系矩陣、關系圖表示。2、關系的性質及其判定關系的性質既是對關系概念的加深理解與掌握，又是關系的閉包、等價關系、半序關系的基礎。對于四種性質的判定，可以依據教材中P49上總結的規律。這其中對傳遞性的判定，難度稍大一點，這里要提及兩點：一是不破壞傳遞性定義，可認為具有傳遞性。如空關系具有傳遞性，同時空關系具有對稱性與反對稱性，但是不具有自反性。另一點是介紹一種判定傳遞性的“跟蹤法”，即若，則。如若，則有，且。３、關系的閉包在理解掌握關系閉包概念的基礎上，主要掌握閉包的求法。關鍵是熟記三個定理的結論：定理2，；定理3，；定理4，推論。４、半序關系及半序集中特殊元素的確定理解與掌握半序關系與半序集概念的關鍵是哈斯圖。哈斯圖畫法掌握了，對于確定任一子集的最大（小）元，極大（小）元也就容易了。這里要注意，最大（小）元與極大（小）元只能在子集內確定，而上界與下界可在子集之外的全集中確定，最小上界為所有上界中最小者，最小上界再小也不小于子集中的任一元素，可以與某一元素相等，最大下界也同樣。５、映射的概念與映射種類的判定映射的種類主要指單射、滿射、雙射與非單非滿射。判定的方法除定義外，可借助于關系圖，而實數集的子集上的映射也可以利用直角坐標系表示進行，尤其是對各種初等函數。[例題分析]例1設集合，判定下列關系，哪些是自反的，對稱的，反對稱的和傳遞的：解：均不是自反的；R4是對稱的；R1,R2,R3,R4,R5是反對稱的；R1,R2,R3,R4,R5是傳遞的。例2設集合，A上的二元關系R為（１）寫出R的關系矩陣，畫出R的關系圖；（２）證明R是A上的半序關系，畫出其哈斯圖；（３）若界。，且，求B的最大元，最小元，極大元，極小元，最小上界和最大下解（1）R的關系矩陣為R的關系圖略（2）因為R是自反的，反對稱的和傳遞的，所以R是A上的半序關系。(A,R)為半序集，(A,R)的哈斯圖如下。4。1。3。2。5(3)當，B的極大元為2，4；極小元為2，5；B無最大元與最小元；B也無上界與下界，更無最小上界與最大下界。第三章命題邏輯[復習知識點]１、命題與聯結詞（否定、析取、合取、蘊涵、等價），復合命題２、命題公式與解釋，真值表，公式分類（恒真、恒假、可滿足），公式的等價３、析取范式、合取范式，極小（大）項，主析取范式、主合取范式４、公式類別的判別方法（真值表法、等值演算法、主析取/合取范式法）５、公式的蘊涵與邏輯結果６、形式演繹本章重點內容：命題與聯結詞、公式與解釋、析取范式與合取范式、公式恒真性的判定、形式演繹[復習要求]１、理解命題的概念；了解命題聯結詞的概念；理解用聯結詞產生復合命題的方法。２、理解公式與解釋的概念；掌握求給定公式真值表的方法，用基本等價式化簡其他公式，公式在解釋下的真值。３、了解析取（合取）范式的概念；理解極大（小）項的概念和主析取（合取）范式的概念；掌握用基本等價式或真值表將公式化為主析取（合取）范式的方法。４、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判別公式類型和公式等價的方法。５、理解公式蘊涵與邏輯結果的概念，掌握基本蘊涵式。6、掌握形式演繹的證明方法。[本章重點習題]P93，1；P98，2，3；P104，2，3；P107，1，3；P112，5；P115，1，2，3。[疑難解析]1、公式恒真性的判定判定公式的恒真性，包括判定公式是恒真的或是恒假的。具體方法有兩種，一是真值表法，對于任給一個公式，主要列出該公式的真值表，觀察真值表的最后一列是否全為1（或全為0），就可以判定該公式是否恒真（或恒假），若不全為0，則為可滿足的。二是推導法，即利用基本等價式推導出結果為1，或者利用恒真（恒假）判定定理：公式G是恒真的（恒假的）當且僅當等價于它的合取范式（析取范式）中，每個子句（短語）均至少包含一個原子及其否定。這里要求的析取范式中所含有的每個短語不是極小項，一定要與求主析取范式相區別，對于合取范式也同樣。2、范式求范式，包括求析取范式、合取范式、主析取范式和主合取范式。關鍵有兩點：一是準確理解掌握定義；另一是巧妙使用基本等價式中的分配律、同一律和互補律，結果的前一步適當使用等冪律，使相同的短語（或子句）只保留一個。另外，由已經得到的主析取（合取）范式，根據原理，參閱《離散數學學習指導書》P71例15，可以求得主合取（析取）范式。3、形式演繹法掌握形式演繹進行邏輯推理時，一是要理解并掌握14個基本蘊涵式，二是會使用三個規則：規則P、規則Q和規則D，需要進行一定的練習。[例題分析]例1求的主析取范式與主合取范式。解（1）求主析取范式，方法1：利用真值表求解G010111100000101001110010111000000011010101因此方法2：推導法（2）求主合取范式方法1：利用上面的真值表為0的有兩行，它們對應的極大項分別為因此，方法2：利用已求出的主析取范式求主合取范式已用去6個極小項，尚有2個極小項，即與于是例2試證明公式為恒真公式。證法一：見〈離散數學學習指導書〉P60例6（4）的解答。（真值表法）證法二：G=（（PQ）（QR））（PR）=（PQ）（QR）PR=（（（PQ）（PR）（QQ）（QR））P）R=（（PQP）（PRP）（QRP））R=（1（QRP））R=QRPR=1故G為恒真公式。例3利用形式演繹法證明{P（QR），SP，Q}蘊涵SR。證明：（1）SP（2）S規則P規則D（3）P規則Q，根據（1），（2）（4）P（QR）規則P（5）QR（6）Q規則Q，根據（3），（4）規則P（7）R規則Q，根據（5），（6）規則D，根據（2），（7）（8）SR第四章謂詞邏輯[復習知識點]1、謂詞、量詞、個體詞、個體域、變元（約束變元與自由變元）2、謂詞公式與解釋，謂詞公式的類型（恒真、恒假、可滿足）3、謂詞公式的等價和蘊涵4、前束范式本章重點內容：謂詞與量詞、公式與解釋、前束范式[復習要求]1、理解謂詞、量詞、個體詞、個體域、變元的概念；理解用謂詞、量詞、邏輯聯結詞描述一個簡單命題；了解命題符號化。2、理解公式與解釋的概念；掌握在有限個體域下消去公式量詞，求公式在給定解釋下真值的方法；了解謂詞公式的類型。3、理解用解釋的方法證明等價式和蘊涵式。4、掌握求公式前束范式的方法。[本章重點習題]P120，1，2；P125~126，1，3；P137，1。[疑難解析]1、謂詞與量詞反復理解謂詞與量詞引入的意義，概念的含義及在謂詞與量詞作用下變量的自由性、約束性與改名規則。2、公式與解釋能將一階邏輯公式表達式中的量詞消除，寫成與之等價的公式，然后將解釋I中的數值代入公式，求出真值。3、前束范式在充分理解掌握前束范式概念的基礎上，利用改名規則、基本等價式與蘊涵式（一階邏輯中），將給定公式中量詞提到母式之前稱為首標。[典型例題]例1設I是如下一個解釋：F(2)F(3)P(2)P(3)Q(2,2)Q(2,3)Q(3,2)Q(3,3)32011101求的真值。解例2試將一階邏輯公式化成前束范式。解第五章圖論[復習知識點]1、圖、完全圖、子圖、母圖、支撐子圖、圖的同構2、關聯矩陣、相鄰矩陣3、權圖、路、最短路徑，迪克斯特拉算法（Dijkstra）4、樹、支撐樹、二叉樹5、權圖中的最小樹，克魯斯卡爾算法（Kruskal）6、有向圖、有向樹本章重點內容：權圖的最短路、二叉樹的遍歷、權圖中的最優支撐樹[復習要求]1、理解圖的有關概念：圖、完全圖、子圖、母圖、支撐子圖、圖的同構。2、掌握圖的矩陣表示（關聯矩陣、相鄰矩陣）。3、理解權圖、路的概念，掌握用Dijkstra算法求權圖中最短路的方法。4、理解樹、二叉樹與支撐樹的有關概念；掌握二叉樹的三種遍歷方法，用Kruskal算法求權圖中最小樹的方法。5、理解有向圖與有向樹的概念。[本章重點習題]P221，2；P225，1；P231，2，3；P239，5；P242，1，2。[疑難解析]1.本章的概念較多，學習時需要認真比較各概念的含義，如：圖、子圖、有向圖、權圖；樹、支撐樹、二叉樹、有向樹；路、簡單路、回路等，這些都是圖的基本概念，今后將在數據結構、數據庫、計算機網絡等課程中用到。2、權圖中的最短路嚴格執行迪克斯特拉（Dijkstra）算法步驟，從起點起，到每一點求出最短路，然后進行仔細比較，最后到達終點，算出最小權和。3、權圖中的最優支撐樹權圖中的最優支撐樹是圖中所帶權和最小的支撐樹，使用克魯斯卡爾（Kruskal）算法。[典型例題]例1在具有n個頂點的完全圖Kn中刪去多少條邊才能得到樹？解：n個頂點的完全圖Kn中共有n（n-1）/2條邊，n個頂點的樹應有n-1條邊，于是，刪去的邊有：n（n-1）/2-（n-1）=（n-1）（n-2）/2例2求下面有限圖中點u到各點間的最短路。（圖上數字見教材P231，第3題。）解uu1，d(u,u1)=1,路(u,u1)uu2,d(u,u2)=9,路(u,u4,u3,u7,u2)uu3,d(u,u3)=5,路(u,u4,u3,)uu4,d(u,u4)=3,路(u,u4)uu5,d(u,u5)=11,路(u,u1,u5)或路(u,u4,u3,u7,u2,u5)uu6,d(u,u6)=13,路(u,u1,u5,u6)uu7,d(u,u7)=8,路(u,u4,u3,u7)uu8,d(u,u8)=11,路(u,u4,u8)uv,d(u,v)=15,路(u,u1,u5,u6,v)或路(u,u4,u3,u7,u6,v)二、考核說明本課程的考核實行形成性考核和終結性考核的形式。形成性考核占總成績的20%，以課程作業的形式進行（共三次，由中央電大統一布置）；終結性考核即期末考試，占總成績的80%。總成績為100分，60分及格。期末考試實行全國統一閉卷考核，試卷滿分為100。由中央電大統一命題，統一評分標準，統一考試時間（考試時間為120分鐘）。1、試題類型試題類型有填空題（分數約占20%）、單項選擇題（分數約占14%）、計算題（分數約占50%）和證明題（分數約占16%）。填空題和單項選擇題主要涉及基本概念、基本理論，重要性質和結論、公式及其簡單計算。計算題主要考核學生的基本運算技能，要求書寫計算、推論過程或理由。證明題主要考查應用概念、性質、定理及主要結論進行邏輯推理的能力，要求寫出推理過程。2、考核試卷題量分配試卷題量在各部分的分配是：集合論約占40%，數理邏輯約占40%，圖論約占20%。具體課程考核情況見課程考核說明。附錄：試題類型及規范解答舉例[填空題]1.設R是集合A上的二元關系，如果關系R同時具有性、對稱性和性，則稱R是等價關系。2.命題公式G=（PQ）R，則G共有為G的個不同的解釋；把G在其所有解釋下所取真值列成一個表，稱；解釋（P，Q，R）或（0，1，0）使G的真值為。3.設G=（P，L）是圖，如果G是連通的，并且，則G是樹。如果根樹T的每個點v最多有兩棵子樹，則稱T為。[單項選擇題]（選擇一個正確答案的代號，填入括號中）1.由集合運算定義，下列各式正確的有（A．XXYB.XXYC.XXYD.YXY）。2.設R1，R2是集合A={a，b，c，d}上的兩個關系，其中R1={（a，a），（b，b），（b，c），（d，d）}，R2={（a，a），（b，b），（b，c），（c，b），（d，d）}，則R2是R1的（）閉包。A．自反D．以上都不是3.設G是由5個頂點組成的完全圖，則從G中刪去（A．4B．5C．6D．10B．對稱C．傳遞）條邊可以得到樹。[計算題]1.化簡下式：（ABC）（（AB）C）（ABC）（ABC）2.通過求主析取范式判斷下列命題公式是否等值。（1）（PQ）（PQR）；（2）（P（QR））（Q（PR））；3.求圖中A到其余各頂點的最短路徑，并寫出它們的權。B7C12A253D46E1F[證明題]1.利用基本等價式證明下面命題公式為恒真公式。（（PQ）（QR））（PR）2.用形式演繹法證明：{PQ，RS，PR}蘊涵QS。試題答案及評分標準[填空題]1、自反；傳遞2、8；真值表；13、無回路；二叉樹[單項選擇題]（選擇一個正確答案的代號，填入括號中）1、A2、B3、C[計算題]1.解：（ABC）（（AB）C）（ABC）（ABC）=（A~B~C）（A~BC）（AB~C）（ABC）=（（A~B）（~CC））（（AB）（~CC））=（（A~B）E）（（AB）E）=（A~B）（AB）E為全集=A（~BB）=AE=A2.解：（PQ）（PQR）（PQ（RR））（PQR）（PQR）（PQR）（PQR）m6m7m3m3m6m7（P（QR））（Q（PR））（PQ）（QR）（PPR）（PQR）（分配律）（PQ（RR））（（PP）QR）（PQR）（PQR）（PQR）（PQR）（PQR）（PQR）m6m7m3m7m3m3m6m7由此可見（PQ）（PQR）（P（QR））（Q（PR））3.解：A到B的最短路徑為AB，權為1；A到E的最短路徑為ABE，權為3；A到F的最短路徑為ABEF，權為4；A到C的最短路徑為ABEFC，權為7；A到D的最短路徑為ABEFCD，權為9。[證明題]1.證明：（（PQ）（QR））（PR）（（PQ）（QR））（PR）（（PQ）（QR））（PR）（PQ）（QR）PR（（PQ）P）（（QR）R）（1（QP））（（QR）1）QPQR（QQ）PR1PR12.證明：（1）PR（2）RP（3）PQ（4）RQ（5）QR（6）RS（7）QS規則P規則Q，根據（1）規則P規則Q，根據（2）（3）規則Q，根據（4）規則P規則Q，根據（5）（6）（8）QS規則Q，根據（7）三、綜合練習及解答（一）填空題1、集合的表示方法有兩種：集合的表示方法表示出來A={法和法。請把“大于3而小于或等于7的整數集合”用任一種}。2、A，B是兩個集合，A={1，2，3，4}，B={2，3，5}，則B-A=，（B）（A）=，（B）的元素個數為。3、設，則從A到B的所有映射是。4、設命題公式，則使公式G為假的解釋是、和。5、設G是完全二叉樹，G有15個點，其中8個葉結點，則G的總度數為，分枝點數為。6、全集E={1，2，3，4，5}，A={1，5}，B={1，2，3，4}，C={2，5}，求AB=，（A）（C）=，C=。7、設A和B是任意兩個集合，若序偶的第一個元素是A的一個元素，第二個元素是B的一個元素，則所有這樣的序偶集合稱為集合A和B的，記作AB，即AB=。AB的子集R稱為A，B上的。8、將幾個命題聯結起來，形成一個復合命題的邏輯聯結詞主要有否定、、、和等值。9、表達式xyL（x，y）中謂詞的定義域是{a，b，c}，將其中的量詞消除，寫成與之等價的命題公式為。10、一個無向圖表示為G=（P，L），其中P是的集合，L是的集合，并且要求。（二）單項選擇題（選擇一個正確答案的代號，填入括號中）1.設命題公式A.恒真的B.恒假的，則G是（D.析取范式）。C.可滿足的2、設集合，A上的關系，則=（）。3、一個公式在等價意義下，下面哪個寫法是唯一的（）。A．析取范式B．合取范式C．主析取范式D．以上答案都不對4、設命題公式G=（PQ），H=P（QP），則G與H的關系是（）。A．GHB．HGC．G=HD．以上都不是5、已知圖G的相鄰矩陣為A.5點，8邊B.6點，7邊6、下列命題正確的是（）。，則G有（）。D.6點，8邊C.5點，7邊A．{}=B．{}=C．{a}{a，b，c}D．{a，b，c}7、設集合A={a，b，c}，A上的關系R={（a，b），（a，c），（b，a），（b，c），（c，a），（c，b），（c，c）}，則R具有關系的（）性質。A．自反B．對稱C．傳遞D．反對稱8、設R為實數集，映射=RR，（x）=-x2+2x-1，則是（）。A．單射而非滿射B．滿射而非單射C．雙射D．既不是單射，也不是滿射9、下列語句中，（）是命題。A．下午有會嗎？B．這朵花多好看呀！C．2是常數。D．請把門關上。10、下面給出的一階邏輯等價式中，（）是錯的。A．x（A（x）B（x））=xA（x）xB（x）B．AxB（x）=x（AB（x））C．x（A（x）B（x））=xA（x）xB（x）D．xA（x）=x（A（x））（三）計算題1、設R和S是集合上的關系，其中，試求：（1）寫出R和S的關系矩陣；（2）計算。2、設A={a，b，c，d}，R1，R2是A上的關系，其中R1={（a，a），（a，b），（b，a），（b，b），（c，c），（c，d），（d，c），（d，d）}，R2={（a，b），（b，a），（a，c），（c，a），（b，c），（c，b），（a，a），（b，b），（c，c）}。（1）畫出R1和R2的關系圖；（2）判斷它們是否為等價關系，是等價關系的求A中各元素的等價類。3、用真值表判斷下列公式是恒真？恒假？可滿足？（1）（PP）Q（2）（PQ）Q（3）（（PQ）（QR））（PR）4、設解釋I為：（1）定義域D={-2，3，6}；（2）F（x）：x3；G（x）：x5。在解釋I下求公式x（F（x）G（x））的真值。5、求下圖所示權圖中從u到v的最短路，畫出最短路并計算它們的權值。V17V312U253V46V21V46、化簡下式：（（ABC）（AB））（（A（BC））A）7、已知A={1，2，3，4，5}，B={1，2，3}，R是A到B的二元關系，并且R={（x，y）|xA且yB且2x+y4}，畫出R的關系圖，并寫出關系矩陣。8、畫出下面偏序集（A，）的哈斯圖，并指出集合A的最小元、最大元、極大元和極小元。其中A={a，b，c，d，e}，={（a，b），（a，c），（a，d），（a，e），（b，e），（c，e），（d，e）}IA。9、求命題公式（PQ）（PQ）的析取范式與合取范式。10、給定解釋I如下：定義域D={2，3}；f（2）f（3）F（2，2）F（2，3）F（3，2）F（3，3）320011求xy（F（x，y）F（f（x），f（y）））。11、設有5個城市v1，v2，v3，v4，v5，任意兩城市之間鐵路造價如下：（以百萬元為單位）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試求出連接5個城市的且造價最低的鐵路網。（四）證明題1、證明等價式。2、利用形式演繹法證明：3、A，B，C為任意的集合，證明：（AB）C=A（BC）蘊涵Q。4、利用一階邏輯的基本等價式，證明：xy（F（x）G（y））=xF（x）yG（y）練習解答（一）填空題1、列舉；描述；A={4，5，6，7}或A={x|3x7}2、{5}；{{5}，{2，5}，{3，5}，{2，3，5}}；83、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；76、{5}；{，{5}}；{1，3，4}7、笛卡爾積（或直乘積）；{（x，y）|xA且yB}；二元關系8、并且（或合取）；或者（或析取）；蘊涵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、點；連接某些不同點對的邊；一對不同點之間最多有一條邊（二）單項選擇題（選擇一個正確答案的代號，填入括號中）1、C6、A2、A7、B3、C8、D4、A9、C5、C10、A（三）計算題1、解：（1）（2）={（1，2），（3，4）}={（1，1），（1，2），（1，3），（2，3），（2，4），（3，4），（4，4）}={（1，1），（3，1），（3，2），（4，3）}={（2，1），（4，3）}2、解：R1和R2的關系圖略。由關系圖可知，R1是等價關系。R1不同的等價類有兩個，即{a，b}和{c，d}。由于R2不是自反的，所以R2不是等價關系。3、解：（1）真值表PQ00011011PPP（PP）Q101010100000因此公式（1）為可滿足。（2）真值表PQ00011011PQ（PQ）（PQ）Q110100100000因此公式（2）為恒假。（3）真值表PQR000001010011100101110111PQQRPR（（PQ）（QR））（PR）11