《離散數(shù)學(xué)(第三版)》方世昌的期末復(fù)習(xí)知識(shí)點(diǎn)總結(jié)含例題

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é)過，這里只多了一個(gè)幕集概念，重點(diǎn)對(duì)幕集加以掌握，一是掌握幕集的構(gòu)成，一是掌握幕集元數(shù)為2no2、集合恒等式的證明通過對(duì)集合恒等式證明的練習(xí)，既可以加深對(duì)集合性質(zhì)的理解與掌握；又可以為第三章命題邏輯中公式的基本等價(jià)式的應(yīng)用打下良好的基礎(chǔ)。實(shí)際上，本章做題是一種基本功訓(xùn)練，尤其要求學(xué)生重視吸收律和重要等價(jià)式在A B A B證明中的特殊作用。例題分析例 1 設(shè) A , B 是兩個(gè)集合，A=1 , 2, 3, B=1 , 2，則 (A)(B)解 (A) ,1,2,3,1,2,1,3,2,3,1,2,3(B) ,1,2,1,2于是 (A) (B

3、) 3, 1,3, 2,3, 1,2,3 例 2 設(shè) A a,b, a,b , ，試求：(1)A a,b ； (2) A ； (3)A ；(4) a,bA； (5)A； (6) A 。解 (1) A a,ba,b ,(2) AA (3) Aa,b,a,b(4) a,b A(5) A(6)A例 3 試證明 AB A BABA B證明A BABABAA BBAAB A AB B BABABAB A B第二章 二元關(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、 偏

4、序關(guān)系與哈斯圖（Hasse）、極大/小元、最大/小元、上/下界、最小上界、最大下界7、函數(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)算。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)系概念的

6、加深理解與掌握，又是關(guān)系的閉包、等價(jià)關(guān)系、半序關(guān) 系的基礎(chǔ)。對(duì)于四種性質(zhì)的判定，可以依據(jù)教材中 P49 上總結(jié)的規(guī)律。這其中對(duì)傳遞性的 判定，難度稍大一點(diǎn)，這里要提及兩點(diǎn)：一是不破壞傳遞性定義，可認(rèn)為具有傳遞性。如 空關(guān)系具有傳遞性，同時(shí)空關(guān)系具有對(duì)稱性與反對(duì)稱性，但是不具有自反性。另一點(diǎn)是介 紹一種判定傳遞性的 “跟蹤法” ，即若 a1,a2 R, a2,a3 R, , ai 1,ai R ，則 a1, ai R。如若 a, b R, b, a R，則有 a,a R，且 b,b R。3、關(guān)系的閉包在理解掌握關(guān)系閉包概念的基礎(chǔ)上，主要掌握閉包的求法。關(guān)鍵是熟記三個(gè)定理的結(jié)n論：定理 2， r

7、R R IA ；定理 3， s R R R 1；定理 4，推論 t RRi 。i14、半序關(guān)系及半序集中特殊元素的確定理解與掌握半序關(guān)系與半序集概念的關(guān)鍵是哈斯圖。哈斯圖畫法掌握了，對(duì)于確定任 一子集的最大 （?。┰?，極大（?。┰簿腿菀琢?。 這里要注意， 最大（?。┰c極大 （小） 元只能在子集內(nèi)確定，而上界與下界可在子集之外的全集中確定，最小上界為所有上界中最小者，最小上界再小也不小于子集中的任一元素，可以與某一元素相等，最大下界也同 樣。5、映射的概念與映射種類的判定映射的種類主要指單射、滿射、雙射與非單非滿射。判定的方法除定義外，可借助于 關(guān)系圖，而實(shí)數(shù)集的子集上的映射也可以利用直角坐

