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

1、二、（8分）個體域為1，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個兒童到公園游樂場，他們在那里可以騎旋轉木馬，坐滑行鐵道，乘宇宙飛船，已知其中20人這三種東西都乘過，其中55人至少乘坐過其中的兩種。若每樣乘坐一次的費用是0.5元，公園游樂場總共收入70元，求有多少兒童沒有乘坐過其中任何一種。解 設、分別表示騎旋轉木馬、坐滑行鐵道、乘宇宙飛船的兒童組成的集合，|20，|2|55，|70/0.5140。由容斥原理，得|所以|75|75(|)(|2|)|75140552010沒有乘坐過其中任何一種的兒童共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和可達距陣P。解：D的鄰接距陣A和可達距陣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分) 設Aa，b，c，d，R是A上的二元關系，且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分)求葉的權分別為2、4、6、8、10、12、14的最優(yōu)二叉樹及其權。解：最優(yōu)二叉樹為權(2+4)×4+6×3+12×2+(8+10)×3+14×21483、（5分）樹T有2個4度頂點，2個3度頂點，其余頂點全是樹葉。問T有幾片樹葉？解、設T有x片樹葉, 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片樹葉.2、（5分）設有向簡單圖D的度數(shù)序列為2、2、3、3,入度序列為0、0、2、3，試求D的出度序列和該圖的邊數(shù)，并在圖4中畫出該有向圖。解：出度序列為2、2、1、0邊數(shù)m=（2+2+3+3）/2=52、寫出對應下面推理的證明：如果今天是星期一，則要進行英語或離散數(shù)學考試。如果英語老師有會，則不考英語。今天是星期一，英語老師有會。所以進行離散數(shù)學考試。（其中p：今天是星期一；q：進行英語考試；r：進行離散數(shù)學考試；s：英語老師有會。） 前提：

9、p（qr），sq，p，s 結論：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設A=1,2,3,4,A上的關系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上整除關系的哈斯圖，并求它的最大元、最小元、極大元、極小元。解 它的最大元、最小元都不存在；極大元為8, 9, 10, 11；極小元為2, 3, 11。2483911103、：（N為自然數(shù)集合），說明f是否為單射、滿射的？計算。解 =<0,0> 不是單射 ,是滿射的五、有向圖如圖3-1所示。27441231365（1）求的鄰接矩陣； （2分）（2）中到長度為4的路徑有幾條？ （2分）（3）中到自身長度為3的回路有幾條？ （2分）（4）是哪類連通圖？ （2分）解：（1） （2）由中可知，到長度為4的路徑有條（，）。（3）由中

11、可知，到自身長度為3的回路有1條（）。（4）是單向連通圖。9. 設，則集合，和中是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上的整除關系。子集B=2，4，6，那么B的最大元是 ；B的最小元是 .答案：不存在；214命題公式的成真賦值為 ，成假賦值為 。答案：010，100，101，110，111； 000，001，01117設簡單圖G有n個頂點m條邊，v是G中度數(shù)為k的頂點，則Gv中有 個頂點， 條邊.答案：n-1；m-k19求下式的主析取范式與主合取范式。答案：主

12、析取范式為 主合取范式為21 推理題（寫出詳細推理過程）航海家都教育自己的孩子成為航海家，有一個人教育他的孩子去做飛行員，證明推理：這個人一定不是航海家。證明：設個體域為人的集合。謂詞s（x）：x是航海家；E（x）：x教育他的孩子成為航海家。前提：結論：推理過程為：（1） 條件引入（2） 存在規(guī)定ES（3） 條件引入（4） 全稱規(guī)定US（5） （2）（4）（6） （2）（5）（7） 存在推廣EG1. 構造下面推理的證明：（10分）前提：p(qÚr)，ØsØr，pÙØs；結論：q.證明： pÙØs 前提引入 p 化簡 p(q&

13、#218;r) 前提引入 qÚr 假言推理 ØsØr 前提引入 Øs 化簡 Ø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. 設集合

15、A=a,b,c,d，R是A上的二元關系，R=<a,b> ,<b,a> ,<b,c> , <c,d >；(8分)（1）畫出R的關系圖；（2）求R2； （3）求出R的自反閉包r(R)、對稱閉包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分） 問：（1）畫出圖G。 （2）試用鄰接矩陣求G中長度小于等于2的通路的條數(shù)，其中回路有幾條？（3）該圖是為強連通圖還是弱連通圖？ 解：（1）有向圖G如右圖： （2）G中長度小于等于2的通路的條數(shù)為：8+14=24，其中，回路為1+5=6條。（3）該圖為弱連通圖。7. 圖G是一個簡單的連通平面圖，頂點數(shù)為8，其無限面的次數(shù)為5，其余面都為三角形（次數(shù)為3），計算平面圖G的邊數(shù)和面數(shù)。解：設平面

17、圖G的邊數(shù)為m，面數(shù)為r。由于圖G頂點個數(shù)為8，由連通平面圖歐拉公式可知： 8 m + r =2 由平面圖握手定理可知： 5 +3(r-1) =2m 解可得：m =16，r =10，即平面圖G的邊數(shù)為16，面數(shù)為10。七、設R=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>，求r(R)、s(R)和t(R)，并作出它們及R的關系圖（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>