離散數(shù)學(xué)本科期末復(fù)習(xí)提要

1、離散數(shù)學(xué)本科期末復(fù)習(xí)提要四川電大 周勇2007年5月離散數(shù)學(xué)使用的教材為中央電大出版的離散數(shù)學(xué)（劉敘華等編）和離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)書（虞恩蔚等編）。離散數(shù)學(xué)主要研究離散量結(jié)構(gòu)及相互關(guān)系，使學(xué)生得到良好的數(shù)學(xué)訓(xùn)練，提高學(xué)生抽象思維和邏輯推理能力，為從事計(jì)算機(jī)的應(yīng)用提供必要的描述工具和理論基礎(chǔ)。其先修課程為：高等數(shù)學(xué)、線性代數(shù)；后續(xù)課程為：數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫(kù)、操作系統(tǒng)、計(jì)算機(jī)網(wǎng)絡(luò)等。 課程的主要內(nèi)容1、 集合論部分（集合的基本概念和運(yùn)算、關(guān)系及其性質(zhì)）；2、 數(shù)理邏輯部分（命題邏輯、謂詞邏輯）；3、 圖論部分（圖的基本概念、樹及其性質(zhì)）。4、 布爾代數(shù) 學(xué)習(xí)建議離散數(shù)學(xué)是理論性較強(qiáng)的學(xué)科，學(xué)習(xí)離散數(shù)學(xué)的

2、關(guān)鍵是對(duì)離散數(shù)學(xué)（集合論、數(shù)理邏輯和圖論）有關(guān)基本概念的準(zhǔn)確掌握，對(duì)基本原理及基本運(yùn)算的運(yùn)用，并要多做練習(xí)。 教學(xué)要求的層次各章教學(xué)要求的層次為了解、理解和掌握。了解即能正確判別有關(guān)概念和方法；理解是能正確表達(dá)有關(guān)概念和方法的含義；掌握是在理解的基礎(chǔ)上加以靈活應(yīng)用。一、各章復(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、理解集

3、合、元素、子集、空集、全集、集合的包含、相等、冪集等基本概念。2、掌握集合的表示法和集合的交、并、差、補(bǔ)等基本運(yùn)算。3、掌握集合運(yùn)算基本規(guī)律，證明集合等式的方法。4、了解序偶與迪卡爾積的概念，掌握迪卡爾積的運(yùn)算。本章重點(diǎn)習(xí)題P56，4、6； P1415，3、6、7； P20，5、7。疑難解析1、集合的概念因?yàn)榧系母拍顚W(xué)生在中學(xué)階段已經(jīng)學(xué)過，這里只多了一個(gè)冪集概念，重點(diǎn)對(duì)冪集加以掌握，一是掌握冪集的構(gòu)成，一是掌握冪集元數(shù)為2n。2、集合恒等式的證明通過對(duì)集合恒等式證明的練習(xí)，既可以加深對(duì)集合性質(zhì)的理解與掌握；又可以為第三章命題邏輯中公式的基本等價(jià)式的應(yīng)用打下良好的基礎(chǔ)。實(shí)際上，本章做題是一種基

4、本功訓(xùn)練，尤其要求學(xué)生重視吸收律和重要等價(jià)式在證明中的特殊作用。例題分析例1 設(shè)A，B是兩個(gè)集合，A=1，2，3，B=1，2，則 。解 于是例2 設(shè)，試求： (1)； (2)； (3)； (4)； (5)； (6)。解 (1) (2) (3) (4) (5) (6)例3 試證明 證明 第二章 二元關(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、函數(shù)及其性質(zhì)（單射、滿射、雙射

5、）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)算。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)系做哈斯圖的方法，極大/小元、最大/小元、上/下界、最小上界、最大下界的求法。6、理解函數(shù)概念：函數(shù)、函數(shù)相等、復(fù)合函數(shù)和反函數(shù)。7、理

6、解單射、滿射、雙射等概念，掌握其判別方法。本章重點(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ù)教材中P49上總結(jié)的規(guī)律。這其中對(duì)傳遞性的判定，難度稍大一點(diǎn)，這里要提及兩點(diǎn)：一