8、標(biāo)系表示進(jìn)行，尤其是對(duì)各種初等函 數(shù)。 例題分析 例1 設(shè)集合 A a,b,c,d ，判定下列關(guān)系，哪些是自反的，對(duì)稱的，反對(duì)稱的和傳遞的：R1 a,a, b,a R2 a,a , b,c , d,a R3 c,d R4 a,a, b,b , c,cR5 a,c, b,d解：均不是自反的；R4是對(duì)稱的；R1 ,R2 ,R3 , R4 ,R5是反對(duì)稱的；R1 ,R2 ,R3 , R4 ,R5是傳遞的。 例2設(shè)集合A 1,234,5，A上的二元關(guān)系 R為R 1,1 , 2,2 , 3,3 , 3,4, 4,4, 5,3,5,4,5,5(1) 寫出R的關(guān)系矩陣，畫出 R的關(guān)系圖；(2) 證明R是A上

9、的半序關(guān)系，畫出其哈斯圖；(3) 若B A，且B 2,3,4,5，求B的最大元，最小元，極大元，極小元，最小上界 和最大下界。解(1) R的關(guān)系矩陣為1000001000M R 00110R 的關(guān)系圖略0001000111( 2)因?yàn)?R 是自反的， 反對(duì)稱的和傳遞的， 所以 R 是 A 上的半序關(guān)系。 (A,R) 為半序集，(A,R) 的哈斯圖如下。4。1。3。2。5（3）當(dāng)B 2,3,4,5 , B的極大元為2, 4;極小元為2, 5; B無最大元與最小元；B也無上界與下界，更無最小上界與最大下界。第三章命題邏輯復(fù)習(xí)知識(shí)點(diǎn)1、命題與聯(lián)結(jié)詞（否定、析取、合取、蘊(yùn)涵、等價(jià)），復(fù)合命題2、命題公

10、式與解釋，真值表，公式分類（恒真、恒假、可滿足），公式的等價(jià)3、析取范式、合取范式，極小（大）項(xiàng)，主析取范式、主合取范式4、公式類別的判別方法（真值表法、等值演算法、主析取/合取范式法）5、公式的蘊(yùn)涵與邏輯結(jié)果6、形式演繹本章重點(diǎn)內(nèi)容：命題與聯(lián)結(jié)詞、公式與解釋、析取范式與合取范式、公式恒真性的判定、形式演繹復(fù)習(xí)要求1、理解命題的概念；了解命題聯(lián)結(jié)詞的概念；理解用聯(lián)結(jié)詞產(chǎn)生復(fù)合命題的方法。2、理解公式與解釋的概念； 掌握求給定公式真值表的方法，用基本等價(jià)式化簡(jiǎn)其他公式，公式在解釋下的真值。3、了解析?。ê先。┓妒降母拍睿焕斫鈽O大（?。╉?xiàng)的概念和主析?。ê先。┓妒降母拍?；掌握用基本等價(jià)式或真值表將

11、公式化為主析取（合?。┓妒降姆椒ā?、掌握利用真值表、等值演算法和主析取/ 合取范式的唯一性判別公式類型和公式等價(jià)的方法。5、理解公式蘊(yùn)涵與邏輯結(jié)果的概念，掌握基本蘊(yùn)涵式。6、掌握形式演繹的證明方法。本章重點(diǎn)習(xí)題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)法，即利用基

12、本等價(jià)式推導(dǎo)出結(jié)果為1，或者利用恒真（恒假）判定定理：公式G是恒真的（恒假的）當(dāng)且僅當(dāng)?shù)葍r(jià)于它的合取范式（析取范式）中，每個(gè)子句（短語(yǔ)）均至 少包含一個(gè)原子及其否定。這里要求的析取范式中所含有的每個(gè)短語(yǔ)不是極小項(xiàng)，一定要與求主析取范式相區(qū) 別，對(duì)于合取范式也同樣。2、范式求范式，包括求析取范式、合取范式、主析取范式和主合取范式。關(guān)鍵有兩點(diǎn)：一是 準(zhǔn)確理解掌握定義；另一是巧妙使用基本等價(jià)式中的分配律、同一律和互補(bǔ)律，結(jié)果的前 一步適當(dāng)使用等幕律，使相同的短語(yǔ)（或子句）只保留一個(gè)。另外，由已經(jīng)得到的主析?。ê先。┓妒剑鶕?jù) G G 1,G G原理，參閱離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)書P71例15,可以求得主合取

