1、 一 判斷題(每小題1分，共 15分)1、 若圖G是自對偶的，則e=2v-2 (T)2、 “離散數學是很有趣的一門課程”，這句話是命題。（T）3、 函數的復合既能交換也能結合。（F）4、 如果ACBC，則AB（F）5、 設G=<V,E>為連通圖，且eE,則當e是G的割邊時，e才在G的每棵生成樹中。（T）6、 是合式公式。（T）7、 任何階數為4的群都是阿貝爾群。（T）8、 設G是簡單連通圖，且有v個結點，e條邊，若G是平面圖，則e3v-6。（T）9、 一個循環群的生成元是唯一的。（F）10、 有任意集合A、B，則f(AB)f(A)f(B)且f(A)f(B)f(AB)。（F）11、

2、（F）12、 對任意集合A，B，C，如果AB以及BC，則AC。（F）13、 整數集上的同余類是對整數集的一個劃分。（T）14、 有限半群中存在等冪元。（T）15、 設<A,*>是一個代數系統，且|A|>1，若該代數系統中存在幺元和零元，則幺元與零元相等。（F）二 、選擇題(每小題2分，共 22分)1、 一棵樹有兩個結點度數為2，一個結點度數為3，三個結點度數為4，則該樹有（D）片樹葉。A.6 B. 7 C. 8 D.92、圖1中v1到v4 長度為2的路有（A）條A. 1 B. 2 C. 3 D.4圖13、設A=1，2，3，4，B=a，b，c，d，f定義為：<1,a>

3、;,<2,b>,<3,c>,<4,d>，則f（D）。 A.不是函數 B.僅為入射函數 C.僅為滿射函數 D.是雙射函數 4、設F(x)：x是烏鴉；G(x,y)：x與y一般黑，則“天下烏鴉一般黑”可以符號化為：(A)A.B.C.D.5、給定下列謂詞公式，則是矛盾式的公式為（C）A.B. C.D.6、設有下列四個集合，偏序關系為整除，則是全序關系的為（D）A. 3,5,15 B.1,2,3,6,12C.3,4,12 D.3,9,27,547、設集合P=x1，x2，x3，x4，x5上的偏序關系如圖2所示，則下列說法中正確的是（A）A、P的最大元素為x1 ，無最小元

4、素，極小元素為x4，x5 ，極大元為素x1 B、P無最大元素，也無最小元素，極小元素為x4，x5 ，極大元為素x1 C、P的最大元素為x1 ，無最小元素，也無極小元素 ，極大元為素x1 D、P的最大元素為x1 ，最小元素為x4，x5，極小元素為x4，x5 ，極大元為素x1 圖28、集合A=a，b，c，A上的關系R=（a，b），（a，c），（b，a），（b，c），（c，a），（c，b），（c，c），則R具有關系的（B）性質。A、自反性 B、對稱性 C、反對稱性 D、傳遞性9、下面給出的一階邏輯等價式中，（B）是錯的。10、一個公式在等價意義下，下面哪個寫法是唯一的（C）。A析取范式 B合取范式

5、C主析取范式 D以上答案都不對11、已知圖G的相鄰矩陣為 A(G) 則G有（A）。 A. 5點，8邊 B. 6點，7邊 C. 5點，7邊 D. 6點，8邊A(G)=三 、填空題(每空2分，共 30分)1、 n為奇數時，無向完全圖Kn是歐拉圖。n為時，無向完全圖Kn僅存在歐拉通路而不存在歐拉回路。2、 如圖2，則k(G)= 2 (G)= 2 (G)= 2 圖23、 假設X和Y是有窮集合，則從X到Y存在入射的必要條件是|X| |Y| ，且f(x1)=f(x2)時必有x1=x2。4、 設P表示命題“8是偶數”，Q表示命題“糖果是甜的”，則命題PQ的反換式所表示的含義是如果8不是偶數，則糖果不是甜的。

6、5、 （PQ）R的對偶式為（PQ）R。6、設P(x)表示x是聰明的，M(x)表示x是人，則命題“盡管有人聰明，但未必一切人都聰明”可以符號化為：7、集合a,a的冪集為：，a，a，a，a8、令R=<1,2>,<3,4>,<2,2>和S=<4,2>,<2,5>,<3,1>,<1,3>，則<1,5>,<3,2>,<2,5>9、設A=a,b,c，R是A上的二元關系，且給定R=<a,b>,<b,c>,<c,a>，則r(R)=<a,b>,&

