離散數(shù)學(xué)試題與答案

試卷二試題與參考答案一、填空1、 P：你努力， Q：你失敗。2、 “除非你努力，否則你將失敗”符號化為；“雖然你努力了，但還是失敗了”符號化為。2、論域 D=1，2 ，指定謂詞 PP (1,1)P (1,2)P (2,1)P (2,2)TTFF則公式x yP( y, x) 真值為。3 設(shè) A=2， 3， 4， 5， 6 上的二元關(guān)系 R x, y | xy x是質(zhì)數(shù) ，則R=（列舉法）。R 的關(guān)系矩陣RM=。4、設(shè) A=1 ，2，3 ，則 A 上既不是對稱的又不是反對稱的關(guān)系R=；A 上既是對稱的又是反對稱的關(guān)系R=。5、設(shè)代數(shù)系統(tǒng) <A， *>，其中 A=a ， b，c,*abcaabcbbbccccb則幺元是；是否有冪等性；是否有對稱性。6、 4 階群必是群或群。7、下面偏序格是分配格的是。8、 n 個結(jié)點的無向完全圖Kn 的邊數(shù)為，歐拉圖的充要條件是。二、選擇1、在下述公式中是重言式為（）A (P Q)(PQ) ； B ( PQ )( P Q) (QP) ；C (PQ)Q ； D P (P Q) 。2、命題公式(PQ )( Q P)中極小項的個數(shù)為（），成真賦值的個數(shù)為（）。A 0；B 1；C 2；D 3 。3、設(shè) S ,1,1,2 ，則2 S有（）個元素。A3； B 6； C 7； D 8 。4、設(shè) S 1,2, 3 ，定義 SS上的等價關(guān)系R a,b, c, d | a,bSS, c, dS S, a d b c 則由 R產(chǎn) 生的 SS上一個劃分共有（）個分塊。A4； B 5； C 6； D 9 。5、設(shè) S 1, 2, 3 ， S 上關(guān)系 R 的關(guān)系圖為則 R 具有（）性質(zhì)。A自反性、對稱性、傳遞性；B反自反性、反對稱性；C反自反性、反對稱性、傳遞性；D 自反性 。6、設(shè), 為普通加法和乘法，則（） S, ,是域。A S x | x a b 3 , a,b Q B S x | x 2n , a, b ZC S x | x 2n 1, n ZD S x | x Z x 0 = N 。7、下面偏序集（）能構(gòu)成格。8、在如下的有向圖中，從V1 到 V4 長度為 3 的道路有（）條。A1；B 2；C 3；D 4 。9、在如下各圖中（）歐拉圖。10、10、設(shè) R 是實數(shù)集合， “”為普通乘法，則代數(shù)系統(tǒng)<R ， > 是（）。A群；B獨異點；C 半群。三、證明1、設(shè) R 是 A 上一個二元關(guān)系，Sa, b| (a,bA)(對于某一個cA, 有a,cR且c, bR)試證明若R是A 上一個等價關(guān)系，則S 也是A 上的一個等價關(guān)系。2、 用邏輯推理證明：所有的舞蹈者都很有風(fēng)度，王華是個學(xué)生且是個舞蹈者。因此有些學(xué)生很有風(fēng)度。3、若無向圖G中只有兩個奇數(shù)度結(jié)點，則這兩個結(jié)點一定連通。m1 ( n 1)(n 2)24、設(shè) G是具有 n 個結(jié)點的無向簡單圖，其邊數(shù)2，則 G是 Hamilton圖。四、計算1、設(shè) <Z6,+ 6>是一個群，這里+6 是模 6 加法， Z6=0 ，1 ， 2 ， 3 ， 4 ， 5，試求出<Z6,+ 6>的所有子群及其相應(yīng)左陪集。2、權(quán)數(shù) 1， 4， 9， 16， 25， 36， 49， 64， 81， 100 構(gòu)造一棵最優(yōu)二叉樹。試卷二參考答案：一、 填空1、PQ ； P Q2、 T3、 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>；11111111110001111111000004、 R=<1,2>,<1,3>,<2,1>；R=<1,1>,<2,2>,<3,3>5、 a ；否；有6、 Klein四元群；循環(huán)群7、 B1 n(n1)8、 2；圖中無奇度結(jié)點且連通二、選擇題目12345678910答案B、 DD； DDBDABBBB、 C三、 明1、（ 1）S 自反的a A，由 R 自反，( a, aR)( a, aR) ，a, aS（ 2）S 稱的a, bAa, bS( a,cR)( c,bR)S 定義(a, cR) (c, bR)R 對稱b, aSR 傳遞（ 3）S 的a, b, cAa, bSb, cS(a, dR)(d , bR) (b, eR)(e, cR)(a, bR)(b, cR)R 傳遞a, cSS 定義由（ 1）、（ 2）、（3）得； S 是等價關(guān)系。2、 明： P(x) ： x 是個舞蹈者；Q(x)： x 很有 度；S(x) ：x 是個學(xué)生；a ：王 上述句子符號化 ：前提： x(P( x)Q( x) 、 S(a) P(a) ： x(S(x) Q (x) 3 分 S( a) P(a)前提引入 x(P( x)Q( x)前提引入 P( a)Q(a) US P(a)化 Q( a).假言推理 I S( a)化 S( a) Q(a)合取 x(S(x)Q (x) EG 11 分、 明：b1 , b2B ,(b1 b2 )f 滿射a1 , a2 A使f ( a1 )b1 , f (a2 )b2 , 且 f (a1 )f (a2 ), 由于 f是函數(shù) ,a1a2又 g (b1 ) x | (xA) ( f ( x) b1 ),g(b2 ) x | ( xA)( f (x)b2 )a1 g(b1 ), a2g(b2 )但 a1 g(b2 ), a2g(b1 )g(b1 )g(b2 )由b1 , b2 任意性知 , g為單射 。4、證明：設(shè) G中兩奇數(shù)度結(jié)點分別為u 和 v，若 u ， v 不連通，則G至少有兩個連通分支G1、G2 ，使得 u 和 v 分別屬于 G1 和 G2，于是 G1 和 G2 中各含有1 個奇數(shù)度結(jié)點，這與圖論基本定理矛盾，因而 u， v 一定連通。5、證明：證 G中任何兩結(jié)點之和不小于n。反證法： 若存在兩結(jié)點u，v 不相鄰且 d(u)d (v)n1, 令 V1 u, v ，則 G-V1 是具有 n-2 個 結(jié) 點 的 簡 單 圖 ， 它 的 邊 數(shù)m 1 (n 1)( n 2) 2 ( n 1)2, 可 得m1 (n 2)(n 3)12，這與11G中G=G-V 為 n-2 個結(jié)點為簡單圖的題設(shè)矛盾，因而任何兩個相鄰的結(jié)點度數(shù)和不少于n。所以 G為 Hamilton圖.四、計算解：子群有 <0,+6>； <0,3,+>；<0,2,4,+6>； <Z ,+>6660的左陪集： 0， 1 ； 2， 3； 4， 50， 3的左陪集： 0 ，3； 1 ， 4 ； 2， 50， 2， 4 的左陪集： 0， 2， 4；1 ， 3 ， 5Z 的左陪集： Z 。66