PAGE1《離散數學》試卷1答案第3頁共3頁江蘇技術師范學院20—20學年第學期《離散數學》試卷（1）參考答案與評分標準一、單項選擇題（本大題共5道小題，每小題2分，共10分）1．設A={1,2,3},B={1,2,3,4,5},C={2,3},則(AB)-C=（C）。

A.{1,2}B.{2,3}C.{1,4,5}D.{1,2,3}2．在自然數集N上定義二元運算*如下，滿足交換律的是（C）。

A.a*b=a-bB.a*b=a+2bC.a*b=min{a,b}D.a*b=a3．設集合A={a,b,c},A上的關系R={<a,a>,<b,b>}具備下列性質（D）。

A.等價性B.自反性C.反自反性D.反對稱性4．當且僅當為下面條件中的哪一個時，無向簡單圖G是哈密頓圖？（D）。

A.G的每對結點的度數不大于頂點的個數B.G的每對結點的度數大于頂點的個數

C.G的每對結點的度數小于頂點的個數D.G的每對結點的度數不小于頂點的個數5．設B(x)：x是金子；F(x)：x會發光；則金子都會發光可符號化為：（B）。

A. B.C.D.二、填空（本大題共10空，每空2分，共20分）設p：我們勤奮，q：我們好學，r：我們取得好成績。命題“只要勤奮好學，我們就能取得好成績”符號化為pqr。若連通的簡單圖中所有結點的度數為偶數，則該圖一定是歐拉圖。群<Z6,+6>的所有子群是：_<Z6,+6>，<{0,2,4},+6>，<{0,3},+6>，<{0},+6>_。n個結點的無向完全圖的邊數m為n(n-1)/2。集合A={1,2,…,10}上的關系R={<x,y>|x+y=10,x,yA}，則R的性質為對稱性。{,{}}。一個圖G有24條邊，若每個結點的度均為2，則G有24個結點。設F(x):x是魚，G(x)：x會游泳；“沒有不會游泳的魚”符號化為（F(x)→G(x)）或x（F(x)∧G(x)）。偏序關系是指：滿足自反性、反對稱性、傳遞性的關系。P()={,{a},{},{{}},{a,},{a,{}},{,{}},{a,,{}}}。三、判斷題（本大題共10小題，每小題1分，共10分）正確的打“√”，錯誤的打“×”（√）若A={Ф},B=P（A）,則有{Ф}B及{Ф}B。（×）設A,B為無限集，則A-B是空集。（×）對集合A,B,C,D，有（AB）(CD)=(AC)(BD)。（×）簡單圖G有n個結點，m條邊,若m=n-1,則它一定是樹。（×）集合R上的關系滿足對稱性與傳遞性，則一定滿足自反性。（×）群中既有零元又有單位元，還有等冪元。（×）對哈密頓圖，奇度結點的個數均為偶數。（√）阿貝爾（Abel）群是交換群。（√）命題公式是重言式。（×）如果1+1＝3，則雪是黑的。這句話不是命題。四、證明題（本大題共4小題，每小題6分，共24分）1.設A、B、C是三個集合，證明：AB=A(B-A)證明：A(B-A)=A(B)=(AB)(A)=(AB)U=AB（6分）2.在命題邏輯中符號化下述命題，并構造推理的證明。若明天是星期一或星期三，我就有課。若有課，今天必須備課。我今天沒備課。所以，明天不是星期一和星期三。解：設p:明天是星期一,q:明天是星期三，r:我有課，s:我備課（1分）前提:(pq)r,rs,s結論:pq（1分）證明①rs前提引入②s前提引入③r①②拒取式④(pq)r前提引入⑤(pq)③④拒取式⑥pq⑤置換結論有效,即明天不是星期一和星期三。（4分）3.設9階無向圖的每個頂點的度數為5或6，證明它至少有5個6度頂點或者至少有6個5度頂點。證明：（6分）方法一討論所有可能的情況.設有a個5度頂點和b個6度頂點(1)a=0,b=9;(2)a=2,b=7;(3)a=4,b=5;(4)a=6,b=3;(5)a=8,b=1(1)~(3)至少5個6度頂點，(4)和(5)至少6個5度頂點方法二假設b<5,則a>9-5=4.由握手定理的推論,a>=64.在一階邏輯中符號化下述命題，并推證之。凡人必有一死，蘇格拉底是人，所以蘇格拉底會死的。解令F(x):x是人,G(x):x是要死的,a:蘇格拉底前提：x(F(x)→G(x))，F(a)結論：G(a)（2分）證明：①F(a)前提引入②x(F(x)→G(x))前提引入③F(a)→G(a)②UI④G(a)①③假言推理（4分）五、計算、應用題（本大題共6小題，第1、2、3、4小題各6分，第5小題4分，第6小題8分，共36分）1．設有一棵樹，它有兩個結點度數為2，三個結點度數為3，四個結點度數為4，其余結點度數均為1，問它有幾個結點度數為1？(6分)解：設有x片樹葉,2*(2+3+4+x-1)=2*2+3*3+4*4+x解得x=13，故有13個結點度數為1。2．有12個人參加聚會，每個人都認識其中的8個，問能否安排坐在一個圓桌上，使每個人認識與坐在他兩邊的人是認識的？為什么？（6分）解：可以。（2分）將每個人對應成相應的頂點，若兩人認識，則對應的兩個頂點間連上一條無向邊，作出一個簡單無向圖。由已知，圖中每個頂點的度數都等于8，故圖中任兩個不相鄰的頂點的度數和16大于等于12，即頂點數。故這個圖是一個哈密爾頓圖，從而存在哈密爾頓回路。任取一條哈密爾頓回路，按回路經過的頂點的次序安排對應的人的座位，就可滿足要求。（4分）3．求以1,3,4,5,6權為的最優2元樹,要求寫出步驟并計算它的權。（6分）（4分）W(T)=(1+3)*3+(4+5+6)*2=42（2分）4．求Q(Q→R)的主析取范式及主合取范式。（6分）解：Q(Q→R)Q(QR)(QQ)RT(主合取范式)（3分）(QR)(QR)(QR)(QR)（主析取范式）（3分）5．求謂詞公式的前束范式。解：（4分）6.A={1,2,3}，R為A上關系，關系矩陣為，(1)畫出關系圖。(2)求RR，R-1。(3)指出R具有的性質。(4)R是偏序關系嗎？若是畫出哈斯圖。解：(1)