離散數(shù)學(xué)習(xí)題集(十五套)

1、離散數(shù)學(xué)試題與答案試卷、填空20%(每小題2分)1. 設(shè)Ax|(xN)且(x5),Bx|xE且x7(N:自然數(shù)集，e+正偶數(shù))貝HAB。2. A,B,C表示三個集合，文圖中陰影部分的集合表達(dá)式為3. 設(shè)P,Q的真值為0,R,S的真值為1,貝U(P(Q(RP)(RS)的真值=4公式(PR)(SR)P的主合取范式為5.若解釋I的論域D僅包含一個元素，則XP(X)XP(X)在|下真值為6. 設(shè)A=1,2,3,4,A上關(guān)系圖為則R2=7. 設(shè)A=a,b,c,d，其上偏序關(guān)系R的哈斯圖為8.圖則R=的補(bǔ)圖為9.設(shè)A=a,b,c,d,A上二元運(yùn)算如下:abedaabedbbedaeedabddabe,它們

2、的那么代數(shù)系統(tǒng)<A,*>的幺元是,有逆元的元素為逆元分別為。10.下圖所示的偏序集中，是格的為、選擇20%（每小題2分）1、下列是真命題的有（)A.aa；B.，;C.，;D.。2、下列集合中相等的有（)A.4,3;B.,3,4;C.4,3,3;D.3,4。3、設(shè)A=1，2，3，貝UA上的二元關(guān)系有（）個。32c322A.23；B.32；C.2;D.3。4、設(shè)R,S是集合A上的關(guān)系，則下列說法正確的是（）A.若R,S是自反的，B.若R,S是反自反的,C.若R,S是對稱的，D.若R,S是傳遞的，則RS是自反的；則RS是反自反的;則RS是對稱的；則RS是傳遞的。5、設(shè)A=1,2,3,4,

