離散數(shù)學(xué)期末測試卷I及答案

1、離散數(shù)學(xué)期末考試復(fù)習(xí)題及答案第一部分、考試形式和時間答題時限： 120 分鐘 考試形式：閉卷筆試第二部分、考試題型和得分構(gòu)成大題號總分一二三四10020101060一、選擇題：對每一道小題，從其4個備選答案中選擇最適合的一項(xiàng)，每小題2分，共10道小題，20分。二、填空題：每空1分，共5道小題，10個空白處待填，10分。三、判斷題：每一道小題均以陳述語句描述，對的打，錯的打。每小題1分，共10道小題，10分。四、綜合題：每小題10分，共6道小題，60分。第三部分、考試復(fù)習(xí)范圍一、選擇題1含n個元素的集合A的冪集的元素個數(shù)為多少？答案：2n個。2 數(shù)理邏輯的創(chuàng)始人是誰？答案：萊布里茨。3 設(shè)(R,

2、+,×)是環(huán)，它有哪些特性？答案：1.(R,+)是阿貝爾群。2.(R,)是半群。3.對+可分配。4 排中律滿足哪些性質(zhì)？答案：A 不成立。（不應(yīng)同時否認(rèn)一個命題（A）及其否定（非A）x（F（x）F（x）對任何個體x而言，x有性質(zhì)F或沒有性質(zhì)F。5 什么是真命題？命題“如果雪是黑的，則1+1=0”是真命題嗎？ 答案：真值為真的命題為真命題。命題“如果雪是黑的，則1+1=0”是真命題！解析：p:雪是黑的；q:1+1=0;如果雪是黑的，則1+1=0:pq。由于p為假，所以無論的真值如何，“pq”的真值都為真。6. 下列哪個等價公式有錯？A；B；C；答案：A 7. 設(shè)G為4階有向圖，度數(shù)列為

3、（3,4,2,3），若它的入度列為（1,2,2,1），則出度列為哪項(xiàng)？A （1,2,1,2）； B（2,2,0,2）； C（2,1,1,2） 答案：B解析：有向圖中：度數(shù)=出度數(shù)+入度數(shù)。8. 設(shè),則表示空元素屬于S怎樣寫？答案:ØS9. 什么是前束范式？下面哪個是前束范式？A ； B答案：前束范式：如果量詞均在全式的開頭，它們的作用域延伸到整個公式的末端，則該公式叫做前束范式。B。解析：如果量詞均在全式的開頭，它們的作用域延伸到整個公式的末端，則該公式叫做前束范式，顯然B選項(xiàng)滿足定義。9. 無向圖中有16條邊，且每個結(jié)點(diǎn)的度數(shù)均為2，則結(jié)點(diǎn)數(shù)是多少？答案：16解析：由于每個結(jié)點(diǎn)的度

4、數(shù)為2，所以可以排除G中存在孤立點(diǎn)（度數(shù)為0）和懸掛點(diǎn)（度數(shù)為1）。由此可知，G中的任何一個結(jié)點(diǎn)皆是使用一度與上一個結(jié)點(diǎn)相連再使用另一度與下一個結(jié)點(diǎn)相連，從而每條邊與兩個結(jié)點(diǎn)關(guān)聯(lián)（上一個結(jié)點(diǎn)與下一個結(jié)點(diǎn)），但是每個結(jié)點(diǎn)又與兩條邊相連，故結(jié)點(diǎn)數(shù)為：16×2÷2=16個。10. 含n個命題變元的命題公式的不同的真值指派有幾種？答案：2n種 11. 集合論的創(chuàng)始人是？答案：G.Cantor(康托爾)13以下推理錯誤的是？ A； B； C答案：B14設(shè)G為4階有向圖，度數(shù)列為（4,4,2,2），若它的入度列為（2,2,1,1），則出度列為哪項(xiàng)？C A（2,1,1,2）； B（1,2

5、,1,2）； C（2,2,1,1） 15圖論中的握手定理的內(nèi)容是什么？答案：握手定理：在任何（n,m）圖G=（V，M）中，其所有結(jié)點(diǎn)度數(shù)之和等于邊數(shù)m 的兩倍，即：deg(v)=2m。16下面哪一種圖不一定是樹？ A有個結(jié)點(diǎn)條邊； B無圈連通圖； C每對結(jié)點(diǎn)間有唯一的一條路的圖 D無圈但增加一條邊，就得到一個且僅有一個圈答案：A17對于任意素數(shù)p和正整數(shù)n，存在多少個元素的有限域？答案：Pn18 下面所示的偏序集中，哪個是格？答案：B【解析】要想對偏序格進(jìn)行正確地判斷，前提是一定要吃透概念和定義：設(shè)(L,)是偏序集，若L中的任意兩個元素組成的子集均存在上確界及下確界，則稱(L,)為偏序格。另外