7、是不破壞傳遞性定義，可認(rèn)為具有傳遞性。如空關(guān)系具有傳遞性，同時(shí)空關(guān)系具有對(duì)稱性與反對(duì)稱性，但是不具有自反性。另一點(diǎn)是介紹一種判定傳遞性的“跟蹤法”，即若，則。如若，則有，且。、關(guān)系的閉包在理解掌握關(guān)系閉包概念的基礎(chǔ)上，主要掌握閉包的求法。關(guān)鍵是熟記三個(gè)定理的結(jié)論：定理2， ；定理3， ；定理4，推論 。、半序關(guān)系及半序集中特殊元素的確定理解與掌握半序關(guān)系與半序集概念的關(guān)鍵是哈斯圖。哈斯圖畫法掌握了，對(duì)于確定任一子集的最大（小）元，極大（小）元也就容易了。這里要注意，最大（?。┰c極大（?。┰荒茉谧蛹瘍?nèi)確定，而上界與下界可在子集之外的全集中確定，最小上界為所有上界中最小者，最小上界再小也不小于

8、子集中的任一元素，可以與某一元素相等，最大下界也同樣。、映射的概念與映射種類的判定映射的種類主要指單射、滿射、雙射與非單非滿射。判定的方法除定義外，可借助于關(guān)系圖，而實(shí)數(shù)集的子集上的映射也可以利用直角坐標(biāo)系表示進(jìn)行，尤其是對(duì)各種初等函數(shù)。例題分析例1 設(shè)集合，判定下列關(guān)系，哪些是自反的，對(duì)稱的，反對(duì)稱的和傳遞的：解：均不是自反的；R4是對(duì)稱的；R1 ,R2 ,R3 , R4 ,R5是反對(duì)稱的；R1 ,R2 ,R3 , R4 ,R5是傳遞的。例2 設(shè)集合，A上的二元關(guān)系R為 （）寫出R的關(guān)系矩陣，畫出R的關(guān)系圖；（）證明R是A上的半序關(guān)系，畫出其哈斯圖；（）若，且，求B的最大元，最小元，極大元，

9、極小元，最小上界和最大下界。解 （1）R的關(guān)系矩陣為 R的關(guān)系圖略 （2）因?yàn)镽是自反的，反對(duì)稱的和傳遞的，所以R是A上的半序關(guān)系。(A,R)為半序集， (A,R)的哈斯圖如下 。4 。1 。3 。2 。5 (3) 當(dāng)，B的極大元為2，4；極小元為2，5；B無最大元與最小元；B也無上界與下界，更無最小上界與最大下界。 第三章命題邏輯復(fù)習(xí)知識(shí)點(diǎn)、命題與聯(lián)結(jié)詞（否定、析取、合取、蘊(yùn)涵、等價(jià)），復(fù)合命題、命題公式與解釋，真值表，公式分類（恒真、恒假、可滿足），公式的等價(jià)、析取范式、合取范式，極?。ù螅╉?xiàng)，主析取范式、主合取范式 、公式類別的判別方法（真值表法、等值演算法、主析取/合取范式法）、公式的

10、蘊(yùn)涵與邏輯結(jié)果、形式演繹本章重點(diǎn)內(nèi)容：命題與聯(lián)結(jié)詞、公式與解釋、析取范式與合取范式、公式恒真性的判定、形式演繹復(fù)習(xí)要求、理解命題的概念；了解命題聯(lián)結(jié)詞的概念；理解用聯(lián)結(jié)詞產(chǎn)生復(fù)合命題的方法。、理解公式與解釋的概念；掌握求給定公式真值表的方法，用基本等價(jià)式化簡(jiǎn)其他公式，公式在解釋下的真值。、了解析?。ê先。┓妒降母拍?；理解極大（?。╉?xiàng)的概念和主析取（合?。┓妒降母拍?；掌握用基本等價(jià)式或真值表將公式化為主析?。ê先。┓妒降姆椒ā?、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判別公式類型和公式等價(jià)的方法。、理解公式蘊(yùn)涵與邏輯結(jié)果的概念，掌握基本蘊(yùn)涵式。6、掌握形式演繹的證明方法。本章重點(diǎn)習(xí)題

11、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ǔ)不是極小項(xiàng)，一

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

13、解G0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1000000111010101101011111因此 方法2：推導(dǎo)法 （2）求主合取范式方法1：利用上面的真值表為0的有兩行，它們對(duì)應(yīng)的極大項(xiàng)分別為因此，方法2：利用已求出的主析取范式求主合取范式已用去6個(gè)極小項(xiàng)，尚有2個(gè)極小項(xiàng)，即 與 于是 例2 試證明公式為恒真公式。證法一： 見離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)書P60例6（4）的解答。（真值表法）證法二 ： G=（PQ）（QR）（PR） =（PQ）（QR）PR =（PQ）（PR）（QQ）（QR）P）R =（PQP）（PRP）（QRP）R =（1（QRP）R =QRPR =