3、P（A）（A的幕集）上規(guī)定二元系如下Rs,t|s,tp(A)(|s|t|則P(A)/R=()AA;B.P(A);C.1,1,2,1,2,3,1,2,3,4;”的哈斯圖為（D.,2,2,3,2,3,4,A6、設(shè)A=，1，1，3，1，2，3則A上包含關(guān)系“1.3ill1,3¥(d也*(CF列函數(shù)是雙射的為（C.f:IE,f(x)=2x；D.f:IN,f(n)=<n,n+1>N,f(x)f:RI,f（x）=x；（注：I整數(shù)集，E偶數(shù)集，N自然數(shù)集,=|x|。R實數(shù)集)）條。&圖中從V1到V3長度為3的通路有（3。A.0；B.9、下圖中既不是Eular圖，也不是Hamil

4、ton圖的圖是（）10、在一棵樹中有7片樹葉，3個3度結(jié)點，其余都是4度結(jié)點則該樹有（)個4度結(jié)點。A.1；B.2；C.3；D.4。三、證明26%1、R是集合X上的一個自反關(guān)系，求證：R是對稱和傳遞的，當(dāng)且僅當(dāng)a,b和a,c在R中有.b,c在R中。（8分）2、f和g都是群Gi,到G2,*的同態(tài)映射，證明C,是Gi,的一個子群。其中c=x|xG且f（x）g（x）（8分）3、G=V,E（|V|=v,|E|=e）是每一個面至少由k（k3）條邊圍成的連通平面ek（v2）e圖，貝Uk2,由此證明彼得森圖（Peterson）圖是非平面圖。（11分）四、邏輯推演16%用CP規(guī)則證明下題（每小題8分）1、CD

5、,DE2、x(P(x)Q(x)xP(x)xQ(x)五、計算18%1、設(shè)集合A=a,b,c,d上的關(guān)系R=<a,b>,<b,a>,<b,c>,<c,d>用矩陣運(yùn)算求出R的傳遞閉包t（R）。（9分）2、如下圖所示的賦權(quán)圖表示某七個城市v1,V2,v7及預(yù)先算出它們之間的一些直接通信線路造價，試給出一個設(shè)計方案，使得各城市之間能夠通信而且總造價最小。（9分）試卷一答案：一、填空20%（每小題2分）1、0,1,2,3,4,6;2、(BC)A；3、1；4、(PSR)(PSR)；5、1;6、<1,1>,<1,3>,<2,2>

6、;,<2,4>7、<a.b>,<a,c>,<a,d>,<b,d>,<c,d>9、a;a,b,c,d;a,d,c,d;10、c;、選擇20%(每小題2分)題目12345678910答案CDB、CCADCADBA三、證明26%1、證：a,b,cX若<a,b>,<a，c>R由R對稱性知<b,a>,<c,aR,由R傳遞性得<b,C>R若<a,b>R，<a,c>R有<b，c>R任意a，bX，因<a，a>R若<a，b>R&

7、lt;b，a>R所以R是對稱的。若<a,b>R<b,c>>R貝y<b,a>Rb,cR<a,c>R即R是傳遞的勺。2、證a,bC有f(a)g(a),f(b)g(b),又f(b1)f1(b),g(b1)g1(b)f(:b1)f1(b)g1(b)g(b1)f(ab1)f(a)*f1(b)g(a)*g(b1)g(ab1)ab1C<1C,>是<G1,>的子群。3、證：2erd(FJrk2er設(shè)Gi有r個面，則i1，即ko而ver2故2v2ek(v2)erveek即得k2o(I8分）k(ve2)彼得森圖為k5,e15,v1

8、0，這樣k2不成立,精品文檔所以彼得森圖非平面圖。（3分）邏輯推演16%1、證明:AP（附加前提）ABT1ABCDPCDT1DT1DET1DEFPFT1AFCP2、證明xP(x)P（附加前提）P(c)USx(P(x)Q(x)PP(c)Q(c)USQ(c)T1xQ(x)UGxP(x)xQ(x)CP三、計算18%1、解：0100101010100101MrMR2MrMrR0001R000000000000精品文檔MR3Mr2Mr0101101000000000Mr4Mr3MR1010010100000000111111110001Mt(R)MRMr2Mr3Mr4t(R)=<a,a>,&

9、lt;a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c.>,<b,d>,<c,d>2、解：用庫斯克(Kruskal)算法求產(chǎn)生的最優(yōu)樹。算法略。結(jié)果如圖：試卷二試題與答案、填空20%(每小題2分)1、P：你努力，Q：你失敗?！俺悄闩Γ駝t你將失敗”的翻譯為；“雖然你努力了，但還是失敗了”的翻譯為。2、論域D=1，2，指定謂詞PP(1,1)P(1,2)P(2,1)P(2,2)TTFF貝U公式xyP(y,x)真值為。2、設(shè)S=a1,a2,，a8,Bi是S的子集，則由B31所表達(dá)的子集是3

10、、設(shè)a=2,3,4,5,6上的二元關(guān)系Rx，y|xyx是質(zhì)數(shù)，則r=（列舉法）。R的關(guān)系矩陣Mr=5、設(shè)A=1,2,3,貝UA上既不是對稱的又不是反對稱的關(guān)系R=；A上既是對稱的又是反對稱的關(guān)系R=。6、設(shè)代數(shù)系統(tǒng)A，*，其中A=a，b，c.*abcaabcbbbc則幺元是;是否有冪等cccb性；是否有對稱性。7、4階群必是群或群。8下面偏序格是分配格的是。CA）（B）（C）9、n個結(jié)點的無向完全圖Kn的邊數(shù)為，歐拉圖的充要條件是10、公式（P（PQ）（PQ）R的根樹表示為、選擇20%（每小題2分）1、在下述公式中是重言式為（）A.(PQ)(PQ)；B.(PQ)(PQ)(QP)C.(PQ)Q；

11、D.P(PQ)。2、命題公式(PQ)(QP）中極小項的個數(shù)為（）,成真賦值的個數(shù)為（）。A.0;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,bc,d|a,bSS,c,dSS,adbc則由r產(chǎn)生的SS上一個劃分共有（）個分塊。B.5;C.6；5、設(shè)S1,2,3,S上關(guān)系則R具有（R的關(guān)系圖為A.自反性、對稱性、傳遞性;B反自反性、反對稱性;C.反自反性、反對稱性、傳遞性;D自反性。6、設(shè)為普通加法和乘法，則（S,是域。x|xQB.Sx|x2n,a,bZC.Sx|x2n1,nZx|xZx0=N。7、

12、ID)8、在如下的有向圖中，從V1到V4長度為3的道路有（）條。A.1;B.2;9、在如下各圖中（C.3;）歐拉圖。W同CD10設(shè)R是實數(shù)集合，“”為普通乘法，則代數(shù)系統(tǒng)R,x是（）。A.群；B.獨異點；C.半群。三、證明46%1、設(shè)R是A上一個二元關(guān)系，Sa,b|（a,bA）（對于某一個cA,有a,cR且c,bR）試證明若R是A上一個等價關(guān)系，則S也是A上的一個等價關(guān)系。（9分）2、用邏輯推理證明：所有的舞蹈者都很有風(fēng)度，王華是個學(xué)生且是個舞蹈者。因此有些學(xué)生很有風(fēng)度。（11分）A3、若f:AB是從a到B的函數(shù)，定義一個函數(shù)g:B2對任意bB有g(shù)（b）x|（xA）（f（x）b），證明：若f是

13、a到B的滿射，則g是從B到2A的單射。（10分）1"2(n1)(n2)1則G是Z6=0,1,2,3,4,5,4、若無向圖G中只有兩個奇數(shù)度結(jié)點，則這兩個結(jié)點一定連通。（8分）5、設(shè)G是具有n個結(jié)點的無向簡單圖，其邊數(shù)Hamilton圖（8分）四、計算14%1、設(shè)Z6,+6是一個群，這里+6是模6加法，試求出Z6,+6的所有子群及其相應(yīng)左陪集。（7分）2、權(quán)數(shù)1,4,9,16,25,36,49,64,81,100構(gòu)造一棵最優(yōu)二叉樹。(7分)試卷二答案:a4,a5,a6,a7,a84B00011111填空20%（每小題2分）】n(n1)111111111100011111113>,

14、<5,4>,<5,5>,<5,6>；000005、R=<1,2>,<1,3>,<2,1>；R=<1,1>,<2,2>,<3,3>6、a；否;有7、Klein四元群；循環(huán)群8、B9、1、PQ；PQ2、T3R=<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>

15、,<5,2>,<5,選擇20%（每小題2分）題目12345678910答案B、DD；DDBDABBBB、C證明46%1、（9分）（1）S自反的aA，由R自反，(a,aR)(a,aR），a,aS(2)S對稱的2、11分證明：設(shè)P（x）:x是個舞蹈者；Q（x）a,bAa,bS(a,cR)(c,bR)S定義(a,cR)(c,bR)R對稱b,aSR傳遞(3)S傳遞1的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)系。x很有風(fēng)度；S（x）:x是個學(xué)生；a：王華上述句子符號化

16、為:前提：x(P(x)Q(x)、S(a)P(a)結(jié)論:x(S(x)Q(x) S(a)P(a) x(P(x)Q(x) P(a)Q(a) P(a) Q(a). S(a) S(a)Q(a)x(S(x)Q(x)3、10分PPUSTITITITIEG證明：dbB,(db2)f滿射11分印月2A使fG)bnf©)b2,且f(ajf®),由于f是函數(shù)，aia?又g(R)x|(xA)(f(x)bi),g(b2)x|(xA)(f(x)b?)aig(bi),a?g(b?)但aig(b?),a?g(bi)g(bjg(b?)由bi,b?任意性知，g為單射。4、8分證明：設(shè)G中兩奇數(shù)度結(jié)點分別為u和

17、v,若u,v不連通，則G至少有兩個連通分支Gi、G2,使得u和v分別屬于Gi和G2，于是Gi和G2中各含有i個奇數(shù)度結(jié)點，這與圖論基本定理矛盾，因而u,v一定連通。5、8分證明：證G中任何兩結(jié)點之和不小于n。反證法：若存在兩結(jié)點u,v不相鄰且d(u)d(v)ni,令Viu，v，則g-Viim-(ni)(n2)2(ni)是具有n-2個結(jié)點的簡單圖，它的邊數(shù)2,可得1m-(n2)(n3)i2 ，這與Gi=G-Vi為n-2個結(jié)點為簡單圖的題設(shè)矛盾，因而G中任何兩個相鄰的結(jié)點度數(shù)和不少于n。所以G為Hamilton圖.四、計算i4%i、7分解：子群有<0,+6>；<0,3,+6>

18、;；<0,2,4,+6>；<Z6,+6>0的左陪集：0,i；2,3;4,50,3的左陪集：0,3;i,4;2,50,2,4的左陪集：0,2,4;i,3,5Z6的左陪集：Z6。2、7分試卷三試題與答案一、填空20%(每空2分)1、設(shè)f,g是自然數(shù)集N上的函數(shù)xN,f(x)x1,g(x)2x,則fg(x)。2、設(shè)A=a，b,c，A上二元關(guān)系R=<a,a>,<a,b>,<a,c>,<c,c>,貝ys(r)=。3、A=1,2,3,4,5,6,A上二元關(guān)系Tx，y|xy是素數(shù)，則用列舉法T的關(guān)系圖為T具有性質(zhì)。4、集2a=合A,2,

19、2的。幕集5、P,Q真值為0；R,S真值為1。則wff(P(RS)(PQ)(RS)的真值為。6、wff(PQ)R)R的主合取范式為。7、設(shè)P(x):x是素數(shù)，E(x):x是偶數(shù)，O(x):x是奇數(shù)N(x,y):x可以整數(shù)y。則謂詞wffx(P(x)y(O(y)N(y,x)的自然語言是8、謂詞wffxy(z(P(x,z)P(y,z)uQ(x,y,u)的前束范式為選擇20%(每小題2分)1、下述命題公式中，是重言式的為()。A、(Pq)(Pq)；b、(pq)(pq)(qp)c、(Pq)q-D、(pp)q。2、wff(pq)1的王析取范式中含極小壩的個數(shù)為()。A、2；B、3;C、5;D、0;E、8

20、。3、給定推理x(F(x)G(x)PF(y)(G(y)US xF(x)P F(y)ES G(y)TI xG(x)UGx(F(x)G(x)xG(x)推理過程中錯在()。A、->；B、->；C、->；D、->；E、->4、設(shè)S1=1,2,，8,9,S2=2,4,6,8,S3=1,3,5,7,9,S4=3,4,5,S5=3,5，在條件X3且XS3下x與()集合相等。A、X=S2或S5;B、X=S4或S5；C、X=S1,S2或S4；D、X與S1,，S5中任何集合都不等。5、設(shè)R和S是P上的關(guān)系，P是所有人的集合，Rx,y|x,yPx是y的父親Sx,y|x,yPx是y的母親

21、則S1R表示關(guān)系()。A、x,y|x,yPx是y的丈夫；B、x,y|x,yPx是y的孫子或?qū)O女；則R具有（）的性質(zhì)。A、自反、對稱、傳遞；B、什么性質(zhì)也沒有；C、反自反、反對稱、傳遞；D、自反、對稱、反對稱、傳遞。8、設(shè)S,1,1,2，則有（）S。A、1,2；B、1,2；C、；D、2。9、設(shè)A=1,2,3，則A上有（）個二元關(guān)系。2332A、23；B、32；C、2；D、2。10、全體小項合取式為（）。A、可滿足式；B、矛盾式；C、永真式；D、A，B，C都有可能。用CP規(guī)則證明16%（每小題8分）1、2、x(P(x)Q(x)xP(x)xQ(x)C、；D、x,y|x,yPx是y的祖父或祖母6、下面

22、函數(shù)（）是單射而非滿射。A、f：:R2R,f(x)x2x1；B、f:ZR,f(x)Inx.C、f:R乙f(x)X,X表示不大于X的最大整數(shù)D、f:RR,f(x)2x1o其中R為實數(shù)集，Z為整數(shù)集，R+,Z+分別表示正實數(shù)與正整數(shù)集。7、設(shè)S=1,2,3,R為S上的關(guān)系，其關(guān)系圖為四、（14%集合X=<1,2>,<3,4>,<5,6>,R=<<x1,y1>,<x2,y2»|x1+y2=X2+y1。1、證明R是X上的等價關(guān)系。（10分）2、求出X關(guān)于R的商集。（4分）五、（10%設(shè)集合A=a,b,c,d上關(guān)系R=<a,b&

23、gt;,<b,a>,<b,c>,<c,d>要求1、寫出R的關(guān)系矩陣和關(guān)系圖。（4分）2、用矩陣運(yùn)算求出R的傳遞閉包。（6分）六、（20%1、（10分）設(shè)f和g是函數(shù)，證明fg也是函數(shù)。2、（10分）設(shè)函數(shù)g:STf:TS，證明f:TS有一左逆函數(shù)當(dāng)且僅當(dāng)f是入射函數(shù)。答案：五、填空20%(每空2分）1、2(x+1)；2、a,a,a,b,a,c,c,c,b,a,c,a；3、2,1,3,1,5,1,4,2,6,2,6,34、/、?1反對稱性、反自反性；4、,2,2,2,2；5、1；6、（PQR)(PQR)(PQR）；7、任意x,如果x是素數(shù)則存在一個y,y是奇數(shù)

24、且y整除x；8、xyzu(P(xz)P(yz)Q(xy,u)o六、選擇20%（每小題2分）題目12345678910答案CCCCABDADC七、證明16%（每小題8分）1、AP（附加前提）ABT1ABCDPCDT1DT1DET1DEFPFTIAFCP2、xP（x）本題可證xQ(x)x(P(x)(x)P(x)xQ(x)Q(x)(xP(x)xQ(x)(xP(x)P（附加前提）x(P(x)P(a)ESx(P(x)Q(x)P(a)Q(a)USxQ(x)EG(xP(x)xQ(x)CP八、14%）證明：1、自反性：x,yX,由于xyxyx,y,X,yRR自反2、對稱性：X1,y1X,X2,y2X當(dāng)X1,%

25、,X2,y2R時即X1y2x2y1也即x2故x22,x1,y1RR有對稱性3、傳遞性：X1,yX,X2,y2XX3,y3當(dāng)x1,Y1,x2,y2R且X2,Y2,X3,Y3R時即%y2X2屮(1)X2y3X3y(2)(1)(2)X1y2X2yX2y1X3y2即x1y3X3y1故x1,y1,x3,y3RR有傳遞性Q（a）TI(1)XyiXiy由（1）（2）（3）知：R是X上的先等價關(guān)系。2、X/R=1,2r九、10%01001010mR00011、0000；10mr2MRMr02、00110mr3MR2mR00001001mR4MR3mR0000關(guān)系圖01010100000001100000100

26、100mr200mR511111111mR400010000<a,d>,<b,a>,'<b,Mt(R)MrMr2Mr3t(R)=<a,a>,<a,b>,<a,Mr3,Mr6Mr4>,<b,c.>,<b,d>,<c,六、20%fgx,y|xdomfxdomgyf(x)yg(x)1、（1）x,y|xdomfdomgyf(x)g(x)令hfgdomfgdomhx|xdomfdomg,f(x)g(x)（2）hx,y|xdomfdomgyh(x)f(x)g(x)對xdomh若有y1,y2使得yih(x

27、)f(x)g(x),y2h(x)f(x)g(x)由于f（或g）是函數(shù),有yiy即xdomh有唯一y使得yh（x）fg也是函數(shù)2、證明:""若f有一左逆g,則對tTgf(t)t故gf是入射,所以f是入射。""f是入射,f:TS定義如下：sf(T),由f入射,|tT,使f(t)s此時令g(s)t,若sf(T)令g(s)cT則對sS,g(s)只有一個值t或c且若f(t)s貝Ugf(t)g(s)t,故g是f的左逆元即若f入射,必能構(gòu)造函數(shù)g,使g為f左逆函數(shù)。試卷四試題與答案一、填空10%(每小題2分)1、若P,Q,為二命題，PQ真值為0當(dāng)且僅當(dāng)。2、命題“對于

28、任意給定的正實數(shù)，都存在比它大的實數(shù)”令F(x):x為實數(shù)，L(x,y):xy則命題的邏輯謂詞公式為。3、謂詞合式公式xP(x)xQ(x)的前束范式為。4、將量詞轄域中出現(xiàn)的和指導(dǎo)變元交換為另一變元符號，公式其余的部分不變，這種方法稱為換名規(guī)則。5、設(shè)x是謂詞合式公式A的一個客體變元，A的論域為D,A(x)關(guān)于y是自由的，貝U被稱為存在量詞消去規(guī)則，記為ESo選擇25%(每小題2.5分)1、下列語句是命題的有()oA、明年中秋節(jié)的晚上是晴天；B、xy0;C、xy0當(dāng)且僅當(dāng)x和y都大于0;D、我正在說謊。2、下列各命題中真值為真的命題有()oA、2+2=4當(dāng)且僅當(dāng)3是奇數(shù)；B、2+2=4當(dāng)且僅當(dāng)

29、3不是奇數(shù)；C、2+2豐4當(dāng)且僅當(dāng)3是奇數(shù)；D、2+2工4當(dāng)且僅當(dāng)3不是奇數(shù);精品文檔3、F列符號串是合式公式的有A1A2Q；c、(pQ)(PQ)；d、(PQ)°A、PQQP；B、P(PR)R；C、P(PQ)Q；d、P(QR)(PQ)R°5、若Ai,A2An和B為wff，且A1A2AnB則()°A、稱A1AAn為B的前件；B、稱B為A1,A2An的有效結(jié)論C、當(dāng)且僅當(dāng)A1A2AnBFD、當(dāng)且僅F列等價式成立的有（）。4、AnO當(dāng)6、A，B為二合式公式，且A、AB為重言式;7、C、“人總是要死的”謂詞公式表示為（論域為全總個體域）M（x）:x是人;Mortal(x)

30、：E、AB為重言式。x是要死的。A、M(x)Mortal(x)；B、M(x)Mortal(x)x(M(x)Mortal(x)；d、x(M(x)Mortal(x)8、公式Ax(P(x)Q（x）的解釋I為：個體域的真值為（A、1；B、0；C、可滿足式;D、無法判定。9、下列等價關(guān)系正確的是()°A、x(P(x)Q(x)xP(x)xQ(x)；B、x(P(x)Q(x)xP(x)xQ(x).C、x(P(x)Q)xP(x)Q.D、x(P(x)Q)xP(x)Q010、下列推理步驟錯在（)°x(F(x)G(x)PF(y)G(y)USxF(x)PC、D=2,P(x):x>3,Q(x):

31、x=4貝UAG(y)TIxG（x）egA、；B、；C、；D、三、邏輯判斷30%1、用等值演算法和真值表法判斷公式A（PQ）（QP）（PQ）的類型。（10分）2、下列問題，若成立請證明，若不成立請舉出反例：（10分）（1）已知ACBC，問AB成立嗎？（2）已知AB，問AB成立嗎？3、如果廠方拒絕增加工資，那么罷工就不會停止，除非罷工超過一年并且工廠撤換了廠長。問：若廠方拒絕增加工資，面罷工剛開始，罷工是否能夠停止。（10分）四、計算10%1、設(shè)命題A1，A2的真值為1，A3，A4真值為0，求命題（A1（A2（A3A1）（A2A4）的真值。（5分）2、利用主析取范式，求公式（PQ）QR的類型。（5

32、分）五、謂詞邏輯推理15%符號化語句：“有些人喜歡所有的花，但是人們不喜歡雜草，那么花不是雜草”。并推證其結(jié)論。六、證明：（10%）設(shè)論域D=a,b,c,求證：xA(x)xB(x)x(A(x)B(x)。答案：十、填空10%（每小題2分）1、P真值為1，Q的真值為0；2、x(F(x)L(x,0)y(F(y)L(y,x)；3、x（P（x）Q（x）；4、約束變元；5、xA(x)A(y)，y為D的某些元素。選擇25%（每小題2.5分）題目12345678910答案A,CA,DC,DA,DB,CA,B,C,D,ECAB(4)十二、邏輯判斷30%1、(1)等值演算法A(PQ)(QP)(PQ)(PQ)(PQ

33、)T(2)真值表法PQPQQP(PQ)(QP)PQA1111111100100101100010011111所以A為重言式。2、(1)不成立。若取CT則ATTBTT有ACBCT但A與B不一定等價，可為任意不等價的公式。(2)成立。證明：AB充要條件ABTT(AB)(BA)(AB)(BA)即：(BA)(AB)(AB)(BA)AB所以ABT故AB。3、解：設(shè)P：廠方拒絕增加工資；Q:罷工停止；R罷工超壺過一年；R:撤換廠長前提：P(RS)Q),P,R結(jié)論：QP(RS)Q)PPP(RS)QT1RPRST1四、計算10%(1(100)(11)(1(10)1(1)解：(10)1111(PQ)QR(PQ)

34、(QR)(2)(PQ)(QR)PQQRFQ罷工不會停止是有效結(jié)論。TI它無成真賦值，所以為矛盾式。五、謂詞邏輯推理15%解：M(x):x是人；F(x):x是花;G(x):x是雜草；H(x,y):x喜歡yy(G(y)H(x,y)x(M(x)y(F(y)H(x,y)x(M(x)x(F(x)G(x)證明：x(M(x)y(F(y)H(x,y)pM(a)y(F(y)H(a,y)ESM(a)tIy(F(y)H(a,y)tIx(M(x)y(G(y)H(x,y)pM(a)y(G(y)H(a,y)USy(G(y)H(a,y)tIy(H(a,y)G(y)TEF(z)H(a,z)usH(a,z)G(z)us(11)

35、 F(z)G(z)TI(12) x(F(x)G(x)UG1十三、證明10%精品文檔xA(x)xB(x)(A(a)A(b)A(c)(B(a)B(b)B(c)(A(a)B(a)(A(a)B(b)(A(a)B(c)(A(b)B(a)(A(b)B(b)(A(b)B(c)(A(c)B(a)(A(c)B(b)(A(c)B(c)(A(a)B(a)(A(b)B(b)(A(c)B(c)x(A(x)B(x)試卷五試題與答案、填空15%（每空3分）1、設(shè)G為9階無向圖，每個結(jié)點度數(shù)不是5就是6,則G中至少有個5度結(jié)點。4、設(shè)R，+，是代數(shù)系統(tǒng)，如果R，+是交換群R，是半群條。則稱R,+,為環(huán)。5、設(shè)L，是代數(shù)系統(tǒng)，

36、則L,滿足幕等律，即對aL有、選擇15%（每小題3分）1、下面四組數(shù)能構(gòu)成無向簡單圖的度數(shù)列的有（）。A、(2,2,2,2,2);C、(1,1,2,2,2);B、(1,1,2,2,3);D、(0,1,3,3,3)。2、下圖中是哈密頓圖的為（）。CAB3、如果一個有向圖D是強(qiáng)連通圖，則D是歐拉圖，這個命題的真值為（）A、真;B、假。4、下列偏序集（）能構(gòu)成格。5、11,2冋tqD),2,3,3,4,4*為普通乘法，則S，*是（）。A、代數(shù)系統(tǒng)；B、半群；C、群；D、都不是。三、證明48%1、（10%）在至少有2個人的人群中，至少有2個人，他們有相同的朋友數(shù)。2、（8%）若圖G中恰有兩個奇數(shù)度頂點

37、，則這兩個頂點是連通的。3、（8%）證明在6個結(jié)點12條邊的連通平面簡單圖中，每個面的面數(shù)都是3。4、（10%）證明循環(huán)群的同態(tài)像必是循環(huán)群。5、（12%）設(shè)B,0，1是布爾代數(shù)，定義運(yùn)算*為a*b（ab）（ab），求證B，*是阿貝爾群。四、計算22%1、在二叉樹中1）求帶權(quán)為2，3，5，7，8的最優(yōu)二叉樹T。（5分）2）求T對應(yīng)的二元前綴碼。（5分）2、下圖所示帶權(quán)圖中最優(yōu)投遞路線并求出投遞路線長度（郵局在D點）。答案:、填空（15%每空3分1、6;2、n;3、2;4、+對分配且對+分配均成立；5、選擇(15%)每小題3分題目12345答案A,BB,DBCD三、證明(48%)1、(10分)證

38、明：用n個頂點V1,，Vn表示n個人，構(gòu)成頂點集V=V1,，Vn，設(shè)Euv|u,vV,且u,v是朋友(uV)，無向圖G=(V,E)現(xiàn)證G中至少有兩個結(jié)點度數(shù)相同。事實上，(1)若G中孤立點個數(shù)大于等于2,結(jié)論成立。(2)若G中有一個孤立點，貝UG中的至少有3個頂點，既不考慮孤立點。設(shè)G中每個結(jié)點度數(shù)均大于等于1,又因為G為簡單圖，所以每個頂點度數(shù)都小于等于n-1,由于G中n頂點其度數(shù)取值只能是1,2,，n-1，由鴿巢原理，必然至少有兩個結(jié)點度數(shù)是相同的。2、(8分)證：設(shè)G中兩個奇數(shù)度結(jié)點分別為u,V。若u,V不連通則至少有兩個連通分支G1、G2，使得u,V分別屬于G1和G2。于是G1與G2中

39、各含有一個奇數(shù)度結(jié)點，與握手定理矛盾。因而u,V必連通。3 (8分)證：n=6,m=12歐拉公式n-m+f=2知f=2-n+m=2-6-12=8由圖論基本定理知：deg(F)2m24，而deg(Fj)3，所以必有deg(Fj)3，即每個面用3條邊圍成。4 (10分)證：設(shè)循環(huán)群A,的生成元為a,同態(tài)映射為f，同態(tài)像為f(A),*，于是nmnmnm、a,aA都有f(aa)f(a)*f(a)對n=1有f(a)f(a)22n=2,有f(a)f(aa)f(a)*f(a)(f(a)若n=k-1時有f(a)(f(a)對n=k時，f(ak)f(ak1a)f(ak1)*f(a)(f(a)k1*f(a)(f(a

40、)k這表明，f(A)中每一個元素均可表示為(f(a)"，所以f(A),*為f(a)生成的循環(huán)群。5、證:(1) 交換律：a,bB有a*b(ab)(ab)(ba)(ba)b*a(2) 結(jié)合律：a,b,cB有(a*b)*c(ab)(ab)*c(ab)(ab)c)(ab)(ab)c(abcabc)(Gab)(ab)cabcabc(aaabbabb)cabcabcbacabcabcabcabcabc而：a*(b)*c；)a*(bc)(bc)(a(bc)(bc)(a(b)(bc)a(bc)(bc)abcabcabcabcabcabc(a*b)*ca*(b*c)(3) 幺：aB有a*0(a0)(

41、a0)a0a0*a(0a)(0a)0aa0是B,幺元。(4) 逆：aBa*a(aa)(aa)000a是a的逆元。綜上所述：B,*是阿貝爾群。四、計算(22%)1、(10分)(1)(5分)由Huffman方法，得最佳二叉樹為：(2)(5分)最佳前綴碼為：000,001，01，10，11道路長度為:2、(12分)圖中奇數(shù)點為E、F，d(E)=3,d(F)=3,d(E,F)=28p=EGF復(fù)制道路EG、GF，得圖G，則G是歐拉圖。由D開始找一條歐拉回路：DEGFGEBACBDCFD。35+8+20+20+8+40+30+50+19+6+12+10+23=281試卷六試題與答案填空15%（每小題3分）

42、1、n階完全圖結(jié)點v的度數(shù)d（v）=。2、設(shè)n階圖G中有m條邊，每個結(jié)點的度數(shù)不是k的是k+1，若G中有Nk個k度頂點，Nk+1個k+1度頂點，則Nk=。3、算式（a（b*c）*d）（e*f）的二叉樹表示為4、如圖5、給出格L,組學(xué)生，臂力的大小，O則幺元、選擇15%（每小題3分）1、設(shè)S=0,1,2,3,w為小于等于關(guān)系，則S,<是（A、群；B、環(huán)；C、域；D、格。則零元為（）。A、a;B、b;C、c;2、設(shè)a,b,c,*為代數(shù)系統(tǒng)，*運(yùn)算如下：*abcaabcbbacccccD、沒有。3、如右圖相對于完全圖K5的補(bǔ)圖為（）。DJBCD4、一棵無向樹T有7片樹葉，3個3度頂點，其余頂點

43、均為4度。則T有（）4度結(jié)點。A、1;B、2；C、3；D、4。5、設(shè)A,+,是代數(shù)系統(tǒng)，其中+,為普通加法和乘法，則A=（）時，A,+,是整環(huán)。A、x|x2n,nz;B、x|x2n1,nZ；C、x|x0，且xZ;D、x|xabV5,a,bR。三、證明50%2nm一1、設(shè)G是（n,m）簡單二部圖，則4。（10分）1m-（n1）（n2）2、設(shè)G為具有n個結(jié)點的簡單圖，且2，貝VG是連通圖。（10分）3、記“開”為1,“關(guān)”為0,反映電路規(guī)律的代數(shù)系統(tǒng)0,1,+,的加法運(yùn)算和乘法運(yùn)算。如下：F-0*.1JL20-000丄丄丄證明它是一個環(huán)，并且是一個域。（14分）4、L，,是一代數(shù)格，“W”為自然偏序，則L,<是偏序格。（16分）精品文檔四、10%設(shè)E(Xi,X2,X3)(XiX2)(X2X3)(X2X3