離散數(shù)學(xué)復(fù)習(xí)題

1、復(fù)習(xí)題（一）一 單項選擇題（每題2分，共20分）題號12345678910答案1.下述命題公式中，是重言式的為（ ）。A、 ； B、 ；C、 ； D、 。2.設(shè)S1=1，2，8，9，S2=2，4，6，8，S3=1，3，5，7，9，S4=3，4，5，S5=3，5，在條件下X與（ ）集合相等。A、 X= S1，S2或S4 ； B、X=S2或S4；C、X=S1，S2 ，S3或S4； D、X與S1，S5中任何集合都不等。3. 設(shè)A為有限集，元素個數(shù)為n個，P(A)為A的冪集，則P(A)的元素個數(shù)及的元素個數(shù)為( ) A B 及 C 及 D以上全不對4設(shè)，R是A上相等關(guān)系“=”，由R產(chǎn)生等價類有( )

2、A10個 B50個 C100個 D1個5. 若供選擇答案中的數(shù)值表示一個簡單圖中各個頂點的度，能畫出圖的是( ). A. (1,2,2,3,4,5) B. (1,2,3,4,5,5) C. (1,1,1,2,3) D. (2,3,3,4,5,6).6設(shè)有函數(shù)（R表示實數(shù)集），且，則復(fù)合數(shù)函數(shù)是（ ） A滿射B單射C雙射7.若無向圖為樹，其中，則等價于以下敘述中的（ ） A連通且 B連通且 C當(dāng)且僅當(dāng)連通 D當(dāng)且僅當(dāng)無回路8 設(shè)I為整數(shù)集，Q為有理數(shù)集，R為實數(shù)集；下列代數(shù)結(jié)構(gòu)為群的是( ). (1) (2) (3) (4) A無 B(1)、(4) C(1)、(3)、(4) D全體都是9. 設(shè)i

3、是虛數(shù)，是復(fù)數(shù)乘法運算，則G=是群，下列是G的子群是( )A. B.-1, C.i, D.-i,10.在下列關(guān)于圖論的命題中，為真的命題是（）A.一個強連通的有向圖一定是歐拉圖； B. 完全圖Kn都是歐拉圖C.完全二部圖都是哈密頓圖 D.完全圖Kn（n2）都是哈密頓圖。二 填空題（2分1020分）1.設(shè)，A上的關(guān)系，則_。2設(shè)G是具有個結(jié)點，條邊的連通圖，則G的生成樹T有_個結(jié)點，_條邊。3一個班有50個人，在第一次考試中有26人得優(yōu)秀，在第二次考試中有21人得優(yōu)秀，如果兩次考試都得優(yōu)秀的有14人，問兩次考試都沒有得優(yōu)秀的有_人？4設(shè)A=a，b，c，A上二元關(guān)系R= , , , 則R的對稱閉包

4、s（R）= 。5 一個無向圖是歐拉圖的充要條件是 。6. 設(shè)A為非空集合1,2,3，P(A)為A的冪集，則對于P(A)中的二元運算：對稱差，群P(A)，中，1-3=_7一個無向圖為二部圖的充要條件是 8將公式化為等價的前束范式: (x)F(x)(x)G(x)_.9 矛盾式的主析取范式為_.10 一個n（n1）階無向簡單圖G中，n為奇數(shù)，已知G中有r個奇數(shù)度頂點，則G的補圖有_個奇數(shù)度頂點。三 （1） 判定公式的類型（10分）（2）求(PQ)R的主析取范式與主合取范式，并寫出其相應(yīng)的成真賦值和成假賦值。（10分）四 （20分）設(shè)為一個偏序集，其中，A = 1, 2, 3, 4, 6, 8, 9,

5、 16, R是A上的整除關(guān)系。（1）畫出R的哈斯圖； （2）求A的極大元和極小元； （3）求B = 4, 6的最小上界和最大下界。 （4）集合A關(guān)于整除偏序關(guān)系是否能構(gòu)成格？為什么？五 （20分） 設(shè)A=0，1，2，3，4，定義 * 運算如下：,(1) 列出 * 的運算表；(2) * 是否有零元、幺元？如有，則求出相應(yīng)值，求出具有逆元的元素和相應(yīng)的逆元。（3）構(gòu)成何種代數(shù)系統(tǒng)？復(fù)習(xí)題（二）一 填空題（每空3分，共45分）1. 設(shè)謂詞公式：，個體域：1, 2，將其中的量詞消去，寫出與之等價的命題公式為 .2. 一個結(jié)點為n的無向完全圖，其邊的數(shù)目為 ；3 完全二部圖K4,5有_條邊, 匹配數(shù)是_

