離散數(shù)學(xué)題庫與答案

1、(完滿版)失散數(shù)學(xué)題庫與答案(完滿版)失散數(shù)學(xué)題庫與答案7/7(完滿版)失散數(shù)學(xué)題庫與答案試卷二十二試題與答案一、單項(xiàng)選擇題：（每題1分，本大題共15分）1設(shè)A=1，2，3，4，5，下面（）會集等于A。A、1，2，3，4，5，6；B、xx是整數(shù)且x225；C、xx是正整數(shù)且x5；D、xx是正有理數(shù)且x5。2設(shè)A=1，2，3，4，5，6，7，8，以下各式中（）是錯的。A、A；B、6，7，8A；C、4，5A；D、1，2，3A。3六階群的子群的階數(shù)能夠是（）。A、1，2，5；B、2，4；C、3，6，7；D、2，3。4設(shè)SAB，以下各式中（）是正確的。A、domSB；B、domSA；C、ranSA；D

2、、domSranS=S。5設(shè)會集X，則空關(guān)系X不具備的性質(zhì)是（）。A、自反性；B、反自反性；C、對稱性；D、傳達(dá)性。6以下函數(shù)中，（）是入射函數(shù)。A、世界上每個人與其年齡的序偶集；B、世界上每個人與其性其余序偶集；B、一個作者的專著與其作者的序偶集；D、每個國家與其國旗的序偶集。7G,*是群，則對*（）。A、滿足結(jié)合律、交換律；B、有單位元，可結(jié)合；C、有單位元、可交換；D、每元有逆元，有零元。8下面（）哈斯圖所描述的偏序關(guān)系構(gòu)成分配格。9以下（）中的運(yùn)算符都是可交換的。A、,；B、,；C、,；D、,。10設(shè)G是n個結(jié)點(diǎn)、m條邊和r個面的連通平面圖，則m等于（）。A、n+r-2；B、n-r+2

3、；C、n-r-2；D、n+r+2。11n個結(jié)點(diǎn)的無向完滿圖Kn的邊數(shù)為（）。A、n(n1)；n(n1)C、n(n1)；n(n1)B、2；D、2。12以下列圖中（）是根樹。A、G1a,b,c,d,a,a,a,b,c,d；B、G2a,b,c,d,a,b,b,d,c,d；C、G3a,b,c,d,a,b,a,d,c,a；D、G4a,b,c,d,a,b,a,c,d,d。13設(shè)P：22=5，Q：雪是黑的，R：24=8，S：太陽從東方升起，以下（）命題的真值為真。A、PQR；B、RPS；C、SQR；D、(PR)(QS)。14下面（）命題公式是重言式。A、PQR；B、(PR)(PQ)；C、(PQ)(QR)；D

