華東交通大學(xué)2009-2010第一學(xué)期離散數(shù)學(xué)期末試卷及參考答案

受弊作因和籍學(xué)除開被將者考人他代或考代人他請道：名簽生學(xué)受弊作因和籍學(xué)除開被將者考人他代或考代人他請道：名簽生學(xué)號學(xué)級班業(yè)專試卷編號： （A）卷離散數(shù)學(xué)課程 課程類別：必修 考試日期： 月 日題號題分一二三四五六題號題分一二三四五六七八九總分 累分人簽100名得分注意事項1、本試卷共8頁（其中試題4頁，總分100 分，考試時間120 分鐘。2、所有答案必須填在答題紙上，寫在試卷上無效；3、考試結(jié)束后，考生不得將試卷、答題紙和草稿紙帶出考場。一、單項選擇題（210=20）下列語句是命題的有[ ]A. x22y1 ；2010年的國慶節(jié)是晴天；青年學(xué)生多么朝氣蓬勃呀！學(xué)生不準(zhǔn)吸煙!2．若一個代數(shù)系統(tǒng)是獨異點（含幺半群，則以下選項中一定滿足的是[ ]A.封閉性，且有零元; B.結(jié)合律，且有幺元；C.交換性，且有幺元; D.結(jié)合律，且每個元素有逆元.3．Z是整數(shù)集合，下列函數(shù)都是Z→Z的映射，則[ ]是單射而非滿射函數(shù)A．(x)=0 B．(x)=x2 C．(x)=2x D．(x)=x與命題p(pq)等值的公式是[ ]。A.p； B.q； C.pq； D.pq.1M={a,b,c}，MR={<a,a>,<b,b>,<c,c>,<b,c>,<c,b>}確定的集合M的劃分是[ ]。A.{{a},,{c}} B.{{a,c},{b,c}} C.{{a,c},} D.{{a},{b,c}}設(shè)D：全總個體域是花是人喜歡y，則命“每個人都喜歡某種花”的邏輯符號化為[ ]。A.x(M(x)y(F(y)H(x,y))；B. x(M(x)y(F(y)H(x,y))；C.x(M(x)y(F(y)H(x,y))；D. x(M(x)y(F(y)H(x,y)).下列圖中，不是哈密頓圖的[ ]。A B C D下列四組數(shù)據(jù)中，能作為某個4階無向簡單圖的度序列的為[ ]A.1,2,3,4； B.2,2,2,3； C.1,1,2,3； D.1,1,1,3.3階無向完全圖（K）有[ ]個非同構(gòu)的生成子圖。3A. 5 B. 4 C. 3 D. 2下列選項中與A∪B=A等價的是 。A．A∩B=A B．BA C．A∪B=B 二、填空題（210=20）1.設(shè)集合A＝{a,b}，B={a,c}，則A(B－A)= 。(為對稱差)2.設(shè)p：我努力學(xué)習(xí)我取得好成績，命題“除非我努力學(xué)習(xí)，否則我不能得好成績”的符號化形式為 。3.II下，xF(x,2) 的真值為 。24.謂詞公式xF(x)∧xG(x)的前束范式為 。65.設(shè)Z={0,1,2,3,4,5}，為模6加法，即x,yZ6，xy=(x+y)mod6，若有程：1x3=2，則x= 。6等價關(guān)系滿足自反性、對稱性和 三個性質(zhì)。設(shè)函數(shù)f(x)=2x，g(x)=x2+1,則fog= 。無向連通圖G是歐拉圖，當(dāng)且僅當(dāng)G中每一個頂點的度數(shù)都為 。設(shè)A為集合，且|A|=3，則A上最多可定義 個不同的二元關(guān)系。設(shè)A為非空有限集P(A為冪集則代數(shù)系統(tǒng)P(), 中的幺元為 。三、綜合題（1、210860）（10分）前提：p→(qr)，s→r，ps；結(jié)論：q.求公式(p→q(q→r)（10分）3.Ab,a>,<b,c>,<c,d分)R的關(guān)系圖；R2；Rr(R)s(R)。4.設(shè)S={1,2,3,4,6,8,12}“”為S上的整除關(guān)系（8分問（1）偏序集S ,的Hass圖如何？偏序集S ,的極小元、最小元、極大元、最大元是什?在偏序集S ,中，B={4,6}的上確界、下確界是什么？3G（8分）v1 2 1 01Av20

0 1 0v0 1 0 13 v 04（1）。

0 1 0（2G2（3）該圖是為強(qiáng)連通圖還是弱連通圖？設(shè)集合G3nnZ}（其中：Z是整數(shù)集G和乘法運算構(gòu)成何種代數(shù)系統(tǒng)（半群、獨異點還是群）？（8分） G85角形（3G（8分）4受弊作因和籍學(xué)除開被將者考人他代或考代人他請：名簽生學(xué)道，后性切受弊作因和籍學(xué)除開被將者考人他代或考代人他請：名簽生學(xué)道，后性切的起弊引作此級班律學(xué)紀(jì)予場授考不守將遵分格處嚴(yán)上將以我及業(yè)諾記專答題紙（參考答案）離散數(shù)學(xué)課程 課程類別必修得分一20二20三60四 五 六 七 八 九 十總分100計分人簽名一、單項選擇題(每小題2分，共20分)題號題號12345678910答案BBCADCADBB二、填空題(每小題2分，共20分)1 {a,b,c} 2p→q或q→p 3.1或真 4.xy(F(x)∧G(y))5. 4 6. 傳遞性 7． 8. 偶數(shù) 9.29 或512 10. 三、綜合題（1、2103-7860）1．1小題答案：得分評閱人證明：①ps前提引入②p①化簡③p→(qr)④qr前提引入②③假言推理注意：案r 須對應(yīng)⑥s⑦r前提引入①化簡⑤⑥假言推理⑧q④⑦析取三段論5注意：答案與題號必須對應(yīng)22小題答案：得分評閱人解： (p→q)(q→r)(pq)(qr)((pq)(rr))((pp)(qr))(pqr)(pqr)(pqr)(pqr)MMMM4526∏(2,4,5,6)∑(0,1,3,7)公式(p→q)(q→r)1,3,7)4,5,6)公式(p→q)(q→r)的成真賦值為：000，001，011，1113小題答案：得分評閱人a?b）關(guān)系圖如右圖：d?c0（2）M1001000010001100,M2MM001001000001,000R2={<a,a>，<a,c>，<b,b>，<b,d>}（3）r(R)=R∪I={<a,b>,<b,a>,<b,c>,<c,d>,<a,a>,<b,b>,<c,c>,<d,d>}As(R)R∪R1={<a,b>,<b,a>,<b,c>,<c,d>,<c,b>,<d,c>}6第4小題答案：得分 評閱人8124623（）<，≤的Hass圖如右圖：1(2)<S，≤>最小元：1極大元：8，12；最大元：無（3）偏序集<S，≤>中，B={4，6}的上確界：12下確界：2第5小題答案：得分 評閱人vv 21v v解（）有向圖G如右圖： 4 31 2 1 0 1 3 3 1 （2）A0 0 1 0,A2

AA0 1 0 10 1 0 1 0 0 2 00 0 1 0 0 1 0 1 G中長度小于等于2的通路的條數(shù)為：8+14=24，其中，回路為1+5=6條。（3）該圖為弱連通圖。7注意：答案與題號必須對應(yīng)6小題答案：得分評閱人證明：G構(gòu)成群>。證明如下：（1）3x,3yG，x,yZ，3x3y=3x+yG，故集合關(guān)于運算是封閉的；（）3,3,3zx,y,（xy）3z=x(3y3z，故集合關(guān)于運算是可結(jié)合的；（3）3xG，xZ，3x1=13x=3x，故集合G關(guān)于1；（4）3xG，xZ，3x3-x=3-x3x