電大歷年離散數學試題匯總

-.z.計算機科學與技術專業(yè)級第二學期離散數學試題2012年1月一、單項選擇題（每小題3分，本題共15分）1．C2．C3．B4．A5．D1．若集合A的元素個數為10，則其冪集的元素個數為（）．A．10B．100C．1024D2．設A={a,b}，B={1,2}，R1，R2，R3是A到B的二元關系，且R1={<a，2>,<a，1>}，R2={<a，1>,<a，2>,<b，1>}，R3={<a，1>,<b，2>}，則（）是從A到B的函數．A．R1和R2B．R2C．R3D．R1和R3．設A={1,2,3,4,5,6,7,8}，R是A上的整除關系，B={2,4,6}，則集合B的最大元、最小元、上界、下界依次為()．A．8、2、8、2B．無、2、無、2C．6、2、6、2D．8、1、6、14．若完全圖G中有n個結點(n≥2)，m條邊，則當（）時，圖G中存在歐拉回路．A．n為奇數B．n為偶數C．m為奇數D．m為偶數5．已知圖G的鄰接矩陣為則G有（）．A．6點，8邊B．6點，6邊C．5點，8邊D．5點，6邊二、填空題（每小題3分，本題共15分）6．設集合A＝{a}，則集合A的冪集是{,{a}}．7．若R1和R2是A上的對稱關系，則R1∪R2，R1∩R2，R1-R2，R2-R1中對稱關系有4個．8．設圖G是有5個結點的連通圖，結點度數總和為10，則可從G中刪去1條邊后使之變成樹．9．設連通平面圖G的結點數為5，邊數為6，則面數為3．10．設個體域D＝{a,b}，則謂詞公式(*)(A(*)∧B（*））消去量詞后的等值式為(A(a)∧B(b))∧(A（a）∧B（b））．三、邏輯公式翻譯（每小題6分，本題共12分）11．將語句“今天有聯(lián)歡活動，明天有文藝晚會．”翻譯成命題公式．設P：今天有聯(lián)歡活動，Q：明天有文藝晚會，（2分）P∧Q．（6分）12．將語句“如果小王來，則小李去．”翻譯成命題公式．設P：小王來，Q：小李去（2分）P→Q．（6分）四、判斷說明題（每小題7分，本題共14分）abcd圖一13．若偏序集<A，R>的哈斯圖如圖一所示，則集合A的最大元為a，極小元不存在．錯誤．（3分）對于集合A的任意元素*，均有<*,a>R（或*Ra），所以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∧（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．設集合A={1，2，3，4}，R={<*,y>|*,yA；|*y|=1或*y=0}，試（1）寫出R的有序對表示；（2）畫出R的關系圖；（3）說明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分）（2）關系圖如圖二：圖二（6分）（3）因為<1,1>,<2,2>,<3,3>,<4,4>均屬于R，即A的每個元素構成的有序對均在R中，故R在A上是自反的．（9分）因有<2,3>與<3,4>屬于R，但<2,4>不屬于R，所以R在A上不是傳遞的．（12分）16．設圖G=<V，E>，V={v1，v2，v3，v4，v5}，E={(v1,v2)，(v1,v3)，(v2,v4)，(v3,v5)，(v4,v5)}，試畫出G的圖形表示；寫出其鄰接矩陣；v1v2v3v4圖三v5(4)畫出圖G的補圖的圖形．16．（1）關系圖如圖三：（3分）（2）鄰接矩陣（6分）（3）deg(v1)=2deg(v2)=2deg(v3)=2deg(v4)=2v1v1v2v3v4圖四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分）說明：此題解法步驟多樣，若能按正確步驟求得結果，均可給分．六、證明題（本題共8分）18．設連通無向圖G有14條邊，3個4度頂點，4個3度頂點，其它頂點的度數均小于3，試說明G中可能有的頂點數．證明：可利用數列可圖化及握手定理解答頂點度數和為214=28，（2分）28-（34+43）=4，則知其他頂點度數和為4，（4分）對于有限圖，若無零度頂點，則除4度及3度頂點外，可能的頂點情況有：2個2度點；1個2度點和2個1度點；4個1度點，（6分）即對應圖的頂點數分別至少為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．22．設G為無向圖，則下列結論成立的是()．A．無向圖G的結點的度數等于邊數的兩倍．B．無向圖G的結點的度數等于邊數．C．無向圖G的結點的度數之和等于邊數的兩倍．D．無向圖G的結點的度數之和等于邊數．ababcdefA．{(a，b)}是邊割集B．{a，c}是點割集C．dnakceo是點割集D．{(c，d)}是邊割集圖一4．設集合A={1}，則A的冪集為()．A．{{1}}B．{1，{1}}C．{，1}D．{，{1}}5．設A(*)：*是人，B(*)：*犯錯誤，則命題“沒有不犯錯誤的人”可符號化為（）．A．┐(*)(A(*)→┐B(*))B．┐(*)(A(*)∧┐B(*))C．┐(*)(A(*)∧B(*))D．(*)(A(*)∧B(*))二、填空題（每小題3分，本題共15分）6．命題公式的真值是真（或T，或1）．7．若無向圖T是連通的，則T的結點數v與邊數e滿足關系v=e+1時，T是樹．8．無向圖G是歐拉圖的充分必要條件是G是連通的且結點度數都是偶數．9．設集合A={1，2}上的關系R＝{<2,2>,<1,2>}，則在R中僅需加入一個元素<1,1>，就可使新得到的關系為自反的．10．(*)(P(*)→R(y)∨S(z))中的約束變元有*．三、邏輯公式翻譯（每小題6分，本題共12分）11．將語句“雪是黑色的．”翻譯成命題公式．設P：雪是黑色的，（2分）則命題公式為：P．（6分）12．將語句“如果明天下雨，則我們就在室內上體育課．”翻譯成命題公式．設P：如果明天下雨，Q：我們在室內上體育課，（2分）則命題公式為：PQ．（6分）四、判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由．13．設集合A={1，2}，B={3，4}，從A到B的關系為f={<1,3>，<1,4>}，則f是A到B的函數．錯誤．（3分）因為A中元素1有B中兩個不同的元素與之對應，故f不是A到B的函數．（7分）14．設G是一個連通平面圖，有5個結點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．設A={{1},{1,2}，1}，B={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．試畫一棵帶權為2,3,3,4,5,的最優(yōu)二叉樹,并計算該最優(yōu)二叉樹的權．最優(yōu)二叉樹如圖二所示．23345510717（10分）圖二權為23+33+32+42+52=39（12分）六、證明題（本題共8分）18．試證明：若R與S是集合A上的對稱關系，則R∩S也是集合A上的對稱關系．證明：設*，yA，因為R對稱，所以若<*,y>R，則<y,*>R．（2分）因為S對稱，所以若<*,y>S，則<y,*>S．（4分）于是若<*,y>R∩S則<*,y>R且<*,y>S即<y,*>R且<y,*>S（6分）也即<y,*>R∩S，故R∩S是對稱的．（8分）中央廣播電視大學2010—2011學年度第一學期“開放本科”期末考試離散數學（本）試題2011年1月一、單項選擇題（每小題3分，本題共15分）1．A2．D3．B4．D5．C1．若集合A＝{a，{1}}，則下列表述正確的是()．A．{1}AB．{1}AC．{a}AD．A2．設圖G＝<V,E>，vV，則下列結論成立的是()．A．deg(v)=2EB．deg(v)=EC．D．3．如圖一所示，以下說法正確的是()．A．(e,c)是割邊B．(d,e)是割邊abcdabcd圖一e4．命題公式（P∨Q）的合取*式是()．A．PB．（P∧Q）C．（P∨P）D．（P∨Q）5．下列等價公式成立的為()．A．PQPQB．QPPQC．PPQQD．PPQ二、填空題（每小題3分，本題共15分）6．設集合A={0,1,2}，B={1,2,3,4,}，R是A到B的二元關系，則R的有序對集合為{<1,1>，<1,2>，<2,1>，<2,2>}．7．設G是連通平面圖，v,e,r分別表示G的結點數，邊數和面數，則v，e和r滿足的關系式v-e+r=2．8．設G＝<V,E>是有20個結點，25條邊的連通圖，則從G中刪去6條邊，可以確定圖G的一棵生成樹．9．無向圖G存在歐拉回路，當且僅當G所有結點的度數全為偶數且連通．10．設個體域D＝{1,2}，則謂詞公式消去量詞后的等值式為A(1)A(2)．三、邏輯公式翻譯（每小題6分，本題共12分）11．將語句“如果小李學習努力，則他就會取得好成績．”翻譯成命題公式．12．將語句“小*學習努力，小王取得好成績．”翻譯成命題公式．11．設P：小李學習努力，Q：小李會取得好成績，（2分）PQ．（6分）12．設P：小*學習努力，Q：小王取得好成績，（2分）PQ．（6分）四、判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由．13．如果R1和R2是A上的自反關系，則R1R2是自反的．14．如圖二所示的圖中存在一條歐拉回路．圖二13．正確．（3分）R1和R2是自反的，*A，<*,*>R1，<*,*>R2，則<*,*>R1R2，所以R1R2是自反的．（7分）14．正確．（3分）因為圖G為連通的，且其中每個頂點的度數為偶數．（7分）五．計算題（每小題12分，本題共36分）15．設A={{2},1,2}，B={1,{1,2}}，試計算（1）（AB）；（2）（A∩B）；（3）A×B．16．設G=<V，E>，V={v1，v2，v3，v4，v5}，E={(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)}，試（1）給出G的圖形表示；（2）寫出其鄰接矩陣；（3）求出每個結點的度數；（4）畫出其補圖的圖形．17．設謂詞公式，試（1）寫出量詞的轄域；（2）指出該公式的自由變元和約束變元．15．（1）AB={2,{2}}（4分）（2）A∩B={1}（8分）（3）A×B={<{2},1>，<{2},{1,2}>，<1,1>，<1,{1,2}>，<2,1>，<2,{1,2}>}（12分）v1v2v3v4圖三v5（3分）（2）鄰接矩陣：（6分）（3）v1，v2，v3，v4，v5結點的度數依次為1，2，4，2，1（9分）v1v2v3v4圖四v5（12分）17．（1）*量詞的轄域為，（2分）z量詞的轄域為,（4分）y量詞的轄域為．（6分）（2）自由變元為中的y，以及中的z（9分）約束變元為中的*與中的z，以及中的y．（12分）六、證明題（本題共8分）18．試證明集合等式A(BC)=(AB)(AC)．18．證明：設S=A(BC)，T=(AB)(AC)，若*∈S，則*∈A或*∈BC，（1分）即*∈A或*∈B且*∈A或*∈C．（2分）也即*∈AB且*∈AC，（3分）即*∈T，所以ST．（4分）反之，若*∈T，則*∈AB且*∈AC，（5分）即*∈A或*∈B且*∈A或*∈C，（6分）也即*∈A或*∈BC，即*∈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．AB 2．集合A={*|*為小于10的自然數}，集合A上的關系R={<*，y>|*+y=10且*,yA}，則R的性質為（）．A．自反的B．對稱的C．傳遞且對稱的D．反自反且傳遞的3．設有向圖（a）、（b）、（c）與（d）如圖一所示，則下列結論成立的是()．圖一A．（a）僅為弱連通的B．（b）僅為弱連通的C．（c）僅為弱連通的D．（d）僅為弱連通的4．設圖G的鄰接矩陣為則G的邊數為()． A．5B．6C．7D．5．下列公式()為永真式．A．PQPQB．(P(QP))(P(PQ))C．(Q(PQ))(Q(PQ))D．(P(PQ))Q二、填空題（每小題3分，本題共15分）6．設集合A＝{1，2，3}，則集合A的冪集是{,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}．7．設A={a，b}，B={1，2}，作f：A→B，則不同的函數個數為4．8．若A={1,2}，R={<*,y>|*A,yA,*+y<4}，則R的自反閉包為{<1,1>,<2,2>,<1,2>,<2,1>}．9．無向連通圖在結點數v與邊數e滿足e=v-1關系時是樹．10．(*)(A(*)→B(*))∨C(*，y)中的自由變元為C(*，y)中的*與y．三、邏輯公式翻譯（每小題6分，本題共12分）11．將語句“他們去旅游，僅當明天天晴．”翻譯成命題公式．12．將語句“今天沒有下雪．”翻譯成命題公式．11．設P：他們去旅游，Q：明天天晴，（2分）P→Q．（6分）12．設P：今天下雪，（2分）P．（6分）四、判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由．13．漢密爾頓圖一定是歐拉圖．圖二存在漢密爾頓圖不是歐拉圖．（5分）反例見圖二．（7分）14．下面的推理是否正確，試予以說明．(1)（*）（F（*）→G（y））前提引入(2)F（y）→G（y）ES（1）．1、錯誤．（3分）（2）應為F（a）→G（y），換名時，約束變元與自由變元不能混淆．（7分）五．計算題（每小題12分，本題共36分）15．設A={0，1，2，3，4，5，6}，R={<*，y>|*A，yA且*+y<1}，S={<*，y>|*A，yA且*+y3}，試求R，S，RS，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分）RS={<0,0>,<0,1>,<0,2>,<0,3>}（6分）R-1={<0,0>}（8分）S-1=S（10分）r(R)=IA．（12分）16．畫一棵帶權為1,2,2,3,6的最優(yōu)二叉樹,計算它們的權．14最優(yōu)二叉樹如圖四：148866535332322121圖四（10分）權為：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)．證明：設S=A∩(B∪C)，T=(A∩B)∪(A∩C)，若*∈S，則*∈A且*∈B∪C，即*∈A且*∈B或*∈A且*∈C，也即*∈A∩B或*∈A∩C，即*∈T，所以ST．（4分）反之，若*∈T，則*∈A∩B或*∈A∩C，即*∈A且*∈B或*∈A且*∈C也即*∈A且*∈B∪C，即*∈S，所以TS．因此T=S．（8分）2010年7月一、單項選擇題（每小題3分，本題共15分）1．B2．D3．B4．C5．B1．若集合A={1，{2}，{1，2}}，則下列表述正確的是()．A．2AB．{1}C．1AD．22．已知一棵無向樹T中有8個頂點，4度、3度、2度的分支點各一個，T的樹葉數為()．A．6B．4C．3D．53．設無向圖G的鄰接矩陣為,則G的邊數為()． A．1B．7C．6D．4．設集合A={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個結點，則T的邊數為4．8．設正則m叉樹的樹葉數為t，分支數為i，則(m-1)i=t-1．9．設集合A={1，2}上的關系R＝{<1,1>,<1,2>}，則在R中僅需加一個元素<2,1>，就可使新得到的關系為對稱的．10．(*)(A(*)→B(*，z)∨C(y))中的自由變元有z，y．三、邏輯公式翻譯（每小題6分，本題共12分）11．將語句“今天上課．”翻譯成命題公式．設P：今天上課，（2分）則命題公式為：P．（6分）12．將語句“他去操場鍛煉，僅當他有時間．”翻譯成命題公式．設P：他去操場鍛煉，Q：他有時間，（2分）則命題公式為：PQ．（6分）四、判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由．13．設集合A={1，2}，B={3，4}，從A到B的關系為f={<1,3>}，則f是A到B的函數．14．設G是一個有4個結點10條邊的連通圖，則G為平面圖．13．錯誤．（3分）因為A中元素2沒有B中元素與之對應，故f不是A到B的函數．（7分）14．錯誤．（3分）不滿足“設G是一個有v個結點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．設A={{1},1,2}，B={1,{2}}，試計算（1）A∩B（2）A∪B（3）A（A∩B）．（1）A∩B={1}（4分）（2）A∪B={1,2,{1},{2}}（8分）（3）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)}，對應邊的權值依次為1、2、3、1、4及5，試（1）畫出G的圖形；（2）寫出G的鄰接矩陣；（3）求出G權最小的生成樹及其權值．圖一a圖一abcd112453（3分）（2）鄰接矩陣：圖二圖二abcd112453（3）最小的生成樹如圖二中的粗線所示：（10分）權為：1+1+3=5（12分）六、證明題（本題共8分）18．試證明：若R與S是集合A上的自反關系，則R∩S也是集合A上的自反關系．證明：設*A，因為R自反，所以*R*，即<*,*>R；又因為S自反，所以*R*，即<*,*>S．（4分）即<*,*>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個結點，則T的邊數為()．A．6B．7 C．8 D．94．圖G如圖一所示，以下說法正確的是()．A．a是割點B．{b,c}是點割集C．{b,d}是點割集D．{c}是點割集圖一5．下列公式成立的為()．A．P∧QP∨QB．PQPQC．QPPD．P∧(P∨Q)Q二、填空題（每小題3分，本題共15分）6．設集合A={2,3,4}，B={1,2,3,4}，R是A到B的二元關系，則R的有序對集合為{<2,2>，<2,3>，<2,4>，<3,3>}，<3,4>，<4,4>}．7．如果R是非空集合A上的等價關系，aA，bA，則可推知R中至少包含<a,a>，<b,b>等元素．8．設G＝<V,E>是有4個結點，8條邊的無向連通圖，則從G中刪去5條邊，可以確定圖G的一棵生成樹．9．設G是具有n個結點m條邊k個面的連通平面圖，則m等于n+k2．10．設個體域D＝{1,2}，A(*)為“*大于1”，則謂詞公式的真值為真（或T，或1）．三、邏輯公式翻譯（每小題6分，本題共12分）11．將語句“今天考試，明天放假．”翻譯成命題公式．設P：今天考試，Q：明天放假．（2分）則命題公式為：P∧Q．（6分）12．將語句“我去旅游，僅當我有時間．”翻譯成命題公式．設P：我去旅游，Q：我有時間，（2分）則命題公式為：PQ．（6分）四、判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由．13．如果圖G是無向圖，且其結點度數均為偶數，則圖G是歐拉圖．錯誤．（3分）當圖G不連通時圖G不為歐拉圖．（7分）14．若偏序集<A，R>的哈斯圖如圖二所示，則集合A的最大元為a，最小元是f．圖二錯誤．（3分）集合A的最大元與最小元不存在，a是極大元，f是極小元，．（7分）五．計算題（每小題12分，本題共36分）15．設謂詞公式，試（1）寫出量詞的轄域；（2）指出該公式的自由變元和約束變元．（1）*量詞的轄域為，（3分）z量詞的轄域為,（6分）（2）自由變元為中的y，（9分）約束變元為*與z．（12分）16．設集合A={{1},1,2}，B={1,{1,2}}，試計算（1）（AB）；（2）（A∩B）；（3）A×B．（1）AB={{1},2}（4分）（2）A∩B={1}（8分）（3）A×B={<{1},1>，<{1},{1,2}>，<1,1>，<1,{1,2}>，<2,1>，<2,{1,2}>}（12分）17．設G=<V，E>，V={v1，v2，v3，v4}，E={(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)}，試（1）給出G的圖形表示；（2）寫出其鄰接矩陣；（3）求出每個結點的度數；（4）畫出其補圖的圖形．（1）G的圖形表示為(如圖三)：（3分）圖三（2）鄰接矩陣：（6分）（3）v1，v2，v3，v4結點的度數依次為1，2，3，2（9分）（4）補圖如圖四所示：（12分）圖四六、證明題（本題共8分）18．設A，B是任意集合，試證明：若AA=BB，則A=B．證明：設*A，則<*，*>AA，（1分）因為AA=BB，故<*，*>BB，則有*B，（3分）所以AB．（5分）設*B，則<*，*>BB，（6分）因為AA=BB，故<*，*>AA，則有*A，所以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,4}上的關系R={<*，y>|*=y且*,yA}，則R的性質為（）．A．不是自反的B．不是對稱的C．傳遞的D．反自反 3．設集合A={1，2，3，4，5}，偏序關系是A上的整除關系，則偏序集<A，>上的元素5是集合A的（）．A．最大元B．極大元C．最小元D．極小元4．圖G如圖一所示，以下說法正確的是()．A．{(a,d)}是割邊 B．{(a,d)}是邊割集C．{(a,d),(b,d)}是邊割集D．{(b,d)}是邊割集圖一5．設A（*）：*是人，B（*）：*是工人，則命題“有人是工人”可符號化為（）．A．(*)(A(*)∧B(*))B．(*)(A(*)∧B(*))C．┐(*)(A(*)→B(*))D．┐(*)(A(*)∧┐B(*)) 二、填空題（每小題3分，本題共15分）6．若集合A={1，3，5，7}，B={2，4，6，8}，則A∩B=空集（或）．7．設集合A={1，2，3}上的函數分別為：f={<1,2>,<2,1>,<3,3>,}，g={<1,3>,<2,2>,<3,2>,}，則復合函數gf={<1,2>,<2,3>,<3,2>,}．8．設G是一個圖，結點集合為V，邊集合為E，則G的結點度數之和為2|E|（或“邊數的兩倍”）．9．無向連通圖G的結點數為v，邊數為e，則G當v與e滿足e=v-1關系時是樹．10．設個體域D＝{1,2,3}，P(*)為“*小于2”，則謂詞公式(*)P(*)的真值為假（或F，或0）三、邏輯公式翻譯（每小題6分，本題共12分）11．將語句“他是學生．”翻譯成命題公式．設P：他是學生，（2分）則命題公式為：P．（6分）12．將語句“如果明天不下雨，我們就去郊游．”翻譯成命題公式．設P：明天下雨，Q：我們就去郊游，（2分）則命題公式為：PQ．四、判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由．13．下面的推理是否正確，試予以說明．(1)（*）F（*）→G（*）前提引入(2)F（y）→G（y）US（1）．錯誤．（3分）（2）應為F（y）→G（*），換名時，約束變元與自由變元不能混淆．（7分）14．如圖二所示的圖G存在一條歐拉回路．圖二錯誤．（3分）因為圖G為中包含度數為奇數的結點．（7分）五．計算題（每小題12分，本題共36分）15．求（P∨Q）→R的析取*式與合取*式．（P∨Q）→R（P∨Q）∨R（4分）(P∧Q)∨R（析取*式）（8分）(P∨R)∧(Q∨R)（合取*式）（12分）16．設A={0，1，2，3}，R={<*，y>|*A，yA且*+y<0}，S={<*，y>|*A，yA且*+y2}，試求R，S，RS，S-1，r(R)．R=,S={<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<2,0>}（3分）RS=，（6分）S-1=S，（9分）r(R)=IA={<0,0>,<1,1>,<2,2>,<3,3>}．（12分）17．畫一棵帶權為1,2,2,3,4的最優(yōu)二叉樹,計算它們的權．1223347512（10分）圖三權為13+23+22+32+42=27（12分）六、證明題（本題共8分）18．試證明集合等式A(BC)=(AB)(AC)．證明：設S=A(BC)，T=(AB)(AC)，若*∈S，則*∈A或*∈BC，即*∈A或*∈B且*∈A或*∈C．也即*∈AB且*∈AC，即*∈T，所以ST．（4分）反之，若*∈T，則*∈AB且*∈AC，即*∈A或*∈B且*∈A或*∈C，也即*∈A或*∈BC，即*∈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，且AB 2．集合A={1,2,3,4,5,6,7,8}上的關系R={<*，y>|*+y=10且*,yA}，則R的性質為（）．A．自反的B．對稱的C．傳遞且對稱的D．反自反且傳遞的 3．如果R1和R2是A上的自反關系，則R1∪R2，R1∩R2，R1-R2中自反關系有（）個．A．0B．2C．1D．4．如圖一所示，以下說法正確的是()．A．{(a,e)}是割邊 B．{(a,e)}是邊割集C．{(a,e),(b,c)}是邊割集D．{(d,e)}是邊割集圖一5．設A（*）：*是人，B（*）：*是學生，則命題“不是所有人都是學生”可符號化為（）．A．(*)(A(*)∧B(*))B．┐(*)(A(*)∧B(*))C．┐(*)(A(*)→B(*))D．┐(*)(A(*)∧┐B(*))二、填空題（每小題3分，本題共15分）6．若集合A的元素個數為10，則其冪集的元素個數為1024．7．設A={a，b，c}，B={1，2}，作f：A→B，則不同的函數個數為8．8．若A={1,2}，R={<*,y>|*A,yA,*+y=10}，則R的自反閉包為{<1,1>,<2,2>}．9．結點數v與邊數e滿足e=v-1關系的無向連通圖就是樹．10．設個體域D＝{a,b,c}，則謂詞公式(*)A(*)消去量詞后的等值式為A(a)∧A(b)∧A（c）．三、邏輯公式翻譯（每小題6分，本題共12分）11．將語句“盡管他接受了這個任務，但他沒有完成好．”翻譯成命題公式．設P：他接受了這個任務，Q：他完成好了這個任務，（2分）PQ．（6分）12．將語句“今天沒有下雨．”翻譯成命題公式．設P：今天下雨，（2分）P．（6分）四、判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由．13．下面的推理是否正確，試予以說明．(1)（*）F（*）→G（*）前提引入(2)F（y）→G（y）US（1）．錯誤．（3分）（2）應為F（y）→G（*），換名時，約束變元與自由變元不能混淆．（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．設A={0，1，2，3，4}，R={<*，y>|*A，yA且*+y<0}，S={<*，y>|*A，yA且*+y3}，試求R，S，RS，R-1，S-1，r(R)．R=,（2分）S={<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>}（4分）RS=，（6分）R-1=，（8分）S-1=S，（10分）r(R)=IA．（12分）17．畫一棵帶權為1,2,2,3,4的最優(yōu)二叉樹,計算它們的權．1223347512權為13+23+22+32+42=27（12分）六、證明題（本題共8分）18．設G是一個n階無向簡單圖，n是大于等于2的奇數．證明G與中的奇數度頂點個數相等(是G的補圖)．證明：因為n是奇數，所以n階完全圖每個頂點度數為偶數，（3分）因此，若G中頂點v的度數為奇數，則在中v的度數一定也是奇數，（6分）所以G與中的奇數度頂點個數相等．（8分）2008年7月一、單項選擇題（每小題3分，本題共15分）1．B2．B3．A4．C5．D1．設A={a,b}，B={1,2}，R1，R2，R3是A到B的二元關系，且R1={<a，2>,<b，2>}，R2={<a，1>,<a，2>,<b，1>}，R3={<a，1>,<b，2>}，則（）不是從A到B的函數．A．R1和R2B．R2C．R3D．R1和R2．設A={1,2,3,4,5,6,7,8}，R是A上的整除關系，B={2,4,6}，則集合B的最大元、最小元、上界、下界依次為()．A．8、2、8、2B．無、2、無、2C．6、2、6、2D．8、1、6、13．若集合A的元素個數為10，則其冪集的元素個數為（）．A．1024B．10C．100D．14．設完全圖K有n個結點(n≥2)，m條邊，當（）時，K中存在歐拉回路．A．m為奇數B．n為偶數C．n為奇數D．m為偶數5．已知圖G的鄰接矩陣為，則G有（）．A．5點，8邊B．6點，7邊C．6點，8邊D．5點，7邊二、填空題（每小題3分，本題共15分）6．設集合A＝{a，b}，則集合A的冪集是{,{a,b},{a},}．7．如果R1和R2是A上的自反關系，則R1∪R2，R1∩R2，R1-R2中自反關系有2個．8．設圖G是有6個結點的連通圖，結點的總度數為18，則可從G中刪去4條邊后使之變成樹．9．設連通平面圖G的結點數為5，邊數為6，則面數為3．10．設個體域D＝{a,b}，則謂詞公式(*)A(*)∧（*）B（*）消去量詞后的等值式為(A(a)∧A(b))∧(B（a）∨B（b）)．三、邏輯公式翻譯（每小題4分，本題共12分）11．將語句“如果所有人今天都去參加活動，則明天的會議取消．”翻譯成命題公式．設P：所有人今天都去參加活動，Q：明天的會議取消，（1分）PQ．（4分）12．將語句“今天沒有人來．”翻譯成命題公式．設P：今天有人來，（1分）P．（4分）13．將語句“有人去上課．”翻譯成謂詞公式．設P(*)：*是人，Q(*)：*去上課，（1分）(*)(P(*)Q(*))．四、判斷說明題（每小題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的任意元素*，均有<*,a>R（或*Ra），所以a是集合A中的最大元．（5分）按照最小元的定義，在集合A中不存在最小元．（7分）五．計算題（每小題12分，本題共36分）16．設集合A={1，2，3，4}，R={<*,y>|*,yA；|*y|=1或*y=0}，試（1）寫出R的有序對表示；（2）畫出R的關系圖；（3）說明R滿足自反性，不滿足傳遞性．（1）R={<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的每個元素構成的有序對均在R中，故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．設圖G=<V，E>，V={v1，v2，v3，v4，v5}，E={(v1,v2)，(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)}，試畫出G的圖形表示；寫出其鄰接矩陣；(3)求出每個結點的度數；v1v2v1v2v3v4v5（1）關系圖（3分）（2）鄰接矩陣（6分）（3）deg(v1)=2deg(v2)=3deg(v3)=4deg(v4)=3v1v2v3v4v1v2v3v4v5（4）補圖（12分）六、證明題（本題共8分）19．試證明（*）（P（*）∧R（*））（*）P（*）∧（*）R（*）．證明：（1）（*）（P（*）∧R（*））P（2）P（a）∧R（a）ES(1)（2分）（3）P（a）T(2)I（4）（*）P（*）EG(3)（4分）（5）R（a）T(2)I（6）（*）R（*）EG(5)（6分）（7）（*）P（*）∧（*）R（*）T(5)(6)I（2分）2008年9月一、單項選擇題（每小題3分，本題共15分）1．C2．C3．D4．A5．B1．若集合A＝{a，{a}，{1，2}}，則下列表述正確的是()．A．{a，{a}}AB．{2}AC．{a}AD．A2．設圖G＝<V,E>，vV，則下列結論成立的是()．A．deg(v)=2EB．deg(v)=EC．D．3．命題公式（P∨Q）→R的析取*式是()A．（P∨Q）∨RB．（P∧Q）∨RC．（P∨Q）∨RD．（P∧Q）∨R4．如圖一所示，以下說法正確的是()．A．e是割點B．{a,e}是點割集C．{b,e}是點割集D．uijatfy是點割集圖一5．下列等價公式成立的為()．A．PQPQB．P(QP)P(PQ)C．Q(PQ)Q(PQ)D．P(PQ)Q二、填空題（每小題3分，本題共15分）6．設集合A={0,1,2,3}，B={2,3,4,5}，R是A到B的二元關系，則R的有序對集合為{<2,2>，<2,3>，<3,2>}，<3,3>．7．設G是連通平面圖，v,e,r分別表示G的結點數，邊數和面數，則v，e和r滿足的關系式v-e+r=2．8．設G＝<V,E>是有6個結點，8條邊的連通圖，則從G中刪去3條邊，可以確定圖G的一棵生成樹．9．無向圖G存在歐拉回路，當且僅當G連通且所有結點的度數全為偶數．10．設個體域D＝{1,2}，則謂詞公式消去量詞后的等值式為A(1)A(2)．三、邏輯公式翻譯（每小題4分，本題共12分）11．將語句“如果你去了，則他就不去．”翻譯成命題公式．設P：你去，Q：他去，（1分）PQ．（4分）12．將語句“小王去旅游，小李也去旅游．”翻譯成命題公式．設P：小王去旅游，Q：小李去旅游，（1分）PQ．（4分）13．將語句“所有人都去工作．”翻譯成謂詞公式．設P(*)：*是人，Q(*)：*去工作，（1分）(*)(P(*)Q(*))．（4分）四、判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由．14．如果R1和R2是A上的自反關系，則R1∪R2是自反的．正確．（3分）R1和R2是自反的，*A，<*,*>R1，<*,*>R2，則<*,*>R1R2，所以R1∪R2是自反的．（7分）15．如圖二所示的圖G存在一條歐拉回路．vv1v2v3v5v4dbacefghn圖二正確．（3分）因為圖G為連通的，且其中每個頂點的度數為偶數．（7分）五．計算題（每小題12分，本題共36分）16．設謂詞公式，試（1）寫出量詞的轄域；（2）指出該公式的自由變元和約束變元．（1）*量詞的轄域為，