kan試卷二十四試題與答kan案

1、試卷二十四試題與答案、填空題：(每空 1 分，本大題共 15 分)1.設(shè)A 2,a,3,4 ,B a，3,4，請(qǐng)?jiān)谙铝忻繉?duì)集合中填入適當(dāng)?shù)姆?hào):(1)a_B , (2)a,4,3 _A。0， x 是奇數(shù)，f (x)2.設(shè)A 0,0，N 為自然數(shù)集，1，x是偶數(shù)。若f:A A，則f是_射的，若f:NA，則f是_ 射的。3.設(shè)圖 G = 中有 7 個(gè)結(jié)點(diǎn)，各結(jié)點(diǎn)的次數(shù)分別為 2, 4, 4, 6, 5, 5，2，貝UG 中有_條邊，根據(jù) _ 。4 .兩個(gè)重言式的析取是_ , 一個(gè)重言式和一個(gè)矛盾式的合取A 0,1,2,4 A;B3,2,1 A；、x x 是整數(shù)且|x 41B 、(g f);1 設(shè)

2、A x x 是整數(shù)且16，下面哪個(gè)命題為假（c、2.設(shè)AB , ，則 B A 是(A M ” ; B、 ;C、, ;3.下圖描述的偏序集中，子集b,e, f的上界為C、4 .設(shè)f和g都是 X 上的雙射函數(shù)，則(f g)1為（5.下面集合）關(guān)于減法運(yùn)算是封閉的。2x x? I ; C、2x1 x I;7D、x x 是質(zhì)數(shù)6.具有如下定義的代數(shù)系統(tǒng)G,）不構(gòu)成群。f、G 1,3, 4,5,9, *是模 11 乘；CG Q（有理數(shù)集），*是普通加法；D、G Q（有理數(shù)集），*是普通乘法AG 1,10, * 是模 11 乘；13.下列集合中哪個(gè)是最小聯(lián)結(jié)詞集（)c r m on i7設(shè)G 2 3 m,

3、n I, *為普通乘法。則代數(shù)系統(tǒng)G，的幺元為（）0 0 _ 11A、不存在；B、e 23； C、e 2 3 ； D、e 23。8 下面集合（）關(guān)于整除關(guān)系構(gòu)成格。A 2，3，6，12，24，36 ； B 、1，2，3，4，6，8，12；C 1，2，3，5，6，15，30 ； D 、3，6，9，12。9.設(shè)V a,b,c,d,e, f，E a , b , b ,c , c , a , a , d , d , e , f , e ，則有向圖GV,E是（）。A、強(qiáng)連通的；B、單側(cè)連通的；C、弱連通的；D、不連通的。10. 下面那一個(gè)圖可一筆畫出（）。11 .在任何圖中必定有偶數(shù)個(gè)（）12.含有 3

