1、離散數學總復習離散數學總復習本次考試題型n1、填空題（2*10=20）n2、選擇題（2*10=20）n3、解答題（5題共30分）n4、證明題（2題10分）n5、應用題（2題20分）樣卷（僅作參考）樣卷（僅作參考）n一一.填空題填空題(20分分)n1、設、設P：我有時間；：我有時間；Q：我將去市里，將：我將去市里，將“只有我有時間，我才去只有我有時間，我才去市里市里”命題符號化命題符號化 _.答案：答案：(QP)n2、公式、公式( x)(P(x, y)Q(x, y) ( z)R(y, z) s(x) 中自由變元為中自由變元為_.約束變元為約束變元為_.n答案：答案：(x,y),(x,z)n3、設

2、、設F=,，G=,，則，則FG = _.n答案：答案：,n4、代數系統、代數系統（其中（其中Z是整數集合，是整數集合，+是普通加法），是普通加法），Z對對+的幺的幺元為元為_,零元為零元為_, 任任xZ, x-1=_.n答案：答案：0，不存在，不存在，-xn一一.填空題填空題(20分分)n5、設設K5 是有是有5個點的完全圖，則個點的完全圖，則K5有有_條邊。條邊。n答案：答案：10:,RR6、設設R為實數集合，映射為實數集合，映射 則則 的性質是的性質是_。:,RR2( )21,xxx 7、 設集合設集合 A=a，b，c,那么集合那么集合A的冪集合的冪集合 是是_。( ), , , , ,

3、, , , , , , , P Aabca ba cb ca b c解:8、謂詞公式謂詞公式 的前束范式是的前束范式是_.( )( )xP xxQ x解：原式解：原式 ( )( )xP xyQ y ( ( )( )x y P xQ x 答案：既不是單射也不是滿射答案：既不是單射也不是滿射. n二二.選擇題選擇題(10分分)n1、 下面下面4個推理定律中，不正確的為個推理定律中，不正確的為 （）。（）。nA. A=(AB) (附加律附加律) nB. (AB) A=B (析取三段論析取三段論)nC. (AB)A=B (假言推理假言推理) nD. (AB) B=A (拒取式拒取式)n答案：答案：Dn

4、2. 下列四個命題中哪一個為真？（）。下列四個命題中哪一個為真？（）。 A. B. anC. D. n答案：答案：Dn3. 設設S=a,b,c,d，R=,，則，則R的性質是的性質是 （）（）nA.自反、對稱、傳遞的自反、對稱、傳遞的 B. 對稱、反對稱、傳遞的對稱、反對稱、傳遞的nC.自反、對稱、反對稱的自反、對稱、反對稱的 D. 只有對稱性只有對稱性n答案：答案：Bn二二.選擇題選擇題(10分分)n4. 下列四組數據中，不能成為任何下列四組數據中，不能成為任何4階無向簡單圖的度數序列的為（）階無向簡單圖的度數序列的為（）n A. 2,2,2,2 B. 1,1,1,3n C. 1,1,2,3

5、D. 1,2,2,3n答案：答案：Cn 5. 設設A=a,b,c，則下列是集合，則下列是集合A的劃分的是（）。的劃分的是（）。nA.b,c,c nB.a,b,a,c nC.a,b,c nD.a,b,cn答案：答案：D三、解答題（6題共42分）n1、設集合A1, 2, 3, 4, 6, 8, 12，R是A上的整除關系，(1)畫出偏序集(A, R)的哈斯圖；(2)寫出A的子集2, 4, 6, 8的上界，下界，最小上界，最大下界； (3) 寫出集合A的最大元，最小元，極大元，極小元。解：(1) 偏序集(A, R)的哈斯圖(2) 子集2, 4, 6, 8無上界，下界是1,2，無最小上界，最大下界是2.

6、(3) A無最大元，最小元是1，極大元是8, 12，極小元是1。12483612n2、求(PQ) (RP) 的主析取范式和主合取范式n解：(PQ)(RP)=(PQ)(RP)（合取范式）=(P Q (R R) (P (Q Q) R)=(P Q R)(P Q R)(P Q R)(P Q R) =(P Q R)(P Q R)(P Q R)（主合取范式）=(0,1,2) （主合取范式）=(3,4,5,6,7) （主析取范式） ,:2,3,(2)3,(3)2, (2)1, (3)0(2,2)(3,3)1,(2,3)(3.2)0( ( ( ), )( ).fPQIDffPPQQQQIx y Q f xyP

7、 x 3 、設 是一元運算是一元謂詞是二元謂詞 給定解釋求在解釋 下的真值解： )(),(xPyxfQyx)(),(xPyxfQyx)()3),()2),(xPxfQxfQx)3()3),3()2),3()2()3),2()2),2(PfQfQPfQfQ)3()3, 2()2, 2()2()3, 3()2, 3(PQQPQQ)010() 101 (114、 如圖給出的賦權圖表示六個城市及架起城市間直接通訊如圖給出的賦權圖表示六個城市及架起城市間直接通訊線路的預測造價。試給出一個設計方案使得各城市間能夠通線路的預測造價。試給出一個設計方案使得各城市間能夠通訊且總造價最小，并計算出最小總造價。訊且

8、總造價最小，并計算出最小總造價。解題解題：（：（最小生成樹的應用）最小生成樹的應用）其樹權即最小造價為：其樹權即最小造價為：1+2+3+5+7=18。5、化簡集合式子、化簡集合式子)()()(ACBABACBAABA：)(原式解ABA)()()(ABAAAB n6、（1）設G1是實數加群，G2是非零實數關于普通乘法構成的群。令：RR*, (x)ex請問是G1到G2的同態映射嗎？（2）設G1,G2是群，e2是G2的幺元。令：G1G2, (a)e2，aG1是G1到G2的同態映射嗎？解：（1）是G1到G2的同態,因為x,yR有(x+y)ex+yex ey(x)(y)因為：G1G2是單射的，則稱為單同

9、態（2）因為a,bG1有(ab)e2 e2e2 (a)(b)因為：G1G2不單射不滿射，不是單同態也不是滿同態。四、證明題（四、證明題（14分）分） 1、證明：、證明：RSQPSRQP)()(證明：（證明：（1） S 附加前提引入附加前提引入（2） 前提引入前提引入PS （3） （2）置換）置換PS （4） (1)(3)假言推理假言推理P（5） 前提引入前提引入)(RQP （6） (4)(5)假言推理假言推理RQ （7） 前提引入前提引入Q（8） (4)(5)假言推理假言推理R（9）CP規則規則RS n2、I上的二元運算*定義為：a,bI，a*b=a+b-2。試證：為群。n證明：n（1）對任意

10、的a,bI，a*b=a+b-2 I,所以I對于二元運算*是封閉的。n（2）a,b,c I，(a*b)*c=(a*b)+c-2=(a+b-2)+c-2=a+b+c-4, a*(b*c)=a+(b*c)-2=a+(b+c-2)-2=a+b+c-4。故(a*b)*c= a*(b*c)，從而*滿足結合律。n（3）記e=2。對a I，a*2=a+2-2=a=2+a-2=2*a.。故e=2是I關于運算*的幺元。n（4）對a I，因為a*（4-a）=a+4-a-2=2=e=4-a+a-2=(4-a)*a。故4-a是a關于運算*的逆元。n 綜上所述，為群。五、應用題（五、應用題（14分）分）例如：例如： 在有向圖在有向圖D（如下圖）中，求從結點（如下圖）中，求從結點v1到到v4長度為長度為4的所有通路條數（要求寫出），從的所有通路條數（要求寫出），從v3到到