1、-. z.離散數學試題與答案試卷一一、填空 20% 每題2分1設N：自然數集，E+正偶數則。2A，B，C表示三個集合，文圖中陰影局部的集合表達式為A B C。3設P，Q 的真值為0，R，S的真值為1，則的真值= 。4公式的主合取*式為。5假設解釋I的論域D僅包含一個元素，則在I下真值為。6設A=1，2，3，4，A上關系圖為則 R2 = 。8圖的補圖為。二、選擇 20% 每題 2分1、以下是真命題的有A； B；C； D。2、以下集合中相等的有 A4，3；B，3，4；C4，3，3；D 3，4。3、設A=1，2，3，則A上的二元關系有個。 A 23 ；B 32 ；C； D。4、設R，S是集合A上的關

2、系，則以下說法正確的選項是 A假設R，S 是自反的，則是自反的； B假設R，S 是反自反的，則是反自反的； C假設R，S 是對稱的，則是對稱的； D假設R，S 是傳遞的，則是傳遞的。5、設A=1，2，3，4，PAA的冪集上規定二元系如下則PA/ R=AA ；BP(A) ；C1，1，2，1，2，3，1，2，3，4；D，2，2，3，2，3，4，A7、以下函數是雙射的為Af : IE , f (*) = 2* ； Bf : NNN, f (n) = ；Cf : RI , f (*) = * ； Df :IN, f (*) = | * | 。注：I整數集，E偶數集， N自然數集，R實數集8、圖中從v1

3、到v3長度為3 的通路有條。A 0；B 1；C 2；D 3。9、以下圖中既不是Eular圖，也不是Hamilton圖的圖是10、在一棵樹中有7片樹葉，3個3度結點，其余都是4度結點則該樹有個4度結點。A1；B2；C3；D4 。五、計算 18%2、如以下圖所示的賦權圖表示*七個城市及預先算出它們之間的一些直接通信線路造價，試給出一個設計方案，使得各城市之間能夠通信而且總造價最小。分試卷二一、填空 20% 每題2分P：你努力，Q：你失敗。除非你努力，否則你將失敗的翻譯為；雖然你努力了，但還是失敗了的翻譯為。2、論域D=1，2，指定謂詞PP (1,1)P (1,2)P (2,1)P (2,2)TTF

4、F則公式真值為。設S=a1 ，a2 ，a8，Bi是S的子集，則由B31所表達的子集是。設A=2，3，4，5，6上的二元關系，則R= 列舉法。R的關系矩陣MR=。9、n個結點的無向完全圖Kn的邊數為，歐拉圖的充要條件是。10、公式的根樹表示為二、選擇 20% 每題2分1、在下述公式中是重言式為A；B；C； D。2、命題公式中極小項的個數為，成真賦值的個數為。A0； B1； C2； D3 。3、設，則有個元素。A3； B6； C7； D8 。設，定義上的等價關系則由 R產生的上一個劃分共有個分塊。A4； B5； C6； D9 。5、設，S上關系R的關系圖為則R具有性質。A自反性、對稱性、傳遞性；

5、B反自反性、反對稱性；C反自反性、反對稱性、傳遞性； D自反性。6、設為普通加法和乘法，則是域。A BC D= N 。7、下面偏序集能構成格。8、在如下的有向圖中，從V1到V4長度為3 的道路有條。A1； B2； C3； D4 。9、在如下各圖中歐拉圖。四、計算 14%權數1，4，9，16，25，36，49，64，81，100構造一棵最優二叉樹。7分試卷三試題與答案填空 20% 每空 2分設 f，g是自然數集N上的函數，則。設A=a，b，c，A上二元關系R= , , , 則sR= 。A=1，2，3，4，5，6，A上二元關系，則用列舉法 T= ；T的關系圖為；T具有性質。集合的冪集= 。P，Q真

6、值為0 ；R，S真值為1。則的真值為。的主合取*式為。設 P*：*是素數， E(*)：* 是偶數，O(*)：*是奇數 N (*,y)：*可以整數y。則謂詞的自然語言是。謂詞的前束*式為。選擇 20% 每題 2分的主析取*式中含極小項的個數為。A 、2； B、 3； C、5； D、0； E、 8 。給定推理PUSPESTIUG推理過程中錯在。A、-; B、-; C、-; D、-; E、-設S1=1，2，8，9，S2=2，4，6，8，S3=1，3，5，7，9，S4=3，4，5，S5=3，5，在條件下*與集合相等。*=S2或S5； B、*=S4或S5；C、*=S1，S2或S4； D、*與S1，S5中

7、任何集合都不等。設R和S是P上的關系，P是所有人的集合，則表示關系。A、；B、；C、； D、。下面函數是單射而非滿射。A、；B、；C、；D、。其中R為實數集，Z為整數集，R+，Z+分別表示正實數與正整數集。設S=1，2，3，R為S上的關系，其關系圖為則R具有的性質。自反、對稱、傳遞； B、什么性質也沒有；C、反自反、反對稱、傳遞； D、自反、對稱、反對稱、傳遞。設，則有。A、1,2 ；B、1,2 ； C、1 ； D、2 。設A=1 ,2 ,3 ，則A上有個二元關系。A、23； B、32； C、； D、。10、全體小項合取式為。A、可滿足式； B、矛盾式； C、永真式； D、A，B，C 都有可能

8、。用CP規則證明 16% 每題 8分1、2、四、14% 集合*=, , , ，R=,|*1+y2 = *2+y1 。證明R是*上的等價關系。10分求出*關于R的商集。4分五、10%設集合A= a ,b , c , d 上關系R= , , , 要求 1、寫出R的關系矩陣和關系圖。4分 2、用矩陣運算求出R的傳遞閉包。6分六、20%1、10分設f和g是函數，證明也是函數。2、10分設函數，證明有一左逆函數當且僅當f是入射函數。試卷四試題與答案1填空 10% 每題 2分假設P，Q，為二命題，真值為0 當且僅當。命題對于任意給定的正實數，都存在比它大的實數令F(*)：*為實數，則命題的邏輯謂詞公式為。

