離散數(shù)學(xué)試卷及答案(2)

1、離散數(shù)學(xué)試卷(二)一、填空 20% （每小題2分）1、 P：你努力，Q：你失敗?！俺悄闩?，否則你將失敗”的翻譯為 ；“雖然你努力了，但還是失敗了”的翻譯為 。2、論域D=1，2，指定謂詞PP (1,1)P (1,2)P (2,1)P (2,2)TTFF則公式真值為 。2、 設(shè)S=a1 ，a2 ，a8，Bi是S的子集，則由B31所表達(dá)的子集是 。3、 設(shè)A=2，3，4，5，6上的二元關(guān)系，則R= （列舉法）。R的關(guān)系矩陣MR= 。5、設(shè)A=1，2，3，則A上既不是對(duì)稱的又不是反對(duì)稱的關(guān)系R= ；A上既是對(duì)稱的又是反對(duì)稱的關(guān)系R= 。*a b cabca b cb b cc c b6、設(shè)代數(shù)系

2、統(tǒng)<A，*>，其中A=a，b，c,則幺元是 ；是否有冪等 性 ；是否有對(duì)稱性 。7、4階群必是 群或 群。8、下面偏序格是分配格的是 。9、n個(gè)結(jié)點(diǎn)的無(wú)向完全圖Kn的邊數(shù)為 ，歐拉圖的充要條件是 。10、公式 的根樹(shù)表示為 。二、選擇 20% （每小題2分）1、在下述公式中是重言式為（ ）A；B；C； D 。2、命題公式 中極小項(xiàng)的個(gè)數(shù)為（ ），成真賦值的個(gè)數(shù)為（ ）。A0； B1； C2； D3 。3、設(shè)，則 有（ ）個(gè)元素。A3； B6； C7； D8 。4、 設(shè)，定義上的等價(jià)關(guān)系則由 R產(chǎn) 生的上一個(gè)劃分共有（ ）個(gè)分塊。A4； B5； C6； D9 。5、設(shè)，S上關(guān)系R的關(guān)

3、系圖為則R具有（ ）性質(zhì)。A自反性、對(duì)稱性、傳遞性； B反自反性、反對(duì)稱性；C反自反性、反對(duì)稱性、傳遞性； D自反性 。6、設(shè) 為普通加法和乘法，則（ ）是域。A BC D= N 。7、下面偏序集（ ）能構(gòu)成格。8、在如下的有向圖中，從V1到V4長(zhǎng)度為3 的道路有（ ）條。A1； B2； C3； D4 。9、在如下各圖中（ ）歐拉圖。10、設(shè)R是實(shí)數(shù)集合，“”為普通乘法，則代數(shù)系統(tǒng)<R ，×> 是（ ）。A群； B獨(dú)異點(diǎn)； C半群 。三、證明 46%1、 設(shè)R是A上一個(gè)二元關(guān)系，試證明若R是A上一個(gè)等價(jià)關(guān)系，則S也是A上的一個(gè)等價(jià)關(guān)系。（9分）2、 用邏輯推理證明：所有的

4、舞蹈者都很有風(fēng)度，王華是個(gè)學(xué)生且是個(gè)舞蹈者。因此有些學(xué)生很有風(fēng)度。（11分）3、 若是從A到B的函數(shù)，定義一個(gè)函數(shù) 對(duì)任意有，證明：若f是A到B的滿射，則g是從B到 的單射。（10分）4、 若無(wú)向圖G中只有兩個(gè)奇數(shù)度結(jié)點(diǎn)，則這兩個(gè)結(jié)點(diǎn)一定連通。（8分）5、 設(shè)G是具有n個(gè)結(jié)點(diǎn)的無(wú)向簡(jiǎn)單圖，其邊數(shù)，則G是Hamilton圖（8分）四、計(jì)算 14%1、 設(shè)<Z6,+6>是一個(gè)群，這里+6是模6加法，Z6=0 ，1，2，3，4，5，試求出<Z6,+6>的所有子群及其相應(yīng)左陪集。（7分）2、 權(quán)數(shù)1，4，9，16，25，36，49，64，81，100構(gòu)造一棵最優(yōu)二叉樹(shù)。（7分）

5、一、 填空 20%（每小題2分）1、； 2、T 3、 4、R=<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,2>,<5,3>,<5,4>,<5,5>,<5,6>； 5、R=<1,2>,<1,3>,<2,1>；R=<1,1>,<2,2>

6、;,<3,3> 6、a ；否；有 7、Klein四元群；循環(huán)群 8、 B 9、；圖中無(wú)奇度結(jié)點(diǎn)且連通 10 、二、 選擇 20%（每小題 2分）題目12345678910答案B、DD；DDBDABBBB、C三、 證明 46%1、（9分）（1） S自反的，由R自反，（2） S對(duì)稱的（3） S傳遞的由（1）、（2）、（3）得；S是等價(jià)關(guān)系。2、11分證明：設(shè)P(x)：x 是個(gè)舞蹈者； Q(x) ：x很有風(fēng)度； S(x)：x是個(gè)學(xué)生； a：王華上述句子符號(hào)化為：前提：、 結(jié)論： 3分PPUSTI TITITIEG11分、0分證明 ：。4、8分證明：設(shè)G中兩奇數(shù)度結(jié)點(diǎn)分別為u 和v，若 u，v不連通，則G至少有兩個(gè)連通分支G1、G2 ，使得u和v分別屬于G1和G2，于是G1和G2中各含有1個(gè)奇數(shù)度結(jié)點(diǎn)，這與圖論基本定理矛盾，因而u，v一定連通。5、8分證明： 證G中任何兩結(jié)點(diǎn)之和不小于n。反證法：若存在兩結(jié)點(diǎn)u，v 不相鄰且,令，則G-V1是具有n-2個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖，它的邊數(shù),可得，這與G1=G-V1為n-2個(gè)結(jié)點(diǎn)為簡(jiǎn)單圖的題設(shè)矛盾，因而G中任何兩個(gè)相鄰的結(jié)點(diǎn)度數(shù)和不少于n。所以G為Hamilton圖.四、 計(jì)算 14%1、 7分解：子群有<0,+6>；<0,3,+6>；<0,