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

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

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

1,設4=3M，)且。<5)},8=5|%=七+且6<7}(N:自然數(shù)集，E卡正偶

數(shù))則AD5=。

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

3.設P,Q的真值為0,R,S的真值為1,則

「(Pv(Q—>(R人一1P)))—?(Rv—>S)的真值=

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

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

6.設A={1,2,3,4},A上關系圖為

7.設人=色，b,c,d},其上偏序關系R的哈斯圖為

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

*abcd

aabcd

bbcda

ccdab

ddabc

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

逆元分別為o

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

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

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

A.{研={{*；B.{{①}}€仲，使}}；

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

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

A.{4,3}U＜t＞；B.{①，3,4}；C.{4,①，3,3}；D.{3,4}。

3、設人={1,2,3},則A上的二元關系有（）個。

323x32x2

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

4、設R,S是集合A上的關系，則下列說法正確的是（）

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

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

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

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

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

R={<s,t>\s,tep（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、設人={①，{1},{1,3},{1,2,3}}則A上包含關系“U”的哈斯圖為（）

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:I->N,f(x)=|x|o

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

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

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

度結(jié)點。

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

三、證明26%

1、R是集合X上的一個自反關系，求證：R是對稱和傳遞的，當且僅當

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

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

群。其中C={x|xe5月/(x)=g(x)}一分)

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

J(L2)

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

四、邏輯推演16%

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

［、AvB—QvfTb=>A—

2、Vx(P(x)fQ(x))nVxP(x)7X/xQ(x)

五、計算18%

1、設集合A={a,b,c,d}上的關系R={<a,b>,<b,a>,<b,c>,<c,d>}用矩陣運算

求出R的傳遞閉包t(R)。(9分)

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

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

試卷一答案：

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

1、｛0,1,2,3,4,6｝；2、（8十。）一4；3、1；4、（「PvSvR）A（「尸v-1svR）；

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”^a,b,c&X若<a,b>,<a,c>eR由R對稱性知

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

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

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

若<a,b>￡R,<b,c>GR則<b,a>GRA<b,c>GR<a,c>GR

即R是傳遞的。

2、證Ma,beC,有/伍)=g(a),/S)=g(。)，又

f(b-')=f-\b),g(b~l)=g-l(b)=g-l(b)=g(b-1)

??./(?★L)=/(a)*f-'3)=g⑷*gb)=g(a★L)

C/.<C,★>是<61,*>的子群。

3、證：

2e=V>rkr<—

①設G有r個面，則i=i，即左。而u—e+r=2故

△,2e/。-2)

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

攵即得k—2。(8分)

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

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

二、邏輯推演16%

1、證明：

①AP（附加前提）

②T①I

③Av8—>C人。P

④CADT②③I

⑤。T?I

@DvET⑤I

⑦￡>vE—>FP

⑧/T⑥⑦I

⑨AT尸CP

證明

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

②P(c)US①