9、謂詞合式公式的前束*式為。將量詞轄域中出現的和指導變元交換為另一變元符號，公式其余的局部不變，這種方法稱為換名規則。設*是謂詞合式公式A的一個客體變元，A的論域為D，A(*)關于y是自由的，則被稱為存在量詞消去規則，記為ES。2選擇 25% 每題 2.5分以下語句是命題的有。明年中秋節的晚上是晴天； B、；C、當且僅當*和y都大于0； D、我正在說謊。以下各命題中真值為真的命題有。2+2=4當且僅當3是奇數；B、2+2=4當且僅當3不是奇數；C、2+24當且僅當3是奇數； D、2+24當且僅當3不是奇數；以下符號串是合式公式的有A、；B、；C、；D、。以下等價式成立的有。A、；B、；C、； D

10、、。假設和B為wff，且則。A、稱為B的前件； B、稱B為的有效結論C、當且僅當；D、當且僅當。A，B為二合式公式，且，則。A、為重言式； B、；C、； D、； E、為重言式。人總是要死的謂詞公式表示為。論域為全總個體域M(*)：*是人；Mortal(*)：*是要死的。A、； B、C、；D、公式的解釋I為：個體域D=2，P(*)：*3, Q(*)：*=4則A的真值為。A、1； B、0； C、可滿足式； D、無法判定。以下等價關系正確的選項是。A、；B、；C、；D、。以下推理步驟錯在。PUSPESTIEGA、；B、；C、；D、3邏輯判斷30% 用等值演算法和真值表法判斷公式的類型。10分以下問題

11、，假設成立請證明，假設不成立請舉出反例：10分，問成立嗎？，問成立嗎？如果廠方拒絕增加工資，則罷工就不會停頓，除非罷工超過一年并且工廠撤換了廠長。問：假設廠方拒絕增加工資，面罷工剛開場，罷工是否能夠停頓。10分四、計算10%設命題A1，A2的真值為1，A3，A4真值為0，求命題的真值。5分利用主析取*式，求公式的類型。5分五、謂詞邏輯推理 15%符號化語句：有些人喜歡所有的花，但是人們不喜歡雜草，則花不是雜草。并推證其結論。六、證明：10%設論域D=a , b , c，求證：。試卷五試題與答案一、填空15%每空3分1、設G為9階無向圖，每個結點度數不是5就是6，則G中至少有個5度結點。2、n階

12、完全圖，Kn的點數* (Kn) = 。3、有向圖中從v1到v2長度為2的通路有條。4、設R，+，是代數系統，如果R，+是交換群R，是半群則稱R，+，為環。5、設是代數系統，則滿足冪等律，即對有。二、選擇15%每題3分下面四組數能構成無向簡單圖的度數列的有。A、2，2，2，2，2； B、1，1，2，2，3；C、1，1，2，2，2； D、0，1，3，3，3。以下圖中是哈密頓圖的為。如果一個有向圖D是強連通圖，則D是歐拉圖，這個命題的真值為A、真； B、假。以下偏序集能構成格。設，*為普通乘法，則S，*是。A、代數系統； B、半群； C、群； D、都不是。三、證明 48%1、10%在至少有2個人的人

13、群中，至少有2 個人，他們有一樣的朋友數。2、8%假設圖G中恰有兩個奇數度頂點，則這兩個頂點是連通的。3、8%證明在6個結點12條邊的連通平面簡單圖中，每個面的面數都是3。4、10%證明循環群的同態像必是循環群。5、12%設是布爾代數，定義運算*為，求證B，*是阿貝爾群。四、計算22%1、在二叉樹中求帶權為2，3，5，7，8的最優二叉樹T。5分求T對應的二元前綴碼。5分以下圖所示帶權圖中最優投遞路線并求出投遞路線長度郵局在D點。試卷六試題與答案一 填空 15% 每題3分n階完全圖結點v的度數d(v) = 。設n階圖G中有m條邊，每個結點的度數不是k的是k+1，假設G中有Nk個k度頂點，Nk+1

14、個k+1度頂點，則N k = 。算式的二叉樹表示為。如圖給出格L，則e的補元是。一組學生，用二二扳腕子比賽法來測定臂力的大小，則幺元是。二、選擇 15% 每題 3分1、設S=0,1,2,3,為小于等于關系，則S，是。A、群；B、環；C、域；D、格。2、設a , b , c，*為代數系統，*運算如下：*abcaabcbbaccccc則零元為。A、a； B、b； C、c； D、沒有。3、如右圖相對于完全圖K5的補圖為。4、一棵無向樹T有7片樹葉，3個3度頂點，其余頂點均為4度。則T有4度結點。A、1； B、2； C、3； D、4。5、設A，+，是代數系統，其中+，為普通加法和乘法，則A=時，A，+

15、，是整環。A、； B、；C、； D、。三、證明 50%1、設G是n,m簡單二部圖，則。10分2、設G為具有n個結點的簡單圖，且，則G是連通圖。10分3、記開為1，關為0，反映電路規律的代數系統0，1，+，的加法運算和乘法運算。如下：+0101001000110101證明它是一個環，并且是一個域。14分是一代數格，為自然偏序，則L，是偏序格。16分四、10%設是布爾代數上的一個布爾表達式，試寫出的析取*式和合取*式10分五、10%如以下圖所示的賦權圖表示*七個城市及預先算出它們之間的一些直接通信成路造價單位：萬元，試給出一個設計方案，使得各城市之間既能夠通信又使總造價最小。試卷七試題與答案填空