4、 個(gè)命題變?cè)木哂胁煌嬷档拿}公式的個(gè)數(shù)為（）A 23；B 、32； C 、223；A、度數(shù)為偶數(shù)的結(jié)點(diǎn)B 、入度為奇數(shù)的結(jié)點(diǎn)；C 度數(shù)為奇數(shù)的結(jié)點(diǎn)D 、出度為奇數(shù)的結(jié)點(diǎn)A、 , ； B 、 , ； C 、； D 、 , , 14下面哪個(gè)命題公式是重言式()。A、(P Q) (Q R)； B 、(P Q) P；C、( P Q) (P Q)； D 、(P Q) P。15在謂詞演算中，下列各式哪個(gè)是正確的()。A、x yA( x, y)y xA(x,y)；B、x yA(x, y)y xA(x,y)；C、x yA(x,y) y xA(x,y)；D、A(a)xA(x)三、判斷改正題：(每小題 2 分

5、，本大題共 20 分)1 設(shè)A1，2,Ba，則2A 2B 2A B0(其中 2A為 P (A)()2設(shè)A 0,1，B 1, 2，則2A2B 0,1,1, 0,1,2,1,0,1, 1, 0,2 3 集合 A 上的恒等關(guān)系是一個(gè)雙射函數(shù)定義為a b max(a,b)，則Q， 是半群0(5.階數(shù)為偶數(shù)的有限群中，周期為 2 的元素的個(gè)數(shù)一定為偶數(shù)0()6. 在完全二元樹中，若有 t 片葉子，則邊的總數(shù) e 2t 1o()7.能一筆畫出的4.設(shè) Q 為有理數(shù)集，Q 上運(yùn)算圖不一定是歐拉圖。()8 設(shè) P, Q 是兩個(gè)命題，當(dāng)且僅當(dāng) P, Q 的真值均為 T 時(shí)，P Q的值為 T。()9命題公式(P(

6、PQ) Q是重言式。()10設(shè)P(x)： x 是研究生，Q(x): x 曾讀過(guò)大學(xué)，命題“所有的研究生都讀過(guò)大學(xué)”符號(hào)化為：x(P(x) Q(x)。()四、簡(jiǎn)答題：(25 分)1設(shè)Aa,b,c，A 上的關(guān)系 a,a , a,b , b ,c , c,b ，求出r( ),S )和 t()。2.集合A2,3,6，12,24,36上的偏序關(guān)系？為整除關(guān)系。設(shè)B 6,12, C 2,3，6，試畫出？的哈斯圖，并求 A，B, C 的最大元素、極大元素、下界、上確界3.圖給出的賦權(quán)圖表示五個(gè)城市V1，V2，V3，V4，V5及對(duì)應(yīng)兩城鎮(zhèn)間公路的長(zhǎng)度。試給出一個(gè)最優(yōu)化的設(shè)計(jì)方案使得各城市間能夠有公路連通。4.

7、 已知G 1，2，3，4，5，6，7為模 7 乘法。試說(shuō)明G，7是否構(gòu)成群？是否為循環(huán)群？若是，生成元是什么？5. 給定命題公式(P( QR)( SW)，試給出相應(yīng)的二元樹。五、證明題：(25 分)8.1 如果集合 A 上的關(guān)系 R 和 S 是反自反的、對(duì)稱的和傳遞的，證明： R S 是 A 上的等價(jià)關(guān)系。2用推理規(guī)則證明P(a)G(a)是x(P(x) (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è)是(ii, m 圖，證明 G 或其補(bǔ)圖 G 是非平面圖。答案、填空題、單項(xiàng)選擇題4.7.

8、(i)，重言式，(P Q)(2)矛盾式P (P Q)P,2, 4; 3， 5,2 雙射，滿射。5 .xy(yQ，(PP (P6, 7;e，Q)Q),G,3 . 14deg(Vi) 2EViV。x)，8.題號(hào)123456789101112131415答案ACBCBDBCCACCABA三、判斷改正題2.X3.V。4.V。5.X階數(shù)為偶數(shù)的有限群中周期為 2 的元素個(gè)數(shù)一定為奇數(shù)6.X完全二叉樹中，邊數(shù)e 2(t 1)。7 .V08.X當(dāng)且僅當(dāng) P, Q 的真值相同時(shí)，PQ的真值為 To9 .V o10.Xx(P(x) Q(x)o四、簡(jiǎn)答案題1.解r( ) a, a ,a,b,b, c,c,b,b,

9、b,c,c s( ) a, a ,a,b,b,c,c,b,b, a2a, a ,a,b,a,c,b,b,c,c ,32a,a ,a,b ,a,c ,a,b ,b, c , c, b t()2a,a ,a,b ,a,c ,b,b , c, c , b,c ,c,b 2.解：？的哈斯圖為1.X2A B2A2B4解：G，7既構(gòu)成群，又構(gòu)成循環(huán)群，其生成元為 3, 5。因?yàn)椋?的運(yùn)算表為:123456112345622461353362514441526355316426654321集合最大兀極大元下界上確界A無(wú)24, 36無(wú)無(wú)B12126, 2, 312C66無(wú)6由破圈法或避圈法得最小生成樹為：其權(quán)

10、數(shù)為 1+1+3+4 = 91）由運(yùn)算表知，7封閉;五、2）7可結(jié)合（可自證明）3)4)1 為幺元;1112143154? ? ?綜上所述，G，7構(gòu)成群。以，3 為其生成元,故G，7為循環(huán)群。由313321.證明：（1）A,a, aS,(2)a,bA，若所以，b,a3，61 6，336344355361? ? ?3 的逆元 5 也為其生成元。5.解：命題公式對(duì)應(yīng)的二元樹見右圖。證明題R, Si反，a,aR S自反。a,b R S，則R , b, a S ,R,a, bb, aa,a S,R , a,b S,由 R，S 對(duì)稱,所以R S 對(duì)稱。（3）a,b,c A，若a,bR S, b,cS,則

11、a,bR, a,b S ,b, c R , b, cS,R，S 傳遞性知,a,cR,a,c S,從而a,cRS,所以，R S 傳遞。綜上所述，R S 是 A 上的等價(jià)關(guān)系(3)(Q(a)R(a)P(4)P(a)T(2)(3)I(5)x(S(x)G(x)P(6)S(a)G(a)US(5)(7)S(a)G(a)T(6)E,I(8)S(a)P(9)G(a)T(7)(8)I(10)P(a)G(a)T(4)(9)I所以，結(jié)論有效。G V,E。因?yàn)槊總€(gè)人恰有三個(gè)朋友，所以，deg(u) 3, ( u V)，3證明：將每個(gè)人用結(jié)點(diǎn)表示，當(dāng)兩個(gè)人是朋友時(shí)，則對(duì)應(yīng)兩結(jié)點(diǎn)連一條邊，則得一無(wú)向2證明：1)xP(x)(Q(x) P(x)2)P(a)(Q(a) P(a)US(1)由任意圖奇數(shù)度結(jié)點(diǎn)一定是偶數(shù)個(gè)，可知，此圖結(jié)點(diǎn)數(shù)一定是偶數(shù)4證明：因?yàn)?G*( 11,m 圖，G為(代m)圖，且m m211 10 55。設(shè)G V，E, 任 V V，則v在 G 中度數(shù)與v在 G 度數(shù)之和定為 n 1 10，若有某點(diǎn)v在 G 中deg(v)4, 則在 G 中deg(v)6,由定理，G為非平面圖。易證 G G 存在漢密爾頓路，所以，連 通。若deg(v)5，貝仙定理，假設(shè) G G 都為簡(jiǎn)單連通平面圖，則 m 3 11 6 27，m 3 11 6 27，于是 m m 54 與 m