③Vx(P(X)T。(初P

④P(C)TQ(C)US③

⑤。(c)T②④I

⑥VxQ(x)UG⑤

⑦VXP(X)TVxQ(x)CP

三、計算18%

1、解:

'0100、'1010'

10100101

MR=M=MR。M口=

R0001Rn2-RR0000

、0000,、0000,

'0101、

1010

=M〃M

R0000

、0000,

q010'

0101

R，=MR、°MR

M0000

、0000>

111、

1111

M,（R）=MR+%+%+%=oo0

1

1k000oj

:.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é)果如圖：

樹權C(T尸23+1+4+9+3+17=57即為總造價。

試卷二試題與答案

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

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

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

________________________O

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

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

TTFF

則公式Vx%,P（y,x）真值為。

2、設S={a］，a?,a^},Bj是S的子集，則由B31所表達的子集是

3、設A={2,3,4,5,6}上的二元關系式二長/丁^^^y丫苫是質(zhì)數(shù)},則R=

__________________________________________________（列舉法）。

R的關系矩陣MR=

5、設A={1,2,3},則A上既不是對稱的又不是反對稱的關系

R=;A上既是對稱的又是反對稱的關系

R=0

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

*abc

aabc

bbbc則幺元是；是否有幕等

cccb性；是否有對稱性。

7、4階群必是群或群。

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

10、公式（P7（［尸AQ））A（（「尸V0）A「R的根樹表示為

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

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

A.（尸入Q）T（PVQ）；B.（PC2）C（（PTQ）A（QTP））；

c.TPTQ）A°；D,P"（PVQ）。

2、命題公式（「PTQ）TV尸）中極小項的個數(shù)為（）,成真賦值的個數(shù)

為（）。

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

3、設$={①,田,{1,2}},則2$有（）個元素。

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

4、設5="，2,3},定義SxS上的等價關系

R={?a.b>,<c.d>|<a,b>￡SxS,<c,d>￡SxS,a+d=。+c}則由R產(chǎn)生

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

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

5、設5={1,2,3},S上關系R的關系圖為

23A

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

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

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

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

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

。

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

7、下面偏序集（）能構成格。

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

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

三、證明46%

1、設R是A上一個二元關系，

S={<a,b>|（a,beA）人（對于某一個ceA,有<a,c>e―且<c,b>eR）}試證

明若R是A上一個等價關系，則S也是A上的一個等價關系。（9分）

2、用邏輯推理證明：

所有的舞蹈者都很有風度，王華是個學生且是個舞蹈者。因此有些學生很有風度。

（11分）

3、若是從A到B的函數(shù)，定義一個函數(shù)g：872A對任意be6有

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

的單射。（10分）

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

m=—（M-1）（H-2）+2

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

Hamilton圖（8分）

四、計算14%

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

試求出<Z"+6>的所有子群及其相應左陪集。（7分）

2、權數(shù)1,4,9,16,25,36,49,64,81,100構造一-棵最優(yōu)二叉樹。（7分）

試卷二答案：

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

1、~<P->Q-P人0,2、T3、^3i=^oooiiin=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、

-n（n-l）

2；圖中無奇度結(jié)點且連通10、

fPQ->PQ

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

題目12345678910

答案B、DD；DDBDABBBB、C

三、證明46%

1、(9分)

(1)S自反的

VQEA,由R自反，???(<見。>￡R)八R),a,a>eS

(2)S對稱的

Va,/?eA

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

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

=><b.a>GS…R傳遞

(3)S傳遞的

Va,仇c￡A

<a.b>G5A<b,c>eS

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

N/?)A(<h.c>€R)…R傳遞

=><a.c>ES…S定義

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

2、11分

證明：設P(x)：x是個舞蹈者；Q(x)：x很有風度；S(x)：x是個學生；a：王華

上述句子符號化為：

前提：”(P(x)T。(初、S⑷人尸(。)結(jié)論：*(S(X)A。0))……3分

①S(a)AP(a)P

②Vx(P(x)TQ(x))P

③P(“)tQ(a)US②

④P（。）T①I

⑤。(a).T③④I

⑥S(a)T①I

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

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

3,10分

€

證明：W仇,打e8，(仇/滿射3a,,a2

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

又g(4)={x|(xeA)A(/(x)=/?1)},g(%)={x[(xe4)△(/(尤)=%)}

4Wg(仇),g€g(%)但%—8(%),。26g(4)???g@l)Xg@2)

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

4、8分

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

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

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

5、8分

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

反證法：若存在兩結(jié)點u,v不相鄰且火")+43)<〃-1,令匕={〃#},則GM

,1

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

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

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

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

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

所以G為Hamilton圖.

四、計算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、設f,g是自然數(shù)集N上的函數(shù)N，f(x)=x+l,g(x)=2x,

則f°gW=。

2、設A={a,b,c},A上二元關系R={va,a>,va,b>,va,c>,vc,c>},

貝ijs(R)=o

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

法

T=；

T的關系圖為

T具有性質(zhì)。

4、集合4={停,2},{2}}的幕集

2A=。

5、P,Q真值為0；R,S真值為1。則昉'(PA(RVS))T((PVQ)A(RAS))的