16、15% 每題 3分任何(n,m) 圖G = (V,E) , 邊與頂點數的關系是 。當n為 時,非平凡無向完全圖Kn是歐拉圖。一棵無向樹T有三個3頂點,一個2度頂點,其余的都是1度頂點,則T中有個1度頂點。n階完全圖Kn的點色數*(KN)= 。一組學生,用兩兩扳腕子比賽來測定臂力大小,則幺元是 。選擇 15% 每題 3分1、下面四組數能構成無向圖的度數列的有( )。 A、 2,3,4,5,6,7； B、 1,2,2,3,4； C、 2,1,1,1,2； D、 3,3,5,6,0。2、圖 的鄰接矩陣為( )。A、；B、；C、；D、。3、以下幾個圖是簡單圖的有( )。G1=(V1,E1), 其中 V

17、1=a,b,c,d,e,E1=ab,be,eb,ae,de；G2=(V2,E2)其中V2=V1,E2=,；G=(V3,E3), 其中V3=V1,E3=ab,be,ed,cc；G=(V4,E4),其中V4=V1,E4=a,a,a,b,b,c,e,c,e,d。4、以下圖中是歐拉圖的有( )。5、，其中，為集合對稱差運算，則方程的解為。A、； B、； C、； D、。證明 34% 證明：在至少有2 個人的人群中，至少有2 個人，他的有一樣的朋友數。8分假設圖G中恰有兩個奇數頂點，則這兩個頂點是連通的。8分證明：在6個結點12條邊的連通平面簡單圖中，每個面的面度都是3。8分證明循環群的同態像必是循環群。

18、10分中國郵遞員問題13%求帶權圖G中的最優投遞路線。郵局在v1點。根樹的應用 13%在通訊中，八進制數字出現的頻率如下：0：30%、1：20%、2：15% 、3：10%、4：10%、5：5%、6：5%、7：5%求傳輸它們最正確前綴碼寫出求解過程。10%設B4=e , a , b , ab ，運算*如下表，*證明是一個群稱作Klein四元群試卷八試題與答案填空 15% 每題 3分n階完全圖Kn的邊數為。右圖的鄰接矩陣A= 。圖的對偶圖為：完全二叉樹中，葉數為nt，則邊數m= 。設為代數系統，* 運算如下：*abcaabcbbaccccc則它的幺元為；零元為；a、b、c的逆元分別為。選擇 15%

19、 每題 3分圖相對于完全圖的補圖為。對圖G 則分別為。A、2、2、2； B、1、1、2； C、2、1、2； D、1、2、2 。一棵無向樹T有8個頂點，4度、3度、2度的分枝點各1個，其余頂點均為樹葉，則T中有片樹葉。A、3； B、4； C、5； D、6設是代數系統，其中+，為普通的加法和乘法，則A=時是整環。A、； B、；C、； D、。設A=1，2，10 ，則下面定義的運算*關于A封閉的有。*y=ma*(* ,y)； B、*y=質數p的個數使得；C、*y=gcd(* , y)； (gcd (* ,y)表示*和y的最大公約數)；D、*y=lcm(* ,y) lcm(* ,y) 表示*和y的最小公

20、倍數。證明 45% 1、設G是n,m簡單二部圖，則。8分2、設G為具有n個結點的簡單圖，且則G是連通圖。8分3、設G是階數不小于11的簡單圖，則G或中至少有一個是非平圖。14分4、記開為1，關為0，反映電路規律的代數系統0，1，+，的加法運算和乘法運算。如下：+0101001000110101證明它是一個環，并且是一個域。15分生成樹及應用 10%1、10分如以下圖所示的賦權圖表示*七個城市及預先測算出它們之間的一些直接通信線路造價，試給出一個設計方案，使得各城市之間既能夠通信而且總造價最小。2、10分構造H、A、P、N、E、W、R、對應的前綴碼，并畫出與該前綴碼對應的二叉樹，寫出英文短語HA

21、PPY NEW YEAR的編碼信息。5%對于實數集合R，在下表所列的二元遠算是否具有左邊一列中的性質，請在相應位上填寫Y或N。Ma*Min+可結合性可交換性存在幺元存在零元試卷九試題與答案填空 30% 每空 3分選擇適宜的論域和謂詞表達集合A=直角坐標系中，單位元不包括單位圓周的點集則A= 。集合A=,的冪集P(A) = 。設A=1，2，3，4，A上二元關系R=，畫出R的關系圖。設A=, , B=,則= 。= 。設|A|=3，則A上有個二元關系。A=1，2，3上關系R= 時，R既是對稱的又是反對稱的。偏序集的哈斯圖為，則= 。設|*|=n，|Y|=m則1從*到Y有個不同的函數。2當n , m滿

22、足時，存在雙射有個不同的雙射。是有理數的真值為。Q：我將去*，R：我有時間，公式的自然語言為。公式的主合取*式是。假設是集合A的一個分劃，則它應滿足。選擇 20% 每題 2分設全集為I，以下相等的集合是。A、； B、；C、； D、。設S=N，Q，R，以下命題正確的選項是。A、； B、；C、； D、。設C=a,b,a,b，則分別為。A、C和a,b；B、a,b與；C、a,b與a,b；D、C與C以下語句不是命題的有。*=13； B、離散數學是計算機系的一門必修課； C、雞有三只腳；D、太陽系以外的星球上有生物； E、你打算考碩士研究生嗎？的合取*式為。A、；B、；C、 D、。設|A|=n，則A上有二

