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

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

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

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

5、）2. 設R是實數集，。求證：都是滿射，但不是單射。（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個結點，每個結點的度數不是5就是6，求證：G中至少有5個6度結點或6個5度結點。（10分）證明：設G中至多有4個6度結點且5個5度結點，d（Vi）=49不是偶數，故它不是一個圖，矛盾。（下面只供參考，個人答案）4. 設平面上有100個點，期中任意兩點間的距離至少是1，則最多有300對點距離恰好