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

卷

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

+

1,設(shè)A={x|(xeN)且(x<5)},3={x|xeE+且Y<7}(N.自然數(shù)集，E正偶

數(shù))則Au3=?

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

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

—>(Pv(Q—>(7?△—>P)))—>(Rv—,5)的真值=。

4.公式。入出小人火四一的主合取范式為

______________________________________O

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

________________________O

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

則R?___________________________________________

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

貝UR=_________________________________________

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

*abcd

aabcd

bbcda

ccdab

ddabc

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

逆元分別為?

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

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

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

A.⑷之⑷}；B.H①}}e{①，{①}}；

C.中€{{中},①};D.{中}G{{中}}。

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

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

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

322x2

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

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

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

B.若R,S是反自反的，則RoS是反自反的;

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

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

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

R={<s,t>\s,t^P(A)A(|S|=|"}則p(A)/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}}0

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

{1,2,31

{1,2,3}{1,2,3}

{1,2,3}

{1,3}

{1}{1,3}口}{1,3}

{1,3}

{1}

①

回(C)(D)

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

A.f:IfE,f(x)=2x；B.f:N->NxN,f(n)=<n,n+1>

C.f：R—>1,f(x)=[x]；D.f(x)|x|。

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

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

A.0；

3。

9、下圖中既不是Eular圖,也不是Hamilton圖的圖是（)

(B)(C)(D)

10、在一棵樹中有7片樹葉，3個(gè)3度結(jié)點(diǎn)，其余都是4度結(jié)點(diǎn)則該樹有（)個(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中有<.b,c>在R中。(8分)

2、f和g都是群<6|,*>到<62.*>的同態(tài)映射，證明《3,★>是<6],十^的一個(gè)子

群。其中c={x|xeG|月』(x)=g(x)}格分)

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

/(吁2)

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

四、邏輯推演16%

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

?A\/B—>CAD、D\/E―>FA—>F

2、Vx(P(x)—>Q(x))nVxP(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è)城市匕#2，?一，匕及預(yù)先算出它們之間的一些直接通

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

試卷一答案：

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

1、｛0」2,3,4,6）；2、（8十C）-A；3、1；4、（「0"SvR）A（「PvFvR）；

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

a

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

題II12345678910

答案CDB、CCADCADBA

三、證明26%

1、證：

“="X/ahcwX若<a,b>,<a,c>eR由R對(duì)稱性知

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

“U”若<a,b>eR,<a,c>eR有<b,c>sR任意a,beX,因

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

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

即R是傳遞的。

2、證V?,/?eC,有/(a)=g(a)JS)=g(A),又

f(b-')=(h),g(b-')=g~'g))=廣i(b)=gTS)=g(b-')

「"(a★人)=/(?)*P'S)=g(a)*g(L)=g(a★人)

:&C：.<C,★>是<6],*>的子群。

3、證：

2e=^d(Fi)>rkr<—

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

,2ek(v-2)

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

k即得k-2。(8分)

②彼得森圖為％=5,e=15,u=l(),這樣k-2不成立，

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

二、邏輯推演16%

1、證明：

①Ap(附加前提)

②Av8T①I

③BTC人Dp

④CAOT②③I

⑤。T@I

@DvET⑤I

⑦DvE—FP

⑧尸T⑥⑦I

⑨Af尸CP

2、證明

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

②P(c)US①

③Vx(P(x)fQ(x))p

④P(c)->Q(c)US③

⑤Q(c)T②④I

⑥VxQ(x)UG⑤

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

三、計(jì)算18%

1、解：

’0100、’1010、

10100101

M=M=MRoMR=

RoooiR?RR0000

,0000,,0000,

‘0101、

1010

Mx=M。MR=

爐DRd21R0000

、0000,

‘1010、

0101

M.=M.0MK=

RRR0000

、0000,

M(R)="R+“屋+%?+%4=000

1^0000；

/.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)樹。算法略。結(jié)果如圖:

樹權(quán)C(T)=23+1+4+9+3+17=57即為總造價(jià)。

試卷二試題與答案

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

1、P：你努力，Q：你失敗?！俺悄闩?，否則你將失敗”的翻y譯為

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

__________________________O

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

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

TTFF

則公式V燈yP(y,x)真值為。

2、設(shè)5=伯|,a?,a8)/Bi是S的子集，則由B3］所表達(dá)的子集是