23、元關系。A、2n ； B、n2 ； C、； D、nn； E、。設r為集合A上的相容關系，其簡化關系圖如圖，則 I r產生的最大相容類為；A、； B、； C、； D、II A的完全覆蓋為。A、； B、；C、； D、。集合A=1，2，3，4上的偏序關系圖為則它的哈斯圖為。以下關系中能構成函數的是。A、；B、；C、； D、。10、N是自然數集，定義即*除以3的余數，則f是。A、滿射不是單射；B、單射不是滿射；C、雙射；D、不是單射也不是滿射。簡答題 15% 1、(10分)設S=1 , 2 , 3 , 4, 6 , 8 , 12 , 24，為S上整除關系，問：1偏序集的Hass圖如何？2偏序集的極小元

24、、最小元、極大元、最大元是什么2、5分設解釋R如下：DR是實數集，DR中特定元素a=0，DR中特定函數，特定謂詞，問公式的涵義如何？真值如何？邏輯推理 10%或者邏輯難學，或者有少數學生不喜歡它；如果數學容易學，則邏輯并不難學。因此，如果許多學生喜歡邏輯，則數學并不難學。五、10%設*=1,2,3,4,5，*上的關系R= , , , , ，用Warshall方法，求R的傳遞閉包t (R)。六、證明 15%每一有限全序集必是良序集。7分設是復合函數，如果滿射，則也是滿射。8分試卷十試題與答案填空 10%每題 2分假設P，Q為二命題，真值為1，當且僅當。對公式中自由變元進展代入的公式為。的前束*式

25、為。設*是謂詞合式公式A的一個客體變元，A的論域為D，A*關于y的自由的，則被稱為全稱量詞消去規則，記為US。與非門的邏輯網絡為。選擇 30%每題 3分以下各符號串，不是合式公式的有。A、； B、；C、； D、。以下語句是命題的有。A、2是素數；B、*+5 6；C、地球外的星球上也有人；D、這朵花多好看呀！。以下公式是重言式的有。A、；B、；C、；D、以下問題成立的有。假設，則； B、假設，則；C、假設，則； D、假設，則。命題邏輯演繹的CP規則為。在推演過程中可隨便使用前提；B、在推演過程中可隨便使用前面演繹出的*些公式的邏輯結果；C、如果要演繹出的公式為形式，則將B作為前提，設法演繹出C；

26、D、設是含公式A的命題公式，則可用B替換中的A。命題有的人喜歡所有的花的邏輯符號化為。設D：全總個體域，F*：*是花，M(*) ：*是人，H(*,y)：*喜歡y A、；B、；C、；D、。公式換名。A、；B、；C、；D、。給定公式，當D=a,b時，解釋使該公式真值為0。A、P(a)=0、P(b)=0；B、P(a)=0、P(b)=1；C、P(a)=1、P(b)=0；D、P(a)=1、P(b)=1下面蘊涵關系成立的是。A、；B、；C、；D、。10、以下推理步驟錯在。PUSESUGEGA、；B、；C、；D、。邏輯判斷 28%1、8分以下命題相容嗎？2、10分用*式方法判斷公式是否等價。3、10分以下前

27、提下結論是否有效？今天或者天晴或者下雨。如果天晴，我去看電影；假設我去看電影，我就不看書。故我在看書時，說明今天下雨。計算 12%1、5分給定3個命題：P：比*人口多；Q：2大于1；R：15是素數。求復合命題：的真值。2、7分給定解釋I：D=2，3，L*,y為L( 2 , 2 ) = L ( 3 , 3 ) = 1 , L ( 2 , 3 ) = L (3 , 2 )=0 ,求謂詞合式公式的真值。邏輯推理20%1、10分所有有理數是實數，*些有理數是整數，因此*些實數是整數。2、10分符號化語句：有些病人相信所有的醫生，但是病人都不相信騙子，所以醫生都不是騙子。并推證其結論。試卷十一試題與答案

28、填空 20% 每題 2分1、 稱為命題。2、命題PQ的真值為0，當且僅當 。3、一個命題含有4個原子命題，則對其所有可能賦值有 種。4、所有小項的析取式為 。5、令P*：*是質數，E*：*是偶數，Q*：*是奇數，D*，y：*除盡y. 則的漢語翻譯為 。6、設S=a，b, c 則S6的集合表示為 。7、PP()= 。8、= 。9、設R為集合A上的關系，則tR= 。10、假設R 是集合A上的偏序關系，則R滿足 。選擇 20% 每題 2分以下命題正確的有。假設是滿射，則是滿射； B、假設是滿射，則都是滿射；C、假設是單射，則都是單射；D、假設單射，則是單射。設f，g是函數，當時，f=g 。A、； B

29、、；C、；D、。以下關系，能構成函數。A、；B、；C、； D、。以下函數滿射；單射；雙射；一般函數。A、； B、除以3的余數；C、；D、。集合A=1，2，3，4上的偏序關系為，則它的Hass圖為。設集合A=1，2，3，4，5上偏序關系的Hass圖為則子集B=2，3，4的最大元；最小元；極大元；極小元；上界；上確界；下界；下確界。無，4，2、3，4，1，1，4，4； B、無，4、5，2、3，4、5，1，1，4，4；C、無，4，2、3，4、5，1，1，4，4； D、無，4，2、3，4，1，1，4，無。設R，S是集合A上的關系，則以下斷言是正確的。自反的，則是自反的；B、假設對稱的，則是對稱的；C、

30、假設傳遞的，則是傳遞的；D、假設反對稱的，則是反對稱的設*為集合，|*|=n，在*上有種不同的關系。A、n2； B、2n； C、； D、。以下推導錯在。PUSESUGA、； B、； C、； D、無。10、沒有不犯錯誤的人的邏輯符號化為。設H*：*是人， P*：*犯錯誤。A、； B、；C、； D、。命題演繹28% 1、10分用反證法證明。2、8分用CP規則證明。3、10分演繹推理：所有的有理數都是實數，所有的無理數也是實數，虛數不是實數。因此，虛數既不是有理數，也不是無理數。8% 將化為與其等價的前束*式。五、8%A=a,b,c,d，R=,為A上的關系，利用矩陣乘法求R的傳遞閉包，并畫出tR的關