6、，加設(shè)SL。上確界：子集S的最小上界：lub(S)或sup(S)下確界：子集S的最大下界：glb(S)或inf(S)注意：1.只有一條線上的兩個元素可以比較大小。未在一條線上的兩個元素沒有偏序關(guān)系（無法比較大?。?.若對于均有,則a為S的上界，反之，為下界。A選項(xiàng)中a,b的下界元素有c和0，但是由于c和0無偏序關(guān)系而無法比較大小，導(dǎo)致a,b沒有下確界。C選項(xiàng)a,b沒有上確界。D選項(xiàng)a,b沒有上、下確界,c,d沒有上、下確界。B選項(xiàng)中（a,c上確界:a,下確界:c;a,b上確界：1，下確界：c;d,e上確界：c,下確界：0；.）任意兩個元素組成的子集都存在上確界和下確界，故B選項(xiàng)是偏序格！19

7、設(shè)表示是學(xué)生。表示是老師，表示欽佩。則命題“所有學(xué)生都?xì)J佩某些老師”符號化為后的表達(dá)式是什么？答案：20 謂詞公式中量詞（）轄域是答案：R(x,y)21 圖論的創(chuàng)始人是誰？答案：瑞士數(shù)學(xué)家L.Euler(歐拉)22 兩個圖同構(gòu)是指其中一個圖近經(jīng)過哪些變換可以變?yōu)榱硪粋€圖？答案：1.挪動點(diǎn)的位置；2.伸縮邊的長短。23. 什么是孤立點(diǎn)和懸掛點(diǎn)？答案：孤立點(diǎn)：在任意圖G(V,E)中，度數(shù)為0的結(jié)點(diǎn)。懸掛點(diǎn)：在任意圖G(V,E)中，度數(shù)為1的結(jié)點(diǎn)。24.域和環(huán)相比增加了哪些要求？答案：域：設(shè)(F,+,)是環(huán)，若(F-0,)是阿貝爾群，則稱(F,+,)是域。25.阿貝爾群具有哪些特點(diǎn)？比普通群增加了什

8、么？答案：阿貝爾群：設(shè)(G,)是群，若其運(yùn)算是可交換的，則稱(G,)為阿貝爾群。二、填空題1鴿籠原理是指什么？ 答：n+1只或更多的鴿子飛進(jìn)n個籠子時，一定有一個籠子里面至少有2只鴿子。2 哪位挪威數(shù)學(xué)家和法國數(shù)學(xué)家先后為群的研究做出了杰出的貢獻(xiàn)？答案：挪威數(shù)學(xué)家Niels Henrik Abel （尼爾斯· 亨利克·阿貝爾）和法國數(shù)學(xué)家Évariste Galois（埃瓦里斯特伽羅瓦） 為群的研究做出了杰出的貢獻(xiàn)。3 單獨(dú)一個節(jié)點(diǎn)v構(gòu)成的序列v到v的長度為多少的路？叫做什么？答案：單獨(dú)一個節(jié)點(diǎn)v構(gòu)成的序列v到v的長度為0的路叫做平凡路4 命題公式(pq)r的析取

9、范式與合取范式各為什么？答案：析取范式： 合取范式：5 集合A, B的對稱差A(yù)ÅB可以表示為什么？答案：6 半群（S, *）滿足哪些特性?答案：S是非空集合，*是S上滿足結(jié)合律的二元封閉運(yùn)算。7 在謂詞邏輯中，命題“所有有理數(shù)是實(shí)數(shù)”符號化為什么？命題“有些實(shí)數(shù)是有理數(shù)”符號化為什么？答案：設(shè)Q(x):x是有理數(shù)，R(x):x是實(shí)數(shù)。則命題“所有有理數(shù)是實(shí)數(shù)”符號化為：命題“有些實(shí)數(shù)是有理數(shù)”符號化為：8 布爾代數(shù)的定義是怎樣的?答案：元素個數(shù)2的有補(bǔ)分配格稱作布爾代數(shù)。9 設(shè)R Í A ´ A, 則R在A是反自反的充要條件是什么？答案：IAR=10 什么情況下稱