13、（析?。┓妒?。3、形式演繹法掌握形式演繹進(jìn)行邏輯推理時(shí)，一是要理解并掌握14個(gè)基本蘊(yùn)涵式，二是會(huì)使用三個(gè)規(guī)則：規(guī)則 P、規(guī)則Q和規(guī)則D，需要進(jìn)行一定的練習(xí)。例題分析例1求G P Q RP的主析取范式與主合取范式。解（1 ）求主析取范式，方法1 ：利用真值表求解P Q RP QP QRG0 0 00100 0 10010 1 00100 1 10011 0 00111 0 10011 1 01111 1 1111因此GPQRP QRPQRPQ R P QRP Q R方法2:推導(dǎo)法GPQ RRPP QRPPQ RPPRQRPPRQQQ RPPPQ QRRPQ RPQRPQRPQ RPQ R PQR

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

15、（ P Q P）（PRP）（QR P ) R=( 1 ( Q RP）R= Q R P R=1故 G 為恒真公式。例3 利用形式演繹法證明 P（QR），S P，Q 蘊(yùn)涵S R 。證明：1）SP規(guī)則P2）S規(guī)則D3）P規(guī)則Q，根據(jù)（1），（ 2）4）P（ Q R）規(guī)則P5）QR規(guī)則Q，根據(jù)（3），（ 4 ）6）Q規(guī)則P7）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)容：謂詞與量詞、公式

16、與解釋、前束范式 復(fù)習(xí)要求 1、理解謂詞、量詞、個(gè)體詞、個(gè)體域、變?cè)母拍?；理解用謂詞、量詞、邏輯聯(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、公式與解釋I中的數(shù)能將一階邏輯公式表達(dá)式中的量詞消除，寫成與之等價(jià)的公式，然后

17、將解釋 值代入公式，求出真值。3、前束范式在充分理解掌握前束范式概念的基礎(chǔ)上，利用改名規(guī)則、基本等價(jià)式與蘊(yùn)涵式（一階 邏輯中），將給定公式中量詞提到母式之前稱為首標(biāo)。典型例題例1設(shè)I是如下一個(gè)解釋：D 2,3FF(3)P(2)P(3)Q(2,2)Q(2,3)Q(3,2)Q(3,3)3201 1101求x yPxQFx ,y的真值。解x yP xQ F x , yx P xQ F x ,2P xQ F x ,3P 2 QF 2 ,2P 2 QF 2 ,3P3 QF 3 ,2P 3 QF 3 ,30 0 (0 1 11 11例2試將一階邏輯公式化成前束范式。GxyP x,yyQ yRxxyP x,

18、yy Q yRxxyP x,yz Q zRxxy zP x,yQzRx第五章 圖論 復(fù)習(xí)知識(shí)點(diǎn) 1、圖、完全圖、子圖、母圖、支撐子圖、圖的同構(gòu)2、關(guān)聯(lián)矩陣、相鄰矩陣3、權(quán)圖、路、最短路徑，迪克斯特拉算法(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、理解樹、二叉樹與支撐

19、樹的有關(guān)概念；掌握二叉樹的三種遍歷方法，用Kruskal 算法求權(quán)圖中最小樹的方法。5、理解有向圖與有向樹的概念。 本章重點(diǎn)習(xí)題 P221，2；P225，1；P231， 2，3；P239，5；P242，1，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)圖

20、中的最優(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)有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)uU2 ,d(u, U2)=9,路(u, U4, U3, U7, U2)uU3 ,d(u, U3)=5,路(u, U4, U3 ,)uU4 ,d(u, U4)=3

21、,路(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)二、考核說明本課程的考核實(shí)行形成性考核和終結(jié)性考核的形式。形成性考核占總成績(jī)的 20%,以課程作業(yè)的形式進(jìn)行(共三次，由中央電大統(tǒng)一布置)；終結(jié)性考核

22、即期末考試，占總成 績(jī)的80%?？偝煽?jī)?yōu)?00分，60分及格。期末考試實(shí)行全國(guó)統(tǒng)一閉卷考核，試卷滿分為100。由中央電大統(tǒng)一命題，統(tǒng)一評(píng)分標(biāo)準(zhǔn)，統(tǒng)一考試時(shí)間(考試時(shí)間為120分鐘)。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)算技能，要求書寫計(jì)算、推論過程或理由。證明題主要考查應(yīng)用概念、性質(zhì)、定理及主要結(jié)論進(jìn)行邏輯推理的能力，要求寫出推理過程。2、考核試卷題量分配試卷題量在各部分的分配是：集合論約占40