3、設(shè)A={2,3,4,5,6}上的二元關(guān)系R={<%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=o

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

*abc

aabc

bbbc則幺元是__________是否有幕等

cccb性______;是否有對(duì)稱性_

7、4階群必是群或群。

9、n個(gè)結(jié)點(diǎn)的無(wú)向完全圖Kn的邊數(shù)為,歐拉圖的充要條件是

10、公式（Pv（［P八Q））八（（一戶vQ）A「A的根樹表示為

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

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

A.（PvQ）；B.（PcQ）c（（PTQ）八9TP））；

C.TPFQ）AQ；D,Pf（PvQ）。

2、命題公式（rPfQ）—（「QvP）中極小項(xiàng)的個(gè)數(shù)為（）,成真賦值的個(gè)數(shù)

為（）o

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è)5={1,2,3},定義SxS上的等價(jià)關(guān)系

R={?a,Z?>,vc,d>|va,Z?>wSxS,vc,d>wSxS,a+d=〃+c}則由R產(chǎn)生

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

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

5、設(shè)5="，2,3},s上關(guān)系R的關(guān)系圖為

則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,bGZ}

QS={x\x-2n+\,n^Z]D.S={X|XGZAX>0}=JSJ

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

8、在如下的有向圖中，從V]到V4長(zhǎng)度為3的道路有（）條。

A.1；

9、在如下各圖中（）歐拉圖。

設(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>1（。,。GA）A（對(duì)于某—fteA,有<”,c>eR且<c,b>GR）}試證

明若R是A上一個(gè)等價(jià)關(guān)系，則S也是A上的一個(gè)等價(jià)關(guān)系。（9分）

2、用邏輯推理證明：

所有的舞蹈者都很有風(fēng)度，王華是個(gè)學(xué)生且是個(gè)舞蹈者。因此有些學(xué)生很有風(fēng)度。

（11分）

3、若f8是從A到B的函數(shù)，定義一個(gè)函數(shù)g：B->2"對(duì)任意。eB有

gS）={x|（xeA）A（/（x）=6）},證明：若f是A到B的滿射，則g是從B到2A

的單射。（10分）

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

777=—（n-1）（n-2）+2

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

Hamilton圖（8分）

四、計(jì)算14%

I、設(shè)<線,+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)二叉樹。（7分）

試卷二答案：

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

1、一1尸fQ；PAQ2、T3、831=^00011111={%，。5，。6，%，。8}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,

‘11111、

11111

00011

11111

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

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

—n(n-1)

選擇20%（每小題2分）

題目12345678910

答案B、DD；DDBDABBBB、C

三、證明46%

1、(9分)

(1)S自反的

VawA,由R自反，；.(<a,a>eR”(<a,a>eR),:.<a,a>&S

(2)S對(duì)稱的

\/a,beA

<a,b>eSn(<a,c>eR)A(<c,〃〉eR)。一、定義

=>(<a,c>e/?)A(<c,b>eR)…H對(duì)稱

=><b,a>eS…R傳遞

(3)S傳遞的

Va,b,c￡A

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

=>(<a,d>eR)A(<d,b>GR)A(<h,e>eR)A(<e,c>eR)

=>(<a,b>G/?)A(<b,c>eR)???7?傳遞

=<a,c>eS???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)-Q(x))、5(?)AP(?)結(jié)論：3x(S(x)AQ(x))..,…3分

①S(a)人P(a)p

②Vx(P(x)fQ(x))p

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

④P(a)T①I

⑤。（。）.T③④I

⑥S(a)T①I

⑦S(a)AQ(a)T⑤⑥I

