《離散數(shù)學(xué)試題與答案》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)試題與答案（12頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、試卷二試題與參考答案一、填空1、 P：你努力， Q：你失敗。2、 “除非你努力，否則你將失敗”符號(hào)化為；“雖然你努力了，但還是失敗了”符號(hào)化為。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 上既不是對(duì)稱的又不是反對(duì)稱的關(guān)系R=；A 上既是對(duì)稱的又是反對(duì)稱的關(guān)系R=。5、設(shè)代數(shù)系統(tǒng) ，其中 A=a ， b，c,*abcaabcbbbccccb
2、則幺元是；是否有冪等性；是否有對(duì)稱性。6、 4 階群必是群或群。7、下面偏序格是分配格的是。8、 n 個(gè)結(jié)點(diǎn)的無(wú)向完全圖Kn 的邊數(shù)為，歐拉圖的充要條件是。二、選擇1、在下述公式中是重言式為（）A (P Q)(PQ) ； B ( PQ )( P Q) (QP) ；C (PQ)Q ； D P (P Q) 。2、命題公式(PQ )( Q P)中極小項(xiàng)的個(gè)數(shù)為（），成真賦值的個(gè)數(shù)為（）。A 0；B 1；C 2；D 3 。3、設(shè) S ,1,1,2 ，則2 S有（）個(gè)元素。A3； B 6； C 7； D 8 。4、設(shè) S 1,2, 3 ，定義 SS上的等價(jià)關(guān)系R a,b, c, d | a,bSS, c
3、, dS S, a d b c 則由 R產(chǎn) 生的 SS上一個(gè)劃分共有（）個(gè)分塊。A4； B 5； C 6； D 9 。5、設(shè) S 1, 2, 3 ， S 上關(guān)系 R 的關(guān)系圖為則 R 具有（）性質(zhì)。A自反性、對(duì)稱性、傳遞性；B反自反性、反對(duì)稱性；C反自反性、反對(duì)稱性、傳遞性；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 長(zhǎng)度為 3 的道路有（
4、）條。A1；B 2；C 3；D 4 。9、在如下各圖中（）歐拉圖。10、10、設(shè) R 是實(shí)數(shù)集合， “”為普通乘法，則代數(shù)系統(tǒng) 是（）。A群；B獨(dú)異點(diǎn)；C 半群。三、證明1、設(shè) R 是 A 上一個(gè)二元關(guān)系，Sa, b| (a,bA)(對(duì)于某一個(gè)cA, 有a,cR且c, bR)試證明若R是A 上一個(gè)等價(jià)關(guān)系，則S 也是A 上的一個(gè)等價(jià)關(guān)系。2、 用邏輯推理證明：所有的舞蹈者都很有風(fēng)度，王華是個(gè)學(xué)生且是個(gè)舞蹈者。因此有些學(xué)生很有風(fēng)度。3、若無(wú)向圖G中只有兩個(gè)奇數(shù)度結(jié)點(diǎn)，則這兩個(gè)結(jié)點(diǎn)一定連通。m1 ( n 1)(n 2)24、設(shè) G是具有 n 個(gè)結(jié)點(diǎn)的無(wú)向簡(jiǎn)單圖，其邊數(shù)2，則 G是 Hamilton
5、圖。四、計(jì)算1、設(shè) 是一個(gè)群，這里+6 是模 6 加法， Z6=0 ，1 ， 2 ， 3 ， 4 ， 5，試求出的所有子群及其相應(yīng)左陪集。2、權(quán)數(shù) 1， 4， 9， 16， 25， 36， 49， 64， 81， 100 構(gòu)造一棵最優(yōu)二叉樹(shù)。試卷二參考答案：一、 填空1、PQ ； P Q2、 T3、 R=,；11111111110001111111000004、 R=,；R=,5、 a ；否；有6、 Klein四元群；循環(huán)群7、 B1 n(n1)8、 2；圖中無(wú)奇度結(jié)點(diǎn)且連通二、選擇題目12345678910答案B、 DD； DDBDABBBB、 C三、 明1、（ 1）S 自反的a A，由 R
6、 自反，( a, aR)( a, aR) ，a, aS（ 2）S 稱的a, bAa, bS( a,cR)( c,bR)S 定義(a, cR) (c, bR)R 對(duì)稱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 是等價(jià)關(guān)系。2、 明： P(x) ： x 是個(gè)舞蹈者；Q(x)： x 很有 度；S(x) ：x 是個(gè)學(xué)生；a ：王 上述句子符號(hào)化 ：前提： x(P( x)Q( x) 、 S(a) P(a) ： x(S(x) Q (
7、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
8、 )g(b1 )g(b2 )由b1 , b2 任意性知 , g為單射 。4、證明：設(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、證明：證 G中任何兩結(jié)點(diǎn)之和不小于n。反證法： 若存在兩結(jié)點(diǎn)u，v 不相鄰且 d(u)d (v)n1, 令 V1 u, v ，則 G-V1 是具有 n-2 個(gè) 結(jié) 點(diǎn) 的 簡(jiǎn) 單 圖 ， 它 的 邊 數(shù)m 1 (n 1)( n 2) 2 ( n 1)2, 可 得m1 (n 2)(n 3)12，這與11G中G=G-V 為 n-2 個(gè)結(jié)點(diǎn)為簡(jiǎn)單圖的題設(shè)矛盾，因而任何兩個(gè)相鄰的結(jié)點(diǎn)度數(shù)和不少于n。所以 G為 Hamilton圖.四、計(jì)算解：子群有 ； ； 6660的左陪集： 0， 1 ； 2， 3； 4， 50， 3的左陪集： 0 ，3； 1 ， 4 ； 2， 50， 2， 4 的左陪集： 0， 2， 4；1 ， 3 ， 5Z 的左陪集： Z 。66
離散數(shù)學(xué)試題與答案
