(完整word版)離散數(shù)學(xué)試卷及答案(24)

1、離散數(shù)學(xué)試卷（24）1583.下圖描述的偏序集中，子集b,e, f的上界為 （一、填空題：（每空 1 分，本大題共 15 分）1設(shè)A =2,a,3 ,4,B =a ,3,4,1，請?jiān)谙铝忻繉现刑钊脒m當(dāng)?shù)姆枺?，?1)a_B,a ,4,30，x 是奇數(shù)，2設(shè)A=0,1，N為自然數(shù)集，f（x，是偶數(shù)。若TA，則f是3.設(shè)圖 G = 中有 7 個(gè)結(jié)點(diǎn)，各結(jié)點(diǎn)的次數(shù)分別為2，4, 4，6，5，5，2，則 G 中有_條邊，根據(jù) _ 。4兩個(gè)重言式的析取是 _，一個(gè)重言式和一個(gè)矛盾式的合取是 _。5 設(shè)個(gè)體域?yàn)樽匀粩?shù)集，命題“不存在最大自然數(shù)”符號化為_。6設(shè) S 為非空有限集，代數(shù)系統(tǒng)：2S，一

2、中幺元為 _，零元為 _ 。7 .設(shè) P、Q 為兩個(gè)命題，其 De-Morden 律可表示為 _ 。&當(dāng)G| =8時(shí)，群cG嚴(yán) 只能有_ 階非平凡子群，不能有 _階子群，平凡子群為 _。二、單項(xiàng)選擇題：（每小題 1 分，本大題共 15 分）1設(shè)A=x x 是整數(shù)且 x21$，下面哪個(gè)命題為假（）。B、-3, -2, -1 A;D、x x 是整數(shù)且 x : 4 A。2設(shè)A = A , B=，：，則 B A 是（）。A、：； B、;C、,：; D、門。_ 射的，若 f:N A，貝U f是射的。A、0,1,2,4 A;離散數(shù)學(xué)試卷（24）1594設(shè)f和g都是 X 上的雙射函數(shù)，則（f g）-

3、為（）。A、f gJ； B、（gf）J；C、gJf；D、gf_1。5.下面集合（）關(guān)于減法運(yùn)算是封閉的。A、N ； B、2X Xl；C、2X+1 XE 1；D、XX 是質(zhì)數(shù)。6. 具有如下定義的代數(shù)系統(tǒng):G ，（）不構(gòu)成群。A、G =1,10, * 是模 11 乘；B、G =1,3,4,5,9, * 是模 11 乘；）關(guān)于整除關(guān)系構(gòu)成格。C、G = Q（有理數(shù)集），*是普通加法D、G=Q（有理數(shù)集），*是普通乘法。7.設(shè)G二2m3n則代數(shù)系統(tǒng):G , 的幺元為（A、不存在B、e=23； C、e=2 39.A、2 , 3,C、1 , 2,12, 24, 36;5, 6, 15, 30;設(shè)V =a

4、,b,c,d,e, f,B、1 , 2, 3,D、3 , 6, 9 ,4, 6,12。8, 12;離散數(shù)學(xué)試卷（24）16012.含有 3 個(gè)命題變元的具有不同真值的命題公式的個(gè)數(shù)為（E = : a , b，: b , c , : c , a，: a , d，: d , ef , e ,則有向圖G =：V , ED、不連通的。C、度數(shù)為奇數(shù)的結(jié)點(diǎn)出度為奇數(shù)的結(jié)點(diǎn)A、 度數(shù)為偶數(shù)入度為奇數(shù)的結(jié)點(diǎn)B、;C、弱連通的A、強(qiáng)連通的； B、單側(cè)連通的離散數(shù)學(xué)試卷（24）16113.下列集合中哪個(gè)是最小聯(lián)結(jié)詞集（14.下面哪個(gè)命題公式是重言式（15在謂詞演算中，下列各式哪個(gè)是正確的A2B二：0,1, 1,