14、1故G為恒真公式。例3 利用形式演繹法證明 P（QR），SP，Q蘊(yùn)涵SR。證明：（1）SP 規(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è)母拍?；理解用謂

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

16、與蘊(yùn)涵式（一階邏輯中），將給定公式中量詞提到母式之前稱為首標(biāo)。典型例題例1 設(shè)I是如下一個(gè)解釋： F(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求的真值。解 例2 試將一階邏輯公式化成前束范式。解 第五章 群與環(huán) 第六章 格和布爾代數(shù)復(fù)習(xí)要求1. 了解代數(shù)運(yùn)算、代數(shù)系統(tǒng)和子代數(shù)系統(tǒng)等概念。掌握二元運(yùn)算的性質(zhì)：結(jié)合律、交換律、分配律、冪等律、吸收律。掌握求集合上代數(shù)運(yùn)算的單位元(幺元)、0元和逆元的方法。 代數(shù)運(yùn)算的性質(zhì)：x,yA，有xy=xyz，運(yùn)算在A上適合交換律。 x,y,zA，有(xy)zx(yz)，運(yùn)算在A

17、上適合結(jié)合律。x,y,zA，有x*(yz)=(x*y)(x*z) 或(yz)*x=(y*x)(z*x)，運(yùn)算* 對(duì) 可分配，適合分配律。 xA，有xx=x，則運(yùn)算在A上適合冪等律。x,yA, 有x*(xy)=x, x(x*y)=x， 和 * 滿足吸收律。el, (或er)A，對(duì)xA, 有elx=x (xer=x), el(或er)是A的運(yùn)算的左單位元(或右單位元)。若e既是右單位元又是左單位元，就稱其為單位元。存在，q就是*的0元。一側(cè)成立叫右0元或左0元。對(duì)xA，若x-1A, 有x-1x=xx-1=e，x-1是x的逆元。 在非空集合A上，定義了若干代數(shù)運(yùn)算f1,f2,fm, (A, f1,f

18、2,fm)稱為代數(shù)系統(tǒng)。若BA，f1,f2,fm在B上成立，(B, f1,f2,fm)稱為子代數(shù)系統(tǒng)。 2. 了解半群、群和子群等概念。掌握群的基本運(yùn)算律及群的判別方法代數(shù)系統(tǒng)3. 了解循環(huán)群、交換群和置換群的概念，掌握其判別方法。 4.了解群的同態(tài)與同構(gòu)等概念，知道它們的主要性質(zhì)。5. 知道環(huán)的概念。6. 了解格的概念。 設(shè)(L，)是一個(gè)偏序集，如果對(duì)于a,bL，L的子集a,b在L中都有一個(gè)最大下界(記為infa,b)和一個(gè)最小上界(記為supa,b),則稱(L，)是一個(gè)偏序格。子集在L中有上確界和下確界的偏序集，就是格。 在L定義二元運(yùn)算*，o滿足：對(duì)a,b,cL,有 (1) 交換律 a*

19、b=b*a，aob=boa(2) 結(jié)合律 (a*b)*c=a*(b*c) , (aob)oc=ao(boc)(3) 吸收律 a*(aob)=a， ao(a*b)=a則稱(L,*,o )是代數(shù)格. 用代數(shù)的語(yǔ)言，格就是在非空集合上定義了兩個(gè)滿足結(jié)合律、交換律和吸收律的運(yùn)算。 7. 知道有界格、有余格、分配格的概念。 8. 了解布爾代數(shù)概念，掌握其性質(zhì)和運(yùn)算。設(shè)B是一個(gè)至少含有兩個(gè)元素的集合，是定義在B上的兩種運(yùn)算，如果對(duì)a,b,cB，滿足下列公理：H1：ab=ba a+b=b+aH2：a(b+c)=ab+ac a+(bc)=(a+b)(a+c)H3：B中有元素0和1，對(duì)aB,有 a1 = a a

20、+0 = aH4：對(duì)aB,有aB，滿足 aa=0 a+a=1則(B， ，0，1)是一個(gè)布爾代數(shù)記住布爾代數(shù)運(yùn)算的10條算律?！颈静糠种攸c(diǎn)】代數(shù)運(yùn)算及性質(zhì)，群的概念，格和布爾代數(shù)的概念，布爾代數(shù)的運(yùn)算及其性質(zhì)例題：例1 試判斷(Z,)是否為格？其中是數(shù)的小于或等于關(guān)系. 解 顯然(Z,)是一個(gè)偏序集. 又，x, y的最小上界為, x, y的最大下界為，皆為整數(shù)，仍然屬于Z. 故對(duì)Z的任意子集，在Z中都有上確界和下確界. 即(Z,)是格. 例2 設(shè)()是布爾代數(shù)，證明()是B的子布爾代數(shù)，而且是布爾代數(shù)，其中. 證明 對(duì)于集合T中的元素作運(yùn)算見表83. 表83 T的元素運(yùn)算表0aa10aa1100

21、aaa0000001aaa1aa0a0Aaaaa1aaa00aaaa1111110aa110由B是布爾代數(shù)可知，從表83得到T對(duì)運(yùn)算， 是封閉的，所以()是子布爾代數(shù). 由定理11知()也是布爾代數(shù). 例3單項(xiàng)選擇題 1. 下列圖(如圖81)表示的偏序集中，是格的為( )(A) (B) (C) (D) 圖81答案：(C)解答：所給(A),(B),(D)的偏序集，都有兩個(gè)極大元，不存在上確界，都不是格，只有(C)的偏序集有上確界和下確界，是格. 故選擇(C)正確. 2. 設(shè)是布爾代數(shù)，則下式不成立的是( )答案：(D)解答：因?yàn)锽是偏序集， . 故選擇(D)正確. 3. 布爾代數(shù)式=( )答案：

