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

1、試卷二試題與參考答案填空1、P:你努力，Q:你失敗。2、“除非你努力，否則你將失敗”符號化為;“雖然你努力了，但還是失敗了”符號化為2、論域D=1，2，指定謂詞PP(1,1)P(1,2)P(2,1)P(2,2)TTFF貝U公式xyP（y,x）真值為。3設(shè)A=2,3,4,5,6上的二元關(guān)系Rx,y|xyX是質(zhì)數(shù)，則R=（列舉法）。R的關(guān)系矩陣MR=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、下面偏序格是分配格

2、的是。CA)的（C）、選擇1、在下述公式中是重言式為（）A(PQ)(PQ);B.(PQ)(PQ)(QP）;C.(PQ)Q.D.P(PQ)。2、命題公式(PQ)(QP)中極小項的個數(shù)為（）,成真賦值的個數(shù)為（）。A0;B.1|;C.2;D.3。3、設(shè)S，1，1,2，則2s有（）個元素。A.3;B.6;C.7;D.8。4、設(shè)S1,2,3,定義SS上的等價關(guān)系Ra,b,c,dIa,bSS,c,dSS,adbc則由R產(chǎn)生的SS上一個劃分共有（）個分塊。A.4;5、設(shè)S1,2,3,S上關(guān)系則R具有（R的關(guān)系圖為BA.自反性、對稱性、傳遞性;反自反性、反對稱性;6、設(shè)-為普通加法和乘法，則（)S,是域。A

3、.Sx|xab3a,bQB.Sx|x2n,a,bZC.Sx|x2n1,nZd.Sx|xZx0=N7、下面偏序集（）能構(gòu)成格。C.反自反性、反對稱性、傳遞性;.自反性。DO8、在如下的有向圖中，從Vi到V4長度為3的道路有(【D)條。A.1;B.4。)歐拉圖。IDa是（)?！睘槠胀ǔ朔?，則代數(shù)系統(tǒng)10、10、設(shè)R是實數(shù)集合,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、用邏輯推理證明：所有的舞蹈者都很有風度，王華是個學生且是個舞蹈者。因此有些學生很有風度

4、。3、若無向圖G中只有兩個奇數(shù)度結(jié)點，則這兩個結(jié)點一定連通。1m(n1)(n2)24、設(shè)G是具有n個結(jié)點的無向簡單圖，其邊數(shù)2，則G是Hamilton圖。四、計算1設(shè)以,+6是一個群，這里+6是模6加法，Z6=0,1，,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；PQ2、T3、R=,；11111111110001111111000004、R=,；R=,5、a;否；有6、Klein四元群；循環(huán)群、選擇7、B題目12345678910答案B、DD;DDBDABBBB、C】n

5、(n1)8、2;圖中無奇度結(jié)點且連通三、證明1、(1)S自反的aA，由R自反，(a,aR)(a,aR)，a,a(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、證明：設(shè)P(x)：x是個舞蹈者；Q(x):x很有風度；S(x):x是個學生；a:王華上述句子符號化為：前提：x(P(x)Q(x)、 S(a)P(a) x(P(x)Q(x) P(a)Q(a) P(a) Q(a

6、). S(a) S(a)Q(a) x(S(x)Q(x)S(a)P(a)結(jié)論:前提引入前提引入US化簡假言推理I化簡合取EGx(S(x)Q(x)3分11分3、證明R,b2B,gb2)f滿射ai,a2使f(3!)d,f(a2)b2,且f(ajf),由于f是函數(shù),又g(bjx|(xA)(f(x)bj,g2)x|(xA)(f(x)b?)aig(bj,a?gd)但a!g(b2),a?g(bjg(bjg(b2)由bi,b2任意性知，g為單射。4、證明：設(shè)G中兩奇數(shù)度結(jié)點分別為u和v，若u,v不連通，則G至少有兩個連通分支G、G,使得u和v分別屬于G和G,于是G和Ga中各含有1個奇數(shù)度結(jié)點，這與圖論基本定理矛盾，因而u,v一定連通。5、證明：證G中任何兩結(jié)點之和不小于n。反證法：若存在兩結(jié)點u,v不相鄰且d(u)d(v)n1,令Mu，v，則g-v是具1m-(n1)(n2)2(n1)有n-2個結(jié)點的簡單圖，它的邊數(shù)2,可得1m-(n2)(n3)12，這與G=G-V1為n-2個結(jié)點為簡單圖的題設(shè)矛盾，因而G中任何兩個相