離散數(shù)學(xué)試卷及答案1

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

一、填空20%(每小題2分)

1.設(shè)A={%|(xeN)K(x<5)},B={X\XG<7}(N:自然數(shù)集，E卡正偶

數(shù))則Au3=o

2.A,B,C表示三個(gè)集合，文圖中陰影部分的集合表達(dá)式為

3.設(shè)P,Q的真值為0,R,S的真值為1,則

TPv(。—>(R人—>P)))—>(Rv—>5)的真值=

4.公式(P人R)v(SAR)v「尸的主合取范式為

5.若解釋I的論域D僅包含一個(gè)元素，則*P(x)fVxP(x)在i下真值為

6.設(shè)A={1,2,3,4},A上關(guān)系圖為

則R2=

7.設(shè)人=伯，b,c,d},其上偏序關(guān)系R的哈斯圖為

則R=

9.設(shè)A={a,b,c,d),A上二元運(yùn)算如下:

*abcd

aabcd

bbcda

ccdab

ddabc

那么代數(shù)系統(tǒng)＜A,*＞的幺元是,有逆元的元素為,它們的

逆元分別為o

10.下圖所示的偏序集中，是格的為。

二、選擇20%（每小題2分）

1、下列是真命題的有（）

A.⑷二乂*；B.{{①}}€{①，［①}}；

