《離散數(shù)學(xué)》考試題庫(kù)及答案

《離散數(shù)學(xué)》考試題庫(kù)及答案、填空20%（每小題2分）設(shè)A={xl（xeN）且（*5）},B={xlx￡E+且xv7}（N;自然數(shù)集，曰正偶數(shù)）則。 A,B,C表示三個(gè)集合，文圖中陰影部分的集合表達(dá)式為 設(shè)P,Q的真值為0,R,S的真值為1,則「（Pv（Qr（Ra「P）））T（Rv「S）的真值=公式成逐）3人&）八戶(hù)的主合取范式為 若解釋I的論域D僅包含一個(gè)元素，則在I下真值為 設(shè)A={1,2,3.4},A上關(guān)系圖為則R2= 設(shè)A=（a,b,c,d},其上偏序關(guān)系R的哈斯圖為 9.設(shè)A={a,b,c,d},A上二元運(yùn)算如下: 9.設(shè)A={a,b,c,d},A上二元運(yùn)算如下:那么代數(shù)系統(tǒng)VA,*＞的幺元是 ,有逆元的元素為 ,它們的逆元分別為 C10.下圖所示的偏序集中，是格的為 ，二、選擇20%（每小題2分）下列是頁(yè)命題的有（中￡｛｛中｝,中｝D.中￡｛｛中｝,中｝D.｛①隹｛｛中｝｝2、 下列集合中相等的有（ ）｛4,3｝^中；B.｛①，3,4｝；C.｛4,中，3,3｝；D.｛3,4｝。3、 設(shè)A=｛1,2,3｝,則A上的二元關(guān)系有（）個(gè)。A.23；B.32；C.23x3.d.32氣4、 設(shè)R,S是集合A上的關(guān)系，則下列說(shuō)法正確的是（ ）若R.S是自反的，則R°S是自反的；若R,S是反自反的，則R°S是反自反的；若R,S是對(duì)稱(chēng)的，則RoS是對(duì)稱(chēng)的；若R,S是傳遞的，則R°S是傳遞的。5、設(shè)A=｛1,2,3.4｝,P（A）（A的驀集）上規(guī)定二元系如下