22、(B)解答：. 故選擇(B)正確. 例4填空題 1. 非空集合L，其上定義二元運(yùn)算和，如果 是交換群，(L,)是 ，而且 滿足分配律，則L對(duì)二元運(yùn)算和構(gòu)成環(huán). 答案：(L,)；半群；二元運(yùn)算對(duì)運(yùn)算解答：見環(huán)的定義. 2. 設(shè)L是一個(gè)集合，和是L上兩個(gè)二元運(yùn)算，如果這兩個(gè)二元運(yùn)算滿足 律， 律和 律，則(L,)是格. 答案：交換律；結(jié)合律；吸收律解答：見代數(shù)格的定義. 3. 在布爾代數(shù)中，有成立. 則該式的對(duì)偶式 也一定成立. 答案：解答：見對(duì)偶原理，知是原式的對(duì)偶式，也是成立的. 第七章 圖論復(fù)習(xí)知識(shí)點(diǎn)1、圖、完全圖、子圖、母圖、支撐子圖、圖的同構(gòu)2、關(guān)聯(lián)矩陣、相鄰矩陣3、權(quán)圖、路、最短路徑，

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

24、，2。疑難解析 1.本章的概念較多，學(xué)習(xí)時(shí)需要認(rèn)真比較各概念的含義，如：圖、子圖、有向圖、權(quán)圖；樹、支撐樹、二叉樹、有向樹；路、簡(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)和。3、權(quán)圖中的最優(yōu)支撐樹 權(quán)圖中的最優(yōu)支撐樹是圖中所帶權(quán)和最小的支撐樹，使用克魯斯卡爾（Kruskal）算法。典型例題例1 在具有n個(gè)頂點(diǎn)的完全圖Kn中刪去多少條邊才能得到樹？解：n個(gè)頂點(diǎn)的完全圖Kn中共有n（n-1）/2條邊，n個(gè)頂點(diǎn)的樹應(yīng)有

25、n-1條邊，于是，刪去的邊有：n（n-1）/2-（n-1）=（n-1）（n-2）/2例2 求下面有限圖中點(diǎn)u到各點(diǎn)間的最短路。（圖上數(shù)字見教材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, u5)或路 (u, u4, u3 , u7 , u2 , u5)u u6 , d(u, u6)=13, 路(u, u1,

26、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) 二、考核說明本課程的考核實(shí)行形成性考核和終結(jié)性考核的形式。形成性考核占總成績(jī)的20%，以課程作業(yè)的形式進(jìn)行（共三次，由中央電大統(tǒng)一布置）；終結(jié)性考核即期末考試，占總成績(jī)的80%?？偝煽?jī)?yōu)?00分，60分及格。期末考試實(shí)行統(tǒng)一閉卷考核，試卷滿分為100。由四川電大統(tǒng)一命題，統(tǒng)一評(píng)分標(biāo)準(zhǔn)，統(tǒng)一考試時(shí)間（考試時(shí)間為120分