23、%，數(shù)理邏輯約占40%，圖論約占20%。具體課程考核情況見課程考核說明。附錄：試題類型及規(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是樹。如果根樹T的每個(gè)點(diǎn)v最多有兩棵子樹，則稱T為單項(xiàng)選擇題（選擇一個(gè)正確答案的代號(hào)，填入括號(hào)中）1.由集合運(yùn)算定義，下列各式正確的有（）。2.3.B.X X Y C.X X YD.Y X Y設(shè)R1

24、, R2是集合A=a , b, c, d上的兩個(gè)關(guān)系，其中c),( d, d) , R2= (a, a),(b, b) ,( b,R2是Ri的（A 自反）閉包。B.對(duì)稱C .傳遞R1= (a, a),(b, b) ,(b,c),( c, b),( d, d) ，則D .以上都不是設(shè)G是由5個(gè)頂點(diǎn)組成的完全圖,則從 G中刪去（）條邊可以得到樹。B. 5D. 10計(jì)算題1. 化簡(jiǎn)下式:(ABC)( A B) C)(A B C)(A2. 通過求主析取范式判斷下列命題公式是否等值。(1) ( P Q)( P Q R)；(2) ( P (Q R)(Q ( PR)；3. 求圖中A到其余各頂點(diǎn)的最短路徑，并

25、寫出它們的權(quán)。B7C1 2E1F證明題1. 利用基本等價(jià)式證明下面命題公式為恒真公式。(P Q)(Q R)(P R)2. 用形式演繹法證明：P Q, R S, PR 蘊(yùn)涵Q試題答案及評(píng)分標(biāo)準(zhǔn)填空題1、自反；傳遞2、8 ;真值表；13、無回路；二叉樹單項(xiàng)選擇題(選擇一個(gè)正確答案的代號(hào)，填入括號(hào)中)1、A2、 B3、C計(jì)算題1. 解：(ABC)( A B) C)(A B C)(A=(A B C)(A B C)(A B C)=(A B)( C C)( A B)( CSoB C)(A B C)C)=(A B) E)( A B) E)E為全集=（A B） （ A B）= A （ B B）= AE= A2

26、. 解：P Q ） （ P Q R）P Q （ R R） （ P Q R）P Q R） （ P Q R） （ P Q R）m6 m7 m3m3 m6m7由此可見Q）PQR）P （ Q R）Q （ P R）P（QR） （ Q（ P R）PQ）（ Q R） （P P R ）（P QR）（分配律）PQ（R R ）（ P P）QR）（PQ R）PQR） （ P QR） （ PQR） （PQR） （P Q R ）m3 m6 m7m6 m7m3m7m33. 解：A 到 B 的最短路徑為 AB ，權(quán)為 1；A 到 E 的最短路徑為 ABE ，權(quán)為 3 ；A 到 F 的最短路徑為 ABEF ，權(quán)為 4；A 到