R={<s,t>1s,tep(A)a(I51=1/1)則p(A)/r=( )A.A：B.P(A):C.({{!}},{{1,2}},{{1,2,3}},{{1,2,3.4}}}；D.({①},{2},{2,3},{{2,3,4}},{A}}06、設(shè)A={小，{lb(1,3},(1,2,3}}則A上包含關(guān)系“W”的哈斯圖為(7、下列函數(shù)是雙射的為（A.f:I^E,f(x)=2x；B.JN—NxN,7、下列函數(shù)是雙射的為（A.f:I^E,f(x)=2x；B.JN—NxN,f(n)=<n,n+l>:C.f:R_I,f(x)=[xl；D.f:LN,f(x)（注：I—整數(shù)集，E一偶數(shù)集，N—自然數(shù)集,R—（注：I—整數(shù)集，E一偶數(shù)集，N—自然數(shù)集,R—實(shí)數(shù)集））條。9、下圖中既不是Eular圖,也不是Hamilton圖的圖是（10、在一棵樹(shù)中有7片樹(shù)葉，3個(gè)3度結(jié)點(diǎn)，其余都是4度結(jié)點(diǎn)則該樹(shù)有（）個(gè)4度結(jié)點(diǎn)。A.1；B.2；C.3；D.4。三、證明26%

1、R是集合X上的一個(gè)自反關(guān)系，求證：R是對(duì)稱(chēng)和傳遞的，當(dāng)且僅當(dāng)<a,b>和va,c>在R中有v.b,c>在R中。(8分)2、 f和g都是群<G,,★>?!]<G,/>的同態(tài)映射，證明<C,★>是<。|,★>的一個(gè)子群。其中c」引'EG]且/'(x)=g(x)}(8分)3、 G=<V,E>(IVI=v,IEI=e)是每一個(gè)面至少由k(kA)條邊圍成的連通平面e<圖，則2-2)e<圖，則2-2)由此證明彼得森圖(Peterson)圖是非平面圖。(11分)四、 邏輯推演16%用CP規(guī)則證明下題(每小題8分)IAvB->CaD,QvEtF=A->F2、S(P(x)->。(同)nSP(x)tSQ⑴五、 計(jì)算18%1、設(shè)集合A={a,b,c.d}上的關(guān)系R={va,b>,vb,a>,vb,c>,vc,d>}用矩陣運(yùn)算求出R的傳遞閉包t(R)。 (9分)2、如下圖所示的賦權(quán)圖表示某七個(gè)城市七'％'…'、及預(yù)先算出它們之間的一些直接通信線(xiàn)路造價(jià)，試給出一個(gè)設(shè)計(jì)方案，使得各城市之間能夠通信而11總造價(jià)最小。 (9分)試卷一答案：一、填空20%(每小題2分)1、{0,1,2,試卷一答案：一、填空20%(每小題2分)1、{0,1,2,3,4,6}；2、(B?C)-A.3、1;4、(^vSv/?)a(->Pv-,Sv/?)；5^1；6^{<!,!>,<1,.3>,<2,2>,<2,4>}；7、{<a.b>,<a,c>,<a,d>,<b,d>,<c,d>}U匕；8、9、a:a,b,c,d:a,d,c,d:10、c;二、選擇20%（每小題2分）題目12345678910答案CDB、CCADCADBA三、證明26%1、證:Pa,b,ccX若<a,b>,<a,c>eR由R對(duì)稱(chēng)性知vb，a>,vc,a>eR,由r傳遞性得vb,c>cR“u”若va,b>gR<a,c>gR有<b,c>gR任意a,bcX,因va,a>eR若va,b>eR「.<b,a>eR所以r是對(duì)禰的。若va,b>cR<b,c>eR則vb,a>€R/\<b,c>€R/.<a,c>eR即R是傳遞的。2、證2、證f(b-i)=/-i(Z>),g(b-i)=g-i(b):.f(b-t)=f-i(b)=g-i(b)=g(b-i)???f(a★H)=/(?)*/-'(b)=g(o)*g(“)=gjb-i)??fb-EC..<(：,★>是vG],★>的子群。3、證:v-e+r=2故2e=^d（F）>rk rv-e+r=2故①設(shè)G有r個(gè)面，則 '，即*。而k即得k_2。（8分）②彼得森圖為*=5,e=15,v=10,這樣 k-2不成立,所以彼得森圖非平面圖o（3分）二、邏輯推演16%1、證明：①AP（附加前提）②代7BT?I③Av8->CaDP④C《DT@③］⑤。T?I?DvET@I⑦DvE—>FP⑧FT@?I⑨A->FCP2、證明①SP(x)P（附加前提）②％）US①③Vx(P(x)>Q(x))p④P(c)->Q(c)US③⑤。（OT?④］⑥S0x)UG⑤⑦VxP(x)->Va0(x)CP三、計(jì)算18%1、解：「0100、noio'10100101M=M=MM=R0001r2 H R0000<000oy<0000,

