1、離散數學復習題一、單項選擇題1.下列命題公式為重言式的是【 A 】。Ap (pq)B(pp)qCqqDpq2下列語句中不是命題的是【 A 】。A這個語句是假的。B1+1=1.0C飛碟來自地球外的星球。D凡石頭都可練成金。3設A=，1，1，3，1，2，3，則A上包含關系“”的哈斯圖為【 C 】4在公式中變元y是【 B 】。A自由變元B約束變元C既是自由變元，又是約束變元D既不是自由變元，又不是約束變元5設A=1，2，3，A上二元關系S=<1，1>，<1，2>，<3，2>，<3，3>，則S是【 D 】。A自反關系B反自反關系C對稱關系D傳遞關系6圖

2、中 從v1到v3長度為3 的通路有【 D 】條。 A0； B1； C2； D3。7在下列代數系統中，不是環的只有【 C 】。A<Z，+，*)，其中Z為整數集，+，*分別為整數加法和乘法。B(Q，+，*)，其中Q為有理數集，+，*分別為有理數加法和乘法。C<R，+，*>，其中R為實數集，+為實數加法，a*b=a+2b。D<Mn (R)，+，*>，其中Mn(R)為實數集n×n階矩陣結合，+，*是矩陣加法和乘法。8下列整數集對于整除關系都構成偏序集，而能構成格的是【 B 】。Al，2，3，4，5B1，2，3，6，12C2，3，7Dl，2，3，79結點數為奇數且

3、所有結點的度數也為奇數的連通圖必定是【 D 】。A歐拉圖B漢密爾頓圖C非平面圖D不存在的10無向圖G是歐拉圖當且僅當G是連通的且【 C 】。AG中各頂點的度數均相等BG中各頂點的度數之和為偶數CG中各頂點的度數均為偶數DG中各頂點的度數均為奇數11.設S=0，1，*為普通乘法，則< S , * >是【 B 】。 A.半群，但不是獨異點； B.只是獨異點，但不是群； C.群 ； D.環，但不是群；12設（A，+，×）是代數系統，其中+，×是普通的加法和乘法運算，能使（A，+，×）成為環的集合A是【 A 】。A所有偶數組成的集合； B所有奇數組成的集合；

4、C所有正整數組成的集合； D所有非負整數組成的集合。13設A=1，2，3，則A上的二元關系有【 C 】個。 A 23 ； B 32 ； C ； D 。14在【 A 】下有。A； B、C、； D、15下列結果正確的是【 B 】。A； B；C； D。 16設p：我很累，q：我去學習，命題：“除非我很累，否則我就去學習”的符號化正確的是【 B 】。ApqBpqCpqDpq 17下列函數是雙射的為【 A 】Af : IE , f (x) = 2x ； Bf : NNN, f (n) = <n , n+1> ；Cf : RI , f (x) = x ； Df :IN, f (x) = | x

5、 | 。（注：I整數集，E偶數集， N自然數集，R實數集）18有向圖中D=<V , E> ，則長度為2的通路有【 D 】條。A0； B1； C2； D3 。19在一棵樹中有7片樹葉，3個度為3的結點，其余都是度為4的結點，則該樹有【 A 】個度為4的結點。A1； B2； C3； D4 。20下圖中既不是Eular圖，也不是Hamilton圖的圖是【 B 】二、填空題請在每小題的空格中填上正確答案。錯填、不填均無分。1.命題邏輯與謂詞邏輯的區別是。2.謂詞邏輯中，命題被分解為_, _兩部分。3.集合的常用表示方法有_, _, _和圖示法四種。4.具有_, _和_ 三種性質的二元關系叫

6、等價關系。5.n階有向完全圖的邊數為_, n階無向完全圖的邊數為_。6.如果一個圖的每條邊都是_稱為有向圖，每條邊都是 稱為無向圖。7.若圖中存在_的通路， 該圖稱為半歐拉圖。8.有向圖樹T中，_稱為根，_稱為樹葉。9.設R是A上的二元關系，當有（a,b）R和（b,c）R時，必有 ,則稱R為可傳遞的二元關系。abca b cb b cc c b10.設代數系統<A，*>，其中A=a，b，c,則幺元是 ；是否有冪等性 ；是否有對稱性 。 11.能夠判斷_稱為命題。 12.不包含任何聯結詞的命題叫做_命題, 至少包含一個聯結詞的命題叫做_命題。 13.二元關系的表示方法有_, _, _

