(完整版)離散數(shù)學題庫與答案

1、試卷二十二試題與答案、單項選擇題：（每小題1分，本大題共15分）1.設 A=1，2，3，4，5，下面（）集合等于A 。2.3.C、設 A=11 , 2, 3, 4, 5, 6;x| X是正整數(shù)且X,2, 3, 4 , 5 , 6 ,C、4 , 5 A;六階群的子群的階數(shù)可以是（A、 1, 2, 5;B、 2, 4;4.設S A B，下列各式中（A、 domSB、domS5 .設集合XA、自反性;6.F列函數(shù)中,5 7,a X X是整數(shù)且B、25 x| X是正有理數(shù)且8，下列各式中B、6 , 7,D、 1 , 2,C、3, 6, 7;C、ranS，則空關系X不具備的性質是（B、反自反性;C、對稱

2、性;）是入射函數(shù)。83）是正確的。D、domSD、傳遞性。5。是錯的。ranS = S。A、世界上每個人與其年齡的序偶集;B、世界上每個人與其性別的序偶集;個作者的專著與其作者的序偶集;每個國家與其國旗的序偶集。7.G,* 是群，則對* （A、滿足結合律、交換律;有單位元，可結合;C、有單位元、可交換;每元有逆元，有零元。卜面（）哈斯圖所描述的偏序關系構成分配格。9.下列（中的運算符都是可交換的。CIC、10 .設G是n個結點、m條邊和r個面的連通平面圖，則 m等于（A、n+r-2 ;B、 n-葉2 ;C、n-2 ;D、n+葉2。11. n個結點的無向完全圖 Kn的邊數(shù)為（A、n（nn(n 1

3、)1) ；B、2；n(n 1)C、n(n 1) ；d、2。12.下列圖中( )是根樹。A、Ga,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.設 P: 2 X2=5, Q:雪是黑的，R:2X4=8, S：太陽從東方升起，下列（）命題的真值為真。A、PQR B、R P S ；C、 在一個有 n個元素的集合上，可以有 種不同的關系，有種不同的函數(shù)。 3若關系R是反對稱的，當且僅當關系矩陣中 ，在關系圖上 。 4設g f是