MR'=MR'oMR0)MR4=MMR'=MR'oMR0)MR4=MM/(/?)=MR+MR2111001000,?,-t(R)=(<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c.>,vb,d>,vc,d>}2、解：用庫(kù)斯克(Kruskal)算法求產(chǎn)生的最優(yōu)樹(shù)。算法略。結(jié)果如圖：樹(shù)權(quán)C(T)=23+1+4+9+3+17=57即為總造價(jià)。試卷二試題與答案一、填空20%（每小題2分）1、P：你努力，Q：你失敗?！俺悄闩Γ駝t你將失敗”的翻〉譯為 ;“雖然你努力了，但還是失敗了”的翻譯為2、論域D={1,2},指定謂詞PP(l.l)P(l,2)P(2,l)P(2,2)TTFF則公式S為p（y,x）真值為 02、設(shè)S={a〕，a?,…，a8）?B】是S的子集，則由B3］所表達(dá)的子果是3、設(shè)A={2,3,4,5,6}上的二元關(guān)系*={<*，、》工<"x是質(zhì)數(shù)},則R= （列舉法）。R的關(guān)系矩陣Mr= 5、設(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= 06、設(shè)代數(shù)系統(tǒng)vA,*>,其中A={a,b,c}.a a b cbbbc 則幺元是 ；是否有幕等c c c b 性 ；是否有對(duì)稱(chēng)性 ?7、 4階群必是 群或 群。8、 下而偏序格是分配格的是 o 10、公式v（「P△0）a（（「PvQ）△的根樹(shù)表示為 二、選擇20%（每小題2分）1、在下述公式中是重言式為（ ）a.（paQ）->（pvq）；b（p<-?e）o（（p^e）A（e->p））:C.TPtQ）/xQ；d.Pt（PwQ）。2、命題公式中極小項(xiàng)的個(gè)數(shù)為（ ），成真賦值的個(gè)數(shù)

B.1；C.2；D.3B.1；C.2；D.3。3、設(shè)S={6,{1},{1,2}},則2S有（）個(gè)元素。A.3：B.6；C.7；D.8。4、設(shè)S={1,2,3},定義SxS上的等價(jià)關(guān)系R=（?<,b>,vc,d>\<a,b>eSxS,vc,d>eSxS,a+d=b+c}則由r產(chǎn)生的SxS上一個(gè)劃分共有（ ）個(gè)分塊。A.4；B.5：C.6；D.9o5、設(shè)S={1,2,3},s上關(guān)系R的關(guān)系圖為歐拉圖9、在如下各圖中（歐拉圖9、在如下各圖中（則R具有（ ）性質(zhì)。A.自反性、對(duì)稱(chēng)性、傳遞性；B.反自反性、反對(duì)稱(chēng)性；C.反自反性、反對(duì)稱(chēng)性、傳遞性；D.自反性。6、設(shè)+，°為普通加法和乘法，則（）VS，+，?！凳怯?。AS={x1a:= ,a,bgQ}BS=(xlx=2〃，a,bgZ)CS={x\x=2n+\,ne.Z}DS=)xlxeZAX>0)=N。7、下面偏序集（ ）能構(gòu)成格。

