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

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

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

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

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

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

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