離散數(shù)學(xué)考試試題及答案

1、二、（8分）個(gè)體域?yàn)?，2，求"x$y（x+y=4）的真值。解："x$y（x+y=4）Û"x（x+1=4）（x+2=4）Û（1+1=4）（1+2=4）（2+1=4）（2+1=4）Û（00）（01）Û11Û0四、（10分）已知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>,<

2、;5,4>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>s(R)=<1,2>,<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>五、(10分)

3、75個(gè)兒童到公園游樂(lè)場(chǎng)，他們?cè)谀抢锟梢则T旋轉(zhuǎn)木馬，坐滑行鐵道，乘宇宙飛船，已知其中20人這三種東西都乘過(guò)，其中55人至少乘坐過(guò)其中的兩種。若每樣乘坐一次的費(fèi)用是0.5元，公園游樂(lè)場(chǎng)總共收入70元，求有多少兒童沒(méi)有乘坐過(guò)其中任何一種。解 設(shè)、分別表示騎旋轉(zhuǎn)木馬、坐滑行鐵道、乘宇宙飛船的兒童組成的集合，|20，|2|55，|70/0.5140。由容斥原理，得|所以|75|75(|)(|2|)|75140552010沒(méi)有乘坐過(guò)其中任何一種的兒童共10人。九、（10分）已知：D=<V,E>，V=1,2,3,4,5，E=<1,2>,<1,4>,<2,3>,

4、<3,4>,<3,5>,<5,1>，求D的鄰接距陣A和可達(dá)距陣P。解：D的鄰接距陣A和可達(dá)距陣P如下：01010111110010011111A=00011P=1111100000000001000011111一、（10分）求命題公式Ø(PQ)«Ø(ØP®R)的主合取范式。解：Ø(PQ)«Ø(ØP®R)Û（Ø(PQ)®Ø(ØP®R)）（Ø(ØP®R)®Ø

5、;(PQ)）Û（(PQ)(ØPØR)）（(PR)(ØPØQ)）Û(PQ)(ØPØR)Û(PØR)（QØP）（QØR）Û(PQØR)(PØQØR)（ØPQR）（ØPQØR）ÛM1M3M4M5五、(10分) 設(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<

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

7、，b>，<b，d>R2t(R)<a，b>，<b，a>，<b，c>，<c，d>，<a，a>，<a，c>，<b，b>，<b，d>，<a，d>十、(10分)求葉的權(quán)分別為2、4、6、8、10、12、14的最優(yōu)二叉樹(shù)及其權(quán)。解：最優(yōu)二叉樹(shù)為權(quán)(2+4)×4+6×3+12×2+(8+10)×3+14×21483、（5分）樹(shù)T有2個(gè)4度頂點(diǎn)，2個(gè)3度頂點(diǎn)，其余頂點(diǎn)全是樹(shù)葉。問(wèn)T有幾片樹(shù)葉？解、設(shè)T有x片樹(shù)葉, n個(gè)頂點(diǎn)，m條邊n=2

8、+2+x，m=n-1= 4+x-1 ，由握手定理2´(4+x-1)=2´4+2´3+x×1解得x=8，故T有8片樹(shù)葉.2、（5分）設(shè)有向簡(jiǎn)單圖D的度數(shù)序列為2、2、3、3,入度序列為0、0、2、3，試求D的出度序列和該圖的邊數(shù)，并在圖4中畫(huà)出該有向圖。解：出度序列為2、2、1、0邊數(shù)m=（2+2+3+3）/2=52、寫(xiě)出對(duì)應(yīng)下面推理的證明：如果今天是星期一，則要進(jìn)行英語(yǔ)或離散數(shù)學(xué)考試。如果英語(yǔ)老師有會(huì)，則不考英語(yǔ)。今天是星期一，英語(yǔ)老師有會(huì)。所以進(jìn)行離散數(shù)學(xué)考試。（其中p：今天是星期一；q：進(jìn)行英語(yǔ)考試；r：進(jìn)行離散數(shù)學(xué)考試；s：英語(yǔ)老師有會(huì)。） 前提：

9、p（qr），sq，p，s 結(jié)論：r 證明：p（qr） 前提引入 p 前提引入qr 假言推理sq 前提引入s 前提引入q 假言推理r 析取三段論1、=，B=，求笛卡爾乘積A×B和A的冪集P(A)。解 A×B=<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2.> P(A)=F,a,b,a.b設(shè)A=1,2,3,4,A上的關(guān)系R=1,1,1,2,2,4,3,1,4,3,求domR、ranR、R1。解 domR=1,2,3,4, ranR=1,2,3,4, R1 =1,1,2,1,4,2,1,

10、3,3,42、集合2, 3, 4, 8, 9, 10, 11上整除關(guān)系的哈斯圖，并求它的最大元、最小元、極大元、極小元。解 它的最大元、最小元都不存在；極大元為8, 9, 10, 11；極小元為2, 3, 11。2483911103、：（N為自然數(shù)集合），說(shuō)明f是否為單射、滿射的？計(jì)算。解 =<0,0> 不是單射 ,是滿射的五、有向圖如圖3-1所示。27441231365（1）求的鄰接矩陣； （2分）（2）中到長(zhǎng)度為4的路徑有幾條？ （2分）（3）中到自身長(zhǎng)度為3的回路有幾條？ （2分）（4）是哪類(lèi)連通圖？ （2分）解：（1） （2）由中可知，到長(zhǎng)度為4的路徑有條（，）。（3）由中

11、可知，到自身長(zhǎng)度為3的回路有1條（）。（4）是單向連通圖。9. 設(shè)，則集合，和中是A的覆蓋的有 ，是A的劃分的有 . 答案：s1, s2, s3, s4, s5 s3, s4, s510. A=1，2，3，4，5，6，7，8，9，10，11，12，R是A上的整除關(guān)系。子集B=2，4，6，那么B的最大元是 ；B的最小元是 .答案：不存在；214命題公式的成真賦值為 ，成假賦值為 。答案：010，100，101，110，111； 000，001，01117設(shè)簡(jiǎn)單圖G有n個(gè)頂點(diǎn)m條邊，v是G中度數(shù)為k的頂點(diǎn)，則Gv中有 個(gè)頂點(diǎn)， 條邊.答案：n-1；m-k19求下式的主析取范式與主合取范式。答案：主

12、析取范式為 主合取范式為21 推理題（寫(xiě)出詳細(xì)推理過(guò)程）航海家都教育自己的孩子成為航海家，有一個(gè)人教育他的孩子去做飛行員，證明推理：這個(gè)人一定不是航海家。證明：設(shè)個(gè)體域?yàn)槿说募稀Ｖ^詞s（x）：x是航海家；E（x）：x教育他的孩子成為航海家。前提：結(jié)論：推理過(guò)程為：（1） 條件引入（2） 存在規(guī)定ES（3） 條件引入（4） 全稱(chēng)規(guī)定US（5） （2）（4）（6） （2）（5）（7） 存在推廣EG1. 構(gòu)造下面推理的證明：（10分）前提：p(qÚr)，ØsØr，pÙØs；結(jié)論：q.證明： pÙØs 前提引入 p 化簡(jiǎn) p(q&

13、#218;r) 前提引入 qÚr 假言推理 ØsØr 前提引入 Øs 化簡(jiǎn) Ør 假言推理 q 析取三段論2. 求公式(pq) Ù(qr)的主析取范式、主合取范式、成真賦值。（10分）解： (pq) Ù(qr)Û(ØpÚ q) Ù(ØqÚ r)Û(Øp Ú q) Ú (r Ù Ør) Ù (pÚØp) (ØqÚr)Û(Øp Ú

14、q Ú r) Ù (Øp Ú q Ú Ør) Ù (p Ú Øq Ú r) Ù (Øp Ú Øq Ú r)ÛM4 Ù M5 Ù M2 Ù M6 Û(2, 4, 5,6)Û(0, 1, 3,7)公式(pq) Ù(qr)的主析取范式為：(0, 1, 3,7)主合取范式為：(2, 4, 5,6)公式(pq) Ù(qr)的成真賦值為：000，001，011，1113. 設(shè)集合