真值為o

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

為。

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

則謂詞wffVx(P(x)tR(O(y)AN(y,x)))的自然語言是

8、謂詞wffVxVy(生(P(x,z)AP(y,z))TBuQ(x,y,u))的前束范式為

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

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

A、(P八q)WpYq)；B、(p"q)c((pTq))ZqTp))；

c、Tp—4)人4；D、(PLp)-q

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

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

3、給定推理

①Wx(尸(X)TG(X))p

②F(y)lG(y)us①

③玉尸(x)p

④F(y)ES③

⑤G(y)T②④I

⑥VxG(x)uG⑤

Vx(F(x)tG(x))=>VxG(x)

推理過程中錯在()。

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

4、設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},在條件xaa且X(Z邑下x與()集合相等。

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

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

5、設R和S是P上的關系，P是所有人的集合，

R-{<x,y>\x,yeP/\x是y的父親},S={<x,y>|x,yeP人x是y的母親}

則S-'R表示關系()。

A、{<x,y>|尸AX是y的丈夫};

B、{<X,y>1X,yeP人X是y的孫子或?qū)O女}.

C、①；D、{<x,y>1%,yeP/\x是)，的祖父或祖母}。

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

A、f：RtR,f{x}=-x2+2x-l.

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

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

D、f：RtR,f(x)=2x+lQ

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

7、設$={1,2,3},R為S上的關系，其關系圖為

0)

?④

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

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

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

8、設5={中,{1},{1,2}},則有()qS。

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

9、設A={1,2,3},則A上有()個二元關系。

A、23；B、32；C、22'；D、23"o

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

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

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

[、AvB—>CA￡>,￡)V￡—nAF

2、Vx(P(x)vQ(x))=VxP(x)v玉。(x)

四、(14%)

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

1、證明R是X上的等價關系。（10分）

2、求出X關于R的商集。（4分）

五、（10%）

設集合A={a,b,c,d}上關系R={<a,b>,<b,a>,<b,c>,<c,d>}

要求1、寫出R的關系矩陣和關系圖。（4分）

2、用矩陣運算求出R的傳遞閉包。（6分）

六、（20%）

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

2、（10分）設函數(shù)g：STT證明/有一左逆函數(shù)當且僅當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、{①,{{①，2}},{{2}},{{①,2},{2}}}；5、1：

6、（PV「QVR）A（「PVQVR）A（PVQVR）；7、任意x,如果x是素數(shù)則

存在一個y,y是奇數(shù)且y整除x；8、VxVyVz3M（-1P（x,z）v-,P（y,z）vQ（x,y,u））o

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

題目12345678910

答案CCCCABDADC

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

1,

①AP（附加前提）

②Av3T①I

③Av8TC八DP

(4)CADT②③I

⑤。T@I

⑥。vE0

⑦DvETFP

⑧/T⑥⑦I

⑨A->FCP

2、

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

