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

電大歷年離散數(shù)學試題匯總電大歷年離散數(shù)學試題匯總/電大歷年離散數(shù)學試題匯總計算機科學與技術(shù)專業(yè)級第二學期離散數(shù)學試題2012年1月一、單項選擇題（每小題3分，本題共15分）1．C2．C3．B4．A5．D1．若集合A的元素個數(shù)為10，則其冪集的元素個數(shù)為（）．A．10B．100C．1024D2．設(shè){a,b}，{1,2}，R1，R2，R3是A到B的二元關(guān)系，且R1={<a，2>,<a，1>}，R2={<a，1>,<a，2>,<b，1>}，R3={<a，1>,<b，2>}，則（）是從A到B的函數(shù)．A．R1和R2B．R2C．R3D．R13．設(shè){1,2,3,4,5,6,7,8}，R是A上的整除關(guān)系，{2,4,6}，則集合B的最大元、最小元、上界、下界依次為()．A．8、2、8、2B．無、2、無、2C．6、2、6、2D．8、1、6、1 4．若完全圖G中有n個結(jié)點(n≥2)，m條邊，則當（）時，圖G中存在歐拉回路．A．n為奇數(shù)B．n為偶數(shù)C．m為奇數(shù)D．m為偶數(shù) 5．已知圖G的鄰接矩陣為則G有（）．A．6點，8邊B．6點，6邊C．5點，8邊D．5點，6邊 二、填空題（每小題3分，本題共15分）6．設(shè)集合A＝{a}，那么集合A的冪集是{,{a}}．7．若R1和R2是A上的對稱關(guān)系，則R1∪R2，R1∩R2，R12，R21中對稱關(guān)系有4個．8．設(shè)圖G是有5個結(jié)點的連通圖，結(jié)點度數(shù)總和為10，則可從G中刪去1條邊后使之變成樹．9．設(shè)連通平面圖G的結(jié)點數(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分）abcd圖一13．若偏序集<A，R>的哈斯圖如圖一所示，則集合A的最大元為a，極小元不存在．錯誤．（3分）對于集合A的任意元素x，均有<x,a>R（或），所以a是集合A中的最大元．（5分）但按照極小元的定義，在集合A中均是極小元．（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∧（P→┐Q）∨P為真，所以┐P∧（P→┐Q）∨P是永真式．（7分）另種說明：┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）與P組成的析取式，只要其中一項為真，則整個公式為真．（5分）可以看到，不論P的值為真或為假，┐P∧（P→┐Q）與P總有一個為真，所以┐P∧（P→┐Q）∨P是永真式．（7分）或用等價演算┐P∧（P→┐Q）∨PT五．計算題（每小題12分，本題共36分）15．設(shè)集合{1，2，3，4}，{<x,y>,yA；1或x0}，試（1）寫出R的有序?qū)Ρ硎?；?）畫出R的關(guān)系圖；（3）說明R滿足自反性，不滿足傳遞性．15．（1）{<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>}（3分）（2）關(guān)系圖如圖二：圖二（6分）（3）因為<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è)圖<V，E>，{v1，v2，v3，v4，v5}，{(v1,v2)，(v1,v3)，(v2,v4)，(v3,v5)，(v4,v5)}，試畫出G的圖形表示；寫出其鄰接矩陣；v1v2v3v4圖三v5(4)畫出圖G的補圖的圖形．16．（1）關(guān)系圖如圖三：（3分）（2）鄰接矩陣（6分）（3）(v1)=2(v2)=2(v3)=2(v4)=2v1v2v1v2v3v4圖四v5（4）補圖如圖四（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度頂點，4個3度頂點，其它頂點的度數(shù)均小于3，試說明G中可能有的頂點數(shù)．證明：可利用數(shù)列可圖化與握手定理解答頂點度數(shù)和為214=28，（2分）28-（34+43）=4，則知其他頂點度數(shù)和為4，（4分）對于有限圖，若無零度頂點，則除4度與3度頂點外，可能的頂點情況有：2個2度點；1個2度點和2個1度點；4個1度點，（6分）即對應(yīng)圖的頂點數(shù)分別至少為9、10、11．（8分）2011年7月一、單項選擇題（每小題3分，本題共15分）1．A2．C3．C4．D5．B1．若集合{1，{1}，{2}，{1，2}}，則下列表述正確的是()．A．{2}AB．{1，2}AC．1AD．22．設(shè)G為無向圖，則下列結(jié)論成立的是()．A．無向圖G的結(jié)點的度數(shù)等于邊數(shù)的兩倍．B．無向圖G的結(jié)點的度數(shù)等于邊數(shù)．C．無向圖G的結(jié)點的度數(shù)之和等于邊數(shù)的兩倍．D．無向圖G的結(jié)點的度數(shù)之和等于邊數(shù)．a(chǎn)bcdabcdefA．{(a，b)}是邊割集B．{a，c}是點割集C．uce9cfj是點割集D．{(c，d)}是邊割集圖一 4．設(shè)集合{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．命題公式的真值是真（或T，或1）．7．若無向圖T是連通的，則T的結(jié)點數(shù)v與邊數(shù)e滿足關(guān)系1時，T是樹．8．無向圖G是歐拉圖的充分必要條件是G是連通的且結(jié)點度數(shù)都是偶數(shù)．9．設(shè)集合{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è)集合{1，2}，{3，4}，從A到B的關(guān)系為{<1,3>，<1,4>}，則f是A到B的函數(shù)．錯誤．（3分）因為A中元素1有B中兩個不同的元素與之對應(yīng)，故f不是A到B的函數(shù)．（7分）14．設(shè)G是一個連通平面圖，有5個結(jié)點9條邊，則G有6個面．正確．（3分）因G是一個連通平面圖，滿足歐拉定理，有2，所以2-（）=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è){{1},{1,2}，1}，{1,2,{2}}，試計算（1）（A∩B）（2）（A∪B）（3）（A∩B）A．（1）（A∩B）={1}（4分）（2）（A∪B）={1,2,{1},{2},{1,2}}（8分）（3）（A∩B）A=（12分）17．試畫一棵帶權(quán)為2,3,3,4,5,的最優(yōu)二叉樹,并計算該最優(yōu)二叉樹的權(quán)．最優(yōu)二叉樹如圖二所示．23345510717（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分）中央廣播電視大學2010—2011學年度第一學期“開放本科”期末考試離散數(shù)學（本）試題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．(v)=2EB．(v)=EC．D．3．如圖一所示，以下說法正確的是()．A．(e,c)是割邊B．(d,e)是割邊abcd圖一abcd圖一e4．命題公式（P∨Q）的合取范式是()．A．PB．（P∧Q）C．（P∨P）D．（P∨Q）5．下列等價公式成立的為()．A．PQPQ B．QPPQC．PPQQD．PPQ 二、填空題（每小題3分，本題共15分）6．設(shè)集合{0,1,2}，{1,2,3,4,}，R是A到B的二元關(guān)系， 則R的有序?qū)蠟閧<1,1>，<1,2>，<2,1>，<2,2>}．7．設(shè)G是連通平面圖，v,e,r分別表示G的結(jié)點數(shù)，邊數(shù)和面數(shù)，則v，e和r滿足的關(guān)系式2．8．設(shè)G＝<V,E>是有20個結(jié)點，25條邊的連通圖，則從G中刪去6條邊，可以確定圖G的一棵生成樹．9．無向圖G存在歐拉回路，當且僅當G所有結(jié)點的度數(shù)全為偶數(shù)且連通．10．設(shè)個體域D＝{1,2}，則謂詞公式消去量詞后的等值式為A(1)A(2)．三、邏輯公式翻譯（每小題6分，本題共12分）11．將語句“如果小李學習努力，那么他就會取得好成績．”翻譯成命題公式．12．將語句“小張學習努力，小王取得好成績．”翻譯成命題公式．11．設(shè)P：小李學習努力，Q：小李會取得好成績，（2分）PQ．（6分）12．設(shè)P：小張學習努力，Q：小王取得好成績，（2分）PQ．（6分）四、判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由．13．如果R1和R2是A上的自反關(guān)系，則R1R2是自反的．14．如圖二所示的圖中存在一條歐拉回路．圖二13．正確．（3分）R1和R2是自反的，xA，<x,x>R1，<x,x>R2，則<x,x>R1R2，所以R1R2是自反的．（7分）14．正確．（3分）因為圖G為連通的，且其中每個頂點的度數(shù)為偶數(shù)．（7分）五．計算題（每小題12分，本題共36分）15．設(shè){{2},1,2}，{1,{1,2}}，試計算（1）（AB）；（2）（A∩B）；（3）A×B．16．設(shè)<V，E>，{v1，v2，v3，v4，v5}，{(v13)，(v23)，(v24)，(v34)，(v35)}，試（1）給出G的圖形表示；（2）寫出其鄰接矩陣；（3）求出每個結(jié)點的度數(shù)；（4）畫出其補圖的圖形．17．設(shè)謂詞公式，試（1）寫出量詞的轄域；（2）指出該公式的自由變元和約束變元．15．（1）AB={2,{2}}（4分）（2）A∩B={1}（8分）（3）A×{<{2},1>，<{2},{1,2}>，<1,1>，<1,{1,2}>，<2,1>，<2,{1,2}>}（12分）v1v2v1v2v3v4圖三v5（3分）（2）鄰接矩陣：（6分）（3）v1，v2，v3，v4，v5結(jié)點的度數(shù)依次為1，2，4，2，1（9分）v1v2v3v4圖四v5（12分）17．（1）x量詞的轄域為，（2分）z量詞的轄域為,（4分）y量詞的轄域為．（6分）（2）自由變元為中的y，以與中的z（9分）約束變元為中的x與中的z，以與中的y．（12分）六、證明題（本題共8分）18．試證明集合等式A(BC)=(AB)(AC)．18．證明：設(shè)A(BC)，(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分）因此．（8分）2011年1月一、單項選擇題（每小題3分，本題共15分）1．D2．B3．C4．A5．B1．若集合{a，b}，{a，{a，b}}，則（）．A．ABB．ABC．ABD．AB 2．集合{為小于10的自然數(shù)}，集合A上的關(guān)系{<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的鄰接矩陣為 則G的邊數(shù)為()． A．5B．6C．7D． 5．下列公式()為永真式．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，b}，{1，2}，作f：A→B，則不同的函數(shù)個數(shù)為4．8．若{1,2}，{<x,y>A,yA,<4}，則R的自反閉包為{<1,1>,<2,2>,<1,2>,<2,1>}．9．無向連通圖在結(jié)點數(shù)v與邊數(shù)e滿足1關(guān)系時是樹．10．(x)(A(x)→B(x))∨C(x，y)中的自由變元為C(x，y)中的x與y．三、邏輯公式翻譯（每小題6分，本題共12分）11．將語句“他們?nèi)ヂ糜?，僅當明天天晴．”翻譯成命題公式．12．將語句“今天沒有下雪．”翻譯成命題公式．11．設(shè)P：他們?nèi)ヂ糜?，Q：明天天晴，（2分）P→Q．（6分）12．設(shè)P：今天下雪，（2分）P．（6分）四、判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由．13．漢密爾頓圖一定是歐拉圖．圖二存在漢密爾頓圖不是歐拉圖．（5分）反例見圖二．（7分）14．下面的推理是否正確，試予以說明．(1)（x）（F（x）→G（y））前提引入(2)F（y）→G（y）（1）．1、錯誤．（3分）（2）應(yīng)為F（a）→G（y），換名時，約束變元與自由變元不能混淆．（7分）五．計算題（每小題12分，本題共36分）15．設(shè){0，1，2，3，4，5，6}，{<x，y>A，yA且<1}，{<x，y>A，yA且3}，試求R，S，RS，1，1，r(R)．{<0,0>}（2分）{<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>}（4分）R{<0,0>,<0,1>,<0,2>,<0,3>}（6分）1={<0,0>}（8分）1=S（10分）r(R)．（12分）16．畫一棵帶權(quán)為1,2,2,3,6的最優(yōu)二叉樹,計算它們的權(quán)．14最優(yōu)二叉樹如圖四：148866535332322121圖四（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è)∩(B∪C)，(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．因此．（8分）2010年7月一、單項選擇題（每小題3分，本題共15分）1．B2．D3．B4．C5．B1．若集合{1，{2}，{1，2}}，則下列表述正確的是()．A．2AB．{1}C．1AD．22．已知一棵無向樹T中有8個頂點，4度、3度、2度的分支點各一個，T的樹葉數(shù)為()．A．6B．4C．3D 3．設(shè)無向圖G的鄰接矩陣為 ,則G的邊數(shù)為()． A．1B．7C．6D． 4．設(shè)集合{a}，則A的冪集為()．A．{{a}}B．{a，{a}}C．{，{a}}D．{，a} 5．下列公式中()為永真式．A．ABABB．AB(AB)C．ABABD．AB(AB) 二、填空題（每小題3分，本題共15分）6．命題公式的真值是假（或F，或0）．7．若無向樹T有5個結(jié)點，則T的邊數(shù)為4．8．設(shè)正則m叉樹的樹葉數(shù)為t，分支數(shù)為i，則(1)1．9．設(shè)集合{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．將語句“他去操場鍛煉，僅當他有時間．”翻譯成命題公式．設(shè)P：他去操場鍛煉，Q：他有時間，（2分）則命題公式為：PQ．（6分）四、判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由．13．設(shè)集合{1，2}，{3，4}，從A到B的關(guān)系為{<1,3>}，則f是A到B的函數(shù)．14．設(shè)G是一個有4個結(jié)點10條邊的連通圖，則G為平面圖．13．錯誤．（3分）因為A中元素2沒有B中元素與之對應(yīng)，故f不是A到B的函數(shù)．（7分）14．錯誤．（3分）不滿足“設(shè)G是一個有v個結(jié)點e條邊的連通簡單平面圖，若v≥3，則e≤36．”（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è){{1},1,2}，{1,{2}}，試計算（1）A∩B（2）A∪B（3）A（A∩B）．（1）A∩{1}（4分）（2）A∪{1,2,{1},{2}}（8分）（3）A（A∩B）={{1},2}（12分）17．圖<V,E>，其中{a,b,c,d}，{(a,b),(a,c),(a,d),(b,c),(b,d),(c,d)}，對應(yīng)邊的權(quán)值依次為1、2、3、1、4與5，試（1）畫出G的圖形；（2）寫出G的鄰接矩陣；（3）求出G權(quán)最小的生成樹與其權(quán)值．圖一a圖一abcd112453（3分）（2）鄰接矩陣：圖二圖二abcd112453（3）最小的生成樹如圖二中的粗線所示：（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é)點，則T的邊數(shù)為()．A．6B．7 C．8 D． 4．圖G如圖一所示，以下說法正確的是()．A．a(chǎn)是割點B．{b,c}是點割集C．{b,d}是點割集D．{c}是點割集 圖一 5．下列公式成立的為()．A．P∧QP∨QB．PQPQC．QPPD．P∧(P∨Q)Q 二、填空題（每小題3分，本題共15分）6．設(shè)集合{2,3,4}，{1,2,3,4}，R是A到B的二元關(guān)系， 則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é)點，8條邊的無向連通圖，則從G中刪去5條邊，可以確定圖G的一棵生成樹．9．設(shè)G是具有n個結(jié)點m條邊k個面的連通平面圖，則m等于2．10．設(shè)個體域D＝{1,2}，A(x)為“x大于1”，則謂詞公式的真值為真（或T，或1）．三、邏輯公式翻譯（每小題6分，本題共12分）11．將語句“今天考試，明天放假．”翻譯成命題公式．設(shè)P：今天考試，Q：明天放假．（2分）則命題公式為：P∧Q．（6分）12．將語句“我去旅游，僅當我有時間．”翻譯成命題公式．設(shè)P：我去旅游，Q：我有時間，（2分）則命題公式為：PQ．（6分）四、判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由．13．如果圖G是無向圖，且其結(jié)點度數(shù)均為偶數(shù)，則圖G是歐拉圖．錯誤．（3分）當圖G不連通時圖G不為歐拉圖．（7分）14．若偏序集<A，R>的哈斯圖如圖二所示，則集合A的最大元為a，最小元是f．圖二錯誤．（3分）集合A的最大元與最小元不存在，a是極大元，f是極小元，．（7分）五．計算題（每小題12分，本題共36分）15．設(shè)謂詞公式，試（1）寫出量詞的轄域；（2）指出該公式的自由變元和約束變元．（1）x量詞的轄域為，（3分）z量詞的轄域為,（6分）（2）自由變元為中的y，（9分）約束變元為x與z．（12分）16．設(shè)集合{{1},1,2}，{1,{1,2}}，試計算（1）（AB）；（2）（A∩B）；（3）A×B．（1）AB={{1},2}（4分）（2）A∩B={1}（8分）（3）A×{<{1},1>，<{1},{1,2}>，<1,1>，<1,{1,2}>，<2,1>，<2,{1,2}>}（12分）17．設(shè)<V，E>，{v1，v2，v3，v4}，{(v13)，(v23)，(v24)，(v34)}，試（1）給出G的圖形表示；（2）寫出其鄰接矩陣；（3）求出每個結(jié)點的度數(shù)；（4）畫出其補圖的圖形．（1）G的圖形表示為(如圖三)：（3分）圖三（2）鄰接矩陣：（6分）（3）v1，v2，v3，v4結(jié)點的度數(shù)依次為1，2，3，2（9分）（4）補圖如圖四所示：（12分）圖四六、證明題（本題共8分）18．設(shè)A，B是任意集合，試證明：若AB，則．證明：設(shè)xA，則<x，x>AA，（1分）因為AB，故<x，x>BB，則有xB，（3分）所以AB．（5分）設(shè)xB，則<x，x>BB，（6分）因為AB，故<x，x>AA，則有xA，所以BA．（7分）故得．（8分）2009年10月一、單項選擇題（每小題3分，本題共15分）1．D2．C3．B4．C5．A1．若G是一個漢密爾頓圖，則G一定是()．A．平面圖B．對偶圖C．歐拉圖D．連通圖 2．集合{1,2,3,4}上的關(guān)系{<x，y>且x,}，則R的性質(zhì)為（）．A．不是自反的B．不是對稱的C．傳遞的D．反自反 3．設(shè)集合{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．若集合{1，3，5，7}，{2，4，6，8}，則A∩空集（或）．7．設(shè)集合{1，2，3}上的函數(shù)分別為：{<1,2>,<2,1>,<3,3>,}，{<1,3>,<2,2>,<3,2>,}，則復合函數(shù)gf={<1,2>,<2,3>,<3,2>,}．8．設(shè)G是一個圖，結(jié)點集合為V，邊集合為E，則G的結(jié)點度數(shù)之和為2（或“邊數(shù)的兩倍”）．9．無向連通圖G的結(jié)點數(shù)為v，邊數(shù)為e，則G當v與e滿足1關(guān)系時是樹．10．設(shè)個體域D＝{1,2,3}，P(x)為“x小于2”，則謂詞公式(x)P(x)的真值為假（或F，或0）三、邏輯公式翻譯（每小題6分，本題共12分）11．將語句“他是學生．”翻譯成命題公式．設(shè)P：他是學生，（2分）則命題公式為：P．（6分）12．將語句“如果明天不下雨，我們就去郊游．”翻譯成命題公式．設(shè)P：明天下雨，Q：我們就去郊游，（2分）則命題公式為：PQ．四、判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由．13．下面的推理是否正確，試予以說明．(1)（x）F（x）→G（x）前提引入(2)F（y）→G（y）（1）．錯誤．（3分）（2）應(yīng)為F（y）→G（x），換名時，約束變元與自由變元不能混淆．（7分）14．如圖二所示的圖G存在一條歐拉回路．圖二錯誤．（3分）因為圖G為中包含度數(shù)為奇數(shù)的結(jié)點．（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è){0，1，2，3}，{<x，y>A，yA且<0}，{<x，y>A，yA且2}，試求R，S，RS，S-1，r(R)．,{<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<2,0>}（3分）R，（6分）S-1=S，（9分）r(R){<0,0>,<1,1>,<2,2>,<3,3>}．（12分）17．畫一棵帶權(quán)為1,2,2,3,4的最優(yōu)二叉樹,計算它們的權(quán)．1223347512（10分）圖三權(quán)為13+23+22+32+42=27（12分）六、證明題（本題共8分）18．試證明集合等式A(BC)=(AB)(AC)．證明：設(shè)A(BC)，(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．因此．2009年7月一、單項選擇題（每小題3分，本題共15分）1．A2．B3．B4．D5．C1．若集合{a，b}，{a，b，{a，b}}，則（）．A．AB，且ABB．AB，但ABC．AB，但ABD．AB，且AB 2．集合{1,2,3,4,5,6,7,8}上的關(guān)系{<x，y>10且x,}，則R的性質(zhì)為（）．A．自反的B．對稱的C．傳遞且對稱的D．反自反且傳遞的 3．如果R1和R2是A上的自反關(guān)系，則R1∪R2，R1∩R2，R12中自反關(guān)系有（）個．A．0B．2C．1 4．如圖一所示，以下說法正確的是()．A．{(a,e)}是割邊 B．{(a,e)}是邊割集C．{(a,e),(b,c)}是邊割集D．{(d,e)}是邊割集圖一 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的元素個數(shù)為10，則其冪集的元素個數(shù)為1024．7．設(shè){a，b，c}，{1，2}，作f：A→B，則不同的函數(shù)個數(shù)為8．8．若{1,2}，{<x,y>A,yA,10}，則R的自反閉包為{<1,1>,<2,2>}．9．結(jié)點數(shù)v與邊數(shù)e滿足1關(guān)系的無向連通圖就是樹．10．設(shè)個體域D＝{a,b,c}，則謂詞公式(x)A(x)消去量詞后的等值式為A(a)∧A(b)∧A（c）．三、邏輯公式翻譯（每小題6分，本題共12分）11．將語句“盡管他接受了這個任務(wù)，但他沒有完成好．”翻譯成命題公式．設(shè)P：他接受了這個任務(wù)，Q：他完成好了這個任務(wù)，（2分）PQ．（6分）12．將語句“今天沒有下雨．”翻譯成命題公式．設(shè)P：今天下雨，（2分）P．（6分）四、判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由．13．下面的推理是否正確，試予以說明．(1)（x）F（x）→G（x）前提引入(2)F（y）→G（y）（1）．錯誤．（3分）（2）應(yīng)為F（y）→G（x），換名時，約束變元與自由變元不能混淆．（7分）14．若偏序集<A，R>的哈斯圖如圖二所示，則集合A的最大元為a，最小元不存在．圖二錯誤．（3分）集合A的最大元不存在，a是極大元．（7分）五．計算題（每小題12分，本題共36分）15．求（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)∧R合取范式（12分）16．設(shè){0，1，2，3，4}，{<x，y>A，yA且<0}，{<x，y>A，yA且3}，試求R，S，RS，1，1，r(R)．,（2分）{<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>}（4分）R，（6分）1=，（8分）1=S，（10分）r(R)．（12分）17．畫一棵帶權(quán)為1,2,2,3,4的最優(yōu)二叉樹,計算它們的權(quán)．1223347512權(quán)為13+23+22+32+42=27（12分）六、證明題（本題共8分）18．設(shè)G是一個n階無向簡單圖，n是大于等于2的奇數(shù)．證明G與中的奇數(shù)度頂點個數(shù)相等(是G的補圖)．證明：因為n是奇數(shù)，所以n階完全圖每個頂點度數(shù)為偶數(shù)，（3分）因此，若G中頂點v的度數(shù)為奇數(shù)，則在中v的度數(shù)一定也是奇數(shù)，（6分）所以G與中的奇數(shù)度頂點個數(shù)相等．（8分）2008年7月一、單項選擇題（每小題3分，本題共15分）1．B2．B3．A4．C5．D1．設(shè){a,b}，{1,2}，R1，R2，R3是A到B的二元關(guān)系，且R1={<a，2>,<b，2>}，R2={<a，1>,<a，2>,<b，1>}，R3={<a，1>,<b，2>}，則（）不是從A到B的函數(shù)．A．R1和R2B．R2C．R3D．R12．設(shè){1,2,3,4,5,6,7,8}，R是A上的整除關(guān)系，{2,4,6}，則集合B的最大元、最小元、上界、下界依次為()．A．8、2、8、2B．無、2、無、2C．6、2、6、2D．8、1、6、1 3．若集合A的元素個數(shù)為10，則其冪集的元素個數(shù)為（）．A．1024B．10C．100D 4．設(shè)完全圖K有n個結(jié)點(n≥2)，m條邊，當（）時，K中存在歐拉回路．A．m為奇數(shù)B．n為偶數(shù)C．n為奇數(shù)D．m為偶數(shù) 5．已知圖G的鄰接矩陣為，則G有（）．A．5點，8邊B．6點，7邊C．6點，8邊D．5點，7邊 二、填空題（每小題3分，本題共15分）6．設(shè)集合A＝{a，b}，那么集合A的冪集是{,{},{a},}．7．如果R1和R2是A上的自反關(guān)系，則R1∪R2，R1∩R2，R12中自反關(guān)系有2個．8．設(shè)圖G是有6個結(jié)點的連通圖，結(jié)點的總度數(shù)為18，則可從G中刪去4條邊后使之變成樹．9．設(shè)連通平面圖G的結(jié)點數(shù)為5，邊數(shù)為6，則面數(shù)為3．10．設(shè)個體域D＝{a,b}，則謂詞公式(x)A(x)∧（x）B（x）消去量詞后的等值式為(A(a)∧A(b))∧(B（a）∨B（b）)．三、邏輯公式翻譯（每小題4分，本題共12分）11．將語句“如果所有人今天都去參加活動，則明天的會議取消．”翻譯成命題公式．設(shè)P：所有人今天都去參加活動，Q：明天的會議取消，（1分）PQ．（4分）12．將語句“今天沒有人來．”翻譯成命題公式．設(shè)P：今天有人來，（1分）P．（4分）13．將語句“有人去上課．”翻譯成謂詞公式．設(shè)P(x)：x是人，Q(x)：x去上課，（1分）(x)(P(x)Q(x))．四、判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由．14．┐P∧（P→┐Q）∨P為永真式．15．若偏序集<A，R>的哈斯圖如圖一所示，則集合A的最大元為a，最小元不存在．圖一14．正確．（3分）┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）與P組成的析取式，如果P的值為真，則┐P∧（P→┐Q）∨P為真，（5分）如果P的值為假，則┐P與P→┐Q為真，即┐P∧（P→┐Q）為真，也即┐P∧（P→┐Q）∨P為真，所以┐P∧（P→┐Q）∨P是永真式．（7分）另種說明：┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）與P組成的析取式，只要其中一項為真，則整個公式為真．（5分）可以看到，不論P的值為真或為假，┐P∧（P→┐Q）與P總有一個為真，所以┐P∧（P→┐Q）∨P是永真式．（7分）或用等價演算┐P∧（P→┐Q）∨PT15．正確．（3分）對于集合A的任意元素x，均有<x,a>R（或），所以a是集合A中的最大元．（5分）按照最小元的定義，在集合A中不存在最小元．（7分）五．計算題（每小題12分，本題共36分）16．設(shè)集合{1，2，3，4}，{<x,y>,yA；1或x0}，試（1）寫出R的有序?qū)Ρ硎?；?）畫出R的關(guān)系圖；（3）說明R滿足自反性，不滿足傳遞性．（1）{<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>}（3分）1234（6分）（3）因為<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分）17．求PQR的析取范式，合取范式、主析取范式，主合取范式．P→（R∨Q）┐P∨(R∨Q)┐P∨Q∨R（析取、合取、主合取范式）（9分）(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q∧R)∨(P∧┐Q∧┐R)∨(P∧┐Q∧R)∨(P∧Q∧┐R)∨(P∧Q∧R)（主析取范式）（12分）18．設(shè)圖<V，E>，{v1，v2，v3，v4，v5}，{(v1,v2)，(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)}，試畫出G的圖形表示；寫出其鄰接矩陣；(3)求出每個結(jié)點的度數(shù)；v1v2v1v2v3v4v5（1）關(guān)系圖（3分）（2）鄰接矩陣（6分）（3）(v1)=2(v2)=3(v3)=4(v4)=3v1v2v3v4v1v2v3v4v5（4）補圖（12分）六、證明題（本題共8分）19．試證明（x）（P（x）∧R（x））（x）P（x）∧（x）R（x）．證明：（1）（x）（P（x）∧R（x））P（2）P（a）∧R（a）(1)（2分）（3）P（a）