1、一、單項(xiàng)選擇題：（每小題1分，本大題共10分）1命題公式是（ ）。A、 矛盾式； B、可滿足式； C、重言式； D、等價(jià)式。2下列各式中哪個(gè)不成立（ ）。 A、 ；B、；C、；D、。3謂詞公式中的 x是（ ）。A、自由變元； B、約束變元；C、既是自由變元又是約束變元； D、既不是自由變元又不是約束變元。4在0 之間應(yīng)填入（ ）符號。 A、= ； B、 ； C、 ； D、 。5設(shè)< A ， > 是偏序集，下面結(jié)論正確的是（ ）。 A、的極大元且唯一； B、的極大元且不唯一；C、的上界且不唯一； D、的上確界且唯一。6在自然數(shù)集N上，下列（ ）運(yùn)算是可結(jié)合的。（對任意） A、 ； B

2、、 ；C、 ； D、。7Q為有理數(shù)集N，Q上定義運(yùn)算*為a*b = a + b ab ,則<Q，*>的幺元為（ ）。 A、a； B、b； C、1； D、0。8給定下列序列，（ ）可以構(gòu)成無向簡單圖的結(jié)點(diǎn)次數(shù)序列。 A、（1，1，2，2，3）； B、（1，1，2，2，2）；C、（0，1，3，3，3）； D、（1，3，4，4，5）。9設(shè)G是簡單有向圖，可達(dá)矩陣P(G)刻劃下列 （ ）關(guān)系。A、點(diǎn)與邊； B、邊與點(diǎn)； C、點(diǎn)與點(diǎn)； D、邊與邊。10一顆樹有兩個(gè)2度結(jié)點(diǎn)，1個(gè)3度結(jié)點(diǎn)和3個(gè)4度結(jié)點(diǎn)，則1度結(jié)點(diǎn)數(shù)為（ ）。A、5； B、7； C、9； D、8。二、填空：（每空1分，本大題共1

3、5分）1在自然數(shù)集中，偶數(shù)集為、奇數(shù)集為，則= ； = 。2設(shè)，則 r (R) = ；s (R) = ；t (R) = 。3設(shè)R為集合A上的等價(jià)關(guān)系，對，集合= ， 稱為元素a形成的R等價(jià)類，因?yàn)?。4任意兩個(gè)不同小項(xiàng)的合取為 ，全體小項(xiàng)的析取式為 。5設(shè)，則下列命題：（1）存在唯一偶素?cái)?shù)；（2）至多有一個(gè)偶素?cái)?shù)；分別形式化：（1） ；（2） 。6設(shè)T為根樹，若 ，則稱T為m元樹；若 則稱T為完全m叉樹。7含5個(gè)結(jié)點(diǎn)，4條邊的無向連通圖（不同構(gòu)）有 個(gè)，它們是 。三、判斷改正題：（每小題2分，本大題共20分）1命題公式是一個(gè)矛盾式。 （ ）2任何循環(huán)群必定是阿貝爾群，反之亦真。 （ ）3根樹中

4、最長路徑的端點(diǎn)都是葉子。 （ ）4若集合A上的關(guān)系R是對稱的，則也是對稱的。 （ ）5數(shù)集合上的不等關(guān)系（）可確定A的一個(gè)劃分。 （ ）6設(shè)集合A、B、C為任意集合，若A×B = A×C，則B = C。 （ ）7函數(shù)的復(fù)合運(yùn)算“。”滿足結(jié)合律。 （ ）8若G是歐拉圖，則其邊數(shù)合結(jié)點(diǎn)數(shù)的奇偶性不能相反。 （ ）9圖G為（n , m）圖，G的生成樹必有n個(gè)結(jié)點(diǎn)。 （ ）10使命題公式的真值為F的真值指派的P、Q、R值分別是T、F、F。 （ ）四、簡答題（每小題5分，本大題共25分）1設(shè)和都是群的子群，問和是否是的子并說明理由。2設(shè)，從A到B的關(guān)系，試給出R的關(guān)系圖和關(guān)系矩陣，并

5、說明此關(guān)系是否為函數(shù)？為什么？3設(shè)是半群，是左零元，對任是否是左零元？為什么？4某次會(huì)議有20人參加，其中每人至少有10個(gè)朋友，這20人擬圍一桌入席，用圖論知識說明是否可能每人鄰做的都是朋友？（理由）5通過主合取范式，求出使公式的值為F的真值指派。五、證明題：（共30分）1設(shè)R為集合A上的二元關(guān)系，如果R是反自反的和可傳遞的，則R一定是反對稱的。2試證明若是群，且任意的，對每一個(gè)，有，則是的子群。3設(shè)G是每個(gè)面至少由（）條邊圍成的連通平面圖，試證明，其中為結(jié)點(diǎn)數(shù)，為邊數(shù)。4符號化下列各命題，并說明結(jié)論是否有效（用推理規(guī)則）。任何人如果他喜歡美術(shù)，他就不喜歡體育。每個(gè)人或喜歡體育，或喜歡音樂，有

6、的人不喜歡音樂，因而有的人不喜歡美術(shù)。一、單項(xiàng)選擇題：題號12345678910答案CACDDBDBCC二、填空題：1。 2， ， ， ，所以， 。3； 。4永假式（矛盾式），永真式（重言式）。5（1）。 （2）。6每個(gè)結(jié)點(diǎn)的出度都小于等于m；除葉子外，每個(gè)結(jié)點(diǎn)的出度都等于m。73。三、判斷改正題：1× 命題公式是一個(gè)重言式。2× 任何循環(huán)群必定是阿貝爾群，但反之不真。3× 根樹中最長路徑的端點(diǎn)不都是葉子。4 5× 不能確定A的一個(gè)劃分。 6 7 8× 歐拉圖其邊數(shù)和結(jié)點(diǎn)數(shù)的奇偶性可以相反。 9 10 四、簡答題1解： 是 的子群，不一定是的子

7、群。 都是的子群， 的子群。如：G = 1，5，7，11，：模12乘，則為群。且H = 1，5，K = 1，7， 皆為的子群，但， 不是的子群。因?yàn)?，即運(yùn)算不封閉。A2349B24710122解：則R的關(guān)系圖為：R的關(guān)系矩陣為 關(guān)系R不是A到B的函數(shù)，因?yàn)樵?，4的象不唯一（或元素9無象）。3解：仍是左零元。因?yàn)椋捎谑亲罅阍裕?為半群，所以*可結(jié)合。 所以，所以，仍是左零元。4解：可能。將人用結(jié)點(diǎn)表示，當(dāng)兩人是朋友時(shí)相應(yīng)結(jié)點(diǎn)間連一條邊，則得一個(gè)無向圖，20人圍一桌，使每人鄰做都是朋友，即要找一個(gè)過每個(gè)點(diǎn)一次且僅一次得回路。由題已知， ，由判定定理，G中存在一條漢密爾頓回路。即所談情況可能。5解：使公式的值為F的真值指派為： ； ； 。五、證明題：1證明：假設(shè)R不是反對稱的，則 由R的傳遞性， 此與R反自反矛盾，R反對稱。2證明：（1）設(shè)群的幺元為，則 有 ，即H非空。 （2），則 有 ，從而 故 是的子群。3解：設(shè)連通平面圖G有個(gè)面： 則有 ，又有題意， 又 ， ， 。從而 ， 。4解：設(shè)：喜歡美術(shù)，：喜歡體育，