本題可證Vx(P(x)vQ(x))n「(VxP(x)-?玉。(x)

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

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

③「P(a)ES②

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

⑤P(a)vQ(a)US④

⑥。（。）T③⑤I

⑦小Q(x)EG@

⑧」(VxP(x)T玉Q(x)CP

八、14%

(1)證明：

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

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

2、對稱性：V<Xi，M>eX，V<X2，>2>eX

當?xt,yt>,<x2,y2?GR時即再+y2=x2+y,也即x?+乃=西+乃

故<<42，乃>，",%?€R…R有對稱性

V<x>e

3、傳遞性：i^iX,y<x2,y2>eXV<x3,y3>€X

當?xt,yt>,<x2,y2?eR且<<x2,y2>,<x3,y3?eR時

即卜i=4+y.⑴

l%2+%=與+為(2)

(1)+(2)X|+乃+》2+>3=》2+X+》3+為

即可+>3=尤3+%

故<<修，%>,<》3，>3>>€尺…R有傳遞性

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

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

九、10%

,0100、

1010

MR

0001

1、000關系圖

1010、

0101

MR?=MR。MR

0000

2、、0000,

'0101、

1010

M,=MOM

RK2K0000

10000J

(\010、

0101

MR*=MR、°MR=MR。

0000

0000,MRS=MK,My=M…

111n

1111

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

R3Ri0001

000

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

d>}<)

六、20%

fg={<x,y>\xedomfAXGdomg八y=/(x)Ay=g(x)}

1、(1)={<x.y>\xedomfndomg/\y=/(x)=g(x)}

令人=/cg

domfCg=domh={x|XGdomfCdomg,f(x)=g(x)}

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

對xedomh若有y,為使得

Ji=〃(x)=f(x)=g(x),y2=力(x)=f(x)=g(x)

由于/(或g)是函數(shù)，有必=y2BPVxedomh有唯一7使得y=//(x)

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

2、證明：

"n"荀有一左峋，則對WeTgof(t)=t

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

"u"/是入射，定義如下：

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

此時令g(s)=f,若/(T)令g(s)=ceT

則對VseS,g(s)只有一-個值t或c且茍⑴=s

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

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

試卷四試題與答案

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

1、若P,Q,為二命題,「一Q真值為0當且僅當o

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

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

為。

3、謂詞合式公式WxP（x）f玉。（x）的前束范式

為o

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

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

5、設x是謂詞合式公式A的一個客體變元，A的論域為D,A（x）關于y是自由的，則

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

ES,

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

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

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

C、町>°當且僅當x和y都大于0；D、我正在說謊。

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

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

C、2+2r4當且僅當3是奇數(shù)；D、2+2關4當且僅當3不是奇數(shù)；

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

「

A、P=B、PnPvQ；c、（［PVQ）A（PVQ）；DX「（P一Q）。

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

A、B、PY（P八R）0R；

C、PA（PTQ）Q。：D、P-R）o（P八Q）TR。

5、若A”&…4,和B為wflf,且A人4人…人A”=>8則（)?

A、稱4人A2A??一?!“為B的前件；B、稱B為4，&…A”的有效結(jié)論

C、當且僅當4AA?人???△A“A8QP；口、當且僅當

AjAA2A???AA-1B=F

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

A、為重言式；B、A*n8"；

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

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

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

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

QVx(M(x)—?Mortal(x)),口、玉(M(X)AMortal(X))

8、公式*=玉(尸(外—°(x))的解釋I為：個體域D={2},P(x)：x>3,Q(x)：x=4則A

的真值為()。

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

9、下列等價關系正確的是()。

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

B、3x(P(x)v(2(x))<=>BxP(x)vBxQ(x).

C、Vx(P(x)t。)oVxP(x)tQ；

D、玉(P(x)T。)=>BxP(x)TQ。

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

①VX(R(X)TG(X))p

②R(y)TG(y)us①

③玉尸(x)p

④*y)ES③

⑤G(y)T②④1

⑥玉G(x)EG⑤

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

三、邏輯判斷30%

1、用等值演算法和真值表法判斷公式A=((P7。)人(。TP))C(PC°)的類

型。(10分)

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

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

(2)已知「A=」8,問403成立嗎？

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

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

四、計算10%

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

(A〕V(A2->(A3A-V4,)))(A2v的真值。(5分)

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

五、謂詞邏輯推理15%

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

其結(jié)論。

六、證明：(10%)

設論域D={a,b,c},求證：Vx(A(x)vB(x))。

答案：

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

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

玉(「P(x)vQ(x))；4、約束變元；5、3s(x)=>A(y),y為口的某些元素。

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

題目12345678910

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

十二、邏輯判斷30%

K（1）等值演算法

4=（（P-。）人（。-P））C（PC。）o（P6。）一（PC。）QT

（2）真值表法

PQPTQQTP(PTQ)A(QTP)Pc。A

1111111

1001001

0110001

0011111

所以A為重言式。

2、(1)不成立。

若取C=T則AvToTBvToT有AvCoBvCoT

但A與B不一定等價，可為任意不等價的公式。

(2)成立。

證明：Y0充要條件-u4<->-.B<^