27、鐘）。1、試題類型試題類型有填空題（分?jǐn)?shù)約占15%）、單項(xiàng)選擇題（分?jǐn)?shù)約占10%）、計(jì)算題（分?jǐn)?shù)約占55%）和證明題（分?jǐn)?shù)約占20%）。填空題和單項(xiàng)選擇題主要涉及基本概念、基本理論，重要性質(zhì)和結(jié)論、公式及其簡(jiǎn)單計(jì)算。計(jì)算題主要考核學(xué)生的基本運(yùn)算技能，要求書寫計(jì)算、推論過程或理由。證明題主要考查應(yīng)用概念、性質(zhì)、定理及主要結(jié)論進(jìn)行邏輯推理的能力，要求寫出推理過程。2、考核試卷題量分配試卷題量在各部分的分配是：集合論約占30%，數(shù)理邏輯約占30%，圖論約占20%，布爾代數(shù)約占20。具體課程考核情況見課程考核說明。附錄：試題類型及規(guī)范解答舉例填空題1. 設(shè)R是集合A上的二元關(guān)系，如果關(guān)系R同時(shí)具有 性

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

29、b），（d，d），則R2是R1的（ ）閉包。A自反 B對(duì)稱 C傳遞 D以上都不是3. 設(shè)G是由5個(gè)頂點(diǎn)組成的完全圖，則從G中刪去（ ）條邊可以得到樹。A4 B5 C6 D10計(jì)算題1. 化簡(jiǎn)下式：（A-B-C）（A-B）C）（AB-C）（ABC）2. 通過求主析取范式判斷下列命題公式是否等值。（1）（PQ）（PQR）；（2）（P（QR）（Q（PR）；3. 求圖中A到其余各頂點(diǎn)的最短路徑，并寫出它們的權(quán)。 B 7 C 1 2 A 2 5 3 D4 6 E 1 F證明題1. 利用基本等價(jià)式證明下面命題公式為恒真公式。（PQ）（QR）（PR）2. 用形式演繹法證明：PQ， RS，PR 蘊(yùn)涵QS。試題

