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

PAGEPAGE4一、單項選擇題(本大題共15小題，每小題1分，共15分)在每小題列出的四個選項中只有一個選項是符合題目要求的，請將正確選項前的字母填在題后的括號內(nèi)。1.一個連通的無向圖G，如果它的所有結(jié)點的度數(shù)都是偶數(shù)，那么它具有一條()A.漢密爾頓回路B.歐拉回路C.漢密爾頓通路D.初級回路2.設(shè)G是連通簡單平面圖，G中有11個頂點5個面，則G中的邊是()A.10B.12C.16D.143.在布爾代數(shù)L中，表達(dá)式(a∧b)∨(a∧b∧c)∨(b∧c)的等價式是()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ù)乘法運算，則G=<{1,-1,i,-i},·>是群，下列是G的子群是()A.<{1},·>B.〈{-1},·〉C.〈{i},·〉D.〈{-i},·〉5.設(shè)Z為整數(shù)集，A為集合，A的冪集為P(A),+、-、/為數(shù)的加、減、除運算，∩為集合的交運算，下列系統(tǒng)中是代數(shù)系統(tǒng)的有()A.〈Z，+，/〉B.〈Z，/〉C.〈Z，-，/〉D.〈P(A)，∩〉6.下列各代數(shù)系統(tǒng)中不含有零元素的是()A.〈Q，*〉Q是全體有理數(shù)集，*是數(shù)的乘法運算B.〈Mn(R),*〉,Mn(R)是全體n階實矩陣集合，*是矩陣乘法運算C.〈Z，〉，Z是整數(shù)集，定義為xxy=xy,x,y∈ZD.〈Z，+〉，Z是整數(shù)集，+是數(shù)的加法運算7.設(shè)A={1,2,3}，A上二元關(guān)系R的關(guān)系圖如下：R具有的性質(zhì)是A.自反性B.對稱性C.傳遞性D.反自反性8.設(shè)A={a,b,c}，A上二元關(guān)系R={〈a,a〉，〈b,b〉,〈a,c〉}，則關(guān)系R的對稱閉包S(R)是()A.R∪IAB.RC.R∪{〈c,a〉}D.R∩IA9.設(shè)X={a,b,c},Ix是X上恒等關(guān)系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R為X上的等價關(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ù)集，a=0,f(x,y)=x-y,A(x,y):x<y.下列公式在R下為真的是()A.(x)(y)(z)(A(x,y))→A(f(x,z),f(y,z))B.(x)A(f(a,x),a)C.(x)(y)（A(f(x,y),x))D.(x)(y)(A(x,y)→A(f(x,a),a))12.設(shè)B是不含變元x的公式，謂詞公式(x)(A(x)→B)等價于()A.(x)A(x)→BB.(x)A(x)→BC.A(x)→BD.(x)A(x)→(x)B13.謂詞公式(x)(P(x,y))→(z)Q(x,z)∧(y)R(x,y)中變元x()A.是自由變元但不是約束變元B.既不是自由變元又不是約束變元C.既是自由變元又是約束變元D.是約束變元但不是自由變元14.若P：他聰明；Q：他用功；則“他雖聰明，但不用功”，可符號化為()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分，共20分)16.在一棵根樹中，僅有一個結(jié)點的入度為______，稱為樹根，其余結(jié)點的入度均為______。17.A={1,2,3,4}上二元關(guān)系R={〈2，4〉，〈3，3〉，〈4，2〉}，R的關(guān)系矩陣MR中m24=______,m34=______。18.設(shè)〈s,*〉是群，則那么s中除______外，不可能有別的冪等元；若〈s,*〉有零元，則|s|=______。19.設(shè)A為集合，P(A)為A的冪集，則〈P(A)，〉是格，若x,y∈P(A),則x,y最大下界是______，最小上界是______。20.設(shè)函數(shù)f:X→Y,如果對X中的任意兩個不同的x1和x2，它們的象y1和y2也不同，我們說f是______函數(shù)，如果ranf=Y，則稱f是______函數(shù)。21.設(shè)R為非空集合A上的等價關(guān)系，其等價類記為〔x〕R。x,y∈A，若〈x,y〉∈R，則〔x〕R與〔y〕R的關(guān)系是______，而若〈x,y〉R，則〔x〕R∩〔y〕R=______。22.使公式(x)(y)(A(x)∧B(y))(x)A(x)∧(y)B(y)成立的條件是______不含有y，______不含有x。23.設(shè)M(x):x是人，D(s):x是要死的，則命題“所有的人都是要死的”可符號化為(x)______,其中量詞(x)的轄域是______。24.若H1∧H2∧…∧Hn是______，則稱H1,H2,…Hn是相容的，若H1∧H2∧…∧Hn是______，則稱H1,H2,…Hn是不相容的。25.判斷一個語句是否為命題，首先要看它是否為，然后再看它是否具有唯一的。三、計算題(共30分)26.(4分)設(shè)有向圖G=(V,E)如下圖所示，試用鄰接矩陣方法求長度為2的路的總數(shù)和回路總數(shù)。27.(5)設(shè)A={a,b},P(A)是A的冪集，是對稱差運算，可以驗證<P(A)，>是群。設(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;30.令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<a2<a3<a4<a5=a6=a7=a8<a9=a10取a1的e1∈T,a2的e2∈T,a3的e3∈T,a4的e4∈T,a5的e5∈T,即，T的總權(quán)和=1+2+3+4+5=1531.原式┐(x1F(x1,y)→y1G(x,y1))∨x2H(x2)(換名)┐x1y1(F(x1,y)→G(x,y1))∨x2H(x2)x1y1┐(F(x1,y1)→G(x,y1))∨x2H(x2)x1y1x2(┐(F(x1,y1)→G(x,y1))∨H(x2)四、證明題32.設(shè)T中有x片樹葉，y個分支點。于是T中有x+y個頂點，有x+y-1條邊，由握手定理知T中所有頂點的度數(shù)之的=2(x+y-1)。又樹葉的度為1，任一分支點的度大于等于2且度最大的頂點必是分支點，于是≥x·1+2(y-2)+k+k=x+2y+2K-4從而2(x+y-1)≥x+2y+2k-4x≥2k-233.從定義出發(fā)證明：由于集合A是非空的，故顯然從A到A的雙射函數(shù)總是存在的，如A上恒等函數(shù)，因此F非空(1)f,g∈F,因為f和g都是A到A的雙射函數(shù)，故fg也是A到A的雙射函數(shù)，從而集合F關(guān)于運算是封閉的。(2)f,g,h∈F,由函數(shù)復(fù)合運算的結(jié)合律有f(gh)=(fg)h故運算是可結(jié)合的。(3)A上的恒等函數(shù)IA也是A到A的雙射函數(shù)即IA∈F,且f∈F有IAf=fIA=f,故IA是〈F，〉中的幺元(4)f∈F,因為f是雙射函數(shù)，故其逆函數(shù)是存在的，也是A到A的雙射函數(shù)，且有ff-1=f-1f=IA,因此f-1是f的逆元由此上知〈F，〉是群34.證明(x)(A(x)→B(x))x(┐A(x)∨B(x))(┐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))┐(x)A(x)∨(x)B(x)(x)A(x)→(x)B(x)五、應(yīng)用題35.令p：他是計算機(jī)系本科生q：他是計算機(jī)系研究生r：他學(xué)過DELPHI語言s:他學(xué)過C++語言t:他會編程序前提：(p∨q)→(r∧s),(r∨s)→t結(jié)論：p→t證①pP(附加前提)②p∨qT①I③(p∨q)→(r∧s)P(前提引入)④r∧sT②③I⑤rT④I⑥r(nóng)∨sT⑤I⑦(r∨s)→tP(前提引入)⑧tT⑤⑥I36.可以把這20個人排在圓桌旁，使得任一人認(rèn)識其旁邊的兩個人。根據(jù)：構(gòu)造無向簡單圖G=<V,E>,其中V={v1,v2,…，V20}是以20個人為頂點的集合，E中的邊是若任兩個人vi和vj相互認(rèn)識則在vi與vj之間連一條邊。Vi∈V,d(vi)是與vi相互認(rèn)識的人的數(shù)目，由題意知vi,vj∈V有d(vi)+d(vj)20,于是G中存在漢密爾頓回路。設(shè)C=Vi1Vi2…Vi20Vi1是G中一條漢密爾頓回路，按這條回路的順序按其排座位即符合要求。一、單項選擇題（本大題共15小題，每小題1分，共15分）在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1．下列是兩個命題變元p，q的小項是（）A．p∧┐p∧q B．┐p∨qC．┐p∧q D．┐p∨p∨q2．令p：今天下雪了，q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號化為（）A．p→┐q B．p∨┐qC．p∧q D．p∧┐q3．下列語句中是命題的只有（）A．1+1=10 B．x+y=10C．sinx+siny<0 D．xmod3=24．下列等值式不正確的是（）A．┐(x)A(x)┐AB．(x)(B→A(x))B→(x)A(x)C．(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)D．(x)(y)(A(x)→B(y))(x)A(x)→(y)B(y)5．謂詞公式(x)P(x,y)∧(x)(Q(x,z)→(x)(y)R(x,y,z)中量詞x的轄域是（）A．(x)Q(x,z)→(x)(y)R(x,y,z))B．Q(x,z)→(y)R(x,y,z)C．Q(x,z)→(x)(y)R(x,y,z)D．Q(x,z)6．設(shè)R為實數(shù)集，函數(shù)f：R→R，f(x)=2x，則f是（）A．滿射函數(shù) B．入射函數(shù)C．雙射函數(shù) D．非入射非滿射7．設(shè)A={a,b,c,d}，A上的等價關(guān)系R={<a,b>,<b,a>,<c,d>,<d,c>}∪IA，則對應(yīng)于R的A的劃分是（）A．{{a},{b,c},zfvnzd7} B．{{a,b},{c},rznhj1p}C．{{a},,{c},b9z7frn} D．{{a,b},{c,d}}8．設(shè)A={?}，B=P(P(A))，以下正確的式子是（）A．{?,{?}}∈B B．{{?,?}}∈BC．{{?},{{?}}}∈B D．{?,{{?}}}∈B9．設(shè)X，Y，Z是集合，一是集合相對補(bǔ)運算，下列等式不正確的是（）A．(X-Y)-Z=X-(Y∩Z)B．(X-Y)-Z=(X-Z)-YC．(X-Y)-Z=(X-Z)-(Y-Z)D．(X-Y)-Z=X-(Y∪Z)10．設(shè)*是集合A上的二元運算，稱Z是A上關(guān)于運算*的零元，若（）A．有x*Z=Z*x=ZB．ZA，且有x*Z=Z*x=ZC．ZA，且有x*Z=Z*x=xD．ZA，且有x*Z=Z*x=Z11．在自然數(shù)集N上，下列定義的運算中不可結(jié)合的只有（）A．a(chǎn)*b=min(a,b)B．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ù)集，R+={x|x∈R∧x>0}，*是數(shù)的乘法運算，<R+，*>是一個群，則下列集合關(guān)于數(shù)的乘法運算構(gòu)成該群的子群的是（）A．{R+中的有理數(shù)} B．{R+中的無理數(shù)}C．{R+中的自然數(shù)} D．{1，2，3}13．設(shè)<A,*,>是環(huán)，則下列正確的是（）A．<A,>是交換群 B．<A,*>是加法群C．對*是可分配的 D．*對是可分配的14．下列各圖不是歐拉圖的是（）15．設(shè)G是連通平面圖，G中有6個頂點8條邊，則G的面的數(shù)目是（）A．2個面 B．3個面C．4個面 D．5個面第二部分非選擇題（共85分）二、填空題（本大題共10小題，每空1分，共20分）請在每小題的空格中填上正確答案。錯填、不填均無分。16．一公式為之充分必要條件是其析取范式之每一析取項中均必同時包含一命題變元及其否定；一公式為之充分必要條件是其合取范式之每一合取項中均必同時包含一命題變元及其否定。17．前束范式具有形式(Q1V1)(Q2V2)…(QnVn)A，其中Qi(1≤i≤n)為，A為的謂詞公式。18．設(shè)論域是{a,b,c}，則(x)S(x)等價于命題公式；()S(x)等價于命題公式。19．設(shè)R為A上的關(guān)系，則R的自反閉包r(R)=，對稱閉包s(R)=。20．某集合A上的二元關(guān)系R具有對稱性，反對稱性，自反性和傳遞性，此關(guān)系R是，其關(guān)系矩陣是。21．設(shè)<S,≤>是一個偏序集，如果S中的任意兩個元素都有和，則稱S關(guān)于≤構(gòu)成一個格。22．設(shè)Z是整數(shù)集，在Z上定義二元運算*為a*b=a+b+a·b，其中+和·是數(shù)的加法和乘法，則代數(shù)系統(tǒng)<Z,*>的幺元是，零元是。23．如下平面圖有2個面R1和R2，其中deg(R1)=，deg(R2)=。24．無向圖G具有一條歐拉回路，當(dāng)且僅當(dāng)G是，并且所有結(jié)點的度數(shù)