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

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

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

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

4、舞蹈者都很有風度，王華是個學生且是個舞蹈者。因此有些學生很有風度。（11分）3、 若是從A到B的函數(shù)，定義一個函數(shù) 對任意有，證明：若f是A到B的滿射，則g是從B到 的單射。（10分）4、 若無向圖G中只有兩個奇數(shù)度結點，則這兩個結點一定連通。（8分）5、 設G是具有n個結點的無向簡單圖，其邊數(shù)，則G是Hamilton圖（8分）四、計算 14%1、 設<Z6,+6>是一個群，這里+6是模6加法，Z6=0 ，1，2，3，4，5，試求出<Z6,+6>的所有子群及其相應左陪集。（7分）2、 權數(shù)1，4，9，16，25，36，49，64，81，100構造一棵最優(yōu)二叉樹。（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、；圖中無奇度結點且連通 10 、二、 選擇 20%（每小題 2分）題目12345678910答案B、DD；DDBDABBBB、C三、 證明 46%1、（9分）（1） S自反的，由R自反，（2） S對稱的（3） S傳遞的由（1）、（2）、（3）得；S是等價關系。2、11分證明：設P(x)：x 是個舞蹈者； Q(x) ：x很有風度； S(x)：x是個學生； a：王華上述句子符號化為：前提：、 結論： 3分PPUSTI TITITIEG11分、0分證明 ：。4、8分證明：設G中兩奇數(shù)度結點分別為u 和v，若 u，v不連通，則G至少有兩個連通分支G1、G2 ，使得u和v分別屬于G1和G2，于是G1和G2中各含有1個奇數(shù)度結點，這與圖論基本定理矛盾，因而u，v一定連通。5、8分證明： 證G中任何兩結點之和不小于n。反證法：若存在兩結點u，v 不相鄰且,令，則G-V1是具有n-2個結點的簡單圖，它的邊數(shù),可得，這與G1=G-V1為n-2個結點為簡單圖的題設矛盾，因而G中任何兩個相鄰的結點度數(shù)和不少于n。所以G為Hamilton圖.四、 計算 14%1、 7分解：子群有<0,+6>；<0,3,+6>；<0,