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

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è)人=2 , 3, 4, 5, 6上的二元關(guān)系R x,y |x y x是質(zhì)數(shù),則R= （列舉法）。R的關(guān)系矩陣Mr=4、設(shè)A=1 , 2 , 3,則A上既不是對(duì)稱(chēng)的又不是反對(duì)稱(chēng)的關(guān)系 R= ; A 上既是對(duì)稱(chēng)的又是反對(duì)稱(chēng)的關(guān)系R= 。5、設(shè)代數(shù)系統(tǒng)<A, *> ,其中A=a , b, c,*a

2、bcaabcbbbccccb則幺元是 ;是否有哥等性 ;是否有對(duì)稱(chēng)性 6、4階群必是 群或 群。7、下面偏序格是分配格的是 。8、n個(gè)結(jié)點(diǎn)的無(wú)向完全圖 Kn的邊數(shù)為 ,歐拉圖的充要條件是、選擇1、在下述公式中是重言式為（A. (p q)(P Q)：B.(PQ) (P Q) (QP)；C.(pQ)Q.D.(P Q)。2、命題公式Q)P)中極小項(xiàng)的個(gè)數(shù)為（）,成真賦值的個(gè)數(shù)A. 0;B. 1;C.2；D. 3 。3、設(shè) S ，1，1，2,則2s）個(gè)元素。A. 3;B. 6;C. 7;D. 8 。4、設(shè)S -2,3，定義S S上的等價(jià)關(guān)系R a,b,c,d | a,bS S, c,d S S, a

3、d b c則由 R 產(chǎn)生的S S上一個(gè)劃分共有（）個(gè)分塊。A. 4;B. 5; C.6；D. 9 。5、設(shè) S 1，2,3 , S上關(guān)系則R具有（R的關(guān)系圖為A.自反性、對(duì)稱(chēng)性、傳遞性；C.反自反性、反對(duì)稱(chēng)性、傳遞性;B.反自反性、反對(duì)稱(chēng)性;D.自反性。)s,， 是域。B S x|x 2n, a,b ZD S x|x Z x 0 = N3的道路有（）條。6、設(shè) ，為普通加法和乘法，則(A S x|x a bJ3, a,b QC S x| x 2n 1, n Z8、在如下的有向圖中，從 Vi到V4長(zhǎng)度為10、A.群；B.獨(dú)異點(diǎn)；C.半群三、證明 1、設(shè)R是A上一個(gè)二元關(guān)系，S a,b |（a,b

4、 A）（對(duì)于某一個(gè) c A,有 a,cR且 c,b R）試證明若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)一定連通。1m (n 1)(n 2) 24、設(shè)G是具有n個(gè)結(jié)點(diǎn)的無(wú)向簡(jiǎn)單圖，其邊數(shù) 2，則G是Hamilton 圖。四、計(jì)算1、設(shè) <Z6,+6> 是一個(gè)群，這里+6 是卞莫 6 加法,Z6=0 , 1 , 2, 3 , 4，,試求出 <Z6,+6> 的所有子群及其相應(yīng)左陪集。2、權(quán)數(shù) 1, 4, 9, 16, 25,

5、 36, 49, 64, 81, 100 構(gòu)造一棵最優(yōu)二叉樹(shù)。試卷二參考答案：一、填空1P Q ； 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>11111111110 0 0 11111110 0 0 0 04、R=

6、<1,2>,<1,3>,<2,1> ; R=<1,1>,<2,2>,<3,3>5、a ;否；有6、Klein四元群；循環(huán)群7、 B1n(n 1)8、2;圖中無(wú)奇度結(jié)點(diǎn)且連通、選擇題目12345678910答案B、DD; DDBDABBBB、C三、證明1、(1) S自反的a A,由R自反，(2) S對(duì)稱(chēng)的a, b Aa, b S ( a,c (a,cb, a(a, a R) ( a, aR) ( c,b R)R) ( c,b R)SR), a, a SS定義R對(duì)稱(chēng)R傳遞(3) S傳遞的2、a, b, c Aa,bSb,cS(

7、a,dR)(d,b(a,bR)(b,ca, c SR)(R)b,e R) ( e,cR傳遞S定義R)由(1)、(2)、(3)得；S是等價(jià)關(guān)系。證明：設(shè)P(x)： x是個(gè)舞蹈者；Q(x) : x很有風(fēng)度；S(x)： x是個(gè)學(xué)生;上述句子符號(hào)化為：a：王華前提：x(P(x) Q(x)、 S(a) P(a) x(P(x) Q(x) P(a) Q(a) P Q(a). S(a) S(a) Q(a) x(S(x) Q(x)3、證明：bi,b2 B,(b1b2)S(a) P(a)結(jié)論：x(S(x) Q(x)前提引入前提引入U(xiǎn)S化簡(jiǎn)假言推理I化簡(jiǎn)合取EG11分f滿射ana2 A使 f(aj bi,f(a2)

8、b2,且f (ai)“a?),由于f是函數(shù)，a1a2又 g(bi) x|(x A) (f(x) b gM) x|(x A) (f(x) bz) ai g(bj a2 g(b2) 但 a g(b2), a2 g(bi)g(b1) gQ)由Wb任意Tt知，g為單射。4、證明：設(shè)G中兩奇數(shù)度結(jié)點(diǎn)分別為 u和v,若u, v不連通，則G至少有兩個(gè)連通分支 Gi、G2 ,使得u和v分別屬于Gi和G2,于是Gi和G2中各含有1個(gè)奇數(shù)度結(jié)點(diǎn)，這與圖 論基本定理矛盾，因而 u, v一定連通。5、證明：證G中任何兩結(jié)點(diǎn)之和不小于 n。反證法：若存在兩結(jié)點(diǎn)u, v不相鄰且d(u) d(v) n 1,令Vi u，v,則G-Vi是1m (n i)(n 2) 2 (n i)具有n-2個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖，它的邊數(shù) 2，可得1m (n 2)(n 3) 12,這與Gi=G-Vi為n-2個(gè)結(jié)點(diǎn)為簡(jiǎn)單圖的題設(shè)矛盾，因而 G中任何兩個(gè)相鄰的結(jié)點(diǎn)度數(shù)和不少于n。所以G為Hamilton圖.四、計(jì)算解：子群有 <0,+ 6>； <0,3,+ 6>