離散復(fù)習(xí)附部分答案.doc

一、范式 1、的主合取范式為 。2、 利用主析取范式，求公式的類型。 解、 它無(wú)成真賦值，所以為矛盾式。3、 求命題公式(PQ)(PR)的主合取范式。 解：(PQ)(PR)（(PQ)(PR)）（(PR)(PQ)）（(PQ)(PR)）（(PR)(PQ)）(PQ)(PR)(PR)（QP）（QR）(PQR)(PQR)（PQR）（PQR）M1M3M4M54、 設(shè)命題公式G = (PQ)(Q(PR), 求G的主析取范式。 G = (PQ)(Q(PR)= (PQ)(Q(PR)= (PQ)(Q(PR)= (PQ)(QP)(QR)= (PQR)(PQR)(PQR)(PQR)(PQR)(PQR)= (PQR)(PQR)(PQR)(PQR)(PQR)= m3m4m5m6m7 = S(3, 4, 5, 6, 7).5、 通過(guò)求主析取范式判斷下列命題公式是否等價(jià)：(1) G = (PQ)(PQR) (2) H = (P(QR)(Q(PR) G(PQ)(PQR)(PQR)(PQR)(PQR)m6m7m3 (3, 6, 7)H = (P(QR)(Q(PR)(PQ)(QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)m6m3m7 (3, 6, 7) G,H的主析取范式相同，所以G = H.6、用等值演算法和真值表法判斷公式的類型。 （1）等值演算法（2）真值表法P QA1 1111111 0010010 1100010 011111所以A為重言式。7、設(shè)命題A1，A2的真值為1，A3，A4真值為0，求命題的真值。（5分）8、公式的主合取范式是 二、推理證明1、敘述并證明蘇格拉底三段論解：所有人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的。符號(hào)化：F（x）：x是一個(gè)人。G（x）：x要死的。A：蘇格拉底。命題符號(hào)化為x（F（x）G（x），F(xiàn)（a）G（a）證明：（1）x(F(x)G(x) P（2）F(a)G(a) T(1),US（3）F(a) P（4）G(a) T(2)(3),I2、設(shè)論域D=a , b , c，求證：。 3、用反證法證明。 4、用CP規(guī)則證明。 5、演繹推理：所有的有理數(shù)都是實(shí)數(shù)，所有的無(wú)理數(shù)也是實(shí)數(shù)，虛數(shù)不是實(shí)數(shù)。因此，虛數(shù)既不是有理數(shù)，也不是無(wú)理數(shù)。6、利用形式演繹法證明：AB, CB, CD蘊(yùn)涵AD。(1) AD(附加)(2) ABP(3) BQ(1)(2)(4) CBP(5) BCQ(4)(6) CQ(3)(5)(7) CDP(8) DQ(6)(7)(9) ADD(1)(8)所以 AB, CB, CD蘊(yùn)涵AD.7、P（附加前提）TIPTITITIPTICP8、P（附加前提）USPUSTIUGCP9、所有的舞蹈者都很有風(fēng)度，王華是個(gè)學(xué)生且是個(gè)舞蹈者。因此有些學(xué)生很有風(fēng)度。證明：設(shè)P(x)：x 是個(gè)舞蹈者； Q(x) ：x很有風(fēng)度； S(x)：x是個(gè)學(xué)生； a：王華上述句子符號(hào)化為：前提：、 結(jié)論： 3分PPUSTI TITITIEG10、符號(hào)化語(yǔ)句：“有些人喜歡所有的花，但是人們不喜歡雜草，那么花不是雜草”。并推證其結(jié)論。解： 證明：PESTITIPUSTITEUSUSTIUG11、符號(hào)化語(yǔ)句：“有些病人相信所有的醫(yī)生，但是病人都不相信騙子，所以醫(yī)生都不是騙子”。并推證其結(jié)論 解：F(x)：x是病人，G(x)：x是醫(yī)生，H(x)：x是騙子，L(x,y)：x相信y符號(hào)化：前提：結(jié)論：PESTITIPUSTITEUSUSTIUG3、 集合1、已知A、B、C是三個(gè)集合，證明A(BC)=(AB)(AC)證明：x A（BC） x Ax（BC） x A（xBxC）（ x AxB）（x AxC） x（AB）x AC x（AB）（AC） A（BC）=（AB）（AC）2、1設(shè) （N：自然數(shù)集，E+ 正偶數(shù)） 則 0，1，2，3，4，6； 。3、A，B，C表示三個(gè)集合，文圖中陰影部分的集合表達(dá)式為 A B C 。4、= 。5、集合的冪集= 。并搜集為 ，交搜集為 6、 4、 二元關(guān)系1、 設(shè)A=2，3，4，5，6上的二元關(guān)系，則R= , （列舉法）。R的關(guān)系矩陣MR= 。2、設(shè)集合A= a ,b , c , d 上關(guān)系R= , , , 要求 1、寫(xiě)出R的關(guān)系矩陣和關(guān)系圖。（4分） 2、用矩陣運(yùn)算求出R的傳遞閉包。（6分）； 關(guān)系圖2、 t (R)= , , , , , , , , 。3、設(shè)R和S是集合Aa, b, c, d上的關(guān)系，其中R(a, a),(a, c),(b, c),(c, d), S(a, b),(b, c),(b, d),(d, d).(1) 試寫(xiě)出R和S的關(guān)系矩陣；(2) 計(jì)算RS, RS, R1, S1R1. 解、 (1) (2)RS(a, b),(c, d),RS(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d), R1(a, a),(c, a),(c, b),(d, c),S1R1(b, a),(d, c). 4、設(shè)Aa，b，c，d，R是A上的二元關(guān)系，且R，求r(R)、s(R)和t(R)。解 r(R)RIA，s(R)RR-1，R2，R3，R4，R2t(R)，5、設(shè)R是集合A = a, b, c, d. R是A上的二元關(guān)系, R = (a,b), (b,a), (b,c), (c,d),(1) 求出r(R), s(R), t(R)；(2) 畫(huà)出r(R), s(R), t(R)的關(guān)系圖.(1) r(R)RIA(a,b), (b,a), (b,c), (c,d), (a,a), (b,b), (c,c), (d,d),s(R)RR1(a,b), (b,a), (b,c), (c,b) (c,d), (d,c),t(R)RR2R3R4(a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d), (c,d)；(2)關(guān)系圖:6、已知A=1,2,3,4,5和R=,，求r(R)、s(R)和t(R)。解：r(R)=,s(R)=,t(R)=,7、集合上的關(guān)系，寫(xiě)出關(guān)系矩陣，畫(huà)出關(guān)系圖并討論R的性質(zhì)。 解： R的關(guān)系圖為 R是自反、對(duì)稱的。8、設(shè)A=，1，1，3，1，2，3則A上包含關(guān)系“”的哈斯圖為9、設(shè)S=1 , 2 , 3 , 4, 6 , 8 , 12 , 24，“”為S上整除關(guān)系，問(wèn)：（1）偏序集的Hass圖如何？（2）若，求的極小元、最小元、極大元、最大元，上界，上確界，下界，下確界=,，,covS=, ,10、設(shè)A=1，2，3，4，5，A上的偏序關(guān)系為求A的子集3，4，5和1，2，3，的上界，下界，上確界和下確界，極大、極小元，最大最小元。11、集合上的偏序關(guān)系為整除關(guān)系。設(shè)，試畫(huà)出的哈斯圖，并求A，B，C的最大元素、極大元素、下界、上確界。 解：的哈斯圖為集合最大元極大元下界上確界A無(wú)24，36無(wú)無(wú)B12126，2，312C66無(wú)612、設(shè)集合A1, 2, 4, 6, 8, 12，R為A上整除關(guān)系。(1) 畫(huà)出半序集(A,R)的哈斯圖；(2) 寫(xiě)出A的最大元，最小元，極大元，極小元；(3) 寫(xiě)出A的子集B = 4, 6, 8, 12的上界，下界，最小上界，最大下界.解 (1) (2) 無(wú)最大元，最小元1，極大元8, 12; 極小元是1.(3) B無(wú)上界，無(wú)最小上界。下界1, 2; 最大下界2.13、設(shè)集合A1, 2, 3, 4, 6, 8, 9, 12，R為整除關(guān)系。（1）畫(huà)出半序集(A,R)的哈斯圖；（2）寫(xiě)出A的子集B = 3,6,9,12的上界，下界，最小上界，最大下界；（3）寫(xiě)出A的最大元，最小元，極大元，極小元。 (1)(2) B無(wú)上界，也無(wú)最小上界。下界1, 3; 最大下界是3.(3) A無(wú)最大元，最小元是1，極大元8, 12, 90+; 極小元是1.14、設(shè)A=a,b,c,d，A上的二元關(guān)系R=,，求R所誘導(dǎo)的等價(jià)關(guān)系，并求出等價(jià)關(guān)系中各元素的等價(jià)類。15、設(shè)X=1,2,3,4,5，X上的關(guān)系R= , , , , ，求R所誘導(dǎo)的等價(jià)關(guān)系，劃分等價(jià)類并求秩16、設(shè)A=1，2，3，4，S=1，2，3，4，為A的一個(gè)劃分，求1）由S導(dǎo)出的等價(jià)關(guān)系。2）求五、圖論1、已知：D=，V=1,2,3,4,5，E=,，求D的鄰接距陣A和可達(dá)距陣P。解：D的鄰接距陣A和可達(dá)距陣P如下：01010111110010011111A=00011P=11111000000000010000111112、給定圖G如圖所示，（1）G中長(zhǎng)度為4的路有幾條？其中有幾條回路？（2）寫(xiě)出G的可達(dá)矩陣。3、如下圖所示的賦權(quán)圖表示某七個(gè)城市及預(yù)先算出它們之間的一些直接通信線路造價(jià)，試給出一個(gè)設(shè)計(jì)方案，使得各城市之間能夠通信而且總造價(jià)最小。解： 用庫(kù)斯克（Kruskal）算法求產(chǎn)生的最優(yōu)樹(shù)。算法略。結(jié)果如圖：樹(shù)權(quán)C(T)=23+1+4+9+3+17=57即為總造價(jià)。4、求圖的可達(dá)性矩陣，并求圖的強(qiáng)分圖，弱分圖，單向分圖 5、下圖所示帶權(quán)圖中最優(yōu)投遞路線并求出投遞路線長(zhǎng)度（郵局在D點(diǎn)）。 圖中奇數(shù)點(diǎn)為E、F ，d(E)=3,d(F)=3,d(E,F)=28 p=EGF復(fù)制道路EG、GF，得圖G，則G是歐拉圖。由D開(kāi)始找一條歐拉回路：DEGFGEBACBDCFD。道路長(zhǎng)度為：35+8+20+20+8+40+30+50+19+6+12+10+23=2816、求帶權(quán)圖G中的最優(yōu)投遞路線。郵局在v1點(diǎn)。解：圖中有4個(gè)奇數(shù)結(jié)點(diǎn)，（1） 求任兩結(jié)點(diǎn)的最短路再找兩條道路使得它們沒(méi)有相同的起點(diǎn)和終點(diǎn)，且長(zhǎng)度總和最短：（2） 在原圖中復(fù)制出，設(shè)圖G，則圖G中每個(gè)結(jié)點(diǎn)度數(shù)均為偶數(shù)的圖G存在歐拉回路，歐拉回路C權(quán)長(zhǎng)為43。7、已知二叉樹(shù)的先序遍歷序列為ABCDEFGH，中序遍歷序列為CBEDFAGH，畫(huà)出二叉樹(shù)。答案：二叉樹(shù)形態(tài) 8、畫(huà)出與下圖所示的森林相對(duì)應(yīng)的二叉樹(shù)，并指出森林中的葉子結(jié)點(diǎn)在二叉樹(shù)中具有什么特點(diǎn)。已知有向圖G如下所示，根據(jù)迪杰斯特拉算法求頂點(diǎn)v0到其他頂點(diǎn)的最短距離。（給出求解過(guò)程）答案：終點(diǎn)從v0到各終點(diǎn)的d值和最短路徑的求解過(guò)程i=1i=2i=3i=4v112 (v0,v1)12 (v0,v1)7 (v0,v4,v1)v24 (v0,v2)v39 (v0,v3)8 (v0,v2,v3)7 (v0,v4,v3)7 (v0,v4,v3)v45 (v0,v4)5 (v0,v4)vjv2v4v1v3sv0,v2v0,v4v0,v4,v1v0,v4,v36、已知圖G如下所示，根據(jù)Prim算法，構(gòu)造最小生成樹(shù)。（要求給出生成過(guò)程）答案：prim算法求最小生成樹(shù)如下：已知圖G如下，根據(jù)克魯斯卡爾算法求圖G的一棵最小生成樹(shù)。（要求給出構(gòu)造過(guò)程）答案：kruskal算法的最小生成樹(shù) 12、已知圖G如下所示，求從頂點(diǎn)a到其余各頂點(diǎn)的最短路徑。（給出求解過(guò)程）543223356abdfce答案：終點(diǎn)最短路徑求解過(guò)程b6