7、 三種。 14.（1）A，B，C表示三個集合，文圖中陰影部分的集合表達式為 A B C 。（2）設P，Q 的真值為0，R，S的真值為1，則的真值= 。（3）公式的主合取范式為 。 15.，*表示求兩數的最小公倍數的運算（Z表示整數集合），對于*運算的幺元是 ，零元是 。 16.將有向圖D各邊的方向去掉得無向圖G, 稱G為D的_。 17.若圖中存在_回路， 該圖稱為歐拉圖。 18.拉格朗日定理說明若<H , *>是群<G,*>的子群，則可建立G中的等價關系R= 。若|G|=n, |H|=m 則m和n關系為 。19根據入射函數，滿射函數，雙射函數的定義填空。設N是自然數集合

8、，Z是整數集合，R是實數集合，則f1（NN, f1（n）= n2）是 函數；f2（NN, f2（n）= n + 10）是 函數；f3（ZZ, f3（z）= z + 10）是 函數；f4（RR, f4（r）= r +5.6）是 函數；f5（Z0,1,當z為偶數時，f5(z)=1;當z為奇數時，f5(z)=0。）是 函數。填空題參考答案：1.在命題邏輯中，原子命題是進行演算的基本單位，不再研究命題的內部結構。而謂詞邏輯的任務就是對原子命題作進一步的分析，研究其內部的邏輯結構。2.個體詞和謂詞兩部分。 3.列舉法、敘述法、特定字母集和圖表法。4自反性、對稱性和傳遞性 5. n2和n(n-1)/26有

9、向邊和無向邊 7一條通過圖中各邊一次且僅一次的通路。8入度為零的頂點稱為根，出度為零的頂點稱為葉子。9（a,c）R 10. a、 否、 有 11能夠判斷內容真假的語句稱為命題。12原子和復合。 13表格法、矩陣法和圖表法。 14.(1)；(2)1；(3) 15不存在、e 16.底圖 17一條通過圖中各邊一次且僅一次的回路。 18、 19入射、入射、雙射、雙射、滿射。三、判斷說明題判斷下列各題正誤，正確的在題后括號內打“”，錯誤的打“×”，并說明其正確或錯誤的理由。（一） 判斷下列語句那些是命題1我是工程師。 【 】2計算機有空嗎？ 【 × 】36是奇數。 【 】4太美妙了！

10、 【 × 】5.雪是白的。 【 】6.我是大學生 【 】7.雪是黑的。 【 】8.外星人是存在的。 【 】9.請打開門！ 【 × 】10.這束花多么好看啊！ 【 × 】（二）下列函數中（15小題），哪些是單射函數，滿射函數，雙射函數。其中N是自然數集合，I是整數集合，R是實數集合。已知集合A =a, b, c，集合B =1, 2, 3, 下列AB的二元關系中，R1R5哪些可以構成函數。1f：NN, f（n）= 2n 【單射 】2f：AB,A=0,1,2,B=0,1,2,3,4,f(a)=a2 【單射 】3f：II, f（i）= i + 10 【 雙射 】 4f:

11、II, f(i)=|i| 【 既不是單射，也不是滿射】 5.f: I0,1,當I為偶數時，f(i)=0;當I為奇數時，f(i)=1。 【滿射 】 6.R1 = （a, 1）,（b, 2）,（c, 3） 【 】 7.R2 = （a, 3）,（c, 2）,（c, 1） 【 × 】 8.R3 = （a, 2）,（b, 1）,（b, 2）,（c, 3） 【 × 】 9.R4 = （b, 1）,（c, 3） 【 × 】 10.R5 = （a, 1）,（b, 1）,（c, 3） 【 】 四、表述題：將下列命題符號化（一） 命題邏輯符號化1.我美麗而又快樂。2.如果老張和老李都

12、不去，他就去。3.電燈不亮，當且僅當燈泡或開關發生故障。 4.王強工作努力且身體好。 5.我是本次校運動會的跳遠或100米短跑的冠軍。 6.只要有學習機會，我一定用功讀書。 7.兩個三角形全等，當且僅當它們的三個對應邊相等。 8.如果不下雨，我不乘公交車上班。（二） 謂詞邏輯符號化（論域為全部個體域） 1.小張不是學生。 2.所有的有理數都是實數。 3.小張大于18歲，身體健康，無色盲，大學畢業，則他可參加飛行員考試。 4.小王不是研究生。37他是跳高或籃球運動員38.曉莉非常聰明和能干39.若m是奇數，則2m是偶數。四、參考答案：（一）1.設P表示命題“我美麗”，Q表示命題“我快樂”。則用符

