2011級離散數(shù)學AB原題與部分答案

PAGE第4頁（共7頁）(A)一、數(shù)理邏輯（共40分）1.判斷下列語句，如果是命題的在后面打√，如果不是命題在后面打×。（5分）（1）起來吧，我的朋友。（）（2）只有小孩才愛哭。（）（3）2+3=8。（）（4）這句話是錯的。（）（5）喜馬拉雅山最高。（）2.用真值表證明等值式P→(Q→R)（P∧Q）→R。（6分）3.求公式的主析取范式。（7分）4.假設論述域為全總個體域，用謂詞和量詞符號化下列命題。（6分）（1）有些人用左手寫字。（2）不是所有的火車都比所有的汽車快。5.若論述域是{a,b,c}，試消去下列公式中的量詞。(5分)6.公安人員審一件盜竊案，已知：甲或乙盜竊了電腦。甲盜竊了電腦僅當作案時間不能發(fā)生在午夜前。若乙證詞正確，則在午夜時屋里燈光未滅。若乙證詞不正確，則作案時間發(fā)生在午夜前。午夜時屋里燈光滅了。問誰是盜竊犯？（第一步：找出原子命題（1分）；第二步：對原命題進行符號化（5分）；第三步：用（步驟命題依據(jù)）的形式，構造證明過程（5分））二、集合、關系和函數(shù)（共36分）（原題與答案）1.用文氏圖表示集合。(2分)答： 結果為灰色區(qū)域2.計算集合{{1}，1}的冪集。（2分）答：{Φ，{{1}}，{1}，{{1}，1}}3.設，，則分別求出=？,=？。（4分）答：={2,3,4,6,8,9,12}={6,12}4.設,是上的關系，求出的元素。(2分)答：{<1,2>,<1,3><1,4><1,5><1,6>,<2,4>,<2,6>,<3,6>}Is5.設，定義在上的關系如下：.(1)畫出的關系圖，并寫出的關系矩陣.(4分)(2)說明具備那些性質(zhì)，并求出r(R),s(R),t(R).（6分）答：（1） （2）反自反，不對稱，不傳遞r(R)=s(R)={<2,1>,<4,2>,<3,1>}t(R).={<1,4>}6．設，畫出集合關于整除關系的哈斯圖，并指出它的極小元、最小元、極大元、最大元。（6分）答： 極小元：1 極大元：6，8，9 最小元：1 最大元：無7．已知f，g，h是R到R的函數(shù)。；；。求，（6分）(提示：(f1f2f3)(x)=f3(f2(f1(x))))答：8．函數(shù)f是N到N的函數(shù)：。證明f是單射不是滿射。（4分）答：設,，則，，則，所以f是單射，設，此x在定義域內(nèi)不存在，所以f不是滿射三、圖論（共24分）1.設n階無向簡單圖G中，有16條邊，每個頂點都是2度頂點，問圖G中有幾個頂點。（要求寫出計算過程）？（4分）答：設有n個頂點2*16=2*nn=162.畫出所有含有5個頂點，3條邊的不同構的簡單圖。（4分）答： 3.下面圖是不是平面圖？如果是，則請給出平面嵌入。（4分） 答： 4.設無向樹T有3個3度，2個2度頂點，其余頂點都是樹葉，問T中有幾片樹葉？（要求寫出計算過程）并畫出滿足要求的非同構的無向樹.。（4分）答：設有n個頂點2*(n-1)=3*3+2*2+(n-3-2)*1n=105.列出下圖所有的割點與割邊。（4分） 答：割點：b,f割邊：(f,g)6.設7個符號在通信中出現(xiàn)的頻率為：A:20%,B:35%,C:15%,D:10%,E:10%,F:5%，G:5%以頻率為權，求最優(yōu)2元樹。(4分)答：

(B)一、數(shù)理邏輯（共40分）1.判斷下列語句，如果是命題的在后面打√，如果不是命題在后面打×。（5分）（1）2是素數(shù)嗎?（）（2）17只能被1和它本身整除。（）（3）2+3=8。（）（4）我正在說謊。（）（5）如果太陽從從西方升起，你就可以長生不老。（）2.寫出命題公式的真值表。(6分)3.求公式的主合取范式。（7分）4.假設論述域為全總個體域，用謂詞和量詞，符號化下列命題。（6分）（1）每個自然數(shù)都有后繼數(shù)。（2）某些人對某些食物過敏。5設個體域為，則消去量詞后為：__________。(5分)6．構造下列命題的證明過程：2是素數(shù)或合數(shù)。若2是素數(shù)，則是無理數(shù)。若是無理數(shù)，則4不是素數(shù)。所以，如果4是素數(shù)，則2是合數(shù)。（第一步：找出原子命題（1分）；第二步：對原命題進行符號化（4分）；第三步：用（步驟命題依據(jù)）的形式，書寫構造性證明過程（6分））二、集合、關系和函數(shù)（共36分）（原題與答案）1.用文氏圖表示集合。(2分)答：2.計算集合{1，2}的冪集。（2分）答：{Φ，{1}，{2}，{1，2}}3.設全集，它的子集：，,則分別求出=?=?。（4分）答：={3}={1,2,5}4.,,,求出的元素。(2分)答：R={<1,1>,<1,3>,<3,1>,<3,3>}5.設，定義在上的關系如下：.(1)畫出的關系圖，并寫出的關系矩陣.(4分)答： (2)說明具備那些性質(zhì)，并求出r(R),s(R),t(R).（6分）答：反自反，不對稱，傳遞r(R)=s(R)={<2,1>,<4,2>,<1,4>}t(R).=6．設，畫出集合關于整除關系的哈斯圖，并指出它的極小元、最小元、極大元、最大元。（6分）答：極小元：1 極大元：24 最小元：1 最大元：247.已知f，g，h是R到R的函數(shù)。；；。求，（6分）(提示：(f1f2f3)(x)=f3(f2(f1(x))))答：8．函數(shù)f是N到N的函數(shù)：。證明g是滿射不是單射。（4分）答：，所以g不是單射任取，若y=0，則x為0，或者1。當y>=1時，x=y+1。所以g是滿射三、圖論（共24分）1．設n階無向簡單圖G中，有21條邊，3個4度頂點，其余的都是3度頂點，問圖G中有幾個頂點。（要求寫出計算過程）（4分）答：設有n個頂點21*2=3*4+(n-3)*3n=132.畫出所有含有4個頂點3條邊不同構的簡單圖。（4分）答：3.下面圖是歐拉圖還是半歐拉圖？如果是歐拉圖，請給出歐拉回路，如果是半歐拉圖請給出歐拉通路。（4分）答：歐拉圖歐拉回路：(a,b),(b,c),(c,f),(f,b),(b,d),(d,f),(f,e),(e,d),(d,c),(c,a)4.設無向樹T有7片樹葉，其余頂點度