C.①e{{回&}；D.{6}《{{①}}。

2、下列集合中相等的有（）

A.{4,3}D①；B.{①，3,4}；C.{4,①，3,3}；D.{3,4}。

3、設(shè)人={1,2,3},則A上的二元關(guān)系有（）個(gè)。

323x32x2

A.2；B.3；C.2；D.3o

4、設(shè)R,S是集合A上的關(guān)系，則下列說(shuō)法正確的是（）

A.若R,S是自反的，則RoS是自反的；

B.若R,S是反自反的，則火。5是反自反的；

C.若R,S是對(duì)稱的，則尺。5是對(duì)稱的；

D.若R,S是傳遞的，則。5是傳遞的。

5、設(shè)人={1,2,3,4),P(A)(A的暮集)上規(guī)定二元系如下

R={<s">|s,/ep(A)A(|s|=|U}則p(人)/R=()

A.A；B.P(A)；C.{{{1}},{{1,2}},{{1,2,3}},{{1,2,3,4}})；

D.{{①},{2},{2,3}，{{2,3,4}},{A}}

6、設(shè)人={①，{1},{1,3},{1,2,3}}則A上包含關(guān)系“三”的哈斯圖為()

<{1,2,3}

<{1,3}

<{1}

'①

(C)(DJ

7、下列函數(shù)是雙射的為（）

A.f:I->E,f（x）=2x；B.f:N—NxN,f（n）=<n,n+l>；

C.f:R->1,f（x）=[x]；D.f:IfN,f（x）=|x|o

（注：I一整數(shù)集，E—偶數(shù)集，N一自然數(shù)集，R—實(shí)數(shù)集）

8、圖中從vi到V3長(zhǎng)度為3的通路有（）條。

9、卜?圖中既不是Eular圖，也不是Hamilton圖的圖是（)

(DJ

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.4o

三、證明26%

1、R是集合X上的一個(gè)自反關(guān)系，求證：R是對(duì)稱和傳遞的，當(dāng)且僅當(dāng)

<a,b>和<a,c>在R中有v.b,c>在R中。(8分)

2、f和g都是群招|,外>到<62,*>的同態(tài)映射，證明<C,★>是<6|,*>的-個(gè)子

群。其中c={x|xeG］月/(x)=g(x)}一分)

3、G=<V,E>(|V|=v,|E|=e)是每一個(gè)面至少由k(k>3)條邊圍成的連通平面

eV-

圖，則k-2,由此證明彼得森圖(Peterson)圖是非平面圖。(11分)

四、邏輯推演16%

用CP規(guī)則證明下題(每小題8分)

［、AVB^CAD,￡>v￡—>F=>A—

2、Vx(P(x)-Q(x))nVxP(x)-VxQ(x)

五、計(jì)算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)圖表示某七個(gè)城市匕，匕，…，匕及預(yù)先算出它們之間的一些直接通

信線路造價(jià)，試給出?個(gè)設(shè)計(jì)方案，使得各城市之間能夠通信而且總造價(jià)最小。(9分)

試卷一答案：

一、填空20%（每小題2分）

1、｛0,1,2,3,4,6｝；2、（8十C）一A；3、1；4,vSv/?）A（-,Pv-.Sv7?）.

5、1；6、｛<1,1>,<1,3>,<2,2>,<2,4>｝；7、｛<a.b>,<a,c>,<a,d>,<b,d>,<c,d>｝UIA；8、

a

e

c

9、a；a,b,c,d；a,d,c,d10、c;

二、選擇20%（每小題2分）

題目12345678910

答案CDB、CCADCADBA

三、證明26%

1、證：

“n"V。,"CGX若<a,b>,<a,c>eR由R對(duì)稱性知

<b,a>,<c,a>eR,由R傳遞性得<b,c>eR

若<a,b>￡R,<a,c>￡R有<b,c>￡R任意a.beX因

<a,a>eR若<a,b>eR,<b,a>eR所以R是對(duì)稱的。

若va,b>wR,<b,c>GR則<b,a>GRA<b,c>GR<a,c>eR

即R是傳遞的。

2、證,有/(a)=g(a),/(fe)=g(fe),又

f(b~l)=f~\b),g")=g")；.f(b-')=f-'(b)=g-'(b)=g(L)

；?/(a★A")=/(a)*/t3)=g(q)*g(b-i)=g(a★)

：.ai^b~xeC:.<C,★>是<61,*>的子群。

3、證：

2e=V>rkr<—

①設(shè)G有r個(gè)面，則i=i，即左。而u-e+〃=2故

C/2e/左。一2)

2=v-6?+r<v-e+—e<-------

攵即得k-2。(8分)

②彼得森圖為k=5，e=15,v=10,這樣k-2不成立,

所以彼得森圖非平面圖。（3分）

二、邏輯推演16%

1、證明：

①AP（附加前提）

②Av3T①I

③AvS—P

(4)CA￡>T②③I

⑤。T?I

@DvET⑤I

⑦Ov￡3FP

⑧尸T⑥⑦I

⑨A->FCP

、證明

①VxP(x)P（附加前提）

②尸(c)US①

③Vx(P(x)->Q(x))p

④P(c)fQ(c)US③

⑤。(c)T②④I

⑥VxQ(x)UG⑤

⑦VxP(x)->VxQ(x)CP

三、計(jì)算18%

1、解:

'0100、'1010'

10100101

MR=M=MoM=

K0001Rn~2RpRp0000

、0000,、0000,

'0101、

1010

M,—M,°M

KRR0000

、0000>

q010'

0101

MR"=MR,°MR

0000

、0000>

111n

1111

M“R)=MR+MR2+MR?+"R?

0001

1k000Oj

