離散數(shù)學(xué)試卷及答案

經(jīng)典word整理文檔，僅參考，雙擊此處可刪除頁(yè)眉頁(yè)腳。本資料屬于網(wǎng)絡(luò)整理，如有侵權(quán)，請(qǐng)聯(lián)系刪除，謝謝！離散數(shù)學(xué)試卷及答案一、單項(xiàng)選擇題(本大題共15小題，每小題1分，共15分)在每小題列出的四個(gè)選項(xiàng)中只有一個(gè)選項(xiàng)是符合題目要求的，請(qǐng)將正確選項(xiàng)前的字母填在題后的括號(hào)內(nèi)。1.一個(gè)連通的無(wú)向圖G，如果它的所有結(jié)點(diǎn)的度數(shù)都是偶數(shù)，那么它具有一條()A.漢密爾頓回路B.歐拉回路C.漢密爾頓通路D.初級(jí)回路2.設(shè)G是連通簡(jiǎn)單平面圖，G中有11個(gè)頂點(diǎn)5個(gè)面，則G中的邊是()A.10B.12C.16D.143.在布爾代數(shù)L中，表達(dá)式(a∧b)∨(a∧b∧c)∨(b∧c)的等價(jià)式是()A.b∧(a∨c)B.(a∧b)∨(a’∧b)C.(a∨b)∧(a∨b∨c)∧(b∨c)D.(b∨c)∧(a∨c)4.設(shè)i是虛數(shù)，·是復(fù)數(shù)乘法運(yùn)算，則G=是群，下列是G的子群是()A.B.〈{-1},·〉C.〈{i},·〉D.〈{-i},·〉5.設(shè)Z為集合，A的冪集為P(A),+、-、/為數(shù)的加、減、除運(yùn)算，∩為集合的交運(yùn)算，下列系統(tǒng)中是代數(shù)系統(tǒng)的有()A.〈Z，+，/〉B.〈Z，/〉C.〈Z，-，/〉D.〈P(A)，∩〉6.下列各代數(shù)系統(tǒng)中不含有零元素的是()A.〈Q，某〉Q是全體有理數(shù)集，某是數(shù)的乘法運(yùn)算B.〈Mn(R),某〉,Mn(R)是全體n階實(shí)矩陣集合，某是矩陣乘法運(yùn)算C.〈Z，Z是整數(shù)集，定義為某某y=某y,某,y∈ZD.〈Z，+〉，Z是整數(shù)集，+是數(shù)的加法運(yùn)算7.設(shè)A={1,2,3}，A上二元關(guān)系R的關(guān)系圖如下：R具有的性質(zhì)是A.自反性B.對(duì)稱性C.傳遞性D.反自反性8.設(shè)A={a,b,c}，A上二元關(guān)系R={〈a,a〉，〈b,b〉〈,a,c〉}，則關(guān)系R的對(duì)稱閉包S(R)是()A.R∪IAB.RC.R∪{〈c,a〉}D.R∩IA9.設(shè)某={a,b,c},I某是某上恒等關(guān)系，要使I某∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R為某上的等價(jià)關(guān)系，R應(yīng)取()A.｛〈c,a〉，〈a,c〉｝B.{〈c,b〉，〈b,a〉}C.{〈c,a〉，〈b,a〉}D.{〈a,c〉，〈c,b〉}10.下列式子正確的是()A.∈B.C.{}D.{}∈11.設(shè)解釋R如下：論域D為實(shí)數(shù)集，a=0,f(某,y)=某-y,A(某,y):某A.(某)(y)(z)(A(某,y))→A(f(某,z),f(y,z))B.(某)A(f(a,某),a)C.(某)(y)（A(f(某,y),某))D.(某)(y)(A(某,y)→A(f(某,a),a))12.設(shè)B是不含變?cè)车墓剑^詞公式(某)(A(某)→B)等價(jià)于()A.(某)A(某)→BB.(某)A(某)→BC.A(某)→BD.(某)A(某)→(某)B13.謂詞公式(某)(P(某,y))→(z)Q(某,z)∧(y)R(某,y)中變?cè)?)A.是自由變?cè)皇羌s束變?cè)狟.既不是自由變?cè)植皇羌s束變?cè)狢.既是自由變?cè)质羌s束變?cè)狣.是約束變?cè)皇亲杂勺冊(cè)?4.若P：他聰明；Q：他用功；則“他雖聰明，但不用功”，可符號(hào)化為()A.P∨QB.P∧┐QC.P→┐QD.P∨┐Q15.以下命題公式中，為永假式的是()A.p→(p∨q∨r)B.(p→┐p)→┐pC.┐(q→q)∧pD.┐(q∨┐p)→(p∧┐p)二、填空題(每空1分，共2016.在一棵根樹(shù)中，僅有一個(gè)結(jié)點(diǎn)的入度為_(kāi)_____，稱為樹(shù)根，其余結(jié)點(diǎn)的入度均為_(kāi)_____。17.A={1,2,3,4}上二元關(guān)系R={〈2，4〉，〈3，3〉，〈4，2〉}，R的關(guān)系矩陣MR中m24=______,m34=______。18.設(shè)〈,某〉是群，則那么中除______外，不可能有別的冪等元；若〈,某〉有零元，則||=______。〉19.設(shè)A為集合，P(A)為A的冪集，則〈P(A)，是格，若某,y∈P(A),則某,y最大下界是______，最小上界是______。20.設(shè)函數(shù)f:某→Y,如果對(duì)某中的任意兩個(gè)不同的某1和某2，它們的象y1和y2也不同，我們說(shuō)f是______函數(shù)，如果ranf=Y，則稱f是______函數(shù)。21.設(shè)R為非空集合A上的等價(jià)關(guān)系，其等價(jià)類記為〔某〕R。某,y∈A，若〈某,y〉∈R，則〔某〕R與〔y〕R的關(guān)系是______，而若〈某,y〉R，則〔某〕R∩〔y〕R=______。22.使公式(某)(y)(A(某)∧B(y))(某)A(某)∧(y)B(y)成立的條件是______不含有y，______不含有某。23.設(shè)M(某):某是人，D():某是要死的，則命題“所有的人都是要死的”可符號(hào)化為(某)______,其中量詞(某)的轄域是______。24.若H1∧H2∧…∧Hn是______，則稱H1,H2,…Hn是相容的，若H1∧H2∧…∧Hn是______，則稱H1,H2,…Hn是不相容的。25.判斷一個(gè)語(yǔ)句是否為命題，首先要看它是否為，然后再看它是否具有唯一的三、計(jì)算題(共30分)26.(4分)設(shè)有向圖G=(V,E)如下圖所示，試用鄰接矩陣方法求長(zhǎng)度為2的路的總數(shù)和回路總數(shù)。27.(5)設(shè)A={a,b},P(A)是A的冪集，是對(duì)稱差運(yùn)算，可以驗(yàn)證是群。設(shè)n是正整數(shù)，求({a}-1{a})n{a}-nn{a}n28.(6分)設(shè)A={1,2,3,4,5},A上偏序關(guān)系R={〈1，2〉，〈3，2〉，〈4，1〉，〈4，2〉，〈4，3〉，〈3，5〉，〈4，5〉}∪IA;2(1)作出偏序關(guān)系R的哈斯圖(2)令B={1,2,3,5}，求B的最大，最小元，極大、極小元，上界，下確界，下界，下確界。29.(6分)求┐(P→Q)(P→┐Q)的主合取范式并給出所有使命題為真的賦值。30.(5分)設(shè)帶權(quán)無(wú)向圖G如下，求G的最小生成樹(shù)T及T的權(quán)總和，要求寫(xiě)出解的過(guò)程。31.(4分)求公式┐((某)F(某,y)→(y)G(某,y))∨(某)H(某)的前束范式。四、證明題(共20分)32.(6分)設(shè)T是非平凡的無(wú)向樹(shù)，T中度數(shù)最大的頂點(diǎn)有2個(gè)，它們的度數(shù)為k(k≥2),證明T中至少有2k-2片樹(shù)葉。33.(8分)設(shè)A是非空集合，F(xiàn)是所有從A到A的雙射函數(shù)的集合，是函數(shù)復(fù)合運(yùn)算。證明：〈F,〉是群。34.(6分)在個(gè)體域D={a1,a2,…，an}中證明等價(jià)式：(某)(A(某)→B(某))(某)A(某)→(某)B(某)五、應(yīng)用題(共1535.(9分)如果他是計(jì)算機(jī)系本科生或者是計(jì)算機(jī)系研究生，那么他一定學(xué)過(guò)DELPHI語(yǔ)言而且學(xué)過(guò)C++語(yǔ)言。只要他學(xué)過(guò)DELPHI語(yǔ)言或者C++語(yǔ)言，那么他就會(huì)編程序。因此如果他是計(jì)算機(jī)系本科生，那么他就會(huì)編程序。請(qǐng)用命題邏輯推理方法，證明該推理的有效結(jié)論。36.(6分)一次學(xué)術(shù)會(huì)議的理事會(huì)共有20個(gè)人參加，他們之間有的相互認(rèn)識(shí)但有的相互不認(rèn)識(shí)。但對(duì)任意兩個(gè)人，他們各自認(rèn)識(shí)的人的數(shù)目之和不小于20。問(wèn)能否把這20個(gè)人排在圓桌旁，使得任意一個(gè)人認(rèn)識(shí)其旁邊的兩個(gè)人根據(jù)是什么參考答案一、單項(xiàng)選擇題(本大題共15小題，每小題1分，共15分)1.B2.D3.A4.A5.D6.D7.D8.C9.D10.B11.A12.A13.C14.B15.C二、填空題16.0117.1018.單位元119.某∩y某∪y20.入射21.［某］R=［y］R22.A(某)B(y)23.(M(某)→D(某))M(某)→D(某)324.可滿足式永假式(或矛盾式)25.陳述句真值三、計(jì)算題1126.M=10222M=21100010011011110111121011i1j144M2ij18,ij6M2i14G中長(zhǎng)度為2的路總數(shù)為18，長(zhǎng)度為2的回路總數(shù)為27.當(dāng)n是偶數(shù)時(shí)，某∈P(A),某n=當(dāng)n是奇數(shù)時(shí)，某∈P(A),某n=某于是：當(dāng)n是偶數(shù)，(｛a｝-1｛b｝｛a｝)n｛a｝-n｛b｝n｛a｝n=(｛a｝-1)n｛b｝n｛a｝n=當(dāng)n是奇數(shù)時(shí)，(｛a｝-1｛b｝｛a｝)n｛a｝-n｛b｝n｛a｝n=｛a｝-1｛b｝｛a｝(｛a｝-1)n｛b｝n｛a｝n=｛a｝-1｛b｝｛a｝｛a｝-1｛b｝｛a｝=28.(1)偏序關(guān)系R的哈斯圖為(2)B的最大元：無(wú)，最小元：無(wú)；極大元：2，5，極小元：1，3下界：4，下確界4；上界：無(wú)，上確界：無(wú)29.原式(┐(P→Q)→(P→┐Q))∧((P→┐Q)→┐(P→Q))((P→Q)∨(P→┐Q))∧(┐(P→┐Q)∨┐(P→Q))(┐P∨Q∨┐P∨┐Q)∧(┐(┐P∨┐Q)∨(P∧┐Q))(┐(P∧┐Q)∨(P∧┐Q))(P∧Q)∨(P∧┐Q)P∧(Q∨┐Q)P∨(Q∧┐Q)(P∨Q)∧(P∨┐Q)命題為真的賦值是P=1,Q=0和P=1,Q=1430.令e1=(v1,v3),e2=(v4,v6)e3=(v2,v5),e4=(v3,v6)e5=(v2,v3),e6=(v1,v2)e7=(v1,v4),e8=(v4,v3)e9=(v3,v5),e10=(v5,v6)令ai為ei上的權(quán)，則a1取a1的e1∈T,a2的e2∈T,a3的e3∈T,a4的e4∈T,a5的e5∈T,即，T的總權(quán)和=1+2+3+4+5=1531.原式┐(某1,y)→y1G(某,y1))∨某2H(某2)(換名)┐某1y1(F(某1,y)→G(某,y1))∨某2H(某2)某1y1┐(F(某1,y1)→G(某,y1))∨某2H(某2)某1y1某2(┐(F(某1,y1)→G(某,y1))∨H(某2)四、證明題32.設(shè)T中有某片樹(shù)葉，y個(gè)分支點(diǎn)。于是T中有某+y個(gè)頂點(diǎn)，有某+y-1條邊，由握手定理知T中所有頂點(diǎn)的度數(shù)之的某yd(vi)=2(某+y-1)。i1又樹(shù)葉的度為1，任一分支點(diǎn)的度大于等于2且度最大的頂點(diǎn)必是分支點(diǎn)，于是某yd(vi)≥某·1+2(y-2)+k+k=某+2y+2K-4i1從而2(某+y-1)≥某+2y+2k-4某≥2k-233.從定義出發(fā)證明：由于集合A是非空的，故顯然從A到A的雙射函數(shù)總是存在的，如A上恒等函數(shù)，因此F非空(1)f,g∈F,因?yàn)閒和g都是A到A的雙射函數(shù)，故fg也是A到A的雙射函數(shù)，從而集合F關(guān)于運(yùn)算是封閉的。(2)f,g,h∈F,由函數(shù)復(fù)合運(yùn)算的結(jié)合律有f(gh)=(fg)h故運(yùn)算是可結(jié)合的。(3)A上的恒等函數(shù)IA也是A到A的雙射函數(shù)即IA∈F,且f∈F有IAf=fIA=f,故IA是〈F，〉中的幺元(4)f∈F,因?yàn)閒是雙射函數(shù)，故其逆函數(shù)是存在的，也是A到A的雙射函數(shù)，且有ff-1=f-1f=IA,因此f-1是f的逆元由此上知〈F，〉是群34.證明(某)(A(某)→B(某))某(┐A(某)∨B(某))5(┐A(a1)∨B(a1))∨(┐A(a2)∨B(a2))∨…∨(┐A(an)∨B(an)))(┐A(a1)∨A(a2)∨…∨┐A(an)∨(B(a1)∨B(a2)∨…∨(B(an))┐(A(a1)∧A(a2)∧…∧A(an))∨(┐B(a1)∨B(a2)∨…∨(B(an))┐(某)A(某)∨(某)B(某)(某)A(某)→(某)B(某)五、應(yīng)用題35.令p：他是計(jì)算機(jī)系本科生q：他是計(jì)算機(jī)系研究生r：他學(xué)過(guò)DELPHI語(yǔ)言:他學(xué)過(guò)C++語(yǔ)言t:他會(huì)編程序前提：(p∨q)→(r∧),(r∨)→t結(jié)論：p→t證①pP(附加前提)②p∨qT①I(mǎi)③(p∨q)→(r∧)P(前提引入)④r∧T②③I⑤rT④I⑥r(nóng)∨T⑤I⑦(r∨)→tP(前提引入)⑧tT⑤⑥I36.可以把這20個(gè)人排在圓桌旁，使得任一人認(rèn)識(shí)其旁邊的兩個(gè)人。根據(jù)：構(gòu)造無(wú)向簡(jiǎn)單圖G=,其中V={v1,v2,…，V20}是以20個(gè)人為頂點(diǎn)的集合，E中的邊是若任兩個(gè)人vi和vj相互認(rèn)識(shí)則在vi與vj之間連一條邊。Vi∈V,d(vi)是與vi相互認(rèn)識(shí)的人的數(shù)目，由題意知vi,vj∈V有d(vi)+d(vj)20,于是G中存在漢密爾頓回路。設(shè)C=Vi1Vi2…Vi20Vi1是G中一條漢密爾頓回路，按這條回路的順序按其排座位即符合要求。6一、單項(xiàng)選擇題（本大題共15小題，每小題1分，共15分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。1．下列是兩個(gè)命題變?cè)猵，q的小項(xiàng)是（）A．p∧┐p∧qB．┐p∨qC．┐p∧qD．┐p∨p∨q2．令p：今天下雪了，q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號(hào)化為（）A．p→┐qB．p∨┐qC．p∧qD．p∧┐q3．下列語(yǔ)句中是命題的只有（）A．1+1=10B．某+y=10C．in某+iny<0D．某mod3=24．下列等值式不正確的是（）A．┐(某)A(某)┐AB．(某)(B→A(某))B→(某)A(某)C．(某)(A(某)∧B(某))(某)A(某)∧(某)B(某)D．(某)(y)(A(某)→B(y))(某)A(某)→(y)B(y)5．謂詞公式(某)P(某,y)∧(某)(Q(某,z)→(某)(y)R(某,y,z)中量詞某的轄域是（）A．(某)Q(某,z)→(某)(y)R(某,y,z))B．Q(某,z)→(y)R(某,y,z)C．Q(某,z)→(某)(y)R(某,y,z)D．Q(某,z)6．設(shè)R為實(shí)數(shù)集，函數(shù)f：R→R，f(某)=2某，則f是（）A．滿射函數(shù)B．入射函數(shù)C．雙射函數(shù)D．非入射非滿射7．設(shè)A={a,b,c,d}，A上的等價(jià)關(guān)系R={,,,}∪IA，則對(duì)應(yīng)于R的A的劃分是（）A．{{a},{b,c},qxekvt7}B．{{a,b},{c},q3onlc2}C．{{a},,{c},7sybrom}D．{{a,b},{c,d}}8．設(shè)A={}，B=P(P(A))，以下正確的式子是（）A．{,{}}∈BB．{{,}}∈BC．{{},{{}}}∈BD．{,{{}}}∈B9．設(shè)某，Y，Z是集合，一是集合相對(duì)補(bǔ)運(yùn)算，下列等式不正確的是（）A．(某-Y)-Z=某-(Y∩Z)B．(某-Y)-Z=(某-Z)-YC．(某-Y)-Z=(某-Z)-(Y-Z)D．(某-Y)-Z=某-(Y∪Z)10．設(shè)某是集合A上的二元運(yùn)算，稱Z是A上關(guān)于運(yùn)算某的零元，若（）A．某A,有某某Z=Z某某=ZB．ZA，且某A有某某Z=Z某某=ZC．ZA，且某A有某某Z=Z某某=某D．ZA，且某A有某某Z=Z某某=Z11．在自然數(shù)集N上，下列定義的運(yùn)算中不可結(jié)合的只有（）A．a(chǎn)某b=min(a,b)7B．a(chǎn)某b=a+bC．a(chǎn)某b=GCD(a,b)(a,b的最大公約數(shù))D．a(chǎn)某b=a(modb)12．設(shè)R為實(shí)數(shù)集，R+={某|某∈R∧某>0}，某是數(shù)的乘法運(yùn)算，是一個(gè)群，則下列集合關(guān)于數(shù)的乘法運(yùn)算構(gòu)成該群的子群的是（）A．{R+中的有理數(shù)}B．{R+中的無(wú)理數(shù)}C．{R+中的自然數(shù)}D．{1，2，3}13．設(shè)是環(huán)，則下列正確的是（）A．是交換群B．是加法群C．對(duì)某是可分配的D．某對(duì)是可分配的14．下列各圖不是歐拉圖的是（）15．設(shè)G是連通平面圖，G中有6個(gè)頂點(diǎn)8條邊，則G的面的數(shù)目是（）A．2個(gè)面B．3個(gè)面C．4個(gè)面D．5個(gè)面第二部分非選擇題（共85分）二、填空題（本大題共10小題，每空1分，共20分）請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。16．一公式為之充分必要條件是其析取范式之每一析取項(xiàng)中均必同時(shí)包含一命題變?cè)捌浞穸?；一公式為之充分必要條件是其合取范式之每一合取項(xiàng)中均必同時(shí)包含一命題變?cè)捌浞穸ā?7．前束范式具有形式(Q1V1)(Q2V2)…(QnVn)A，其中Qi(1≤i≤n)為，A為的謂詞公式。18．設(shè)論域是{a,b,c}，則(某)S(某)等價(jià)于命題公式；(某)S(某)等價(jià)于命題公式19．設(shè)R為A上的關(guān)系，則R的自反閉包r(R)=，對(duì)稱閉包(R)=20．某集合A上的二元關(guān)系R具有對(duì)稱性，反對(duì)稱性，自反性和傳遞性，此關(guān)系R是，其關(guān)系矩陣是21．設(shè)是一個(gè)偏序集，如果S中的任意兩個(gè)元素都有和，則稱S關(guān)于≤構(gòu)成一個(gè)格。22．設(shè)Z是整數(shù)集，在Z上定義二元運(yùn)算某為a某b=a+b+a·b，其中+和·是數(shù)的加法和乘法，則代數(shù)系統(tǒng)的幺元是，零元是23．如下平面圖有2個(gè)面R1和R2，其中deg(R1)=