離散數(shù)學(xué)期末考試題有幾套帶答案

1、-. z.離散數(shù)學(xué)試題(A卷及答案一、證明題10分1)(P(QR)(QR)(PR)R2)*(A(*)B(*)*A(*)*B(*)二、求命題公式(P(QR)(PQR)的主析取*式和主合取*式10分證明：(P(QR)(PQR)(P(QR)(PQR)P(QR)(PQR)(PQ)(PR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)m0m1m2m7M3M4M5M6三、推理證明題10分-. z.CD, (CD)E, E(AB), (AB)(RS)RS證明：(1) (CD)E (2) E(AB) (3) (CD)(AB)(4) (AB)(RS) (5) (CD)(RS) (6) CD (7)

2、 RS2) *(P(*)Q(y)R(*)，*P(*)Q(y)*(P(*)R(*)證明1*P(*)(2)P(a)(3)*(P(*)Q(y)R(*)(4)P(a)Q(y)R(a)(5)Q(y)R(a)(6)Q(y)(7)R(a)(8)P(a)(9)P(a)R(a)(10)*(P(*)R(*)(11)Q(y)*(P(*)R(*)-. z.四、設(shè)m是一個取定的正整數(shù)，證明：在任取m1個整數(shù)中，至少有兩個整數(shù)，它們的差是m的整數(shù)倍證明 設(shè)，為任取的m1個整數(shù)，用m去除它們所得余數(shù)只能是0，1，m1，由抽屜原理可知，這m1個整數(shù)中至少存在兩個數(shù)和，它們被m除所得余數(shù)一樣，因此和的差是m的整數(shù)倍。五、A、B

3、、C是三個集合，證明A-(BC)=(A-B)(A-C) 15分證明* A-BC * A*BC * A*B*C * A*B* A*C *A-B*A-C *A-BA-CA-BC=A-BA-C六、R、S是N上的關(guān)系，其定義如下：R=| *,yNy=*2，S=| *,yNy=*+1。求R-1、R*S、S*R、R1,2、S1,210分解：R-1=| *,yNy=*2，R*S=| *,yNy=*2+1，S*R=| *,yNy=*+12，七、假設(shè)f:AB和g:BC是雙射，則gf-1=f-1g-110分。證明：因?yàn)閒、g是雙射，所以gf：AC是雙射，所以gf有逆函數(shù)gf-1：CA。同理可推f-1g-1：CA是

4、雙射。因?yàn)閒-1g-1存在zg-1f-1存在zfggfgf-1,所以gf-1=f-1g-1。R1,2=,，S1,2=1,4。八、15分設(shè)是半群，對A中任意元a和b，如ab必有a*bb*a，證明：(1)對A中每個元a，有a*aa。(2)對A中任意元a和b，有a*b*aa。(3)對A中任意元a、b和c，有a*b*ca*c。證明 由題意可知，假設(shè)a*bb*a，則必有ab。(1)由(a*a)*aa*(a*a)，所以a*aa。(2)由a*(a*b*a)(a*a)*(b*a)a*b*(a*a)(a*b*a)*a，所以有a*b*aa。(3)由(a*c)*(a*b*c)(a*c*a)*(b*c)a*(b*c)

5、(a*b)*c(a*b)*(c*a*c)(a*b*c)*(a*c)，所以有a*b*ca*c。九、給定簡單無向圖G，且|V|m，|E|n。試證：假設(shè)n2，則G是哈密爾頓圖證明 假設(shè)n2，則2nm23m6 1。假設(shè)存在兩個不相鄰結(jié)點(diǎn)、使得d()d()m，則有2nm(m2)(m3)mm23m6，與1矛盾。所以，對于G中任意兩個不相鄰結(jié)點(diǎn)、都有d()d()m，所以G是哈密爾頓圖。離散數(shù)學(xué)試題(B卷及答案一、證明題10分1)(PQ)(P(QR)(PQ)(PR)T證明左端(PQ)(P(QR)(PQ)(PR)(摩根律) (PQ)(PQ)(PR)(PQ)(PR)(分配律) (PQ)(PR)(PQ)(PR) (

6、等冪律) T(代入)2)*(P(*)Q(*)*P(*)*(P(*)Q(*)證明*(P(*)Q(*)*P(*)*(P(*)Q(*)P(*)*(P(*)Q(*)P(*)*(P(*)Q(*)*P(*)*Q(*)*(P(*)Q(*)二、求命題公式(PQ)(PQ) 的主析取*式和主合取*式10分解：(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ) (PPQ)(QPQ)(PQ)M1m0m2m3三、推理證明題10分-. z.1)(P(QS)(RP)QRS證明：1R 附加前提(2)RP P(3)P T(1)(2),I(4)P(QS) P(5)QS T(3)(4),I(6)Q P(7)S T(5

7、)(6),I(8)RS CP2) *(P(*)Q(*)，*P(*)* Q(*)證明：(1)*P(*) P(2)P(c) T(1),US(3)*(P(*)Q(*) P(4)P(c)Q(c) T(3),US(5)Q(c) T(2)(4),I(6)* Q(*) T(5),EG-. z.四、例5在邊長為1的正方形內(nèi)任意放置九個點(diǎn)，證明其中必存在三個點(diǎn)，使得由它們組成的三角形可能是退化的面積不超過1/810分。證明：把邊長為1的正方形分成四個全等的小正方形，則至少有一個小正方形內(nèi)有三個點(diǎn)，它們組成的三角形可能是退化的面積不超過小正方形的一半，即1/8。五、A、B、C是三個集合，證明A(BC)=(AB)(

8、AC) 10分證明：* ABC * A*BC * A*B*C * A*B* A*C *AB* AC *ABACABC=ABAC六、=A1，A2，An是集合A的一個劃分，定義R=|a、bAi，I=1，2，n，則R是A上的等價關(guān)系15分。證明：aA必有i使得aAi，由定義知aRa，故R自反。a,bA，假設(shè)aRb ，則a,bAi，即b,aAi，所以bRa，故R對稱。a,b,cA，假設(shè)aRb 且bRc，則a,bAi及b,cAj。因?yàn)閕j時AiAj=，故i=j，即a,b,cAi，所以aRc，故R傳遞?？傊甊是A上的等價關(guān)系。七、假設(shè)f:AB是雙射，則f-1:BA是雙射15分。證明:對任意的*A，因?yàn)閒是

9、從A到B的函數(shù)，故存在yB，使f，f-1。所以,f-1是滿射。對任意的*A，假設(shè)存在y1,y2B，使得f-1且f-1,則有f且f。因?yàn)閒是函數(shù)，則y1=y2。所以，f-1是單射。因此f-1是雙射。八、設(shè)是群，和是的子群，證明：假設(shè)ABG，則AG或BG10分。證明 假設(shè)AG且BG，則存在aA，aB，且存在bB，bA否則對任意的aA，aB，從而AB，即ABB，得BG，矛盾。對于元素a*bG，假設(shè)a*bA，因A是子群，a-1A，從而a-1 * (a*b)bA，所以矛盾，故a*bA。同理可證a*bB，綜合有a*bABG。綜上所述，假設(shè)不成立，得證AG或BG。九、假設(shè)無向圖G是不連通的，證明G的補(bǔ)圖是連

10、通的10分。證明 設(shè)無向圖G是不連通的，其k個連通分支為、。任取結(jié)點(diǎn)、G，假設(shè)和不在圖G的同一個連通分支中，則，不是圖G的邊，因而，是圖的邊；假設(shè)和在圖G的同一個連通分支中，不妨設(shè)其在連通分支1中，在不同于的另一連通分支上取一結(jié)點(diǎn)，則，和，都不是圖G的邊，因而，和，都是的邊。綜上可知，不管那種情況，和都是可達(dá)的。由和的任意性可知，是連通的。 選擇題.(每題2分，總計(jì)30) 給定語句如下：115是素?cái)?shù)質(zhì)數(shù)210能被2整除，3是偶數(shù)。3你下午有會嗎？假設(shè)無會，請到我這兒來！42*+30.5只有4是偶數(shù)，3才能被2整除。(6)明年5月1日是晴天。以上6個語句中，是簡單命題的為A,是復(fù)合命題的為B,是

11、真命題的為C,是假命題的是D,真值待定的命題是EA: (1)(3)(4)(6) (1)(4)(6) (1)6 B: (2)(4) (2)(4)(6) (2)(5)C: (1)(2)(5)(6) 無真命題 5 D: (1)(2) 無假命題 (1)(2)(4)(5)E: (4)(6) 6 無真值待定的命題將以下語句符號化：14是偶數(shù)或是奇數(shù)。A設(shè)p：4是偶數(shù)，q：4是奇數(shù)2只有王榮努力學(xué)習(xí)，她才能取得好成績。B設(shè)p：王榮努力學(xué)習(xí)，q：王榮取得好成績3每列火車都比*些汽車快。C設(shè)F(*):*是火車，G(y):y是汽車，H(*,y):*比y快。A: pq pq pq B: pq qp pqC: *y

12、(F(*)G(y) (H(*,y)* (F(*)y(G(y)H(*,y)* (F(*)y(G(y)H(*,y)3.設(shè)S=1,2,3,以下圖給出了S上的5個關(guān)系,則它們只具有以下性質(zhì):R1是A,R2是(B),R3是(C)。A B C:自反的，對稱的，傳遞的 反自反的，對稱的 自反的反對稱的 對稱的 自反的，對稱的，反對稱的，傳遞的4. 設(shè)S=，1，1，2，則有 1AS 2 (B)S3 P(S)有C個元數(shù)。 4D既是S的元素，又是S的子集A: 1,2 1 B:1,2 1C: 3 6 7 8 D: 1 二、證明本大題共2小題，第1小題10分，第2小題10分，總計(jì)20分1、用等值演算算法證明等值式 (

13、pq)(pq)p2、構(gòu)造下面命題推理的證明如果今天是星期三，則我有一次英語或數(shù)學(xué)測驗(yàn)；如果數(shù)學(xué)教師有事，則沒有數(shù)學(xué)測驗(yàn)；今天是星期三且數(shù)學(xué)教師有事，所以我有一次英語測驗(yàn)。三、計(jì)算本大題共4小題，第1小題5分，第2小題10分，第3小題15分，總計(jì)30分1、設(shè)，求公式：的真值。2、設(shè)集合上的關(guān)系 ，求出它的自反閉包，對稱閉包和傳遞閉包。3、設(shè)上的整除關(guān)系，是否為上的偏序關(guān)系？假設(shè)是，則：1、畫出的哈斯圖；10分2、求它的極小元，最大元，極大元，最大元。5分四、用推導(dǎo)法求公式的主析取*式和主合取*式。本大題10分答案：選擇題A: B: C: D: E: 2.A: B: C:3.A: B: C: 4.

14、A: B: C: D:二、證明題證明 左邊(pq)p(pq)q) 分配律 p(pq)q) (吸收律) p(pq) (qq) 分配律 p(pq)1 排中律 p (pq) 同一律 p 吸收律2.解：p：今天是星期三。 q：我有一次英語測驗(yàn)。 r：我有一次數(shù)學(xué)測驗(yàn)。 s：數(shù)學(xué)教師有事。 前提：p(qr) , sr , ps 結(jié)論：q 證明：ps 前提引入p 化簡p(qr) 前提引入qr 假言推理s 化簡sr 前提引入r 假言推理q 析取三段論推理正確。三、計(jì)算1. 該公式的真值是1，真命題?；蛘?、3、1 是上的偏序關(guān)系。2極小元、最小元是1,極大元、 最大元是24。四、*大學(xué)2004-2005學(xué)年

15、第二學(xué)期離散數(shù)學(xué)期末考試試卷A卷參考答案一、單項(xiàng)選擇1 在自然數(shù)集上，以下哪種運(yùn)算是可結(jié)合的？ A. B. C. D. 2 以下代數(shù)系統(tǒng)中，哪個是群？ A. ，*是模7加法 B. 有理數(shù)集合，*是一般乘法C. 整數(shù)集合，*是一般減法 D. ，*是模11乘法3 假設(shè)是的真子群，且，則有 。A. 整除 B. 整除C. 整除且 整除 D. 不整除且 不整除4 下面哪個集合關(guān)于指定的運(yùn)算構(gòu)成環(huán)？ A. ，關(guān)于數(shù)的加法和乘法abcdefabcdefgC. ，關(guān)于數(shù)的加法和乘法D. ，關(guān)于矩陣的加法和乘法5 在代數(shù)系統(tǒng)中，整環(huán)和域的關(guān)系為 。A. 域一定是整環(huán) B.域不一定是整環(huán) C. 整環(huán)一定是域 D.

16、 域一定不是整環(huán)6 是自然數(shù)集，是小于等于關(guān)系，則是 。A. 有界格 B.有補(bǔ)格 C. 分配格 D. 有補(bǔ)分配格7 圖1-1給出的哈斯圖表示的格中哪個元素?zé)o補(bǔ)元？ A. B. C. D. 圖1-18 給定以下序列，可構(gòu)成無向簡單圖的結(jié)點(diǎn)度數(shù)序列的是 。A.1，1，2，2，3 B.1，3，4，4，5C.0，1，3，3，3 D.1，1，2，2，29 歐拉回路是 。A.路徑 B.簡單回路 C.既是根本回路也是簡單回路 D.既非根本回路也非簡單回路10 哈密爾頓回路是 。A.路徑 B.簡單回路 C.既是根本回路也是簡單回路 D.既非根本回路也非簡單回路填空題以下每個下劃線為一空，請按要求填入適宜的內(nèi)容

17、。每空2分，共30分。1 設(shè)是非空有限集，代數(shù)系統(tǒng)中，對運(yùn)算的單位元是，零元是，對運(yùn)算的單位元是。 a b ca = 1 * GB3 a b ca = 1 * GB3 a = 2 * GB3 b a b cc = 3 * GB3 c = 4 * GB3 = 1 * GB3 ， = 2 * GB3 ， = 3 * GB3 ， = 4 * GB3 。3 設(shè)，是群的子群，其中，是模12加法，則有個真子群，的左陪集，。4設(shè)是一個布爾代數(shù)，如果在上定義二元運(yùn)算為：，則是一個。表2-15 任何一個具有個元素的有限布爾代數(shù)都是。6 假設(shè)連通平面圖有4個結(jié)點(diǎn)，3個面，則有條邊。7 一棵樹有兩個結(jié)點(diǎn)度數(shù)為2，一

18、個結(jié)點(diǎn)度數(shù)為3，三個結(jié)點(diǎn)度數(shù)為4，它有個度數(shù)為1的結(jié)點(diǎn)。8 無向圖是由棵數(shù)組成的森林，至少要添加條邊才能使成為一棵樹。三、求解題20分 1 試寫出中每個子群及其相應(yīng)的左陪集。 6分274412274412313653 有向圖如圖3-1所示。1求的鄰接矩陣； 2分2中到長度為4的路徑有幾條？ 2分3中到自身長度為3的回路有幾條？ 2分4是哪類連通圖？ 2分圖3-1四、證明題30分1 設(shè)是一群，。定義：，。證明也是一群。 2 證明：1證明在格中成立：。 5分2證明布爾恒等式：。 5分3 證明：1在6個結(jié)點(diǎn)12條邊的連通平面簡單圖中，每個面由3條邊圍成。 5分2證明當(dāng)每個結(jié)點(diǎn)的度數(shù)大于等于3時，不存

19、在有7條邊的簡單連通平面圖。*大學(xué)2004-2005學(xué)年第二學(xué)期離散數(shù)學(xué)期末考試試卷A卷參考答案一、單項(xiàng)選擇1B; 2.D; 3.A; 4.C; 5.A; 6.C; 7.B; 8.D; 9.B; 10.C.填空題1 ，； 2 ，；3 5，；4 交換群；5 同構(gòu)；6 5；7 9；8 。三、求解題解：子群有：，。的左陪集為：，的左陪集為：，的左陪集為：，2 答：1一個有向歐拉圖一定是強(qiáng)連通圖。因?yàn)槭菤W拉圖，存在歐拉回路，中的每個結(jié)點(diǎn)至少在中出現(xiàn)一次。因而中任意兩點(diǎn)，都在中，相互可達(dá)，故是強(qiáng)連通的。2一個強(qiáng)連通圖不一定是有向歐拉圖。因?yàn)閺?qiáng)連通圖中每個結(jié)點(diǎn)的入度不一定等于其出度。3 解：12由中可知，

20、到長度為4的路徑有條56748，。567483由中可知，到自身長度為3的回路有1條。4是單向連通圖。四、證明題1 證明：顯然是上的二元運(yùn)算即滿足封閉性，要證是群，需證結(jié)合律成立，同時有單位元，每個元素有逆元。，有運(yùn)算是可結(jié)合的。 其次，是的單位元。事實(shí)上，有； 最后證明，是在中的逆元。事實(shí)上， 由以上證明，是群。2 證明：1 公式(13)分配不等式又因?yàn)?，所以?因?yàn)?，所以有?吸收律即等式成立。 3 證明：1因圖中結(jié)點(diǎn)數(shù)和邊數(shù)分別為，根據(jù)歐拉公式，得。又，而簡單連通平面圖的每個面至少由3條邊圍成，所以在6個結(jié)點(diǎn)12條邊的連通平面簡單圖中，每個面由3條邊圍成。2設(shè)圖為簡單連通平面圖，有個面。反

21、證法 假設(shè)，由歐拉公式知，而每個面至少由3條邊圍成，有，則，且是整數(shù)，所以；又對任結(jié)點(diǎn)，有，故，且是整數(shù)，所以。這樣就有，與矛盾，所以結(jié)論正確。*大學(xué)2007 2008學(xué)年第 2 學(xué)期離散數(shù)學(xué)下考試試卷A卷一、單項(xiàng)選擇題每題2分，共20分1. 以下集合關(guān)于數(shù)的加法和乘法運(yùn)算不能構(gòu)成環(huán)的是 A.自然數(shù)集合； B.整數(shù)集合； C.有理數(shù)集合； D.實(shí)數(shù)集合。2. 設(shè)為整數(shù)集合，則以下集合關(guān)于數(shù)的加法運(yùn)算不能構(gòu)成獨(dú)異點(diǎn)的是 A.； B.； C.； D.。設(shè)，為模加法，則以下元素是的生成元的是 A.； B.3； C.4； D.5。4. 設(shè)是整環(huán)，則不一定是 A.可交換環(huán)； B.無零因子環(huán)； C.含么環(huán)

22、； D.域。5. 格不一定具有 A.交換律； B.結(jié)合律； C.分配律； D.吸收律。6. 設(shè)，和分別表示求最小公倍數(shù)和最大公約數(shù)運(yùn)算，則是 A.有補(bǔ)格； B.分配格； C.有補(bǔ)分配格； D.布爾代數(shù)。7. 一個含個結(jié)點(diǎn)的無向圖中有個結(jié)點(diǎn)的度數(shù)分別為，則第個結(jié)點(diǎn)的度數(shù)不可能是 A.0； B.1； C.2； D.4。設(shè)連通的簡單平面圖中有10條邊和5個面，則的結(jié)點(diǎn)數(shù)為 A.6； B.7； C.8； D.9。設(shè)無向樹中有個結(jié)點(diǎn)度數(shù)為，個結(jié)點(diǎn)度數(shù)為，個結(jié)點(diǎn)度數(shù)為，則中的樹葉數(shù)為 A.10； B.11； C.12； D.13。10設(shè)為連通的無向圖，假設(shè)僅有個結(jié)點(diǎn)的度數(shù)是奇數(shù)，則一定具有路徑； 哈密爾頓路徑；哈密爾頓回路。二、填空題每小空2分，共20分1. 設(shè)為實(shí)數(shù)集合，則在代數(shù)中，關(guān)于運(yùn)算的么元是 ，零元是 。2. 設(shè)為模加法，則在中，元素的階為，的階為 。3. 設(shè)，和分別為求最大公約數(shù)和最小公倍數(shù)運(yùn)算，則在布爾代數(shù)中，原子的個數(shù)為 ，元