/.t(R)={<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c.>,

<b,d>,<c,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：你失敗。“除非你努力，否則你將失敗”的翻譯為

；“雖然你努力了，但還是失敗了”的翻譯為

________________________O

2、論域D={1,2},指定謂詞P

P(l,l)P(l,2)P(2,l)P(2,2)

TTFF

則公式真值為。

2、設(shè)S={a］，a2,…，a&},Bj是S的子集，則由B31所表達(dá)的子集是

3、設(shè)A={2,3,4,5,6}上的二元關(guān)系A(chǔ)={<X，y〉|x<yvx是質(zhì)數(shù)},則R=

__________________________________________________（列舉法）。

R的關(guān)系矩陣MR=

5、設(shè)A={1,2,3},則A上既不是對(duì)稱的又不是反對(duì)稱的關(guān)系

R=;A上既是對(duì)稱的又是反對(duì)稱的關(guān)系

R=0

6、設(shè)代數(shù)系統(tǒng)<A,*>,其中A={a,b,c）,

*abc

aabc

bbbc則幺元是；是否有幕等

cccb性；是否有對(duì)稱性。

7、4階群必是群或群。

8、下面偏序格是分配格的是。

10、公式（PV（「PAQ））A（（「PV°）A「R的根樹(shù)表示為

二、選擇20%（每小題2分）

1、在下述公式中是重言式為（）

A.（尸入Q）->（Pv。）；B.（P?2）C（（P->0）A（Q->P））；

c.TPfQ）A0；d.Pf（PvQ）。

2、命題公式（［PQ）f（「。v尸）中極小項(xiàng)的個(gè)數(shù)為（）,成真賦值的個(gè)數(shù)

為（）。

A.0；B.1；C.2；D.3o

3、設(shè)5=仲，{1}，{1，2}},則2,有（）個(gè)元素。

A.3；B.6；C.7；D.8o

4、設(shè)$="，2,3},定義SxS上的等價(jià)關(guān)系

R={?a.b>,<c.d>\<a.b〉ESxS,vc,dSxS,a+d=。+c}則由R產(chǎn)生

的SxS上一個(gè)劃分共有（）個(gè)分塊。

A.4；B.5；C.6；D.9o

5、設(shè)5={1,2,3},S上關(guān)系R的關(guān)系圖為

23A

則R具有（）性質(zhì)。

A.自反性、對(duì)稱性、傳遞性；B.反自反性、反對(duì)稱性；

C.反自反性、反對(duì)稱性、傳遞性；D.自反性。

6、設(shè)+，°為普通加法和乘法，則（）＜5,+,。＞是域。

A.S={x|x=a+by/3,a,beQ}B.S={x\x=2n,a.beZ}

〃。

C.S={x|x=2+1,neZ}D.5={X|XGZAX>0)=N

7、下面偏序集（）能構(gòu)成格。

設(shè)R是實(shí)數(shù)集合，“x”為普通乘法，則代數(shù)系統(tǒng)＜R,x＞是（）。

A.群；B.獨(dú)異點(diǎn)；C.半群。

三、證明46%

1、設(shè)R是A上一個(gè)二元關(guān)系，

S={<a,b>|（a,beA）A（對(duì)于某一個(gè)cwA,有<a,c>e尺且<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、若/：Af8是從A到B的函數(shù)，定義一個(gè)函數(shù)g：8-2'對(duì)任意有

g屹）="|（xeA）人（/（x）=3},證明：若f是A到B的滿射,則g是從B到2A

的單射。（10分）

4、若無(wú)向圖G中只有兩個(gè)奇數(shù)度結(jié)點(diǎn)，則這兩個(gè)結(jié)點(diǎn)一定連通。（8分）

m=—（n-l）（n-2）+2

5、設(shè)G是具有n個(gè)結(jié)點(diǎn)的無(wú)向簡(jiǎn)單圖，其邊數(shù)2，則G是

Hamilton圖（8分）

四、計(jì)算14%

1、設(shè)VZ6,+6是一個(gè)群,這里+6是模6加法,Z6={[0],[1],[2],[3],[4],[5]},

試求出<Z"+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->Q-P人0,2、T3、831=綜001nu=4、

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,

Jill

1111

0001

11111

3>,<5,4>,<5,5>,<5,6>}；、00005、R={<1,2>,<1,3>,<2,1>};

R={<1,1>,<2,2>,<3,3>}6、a；否；有7、Klein四元群；循環(huán)群8、B9、

2；圖中無(wú)奇度結(jié)點(diǎn)且連通10、

fPQ->PQ

二、選擇20%（每小題2分）

題目12345678910

答案B、DD；DDBDABBBB、C

三、證明46%

1、(9分)

(1)S自反的

VaeA,由R自反，，(<R)八(<a,a>wR),:.<a,a>GS

(2)S對(duì)稱的

Pa,bGA

<a,b>GS=>(<a,c>eR)A(<c,h>GR)?.?S定義

=>(<a,c>G/?)A(<c,b>€R)…R對(duì)稱

=><b.a>GS???/?傳遞

(3)S傳遞的

VQ,仇cGA

<a.b>GSA<b,c>GS

=>(<〃,/>e/?)A(<d,b>G7?)A(<b.e>G/?)A(<e,c>GR)

n(<a,b>G/?)A(<h.c>eR)…R傳遞

a.c>G5???S定義

由(1)、(2)、(3)得；S是等價(jià)關(guān)系。

2、11分

證明：設(shè)P(x)：x是個(gè)舞蹈者；Q(x)：x很有風(fēng)度；S(x)：x是個(gè)學(xué)生；a：王華

上述句子符號(hào)化為：

前提：Vx(P(x)fQ(x))、S(〃)AP(〃)結(jié)論：3X(S(X)A(2(X))……3分

①S(a)AP(a)P

②Vx(P(x)f。*))P

③P(a)->Q(a)US②

④P（。）T①I

⑤。5).T③④I

