PAGE3PAGE3一、單項(xiàng)選擇題（每小題3分，本題共15分）1．若集合A＝{b,c,d}，則下列表述正確的是()．A．{b,c,d}AB．A{c,d}C．{b,c,d}AD．{b,c}A2．已知無向圖G的鄰接矩陣為，則G有（）．A．6點(diǎn)，10邊B．5點(diǎn)，12邊C．6點(diǎn)，5邊D．5點(diǎn)，6邊3．無向圖G是個棵樹，結(jié)點(diǎn)數(shù)為10，則G的邊數(shù)是（）．A．9B．10C．11D．124．設(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)) 5．下面的推理正確的是（）．A．(1)（x）F（x）→G（x）前提引入(2)F（y）→G（y）US（1）．B．(1)（x）（F（x）→G（x））前提引入(2)F（y）→G（y）US（1）．C．(1)（x）F（x）→G（x）前提引入(2)F（y）→G（y）US（1）．D．(1)（x）(F（x）→G（x））前提引入(2)F（y）→G（x）ES（1）． 二、填空題（每小題3分，本題共15分）6．設(shè)A={a，b，c}，B={1，2，3}，作f：A→B，則不同的函數(shù)個數(shù)為．7．任一無向圖中，度數(shù)為奇數(shù)的結(jié)點(diǎn)的個數(shù)為．8．設(shè)G是漢密爾頓圖，S是其結(jié)點(diǎn)集的一個子集，若S的元素個數(shù)為6，則在G-S中的連通分支數(shù)不超過．9．設(shè)G是有8個結(jié)點(diǎn)的連通圖，結(jié)點(diǎn)的度數(shù)之和為28，則可從G中刪去條邊后使之變成樹．10．設(shè)個體域D＝{1,2}，則謂詞公式(x)P(x)∨（x）Q（x）消去量詞后的等值式為．三、邏輯公式翻譯（每小題6分，本題共12分）11．將語句“小張和小李都可以完成這項(xiàng)工作”翻譯成命題公式．12．將語句“a是偶數(shù)當(dāng)且僅當(dāng)a能被2整除．”翻譯成命題公式．四、判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由．13．存在集合A與B，使得AB與AB同時成立．14．完全圖K5是平面圖．五、計(jì)算題（每小題12分，本題共36分）15．設(shè)A={2,3,6,12,24,36}，B為A的子集，其中B={6,12}，R是A上的整除關(guān)系，試（1）寫出R的關(guān)系表達(dá)式；（2）說明R為偏序關(guān)系；（3）畫出關(guān)系R的哈斯圖；（4）求出B的最大元素、極大元素、上確界．16．．設(shè)圖G=<V，E>，V={v1，v2，v3，v4，v5}，E={(v1,v2)，(v1,v3)，(v1,v5)，(v2,v3)，(v2,v4)，(v2,v5)，(v3,v4)，(v3,v5)，(v4,v5)}，試（1）畫出G的圖形表示；（2）寫出其鄰接矩陣；（3）求出每個結(jié)點(diǎn)的度數(shù)；（4）畫出圖G的補(bǔ)圖的圖形．17．求P→（Q∧R）的合取范式與主合取范式．六、證明題（本題共8分）18．對任意集合A，B和C，若有C，則有：AB的充分必要條件是CACB．

離散數(shù)學(xué)（本）2015年1月份試題參考解答一、單項(xiàng)選擇題（每小題3分，本題共15分）1．D2．D3．A4．C5．B二、填空題（每小題3分，本題共15分）6．277．偶數(shù)8．69．710．(P(1)∧P(2))∨(Q（1）∨Q（2))三、邏輯公式翻譯（每小題6分，本題共12分）11．設(shè)P：小張可以完成這項(xiàng)工作，Q：小李可以完成這項(xiàng)工作．（2分）則命題公式為：P∧Q．（6分）12．設(shè)P：a是偶數(shù)，Q：a能被2整除．（2分）則命題公式為：P?Q．（6分）四、判斷說明題（每小題7分，本題共14分）13．正確．（3分）例：設(shè)A={a}，B={a，{a}}（5分）則有AB且AB．（7分）說明：舉出符合條件的例均給分．14．錯誤．（3分）完全圖K5是有5個結(jié)點(diǎn)10條邊，因35-6<10，即e3v-6對K5不成立，（5分）故K5不是平面圖．（7分）五、計(jì)算題（每小題12分，本題共36分）15．（1）因?yàn)樵诩螦={2,3,6,12,24,36}中，集合A上的整除關(guān)系R為：R={<2,2>,<3,3>,<6,6>,<12,12>,<24,24>,<36,36>,<2,6>,<3,6>,<2,12>,<3,12>,<6,12>,<2,24>,<3,24>,<6,24>,<12,24>,<2,36>,<3,36>,<6,36>,<12,36>}．（3分）（2）R中的每個有序?qū)Φ牡谝粋€元素都可以整除第二個元素，即R為整除關(guān)系．每個數(shù)可以整除自身，則關(guān)系R是自反的；由R的元素可看出，若xy，當(dāng)存在<x,y>R，就有<y,x>R，則說明關(guān)系R是反對稱的；由R的元素可看出，若存在<x,y>R，<y,z>R,就有<x,z>R，則說明關(guān)系R是傳遞的．所以A上的整除關(guān)系R為偏序關(guān)系．（6分）說明：只要指出R是自反的、反對稱的、傳遞的，即可給分．（3）關(guān)系R的哈斯圖如圖一所示：（9分）圖一（4）集合B的最大元素12、極大元素12、上確界為12（12分）v1v2vv1v2v3v4圖二v5（3分）（2）鄰接矩陣（6分）（3）deg(v1)=3deg(v2)=4deg(v3)=4deg(v4)=3v1vv1v2v3v4圖三v5（4）補(bǔ)圖如圖三所示：（12分）17．P→（Q∧R）P∨(Q∧R)（2分）(P∨Q)∧(P∨R)合取范式（5分）(P∨Q)∨(R∧R)∧(P∨R)（7分）(P∨Q)∨(R∧R)∧(P∨R)∨(Q∧Q)（9分）(P∨Q∨R)∧(P∨Q∨R)∧(P∨R∨Q)∧(P∨R∨Q)（11分）(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)主合取范式（12分）六、證明題（本題共8分） 18．證明：已知C，即存在c∈C，設(shè)AB，則對任意<c，a>∈CA，有c∈C，a∈A，（1分）可得c∈C，a∈B，（2分）即有<c，a>∈CB，（3分）所以CACB．（4分）再設(shè)CACB，則對任意a∈A，由<c，a>∈CA可得<c，a>∈CB，（5分）即有c∈C，a∈B，（6分）所以AB，