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

1、試卷二十四試題與答案一、填空題：（每空1分，本大題共15分）1設(shè)，請(qǐng)?jiān)谙铝忻繉?duì)集合中填入適當(dāng)?shù)姆?hào)：。 （1） , (2) 。2設(shè)，N為自然數(shù)集，若，則是 射的，若，則是 射的。3設(shè)圖G = < V ，E >中有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ù)”符號(hào)化為 。6設(shè)S為非空有限集，代數(shù)系統(tǒng)中幺元為 ，零元為 。7設(shè)P、Q為兩個(gè)命題，其De-Morden律可表示為 。8當(dāng)時(shí)，群只能有 階非平凡子群，不能有 階子群，平凡子群為 。二、單項(xiàng)選擇

2、題：（每小題1分，本大題共15分）1設(shè)，下面哪個(gè)命題為假（ ）。 A、； B、；C、； D、。2設(shè)，則BA是（ ）。A、； B、； C、； D、。3下圖描述的偏序集中，子集的上界為 （ ）。A、； B、； C、； D、。4設(shè)和都是X上的雙射函數(shù)，則為（ ）。A、； B、； C、； D、。5下面集合（ ）關(guān)于減法運(yùn)算是封閉的。A、N ； B、2IxxÎ； C、； D、。6具有如下定義的代數(shù)系統(tǒng)，（ ）不構(gòu)成群。A、，*是模11乘 ； B、，*是模11乘 ；C、（有理數(shù)集），*是普通加法 ； D、（有理數(shù)集），*是普通乘法。7設(shè)，*為普通乘法。則代數(shù)系統(tǒng)的幺元為（ ）。A、不存在 ； B

3、、； C、； D、。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è)，則有向圖是（ ）。A、強(qiáng)連通的 ； B、單側(cè)連通的 ； C、弱連通的 ； D、不連通的。10下面那一個(gè)圖可一筆畫出（ ）。11在任何圖中必定有偶數(shù)個(gè)（ ）。A、度數(shù)為偶數(shù)的結(jié)點(diǎn) ； B、入度為奇數(shù)的結(jié)點(diǎn) ；C、度數(shù)為奇數(shù)的結(jié)點(diǎn) ； D、出度為奇數(shù)的結(jié)點(diǎn) 。12含有3個(gè)命題變?cè)木哂胁煌嬷档拿}公式的個(gè)數(shù)為（ ）。A、； B、； C、； D、。13下列集合中哪個(gè)是最小聯(lián)結(jié)詞集（ ）。A、； B、；

4、C、； D、。14下面哪個(gè)命題公式是重言式（ ）。A、； B、；C、； D、。15在謂詞演算中，下列各式哪個(gè)是正確的（ ）。A、； B、；C、； D、。三、判斷改正題：（每小題2分，本大題共20分）1設(shè)，則 。（其中為P（A） ( )2設(shè)，則 。 （ ）3集合A上的恒等關(guān)系是一個(gè)雙射函數(shù)。 （ ）4設(shè)Q為有理數(shù)集，Q上運(yùn)算 * 定義為，則是半群。（ ）5階數(shù)為偶數(shù)的有限群中，周期為2的元素的個(gè)數(shù)一定為偶數(shù)。 （ ）6在完全二元樹中，若有片葉子，則邊的總數(shù)。 （ ）7能一筆畫出的圖不一定是歐拉圖。 （ ）8設(shè)P，Q是兩個(gè)命題，當(dāng)且僅當(dāng)P，Q的真值均為T時(shí)，的值為T。（ ）9命題公式是重言式。 （

5、 ）10設(shè) 命題“所有的研究生都讀過大學(xué)”符號(hào)化為：。 （ ）四、簡答題：（25分）1設(shè)，A上的關(guān)系 ，求出 。2集合上的偏序關(guān)系為整除關(guān)系。設(shè)，試畫出的哈斯圖，并求A，B，C的最大元素、極大元素、下界、上確界。3圖給出的賦權(quán)圖表示五個(gè)城市及對(duì)應(yīng)兩城鎮(zhèn)間公路的長度。試給出一個(gè)最優(yōu)化的設(shè)計(jì)方案使得各城市間能夠有公路連通。4已知，為模7乘法。試說明是否構(gòu)成群？是否為循環(huán)群？若是，生成元是什么？5給定命題公式，試給出相應(yīng)的二元樹。五、證明題：（25分）1如果集合A上的關(guān)系R和S是反自反的、對(duì)稱的和傳遞的，證明：是A上的等價(jià)關(guān)系。2用推理規(guī)則證明是 的有效結(jié)論。3若有n個(gè)人，每個(gè)人都恰有三個(gè)朋友，則n

6、必為偶數(shù)。4設(shè)G是（11，m）圖，證明G或其補(bǔ)圖是非平面圖。答案一、填空題1（1）， （2）。 2雙射 ， 滿射。 314 ，。4重言式 ，矛盾式 。 5， 6，S 。 7； 。82，4； 3，5，6，7；。二、單項(xiàng)選擇題題號(hào)123456789101112131415答案ACBCBDBCCACCABA三、判斷改正題1× 。2× 3 。4 。 5× 階數(shù)為偶數(shù)的有限群中周期為2 的元素個(gè)數(shù)一定為奇數(shù)。6× 完全二叉樹中，邊數(shù)。 7 。 8× 當(dāng)且僅當(dāng)P，Q的真值相同時(shí)，的真值為T。 9 。 10× 。四、簡答案題1解， ， ，。2解：的

7、哈斯圖為集合最大元極大元下界上確界A無24，36無無B12126，2，312C66無63解此問題的最優(yōu)設(shè)計(jì)方案即要求該圖的最小生成樹， 由破圈法或避圈法得最小生成樹為： 其權(quán)數(shù)為1+1+3+4 = 9 。4解：既構(gòu)成群，又構(gòu)成循環(huán)群，其生成元為3，5。因?yàn)椋旱倪\(yùn)算表為： 1234561123456224613533625144415263553164266543211）由運(yùn)算表知，封閉；2）可結(jié)合（可自證明）3）1為幺元；4），綜上所述，構(gòu)成群。 由，。所以，3為其生成元，3的逆元5也為其生成元。故為循環(huán)群。5解：命題公式對(duì)應(yīng)的二元樹見右圖。五、證明題1證明：（1） 自反。 （2），若，則由R ，S對(duì)稱， 所以，所以 對(duì)稱。 （3），若則由R ，S傳遞性知，從而 所以，傳遞。綜上所述，是A上的等價(jià)關(guān)系。2證明：（1） P （2） US(1) (3) P (4) T(2)(3)I (5) P (6) US(5) (7) T(6)E,I (8) P (9) T(7)(8)I (10) T(4)(9)I所以，結(jié)論有效。3證明：將每個(gè)人用結(jié)點(diǎn)表示，當(dāng)兩個(gè)人是朋友時(shí)，則對(duì)應(yīng)兩結(jié)點(diǎn)連一條邊，則得一無向圖 。因?yàn)槊總€(gè)人恰有三個(gè)朋友，所以，由任意圖奇數(shù)度結(jié)點(diǎn)一定是偶數(shù)個(gè)，可知，此圖結(jié)點(diǎn)數(shù)一定是偶數(shù)。