⑥S(a)T①I

⑦S(“)AQ(。)T⑤⑥I

⑧A(S(x)人。(x)EG⑦……11分

3,10分

證明：V仇e8,(伍*:/滿射.e.Hat,a2eA

使〃%)=仇，/(。2)=%，且/(/)。/(。2)，由于Z是函數(shù)，

又g(4)="I(xeA)八(/(x)=/?,)},g(%)={x[(xeA)八(/(x)=&2)}

/eg(伉),geg(%)但％史8(一),。2-(4)，g@”g@2)

由仇,與任意性知，g為單射。

4、8分

證明：設(shè)G中兩奇數(shù)度結(jié)點(diǎn)分別為u和v,若u,v不連通，則G至少有兩個(gè)連

通分支G|、G2,使得u和v分別屬于G|和G?,于是GI和G2中各含有1個(gè)奇數(shù)度結(jié)

點(diǎn)，這與圖論基本定理矛盾，因而U,V一定連通。

5、8分

證明：證G中任何兩結(jié)點(diǎn)之和不小于no

反證法：若存在兩結(jié)點(diǎn)u,v不相鄰且d(")+d3)?〃T,令匕={〃#},則GM

,1

m>-(n-1)(/7-2)+2-(/1-1)

是具有n-2個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖，它的邊數(shù)2，可得

m>一(〃-2)(/7—3)+1

2,這與G『G-V|為n-2個(gè)結(jié)點(diǎn)為簡(jiǎn)單圖的題設(shè)矛盾，因而G

中任何兩個(gè)相鄰的結(jié)點(diǎn)度數(shù)和不少于n?

所以G為Hamilton圖.

四、計(jì)算14%

1、7分

解:子群有<{[0]},+6>;<{[0],[3]},+6>；<{[0],[2],[4]},+6>；<{Z6},+6>

{[0]}的左陪集：{[0]},{[1]};{[2]},{[3]}；{[4]},{[5]}

{[0]，[3]}的左陪集：{[0],[3]}；{[1],[4]}；{[2],[5]}

{[0]，[2],[4]}的左陪集：{[0],[2],[4]}；{[1],[3],[5]}

Z6的左陪集：Z6o

2、7分

8

試卷三試題與答案

一、填空20%(每空2分)

1、設(shè)f,g是自然數(shù)集N上的函數(shù)VxeN，f(x)=x+l,g(x)=2x,

則f°gW=。

2、設(shè)A={a,b,c},A上二元關(guān)系R={va,a>,va,b>,va,c>,vc,c>},

貝ijs(R)=o

3、A={1,2,3,4,5,6},A上二元關(guān)系7={<X。>1x+y是素?cái)?shù)},則用列舉

法

T=；

T的關(guān)系圖為

T具有性質(zhì)。

4、集合A={?,2},{2}}的幕集

2A=。

5、P,Q真值為0；R,S真值為1。則昉'(尸A(RvS))->((尸v。)A(HAS))的

真值為o

6、昉T(PAQ)VR)-R的主合取范式

為。

7、設(shè)P(x)：x是素?cái)?shù)，E(x)：x是偶數(shù),0(x)：x是奇數(shù)N(x,y)：x可以整數(shù)y。

則謂詞wffVx(P(x)t3y(0(y)AN(y,x)))的自然語(yǔ)言是

8、謂詞MfVxVy(土(P(x,z)AP(y,z))f3uQ(x,y,w))的前束范式為

二、選擇20%(每小題2分)

1、下述命題公式中，是重言式的為()。

A、(P八q)*pvq)；B、(p?q)c((p->q))7q-p))；

c、TPfq)八q；D、(「人可)64。