4、、(P(QR)(PQ)(PR)。15設(shè)L(x)：x是演員，J(x)：x是老師，A(x,y)：x敬重y，命題“所有演員都敬重某些老師”符號化為（）。A、x(L(x)A(x,y)；B、C、xy(L(x)J(y)A(x,y)；D、x(L(x)y(J(y)A(x,y)；xy(L(x)J(y)A(x,y)。二、填空題：（每空1分，本大題共15分）1設(shè)Mx1x12,x被2整除，xZ，Nx1x12,x被3整除，xZ，則MN，MN。2在一個有n個元素的會集上，能夠有種不同樣的關(guān)系，有種不同樣的函數(shù)。3若關(guān)系R是反對稱的，當(dāng)且僅當(dāng)關(guān)系矩陣中，在關(guān)系圖上。4設(shè)gf是一個復(fù)合函數(shù)，若g和f都是滿射，則gf為，若g和

5、f都是入射，則gf是。5三階群有個（不同樣構(gòu)），其運(yùn)算表為。0101A101111006設(shè)圖G=，Vv1,v2,v3,v4的毗鄰矩陣1000，則v1的入度deg(v1)=，v4的出度deg(v4)=，從v2到v4的長度為2的路有條。7命題公式AP(P(Q(QR)的主合取范式為，其編碼表示為。三、判斷改正題：判斷以下各題可否正確，正確的劃“”，錯誤的劃“”，并加以改正。（每題2分，本大題共20分）1A，B，C為任領(lǐng)悟集，若ABAC，則B=C。（）2設(shè)R是實(shí)數(shù)集，R上的關(guān)系fx,yxy2,x,yR，R是相容關(guān)系。（）3設(shè)是偏序集，BA，則B的極大元bB且唯一。（）4謂詞公式xP(x)xQ(x)yR

6、(y)的前束范式是xzy(P(x)Q(z)R(y)。（）5在代數(shù)系統(tǒng)中，若一個元素的逆元是唯一的，其運(yùn)算必是可結(jié)合的。（）6每一個有限整環(huán)必然是域，反之也對。（）7有割點(diǎn)的連通圖可能是哈密爾頓圖。（）8x(A(x)B(x)xA(x)xB(x)。（）9無多重邊的圖是簡單圖。（）10設(shè)A,是布爾代數(shù)，則A,必然為有補(bǔ)分配格。（）四、簡答題：（每題5分，本大題共20分）1設(shè)R1和R2是A上的任意二元關(guān)系，若是R1和R2是自反的，R1R2可否也是自反的，為什么？若是R1和R2是對稱的，R1R2是對稱的嗎？2如圖給出的賦權(quán)圖表示六個城市a,b,c,d,e,f及架起城市間直接通訊線路的展望造價。試給出一個

7、設(shè)計(jì)方案使得各城市間能夠通訊且總造價最小，并計(jì)算出最小總造價。3設(shè)S=R-1（R為實(shí)數(shù)集），ababab。（1）說明S,可否構(gòu)成群；（2）在S中解方程2x37。4將公式(PQ)R）(PR)劃為只含有聯(lián)系詞，的等價公式。五、證明題：（共30分）1設(shè)A1,2,3,9，在AA上定義關(guān)系R:a,b,c,dR當(dāng)且僅當(dāng)adbc，證明R是AA上的等價關(guān)系，并求出2,5R?2用CP規(guī)則證明A(BC)，(EF)C，B(AS)BE。3將以下命題形式化，并證明結(jié)論的有效性：所有有理數(shù)都是實(shí)數(shù)，某些有理數(shù)是整數(shù)。因此，某些實(shí)數(shù)是整數(shù)。n15證明：若T是有n個結(jié)點(diǎn)的完滿二叉樹，則T有2片葉子。答案一、單項(xiàng)選擇題：題號1

8、23456789答案CDDBADBDD題號101112131415答案ADCADB二、填空題：16，12；2，4，8，10。22n2；nn。3以主對角線為對稱的元素不能夠同時為1；兩個不同樣結(jié)點(diǎn)間的定向弧線，不能能成對出現(xiàn)。4滿射；入射。*eabeeab51；aabebbea63；1；1。7(PQR)(PQR)；M000M001。三、判斷改正題：1若ABAC，則不用然BC。2。3B的極大元bB但能夠不唯一。4。5運(yùn)算*不用然可結(jié)合。6有限整環(huán)必然是域，但反之不成立。7有割點(diǎn)的連通圖不能能是漢密爾頓圖。8。9無多重邊和自環(huán)的圖是簡單圖。10。四、簡答題：1解：若R1,R2是自反的，則R1R2也是

9、自反的。因?yàn)閍A,R1,R2自反，a,aR1,a,aR2，從而a,aR1R2，即R1R2也是自反的。若R1,R2是對稱的，但R1R2不用然是對稱的。如：A=a,b,c，R1a,b,b,a，R2b,c,c,b，則R1,R2是對稱的，但R1R2a,c不是對稱的。2要設(shè)計(jì)一個方案使各城市間能夠通訊且總造價最小，即要求該圖連通、無回路、邊權(quán)之和最小的子圖即最小生成樹，由避圈法或破圈法可得：其最小生成樹為：其樹權(quán)即最小造價為：1+2+3+5+7=18。3解：（1）1）a,bS易證abababS，即運(yùn)算*是封閉的。2）a,b,cS(ab)c(abab)cababc(abab)cabcabacbcabc,而

10、a(bc)a(bcbc)a(bcbc)a(bcbc)abcbcabacabc,(ab)ca(bc)，即*可結(jié)合。3）設(shè)S關(guān)于*有幺元e，則aS,eaaea。而aeeaaeeaa,e0。4）aS設(shè)有逆元a1。則aa1a1ae，即aa1aa10，a11aa，即S中任意元都有逆元，綜上得出，S,構(gòu)成群。（2）由2x32x32x3x66x12x117，1x。4解：原式(PQ)R)(PR)(PQ)R(PR)(PQ)R(PR)。五、證明題：1證明：1）a,bAA,abba,a,b,a,bR,即R自反。2）a,b,c,dR,則adbc,dacb,即cbda,從而c,d,a,bR，即R對稱。a,b,c,dR,

11、c,d,e,fR,3）則adbc,cfdefdec從而afadecbcecbe，a,b,e,fR,即R傳達(dá)。綜上得出，R是等價關(guān)系。2,5Ra,ba,bAA,a5b2a,ba,bAA,ab3且1,4,2,5,3,6,4,7,5,8,6,92證明：（1）BP(附加前提)（2）B(AS)P(3)AST(1)(2)I(4)AT(3)I(5)ABCP(6)BCT(4)(5)I(7)CT(6)I(8)(EF)CP(9)(EF)T(7)(8)I(10)EFT(9)E(11)ET(10)I(12)BECP3解：設(shè)Q(x)：x是有理數(shù)，R(x)：x是實(shí)數(shù)，Z(x)：x是整數(shù)。命題形式化：證明：（1）x(Q(x)R(x),x(Q(x)Z(x)x(R(x)Z(x)。x(Q(x)Z(x)P(2)Q(a)