5、：0,1,2 , (Q(x)R(x) ,-(Q(a)R(a) , S(a) ,-x(S(x)G(x)的有效結(jié)論。3.若有 n 個(gè)人，每個(gè)人都恰有三個(gè)朋友，則n 必為偶數(shù)。4設(shè) G 是(11 , m)圖，證明 G 或其補(bǔ)圖G是非平面圖。一、填空題1.( 1),(2)冬。2雙射，滿射。 3. 14deg(vJ=：2E4.重言式，矛盾式。 5.-xTy(y . x), 6. ：,S。離散數(shù)學(xué)試卷(24)1647.(P Q)二一P Q , -(P Q)= P Q;P(P Q)=P, P(P Q) =P。& 2, 4;3,5, 6, 7;: e,，:G,。、單項(xiàng)選擇題題號123456789101

6、112131415答案ACBCBDBCCACCABA三、判斷改正題1.x2A-B=2A一 2B。2.xA2x B =0,0, A , 0,0,2 a , , 0,1,2 A , , 1,0,，a , Q(x)。四、簡答案題1.解r()=：a,a，:：a,b，:：b,c，: c,b，:：b, b，:：c, c,s(;?) =a, a，:：a, b，:：b,c，:：c,b，:b, a,2二=：a, a，:：a,b，:：a,c，:b, b，:c,c,3二；2 =：a, a，:a,b，: a, c，:a, b，: b,c，:c, b ,離散數(shù)學(xué)試卷（24）1652t（町 彳:a,a ,：a,b，: a

7、, c，: b,b，: c,c，:b, c，:c,b 。2解：的哈斯圖為3解此問題的最優(yōu)設(shè)計(jì)方案即要求該圖的最小生成樹, 由破圈法或避圈法得最小生成樹為：其權(quán)數(shù)為 1 + 1+3+4 = 9。4.解：:G,7既構(gòu)成群，又構(gòu)成循環(huán)群，其生成元為沢71234561123456224613533625144415263553164266543211 ）由運(yùn)算表知，7封閉；2）7可結(jié)合（可自證明）集合最大兀極大兀下界上確界A無24, 36無無B12126, 2, 312C66無63，5。因?yàn)椋?的運(yùn)算表為:32離散數(shù)學(xué)試卷(24)1663） 1 為幺元；4）11,2仁4, 3-5 ,4仁2, 5 3

8、, 6仁6 ,離散數(shù)學(xué)試卷(24)167綜上所述，G,7.構(gòu)成群。由31=3,32= 2,33=6,34=4,35,36=1。所以，3 為其生成元，3 的逆元 5 也為其生成元。故:G，7-為循環(huán)群。5. 解：命題公式對應(yīng)的二元樹見右圖。五、證明題1 .證明：(1)-a A,；R , S 自反,：:：a, a三R ,：a, aS ,:a, a，二R S , ” R S自反。(2)一a, b A，若:a, bER S，則：:：a,b沁R ,：a, b沁S ,由 R , S 對稱， 所以，：:b,a沙R ,：b,a沁S , :b,aR S，所以R S對稱。(3)一a,b,c A，若：a,b三RS

9、,：b,c沁R S ,貝U：a,b三R ,：a,b匕三S ,:b,c三R ,：b,c H S ,由 R , S 傳遞性知，：:：a,c三R，:a,c三S ,從而:a,c R - S,所以，R- S傳遞。綜上所述，R-S是 A 上的等價(jià)關(guān)系。2證明：(1)-xP(x) (Q(x)P(x)P(2)P(a) (Q(a)P(a)US(1)-(Q(a)R(a)P離散數(shù)學(xué)試卷(24)168P(a)T(2)(3)I-x(S(x)，G(x)PS(a)G(a)US(5)S(a) G(a)T(6)E,I(8)S(a)P(9)G(a)T(8)1(10)一 P(a) G(a)T(4)(9)1所以，結(jié)論有效。3證明：將每個(gè)人用結(jié)點(diǎn)表示，當(dāng)兩個(gè)人是朋友時(shí)，則對應(yīng)兩結(jié)點(diǎn)連一條邊，則得一無向圖G=V,E。因?yàn)槊總€(gè)人恰有三個(gè)朋友，所以，deg(u)=3,(-u V)，由任意圖奇數(shù)度結(jié)點(diǎn)一定是偶數(shù)個(gè)，可知，此圖結(jié)點(diǎn)數(shù)一定是偶數(shù)。14證明：因?yàn)?G 為(11，m)圖，.G 為(11, m)圖，且m m 11 10 = 55。設(shè)2G =： V, E，任v V，則v在 G 中度數(shù)與v在G度數(shù)之和定為n -1 = 10，若有某點(diǎn)v在G