2、wff「(PA4)的主析取范式中含極小項(xiàng)的個(gè)數(shù)為()。

A、2；B、3；C、5；D、0；E、8。

3、給定推理

①Vx(尸(x)->G(x))p

②F(y)-G(y)us①

③女尸(x)p

④F(y)ES③

⑤G(y)T②④I

⑥VxG(x)uG⑤

Vx(F(x)->G(x))nVxG(x)

推理過(guò)程中錯(cuò)在()o

A、①->②；B、②->③；C、③->④；D、④->⑤；E、⑤->⑥

4、設(shè)S產(chǎn){1,2,8,9},S2={2,4,6,8},S3={1,3,5,7,9},S4={3,4,5},

S5={3.5},在條件X=5］且X邑下X與()集合相等。

A、X=S2或S5；B、X=S4或S5；

C、X=Si，S2或S4;D、X與S|,…，S5中任何集合都不等。

5、設(shè)R和S是P上的關(guān)系，P是所有人的集合，

/?={<x,y>|x,yeP△x是y的父親},S={<x,y>|x,yeP△x是y的母親}

則Si。??表示關(guān)系()。

A、{<〉|wPAX是y的丈夫}:

B、{<x,y〉|x,yePAx是y的孫子或?qū)O女}.

C、①；口、{<苫,丁>|尤,丁€2人工是)，的祖父或祖母}。

6、下面函數(shù)()是單射而非滿射。

A、f：RtR,/(x)=-x?+2x-1；

B、/：Z+->R,/(x)=lnx；

C、f：RTZ,/(x)=[x],[x]表示不大于x的最大整數(shù)；

D、f：RtR,/(x)=2x+l。

其中R為實(shí)數(shù)集，Z為整數(shù)集，R+,Z+分別表示正實(shí)數(shù)與正整數(shù)集。

7、設(shè)$={1,2,3},R為S上的關(guān)系，其關(guān)系圖為

0)

?④

則R具有()的性質(zhì)。

A、自反、對(duì)稱、傳遞；B、什么性質(zhì)也沒(méi)有；

C、反自反、反對(duì)稱、傳遞；D、自反、對(duì)稱、反對(duì)稱、傳遞。

8、設(shè)5={。{1},{1,2}},則有()=5。

A、{{1,2}}；B、{1,2}；C、{1}；D、{2}o

9、設(shè)A={1,2,3},則A上有()個(gè)二元關(guān)系。

3223

A、2；B.3；C、2'；D、2"0

10、全體小項(xiàng)合取式為()?

A、可滿足式；B、矛盾式；C、永真式；D、A,B,C都有可能。

三、用CP規(guī)則證明16%(每小題8分)

]、AvB—>CA￡),￡>VE—>F=>hfF

2、Vx(P(x)vQ(x))=>VxP(x)v3xQ[x}

四、(14%)

集合X={〈1,2>,<3,4>,v5,6>,…},R={?xi,y1>,<x2,y2?|xi+y2=x2+yi}。

1、證明R是X上的等價(jià)關(guān)系。（10分）

2、求出X關(guān)于R的商集。（4分）

五、（10%）

設(shè)集合A={a,b,c,d}上關(guān)系R={<a,b>,<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ù)，證明/Cg也是函數(shù)。

2、（10分）設(shè)函數(shù)g：STTf盯tS,證明f：T-S有一左逆函數(shù)當(dāng)且僅當(dāng)f是

入射函數(shù)。

答案：

五、填空20%（每空2分）

1、2（x+l）；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,3>}.

反對(duì)稱性、反自反性；4、{①，{{①2}},{{2}},{{①,2},{2}}}；5、1；

6、（PV「QVR）A（「PV0VR）/\（PV0VR）；7、任意x,如果x是素?cái)?shù)則

存在一個(gè)y,y是奇數(shù)且y整除x；8、VxVyVz3M(^P(x,z)v^P(y,z)vQ(x,y,u))o

六、選擇20%(每小題2分)

題目12345678910

答案CCCCABDADC

七、證明16%（每小題8分）

1,

①AP（附加前提）

②Av3T①I

③AvB—>。八。P

④CA。T②③I

