離散數(shù)學(xué)期末考試試題(配答案)

1、廣東技術(shù)師范學(xué)院模擬試題 科 目：離散數(shù)學(xué) 考試形式：閉卷 考試時(shí)間: 120 分鐘系別、班級(jí)： 姓名： 學(xué)號(hào)： 一填空題（每小題2分，共10分）1. 謂詞公式的前束范式是_ xy¬P(x)Q(y) _。2. 設(shè)全集則AB =_2_，_4,5_，_ 1,3,4,5 _3. 設(shè)，則_ c,a,c,b,c,a,b,c _，_。4. 在代數(shù)系統(tǒng)（N，+）中，其單位元是0，僅有 _1_ 有逆元。5如果連通平面圖G有個(gè)頂點(diǎn)，條邊，則G有_e+2-n_個(gè)面。二選擇題（每小題2分，共10分）1. 與命題公式等價(jià)的公式是（ ）（A） （B） （C） （D）2. 設(shè)集合,A上的二元關(guān)系不具備關(guān)系( )

2、性質(zhì)（A） (A)傳遞性 (B)反對(duì)稱性 (C)對(duì)稱性 (D)自反性3. 在圖中,結(jié)點(diǎn)總度數(shù)與邊數(shù)的關(guān)系是( )(A) (B) (C)(D) 4. 設(shè)D是有n個(gè)結(jié)點(diǎn)的有向完全圖,則圖D的邊數(shù)為( )(A) (B) (C) (D)5. 無向圖G是歐拉圖,當(dāng)且僅當(dāng)( )(A) G的所有結(jié)點(diǎn)的度數(shù)都是偶數(shù) (B)G的所有結(jié)點(diǎn)的度數(shù)都是奇數(shù)(C)G連通且所有結(jié)點(diǎn)的度數(shù)都是偶數(shù) (D) G連通且G的所有結(jié)點(diǎn)度數(shù)都是奇數(shù)。三計(jì)算題（共43分）1. 求命題公式的主合取范式與主析取范式。（6分）解：主合取方式：pqr(pqr)(p¬qr)(¬pqr)= 0.2.4主析取范式：pqr(pqr

3、) (pq¬r) (¬pqr) (¬p¬qr) (p¬qr)= 1.3.5.6.72. 設(shè)集合上的二元關(guān)系R的關(guān)系矩陣為,求的關(guān)系矩陣，并畫出R，的關(guān)系圖。（10分）3 無向圖G有12條邊，G中有6個(gè)3度結(jié)點(diǎn)，其余結(jié)點(diǎn)的度數(shù)均小于3，問G中至少有多少個(gè)結(jié)點(diǎn)？（10分）解：G（V,E），| E |=V，d（Vi）<3,設(shè)至少有x個(gè)節(jié)點(diǎn)，由握手定理得：2×12=d（Vi）<6×3+(x-6)×32<(x-6) = x>8故G中至少有9個(gè)節(jié)點(diǎn)。4 求下面兩個(gè)圖的最小生成樹。（12分）5. 試判斷是

4、否為格？說明理由。（5分）解：（Z,）是格，理由如下：對(duì)于任意aZ，aa成立，滿足自反性；對(duì)于任意aZ，bZ，若ab且ba，則a=b，滿足反對(duì)稱性；對(duì)于任意a，b，cZ，若ab，bc，則ac，滿足傳遞性；而對(duì)于任意a，bZ，ab，b為最小上界，a為最大下界，故（Z，）是格。（注：什么是格？）四證明題（共37分）1. 用推理規(guī)則證明。（10分）證明： 編號(hào)公式依據(jù)（1）（¬BC）¬C前提（2）¬BC，¬C（1）（3）¬B（2）（4）AB（3）（5）¬A（3）（4）（6）¬（¬AD）前提（7）A¬D（6）（8

5、）¬D（5）（6）2. 設(shè)R是實(shí)數(shù)集，。求證：都是滿射，但不是單射。（10分）證明：要證f是滿射，即yR,都存在（x1，x2）R×R，使f（x1，x2）=y，而f（x1，x2）=x1+x2，可取x1=0，x2=y，即證得；再證g是滿射，即yR，,都存在（x1，x2）R×R，使g（x1，x2）=y，而g（x1，x2）=x1x2，可取x1=1，x2=y，即證得；最后證f不是單射，f（x1，x2）=f（x2，x1）取x1x2，即證得，同理：g（x1，x2）=g（x2，x1），取x1x2，即證得。3. 無向圖G有9個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)的度數(shù)不是5就是6，求證：G中至少有5個(gè)6度結(jié)點(diǎn)或6個(gè)5度結(jié)點(diǎn)。（10分）證明：設(shè)G中至多有4個(gè)6度結(jié)點(diǎn)且5個(gè)5度結(jié)點(diǎn)，d（Vi）=49不是偶數(shù)，故它不是一個(gè)圖，矛盾。（下面只供參考，個(gè)人答案）4. 設(shè)平面上有100個(gè)點(diǎn)，期中任意兩點(diǎn)間的距離至少是1，則最多有300對(duì)點(diǎn)距離恰好為1。（7分）證明：設(shè)任意兩點(diǎn)間的讀書和恰好為1