13、號表示命題為：PQ2.P表示“老張去”；Q表示“老李去”；R表示“他去”。則（PQ）R。3.設P表示“電燈不亮”，Q表示“燈泡發生故障”；R表示“開關發生故障”。則P（QR）。 4.設P表示命題王強工作努力，Q表示命題王強身體好。則用聯結詞表示復合命題為：PQ 5.設P：我是本次校運動會的跳遠冠軍Q：我是本次校運動會的100米短跑的冠軍，則PQ。 6.設P：有學習機會，Q：我一定用功讀書，則PQ。 7.設P：兩個三角形全等，Q：三個對應邊相等，則PQ 8.P：下雨，Q：我不乘公交車上班。則PQ。 （二） 1.令S（x）:x是學生；a:小張；則S(a) 2. 設Q(x):x是有理數；R(x):x

14、是實數，則符號化為：x(Q(x) R(x) 3.設A(x):x超過18歲；B(x):x身體健康；C(x):x 色盲；D(x):x大學畢業 E(x):x參加飛行員考試；a:小張；則A(a)B(a)C(a)D(a) E(a)。 4.設A(x):x是研究生；a:小王，則A(a)。 5.設A(x):x是跳高運動員；B(X):x是籃球運動員；a：他；則A(a)B(a) 6.設A(x):x非常聰明；B(x): x能干；a: 曉莉；則A(a)B(a) 7.A(x):x是奇數；B(x): x 是偶數；m:某整數；則A(m) B(2m)。五、計算題1構造 公式：P Q的真值表2.已知集合A =1, 2, 求集合

15、A的冪集P（A）。3. 已知集合A =a, b, 求集合A 上的笛卡爾積A×A.4. 知集合A =a, b, c, d, R=（a, a）,（a, c）,（a,d）,（b,a）,（b,b）,（b,d）,（c,a）,（d,b）,（d,c） 是A上的關系，試用矩陣表示法表示R。5. 試畫出樹葉權為1，2，3，5，7，12的最優二元樹，并求出該樹的權。 6.求公式( P Q ) ( P Q )的真值表。 7已知集合A =1, 2, 3, 求集合A的冪集P（A）。8已知集合A =a, b, c, 求集合A 上的笛卡爾積A×A. 9畫出一個3階有向完全圖10（A，R）是偏序集，A=2

16、，3，4，5，6，8，12，16，24，R是A上的整除關系。試寫出A中的所有極大元和極小元，它有沒有最大元和最小元？ 五、參考答案： 1.PQP QFFTFTTTFFTTT2.因為A2，所以A的冪集P（A）224。P（A），1,2,1,2 3.A×A=a,b×a,b=(a,a),(a,b),(b,a),(b,b), 4.A =a, b, c, d, R=（a, a）,（a, c）,（a,d）,（b,a）,（b,b）,（b,d）,（c,a）,（d,b）,（d,c） 矩陣表示：10111101100001101811633001275312 5. 最優二元樹為：最優二元樹的權為

17、： W=12+18+2*(7+11)+3*(5+6)+4*(3+3)+5*(1+2)=138 6.PQPQP QP Q( P Q ) ( P Q )TTFFFFFTFFTFTTFTTFTFTFFTTFFF 7.因為A3，所以A的冪集P（A）238。P（A），1,2,3,1,21,3,2,3,1,2,3 8A×A=a,b,c×a,b,c=(a,a),(a,b),(a,c),(b,a),(b,b),(b,c),(c,a),(c,b),(c,c)V1V3V1 9. 10極大元為：5，16，24；極小元為：2，3，5。無最大和最小元。六、證明題1設R是A上的反自反關系和可傳遞關系，證明R是A上的反對稱關系。2. 若圖G中恰有兩個奇數頂點，則這兩個頂點是連通的。3.設A和B是集合，證明A（B-A）=AB。4R是集合X上的一個自反關系，求證：R是對稱和傳遞的，當且僅當< a, b> 和<a , c>在R中，則有<.b , c>在R中。六、參考答案：1.證：因為當ab，且（a,b）R時，