⑤oT@I

⑥OvET⑤I

⑦DYEfFP

⑧/T⑥⑦I

⑨ATFCP

2、

?/VxP(x)vBxQ(x)o-i(Vx)尸(x)->3xQ(x)

本題可證Vx(P(x)vQ(x))=「(VxP(x)^xQ(x)

①-<vxp（x））P（附加前提）

②玉（-1P（尤））T①E

③->P(a)ES②

④Vx(P(x)vQ(x))P

⑤P(a)vQ(a)US④

⑥。（。）T③⑤I

⑦*Q(x)EG@

⑧」(VxP(x)->*Q(x)CP

八、14%

(1)證明：

1、自反性：V<x,y>eX,由于x+y=x+y

?x,y>,<x,y?eR???7?自反

2、對(duì)稱性：V<X|，H>eX，\/<*2,為〉eX

當(dāng)?修，%>,<x2,y2?eR時(shí)即再+y2=它+M也即/+%=匹+當(dāng)

故<<%2，%>，</，%>>eR…R有對(duì)稱性

v<x>eX

3、傳遞性：i^i,V<x2,y2>eX\/<x3,y3>eX

當(dāng)<<x”yi>,<x2,y2?e7?fi?x2,y2>,<x3,y3>>eR時(shí)

即［為+>2=工2+必(1)

La+%=無(wú)3+%(2)

(1)+(2)xt+y2+x2+y3=x2+y}+x3+y2

即Xl+X=無(wú)3+月

故<<演,必〉,<》3，>3>>€R???/?有傳遞性

由(1)(2)(3)知：R是X上的先等價(jià)關(guān)系。

2、X/R={[<1，2>]?}

九、10%

,0100、

1010

MR

000i

1、000關(guān)系圖

1010、

0101

M產(chǎn)=MR。MR

0000

2、、0000,

'0101、

1010

MR3=MR2°MR

0000

、0000>

q010、

0101

MR*=MR、°MRMR,

0000

、0000>MRS=M?,MR6=MR4,

111n

1111

M,(R)=MR+M產(chǎn)+M+M

RiRi0001

000

t(R)={<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c.>,<b,d>,<c,

d>}<)

六、20%

fryg={<x,y>\xedomfAxGdomg/\y=f(x)/\y=g(x)}

1、(1)={<x,y>\xedomfcdomg/\y=/(x)=g(x)}

令h=/cg

domfcg=domh={x\xEdomfcdomg,/(x)=g(x)}

(2)h={<x,y>\xedomfndomgAy=〃(x)=f(x)=g(x)}

對(duì)xedomh若有y,為使得

Ji=〃(x)=/(x)=g(x),y2=h(x)=f(x)=g(x)

由于/'(或g)是函數(shù)，有％=y2即Vxedomh有唯一7使得y=h[x)

：.feg也是函數(shù)。

2、證明：

"n"荀有一左峋，則對(duì)VreTgo/(r)=r

故g。/是入射，所以/是入射。

"<="/是入射，/:TfS定義如下：

Vse/(T),由/入射，與feT，W(f)=s

此時(shí)令g(s)=f，若s《/(T)令g(s)=cwT

則對(duì)WseS,g(s)只有一-個(gè)值t或c且茍⑺=s

則go/(，)=g(s)=f,故g尉的左逆元

即若/入射，必能構(gòu)造函數(shù)?，使g為/左逆函數(shù)。

試卷四試題與答案

一、填空10%（每小題2分）

1、若P,Q,為二命題,P-0真值為0當(dāng)且僅當(dāng)o

2、命題“對(duì)于任意給定的正實(shí)數(shù)，都存在比它大的實(shí)數(shù)”令F（x）：x為實(shí)數(shù)，

L（x,y）:x>y則命題的邏輯謂詞公式

為。

3、謂詞合式公式VxP（x）fAQ（x）的前束范式

為o

4、將量詞轄域中出現(xiàn)的和指導(dǎo)變?cè)粨Q為另一變?cè)?hào)，公式其余

的部分不變，這種方法稱為換名規(guī)則。

5、設(shè)x是謂詞合式公式A的一個(gè)客體變?cè)?，A的論域?yàn)镈,A（x）關(guān)于y是自由的，則