10、 f 是 A到B的雙射？答案：f既是A到B的單射，也是A到B的滿射時稱f是A到B的雙射。11 補(bǔ)元的定義是怎樣的？答案：.則稱是A的補(bǔ)元。 12 什么是分配格？答案：若格的乘法運(yùn)算“”對格的加法運(yùn)算“+”相互可分配，則稱是分配格。13 設(shè)(R,+,×)是環(huán)，怎樣成為交換環(huán)、含幺環(huán)、無零因子環(huán)？答案：環(huán)的定義：(R,+,)是含有兩個二元運(yùn)算的代數(shù)結(jié)構(gòu)，若：(1) (R,+)是阿貝爾群。(2) (R,)是半群。(3) 對+可分配。則稱(R,+,)是環(huán)。另外：R中的乘法運(yùn)算可交換，則稱(R,+,)是交換環(huán)。R中的乘法運(yùn)算有幺元，則稱(R,+,)是含幺環(huán)。14 命題公式中的對偶式分別是怎樣定

11、義的？答案：將至多含有3個邏輯聯(lián)結(jié)詞（否定聯(lián)結(jié)詞，析取聯(lián)結(jié)詞，合取聯(lián)結(jié)詞）的命題公式A中的析取聯(lián)結(jié)詞換成合取聯(lián)結(jié)詞，將1換成0，將0換成1，合取聯(lián)結(jié)詞換成析取聯(lián)結(jié)詞后所得到的命題公式A*稱為命題公式A的對偶式。15 一個集合的上/下確界是怎樣定義的？答案：在偏序集(A,)，SA，S的最小上界稱為上確界sup(S)，S的最大下界稱為下確界inf(S).三、判斷題1 (A, f1, f2, fk)=(B, g1, g2, gk) 表示這兩個代數(shù)結(jié)構(gòu)是同構(gòu)的。答：錯。 (A, f1, f2, fk)(B, g1, g2, gk)才表示這兩個代數(shù)結(jié)構(gòu)是同構(gòu)的。2 關(guān)系圖GR中的每一對不同點(diǎn)之間的邊都是

12、成對出現(xiàn)的，則稱R是對稱的。答：正確。3 若(S, *)是有限半群，則一定存在幺元e，并構(gòu)成獨(dú)異點(diǎn)(S, *，e)。答：錯誤。代數(shù)結(jié)構(gòu)(S,*)中，若S為有限集合，*是S上滿足結(jié)合律的二元封閉運(yùn)算，則稱(S,*)為有限半群。例如：S=0,2,4,*8是模8乘法運(yùn)算。則(S,*8)是有限半群，但不存在幺元。4 有向圖G=(V, E)中的"u, vÎV, u和v相互可達(dá)，則稱G為強(qiáng)連通圖。答：正確。5 在關(guān)系圖GR中，對任意的x,y,zÎA,只要x到y(tǒng)有邊且y到z有邊，就一定有x到z有邊，則R是傳遞的。答：正確。6 設(shè)是一個群，則0。答：錯誤。設(shè)G是非0實(shí)數(shù)集，*是其

13、上的數(shù)的乘法運(yùn)算，顯然(G,*)是群。則任意屬于G的元素x，其逆元X-1 = ，從而(X-1)-1=X。7 設(shè)是一個偏序集，如果中任意兩個元素都有上確界和下確界，則稱 是一個格。答：正確。也稱(A,)為偏序格。8 命題公式的逆反式是。答：正確。左邊=右邊9 圖 是弱連通圖。答：正確。該圖為強(qiáng)連通圖且屬于弱連通圖。10 A上的關(guān)系R是等價的意味著R必須具有自反性、對稱性和傳遞性。答：正確。11 若關(guān)系R的MR中主對角線元素全為1，則R是反自反的。答：錯誤。若關(guān)系R的MR中主對角線元素全為1，表示R是自反的。12 設(shè)R，S是集合A上的傳遞關(guān)系，則RS一定是傳遞的。答：錯誤。不一定：取A=a,b,c