設(shè)R是實(shí)數(shù)集合，“X”為普通乘法,則代數(shù)系統(tǒng)vR,x>是（設(shè)R是實(shí)數(shù)集合，“X”為普通乘法,則代數(shù)系統(tǒng)vR,x>是（A.群；B.獨(dú)異點(diǎn);C.半群。三、證明46%1、設(shè)R是A上一個(gè)二元關(guān)系，S={<a,b>1（a,bgA）a（對(duì)于某—個(gè)cg人，有va,c>eA且<c,b>eR）}試證明若R是A上一個(gè)等價(jià)關(guān)系，則S也是A上的一個(gè)等價(jià)關(guān)系。（9分）2、用邏輯推理證明：所有的舞蹈者都很有風(fēng)度，王華是個(gè)學(xué)生且是個(gè)舞蹈者。因此有些學(xué)生很有風(fēng)度。（11分）3、 若是從a到B的函數(shù)，定義一個(gè)函數(shù)對(duì)任意bwB有g(shù)（b）={x\（xeA）^（f（x）=b））t證明：若f是a到B的滿(mǎn)射，則g是從B到2A的單射。（10分）4、 若無(wú)向圖G中只有兩個(gè)奇數(shù)度結(jié)點(diǎn)，則這兩個(gè)結(jié)點(diǎn)一定連通。（8分）m=l（n-l）（/i-2）+25、 設(shè)G是具有n個(gè)結(jié)點(diǎn)的無(wú)向簡(jiǎn)單圖，其邊數(shù)2 ，則G是Hamilton圖（8分）四、計(jì)算14%1、 設(shè)<Z6,+6>是一個(gè)群，這里+6是模6加法，Z6=（[0],[1],[21，[3],[4],[5]},試求出<Z6，+6>的所有子群及其相應(yīng)左陪集。（7分）2、 權(quán)數(shù)1,4,9,16,25,36,49,64,81,100構(gòu)造一棵最優(yōu)二叉樹(shù)。（7分）試卷二答案：一、填空20%（每小題2分）1、「P*；P"2、T3、氣廣氣?昨={氣V七，％叩4、

R={<2,2>,v2,3>,v2,4>,<2,5>,<2,6>,v3,2>,v3,3>,v3,4>,v3,5>,<3,6>,<4,5>,<4,6>,<5,2>,<5,3>.<5.4>,<5,5>.<5,6>}:R={<1,1>,<2,2>,<3,3>}6、3>.<5.4>,<5,5>.<5,6>}:R={<1,1>,<2,2>,<3,3>}6、5、R={vl,2>,vl,3>,v2,l>}；a；否；有7、Klein四元群；循環(huán)群8、B9、二、三、???S二、三、???S定義???R對(duì)稱(chēng)?R傳遞選擇20%（每小題2分）題目12345678910答案B、DD；DDBDABBBB、C證明46%1、 (9分)S自反的X/aeAt由r自反，...(<o,o>eR)/\(<n,o>eR),:.<a,a>eSS對(duì)稱(chēng)的Pa,bcAa,b>eS=>(<a,c>eR)a(<c,b>eR)=>(<a,c>eR)a(<c,b>eR)=><b,a>eSS傳遞的Pa,b,c￡Aayb>gSa<b,c>eS=>(<a,d>gR)a(<d,b>gR)a(<b,e>gR)a(<e,c>gR)=>(<a,b>gR)a(<b,c>g/?) ???—傳遞nva,c>〈S ???，定義由(1)、(2)、(3)得：S是等價(jià)關(guān)系。2、 1］分證明：設(shè)P(x)：x是個(gè)舞蹈者；Q(x):x很有風(fēng)度；S(x)：x是個(gè)學(xué)生；a：王華上述句子符號(hào)化為：S(a)AP(a)結(jié)論：3x(S(x)Ag(x))前提：頃S(a)AP(a)結(jié)論：3x(S(x)Ag(x))S(a)aP(?)Vx(P(x)->。(對(duì))③P(a)->Q(a)US②④P⑴T?I⑤T③④］⑥S(。)T?I⑦S(a)a2(a)T@?I⑧3x(5(%)a0(x)EG@……11分3、 10分證明.邳2)/滿(mǎn)射?■-^a^a2EAW(氣)=?,f(a,)=b,,且了(氣)*y(氣)，由于/是函數(shù)，.?.％*七又g(q)={xI(xEA)a(/(x)=q)},g(b)={x\(xeA)/\(f(x)=b)}.?.%eg(b),aeg(b)但。/g(b),a任g(b)/.g(b)#g(b)由％b,任意性知，g為單射。4、 8分證明：設(shè)G中兩奇數(shù)度結(jié)點(diǎn)分別為u和v,若u,v不連通，則G至少有兩個(gè)連通分支G「G,,使得u和v分別屬于Q和G,,于是Q和G,中各含有1個(gè)奇數(shù)度結(jié)點(diǎn)，這與圖論基本定理矛盾，因而u,v一定連'通。5、8分證明：證G中任何兩結(jié)點(diǎn)之和不小于n0反證法：若存在兩結(jié)點(diǎn)u,v不相鄰且"(”)+d(u)K〃-1,令匕=｛外刃，則g-匕m2—(n-l)(n-2)+2-(w-1)是具有n-2個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖，它的邊數(shù)2 ，可得m>-5.(/1-2)(〃-3)+12 ,這與G=G-V,為n-2個(gè)結(jié)點(diǎn)為簡(jiǎn)單圖的題設(shè)矛盾，因而G中任何兩個(gè)相鄰的結(jié)點(diǎn)度數(shù)和不少于no所以G為Hamilton圖.四、計(jì)算14%d1、7分解：子群有<{[0]}.+6>；<{[0].[3]),+6>；<{[0]J2],[4]}.+6>；<{Z6},+6>{[0]}的左陪集：{[0]}.{[1]}；{[2]},{[3]}；([4]},([5]}{[0],[3]}的左陪集：([0],[3]}：([1],[4]}；([2],[5]}{[0]，[2]，[4]}的左陪集：{[0],[2],[41}；{[1],[3],[5]}Z6的左陪集：Z6。2、7分試卷三試題與答案一、填空20%(每空2分)1、 設(shè)f,g是自然數(shù)集N上的函數(shù)SeMf(x)=x+\yg(x)=2七則f飲同= . 2、 設(shè)A={a,b,c},A上二元關(guān)系R={<a,a>,<a,b>,<a,c>,<c,c>},貝Os(R)= o3、 A={1,2,3,4,5,6},A上二元關(guān)系丁=O"y是素?cái)?shù)},則用列舉法T= :T的關(guān)系圖為 T具有 性質(zhì)。4、 集合 A={{6,2},{2}} 的繇集2川= 。5、 P,Q真值為0:R,S真值為1。則明(Pa(/?vS))t((PvQ)/\(/?aS))的真值為 。6、 研T(P")vR)tR的主合取范式為 o 7、 設(shè)P(x)：x是素?cái)?shù)，E(x)：x是偶數(shù)，O(x)：x是奇數(shù)N(x,y)：x可以整數(shù)y。則謂詞wffS(P(x)->為(O(y)aN(y,x)))的自然語(yǔ)言是

8、謂詞h#VxVy(3z(P(x,z)AP(y,z))->BuQ(x,y,u))的前束范式為8、二、選擇二、選擇20%（每小題2分）下述命題公式中，是重言式的為（下述命題公式中，是重言式的為（A、(p/\0)T(pV0).B、(psq)XpTA、(p/\0)T(pV0).B、(psq)XpT0))人(0->p)).c、D、(PEp)sq2、c、D、(PEp)sq2、wff」（p△q）-‘的主析取范式中含極小項(xiàng)的個(gè)數(shù)為（4、5、A、2；B、3；C、5；給定推理①Vx(F(x)TGW)②F(y)->G(y)③*(x)④F（y）⑤G(y)⑥SG(x)4、5、A、2；B、3；C、5；給定推理①Vx(F(x)TGW)②F(y)->G(y)③*(x)④F（y）⑤G(y)⑥SG(x)D、0；E、8US①ES③T?④IUG?/.Vx（F（x）->G（x））=VxG（x）推理過(guò)程中錯(cuò)在（A、①-〉②；B、?->@;C、③-〉④；D、④-〉⑤；E、⑤-〉⑥設(shè)S『{I,2,…，8,9}.S2={2,4,6,8},S3={1,3,5.7,9},S『{3,4,5},S5={3,5},在條件X-Si且*下x與（ ）集合相等。A、X=S?或Ss;B、X=S‘或％C、X=srs2或S4；D、X與S],…，S[中任何集合都不等。設(shè)R和S是P上的關(guān)系，P是所有人的集合，R={vX,y>1X,y€Pa工是y的父親}S={<x,y>1a,ygPax是y的母親}A、B、R表示關(guān)系（ ）。{<x,y>1x,yePA尤是y的丈夫}.?{<x,y>1ePax是y的孫子或?qū)O女}.C、中?D、ePAX^y的祖父或祖母}。6、 下面函數(shù)( )是單射而非滿(mǎn)射。Af;RTR,f(x)=-x2+2x-\B、f：Z+tR,/(x)=lnx.c/:/?->Z,/Xx)=[x],[同表示不大于x的最大整數(shù).nf:RTR,f(x)=2x+i其中R為實(shí)數(shù)集，Z為整數(shù)集，R+,3分別表示正實(shí)數(shù)與正整數(shù)集。7、 設(shè)S={1,2,3},R為S上的關(guān)系，其關(guān)系圖為曲③則R具有( )的性質(zhì)。A、自反、對(duì)稱(chēng)、傳遞；B、什么性質(zhì)也沒(méi)有；C、反自反、反對(duì)稱(chēng)、傳遞；D、自反、對(duì)稱(chēng)、反對(duì)稱(chēng)、傳遞。8、設(shè)S={<D,{1},{1,2}},則有（）"A、{{1,2}}:B、{1,2}:C、⑴:D、{2}。9、設(shè)A={1,2,3},則A上有（)個(gè)二元關(guān)系。A、23；B、32；C、22,；d、2獎(jiǎng)。10、全體小項(xiàng)合取式為( )。A、可滿(mǎn)足式；B、矛盾式；C、永真式；D、A.B,C都有可能。三、 用CP規(guī)則證明16%(每小題8分)IAvB—>CaD,DvE—>F=>AF2、Vx(P(x)v0(x))=>VxP(x)v3x2(x)四、 (14%)集合X={vl,2>,v3,4>,<5,6>,…},R=(?x1,y1>,<x2,y2?lxJ+y2=x2+yt}=1、 證明R是X上的等價(jià)關(guān)系。(10分)2、 求出X關(guān)于R的商集o(4分)

五、(10%)設(shè)集合A=（a,b,c,d}上關(guān)系R={<a,b>,<b,a>,vb,c>,vc,d>}要求1、寫(xiě)出R的關(guān)系矩陣和關(guān)系圖。（4分）2、用矩陣運(yùn)算求出R的傳遞閉包。（6分）六、(20%)1、 （10分）設(shè)f和g是函數(shù)，證明/eg也是函數(shù)。2、 （10分）設(shè)函數(shù)g：SrT「TfS,證明「TTS有一左逆函數(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>,v3,1>,<5,1>,v4,2>,<6,2>,<6,3>}.4、反對(duì)稱(chēng)性、反自反性;4、仲，{{中，2}}，{{2}},{{中,2},{2}}}；5、1；6、（Pv2v/?）a（「PvQvR）/\（PvQv&）；7、任意x,如果x是素?cái)?shù)則存在一個(gè)y,y>奇數(shù)日y整除x:8、殂z）v「P（y,Z）vQ（x,y,“））.六、選擇20%（每小題2分）題目12345678910答案CCCCABDADC七、證明16%（每小題8分）①AP（附加前提）②A(yíng)v8T?I③AvB->CaDP④CaDT@③］⑤DT@I?DvET@I⑦E—>FP