31、系圖。六、證明16%8分設A=1，2，3，4，在PA上規定二元關系如下： PA證明R是PA上的等價關系并寫出商集PA/R。8分設f是A到A的滿射，且，證明f=IA。試卷十二試題與答案填空 20% 每空 2分設集合A=1，2，3，4，5，6，7，8，9，10，定義A上的二元關系為* y = *|y , 則= 。設，定義A上的二元運算為普通乘法、除法和加法，則代數系統中運算*關于運算具有封閉性。設集合S=，S上的運算*定義為*則代數系統中幺元是，左逆元是，無左逆元的元素是。在群坯、半群、獨異點、群中滿足消去律。設是由元素生成的循環群，且|G|=n，則G = 。拉格朗日定理說明假設是群的子群，則可建

32、立G中的等價關系R= 。假設|G|=n, |H|=m 則m和n關系為。設f是由群到群的同態映射，是中的幺元，則f的同態核Ker(f )= 。選擇 20% 每題 2分1、設f是由群到群的同態映射，則ker (f)是。A、的子群； B、G的子群； C、包含； D、包含G。2、設 是環，ab的關于+的逆元是。A、(-a)(-b)； B、(-a)b； C、a(-b)； D、ab 。3、設 是一代數系統且是Abel群，如果還滿足是域。A、是獨異點且對+可分配；B、是獨異點，無零因子且對+可分配；C、是Abel群且無零因子；D、是Abel且對+可分配。4、設是一代數系統，+、為普通加法和乘法運算，當A為時

33、，是域。A、；B、；C、； D、。5、設是一個格，由格誘導的代數系統為，則成立。A、；B、；C、；D、。6、設是偏序集，定義為：，則當A=時，是格。A、1,2,3,4,6,12； B、1,2,3,4,6,8,12,14； C、1,2,3,，12； D、1,2,3,4。7、設是由格誘導的代數系統，假設對，當時，有是模格。A、； B、；C、； D、。8、在中，補元是唯一的。A、有界格； B、有補格； C、分配格； D、有補分配格。9、在布爾代數中，當且僅當。A、； B、； C、； D、。10、設是布爾代數，f是從An到A的函數，則。f是布爾代數； B、f能表示成析取*式，也能表示成合取*式；C、假

34、設A=0，1，則f一定能表示成析取*式，也能表示成合取*式；D、假設f是布爾函數，它一定能表示成析合取*式。三、8%設A=1，2，A上所有函數的集合記為AA, 是函數的復合運算，試給出AA上運算的運算表，并指出AA中是否有幺元，哪些元素有逆元。四、證明42%設是一個代數系統，*是R上二元運算，則0是幺元且是獨異點。8分設是n階循環群，G=(a)，設b=ak，則元素b的階為，這里d=GCD ( n , k )。10分證明如果f是由到的同態映射，g是由到的同態映射，則是由到的同態映射。6分設是一個含幺環，且任意都有aa=a，假設|A|3則不可能是整環。8分K= 1, 2 , 5 , 10 , 11

35、 , 22 , 55 ,110 是110的所有整因子的集合，證明：具有全上界110和全下界1的代數系統是一個布爾代數。10分五、布爾表達式 10%設是布爾代數上的一個布爾表達式，試寫出其析取*式和合取*式。10分試卷十三試題與答案填空 10% 每題 2分1、，*表示求兩數的最小公倍數的運算Z表示整數集合，對于*運算的幺元是，零元是。2、代數系統中，|A|1，如果分別為的幺元和零元，則的關系為。3、設是一個群，是阿貝爾群的充要條件是。4、圖的完全關聯矩陣為。5、一個圖是平面圖的充要條件是。選擇 10% 每題 2分下面各集合都是N的子集，集合在普通加法運算下是封閉的。A、* | * 的冪可以被16

36、整除； B、* | * 與5互質；C、* | *是30的因子； D、* | *是30的倍數。設，其中表示模3加法，*表示模2乘法，則積代數的幺元是。A、； B、； C、； D、 。設集合S=1,2,3,6，為整除關系，則代數系統是。A、域； B、格，但不是布爾代數； C、布爾代數； D、不是代數系統。設n階圖G有m條邊，每個結點度數不是k就是k+1，假設G中有Nk個k度結點，則Nk=。A、nk； B、n(k+1)； C、n(k+1)-m； D、n(k+1)-2m 。一棵樹有7片樹葉，3個3度結點，其余全是4度結點，則該樹有個4度結點。A、1； B、2； C、3； D、4 。三、判斷10% 每題

37、 2分1、設S=1,2，則S在普通加法和乘法運算下都不封閉。2、在布爾格中，對A中任意原子a，和另一非零元b，在或中有且僅有一個成立。3、設，+,為普通加法和乘法，則是域。4、一條回路和任何一棵生成樹至少有一條公共邊。5、沒T是一棵m叉樹，它有t片樹葉，i個分枝點，則(m-1)i = t-1。四、證明 38%1、8分對代數系統，*是A上二元運算，e為A中幺元，如果*是可結合的且每個元素都有右逆元，則1中的每個元素在右逆元必定也是左逆元。2每個元素的逆元是唯一的。2、12分設是一個布爾代數，如果在A上定義二元運算，為，則是一阿貝爾群。3、10分證明任一環的同態象也是一環。4、8分假設是每一個面至

38、少由k(k3)條邊圍成的連通平面圖，則。五、應用 32%8分*年級共有9門選修課程，期末考試前必須提前將這9門課程考完，每人每天只在下午考一門課，假設以課程表示結點，有一人同時選兩門課程，則這兩點間有邊其圖如右，問至少需幾天？用washall方法求圖的可達矩陣，并判斷圖的連通性。8分設有a、b、c、d、e、f、g七個人，他們分別會講的語言如下：a：英，b：漢、英，c：英、西班牙、俄，d：日、漢，e：德、西班牙，f：法、日、俄，g：法、德，能否將這七個人的座位安排在圓桌旁，使得每個人均能與他旁邊的人交談？8分用 Huffman算法求出帶權為2，3，5，7，8，9的最優二叉樹T，并求WT。假設傳遞