27、 C 的最短路徑為 ABEFC ，權(quán)為 7；A 到 D 的最短路徑為 ABEFCD ，權(quán)為 9。證明題1. 證明：（PQ）（QR）（ P R）（P Q）（Q R ）（ P R ）（PQ） （Q R ） （ P R）PQ）（QR）PR（ P Q） P ） （ Q R） R）(1( Q P )Q P Q R(Q Q) PR1 P R12. 證明：(1) P R(2) RP(3) P Q(4) RQ(5) QR(6) R S(7) QS(8) Q S(Q R)1)規(guī)則P規(guī)則Q ,根據(jù)(1)規(guī)則P規(guī)則Q,根據(jù)(2)( 3)規(guī)則Q,根據(jù)(4)規(guī)則P規(guī)則Q,根據(jù)(5)( 6)規(guī)則Q ,根據(jù)(7)三、綜合練

28、習(xí)及解答(一) 填空題1、 集合的表示方法有兩種： 法和法。請(qǐng)把“大于 3而小于或等于7的整數(shù)集合”用任一種集合的表示方法表示出來A= 。2、 A，B 是兩個(gè)集合，A=1，2，3，4，B=2，3，5，則 B-A=，( B)(A) =，( B)的元素個(gè)數(shù)為。3、設(shè)A a,b, B 1,2，則從A到B的所有映射是4、設(shè)命題公式G P (Q R)，則使公式G為假的解釋是 和。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，求 A B=,(A )( C) =, C=。7、設(shè)A和B是任意兩個(gè)集

29、合，若序偶的第一個(gè)元素是A的一個(gè)元素，第二個(gè)元素是B的一個(gè)元素，則所有這樣的序偶集合稱為集合A和B的，記作A B，即A B=。A B的子集R稱為A，B上的。&將幾個(gè)命題聯(lián)結(jié)起來，形成一個(gè)復(fù)合命題的邏輯聯(lián)結(jié)詞主要有否定、和等值。9、表達(dá)式 x yL (x，y)中謂詞的定義域是a，b, c，將其中的量詞消除，寫成與之等 價(jià)的命題公式為10、一個(gè)無向圖表示為 G=( P，L)，其中P是的集合，L是的集合，并且要求。(二) 單項(xiàng)選擇題(選擇一個(gè)正確答案的代號(hào)，填入括號(hào)中)1. 設(shè)命題公式G (P P) (Q R) P)，則G是()。A.恒真的B.恒假的C可滿足的D.析取范式22、設(shè)集合 A a,b,c

30、，A 上的關(guān)系 R (a,a),(a,b),(b,c)，貝U R =()。(A)(a,a),(a,b),(a,c);(B)( a, b), (a, c), (b, c);(C)( a,b),(a,c),(b,b);(D)(a,a),(a,b),(c,c).3、一個(gè)公式在等價(jià)意義下，下面哪個(gè)寫法是唯一的()。A 析取范式B .合取范式C.主析取范式D.以上答案都不對(duì)4、設(shè)命題公式G=(P Q), H=P(QP),貝y G與H的關(guān)系是()。A. G HB. H GC.G=HD .以上都不是0 10111 00015、已知圖G的相鄰矩陣為 00011，則G有()。1 01011 1110A.5點(diǎn)，8