T@⑦ICPVa-P(x)vBxQ(x)<=>TVx)P(x)->BxQ(x)

本題可證Vx(P(x)vQ(x))n->(VaP(x)t3xQ(x)TSP(x))3x(-iP(x))「P。)Vx(P(x)v0(x))P(a)vQ(a)"3xQ(x)TW(x)t3xQ{x)14%TSP(x))3x(-iP(x))「P。)Vx(P(x)v0(x))P(a)vQ(a)"3xQ(x)TW(x)t3xQ{x)14%證明：自反性：V<x，)'>cX,由^x+y=x+yP(附加前提)T?EES②US?T@?IEG?CP八、(1)1、?xty>i<x,y?GR-R自反對(duì)稱(chēng)性：?xty>i<x,y?GR-R自反對(duì)稱(chēng)性：▼<%，七,ex，x當(dāng)<<X,y>，<七，〉2>>eR時(shí)即*1+，2=”2+'1也即七+七=七+>故?x,y>,<x,y?eR???&有對(duì)稱(chēng)性2、傳遞性：V<x1'>\>eX'V<x2'>,2>eX X當(dāng)?x,y>,<x,V?gR且<<a:,V>,<x,y?gR時(shí)1 1 2 2 2 2 3 33、即％+%=%+*⑴x+y=x+y(2)2 3 3 2(1)+(2)x+y+x+y=x+y+x+y1 2 2 3 2 13即氣+%=%+*故<<x,y>,vx,y>>￡R???/?有傳遞性由(1)(2)(3)知：R是X上的先等價(jià)關(guān)系。2、X/R={[E2>]「九、九、10% a2、MR2=MMR1=MMR410000100oMoM=MoMR3RM/(?)=M+M關(guān)系圖012、MR2=MMR1=MMR410000100oMoM=MoMR3RM/(?)=M+M關(guān)系圖01000)100；010010000100100010001000+MR2R'R*=MR：=MR3W=MR6Ra110011001110((R)={<a,a>,va,b>,<a,c>,<a,d>,vb,a>,vb,b>,vb.c.>,vb.d>,vc.六、20%fr\g={<x,y>\xgdomfaxgdoingay=f(x)ay=g(x)}1、(1)={<x,y>1xgdoinfcdoingay=1、(1)々h=fcg:.domfcg=domh=|xIxedomfcdomg,f(x)=g(x))(2)"={<x，)'>1x￡domfcdomgay=h(x)=f(x)=g(x)}對(duì)xedomh若有七,七使得*=h(x)=f(x)=g(x),y2=h(x)=f(x)=g(x)由于/(或g)是函數(shù)，有)；=七即Scdomh有唯一y使得y=h(x).../eg也是函數(shù)2、證明：”新有一左逆g測(cè)對(duì)X/teTgof(t)=t故g。/是入射,所以/是入射"<^"f是入射，f：TTS定義如下：V5G/(r),由/入射，引衝")=S此時(shí)令g($)=￡,若建/(丁)令g(s)=cyr則對(duì)聽(tīng)gS,g(s)只有一個(gè)值t或c且若/*(，)=s貝Ug。f?)=g(s)=t,故g是/■的左逆元即精入射，必能構(gòu)造函您，使g為佐逆函數(shù)c試卷四試題與答案一、填空10%(每小題2分)1、2、若P,Q,1、2、若P,Q,為二命題，P*真值為0當(dāng)且僅當(dāng) 命題“對(duì)于任意給定的正實(shí)數(shù)，都存在比它大的實(shí)數(shù)”令F(x)：x為實(shí)數(shù),Ux,y):x>y則命題的邏輯謂為 3、謂詞合式公式SP(x)T3、謂詞合式公式SP(x)T女。(同的前束范式為 4、將量詞轄域中出現(xiàn)的 4、將量詞轄域中出現(xiàn)的 和指導(dǎo)變?cè)粨Q為另一變?cè)?hào)，公式其余的部分不變，這種方法稱(chēng)為換名規(guī)則。5、設(shè)x是謂詞合式公式A的一個(gè)客體變?cè)珹的論域?yàn)镈,A(x)關(guān)于y是自由的，則5、 被稱(chēng)為存在量詞消去規(guī)則，記為二、選擇25%(每小題2.5分)1、 下列語(yǔ)句是命題的有( )。A、明年中秋節(jié)的晚上是晴天； B、*+)'>°；C、當(dāng)且僅當(dāng)x和y都大于0；D、我正在說(shuō)謊。2、 下列各命題中真值為真的命題有( )。A、2+2=4當(dāng)且僅當(dāng)3是奇數(shù)；B、2+2=4當(dāng)且僅當(dāng)3不是奇數(shù)；C、2+2H4當(dāng)且僅當(dāng)3是奇數(shù)；D、2+2=4當(dāng)且僅當(dāng)3不是奇數(shù)；3、 下列符號(hào)串是合式公式的有()A、PoQ：B、PnP7Q；c、(「PvQ)a(PvP)；d、WQ)

4、卜.列等價(jià)式成立的有（)oA、PtQDiQt-hP：B、Pv(PaR)=R：4、卜.列等價(jià)式成立的有（)oA、PtQDiQt-hP：B、Pv(PaR)=R：C、P人（P*）OQ.D、P-*(Q—>R)<=>(PaQ)tR5、若午氣…土和B為wff,且AaAa-aA=>BM（A、稱(chēng)4人氣人…八，”為B的前件；B、稱(chēng)B為*泄2_A“的有效結(jié)論C、C、當(dāng)且僅當(dāng)^_aAA-AAziAfi?F當(dāng)且僅當(dāng)AaAa???aAa—\B<=>F6、A,6、A,B為二合式公式，且A=B,則（A、B、A、B、7、C、A=>B.D,A*E、為重言式。“人7、C、A=>B.D,A*E、為重言式?！叭丝偸且赖摹敝^詞公式表示為（)o（論域?yàn)槿倐€(gè)體域）M（x）：x（論域?yàn)槿倐€(gè)體域）M（x）：x是人：Mortal（x）：x是要死的。A、M(x)TA、M(x)TMortal(x).BM(x)aMortal(x)C、Vx(M(x)Mortal(x))D3x(M(x)aMortal(x))C、8、公式A=3x(PM->QM)的解釋i為：個(gè)體域D={2},P(x)：x>3,Q(x)：x=4則A的真值為（A、1B、0；C、可滿(mǎn)足式：D、無(wú)法判定。9、下列等價(jià)關(guān)系正確的是（A、Vx(P(x)vQ(x))=VaP(x)vVx0(x).B、3x(P(x)vQ(x))=BxP(x)vBxQ(x).C、Vx(P(x)TQ)u>VxP(x)->Q.D、3x(P(x)tQ)o3xP(x)->Q10、下列推理步驟錯(cuò)在（②F(y)rG(y)US①③女F（x）④F(y)ES③⑤G（y）T??I⑥女G（x）EG⑤A、②；B、?；C、?；D、⑥三、 邏輯判斷30%1、 用等值演算法和真值表法判斷公式A=（（PtQ）a（Q->P））0（P”。）的類(lèi)型。（10分）2、 下列問(wèn)題，若成立請(qǐng)證明，若不成立請(qǐng)舉出反例：（10分）（1） 已知AvC=8vC,問(wèn)A=B成立嗎？（2） 己知問(wèn)AoB成立嗎？3、 如果廠(chǎng)方拒絕增加工資，那么罷工就不會(huì)停止，除非罷工超過(guò)一年并且工廠(chǎng)撤換了

廠(chǎng)長(zhǎng)。問(wèn)：若廠(chǎng)方拒絕增加工資，面罷工剛開(kāi)始，罷工是否能夠停止。（10分）四、 計(jì)算10%1、 設(shè)命題氣，A?的真值為1,A3,A,真值為0,求命題（4v（氣T（Aay）））“（Avf）的真也（5分）2、 利用主析取范式，求公式」（PtQ）.Q.R的類(lèi)型。（5分）五、 謂詞邏輯推理15%符號(hào)化語(yǔ)句：“有些人喜歡所有的花，但是人們不喜歡雜草，那么花不是雜草并推證其結(jié)論。六、 證明：（10%）設(shè)論域D={a,b,c},求證：VxA(x)vXfxff(x)=>Vx(A(x)vB(x))設(shè)論域D={a,b,c},答案:十、填空10%十、填空10%（每小題2分）1、P真值為1，Q的真值為0;2、1、P真值為1，Q3xHP?v2（x））；&約束變?cè)?、mx4（x）=A（y）,y為d的某些元素。十一、選擇25%（每小題2.5分）題目12345678910答案A.CA.DC.DA,DB,C