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

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

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

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

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

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

(4),因?yàn)?因此是的逆元

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