6、.4 設(shè)M(x):x是人，D(x):x是要死的，則命題“所有的人都是要死的”可符號化為(x) _,其中量詞(x)的轄域是_。5. 已知n階無向簡單圖G有m條邊，則G的補圖有_條邊。6設(shè)，則A的冪集有元素_個。7. 重言式的主合取范式為 _, 矛盾式的主析取范式為_.8. 一個有向圖為歐拉圖的充要條件是 .9整數(shù)集合上關(guān)于普通加法運算所構(gòu)成的群Z，中，元素(-2)-3_10設(shè)A=a，b，c，A上二元關(guān)系R= , , , 則自反閉包r（R）= 。11 一個班有45個人，在第一次考試中有26人得優(yōu)秀，在第二次考試中有21人得優(yōu)秀，如果兩次考試都得優(yōu)秀的有14人，問兩次考試都沒有得優(yōu)秀的有_人？12

7、設(shè)無向圖中有6條邊，有一個3度頂點和一個5度頂點，其余頂點度為2，則該圖的頂點數(shù)是_。二. (15分) 設(shè)集合A1, 2, 3，R和S是A上的兩個關(guān)系，它們的關(guān)系矩陣為：寫出關(guān)系R和S 的集合表達式，(2) 畫出R和S的關(guān)系圖，(3) 說明R和S滿足關(guān)系的哪些特性.三（1）. 判定公式的類型 (10分) (pqq)（2） (10分)求下列公式的主合取范式及主析取范式(PQ)R四 .(10分) 設(shè)集合A1, 2, 3, 4, 6, 8, 12，R是A上的整除關(guān)系，（1）畫出偏序集(A, R)的哈斯圖；（2）寫出集合A的極大元，極小元，最大元，最小元。五 (10分)設(shè)Z是整數(shù)集合，在Z上定義二元運

8、算如下：x * y = x + y 2，證明：Z，*是群。復(fù)習(xí)題答案（一）一、 單項選擇題（每題2分，共20分）1-5 ACBCC 6-10 CABAD 二、 填空題（每題2分，共20分）(1) （2）n，n1（3）17 （4） , , ，, (5) 連通且所有頂點的度數(shù)都是偶數(shù) (6) 1(7) G中無奇數(shù)度長度的回路 (8) （9）0 （10）r三（共20分）（1） 所以該式是永真式。2）(PQ)R(PQ)R(PQ)R(P(QQ)R)(PP)QR)(PQR)(PQR)(PQR)(PQR) 主析取范式為： 主合取范式為：其相應(yīng)的成真賦值為000、001、011、101、111成假賦值為：01

9、0、100、110 。四（共20分）（2）極大元：6，9，16 極小元：1 （3）最小上界：不存在，最大下界：2 （4）構(gòu)不成格，因為集合中任意兩元素構(gòu)成的集合并不是都有最小上界和最大下界。例如4,6無最小上界。 五 （20分）*01234000000101234202413303142404321（2）零元是0，幺元是1. O無逆元，1的逆元是1，2和3互為逆元，4的逆元是4；（3） 是獨異點，因為滿足結(jié)合律，有幺元，但是不是所有元素有逆元。復(fù)習(xí)題答案（二）一填空題（每空3分，共45分）(1) （2）（3）20，4 （4），(5) (6) 8 (7) 1，0 (8) 連通且所有頂點的入度等于

10、初度（9）6 （10） , , ， （11）12 （12）4二 （15分）R= , , ，, S= , , 關(guān)系圖略關(guān)系R：自反； 關(guān)系S：反對稱，傳遞三 （20分）（1）(pqq)所以該式是矛盾式。2）(PQ)R(PQ)R(PQ)R(P(QQ)R)(PP)QR)(PQR)(PQR)(PQR)(PQR) 主析取范式為： 主合取范式為：其相應(yīng)的成真賦值為000、001、011、101、111成假賦值為：010、100、110四（共10分）哈斯圖略極小元：1 極大元：8，12 最小元：1 最大元：不存在五（10分）證明：要證Z，*是群, 即要證*運算在整數(shù)集合上滿足結(jié)合律，有幺元，每個元素都有逆元。（3分）任取整數(shù)x, y, z， x * y* z = （x + y 2）*