⑧HX(S(X)AQ(X)EG⑦……11分

3、10分

證明：wZ?2）???/滿射-36Zpa2€A

阿（。1）=仇,/（。2）=。2,且/（卬）^/（。2），由^^/^函數(shù)，

又g（4）={x］（xwA）A（/a）=b|）},g（b2）={x|（xeA）A（/（x）=b2）}

a〕egSJa2Ggs2）但.史目包），％史g（4）r.gSjHgSz）

由4,打任意性知，g為單射。

4、8分

證明：設(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、8分

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

反證法：若存在兩結(jié)點(diǎn)u,v不相鄰且△（“）+”3）〈〃-1,令匕={〃#},則G-VI

1

m>—(zi-1)(n-2)+2-(n-1)

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

1

m2—(〃一2)(〃一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%d

1、7分

解：子群有<{[0]},+6>；<{[0],[3]}(+6>；<{[0],[2],[4]},+6>；<{Z6),+6>

{⑼}的左陪集：{⑼},{⑴};{⑵},{[3]}；{[4]},{[5]}

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

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

Z6的左陪集：私。

2、7分

試卷三試題與答案

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

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

則/og(x)=。

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

則s(R)=o

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

法

T=；

T的關(guān)系圖為

T具有性質(zhì)。

4、集合4={{6,2},{2}}的事集

2%。

5、P,Q真值為0；R,S真值為1。貝yl#(PA(AvS))f((PvQ)A(RAS))的

真值為。

6、M#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。

則謂詞wffVMP(x)-R'(O(y)AN(y,x)))的自然語(yǔ)言是

8、謂詞wffVWy(3z(P(x,z)AP(y,z))T3uQ(x,y,u))的前束范式為

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

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

A、(P八q)f(pvq)；B、(〃—4)一((〃-4))人(4fP))；

c、TP—q)人q；D、q。

2、助,「(”八幻—廠的主析取范式中含極小項(xiàng)的個(gè)數(shù)為()。

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

3、給定推理

①Vx(尸(x)fG(x))p

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

③士F(x)P

④R(y)ES③

⑤G(y)T②④i

⑥VxG(x)UG⑤

/.Vx(F(x)—>G(x))=>VxG(x)

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

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

4、設(shè)Si={l,2,…，8,9),S2={2,4,6,8},S3={1,3,5,7,9},S4={3,4,5},

S5={3,5},在條件X=且XZS3下*與()集合相等。

A、X=S2或Ss;B、X=S4或S5;

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

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

7?={<x,y>|ePAX是y的父親},S={<x,y>|e尸人》是》的母親}

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

A、{<x,y>|x,yw尸Ax是y的丈夫}；

B、{<尤,y>|x,yeP△x是y的孫'子或?qū)O'女.

C、①；D、{<*，y>1蒼丁62人1是丁的祖父或祖母。

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

A、于：RTR,f(x)=-x2+2x-l.

B、/：Z+fR,/(x)=lnx.

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

D、f：RfR,/(x)=2x+lo

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

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

@③

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

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

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

8、設(shè)5={中,{1},工2}},貝第()cSo

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

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

A、23；B.32：C、22''；D、23'。

10、全體小項(xiàng)合取式為（）。

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

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

］、AvB—>CAD,DVE—>F=A—>F

2、Vx（P（x）vQ（x））=>VxP（x）v3%2（x）

四、（14%）

集合X={<1,2>,<3,4>,<5,6>,…},R={?x?,y?>,<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ù)，證明/eg也是函數(shù)。

2、（10分）設(shè)函數(shù)g：S—>丁于盯fS,證明于：TfS有?一左逆函數(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>}.

4、

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

6、(Pv^QvR)八一PvQvR)八(PvQvR)；7、任意x,如果x是素?cái)?shù)則

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

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

題目12345678910

答案cCCCABDADC

七、證明16%(每小題8分)

1、

①AP(附加前提)

②AvB31

③AvBTC八DP

④C八DT②③I

⑤。T④I

⑥。vET⑤I

⑦DvEfFP

⑧FT⑥⑦I

⑨A/CP

2、

,/VxP(x)v3xQ(x)<=>—>(Vx)P(x)T3xQ(x)

本題可證Vx(P(x)vQ(x))n["xP(x)T3XQ{X}

①TVxP(x))P(附加前提)

②3x(-1P(x))T①E

③田。)ES②

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

⑤P(a)vQ(a)US@

⑥。⑷T③⑤I

⑦Hxax)EG@

⑧TVxP(x)-3xQ{x}CP

八、14%

(1)證明:

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

?x,y>,<x,y?eR…R自反

2、對(duì)稱性：>eX，\/<々，刈>eX

當(dāng)<<X],必>,<x2,y2?eH時(shí)即2+%=乙+M也即々M=X+%

故<<%2，%>，<X|，y?GR…R有對(duì)稱性

V<XPI€XG

3、傳遞性：J>,y<x2,y2>XV<x3,y3>eX

GG

當(dāng)<<X],y>,<x2,y2?R且<<x2,y2>,<x3,y3?R時(shí)

艮JX|+%=9+H(1)

