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

1、一、范式 1、的主合取范式為 。2、 利用主析取范式，求公式的類(lèi)型。 解、 它無(wú)成真賦值，所以為矛盾式。3、 求命題公式Ø(PQ)«Ø(ØP®R)的主合取范式。 解：Ø(PQ)«Ø(ØP®R)Û（Ø(PQ)®Ø(ØP®R)）（Ø(ØP®R)®Ø(PQ)）Û（(PQ)(ØPØR)）（(PR)(ØPØQ)）Û(PQ)(ØP

2、ØR)Û(PØR)（QØP）（QØR）Û(PQØR)(PØQØR)（ØPQR）（ØPQØR）ÛM1M3M4M54、 設(shè)命題公式G = Ø(PQ)(Q(ØPR), 求G的主析取范式。 G = Ø(PQ)(Q(ØPR)= Ø(ØPQ)(Q(PR)= (PØQ)(Q(PR)= (PØQ)(QP)(QR)= (PØQR)(PØQØR)(PQR)(PQØR)

3、(PQR)(ØPQR)= (PØQR)(PØQØR)(PQR)(PQØR)(ØPQR)= m3m4m5m6m7 = S(3, 4, 5, 6, 7).5、 通過(guò)求主析取范式判斷下列命題公式是否等價(jià)：(1) G = (PQ)(ØPQR) (2) H = (P(QR)(Q(ØPR) G(PQ)(ØPQR)(PQØR)(PQR)(ØPQR)m6m7m3å (3, 6, 7)H = (P(QR)(Q(ØPR)(PQ)(QR)(ØPQR)(PQØR)(PQ

4、R)(ØPQR)(PQR)(ØPQR)(PQØR)(ØPQR)(PQR)m6m3m7å (3, 6, 7) G,H的主析取范式相同，所以G = H.6、用等值演算法和真值表法判斷公式的類(lèi)型。 （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要

5、死的。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, ØCØB, CD蘊(yùn)涵AD。(1) AD(附加)(2) ØABP

6、(3) BQ(1)(2)(4) ØCØBP(5) BCQ(4)(6) CQ(3)(5)(7) CDP(8) DQ(6)(7)(9) ADD(1)(8)所以 ØAB, ØCØB, 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ǔ)句：“有些人喜歡所

7、有的花，但是人們不喜歡雜草，那么花不是雜草”。并推證其結(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（xÎBxÎC）

8、19;（ xÎ AxÎB）（xÎ AxÎC） Û 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= <2,2>,<2,3>,<2,4>,<2,5>,<2,6&

9、gt;,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,2>,<5,3>,<5,4>,<5,5>,<5,6> （列舉法）。R的關(guān)系矩陣MR= 。2、設(shè)集合A= a ,b , c , d 上關(guān)系R=< a, b > , < b , a > , < b , c > , < c , d > 要求 1、寫(xiě)出R的關(guān)系矩陣和關(guān)系圖。（4分） 2、用矩陣運(yùn)算求出R的傳遞閉包。（

10、6分）； 關(guān)系圖2、 t (R)=<a , a> , <a , b> , < a , c> , <a , d > , <b , a > , < b ,b > , < b , c . > , < b , d > , < c , d > 。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. 解、

11、 (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<a，b>，<b，a>，<b，c>，<c，d>，求r(R)、s(R)和t(R)。解 r(R)RIA<a，b>，<b，a>，<b，c>，<c，d>，<a，a>，<b，b>，<c，

12、c>，<d，d>s(R)RR-1<a，b>，<b，a>，<b，c>，<c，d>，<c，b>，<d，c>R2<a，a>，<a，c>，<b，b>，<b，d>R3<a，b>，<a，d>，<b，a>，<b，c>R4<a，a>，<a，c>，<b，b>，<b，d>R2t(R)<a，b>，<b，a>，<b，c>，<c，d>，<

13、;a，a>，<a，c>，<b，b>，<b，d>，<a，d>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)

14、, (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=<1,2>,<2,1>,<2,3>,<3,4>,<5,4>，求r(R)、s(R)和t(R)。解：r(R)=<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>s(R)=<1,2>

15、,<2,1>,<2,3>,<3,4>,<5,4>,<3,2>,<4,3>,<4,5>t(R)=<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<1,3>,<2,2>,<2,4>,<1,4>7、集合上的關(guān)系，寫(xiě)出關(guān)系矩陣，畫(huà)出關(guān)系圖并討論R的性質(zhì)。 解： R的關(guān)系圖為 R是自反、對(duì)稱(chēng)的。8、設(shè)A=，1，1，3，1，2，3則A上包含關(guān)系“”的哈斯圖為9、設(shè)S=1 , 2 ,

16、 3 , 4, 6 , 8 , 12 , 24，“”為S上整除關(guān)系，問(wèn)：（1）偏序集的Hass圖如何？（2）若，求的極小元、最小元、極大元、最大元，上界，上確界，下界，下確界=<1,2>,<1,3>,<1,4>,<1,6>,<1,8>,<1,12>,<1,24>,<2,4>,<2,6>,<2,8>，<2,12>,<2,24>,<3,6>,<3,12>,<3,24>,<4,8>,<4,12>,&

17、lt;4,24>,<6,12>,<6,24>,<8,24>,<12,24>covS=<1,2>,<1,3>,<2,4>,<2,6>,<3,6>,<4,8>,<4,12>,<6,12> ,<8,24>,<12,24>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的最大

18、元素、極大元素、下界、上確界。 解：的哈斯圖為集合最大元極大元下界上確界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)的哈斯

19、圖；（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=<a,b>,<b,a>,<c,d>,<d,c>，求R所誘導(dǎo)的等價(jià)關(guān)系，并求出等價(jià)關(guān)系中各元素的等價(jià)類(lèi)。15、設(shè)X=1,2,3,4,5，X上的關(guān)系R=<1,1> , < 1 , 2 > , <2 , 4 &g

20、t; , < 3 , 5 > , < 4 , 2 > ，求R所誘導(dǎo)的等價(jià)關(guān)系，劃分等價(jià)類(lèi)并求秩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,E>，V=1,2,3,4,5，E=<1,2>,<1,4>,<2,3>,<3,4>,<3,5>,<5,1>，求D的鄰接距陣A和可達(dá)距陣P。解：D的鄰接距陣A和可達(dá)距陣P如下：01010111110010011111A=00011P=1111100000000001000011

21、1112、給定圖G如圖所示，（1）G中長(zhǎng)度為4的路有幾條？其中有幾條回路？（2）寫(xiě)出G的可達(dá)矩陣。3、如下圖所示的賦權(quán)圖表示某七個(gè)城市及預(yù)先算出它們之間的一些直接通信線(xiàn)路造價(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)投遞路線(xiàn)并求出投遞路線(xiàn)長(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)投遞路線(xiàn)。郵局在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ù)。答案：