離散數(shù)學(xué)復(fù)習(xí)題與參考答案

離散數(shù)學(xué)復(fù)習(xí)題與參考答案

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

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

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

偶數(shù))貝U。

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

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

一1(Pv>(RA-iP)))->(7?v-i5)的真值=

4.公式(PAR)V(SAR)V「P的主合取范式為

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

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

則R2=

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

貝ijR=

a

8.圖的補圖為

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

*abcd

aabcd

bbcda

ccdab

ddabc

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

的逆元分別為?

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

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

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

A.{。}1{{叫；B.{{①{①，{①}}；

C.①6{{①},①};D,{中}e{{①}}。

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

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

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

A.23；B.32；C.23x3；D.32x2。

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

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

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

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

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

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

R={<s,^>|s,^ep(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}}

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

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

{1,2,3}

■{1,3}fib

(J)

(C)(D)

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

A.f(x)=2x；B.f:NfNxN,f(n)=<n,n+l>；

C.f:R->1,f(x)=[x]；D.f(x)=|x|o

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

8、圖中從”到V3長度為3的通路有()條。

0；B.1；D.3o

9、下圖中既不是Eular圖，也不是Hamilton圖的圖是()

10、在一棵樹中有7片樹葉，3個3度結(jié)點，其余都是4度結(jié)點則該樹有（）個4

度結(jié)點。

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

三、證明26%

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

＜a,b＞利＜a,c＞在R中有v.b,c＞在R中。（8分）

2、f和g都是群＜G|＞★＞到＜62,*＞的同態(tài)映射，證明＜C,★＞是＜61,★＞的一個

子群。其中c={x|xeG「目，（x）=g（x）}信分）

3、G=＜V,E＞（|V|=v,|E|=e）是每一個面至少由k（k＞3）條邊圍成的連通平

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

分）

四、邏輯推演16%

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

［、BTC/\D,D7ETF=A—F

2、VA:(P(X)rQ(x))nVxP(x)tVXQ(X)

五、計算18%

I、設(shè)集合A={a,b,c,d}上的關(guān)系R={va,b>,<b,a>,<b,c>,<c,d>}用矩陣運

算求出R的傳遞閉包t（R）。（9分）

2、如下圖所示的賦權(quán)圖表示某七個城市匕，匕，…，匕及預(yù)先算出它們之間的一些直接

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

分）

v6v3

試卷一答案：

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

1、{0,1,2,3,4,6}；4、(-\PvSvR)A(-\Pv-\Sv/?).

{<a.b>,<a,c>,<a,d>,<b,d>,<c,d>}UIA；8、

5、1；6、{<1,1>,<1,3>,<2,2>,<2,4>};7、

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

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

題目12345678910

答案CDB、CCADCADBA

三、證明26%

1、證：

“n”^a,b,ceX若<a,b>,<a,c>GR由R對稱性知

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

“u”若<a,b>eR,<a,c>eR有<b,c>eR任意a,b€X,因

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

若<a,b>eR,<b,c>eR貝q<b,a>eRA<b,c>eR<a,c>GR

即R是傳遞的。

2、證\fa,beC有f(a)=g(a)J(b)=g(b)又

l1

f(b-')=f-(b),g(L)=gt3)f(b-')=f-'(b)=g-(b)=gb)

f(a★L(fēng))=f(a)*尸㈤=g(a)*g(b~l)=g(a^b-')

?"★L(fēng)€C.-.<c,★>是<6],*>的子群。

3、證：

2e=￡d(Fj)Nrk.絲

①設(shè)G有r個面，則片1，即k。而u-e+r=2故

/2e/W-2)

v-e+r<v-e+—e<-------

k即得k-2。(8分)

心—2)

e<-------

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

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

二、邏輯推演16%

1、證明：

①AP（附加前提）

②4vBT①I

③AvBTC八DP

@CADT②③I

⑤oT@I

⑥D(zhuǎn)vET⑤I

①DTETFP

⑧尸T⑥⑦I

⑨4-?FCP

2,證明

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

②P(c)US①

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

④P(c)-0(c)US③

⑤。(c)T②④I

⑥VxQ(x)UG⑤

⑦VxP(x)fVxQ(x)CP

三、計算18%

1、解:

'0100、q010、

10100101

MK=M'=MAR。MKR=

0001R-0000

、0000,、0000,

<0ior

1010

=MR2OMR=

0000

10000,

「1010、

0101

此4=M.。MR—

R0000

(0000,

'1111、

1111

MM+M+M..+M,二

?nR-KIT0001

、000

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

<b,d>,<c,d>}

2、解：用庫斯克(Kruskal)算法求產(chǎn)生的最優(yōu)樹。算法略。結(jié)果如圖：

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

試卷二試題與答案

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

1、P：你努力，Q：你失敗。“除非你努力，否則你將失敗”的翻譯為

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

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

P(1J)P(l,2)P(2,l)P(2,2)

TTFF

則公式Vx才P（/x）真值為。

2、設(shè)S={a］，a?,ag},Bj是S的子集，則由B31所表達的子集是

/?

3、設(shè)A={2,3,4,5,6}上的二元關(guān)系={<%，^>1%<y丫》是質(zhì)數(shù)},則R=

__________________________________________________（列舉法）。

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

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

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

R=_______________________0

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

*abc

aabc

bbbc

cccb

則幺元是;是否有靠等性;是否有對稱性

7、4階群必是群或群。

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

10、公式（PvJPAQ））人（（「PvQ）A的根樹表示為

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

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

A.（PAQ）->（PV。）；B.（P?Q）?（（Pf。）八（。-P））；

C.TP-。）八。；D.P，PvQ）。

2、命題公式（「P一。）-（「Qv尸）中極小項的個數(shù)為（）,成真賦值的個

數(shù)為（）o

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

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

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

4、設(shè)5={1,2,3},定義SxS上的等價關(guān)系

R={?a,b>,<c,d>\<a,b>eSXjd>￡SxS,a+d=b+c}貝“山R產(chǎn)

生的SxS上一個劃分共有（）個分塊。

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

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

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

A.自反性、對稱性、傳遞性；B.反自反性、反對稱性;

C.反自反性、反對稱性、傳遞性：D.自反性。

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

A.S={X|X=Q+〃6,a,beQ}B.S={x\x=2n9a.bGZ}

QS={x\x=2n+\,nGZ}D.S={X|XCZAXNO}=N。

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

8、在如下的有向圖中，從V1到V4長度為3的道路有（）條。

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

A.群;B.獨異點；C.半群。

三、證明46%

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

S={<a,b>|（a,beA）△（對于某一個ceA,W<a,c>e7?且<R）}試

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

2、用邏輯推理證明：

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

（11分）

3、若-8是從A到B的函數(shù)，定義一個函數(shù)g2"對任意be8有

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

2A的單射。（10分）

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

—1）（〃—2）+2

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

Hamilton圖（8分）

四、計算14%

1、設(shè)<Z6,+6>是一個群,這里+6是模6加法，Z6={[0],[1],[2],[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)二叉樹。（7分）

試卷二答案：

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

1、-'P->Q-PAQ2、T3、B31=綜0。11111={%，%，%，%，/}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>,<

’11111、

111I1

00011

11111

5,3>,<5,4>,<5,5>,<5,6>}、00000,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-l)

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

題目12345678910

答案B、DD；DDBDABBBB、C

三、證明46%

1、(9分)

(1)S自反的

VaeA,由R自反，?1?(<>6A(<?,?>6R)；：.<a,a>eS

(2)S對稱的

Ya,beA

<a,b>GS=>(<a,c>eR)A(<c,b>G/?)…S定義

=>(<a,c>e/?)A(<c,Z?>eR)…R對稱

=<b,a>GS…R傳遞

(3)S傳遞的

X/a,b,ceA

<a,b>e5A<b,c>eS

=>(<a,d>G/?)A(<d,b>eR)A(<b?e>eR)A(<e,c>e7?)

=>(<a,b>e/?)A(<h,c>e/?)…R傳遞

=><a,c〉eS…S定義

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

2、11分

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

上述句子符號化為：

前提:Vx(P(x)->2(x))>S(a)AP(a)結(jié)論：3x(S(x)A<2(x))3分

①S⑷人P(a)p

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

③P(。)tQ(a)US②

④P(。)T①I

⑤。(a).T③④I

⑥S(a)T①I

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

⑧士(S(x)/\Q(x)EG⑦……11分

3、10分

證明：V仇也e8,(4#/?2)；/滿射

使/1(%)=仇,/(。2)=62，且，(。1)1/(。2)，由于偃函數(shù)，，。尸。2

又A

g(4)={xI(X")△(/(X)=4)},g(b2)={xI(xeA)(f(x)=b2)}

但電

?■?.eg(4),a2eg(b2)a1g(b2),a2g(b1)：.g(—)Hg(%)

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

4、8分

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

連通分支G|、G2,使得u和v分別屬于Gi和G2，于是Gi和G2中各含有1個奇數(shù)

度結(jié)點，這與圖論基本定理矛盾，因而u,v一定連通。

5、8分

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

反證法:若存在兩結(jié)點u,v不相鄰且4(〃)+火式”"-1,令匕={〃)},則6與1

m>—(/z-l)(/z-2)+2-(n-1)

是具有個結(jié)點的簡單圖，它的邊數(shù)，可得

n-22

,1、

m2—(n—2)(〃-3)+1

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

中任何兩個相鄰的結(jié)點度數(shù)和不少于n。

所以G為Hamilton圖.

四、計算14%

1、7分

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

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

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

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

Z6的左陪集：Z60

2、7分

8

□JI4I

試卷三試題與答案

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

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

則/。g(x)=.

2^設(shè)人={@,b,c},A上二元關(guān)系R={〈a,a>,<a,b>,<a,c>,<c,c>},

則s(R)=o

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

法

T=；

T的關(guān)系圖為

____________________________________;

T具有性質(zhì)。

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

2A=o

5、P,Q真值為0；R,S真值為1。則(尸人(RVS))~((PVQ)A(RAS))的

真值為。

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

為。

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

則謂詞wffWx(P(x)T寺(0(y)AN(y,x)))的自然語言是

8、謂詞wffVxVy(土(P(x,z)AP(y,z))-3uQ(x,y,u))的前束范式為

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

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

A、("4)—(Pj)；B、(PCq)C((pTq)人(qfp))；

c、TP—q)八q：D、(P「P)cq。

2、Mf「的主析取范式中含極小項的個數(shù)為()。

A2；B、3；C>5；D、0；E、8。

3、給定推理

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

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

③土尸(x)p

④尸(y)ES③

⑤G(y)T②④I

⑥VxG(x)UG⑤

Vx(F(x)fG(x))nVxG(x)

推理過程中錯在()。

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

4、設(shè)S|={1,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或S$;B、X=S4或S5;

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

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

/?={<>|e是y的父親},

5

5={<%,>|工,,6/八犬是丁的母親}則5-1。/?表示關(guān)系（）o

A、{<%,—>|X,。€/^%是、的丈夫}；

B、{<x,y>|x,y€PAX是y的孫子或?qū)O女}；

C、①；D、{<%y>|了,丁€2人》是丁的祖父或祖母。

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

2

A、f：RTR,/（X）=-X+2X-1;

B、-R,/（x）=lnx;

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

D、f：RTR，/（x）=2x+l。

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

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

?@

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

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

C、反自反、反對稱、傳遞；D、自反、對稱、反對稱、傳遞。

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

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

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

A,23；Bs32；C、I-；D、23：,

10、全體小項合取式為（）。

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

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

］、AvB—>CA￡）,￡）VE—>F=>AF

2、Vx（P（x）vQ（x））=VxP（x）v3xQ（x）

四、（14%）

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

1、證明R是X上的等價關(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、用矩陣運算求出R的傳遞閉包。（6分）

六、（20%）

1、（10分）設(shè)f和g是函數(shù)，證明/eg也是函數(shù)。

2、（10分）設(shè)函數(shù)g：SIT證明/—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>}.

4、

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

6、（PviQvR）八LPYQVR）八（PvQvR）；7、任意x,如果x是素數(shù)

則存在一個y,y是奇數(shù)且y整除x；8、

VxVyVz口，(-1P(x,z)v「P(y,z)vQ(x,y,u))o

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

題目12345678910

答案cCCCABDADc

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

1、

①AP（附加前提）

②Av8T①I

③AvB—>CA￡>P

@CA￡)T②③I

⑤。T@I

@DvET⑤I

⑦D\ETFP

⑧/T⑥⑦I

⑨CP

2、

VxP(x)vBxQ(x)=-i(Vx)P(x)T3x(2(x)

本題可證Vx(P(x)vQ(x))=>-i(DxP(x)T3xQ(x)

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

②玉(lP(x))T①E

③「P(a)ES②

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

⑤P(a)vQ(a)US@

⑥。⑷T③⑤1

⑦玉。（x）EG@

⑧「(VxP(x)CP

八、14%

(1)證明:

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

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

2、對稱性：V<x”必>eX，V<X2，V2>eX

當(dāng)<",4>,<x2,y2>>e/?時即玉+乃+必也即%2+必=再+力

故<<%2，%>，</，為》€(wěn)寵…R有對稱性

v<

3、傳遞性：^i，yi>€x<x2,y2>eXV<x3,y3>eX

當(dāng)<<花，%>,<x2,y2?e??K?x2,y2>,<x3,y3>>eR時

即卜+乃=+H(1)

1%2+為=七+%(2)

(1)+(2)/+乃+尤2+%=+%+尤3+為

即為+為=七+M

故<<Xi，M>,<當(dāng),力>>e?…R有傳遞性

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

2、X/R={[<1，2汕}

九、10%

’0100、

1010

MR=

0001

<°00°J；關(guān)系圖

"1010"

0101

M.=MR。MR=

R~RRoooo

、0000,

’0101、

1010

MR\=MOM

K2R0000

、0000,

‘1010、

0101

RRK0000R

.000ojMRSUMR-MR,=MR……

'1111、

1111

MI(R)=MK+MR2+MR,+MRi=o00]

、0000,

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

>}°

六、20%

/cg={<x,y>|x￡domfAxedomgAy=f(x)Ay=g(x)}

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

令力=/cg

r.domfcg=domh={x|xedomfndomg,f(x)=g(x)}

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

對xedomh若有口,為使得

%=%(x)=f(x)=g(x),y2=h(x)=f(x)=g(x)

由于/(或g)是函數(shù)，有y=>2即Wxedomh有唯一>使得y=h[x}

二/eg也是函數(shù)。

2、證明：

置/有一左股，則對VfeTgo/(f)=f

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

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

Vse/(T),由/入射，V管,雷⑴=s

此時令g(s)=t,若sef(T)令g(s)=ceT

貝U對Vs6S,g(s)只有一個值t或c且若/。)=s

則g0f(t)=g(s)=t,故g是f的左逆元

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

試卷四試題與答案

填空10%（每小題2分）

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

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

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

為。

3、謂詞合式公式VxP（x）—玉。（工）的前束范式

為O

4、將量詞轄域中出現(xiàn)的和指導(dǎo)變元交換為另一變元符號，公式其

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

5、設(shè)x是謂詞合式公式A的一個客體變元，A的論域為D,A（x）關(guān)于y是自由的，

則

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

為ES?

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

1、下列語句是命題的有（）?

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

C、xy>°當(dāng)且僅當(dāng)X和y都大于0；D、我正在說謊。

2、下列各命題中真值為真的命題有（）。

A、2+2=4當(dāng)且僅當(dāng)3是奇數(shù)；B、2+2=4當(dāng)且僅當(dāng)3不是奇數(shù)；

C、2+2關(guān)4當(dāng)且僅當(dāng)3是奇數(shù)：D、2+2/4當(dāng)且僅當(dāng)3不是奇數(shù)；

3、下列符號串是合式公式的有（）

A、P=Q；B、PnPvQ；c、（「Pv°）A（尸v-,0）；D、TP?Q）。

4、下列等價式成立的有（）。

A、PfQ=-iQ—>—；B、P7（P/\R）=R；

c、0）0。；D、P4（QTR）O（P八Q）fR。

5、若4，42…A.和B為wfF,且4|人人2△…人4=>3則（）。

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

C、當(dāng)且僅當(dāng)4人42△…△A.ABOP；D、當(dāng)且僅當(dāng)

A,AA2A???AA—18u>F。

6、A,B為二合式公式，且Ao8,貝ij()。

A、A—8為重言式；B、A*=3*；

C、A=>B.D、A*u>8*；E、A-8為重言式。

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

(論域為全總個體域)M(x)：x是人；Mortal(x)：x是要死的。

A、M(^)Mortal(x).B、M(X)/\Mortal(X)

C、Vx(M(x)TMortal(x)),D、3X(M(X)AMortal(x))

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

A的真值為()。

A、1；B、0：C、可滿足式；D、無法判定。

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

A、Vx(P(x)vQ(x))oVxP(x)vVxQ(x).

B、3x(P(x)vQ(x))3xP(x)v3xQ(x).

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

、

D3x(P(x)->Q)<=>BxP(x)->Qo

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

(尸

①Vx(x)fG(x))P

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

③玉尸(x)p

④Ay)ES③

⑤G(y)T②④I

⑥HxG(x)EG⑤

A、②；B、④：C、⑤：D、(6)

三、邏輯判斷30%

1、用等值演算法和真值表法判斷公式A=((P-Q)人①fP))C(PCQ)的類

型。(10分)

2、下列問題，若成立請證明，若不成立請舉出反例：(10分)

(1)已知AvCoBvC,問4=8成立嗎？

(2)已知Y問A=8成立嗎？

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

了廠長。H：若廠方拒絕增加工資，面罷工剛開始，罷工是否能夠停止。(10分)

四、計算10%

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

(4v(A2->(4△Y])))?(4VY4)的真值。(5分)

2、利用主析取范式，求公式[(PfQ)AQAR的類型。(5分)

五、謂詞邏輯推理15%

符號化語句：“有些人喜歡所有的花，但是人們不喜歡雜草，那么花不是雜草”。并推

證其結(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(j)AL(y,x)).3、

士(「P(X)VQ(X))；4、約束變元；5、*4(x)=A(y),y為D的某些元素。

H■一、選擇25%(每小題2.5分)

題目12345678910

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

十二、邏輯判斷30%

1、（1）等值演算法

A=（（P->。）△（。rP））?（P?。）o（P?》（Pc。）oT

（2）真值表法

PQPTQQfP(PfQ)/x(Q->P)P