2016離散數(shù)學練習題-(答案修改)(文檔)

2016注意事項：1、第一遍復(fù)習一定要認真按考試大綱要求將本學期所學習內(nèi)容系統(tǒng)復(fù)習一遍。2、第二遍復(fù)習按照考試大綱的總結(jié)把重點內(nèi)容再做復(fù)習。另外，把大綱中指定的例題及書后習題認真做一做。檢驗一下主要內(nèi)容的掌握情況。3、第三遍復(fù)習把隨后發(fā)去的練習題認真做一做，檢驗一下復(fù)習情況，要認真理解,注意做題思路與方法。離散數(shù)學綜合練習題一、選擇題1．令:今天下雪了，:路滑，r:他遲到了。則命題“下雪路滑，他遲到了”可符號化為（A）。A. B.C. D.2.設(shè):是整數(shù)，:的絕對值，：大于等于；命題“所有整數(shù)的絕對值大于等于0”可符號化為（B）。A. B.C. D.3.設(shè):是人，:犯錯誤，命題“沒有不犯錯誤的人”符號化為（D）。A． B．C． D．*4.下列命題公式不是永真式的是（A）。A. B.C. D.5．設(shè)p：我們劃船，q：我們跳舞，命題“我們不能既劃船又跳舞”符號化正確的是（B）。A. B.C. D.6．設(shè):x為有理數(shù)；:x為實數(shù)。命題“任何有理數(shù)都是實數(shù)”的符號化為（A）A． B．C． D．7.設(shè)個體域，與公式等價的命題公式是(C)A． B．C． D．8．無向圖G有20條邊，4個6度頂點，2個5度頂點，其余均為2度頂點，則G一共有（C）個頂點。A.7 B.8 C.9 D.10*9.設(shè)集合A={c,{c}}，下列命題是假命題的為（C）。A.B.C. D.10.設(shè)X=，則下列陳述正確的是（C）。A. B.C. D.11.有向圖D是連通圖，當且僅當（D）。A.圖D中至少有一條通路B.圖D中有通過每個頂點至少一次的通路C.圖D的連通分支數(shù)為一D.圖D中有通過每個頂點至少一次的回路12.設(shè)A={a,b,c}，則下列是集合A的劃分的是(B)A. B.C. D.13.下列謂詞公式中是前束范式的是（D）。A． B．C． D．14.設(shè)簡單圖G所有結(jié)點的度數(shù)之和為50，則G的邊數(shù)為（B）。A.50 B.25C.10 D.515.設(shè)集合,上的等價關(guān)系，則對應(yīng)于的劃分是（A）。A. B.C. D.16.設(shè)，則是(C)。A．從X到Y(jié)的雙射B．從X到Y(jié)的滿射，但不是單射C．從X到Y(jié)的單射，但不是滿射D．從X到Y(jié)的二元關(guān)系，但不是從X到Y(jié)的映射17.下列圖是歐拉圖的是（D）。18.給定一個有n個結(jié)點的無向樹，下列陳述不正確的是（A）。A．所有結(jié)點的度數(shù)≥2 B．無回路但若增加一條新邊就會變成回路C．連通且，其中e是邊數(shù)，v是結(jié)點數(shù)D．無回路的連通圖19．若供選擇答案中的數(shù)值表示一個簡單圖中各個頂點的度，能畫出圖的是（C）。A.(1,2,2,3,4,5) B.(1,2,3,4,5,5)C.(1,1,1,2,3) D.(2,3,3,4,5,6)20.設(shè)則其冪集的元素總個數(shù)為（C）。A.3 B.4C.8 D.1621.設(shè)簡單圖G所有結(jié)點的度數(shù)之和為48，則G的邊數(shù)為(B)A.48 B.24C.16 D.1222．下面既是哈密頓圖又是歐拉圖的圖形是（B）。23.下列必為歐拉圖的是（D）A.有回路的連通圖 B.不可以一筆畫的圖C.有1個奇數(shù)度結(jié)點的連通圖 D.無奇數(shù)度結(jié)點的連通圖24.二部圖是（B）。A.歐拉圖 B.哈密頓圖C.平面圖 D.完全圖25．下列所示的哈斯圖所對應(yīng)的偏序集中能構(gòu)成格的是（C）。A. B.C. D.26.設(shè)集合，A上的關(guān)系，則R是（B）A．自反的 B．對稱的C．傳遞的 D．反對稱的27．設(shè)是集合上的兩個關(guān)系，其中，，則是的（B）閉包。A．自反 B．對稱C．傳遞 D．自反、對稱且傳遞閉包28.下列公式是前束范式的是（A）。A． B．C． D．29.設(shè)R為實數(shù)集，函數(shù)，，則是（D）。A．單射而非滿射 B．滿射而非單射C．雙射 D．既不是單射，也不是滿射30．下列各圖中既是歐拉圖，又是漢密爾頓圖的是（C）。A．B．C．D．12.設(shè)，則方程的解為（B）。A．M∩N B．M∪NC．MNC．M-N13.設(shè)是群，則下列陳述不正確的是（C）。A. B.C. D.二、填空題1．命題公式的成真指派為000111,成假指派為_10__。2．公式約束變元為x,y，自由變元為x,z。3．設(shè)，，則,，{{a,b}}。4．設(shè)，上的關(guān)系，則對稱閉包，傳遞閉包。5.一棵無向樹的頂點數(shù)與邊數(shù)的關(guān)系是n-1。6階無向連通圖至多有6棵不同構(gòu)的生成樹。6．設(shè)，，則復(fù)合函數(shù)=,=。7.是一個群，其中，，則當=6時，在中，2的階為__3____,3的階為_2。8．設(shè)<A，≤>是格，其中A={1,3,4，6，8，12，24}，≤為整除關(guān)系，則1的補元是___24__，3的補元是__8__。9．設(shè)A=｛<1，3>，<3，5>，<4，4>｝，B=｛<1,3>,<4,5>,<5,5>｝,那么={1,3,4,5}ran={3}_。10.設(shè)A={l,2,3,4},A上的二元關(guān)系R={<1,2>,<2,3>,<3,2>}，S={<l,3>,<2,3>，<4，3>}，則{<1,3>,<3,3>},{<3,1>,<3,3>}。11．設(shè)復(fù)合函數(shù)gf是從A到C的函數(shù)，如果gf是滿射，那么__g___必是滿射，如果gf是單射，那么__f_必是單射。12．給出A={l，2}上的一個等價關(guān)系，并給出其對應(yīng)的劃分。13．設(shè)，上的二元關(guān)系，則的自反閉包，傳遞閉包R14．設(shè)個體域是實數(shù)集，命題的真值為1；命題的真值為0。15.設(shè)f∶R→R,f(x)=x+3,g∶R→R,g(x)=2x+1,則復(fù)合函數(shù),。16．設(shè)為模6加群，其中，則2-3=0，4-2=4。17．一個結(jié)點為n的無向完全圖，其邊的數(shù)目為n(n-1)/2，頂點的度為n-1。18.已知階無向簡單圖有條邊，則的補圖中有n(n-1)/2-m條邊。19.設(shè)是個頂點的完全圖，則K5有_10____條邊，每個頂點的度數(shù)為___4___。20.一個班有40個人，在第一次考試中有26人得優(yōu)秀，在第二次考試中有21人得優(yōu)秀，如果兩次考試都得優(yōu)秀的有17人，兩次考試都沒有得優(yōu)秀的人數(shù)為10，至少有一次得優(yōu)秀的人數(shù)為30。三、計算題（僅給出部分題目的解題思路，未給出答案自己完成）1.已知命題公式（1）構(gòu)造真值表；（2）用等值演算法求公式的主析取范式。解：（1）真值表pqr00000110010101010101101111001001100101110011011001111100（2）主析取范式2．求公式的主合取范式及主析取范式。3.設(shè)，,，其中表示實數(shù)集。（1）求函數(shù)，；（2）哪些函數(shù)有反函數(shù)？如果有，求出這些反函數(shù)。解：（1）（2）和有反函數(shù)，；4.設(shè)，為整除關(guān)系。（1）畫出偏序集<A,>的哈斯圖；（2）求A中的極大元；（3）求子集B=｛3,6,9｝的上確界與下確界。解：（1）哈斯圖（2）A中的極大元為24，54；極小元為1；最大元：無；最小元：1（3）求子集B=｛3,6,9｝的上確界為54，下確界為3。5.設(shè)有向圖如圖所示，用鄰接矩陣計算到長度小于或等于3的通路數(shù)。解：有向圖的鄰接矩陣為，，v1到v3長度小于或等于3的通路數(shù)為6．設(shè)，給出模6加運算的運算的運算表。解：運算的運算表為012345001234511234502234501334501244501235501234參看教材P197-198例9.4與9.57.設(shè)A＝{1，2，3，4，5}，R是A上的二元關(guān)系，且R＝{（2，1>，<2，5），<2，4>，<3，4)，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。解：r(R)=R∪IAs(R)=R∪R-1t(R)={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>,（2,2>,<5,5>}8.一棵（無向）樹有2結(jié)點的度為2，1個結(jié)點的度為3，3個結(jié)點的度為4,其余都是葉結(jié)點，問該樹有幾個葉結(jié)點？解：在一個有限圖中，各結(jié)點的度數(shù)總和是邊數(shù)的2倍；而樹中的邊數(shù)為結(jié)點數(shù)減1。根據(jù)這兩點，可知樹中各結(jié)點的度數(shù)總和=2*（樹中點數(shù)-1），設(shè)樹葉有x個，于是，2*2+3+3*4+x=2*（2+1+3+x-1）