30、答案及評(píng)分標(biāo)準(zhǔn)填空題1、 自反；傳遞2、 8；真值表；13、 無回路；二叉樹單項(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為全集 =（AB）（AB） = A（BB） = AE = A 2. 解： （PQ）（PQR）（PQ（RR）（PQR）（PQR）（PQR）（PQR） m6m7m3 m3m6m7 （P（QR）（Q（PR）（PQ） （QR）（PPR）（P Q R） （分配律）（PQ（RR） （

31、PP）QR）（P Q R）（PQR） （PQR） （PQR）（PQR）（P Q R） m6m7m3m7m3 m3m6m7 由此可見 （PQ）（PQR） （P（QR）（Q（PR）3. 解： A到B的最短路徑為AB，權(quán)為1；A到E的最短路徑為ABE，權(quán)為3；A到F的最短路徑為ABEF，權(quán)為4；A到C的最短路徑為ABEFC，權(quán)為7；A到D的最短路徑為ABEFCD，權(quán)為9。證明題1. 證明： （PQ）（QR）（PR） （PQ）（QR）（PR） （PQ）（QR）（PR）（PQ）（QR）PR （PQ）P ）（QR）R）（1（QP ）（QR）1） QPQR （QQ） P R 1 P R 1 2. 證明：（1

32、） PR 規(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） QS 規(guī)則Q ，根據(jù)（7） 三、 綜合練習(xí)及解答（一）填空題1、集合的表示方法有兩種： 法和 法。請(qǐng)把“大于3而小于或等于7的整數(shù)集合”用任一種集合的表示方法表示出來A= 。2、 A，B是兩個(gè)集合，A=1，2，3，4，B=2，3，5，則B-A= ，r（B）-r（A）= ，r（B）的元素個(gè)數(shù)為 。3、 設(shè)，則從A到B的所有映射是 。4、 設(shè)命題公式，則使公式G為假的解釋是 、 和

33、 。5、設(shè)G是完全二叉樹，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= ，r（A）r（C）= ，C= 。7、設(shè)A和B是任意兩個(gè)集合，若序偶的第一個(gè)元素是A的一個(gè)元素，第二個(gè)元素是B的一個(gè)元素，則所有這樣的序偶集合稱為集合A和B的 ，記作AB，即AB= 。AB的子集R稱為A，B上的 。8、將幾個(gè)命題聯(lián)結(jié)起來，形成一個(gè)復(fù)合命題的邏輯聯(lián)結(jié)詞主要有否定、 、 、 和等值。9、表達(dá)式x$yL（x，y）中謂詞的定義域是a，b，c，將其中的量詞消除，寫成與之等價(jià)的命題公式為 。10、一個(gè)無向圖表示為G=（

34、P，L），其中P是 的集合，L是 的集合，并且要求 。（二）單項(xiàng)選擇題（選擇一個(gè)正確答案的代號(hào)，填入括號(hào)中）1. 設(shè)命題公式，則G是（ ）。A.恒真的 B.恒假的 C.可滿足的 D.析取范式2、設(shè)集合，A上的關(guān)系，則=（ ）。 3、一個(gè)公式在等價(jià)意義下，下面哪個(gè)寫法是唯一的（ ）。A析取范式 B合取范式 C主析取范式 D以上答案都不對(duì)4、設(shè)命題公式G=（PQ），H=P（QP），則G與H的關(guān)系是（ ）。AGH BHG CG=H D以上都不是5、已知圖G的相鄰矩陣為，則G有（ ）。 A.5點(diǎn)，8邊 B. 6點(diǎn)，7邊 C. 5點(diǎn)，7邊 D. 6點(diǎn)，8邊6、下列命題正確的是（ ）。Aff=f Bff=

35、f Caa，b，c Dfa，b，c7、設(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ù)集，映射s=RR，s（x）= -x2+2x-1，則s是（ ）。A單射而非滿射 B滿射而非單射 C雙射 D既不是單射，也不是滿射9、下列語(yǔ)句中，（ ）是命題。A下午有會(huì)嗎？ B這朵花多好看呀！ C2是常數(shù)。 D請(qǐng)把門關(guān)上。10、下面給出的一階邏輯等價(jià)式中，（ ）是錯(cuò)的。A x（A（x）B（x）=xA（x）xB（x）B AxB（x）=x （AB（x）C $x（A（x）B（

36、x）=$xA（x）$xB（x）D xA（x）=$x（A（x）（三）計(jì)算題1、設(shè)R和S是集合上的關(guān)系，其中，試求： （1）寫出R和S 的關(guān)系矩陣；（2）計(jì)算。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，d），R2=（a，b），（b，a），（a，c），（c，a），（b，c），（c，b），（a，a），（b，b），（c，c）。（1） 畫出R1和R2的關(guān)系圖；（2） 判斷它們是否為等價(jià)關(guān)系，是等價(jià)關(guān)系的求A中各元素的等價(jià)類。3、 用真值表判斷下列公式是恒真？恒假？可滿足？（1）（PP）Q（2）（P

37、Q）Q（3）（PQ）（QR）（PR）4、 設(shè)解釋I為：（1） 定義域D=-2，3，6；（2） F（x）：x3；G（x）：x5。 在解釋I下求公式$x（F（x）G（x）的真值。5、 求下圖所示權(quán)圖中從u到v的最短路，畫出最短路并計(jì)算它們的權(quán)值。 V1 7 V31 2 U 2 5 3 V4 6 V2 1 V4 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，畫出R的關(guān)系圖，并寫出關(guān)系矩陣。8、 畫出下面偏序集（A，）的哈斯圖，并指出集合A的最小元、最大元、極大元和極小元。其

38、中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） 3 2 0 0 1 1求xy（F（x，y）F（f（x），f（y）。11、設(shè)有5個(gè)城市v1，v2，v3，v4，v5，任意兩城市之間鐵路造價(jià)如下：（以百萬元為單位）w（v1，v2）=4， w（v1，v3）=7， w（v1，v4）=16， w（v1，v5）=10， w（v2，v3）=13， w（v2，v4）=8，

39、w（v2，v5）=17， w（v3，v4）=3， w（v3，v5，）=10， w（v4，v5）=12試求出連接5個(gè)城市的且造價(jià)最低的鐵路網(wǎng)。（四）證明題1、證明等價(jià)式。 2、 利用形式演繹法證明：蘊(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|3x72、5；5，2，5，3，5，2，3，5；83、s1=（a，1），（b，1）；s2=（a，2），（b，2）；s3=（a，1），（b，2）；s4=（a，2），（b，1）4、（1，0，

40、1）； （1，1，1）； （1，0，0）5、 28； 76、5；f，5；1，3，47、笛卡爾積（或直乘積）；（x，y）|xA且yB；二元關(guān)系8、并且（或合?。?；或者（或析取）；蘊(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、C6、A 7、B 8、D 9、C 10、A（三）計(jì)算題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的關(guān)系圖略。 由關(guān)系圖