_______________________________________被稱為存在量詞消去規(guī)則，記為

ES,

二、選擇25%（每小題2.5分）

1、下列語(yǔ)句是命題的有（）。

A、明年中秋節(jié)的晚上是晴天；B、x+y〉°；

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+2r4當(dāng)且僅當(dāng)3是奇數(shù)；D、2+2關(guān)4當(dāng)且僅當(dāng)3不是奇數(shù)；

3、下列符號(hào)串是合式公式的有（）

A、PoQ；B、c、（「PvQ'ZPv-1。）；D、「（P―'Q）。

4、下列等價(jià)式成立的有（）。

A、B、pV（P八R）CR；

C、PA（P-Q）oQ：D、Pf（QfR）=（P人Q）fR。

5、若4,4…4,和B為wflf,且4人4△…AA”=>8貝()?

A、稱4人42人…AA”為B的前件；B、稱B為4，&…A”的有效結(jié)論

C、當(dāng)且僅當(dāng)A|AA2/V-A4“A8OE；口、當(dāng)且僅當(dāng)

AA4八…AA〃A—\B<=>F

6、A,B為二合式公式，且AO8,則()。

A、為重言式；B、A'=>B'.

C、4=8；D、A*o";E、A—8為重言式。

7、“人總是要死的”謂詞公式表示為()。

(論域?yàn)槿倐€(gè)體域)M(x)：x是人;Mortal(x)：x是要死的。

A、M(x)Mortal(x).gM(x)AMortal{x}

QVx(A/(x)—?Mortally),D、3X(M(X)AMortal(x))

8、公式A=mx(P(x)—>Q(x))的解釋i為：個(gè)體域D={2},P(x)：x>3,Q(x)：x=4則A

的真值為()。

A、1；B、0；C、可滿足式；D、無(wú)法判定。

9、下列等價(jià)關(guān)系正確的是()。

A、Vx(P(x)v<2(x))oVxP(x)vVxQ(x).

B、3x(P(x)v(2(x))3xP(x)vBxQ(x).

C、Vx(P(x)fQ)oVxP(x)fQ；

D、Bx(P(x)->0)<=>3xP(x)->Qo

10、下列推理步驟錯(cuò)在()。

①Vx(T(x)->G(x))p

②R(y)->G(y)us①

③★產(chǎn)(x)p

④*y)ES③

⑤G(y)T②④1

⑥HxG(x)EG⑤

A、②；B、④：C、⑤：D、?

三、邏輯判斷30%

1、用等值演算法和真值表法判斷公式A=((「-。)人(。-P))?(P?0)的類

型。(10分)

2、下列問(wèn)題，若成立請(qǐng)證明，若不成立請(qǐng)舉出反例：(10分)

(1)已知4\/。08"。，問(wèn)408成立嗎？

(2)已知「40」8,問(wèn)403成立嗎？

3、如果廠方拒絕增加工資，那么罷工就不會(huì)停止，除非罷工超過(guò)一年并且工廠撤換了

廠長(zhǎng)。問(wèn)：若廠方拒絕增加工資，面罷工剛開(kāi)始，罷工是否能夠停止。(10分)

四、計(jì)算10%

1、設(shè)命題A”A2的真值為1,A3,A4真值為0,求命題

(A〕v(47(A3AiA,)))<^(A2vY4)的真值。(5分)

2、利用主析取范式，求公式「(P-0)人。人氏的類型。(5分)

五、謂詞邏輯推理15%

符號(hào)化語(yǔ)句：“有些人喜歡所有的花，但是人們不喜歡雜草，那么花不是雜草”。并推證

其結(jié)論。

六、證明：(10%)

設(shè)論域D={a,b,c},求證：VxA(x)vVxB(x)Vx(A(x)vB(x))o

答案：

十、填空10%(每小題2分)

1、P真值為1,Q的真值為0；2、Vx(F(x)AL(x,0)->3y(F(y)AL(y,x)).3、

lr(「P(x)vQ(x))；4、約束變?cè)?、三也(幻=>4>),y為D的某些元素。

H—、選擇25%(每小題2?5分)

題目1