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

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

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