15、A=a,b,c,d，R是A上的二元關(guān)系，R=<a,b> ,<b,a> ,<b,c> , <c,d >；(8分)（1）畫(huà)出R的關(guān)系圖；（2）求R2； （3）求出R的自反閉包r(R)、對(duì)稱(chēng)閉包s(R)。 2） R2 = <a, a>，< a, c >，< b, b >，< b, d > （3）r(R)= RIA=<a,b>,<b,a>,<b,c>,<c,d>,<a,a >,<b,b>,<c,c>,<d,d>s

16、(R)=RR1=<a,b>,<b,a>,<b,c>,<c,d>,<c,b >,<d,c> 5. 已知某有向圖G的鄰接矩陣如下：（8分） 問(wèn)：（1）畫(huà)出圖G。 （2）試用鄰接矩陣求G中長(zhǎng)度小于等于2的通路的條數(shù)，其中回路有幾條？（3）該圖是為強(qiáng)連通圖還是弱連通圖？ 解：（1）有向圖G如右圖： （2）G中長(zhǎng)度小于等于2的通路的條數(shù)為：8+14=24，其中，回路為1+5=6條。（3）該圖為弱連通圖。7. 圖G是一個(gè)簡(jiǎn)單的連通平面圖，頂點(diǎn)數(shù)為8，其無(wú)限面的次數(shù)為5，其余面都為三角形（次數(shù)為3），計(jì)算平面圖G的邊數(shù)和面數(shù)。解：設(shè)平面

17、圖G的邊數(shù)為m，面數(shù)為r。由于圖G頂點(diǎn)個(gè)數(shù)為8，由連通平面圖歐拉公式可知： 8 m + r =2 由平面圖握手定理可知： 5 +3(r-1) =2m 解可得：m =16，r =10，即平面圖G的邊數(shù)為16，面數(shù)為10。七、設(shè)R=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>，求r(R)、s(R)和t(R)，并作出它們及R的關(guān)系圖（15分）。解：r(R)=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>s(R)=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>R2=R5=<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>R3=<2,1>