《離散數(shù)學試題與答案》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學試題與答案（12頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 試卷二試題與參考答案 一、填空 1、 P：你努力， Q：你失敗。 2、 “除非你努力，否則你將失敗”符號化為 ； “雖然你努力了，但還是失敗了”符號化為 。 2、論域 D={1，2} ，指定謂詞 P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 則公式 x yP( y, x) 真值為 。 3 設(shè) A={2， 3， 4， 5， 6}

2、上的二元關(guān)系 R { x, y | x y x是質(zhì)數(shù) } ，則 R= （列舉法）。 R 的關(guān)系矩陣 R M= 。 4、設(shè) A={1 ，2，3} ，則 A 上既不是對稱的又不是反對稱的關(guān)系 R= ； A 上既是對稱的又是反對稱的關(guān)系 R= 。 5、設(shè)代數(shù)系統(tǒng) ，其中 A={a ， b，c}, * a b c a a b

3、c b b b c c c c b 則 幺 元 是 ；是否 有冪等 性 ；是否有對稱性 。 6、 4 階群必是 群或 群。 7、下面偏序格是分配格的是 。 8、 n 個結(jié)點的無向完全圖  Kn 的邊數(shù)為 

4、 ，歐拉圖的充要條件是 。 二、選擇 1、在下述公式中是重言式為（ ） A． (P Q) (P Q) ； B． ( P Q )(( P Q) (Q P)) ； C． (P Q) Q ； D ． P (P Q) 。 2、命題公式 ( P Q ) ( Q P) 中極小項的個數(shù)為（ ），成真賦值的個數(shù) 為（ ）。 A． 0； B ． 1； C ． 2

5、； D ． 3 。 3、設(shè) S { ,{1}, {1,2}} ，則 2 S 有（ ）個元素。 A．3； B ． 6； C ． 7； D ． 8 。 4、設(shè) S { 1, 2, 3} ，定義 S S上的等價關(guān)系 R { a,b , c, d | a,b S S, c, d S S, a d b c} 則由 R 產(chǎn) 生 的 S S上一個劃分共有（ ）個分塊。 A．4； B ． 5； C ． 6； D ． 9 。 5、設(shè) S { 1, 2, 3} ， S

6、上關(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 Z} C． S { x | x 2n 1, n Z} D ． S { x | x Z

7、 x 0} = N 。 7、下面偏序集（ ）能構(gòu)成格。 8、在如下的有向圖中，從 V1 到 V4 長度為 3 的道路有（ ）條。 A．1； B ． 2； C ． 3； D ． 4 。 9、在如下各圖中（ ）歐拉圖。 10、 10、設(shè) R 是實數(shù)集合， “ ”為普通乘法，則代數(shù)系統(tǒng) 是（ ）。 A．群； B ．獨異點； C ．半群 。

8、 三、證明 1、設(shè) R 是 A 上一個二元關(guān)系， S {  a, b  | (a,b  A) (對于某一個  c  A, 有  a,c  R且  c, b  R)} 試證明若  R是  A 上一個等價關(guān)系，則  S 也是  A 上的一個等價關(guān)系。 2、 用邏輯推理證明： 所有的舞蹈者

9、都很有風度，王華是個學生且是個舞蹈者。因此有些學生很有風度。 3、若無向圖 G中只有兩個奇數(shù)度結(jié)點，則這兩個結(jié)點一定連通。 m 1 ( n 1)(n 2) 2 4、設(shè) G是具有 n 個結(jié)點的無向簡單圖，其邊數(shù) 2 ，則 G是 Hamilton 圖。 四、計算 1、設(shè) 是一個群，這里 +6 是模 6 加法， Z6={[0 ] ，[1] ， [2] ， [3] ， [4] ， [5]} ，試求 出的所有子群及其相應(yīng)左陪集。 2、權(quán)數(shù) 1， 4， 9， 16， 25， 36， 49， 6

10、4， 81， 100 構(gòu)造一棵最優(yōu)二叉樹。 試卷二參考答案： 一、 填空 1、 P Q ； P Q 2、 T 3、 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>} ； 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 4、 R={<1,2>,<1,3>,<2,1>} ；R={<1,1>,<2,

11、2>,<3,3>} 5、 a ；否；有 6、 Klein 四元群；循環(huán)群 7、 B 1 n(n 1) 8、 2 ；圖中無奇度結(jié)點且連通 二、選擇 題目 1 2 3 4 5 6 7 8 9 10 答案 B、 D D； D D B D A B B B B、 C 三、 明 1、 （ 1） S 自反的 a A，由 R 自反， ( a, a R) ( a, a R) ， a, a S （ 2） S 稱的 a, b A

12、 a, b S ( a,c R) ( c,b R) S 定義 ( a, c R) ( c, b R) R 對稱 b, a S R 傳遞 （ 3） S 的 a, b, c A a, b S b, c S ( a, d R) ( d , b R) ( b, eR) ( e, c R) ( a, b R) ( b, c R) R 傳遞

13、 a, cS S 定義 由（ 1）、（ 2）、（3）得； S 是等價關(guān)系。 2、 明： P(x) ： x 是個舞蹈者； Q(x) ： x 很有 度； S(x) ：x 是個學生； 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

14、 ④ P(a) ①化 ⑤ Q( a). ③④假言推理 I ⑥ S( a) ①化 ⑦ S( a) Q(a) ⑤⑥合取 ⑧ x(S(x) Q (x) ⑦ EG ?? 11 分 ３、 明 ：b1 , b2 B ,(b1 b2 ) f 滿射 a1 , a2 A 使f ( a1 ) b1 , f (a2 ) b2 , 且 f (a1 ) f (a2 ), 由于 f是函數(shù) , a1 a2 又 g (b1 ) { x | (x A)

15、 ( f ( x) b1 )}, g(b2 ) { x | ( x A) ( f (x) b2 )} a1 g(b1 ), a2 g(b2 ) 但 a1 g(b2 ), a2 g(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é)點，這與圖論基

16、 本定理矛盾，因而 u， v 一定連通。 5、證明： 證 G中任何兩結(jié)點之和不小于 n。 反證法： 若存在兩結(jié)點 u，v 不相鄰且 d(u) d (v) n 1, 令 V1 {u, v} ，則 G-V1 是具 有 n-2 個 結(jié) 點 的 簡 單 圖 ， 它 的 邊 數(shù) m 1 (n 1)( n 2) 2 ( n 1) 2 , 可 得 m 1 (n 2)(n 3) 1 2 ，這與 1

17、1 G中 G=G-V 為 n-2 個結(jié)點為簡單圖的題設(shè)矛盾，因而 任何兩個相鄰的結(jié)點度數(shù)和不少于 n。 所以 G為 Hamilton 圖. 四、 計算 解：子群有 <{[0]},+ 6 >； <{[0],[3]},+ >；<{[0],[2],[4]},+ 6 >； <{Z },+ > 6 6 6 {[0]} 的左陪集： {[0]} ， {[1]} ； {[2]} ， {[3]} ； {[4]} ， {[5]} {[0] ， [3]} 的左陪集： {[0] ，[3]} ； {[1] ， [4]} ； {[2] ， [5]} {[0] ， [2] ， [4]} 的左陪集： {[0] ， [2] ， [4]} ；{[1] ， [3] ， [5]} Z 的左陪集： Z 。 6 6