31、邊B. 6點(diǎn)，7邊C. 5點(diǎn)，7邊D. 6點(diǎn)，8邊6、下列命題正確的是（）。7、8、9、A. =B. =C a a，b，cD . a , b, c設(shè)集合 A=a ，a),( c, b)A 自反設(shè) R 為實(shí)數(shù)集,b，c , A 上的關(guān)系 R= ( a, b),( a,（c, c） ，貝U R具有關(guān)系的（B.對(duì)稱C.傳遞映射A .單射而非滿射列語(yǔ)句中,（A .下午有會(huì)嗎?c),( b, a),( b, c),( c,）性質(zhì)。D.反對(duì)稱=R R,(x) = -x2+2x-1 ,貝B .滿射而非單射C.雙射是命題。B .這朵花多好看呀！是（）。D .既不是單射,也不是滿射C. 2是常數(shù)。D .請(qǐng)把門關(guān)

32、上。10、下面給出的一階邏輯等價(jià)式中,（）是錯(cuò)的。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)三）計(jì)算題1、設(shè)R和S是集合A 1,2,3,4上的關(guān)系，其中(1,1),(1,3),(2,3),(3,4)(1,2),(2,3),(2,4),(4,4),試求：（1）寫出R和S的關(guān)系矩陣;2)計(jì)算 R S, R S, R 1, S 1 R 12、設(shè)A=a , b, c, d, Ri, R2是A上的關(guān)系，其中R1= （ a，a），（ a，b），b，b），（

33、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）畫出Ri和R2的關(guān)系圖；（2） 判斷它們是否為等價(jià)關(guān)系，是等價(jià)關(guān)系的求A中各元素的等價(jià)類。3、用真值表判斷下列公式是恒真?恒假?可滿足?1)(PP)Q2)(PQ)Q3)(PQ)( Q R)(P R)4、設(shè)解釋 I 為：(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的最短路，

34、畫出最短路并計(jì)算它們的權(quán)值。6V44V26、化簡(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）|x A且y B且2 x+y 4，畫出R的關(guān)系圖，并寫出關(guān)系矩陣。& 畫出下面偏序集（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）

35、f （ 3）F （2，2）F （2，3） F （ 3，2）F （3，3）320011求 x y （ 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， w （ V2，V5） =17， W （ V3， V4） =3， W （ V3，V5，）= 10，w ( V4， V5) =12試求出連接 5 個(gè)城市的且造價(jià)最低的鐵路網(wǎng)。（四）證

36、明題1、證明等價(jià)式 （ P （ Q R） （Q R） （P R） R 。R, T 蘊(yùn)涵 Q。2、 利用形式演繹法證明： P Q, P R, S T, S3、A，B，C 為任意的集合，證明：（ A B） C=A （B C）4、利用一階邏輯的基本等價(jià)式，證明：x y（F（x） G（y） = xF（ x） yG（y）練習(xí)解答（一）填空題1、列舉；描述； A=4 ，5，6，7或 A=x|3 x 72、5 ；5 ，2，5 ，3，5，2，3，5 ；83、1=（ a， 1），（ b，1） ； 2= (a，2），（ b，2) ； 3=4=（ a， 2），（ b，1）4、（1，0， 1）； （1，1，1）； （

37、1，0，0）5、28；76、5 ； ，5 ； 1，3，4A且y B ；-V* R二元關(guān)系7、笛卡爾積（或直乘積）； ( x ， y ) |x8、并且（或合?。换蛘撸ɑ蛭鋈。?；蘊(yùn)涵9、（L（a， a） L（ a，b）L（a，c）（L（b，a）L（b，b）a）L （c，b） L（ c，c）a，1），（ b， 2）；L（ b，c） （L（c，5、C10、A10、點(diǎn)；連接某些不同點(diǎn)對(duì)的邊；一對(duì)不同點(diǎn)之間最多有一條邊 （二）單項(xiàng)選擇題（選擇一個(gè)正確答案的代號(hào)，填入括號(hào)中） 1、C2、 A3、C4、A6、A7、 B8、D9、C（三）計(jì)算題1、解：（ 1）1 01001000 0100011MrMs0 00100000 0000001(2)R S=(1,2),(3, 4) R S= (1,1),( 1 , 2),( 1, 3),( 2, 3),( 2, 4),(3, 4),( 4, 4) 1R = (1, 1),( 3, 1),( 3, 2),( 4, 3) S 1 R 1= (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 QPP P(P P) Q0 01010 11001 00011 100