電大歷年離散數(shù)學(xué)試題匯總

.........資料.....資料.........資料....計算機(jī)科學(xué)與技術(shù)專業(yè)級第二學(xué)期離散數(shù)學(xué)試題2012年1月一、單項選擇題（每小題3分，本題共15分）1．C2．C3．B4．A5．D1．若集合A的元素個數(shù)為10，則其冪集的元素個數(shù)為（）．A．10B．100C．1024D．12．設(shè)A={a,b}，B={1,2}，R，R，R是A到B的二元關(guān)系，且R={<a，2>,<a，1>}，R={<a， 1 2 3 1 21>,<a，2>,<b，1>}，R={<a，1>,<b，2>}，則（）是從A到B的函數(shù)．3A．R和RB．RC．RD．R和R 1 2 2 3 1 33．設(shè)A={1,2,3,4,5,6,7,，R是8}A上的整除關(guān)系，B={2,4,6}，則集合B的最大元、最小元、上界、下界依次為()．A．8、2、8、2B．無、2、無、2C．6、2、6、2D．8、1、6、14．若完全圖G中有n個結(jié)點(diǎn)(n≥2)，m條邊，則當(dāng)（）時，圖G中存在歐拉回路．A．n為奇數(shù)B．n為偶數(shù)C．m為奇數(shù)D．m為偶數(shù)5．已知圖G的鄰接矩陣為則G有（）．A．6點(diǎn)，8邊B．6點(diǎn)，6邊C．5點(diǎn)，8邊D．5點(diǎn)，6邊二、填空題（每小題3分，本題共15分）6．設(shè)集合A＝{a}，那么集合A的冪集是{,{a}}． 7．若R和R是A上的對稱關(guān)系，則R∪R，R∩ ，R-R中對稱關(guān)系有4個． 1 2 1 2 2 1 8．設(shè)圖G是有5個結(jié)點(diǎn)的連通圖，結(jié)點(diǎn)度數(shù)總和為10，則可從G中刪去1條邊后使之變成樹．9．設(shè)連通平面圖G的結(jié)點(diǎn)數(shù)為5，邊數(shù)為6，則面數(shù)為3．10．設(shè)個體域D＝{a,b}，則謂詞公式(x)(A(x)∧B（x））消去量詞后的等值式為(A(a)∧B(b))∧(A（a）∧B（b））．邏輯公式翻譯（每小題6分，本題共12分）11．將語句“今天有聯(lián)歡活動，明天有文藝晚會．”翻譯成命題公式．設(shè)P：今天有聯(lián)歡活動，Q：明天有文藝晚會，（2分）P∧Q．（6分）12．將語句“如果小王來，則小李去．”翻譯成命題公式．設(shè)P：小王來，Q：小李去（2分）P→Q．（6分）判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由．a(chǎn)13．若偏序集<A，R>的哈斯圖如圖一所示， 則集合A的最大元為a，極小元不存在． b c d 圖一錯誤．（3分）對于集合A的任意元素x，均有<x,a>R（或xRa），所以a是集合A中的最大元．（5分）但按照極小元的定義，在集合A中b,c,d均是極小元．（7分）14．┐P∧（P→┐Q）∨P為永假式．錯誤．（3分）┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）與P組成的析取式，如果P的值為真，則┐P∧（P→┐Q）∨P為真，（5分）如果P的值為假，則┐P與P→┐Q為真，即┐所以┐P∧（P→┐Q）∨P是永真式．（7分）另種說明：┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）與P組成的析取式，只要其中一項為真，則整個公式為真．（5分）可以看到，不論P(yáng)的值為真或為假，┐P∧（P→┐Q）與P總有一個為真，所以┐P∧（P→┐Q）∨P是永真式．（7分）或用等價演算┐P∧（P→┐Q）∨PT五．計算題（每小題12分，本題共36分）15．設(shè)集合A={1，2，3，4}，R={<x,y>|x,yA；|xy|=1或xy=0}，試寫出R的有序?qū)Ρ硎?；畫出R的關(guān)系圖；說明R滿足自反性，不滿足傳遞性．15．（1）R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>}（3分）關(guān)系圖如圖二：圖二（6分）因為<1,1>,<2,2>,<3,3>,<4,4>均屬于R，即A的每個元素構(gòu)成的有序?qū)赗中，故R在A上是自反的．（9分）因有<2,3>與<3,4>屬于R，但<2,4>不屬于R，所以R在A上不是傳遞的．（12分）16．設(shè)圖G=<V，E>，V={v，v，v，v，v}，E={(v,v)，(v,v)，(v,v)，(v,v)，(v,v)，} 1 2 3 4 5 1 2 1 3 2 4 3 5 4 5試畫出G的圖形表示；寫出其鄰接矩陣；求出每個結(jié)點(diǎn)的度數(shù)；畫出圖G的補(bǔ)圖的圖形． v16．（1）關(guān)系圖如圖三：v5 v3 v4圖三（3分）01101001001000101001001（6分）10鄰接矩陣deg(v)=21deg(v)=22deg(v)=23deg(v)=24deg(v)=2（9分） v2v5 v3 v4 圖四（12分）17．求PQ∧R的合取范式與主析取范式．P→（R∧Q）┐P∨(R∧Q)（4分）（┐P∨Q）∧（┐P∨R）（合取范式）（6分）P→（R∧Q）.........資料..... ........資料....┐P∨(R∧Q)(┐P∧(┐Q∨Q))∨(R∧Q)（7分）(┐P∧┐Q)∨(┐P∧Q)∨(R∧Q)（8分）((┐P∧┐Q)∧(┐R∨R))∨(┐P∧Q)∨(R∧Q)（9分）(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q)∨(R∧Q)（10分）(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨((┐P∧Q)∧(┐R∨R))∨(R∧Q)(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q∧┐R)∨(┐P∧Q∧R)∨(R∧Q)(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q∧┐R)∨(┐P∧Q∧R)∨((┐P∨P)∧(R∧Q))(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q∧┐R)∨(┐P∧Q∧R)∨(P∧R∧Q)（主析取范式）（12分）說明：此題解法步驟多樣，若能按正確步驟求得結(jié)果，均可給分．六、證明題（本題共8分）18．設(shè)連通無向圖G有14條邊，3個4度頂點(diǎn)，4個3度頂點(diǎn)，其它頂點(diǎn)的度數(shù)均小于3，試說明G中可能有的頂點(diǎn)數(shù)．證明：可利用數(shù)列可圖化及握手定理解答頂點(diǎn)度數(shù)和為214=28，（2分）28-（34+43）=4，則知其他頂點(diǎn)度數(shù)和為4，（4分）對于有限圖，若無零度頂點(diǎn)，則除4度及3度頂點(diǎn)外，可能的頂點(diǎn)情況有：2個2度點(diǎn)；1個2度點(diǎn)和2個1度點(diǎn)；4個1度點(diǎn)，（6分）即對應(yīng)圖的頂點(diǎn)數(shù)分別至少為9、10、11．（8分）2011年7月一、單項選擇題（每小題3分，本題共15分）1．A2．C3．C4．D5．B1．若集合A={1，{1}，{2}，{1，2}}，則下列表述正確的是()．A．{2}AB．{1，2}AC．1AD．2A2．設(shè)G為無向圖，則下列結(jié)論成立的是()．A．無向圖G的結(jié)點(diǎn)的度數(shù)等于邊數(shù)的兩倍．B．無向圖G的結(jié)點(diǎn)的度數(shù)等于邊數(shù)．C．無向圖G的結(jié)點(diǎn)的度數(shù)之和等于邊數(shù)的兩倍．D．無向圖G的結(jié)點(diǎn)的度數(shù)之和等于邊數(shù)．3．圖G如圖一所示，以下說法正確的是()．cA．{(a，b)}是邊割集 a eB．{a，c}是點(diǎn)割集C．w8cwyka是點(diǎn)割集D．{(c，d)}是邊割集 b d f圖一4．設(shè)集合A={1}，則A的冪集為()．A．{{1}}B．{1，{1}}C．{，1}D．{，{1}}5．設(shè)A(x)：x是人，B(x)：x犯錯誤，則命題“沒有不犯錯誤的人”可符號化為（）．A．┐(x)(A(x)→┐B(x))B．┐(x)(A(x)∧┐B(x))C．┐(x)(A(x)∧B(x))D．(x)(A(x)∧B(x))二、填空題（每小題3分，本題共15分）6．命題公式PP的真值是真（或T，或1）．7．若無向圖T是連通的，則T的結(jié)點(diǎn)數(shù)v與邊數(shù)e滿足關(guān)系v=e+1時，T是樹．8．無向圖G是歐拉圖的充分必要條件是G是連通的且結(jié)點(diǎn)度數(shù)都是偶數(shù)．9．設(shè)集合A={1，2}上的關(guān)系R＝{<2,2>,<1,2>}，則在R中僅需加入一個元素<1,1>，就可使新得到的關(guān)系為自反的．10．(x)(P(x)→R(y)∨S(z))中的約束變元有x．邏輯公式翻譯（每小題6分，本題共12分）11．將語句“雪是黑色的．”翻譯成命題公式．設(shè)P：雪是黑色的，（2分）則命題公式為：P．（6分）12．將語句“如果明天下雨，則我們就在室內(nèi)上體育課．”翻譯成命題公式．設(shè)P：如果明天下雨，Q：我們在室內(nèi)上體育課，（2分）則命題公式為：PQ．（6分）判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由．13．設(shè)集合A={1，2}，B={3，4}，從A到B的關(guān)系為f={<1,3>，<1,4>}，則f是A到B的函數(shù)．錯誤．（3分）因為A中元素1有B中兩個不同的元素與之對應(yīng)，故f不是A到B的函數(shù)．（7分）14．設(shè)G是一個連通平面圖，有5個結(jié)點(diǎn)9條邊，則G有6個面．正確．（3分）因G是一個連通平面圖，滿足歐拉定理，有v-e+r=2，所以r=2-（v-e）=2-（5-9）=6（7分）五．計算題（每小題12分，本題共36分）15．試求出P→（R∧Q）的合取范式．P→（R∧Q）┐P∨（R∧Q）（6分）(┐P∨R)∧（┐P∨Q）（合取范式）（12分）16．設(shè)A={{1},{1,，2}1}，B={1,2,{2}}，試計算（1）（A∩B）（2）（A∪B）（3）（A∩B）A．（A∩B）={1}（4分）（A∪B）={1,2,{1},{2},{1,2}}（8分）（A∩B）A=（12分）17．試畫一棵帶權(quán)為2,3,3,4,5,的最優(yōu)二叉樹,并計算該最優(yōu)二叉樹的權(quán)．最優(yōu)二叉樹如圖二所示．17 10 7 資料.5 53 4 2 3（10分）圖二權(quán)為23+33+32+42+52=39（12分）六、證明題（本題共8分）18．試證明：若R與S是集合A上的對稱關(guān)系，則R∩S也是集合A上的對稱關(guān)系．證明：設(shè)x，yA，因為R對稱，所以若<x,y>R，則<y,x>R．（2分）因為S對稱，所以若<x,y>S，則<y,x>S．（4分）于是若<x,y>R∩S則<x,y>R且<x,y>S即<y,x>R且<y,x>S（6分）也即<y,x>R∩S，故R∩S是對稱的．（8分）中央廣播電視大學(xué)2010—2011學(xué)年度第一學(xué)期“開放本科”期末考試離散數(shù)學(xué)（本）試題2011年1月單項選擇題（每小題3分，本題共15分）1．A2．D3．B4．D5．C1．若集合A＝{a，{1}}，則下列表述正確的是()．A．{1}AB．{1}AC．{a}AD．A2．設(shè)圖G＝<V,E>，vV，則下列結(jié)論成立的是()．A．deg(v)=2EB．deg(v)=EC．deg(v)ED．deg(v)2E3．圖一所示，以下說法正確的是()A．(e,c)是割邊B．(d,e)是割邊C．(b,a)是割邊D．(b,c)是割邊 edc 圖一4．命題公式（P∨Q）的合取范式是()．A．PB．（P∧Q）C．（P∨P）D．（P∨Q）5．下列等價公式成立的為()．A．PQPQB．QPPQC．PPQQD．PPQ填空題（每小題3分，本題共15分）.........資料.....資料.........資料....6．設(shè)集合A={0,1,2}，B={1,2,3,4,，}R是A到B的二元關(guān)系，R{x,yxA且yB且x,yAB}則R的有序?qū)蠟閧<1,1>，<1,2>，<2,1>，<2,2>}．7．設(shè)G是連通平面圖，v,e,r分別表示G的結(jié)點(diǎn)數(shù)，邊數(shù)和面數(shù)，則v，e和r滿足的關(guān)系式v-e+r=2．8．設(shè)G＝<V,E>是有20個結(jié)點(diǎn)，25條邊的連通圖，則從G中刪去6條邊，可以確定圖G的一棵生成樹．9．無向圖G存在歐拉回路，當(dāng)且僅當(dāng)G所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)且連通．10．設(shè)個體域D＝{1,2}，則謂詞公式xA(x)消去量詞后的等值式為A(1)A(2)．邏輯公式翻譯（每小題6分，本題共12分）11．將語句“如果小李學(xué)習(xí)努力，那么他就會取得好成績．”翻譯成命題公式．12．將語句“小張學(xué)習(xí)努力，小王取得好成績．”翻譯成命題公式．11．設(shè)P：小李學(xué)習(xí)努力，Q：小李會取得好成績，（2分）PQ．（6分）12．設(shè)P：小張學(xué)習(xí)努力，Q：小王取得好成績，（2分）PQ．（6分）判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由．13．如果R1和R2是A上的自反關(guān)系，則R1R2是自反的．14．如圖二所示的圖中存在一條歐拉回路． 圖二13．正確．（3分）R和R是自反的，xA，<x,x>R，<x,x>R， 1 2 1 2則<x,x>RR2，所以RR2自反的．（7分）114．正確．（3分）因為圖G為連通的，且其中每個頂點(diǎn)的度數(shù)為偶數(shù)．（7分）五．計算題（每小題12分，本題共36分）15．設(shè)A={{2},1,2}，B={1,{1,2}}，試計算（1）（AB）；（2）（A∩B）；（3）A×B．16．設(shè)G=<V，E>，V={v，v，v，v，v}，E={(v,v)，(v,v)，(v,v)，(v,v)，(v,v)}，試 1 2 3 4 5 13 23 24 34 35（1）給出G的圖形表示；（2）寫出其鄰接矩陣；（3）求出每個結(jié)點(diǎn)的度數(shù)；（4）畫出其補(bǔ)圖的圖形．17．設(shè)謂詞公式x(A(x,y)zB(x,y,z))yC(y,z)，試寫出量詞的轄域；（2）指出該公式的自由變元和約束變元．15．（1）AB={2,{2}}（4分）A∩B={1}（8分）A×B={<{2},1>，<{2},{1,2}>，<1,1>，<1,{1,2}>，<2,1>，<2,{1,2}>}（12分）16．（1）G的圖形表示如圖三： v1 5 v3 v4圖三（3分）（2）鄰接矩陣：00001101001101101100001（6分）00（3）v，v，v，v，v結(jié)點(diǎn)的度數(shù)依次為1，2，4，2，1（9分） 1 2 3 4 5（4）補(bǔ)圖如圖四：v 1 v2v5圖四（12分）17．（1）x量詞的轄域為(A(x,y)zB(x,y,z))，（2分）z量詞的轄域為B(x,y,z),（4分）y量詞的轄域為C(y,z)．（6分）（2）自由變元為(A(x,y)zB(x,y,z))中的y，以及C(y,z)中的z（9分）約束變元為(A(x,y)zB(x,y,z))中的x與B(x,y,z)中的z，以及C(y,z)中的y．（12分）六、證明題（本題共8分）18．試證明集合等式A(BC)=(AB)(AC)．18．證明：設(shè)S=A(BC)，T=(AB)(AC)，若x∈S，則x∈A或x∈BC，（1分）即x∈A或x∈B且x∈A或x∈C．（2分）也即x∈AB且x∈AC，（3分）即x∈T，所以ST．（4分）反之，若x∈T，則x∈AB且x∈AC，（5分）即x∈A或x∈B且x∈A或x∈C，（6分）也即x∈A或x∈BC，即x∈S，所以TS．（7分）因此T=S．（8分）2011年1月一、單項選擇題（每小題3分，本題共15分）1．D2．B3．C4．A5．B1．若集合A={a，b}，B={a，{a，b}}，則（）．A．ABB．ABC．ABD．AB2．集合A={x|x為小于10的自然數(shù)}，集合A上的關(guān)系R={<x，y>|x+y=10且x,yA}，則R的性質(zhì)為（）．A．自反的B．對稱的C．傳遞且對稱的D．反自反且傳遞的3．設(shè)有向圖（a）、（b）、（c）與（d）如圖一所示，則下列結(jié)論成立的是()．圖一A．（a）僅為弱連通的B．（b）僅為弱連通的C．（c）僅為弱連通的D．（d）僅為弱連通的4．設(shè)圖G的鄰接矩陣為011001001110000 0100101010則G的邊數(shù)為()．A．5B．6C．7D．85．下列公式()為永真式．A．PQPQB．(P(QP))(P(PQ))C．(Q(PQ))(Q(PQ))D．(P(PQ))Q二、填空題（每小題3分，本題共15分）6．設(shè)集合A＝{1，2，3}，那么集合A的冪集是{,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}．7．設(shè)A={a，b}，B={1，2}，作f：A→B，則不同的函數(shù)個數(shù)為4．8．若A={1,2}，R={<x,y>|xA,yA,x+y<4}，則R的自反閉包為{<1,1>,<2,2>,<1,2>,<2,1>}．9．無向連通圖在結(jié)點(diǎn)數(shù)v與邊數(shù)e滿足e=v-1關(guān)系時是樹．10．(x)(A(x)→B(x))∨C(x，y)中的自由變元為C(x，y)中的x與y．邏輯公式翻譯（每小題6分，本題共12分）11．將語句“他們?nèi)ヂ糜?，僅當(dāng)明天天晴．”翻譯成命題公式．12．將語句“今天沒有下雪．”翻譯成命題公式．11．設(shè)P：他們?nèi)ヂ糜?，Q：明天天晴，（2分）P→Q．（6分）12．設(shè)P：今天下雪，（2分）P．（6分）判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由．13．漢密爾頓圖一定是歐拉圖．（7分）圖二14．下面的推理是否正確，試予以說明．（x）（F（x）→G（y））前提引入F（y）→G（y）ES（1）．1、錯誤．（3分）（2）應(yīng)為F（a）→G（y），換名時，約束變元與自由變元不能混淆．（7分）五．計算題（每小題12分，本題共36分）15．設(shè)A={0，1，2，3，4，5，6}，R={<x，y>|xA，yA且x+y<1}，S={<x，y>|xA，yA且x+y3}，試求R，S，R?S，R-1，S-1，r(R)．.........資料.....資料.........資料....R={<0,0>}（2分）S={<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>}（4分）R?S={<0,0>,<0,1>,<0,2>,<0,3>}（6分）R-1={<0,0>}（8分）S-1=S（10分）r(R)=I．（12分）A 16．畫一棵帶權(quán)為1,2,2,3,的最優(yōu)二叉樹6 ,計算它們的權(quán)．最優(yōu)二叉樹如圖四：143685 1 2 2 3圖四（10分）權(quán)為：13+23+23+33+61=30（12分）注:其他正確的最優(yōu)二叉樹參照給分．17．求（P∨Q）→（R∨Q）的析取范式，合取范式．（P∨Q）→（R∨Q）（P∨Q）∨（R∨Q）（4分）(P∧Q)∨（R∨Q）(P∨R∨Q)∧(Q∨R∨Q)(P∨R∨Q)析取、合取范式（12分）注:其他正確答案參照給分．六、證明題（本題共8分）18．試證明集合等式A(BC)=(AB)(AC)．證明：設(shè)S=A∩(B∪C)，T=(A∩B)∪(A∩C)，若x∈S，則x∈A且x∈B∪C，即x∈A且x∈B或x∈A且x∈C，也即x∈A∩B或x∈A∩C，即x∈T，所以ST．（4分）反之，若x∈T，則x∈A∩B或x∈A∩C，即x∈A且x∈B或x∈A且x∈C也即x∈A且x∈B∪C，即x∈S，所以TS．因此T=S．（8分）2010年7月一、單項選擇題（每小題3分，本題共15分）1．B2．D3．B4．C5．B1．若集合A={1，{2}，{1，2}}，則下列表述正確的是()．A．2AB．{1}AC．1AD．2A2．已知一棵無向樹T中有8個頂點(diǎn)，4度、3度、2度的分支點(diǎn)各一個，T的樹葉數(shù)為()．A．6B．4C．3D．53．設(shè)無向圖G的鄰接矩陣為0111110011,10000 1100111010則G的邊數(shù)為()．A．1B．7C．6D．144．設(shè)集合A={a}，則A的冪集為()．A．{{a}}B．{a，{a}}C．{，{a}}D．{，a}5．下列公式中()為永真式．A．ABABB．AB(AB)C．ABABD．AB(AB)填空題（每小題3分，本題共15分）6．命題公式PP的真值是假（或F，或0）．7．若無向樹T有5個結(jié)點(diǎn)，則T的邊數(shù)為4．8．設(shè)正則m叉樹的樹葉數(shù)為t，分支數(shù)為i，則(m-1)i=t-1．9．設(shè)集合A={1，2}上的關(guān)系R＝{<1,1>,<1,2>}，則在R中僅需加一個元素<2,1>，就可使新得到的關(guān)系為對稱的．10．(x)(A(x)→B(x，z)∨C(y))中的自由變元有z，y．邏輯公式翻譯（每小題6分，本題共12分）11．將語句“今天上課．”翻譯成命題公式．設(shè)P：今天上課，（2分）則命題公式為：P．（6分）12．將語句“他去操場鍛煉，僅當(dāng)他有時間．”翻譯成命題公式．設(shè)P：他去操場鍛煉，Q：他有時間，（2分）則命題公式為：PQ．（6分）判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由．13．設(shè)集合A={1，2}，B={3，4}，從A到B的關(guān)系為f={<1,3>}，則f是A到B的函數(shù)．14．設(shè)G是一個有4個結(jié)點(diǎn)10條邊的連通圖，則G為平面圖．13．錯誤．（3分）因為A中元素2沒有B中元素與之對應(yīng)，故f不是A到B的函數(shù)．（7分）14．錯誤．（3分）不滿足“設(shè)G是一個有v個結(jié)點(diǎn)e條邊的連通簡單平面圖，若v≥3，則e≤3v-6．”（7分）五．計算題（每小題12分，本題共36分）15．試求出（P∨Q）→（R∨Q）的析取范式．（P∨Q）→（R∨Q）┐(P∨Q)∨（R∨Q）（4分）(┐P∧┐Q)∨（R∨Q）（8分）(┐P∧┐Q)∨R∨Q（析取范式）（12分）16．設(shè)A={{1},1,，2}B={1,{2}}，試計算（1）A∩B（2）A∪B（3）A（A∩B）．A∩B={1}（4分）A∪B={1,2,{1},{2}}（8分）A（A∩B）={{1},2}（12分）17．圖G=<V,E>，其中V={a,b,c,d}，E={(a,b),a(,c),a(,d),b(,c),b(,d),c(,d)}，對應(yīng)邊的權(quán)值依次為1、2、3、1、4及5，試（1）畫出G的圖形；寫出G的鄰接矩陣；求出G權(quán)最小的生成樹及其權(quán)值．242415 b 1 c 圖一（3分）鄰接矩陣：01111011（6分）1101 111024最小的生成樹如圖二中的粗線所示： 151c（10分）權(quán)為：1+1+3=5圖二（12分）六、證明題（本題共8分）18．試證明：若R與S是集合A上的自反關(guān)系，則R∩S也是集合A上的自反關(guān)系．證明：設(shè)xA，因為R自反，所以xRx，即<x,x>R；.........資料.....資料.........資料....又因為S自反，所以xRx，即<x,x>S．（4分）即<x,x>R∩S（6分）故R∩S自反．（8分）2010年1月一、單項選擇題（每小題3分，本題共15分）1．A2．C3．B4．B5．D1．若集合A＝{a，{a}}，則下列表述正確的是()．A．{a}AB．{{{a}}}AC．{a，{a}}AD．A2．命題公式（P∨Q）的合取范式是()A．（P∧Q）B．（P∧Q）∨（P∨Q）C．（P∨Q）D．（P∧Q）3．無向樹T有8個結(jié)點(diǎn)，則T的邊數(shù)為()．A．6B．7C．8D．94．圖G如圖一所示，以下說法正確的是()．A．a(chǎn)是割點(diǎn)B．{b,c}是點(diǎn)割集C．{b,d}是點(diǎn)割集D．{c}是點(diǎn)割集圖一5．下列公式成立的為()．A．P∧QP∨QB．PQPQC．QPPD．P∧(P∨Q)Q二、填空題（每小題3分，本題共15分）6．設(shè)集合A={2,3,4}，B={1,2,3,，4}R是A到B的二元關(guān)系，R{x,yxA且yB且xy}則R的有序?qū)蠟閧<2,2>，<2,3>，<2,4>，<3,3>}，<3,4>，<4,4>}．7．如果R是非空集合A上的等價關(guān)系，aA，bA，則可推知R中至少包含<a,a>，<b,b>等元素．8．設(shè)G＝<V,E>是有4個結(jié)點(diǎn)，8條邊的無向連通圖，則從G中刪去5條邊，可以確定圖G的一棵生成樹．9．設(shè)G是具有n個結(jié)點(diǎn)m條邊k個面的連通平面圖，則m等于n+k2．10．設(shè)個體域D＝{1,2}，A(x)為“x大于1”，則謂詞公式(x)A(x)的真值為真（或T，或1）．邏輯公式翻譯（每小題6分，本題共12分）11．將語句“今天考試，明天放假．”翻譯成命題公式．設(shè)P：今天考試，Q：明天放假．（2分）則命題公式為：P∧Q．（6分）12．將語句“我去旅游，僅當(dāng)我有時間．”翻譯成命題公式．設(shè)P：我去旅游，Q：我有時間，（2分）則命題公式為：PQ．（6分）判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由．13．如果圖G是無向圖，且其結(jié)點(diǎn)度數(shù)均為偶數(shù)，則圖G是歐拉圖．錯誤．（3分）當(dāng)圖G不連通時圖G不為歐拉圖．（7分）14．若偏序集<A，R>的哈斯圖如圖二所示，則集合A的最大元為a，最小元是f．圖二錯誤．（3分）集合A的最大元與最小元不存在，15．設(shè)謂詞公式(x)(A(x,y)(z)B(y,x,z))，試（1）寫出量詞的轄域；（2）指出該公式的自由變元和約束變元．x量詞的轄域為(A(x,y)(z)B(y,x,z))，（3分）z量詞的轄域為B(y,x,z),（6分）自由變元為(A(x,y)(z)B(y,x,z))中的y，（9分）約束變元為x與z．（12分）16．設(shè)集合A={{1},1,2}，B={1,{1,2}}，試計算（1）（AB）；（2）（A∩B）；（3）A×B．AB={{1},2}（4分）A∩B={1}（8分）A×B={<{1},1>，<{1},{1,2}>，<1,1>，<1,{1,2}>，<2,1>，<2,{1,2}>}（12分）17．設(shè)G=<V，E>，V={v，v，v，v}，E，試 1 2 3 4（1）給出G的圖形表示；（2）寫出其鄰接矩陣；（3）求出每個結(jié)點(diǎn)的度數(shù)；（4）畫出其補(bǔ)圖的圖形．（1）G的圖形表示為(如圖三)：圖三（2）鄰接矩陣：001000111101（6分） 0110 （3）v，v，v，v結(jié)點(diǎn)的度數(shù)依次為1，2，3，2（9分）（4）圖圖所：圖四（3分）（12分）18．設(shè)A，B是任意集合，試證明：若AA=BB，則A=B．證明：設(shè)xA，則<x，x>AA，（1分）因為AA=BB，故<x，x>BB，則有xB，（3分）所以AB．（5分）設(shè)xB，則<x，x>BB，（6分）因為AA=BB，故<x，x>AA，則有xA，所以BA．（7分）故得A=B．（8分）2009年10月一、單項選擇題（每小題3分，本題共15分）1．D2．C3．B4．C5．A1．若G是一個漢密爾頓圖，則G一定是()．A．平面圖B．對偶圖C．歐拉圖D．連通圖2．集合A={1,2,3,上的關(guān)系4} R={<x，y>|x=y且x,yA}，則R的性質(zhì)為（）．A．不是自反的B．不是對稱的C．傳遞的D．反自反3．設(shè)集合A={1，2，3，4，5}，偏序關(guān)系是A上的整除關(guān)系，則偏序集<A，>上的元素5是集合A的（）．A．最大元B．極大元C．最小元D．極小元4．圖G如圖一所示，以下說法正確的是()．A．{(a,d)}是割邊B．{(a,d)}是邊割集C．{(a,d),b,d()}是邊割集D．{(b,d)}是邊割集圖一5．設(shè)A（x）：x是人，B（x）：x是工人，則命題“有人是工人”可符號化為（）．A．(x)(A(x)∧B(x))B．(x)(A(x)∧B(x))C．┐(x)(A(x)→B(x))D．┐(x)(A(x)∧┐B(x))填空題（每小題3分，本題共15分）6．若集合A={1，3，5，7}，B={2，4，6，8}，則A∩B=空集（或）．7．設(shè)集合A={1，2，3}上的函數(shù)分別為：f={<1,2>,<2,1>,<3,3>,，}g={<1,3>,<2,2>,<3,2>,，則復(fù)合}函數(shù)gf={<1,2>,<2,3>,<3,2>,}．8．設(shè)G是一個圖，結(jié)點(diǎn)集合為V，邊集合為E，則G的結(jié)點(diǎn)度數(shù)之和為2|E|（或“邊數(shù)的兩倍”）．9．無向連通圖G的結(jié)點(diǎn)數(shù)為v，邊數(shù)為e，則G當(dāng)v與e滿足e=v-1關(guān)系時是樹．10．設(shè)個體域D＝{1,2,，3}P(x)為“x小于2”，則謂詞公式(x)P(x)的真值為假（或F，或0）．邏輯公式翻譯（每小題6分，本題共12分）11．將語句“他是學(xué)生．”翻譯成命題公式．設(shè)P：他是學(xué)生，（2分）則命題公式為：P．（6分）12．將語句“如果明天不下雨，我們就去郊游．”翻譯成命題公式．設(shè)P：明天下雨，Q：我們就去郊游，（2分）則命題公式為：PQ．判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由．13．下面的推理是否正確，試予以說明．（x）F（x）→G（x）前提引入F（y）→G（y）US（1）．錯誤．（3分）（2）應(yīng)為F（y）→G（x），換名時，約束變元與自由變元不能混淆．（7分）14．如圖二所示的圖G存在一條歐拉回路．圖二錯誤．（3分）因為圖G為中包含度數(shù)為奇數(shù)的結(jié)點(diǎn)．（7分）五．計算題（每小題12分，本題共36分）15．求（P∨Q）→R的析取范式與合取范式．（P∨Q）→R（P∨Q）∨R（4分）(P∧Q)∨R（析取范式）（8分）(P∨R)∧(Q∨R)（合取范式）（12分）16．設(shè)A={0，1，2，3}，R={<x，y>|xA，yA且x+y<0}，S={<x，y>|xA，yA且x+y2}，試求R，S，R?S，S-1，r(R)．R=,S={<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<2,0>}（3分）R?S=，（6分）S-1=S，（9分）r(R)=I={<0,0>,<1,1>,<2,2>,<3,3>}．（12分）A17．畫一棵帶權(quán)為1,2,2,3,的最優(yōu)二叉樹4 ,計算它們的權(quán)．最優(yōu)二叉樹如圖三所示 12 7 5 23（10分） 1 2圖三權(quán)為13+23+22+32+42=27（12分）六、證明題（本題共8分）18．試證明集合等式A(BC)=(AB)(AC)．證明：設(shè)S=A(BC)，T=(AB)(AC)，若x∈S，則x∈A或x∈BC，即x∈A或x∈B且x∈A或x∈C．也即x∈AB且x∈AC，即x∈T，所以ST．（4分）反之，若x∈T，則x∈AB且x∈AC，即x∈A或x∈B且x∈A或x∈C，也即x∈A或x∈BC，即x∈S，所以TS．因此T=S．2009年7月一、單項選擇題（每小題3分，本題共15分）1．A2．B3．B4．D5．C1．若集合A={a，b}，B={a，b，{a，b}}，則（）．A．AB，且ABB．AB，但ABC．AB，但ABD．AB，且AB2．集合A={1,2,3,4,5,6,7,上的關(guān)系8}R={<x，y>|x+y=10且x,yA}，則R的性質(zhì)為（）．A．自反的B．對稱的C．傳遞且對稱的D．反自反且傳遞的3．如果R和R是A上的自反關(guān)系，則R∪R，R∩R，R-R中自反關(guān)系有（）個． 1 21 2 1 2A．0B．2C．D．34．如圖一所示，以下說法正確的是()．A．{(a,e)}是割邊B．{(a,e)}是邊割集C．{(a,e),b,c()}是邊割集D．{(d,e)}是邊割集圖一5．設(shè)A（x）：x是人，B（x）：x是學(xué)生，則命題“不是所有人都是學(xué)生”可符號化為（）．A．(x)(A(x)∧B(x))B．┐(x)(A(x)∧B(x))C．┐(x)(A(x)→B(x))D．┐(x)(A(x)∧┐B(x))二、填空題（每小題3分，本題共15分）6．若集合A的元素個數(shù)為10，則其冪集的元素個數(shù)為1024．7．設(shè)A={a，b，c}，B={1，2}，作f：A→B，則不同的函數(shù)個數(shù)為8．8．若A={1,2}，R={<x,y>|xA,yA,x+y=10}，則R的自反閉包為{<1,1>,<2,2>}．9．結(jié)點(diǎn)數(shù)v與邊數(shù)e滿足e=v-1關(guān)系的無向連通圖就是樹．10．設(shè)個體域D＝{a,b,c}，則謂詞公式(x)A(x)消去量詞后的等值式為