得x=9。四、簡答題1.設(shè)是A=上的二元關(guān)系。（1）畫出R的關(guān)系圖；（2）寫出R的關(guān)系矩陣；（3）討論R的性質(zhì)。（4）R是否為函數(shù)解：（1）R的關(guān)系圖（2）R的關(guān)系矩陣（3）R非自反、非反自傳、對稱、非反對稱、非傳遞的（4）R不是函數(shù)，不滿足函數(shù)單值性的要求。2.設(shè)集合上的關(guān)系（1）畫出的關(guān)系圖，并寫出的關(guān)系矩陣；（2）是否為等價關(guān)系？若是，寫出的所有等價類。解：（1）R的關(guān)系圖為（2）R的關(guān)系矩陣由關(guān)系圖可以看出是等價關(guān)系。等價類為：或?qū)憺椋篈/R={{1,3,6},{2,5},{4}}3．判斷下圖是否為二部圖？若是，找出它的互補結(jié)點子集。它是否為哈密頓圖？若是，找出一條哈密頓回路。四、證明題1．設(shè)為正整數(shù)，在上定義二元關(guān)系如下：當且僅當。證明：是一個等價關(guān)系。證明：任取所以R自反的。任取所以R是對稱的。任取所以R是傳遞的。因此，R是等價關(guān)系。2．設(shè)為正整數(shù)，在上定義二元關(guān)系如下：當且僅當。證明：是一個等價關(guān)系。證明：任取所以R自反的。任取所以R是對稱的。任取所以R是傳遞的。因此，R是等價關(guān)系。3.用一階邏輯的推理理論證明：4．設(shè)代數(shù)系統(tǒng)，，為模6加法。證明：關(guān)于運算構(gòu)成群。證明：集合顯然非空。

(1),,從而集合關(guān)于運算是封閉的。

(2),有，故運算是可結(jié)合的。

(3),,故0是中的幺元。

(4),因為,因此是的逆元

由此上知是群5．設(shè)A是集合，P(A)是A的冪集合，是對稱差運算，證明<P(A),>構(gòu)成群。五、應(yīng)用題（未給出參考答案的自己完成）1.構(gòu)造下列推理的證明。如果今天是星期一，則要進行英語或離散數(shù)學考試。如果英語老師有會，則不考英語。今天是星期一，英語老師有會，所以進行離散數(shù)學考試。（給答案）2.構(gòu)造下列推理的證明。小王是理科學生，則他的數(shù)學成績很好。如果小王不是文科學生，則他一定是理科學生。小王的數(shù)學成績不好,所以小王是文科學生。3.用一階邏輯推理證明前提：，，結(jié)論：證明：（1）前提引入（2）（1）（3）前提引入（4）（3）（5）（2）（4）析取三段論（6）前提引入（7）（6）（8）（5）（7）假言推理（9）（8）4．今有于7個人，已知下列事實：a會講英語；b會講英語和漢語；c會講英語、意大利語和俄