4、一個復合函數(shù)，若 g和f都是滿射，則g f為 ，若g禾廿f者e是入射，貝y g f是 。 三階群有 個（不同構），其運算表為 。Q R； D、(PR) (Q S)。14.下面（）命題公式是重言式。A、PQR .B、(PR)(PQ)；c、（PQ)(QR) ；D、(P(QR)(PQ)(P R)。15設 L(x):x是演員，J(x): x 是老師，A(x , y):x欽佩y,命題“所有演員都欽佩某些老師”符號化為（）。A、 x(L(x)A(x, y)；B、x(L(x)y(J(y)A(x, y)；C、 x y(L(x)J(y) A(x, y) ； D、xy(L(x)J(y)A(x, y)。二、填空題：

5、（每空1分，本大題共15 分)1設 M x1 x12,x被2整除,x ZNx1 x12,x被3整除，x Z則M NMNc01011011A11006設圖 G = , V V1，V2,V3, V4的鄰接矩陣1000 ，則V1的入度deg (w)= , V4 的出度 deg(V4)= ，從 v到 v的長度為2的路有條。7 命題公式A P ( P (Q ( Q R)的主合取范式為 ，其編碼表示為 。三、判斷改正題：判斷下列各題是否正確，正確的劃“V”錯誤的劃“ ”并加以改正。(每小題2分，本大題共20分)1. A , B, C為任意集合，若ABAC，則B = C。()2 設R是實數(shù)集，R上的關系f

6、x,y x y 2,x, y R , r是相容關系。( )3 .設A,w 是偏序集，B A，貝V B的極大元b B且唯一。()4謂詞公式 xP(x) xQ(x)yR(y)的前束范式是x z y(P(x) Q(z) R(y) o()5.在代數(shù)系統(tǒng) S , 中，若一個元素的逆元是唯一的，其運算 必是可結合的。()6.每一個有限整環(huán)疋疋域，反之也對。(7.有割點 的連通圖可臺匕 冃匕是哈密爾頓 圖 。()8x(A(x)B(x)xA(x)xB(x)o()9無多重邊的圖是簡單圖。()10 .設A,是布爾代數(shù)，則A,一*定為有補分配格。()四、簡答題：(每小題5分，本大題共20分)1 .設R1和R2是A上

7、的任意二元關系，如果 R1和R2是自反的，R1 R2是否也是自反的,為什么？如果 R1和R2是對稱的，R1 R2是對稱的嗎？2. 如圖給出的賦權圖表示六個城市a,b,c,d,e, f及架起城市間直接通訊線路的預測造價。試給出一個設計方案使得各城市間能夠通訊且總造價最小，并計算出最小總造價。設S = R - -1（ R為實數(shù)集），a（1）說明S，是否構成群（P R）劃為只含有聯(lián)結詞，b a b ab。；（2 ）在S中解方程的等價公式。五、證明題：（共30分）1 .設A 1,2,3,9，在A A上定義關系R ： a, b , c, dR當且僅當a d b c,證明R是A A上的等價關系，并求出2,

8、5 r2.用CP規(guī)則證明A (B C) , (EF)C B (A S)3. 將下列命題形式化，并證明結論的有效性：所有有理數(shù)都是實數(shù)，某些有理數(shù)是整數(shù)。 因此，某些實數(shù)是整數(shù)。n 15.證明：若T是有n個結點的完全二叉樹，則 T有 2 片葉子。答案一、單項選擇題：題號123456789答案CDDBADBDD題號101112131415答案ADCADB、填空題:21. 6 , 12 ; 2 , 4, 8, 10。2 . 2n ; nn。3.以主對角線為對稱的元素不能同時為1;4.滿射；入射。兩個不同結點間的定向弧線，不可能成對出現(xiàn)。ecrK5. 1 ；eabaabebbea6.3 ；1； 1。7

9、.(PQ R) (P QR) ； M 000三、判斷改正題：1.X若A B A C ,則不一定B3.XB的極大元b B但可以不唯一。5.X運算*不一定可結合。67.X有割點的連通圖不可能是漢密爾頓圖。9.X無多重邊和自環(huán)的圖是簡單圖。四、簡答題：1 .解：若R，R2是自反的，則RlM 001oC 。 2.2。4. V 。.X 有限整環(huán)一定是域，但反之不成立。8.2。10 .2 。R2也是自反的。因為a A， R1，R2 自反,a, aR| , a,aR2，從而a，aR1R2即R R2也是自反的。若尺,R2是對稱的，但R R2不一定是對稱的。b,a ，R2 b,c , c,b ，則 R , R2

10、是對如: A = a , b , c ， R a,b稱的，但R1 R2 a,C 不是對稱的。2要設計一個方案使各城市間能夠通訊且總造價最小，即要求該圖連通、無回路、邊權之和最小的子圖即最小生成樹，由避圈法或破圈法可得: aI - 其最小生成樹為：b5_o-f 其樹權即最小造價為：1+2+3+5+7=18。e/3.解：(1) 1)a,bS易證 a ba b ab S，即運算*是封閉的。2)a, b, c S(ab) c (a bab) ca bab c (a bab)ca bc abac bcabc,而(2)由a (b e) a (b e be) a (b e be) be ab ae abe,

11、(a b) c a (be），即*可結合。3)設4)出,S關于*有幺元e,S,ee eaS設有逆元S,。則aa(b c be)1 aa，即S中任意元都有逆元，綜上得構成群。2x3x6x12x11 7R)(PQ) R (PR)。五、證明題：1.證明:1)a, bA A ,a bb a ,a,b,a,b2)a,be,dR,則ad b e,d a e b即e bda ,從而e,d,a,bR即R對稱。a,b,e,dR,e,d , e, fR,3)則adb e, ef def de e從而afa d ee be e e bea, b,e, fR,即R傳遞。綜上得出，R是等價關系。2,5r a,ba, b

12、A A, a 5b 2 a,ba,bA A , a b3且 1,4 ,2,5 ,3,6 , 4,7 ,5,8 ,6,92證明:(1)BP（附加前提）(2)B(AS)PQ)Q)(PR)(PR)(PR (P4解：原式R,A ST(1)(2)l即R自反。(4) AT(3)IA B CPB CT(4)(5)l(7) CT(6)I(8)(EF)CP(9)(EF)T(7)(8)I(10) E FT(9)E(11) ET(10)I(12) B ECP3.解：設Q(x) : x是有理數(shù)，R(x) : x是實數(shù)，Z(x) : x是整數(shù)。命題形式化：x(Q(x) R(x), x(Q(x) Z(x)卜 x(R(x) Z(x)。證明：(