39、a ，b， c， d ，e， f 的頻率分別為2%， 3% ，5 %， 7% ，8% ，9%求傳輸它的最正確前綴碼。8分試卷十四試題與答案填空 10% 每題 2分設是由有限布爾格誘導的代數系統，S是布爾格，中所有原子的集合，則。集合S=，上的二元運算*為*則，代數系統中的幺元是 , 的逆元是。設I是整數集合，Z3是由模3的同余類組成的同余類集，在Z3上定義+3如下：，則+3的運算表為；是否構成群。設G是n階完全圖，則G的邊數m= 。如果有一臺計算機，它有一條加法指令，可計算四數的和?，F有28個數需要計算和，它至少要執行次這個加法指令。選擇 20% 每題 2分在有理數集Q上定義的二元運算*，有，

40、則Q中滿足。所有元素都有逆元； B、只有唯一逆元；C、時有逆元； D、所有元素都無逆元。設S=0，1，*為普通乘法，則是。半群，但不是獨異點； B、只是獨異點，但不是群；C、群； D、環，但不是群。3、圖給出一個格L，則L是。A、分配格； B、有補格； C、布爾格； D、 A,B,C都不對。有向圖D= ，則長度為2的通路有條。A、0； B、1； C、2； D、3 。在Peterson圖中，至少填加條邊才能構成Euler圖。A、1； B、2； C、4； D、5 。判斷 10% 每題 2分在代數系統中如果元素的左逆元存在，則它一定唯一且。設是群的子群，則中幺元e是中幺元。設， +,為普通加法和乘法

41、，則代數系統是域。設G=是平面圖，|V|=v, |E|=e，r為其面數，則v-e + r=2。如果一個有向圖D是歐拉圖，則D是強連通圖。四、證明 46%設，是半群，e是左幺元且，使得，則是群。10分循環群的任何非平凡子群也是循環群。10分設aH和bH是子群H在群G中的兩個左陪集，證明：要末，要末。8分設，是一個含幺環，|A|3，且對任意，都有，則不可能是整環這時稱是布爾環。8分假設圖G不連通，則G的補圖是連通的。10分五、布爾表達式 8%設是布爾代數上的一個布爾表達式，試寫出其的析取*式和合取*式。六、圖的應用 16%構造一個結點v與邊數e奇偶性相反的歐拉圖。6分假設英文字母，a，e，h，n，

42、p，r，w，y出現的頻率分別為12%，8%，15%，7%，6%，10%，5%，10%，求傳輸它們的最正確前綴碼，并給出happy new year的編碼信息。10分試卷十五試題與答案填空 20% 每空 2分如果有限集合A有n個元素，則|2A|= 。*集合有101個元素，則有個子集的元素為奇數。設S=a1，a2,，a8，Bi是S的子集，由B17表達的子集為，子集a2,a6,a7規定為。由A1，A2,，An，生成的最小集的形式為，它們的并為集，它們的交為集。*人有三個兒子，組成集合A=S1,S2,S3，在A上的兄弟關系具有性質。6、每一個良序集必為全序集，而全序集必為良序集。7、假設是函數，則當f

43、是的，是f的逆函數。選擇 15% 每題 3分集合的冪集為。A、；B、；C、；D、以下結果正確的選項是。A、；B、；C、；D、；E、；F、AA=A 。集合的最小集*式為由A、B、C生成。A、； B、；C、； D、。在下有。A、；B、；C、；D、以下二元關系中是函數的有。A、；B、；C、。三、 15% 用Warshall算法，對集合A=1，2，3，4，5上二元關系R=,求tR。四、15%集合，C*上定義關系，則R是C*上的一個等價關系，并給出R等價類的幾何說明。五、計算 15%設A=1，2，3，4，S=1，2，3，4，為A的一個分劃，求由S導出的等價關系。4分設為整數集，關系為Z上等價關系，求R的

44、模K等價關系的商集Z/R，并指出R有秩。5分設A=1，2，3，4，5，A上的偏序關系為求A的子集3，4，5和1，2，3，的上界，下界，上確界和下確界。6分六、證明 20%假定，且是一個滿射，g是個入射，則f是滿射。10分設f，g是A到B的函數，證明。10分試卷十六試題與答案判斷正誤 20% 每題 2分1、設A，B， C是任意三個集合。 1假設AB且BC，則AC。 2假設AB且BC，則AC。 3假設AB且BC，則AC。 4A。 5(AB)C=(AC) (BC)。 2、可能有*種關系，既是對稱的，又是反對稱的。 、假設平面圖共有v個結點，e條邊和r個面，則v-e+r=2。 、任何有向圖中各結點入度

45、之和等于邊數。 、代數系統中一個元素假設有左逆元，則該元素一定也有右逆元。 、任何一個循環群必定是阿貝爾群。 8% 將謂詞公式化為前束析取*式與前束合取*式。8%設集合a,b,c,d,e上的關系,寫出它的關系矩陣和關系圖，并用矩陣運算方法求出的傳遞閉包。四、10%設是一個群，證明：假設對任意的，都有，, 則是一個阿貝爾群。五、8% 根據庫拉托夫斯基定理，證明以下圖為非平面圖，要求用兩種證法。法1是找出與K3，3在2度結點內同構的子圖。法2是找出與K5在2度結點內同構的子圖。六、10%證明：每個結點的度數至少為2的圖必包含一個回路。七、12%用規則證明：、八、12% 用推理規則證明下式：前提:

46、結論：九、12%假設集合0，2，2，4，證明R是*上的等價關系。求出*關于R的商集。試卷十七試題與答案判斷正誤 20% 每題 2分1、設A.B. C是任意三個集合。 1假設AB且BC，則AC。 2假設AB且BC，則AC。 3假設AB且BC，則AC。 4A。 5(AB)C=(AC)-(BC)。 2、可能有*種關系，既不是自反的，也不是反自反的。 、假設兩圖結點數一樣，邊數相等，度數一樣的結點數目相等，則兩圖是同構的。 、一個圖是平面圖，當且僅當它包含與3，3或5在度結點內同構的子圖。 、代數系統中一個元素的左逆元并一定等于該元素的右逆元。 、群是每個元素都有逆元的半群。 8% 將謂詞公式化為前束

47、析取*式與前束合取*式。8%設集合a,b,c,d上的關系,寫出它的關系矩陣和關系圖，并用矩陣運算方法求出的傳遞閉包。四、9%、畫一個有一條歐拉回路和一條漢密爾頓回路的圖。、畫一個有一條歐拉回路，但沒有一條漢密爾頓回路的圖。、畫一個有一條歐拉回路，但有一條漢密爾頓回路的圖。五、10% 證明：假設圖是不連通的，則的補圖是連通的。六、10%證明：循環群的任何子群必定也是循環群。七、12%用規則證明：。八、10% 用推理規則證明下式：前提: 結論：S九、13%假設集合，1、證明R是*上的等價關系。2、求出*關于R的商集。試卷十八試題與答案選擇：總分值20分，每題2分 1以下語句中不是命題的有 9+51

48、2 ； *+3=5；我用的計算機CPU主頻是1G嗎？；我要努力學習。 2命題我不能一邊聽課，一邊看小說的符號化為；。 3以下表達式正確的有；。 4n個命題變元可產生個互不等價的小項。 n ； n2； 2n ； 2n。 5假設公式的主析取*式為則它的主合取*式為；。 6命題盡管有人聰明，但未必一切人都聰明的符號化P(*)：*是聰明的，M(*)：*是人7設A= ，B=(A) 以下表達式成立。；。8A是素數集合，B是奇數集合，則A-B=素數集合；奇數集合； 2。 9集合A=2，3，6，12，24，36上偏序關系R的Hass圖為則集合B=2，3，6，12的上確界。 B=2，3，6，12的下界。 B=6

49、，12，24，36的下確界。B=6，12，24，36的上界。 2； 3； 6； 12；無。 10假設函數g和f的復合函數gf 是雙射，則一定是正確的。 g是入射； f是入射； g是滿射； f是滿射。填空：總分值20，每題2分設P：它占據空間，Q：它有質量，R：它不斷運動，S：它叫做物質。命題占據空間的，有質量的而且不斷運動的叫做物質的符號化為。設A，B是兩命題公式，當且僅當。3要證為前提的有效結論，運用CP規則是。4對謂詞公式的自由變元代入得。5設S=a1,a2,a8,Bi是S的子集，則B31=。6設I為整數集合，R=*y(mod3) 則 1= 。7偏序集a,b，的Hass圖為。8對集合*和Y

50、，設|*|=m ，|Y|=n ，則從*到Y的函數有 個。9設R為實數集，S=*|0*1，f：RS，則f(*)=為雙射。10設KN= 0，K(0,1)= ，則KN(0,1)=。證明：48分不構造真值表證明蘊涵式7分用邏輯推演下式，7分用CP規則證明7分符號化并證明其結論：所有有理數是實數，*些有理數是整數，因此*些實數是整數設R(*)：*是實數，Q(*)：*是有理數，I(*)：*是整數7分設R是集合*上的一個自反關系，求證：R是對稱的和傳遞的當且僅當a,b和a,c在R中，則有b,c在R中 (8分)。設f和g是函數，則fg也是函數。6分證明 0，10，16分四、6分集合S=1，2，3，4，5，找出

51、S上的等價關系，此關系能產生劃分1，2，3，4，5，并畫出關系圖。五、6分求的主合取*式。試卷十九試題與答案一、填空20%每空2分：1假設對命題P賦值1，Q賦值0，則命題的真值為。2命題如果你不看電影，則我也不看電影P：你看電影，Q：我看電影的符號化為。3公式的對偶公式為。4圖的對偶圖為。5假設關系R是等價關系，則R滿足性質。6關系R的傳遞閉包t (R) = 。7代數系統是群，則它滿足。8設是兩代數系統，f是從的同態映射，則f具有性質。9假設連通平面圖共有r個面，其中，則它滿足的Euler公式為。10樹T的邊數e與點數v有關系。二、選擇10%每題2分：1如果解釋I使公式A為真，且使公式也為真，

52、則解釋I使公式B為。A、真； B、假； C、可滿足； D、與解釋I無關。2設，則PAA = 。 A、A ； B、PA； C、；D、。3設集合A，B是有窮集合，且，則從A到B有個不同的雙射函數。 A、； B、； C、； D、。4設K = e , a , b , c，是Klein四元群，則元素a的逆元為。 A、e ； B、a ； C、b ； D、c。5一個割邊集與任何生成樹之間。A、沒有關系； B、割邊集誘導子圖是生成樹； C、有一條公共邊； D、至少有一條公共邊。三、邏輯推理12%：符號化命題每個學術會的成員都是工人并且是專家，有些成員是青年人，所以有的成員是青年專家；并用演繹方法證明上面推理。