7、lt;b,c>,<c,a>,<a,a>,<b,b>,<c,c>10、設I是整數集合，R是同余模3的關系，則I/R=0R,1R,2R11、設謂詞的定義域為，將表達式中的量詞消除，寫成與之等價的命題公式是 12、設P(x)：x是素數；E(x)：x是偶數；O(x)：x是奇數；N(x，y)：x可以整除y。則可以譯成自然語言為：對于任意的x，如果x是素數，則存在一個y，y是奇數且y整除x。四 、證明題(第1，2題各5分，第3題8分，共 18分)1、如果馬會飛或羊吃草，則母雞就會是飛鳥；如果母雞是飛鳥，那么烤熟的鴨子還會跑；烤熟的鴨子不會跑。所以羊不吃

8、草。符號化該命題，并用推理理論證明之。 解：設P：馬會飛；Q：羊吃草；R：母雞是飛鳥；S：烤熟的鴨子還會跑。則上述語句可以符號化為：前提：結論：證明 采用直接證明方法（1）¬S P（2）RS P（3）¬R T（1），（2）I（4）PQR P（5）¬（PQ） T（3），（4）I（6）¬ P¬Q T（5）E（7）¬ Q T（6）I 2、證明：若X×Y=X×Z，且X不為空集，則Y=Z。證明：因為X×Y=X×Z，則X×YX×Z，且X×YX×Z又因為X不為空集，所以

9、有YZ，且YZ，所以Y=Z成立。3、設<A,*>是半群，e是左幺元且對每一個xA，存在xA，使得x*x=e。a) 證明：對于任意的a,b,cA，如果a*b=a*c，則b=c。b) 通過證明e是A中的幺元，證明<A,*>是群。證明：a)因為a*b=a*c，則a*a*b=a*a*c 即e*b=e*c 所以b=cb)對任一xA,則x*(x*e)=x*x*e=x*x，由a)可得x*e=x，又e是左幺元，所以e是幺元。即有e*x=x*e 則有x*x*x=x*x*x 所以有 x*x=x*x=e 即每個元素都有逆元所以<A,*>是群。五 、應用題(第1題5分，第2題10分

10、，共15 分)1、 雙射函數是密碼學中的重要工具，因為在密碼體制中大都會同時涉及加密和解密，假設f是由表1定義的，即f(A)=D,f(B)=E,F(C)=S,等，試找出給定密文“ARDJYLRXBMB”對應的明文。 表1ABCDEFGHIJKLMDESTINYABCFGH 續表1NOPQRSTUVWXYZJKLMOPQRUVWXZ 解：表1給出了一個雙射函數f，為了求出給定密文的明文，只需要求出f的逆函數f-1，按照f-1的對應關系依次還原出對應字母的原象就可以得到該密文對應的明文。由表1知f-1如下表所示：ABCDEFGHIJKLMHIJABKLMENOPQNOPQRSTUVWXYZFRST

11、UCDVWXYGZ則給定密文“ARDJYLRXBMB”對應的明文為“HUANGPUYIQI”2、 設按順序排列的13張紅心紙牌 A 2 3 4 5 6 7 8 9 10 J Q K經過1次洗牌后牌的順序變為：3 8 K A 4 10 Q J 5 7 6 2 9問，再經過兩次同樣方式的洗牌后牌的順序是怎么的？為什么？解：將洗牌的過程看成建立函數f的過程，即有f(A)=3,f(2)=8,f(3)=K,f(4)=A, f(5)=4,f(6)=10,f(7)=Q, f(8)=J,f(9)=5,f(10)=7,f(J)=6,f(Q)=2, f(K)=9.則求經過兩次同樣方式的洗牌后牌的順序即為求f f f的值。則經過兩次同樣方式的洗牌后牌的順序是9 6 5 K 3 Q 8 10 A 2 7 J 43、設有a,b,c,d,e,f,g七個人，他們分別會講如下各種語言：a會講英語；b會講漢語與英語；c會講英語、西班牙語和俄語；d會講日語和漢語；e會講德語和