14、,d,令R=(a,b),(b,c),(a,c),S=(b,c),(c,a),(b,a),易知R,S是A上的傳遞關(guān)系。然而，RS=(a,c),(a,a),(b,a),其中(b,a)RS,(a,c)RS,但是(b,c)RS，因此RS不傳遞。13 對命題變元p和q，則命題公式p(pØ q）是中性的。答：正確。14 圖 是強(qiáng)連通圖。答：錯誤。應(yīng)為弱連通圖。15 (R, +, ×)是環(huán)的主要特性之一是 × 對+可分配。 答：正確。16 整數(shù)集合Z上的整除關(guān)系“|”是對稱的。答：錯誤。1|2，但是2不整除1，故整數(shù)集合Z上的整除關(guān)系“|”是反對稱的。17 實(shí)數(shù)集合R是的小于等

15、于關(guān)系“”不是對稱的。答：正確。18 任意非永假命題公式都存在多個的主析取范式。答：錯誤。任意非永假（非永真）命題公式都存在唯一的主析取范式（主合取范式）。19 設(shè)A和B是兩個命題公式，則A = B的充要條件是A « B為永真式 。 答：正確。20 答：正確。四、綜合題：1設(shè)代數(shù)系統(tǒng)V=N8，是群。（1）寫出運(yùn)算表； （2）求每個元素的逆元 ； （3）求元素2的階及含2的各階元素的子集A使A，構(gòu)成N6，的子群。0 1 2 3 4 5 0 0 1 2 3 4 5 1 1 2 3 4 5 0 2 2 3 4 5 0 1 3 3 4 5 0 1 2 4 4 5 0 1 2 3 5 5 0

16、1 2 3 4 解：(1)(2) 0-1=0 1-1=5 2-1=4 3-1=3 (3) 元素4的階為3, A=0,2,4 2. 設(shè)集合A=1，2，3，5，6，10，15，30，“”是整除關(guān)系，代數(shù)系統(tǒng) V=，是布爾格。（1）畫出偏序集V=，的哈斯圖； （2）求出每個元素的補(bǔ)元；（3）求A的四元子集B，使B，是，的子格； （4）求A的四元子集C，使C，是格，但不是，的子格。解：哈斯圖. .（2分）1與30互補(bǔ)；（1分） 2 與15互補(bǔ)； （1分） 3 與10互補(bǔ)；（1分） 5 與6互補(bǔ)； （1分） B=1，2，3，6 (不唯一) （2分） C=1，2，3，30 （不唯一） .（2分） 3. 某

17、電路中有一只燈泡和三個開關(guān)A, B, C。已知當(dāng)且僅當(dāng)在下述4種情況之一燈亮：（1）C的搬鍵向上，A和B的搬鍵向下；（2）A的搬鍵向上，B和C的搬鍵向下；（3）B和C的搬鍵向上，A的搬鍵向下； （4）A和B的搬鍵向上，C的搬鍵向下.令F表示燈亮，p, q, r分別表示A, B, C的搬鍵向上，求F=F(p, q, r)的邏輯表達(dá)式以及F的主合取范式。解：001011100110000010101111(主合取范式)4. 設(shè)集合a, b, c, d，上的關(guān)系a, b,b, a,b, c,c,d，用集合表示法求R的自反閉包、對稱閉包、傳遞閉包。解：r(R)=a, b,b, a,b, c,c,d，&

18、lt;a,a>,<b,b>,<c,c>,<d,d>S(R)=a, b,b, a,b, c,c,d,<c,b>,<d,c>t(R)=a, b,b, a,b, c,c,d,<a,a>,<a,c>,<b,b>,<b,d>,6 是一個群，而,若f是從G到G的映射，使得對每一個，都有：。試證明：f是一個從G到G上的自同構(gòu)。證：首先證明f是單射。 其次證明f是滿射。 對 綜合以上兩點(diǎn)，知f是雙射。 6. 對于以下謂詞公式的解釋。個體域D=1, 2， 個體常量：a/1, b/2, 函詞f：f (1)/2, f (2)/1,謂詞P：P(1,1)/1, P(1, 2)/1, P(2, 1)/0, P(2, 2)/0分別求下列謂詞公式在上述解釋下的真值。（1）P(f(a), a)P(f(b), b)（2）$y"xP(y, x).解：（1）P(f (a), a)P(f (b), b)=P(f (1), 1)P(f (2), 2) =P(2, 1)P(1, 2) =01=0 （2）$y"xP(y, x).=$y (P(y, 1).P(y, 2) =(P(1, 1).P(1, 2)(P(2, 1).P(2, 2)