53、F(*)：*是學術會成員；H(*)：*是工人；G(*)：*是專家；R(*)：*是青年人四、8%：求集合的并與交。五、12%：在實數平面上，畫出關系，并判定關系的特殊性質。六、8%：問代數系統是否是布爾代數，為什么？其中為能整除24的所有正整數，LCM為最小公倍數，GCD為最大公約數，七、10%：求圖中的一棵最小生成樹。八、10%：求圖的鄰接矩陣和可達矩陣。九、10%：證明：如果G是無向簡單圖且，則G包含一條長度不小于的根本回路。試卷二十試題與答案一、填空20%每空2分1n 個命題變元有個互不等價的極小項。2按De-Morgan定理，= 。3公式的主析取*式為 。4設P(*)：*是大象，Q(*)

54、：*是老鼠，R(*,y)：*比y重，則命題大象比老鼠重的符號化為。5設，*上的關系R的關系矩陣是，則。6在具有n個結點的有向圖中，任何根本通路的長度都不超過。7任何圖的點連通度，邊連通度，最小點度的關系為。8結點數n的簡單連通平面圖的邊數為m，則m與n的關系為。9群G的非空子集H是G的子群當且僅當假設* , yH 則。10代數系統是環，假設對運算還滿足則是整環。二、選擇10%每題2分1集合對運算封閉。A、加法； B、減法； C、乘法； D、。2設I為整數集合，m是任意正整數，是由模m的同余類組成的同余類集合，在上定義運算，則代數系統最確切的性質是。A、封閉的代數系統； B、半群； C、獨異點；

55、 D、群。3設是偏序格，其中N是自然數集合，是普通的數間小于等于關系，則有。A、a ； B、b ； C、ma*(a，b) ； D、min(a，b)。4連通非平凡的無向圖G有一條歐拉回路當且僅當圖G ( )。A、只有一個奇度結點； B、只有兩個奇度結點；C、只有三個奇度結點； D、沒有奇度結點。5設無向圖是連通的且假設則G是樹。 A、M=N+1 ； B、n=m+1 ； C、； D、。三、12%邏輯推理：符號化命題有些病人相信醫生，但是沒有病人相信法輪功，因此醫生都不信法輪功。用演繹法證明其結論。P(*)：*是病人，D(*)：*是醫生，Q(*)：*是法輪功練習者，L(* , y)：*相信y四、序關

56、系8%：設，偏序集的Hass圖為求 A中最小元與最大元；的上界和上確界，下界和下確界。五、函數8%設是映射且使得是滿射，假設g是入射，證明f是滿射。六、圖8%設G是連通簡單平面圖，結點數為n，邊數為m，面數為r，則。七、樹的應用12%設7個符號在通訊中使用的頻率如下：a：35% ，b：20% ，c：15% ，d：10% ， e：10% ，f：5% ，g ：5%編一個相應的二元前綴碼，使通訊中出現的符號盡可能地減少，并畫出對應的二叉樹及求二叉樹的過程。八、道路的根本性質10%設u ，v是樹T的兩個不同的結點，從u至v的根本通路結點不同的道路是T中最長的根本道路，證明：d(u)=d(v)=1。九、

57、子群12%假設H是G的子群，則。試卷二十一試題與答案一、問答10%定義在集合上的運算*如下表：*abcdaabcdbbadcccdbaddcab試問：1是代數系統否？2是子群否？3是群否？4有單位元否？5滿足交換律否？二、填空10%下表中的運算均定義在實數集上，請在相應的空格中打或填上具體實數不滿足或無該項者不填+-結合律交換律幺元含左、右幺元零元含左、右零元 v1 v2 v3 v4三、有向圖的矩陣表示應用15%*有向圖的鄰接矩陣如下：試求：到的長度為4的有向路徑的條數。四、圖的同構15%下面兩圖是否同構，假設是給出點集間的同構映射。五、樹的性質15%*樹有2個2度結點、3個3度結點、4個4度

58、結點，問有幾個葉子點無其它度數點。六、最小生成樹15%使用普里姆算法求以下圖的最小生成樹七、自同構映射10%令，定義映射g：為，試證：g是到的自同構映射。八、群與子群10%設是階為6的群，證明它至多有一個階為3的子群。試卷二十二試題與答案一、單項選擇題：每題1分，本大題共15分1設A=1，2，3，4，5，下面集合等于A 。A、1，2，3，4，5，6； B、；C、； D、。2設A=1，2，3，4，5，6，7，8，以下各式中是錯的。A、； B、6，7，8A；C、4，5A； D、1，2，3A 。3六階群的子群的階數可以是。A、1，2，5； B、2，4； C、3，6，7； D、2，3 。4設，以下各式

59、中是正確的。domSB ； B、domSA； C、ranSA； D、domS ranS = S。5設集合，則空關系不具備的性質是。A、自反性； B、反自反性； C、對稱性； D、傳遞性。6以下函數中，是入射函數。A、世界上每個人與其年齡的序偶集； B、世界上每個人與其性別的序偶集；一個作者的專著與其作者的序偶集； D、每個國家與其國旗的序偶集。7是群，則對*。A、滿足結合律、交換律； B、有單位元，可結合；C、有單位元、可交換； D、每元有逆元，有零元。8下面哈斯圖所描述的偏序關系構成分配格。9以下中的運算符都是可交換的。A、； B、； C、； D、。10設G是n個結點、m條邊和r個面的連通平

60、面圖，則m等于。A、n+r-2 ； B、n-r+2 ； C、n-r-2 ； D、n+r+2 。11n個結點的無向完全圖的邊數為。A、； B、； C、； D、。12以下圖中是根樹。A、；B、；C、；D、。13設P：22=5，Q：雪是黑的，R：24=8，S：太陽從東方升起，以下命題的真值為真。 A、； B、； C、； D、。14下面命題公式是重言式。 A、； B、；C、； D、。15設L(*)：*是演員，J(*)：*是教師，A(* , y)：*欽佩y，命題所有演員都欽佩*些教師符號化為。A、； B、；C、； D、。二、填空題：每空1分，本大題共15分1設，則，。2在一個有n個元素的集合上，可以有種