[x2+y3=x3+y2(2)

(1)+(2)X]+必+H=“2+y+%3+%

即=%+y

故<<知%>,<x3,y3?e/?…H有傳遞性

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

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

九、10%

‘0100、

1010

0001

、0000,關(guān)系圖

q010、

0101

M足=MR°MR

0000

2、、0000J

101、

1010

%=%。%

0000

000>

’1010、

0101

MR，=/°%

0000

、0000>%=MR，以=%

‘1111、

1111

MMR)=MR+MR2+MR、+MR,=0001

,0000,

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

d>}o

六、20%

feg={<x,y>|xGdomf/\x6domg/\y=/(x)Ay=g(x)}

K(1)={<x,y>|xedomfodomg/\y=/(x)=g(x)}

令〃=/cg

domf(~\g—domh-{x|xedomfr\dom^f(x)—g(x)}

(2)h={<x,y>\x&domfrydomg八y=h{x}=f(x)=g(x)}

對(duì)xGdomh若有y,必使得

必=〃(x)=/(x)=g(x),y2=h(x)=/(x)=g(x)

由于f(或?)是函數(shù)有必=為即,G八加〃有唯二y使得y=h(x)

/eg也是函數(shù)。

2、證明：

"="荀有一左峋，則對(duì)VreTgof(t)=t

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

"U"/是入射，/：TfS定義如下：

Vse/(T),由/入射，引reT,慟⑺=s

此時(shí)令g(s)=f,若s史/(T)令g(s)=cwT

則對(duì)VseS,g(s)只有一個(gè)值t或c且茍1(/)=s

則g。/?)=gG)=f，故g是/■的左逆元

即茍入射，必能構(gòu)造函麴，使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、謂詞合式公式h&幻的前束范式

為。

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)*和丫都大于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+2W4當(dāng)且僅當(dāng)3是奇數(shù)；D、2+2W4當(dāng)且僅當(dāng)3不是奇數(shù)；

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

A、P=B、P=PyQ；C、（「PVQ）A（PV「Q）；D、TPCQ）。

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

A、P—>尸；B、P7（P八R）oR；

C、尸人（。-Q）=Q；D、（Q-R）=（PAQ）->R。

5、若4,4…A“和B為wff,且A八4=>3則（）o

A、稱4八4△???△A,為B的前件；B、稱B為4,4.一4,的有效結(jié)論

當(dāng)且僅當(dāng)AAA2A---AA?AB<=>F.D、當(dāng)且僅當(dāng)

A1AA2A???AA—iB<=>F

6、A,B為二合式公式，且A=則（）o

A、A-8為重言式；B、A*=B；

C、An8：D、A*<=>B.E、A—8為重言式。

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

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

A、A/(x)Mortal(x),gM(x)AMortaV^x)

QVx(M(x)—>Morta(x)),D、3x(Af(x)AMortal(x))

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

的真值為()?

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

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

A、Vx(P(x)vQ(x))<=>VxP(x)vX/xQ(x).

B、3x(P(x)vQ(x))o3xP(x)v3xQkx}.

C、Vx(P(x)->Q)=VxP(x)fQ.

D、士(P(x)fQ)ohP(x)-Q。

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

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

②尸(y)fG(y)us①

③3xP(x)p

④尸(y)ES③

⑤G(y)T②④i

⑥3%G(X)EG⑤

A、②；B、④；C、⑤；D、⑥

三、邏輯判斷30%

1、用等值演算法和真值表法判斷公式A=（（PfQ）八（0fP））―（Pc。）的類

型。（10分）

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

（1）已知AvCoBvC,問(wèn)Ao8成立嗎？

（2）已知「Ao」8,問(wèn)Ao8成立嗎？

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

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

四、計(jì)算10%

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

（Av（4f（4A-vAm—lAV-TAJ的真值。（5分）

2、利用主析取范式，求公式TPfQ)AQAH的類型。(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、VXF(x)AL(x,O)3y(F(y)AL(y,x)),3、

士(fP(x)vQ(x))；4、約束變?cè)?、丸A(x)=>A(y),y為口的某些元素。

4^一、選擇25%(每小題2.5分)

題目12345678910

答案A,CA,DC,DA,DB,CA,B,C,D,ECAB(4)

十二、邏輯判斷30%

1、(1)等值演算法

A=((PfQ)A(Q-P))—