离散数学试卷及答案1

离散数学试题与答案试卷一

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

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

数)则Au3=o

2.A,B,C表示三个集合，文图中阴影部分的集合表达式为

3.设P,Q的真值为0,R,S的真值为1,则

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

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

5.若解释I的论域D仅包含一个元素，则*P(x)fVxP(x)在i下真值为

6.设A={1,2,3,4},A上关系图为

则R2=

7.设人=伯，b,c,d},其上偏序关系R的哈斯图为

则R=

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

*abcd

aabcd

bbcda

ccdab

ddabc

那么代数系统＜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、设人={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的暮集)上规定二元系如下

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、设人={①，{1},{1,3},{1,2,3}}则A上包含关系“三”的哈斯图为()

<{1,2,3}

<{1,3}

<{1}

'①

(C)(DJ

7、下列函数是双射的为（）

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一整数集，E—偶数集，N一自然数集，R—实数集）

8、图中从vi到V3长度为3的通路有（）条。

9、卜♦图中既不是Eular图，也不是Hamilton图的图是（)

(DJ

10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（）个4

度结点。

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

三、证明26%

1、R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当

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

2、f和g都是群招|,外>到<62,*>的同态映射，证明<C,★>是<6|,*>的-个子

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

3、G=<V,E>(|V|=v,|E|=e)是每一个面至少由k(k>3)条边围成的连通平面

eV-

图，则k-2,由此证明彼得森图(Peterson)图是非平面图。(11分)

四、逻辑推演16%

用CP规则证明下题(每小题8分)

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

2、Vx(P(x)-Q(x))nVxP(x)-VxQ(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㊉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对称性知

<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是对称的。

若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<—

①设G有r个面，则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

三、计算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、解：用库斯克(Kruskal)算法求产生的最优树。算法略。结果如图：

树权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

则公式真值为。

2、设S={a］，a2,…，a&},Bj是S的子集，则由B31所表达的子集是

3、设A={2,3,4,5,6}上的二元关系A={<X，y〉|x<yvx是质数},则R=

__________________________________________________（列举法）。

R的关系矩阵MR=

5、设A={1,2,3},则A上既不是对称的又不是反对称的关系

R=;A上既是对称的又是反对称的关系

R=0

6、设代数系统<A,*>,其中A={a,b,c）,

*abc

aabc

bbbc则幺元是；是否有幕等

cccb性；是否有对称性。

7、4阶群必是群或群。

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

10、公式（PV（「PAQ））A（（「PV°）A「R的根树表示为

二、选择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尸）中极小项的个数为（）,成真赋值的个数

为（）。

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

3、设5=仲，{1}，{1，2}},则2,有（）个元素。

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

4、设$="，2,3},定义SxS上的等价关系

R={«a.b>,<c.d>\<a.b〉ESxS,vc,dSxS,a+d=。+c}则由R产生

的SxS上一个划分共有（）个分块。

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

5、设5={1,2,3},S上关系R的关系图为

23A

则R具有（）性质。

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=2+1,neZ}D.5={X|XGZAX>0)=N

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

设R是实数集合，“x”为普通乘法，则代数系统＜R,x＞是（）。

A.群；B.独异点；C.半群。

三、证明46%

1、设R是A上一个二元关系，

S={<a,b>|（a,beA）A（对于某一个cwA,有<a,c>e尺且<c,b>eR）}试证

明若R是A上一个等价关系，则S也是A上的一个等价关系。（9分）

2、用逻辑推理证明：

所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。

（11分）

3、若/：Af8是从A到B的函数，定义一个函数g：8-2'对任意有

g屹）="|（xeA）人（/（x）=3},证明：若f是A到B的满射,则g是从B到2A

的单射。（10分）

4、若无向图G中只有两个奇数度结点，则这两个结点一定连通。（8分）

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

5、设G是具有n个结点的无向简单图，其边数2，则G是

Hamilton图（8分）

四、计算14%

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

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

2、权数1,4,9,16,25,36,49,64,81,100构造一-棵最优二叉树。（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四元群；循环群8、B9、

2；图中无奇度结点且连通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对称的

Pa,bGA

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

=>(<a,c>G/?)A(<c,b>€R)…R对称

=><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是等价关系。

2、11分

证明：设P(x)：x是个舞蹈者；Q(x)：x很有风度；S(x)：x是个学生；a：王华

上述句子符号化为：

前提：Vx(P(x)fQ(x))、S(〃)AP(〃)结论：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是函数，

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

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

由仇,与任意性知，g为单射。

4、8分

证明：设G中两奇数度结点分别为u和v,若u,v不连通，则G至少有两个连

通分支G|、G2,使得u和v分别属于G|和G?,于是GI和G2中各含有1个奇数度结

点，这与图论基本定理矛盾，因而U,V一定连通。

5、8分

证明：证G中任何两结点之和不小于no

反证法：若存在两结点u,v不相邻且d(")+d3)«〃T,令匕={〃#},则GM

,1

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

是具有n-2个结点的简单图，它的边数2，可得

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

2,这与G『G-V|为n-2个结点为简单图的题设矛盾，因而G

中任何两个相邻的结点度数和不少于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是自然数集N上的函数VxeN，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。>1x+y是素数},则用列举

法

T=；

T的关系图为

T具有性质。

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

2A=。

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

真值为o

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

为。

7、设P(x)：x是素数，E(x)：x是偶数,0(x)：x是奇数N(x,y)：x可以整数y。

则谓词wffVx(P(x)t3y(0(y)AN(y,x)))的自然语言是

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)的主析取范式中含极小项的个数为()。

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)

推理过程中错在()o

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

4、设S产{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、设R和S是P上的关系，P是所有人的集合，

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

则Si。??表示关系()。

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

B、{<x,y〉|x,yePAx是y的孙子或孙女}.

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

6、下面函数()是单射而非满射。

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

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

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

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

其中R为实数集，Z为整数集，R+,Z+分别表示正实数与正整数集。

7、设$={1,2,3},R为S上的关系，其关系图为

0)

©④

则R具有()的性质。

A、自反、对称、传递；B、什么性质也没有；

C、反自反、反对称、传递；D、自反、对称、反对称、传递。

8、设5={。{1},{1,2}},则有()=5。

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

9、设A={1,2,3},则A上有()个二元关系。

3223

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

10、全体小项合取式为()«

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

三、用CP规则证明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上的等价关系。（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是函数，证明/Cg也是函数。

2、（10分）设函数g：STTf盯tS,证明f：T-S有一左逆函数当且仅当f是

入射函数。

答案：

五、填空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（「PV0VR）/\（PV0VR）；7、任意x,如果x是素数则

存在一个y,y是奇数且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、对称性：V<X|，H>eX，\/<*2,为〉eX

当«修，%>,<x2,y2»eR时即再+y2=它+M也即/+%=匹+当

故<<%2，%>，</，%>>eR…R有对称性

v<x>eX

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

当<<x”yi>,<x2,y2»e7?fi«x2,y2>,<x3,y3>>eR时

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

La+%=无3+%(2)

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

即Xl+X=无3+月

故<<演,必〉,<》3，>3>>€R•••/?有传递性

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

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

九、10%

,0100、

1010

MR

000i

1、000关系图

1010、

0101

M产=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产+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)}

对xedomh若有y,为使得

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

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

：.feg也是函数。

2、证明：

"n"荀有一左峋，则对VreTgo/(r)=r

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

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

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

此时令g(s)=f，若s《/(T)令g(s)=cwT

则对WseS,g(s)只有一-个值t或c且苟⑺=s

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

即若/入射，必能构造函数?，使g为/左逆函数。

试卷四试题与答案

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

1、若P,Q,为二命题,P-0真值为0当且仅当o

2、命题“对于任意给定的正实数，都存在比它大的实数”令F（x）：x为实数，

L（x,y）:x>y则命题的逻辑谓词公式

为。

3、谓词合式公式VxP（x）fAQ（x）的前束范式

为o

4、将量词辖域中出现的和指导变元交换为另一变元符号，公式其余

的部分不变，这种方法称为换名规则。

5、设x是谓词合式公式A的一个客体变元，A的论域为D,A（x）关于y是自由的，则

_______________________________________被称为存在量词消去规则，记为

ES,

二、选择25%（每小题2.5分）

1、下列语句是命题的有（）。

A、明年中秋节的晚上是晴天；B、x+y〉°；

C、町>°当且仅当x和y都大于0；D、我正在说谎。

2、下列各命题中真值为真的命题有（）。

A、2+2=4当且仅当3是奇数；B、2+2=4当且仅当3不是奇数；

C、2+2r4当且仅当3是奇数；D、2+2关4当且仅当3不是奇数；

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

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

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

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”的有效结论

C、当且仅当A|AA2/V-A4“A8OE；口、当且仅当

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

6、A,B为二合式公式，且AO8,则()。

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

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

7、“人总是要死的”谓词公式表示为()。

(论域为全总个体域)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为：个体域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))3xP(x)vBxQ(x).

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

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

10、下列推理步骤错在()。

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

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

③★产(x)p

④*y)ES③

⑤G(y)T②④1

⑥HxG(x)EG⑤

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

三、逻辑判断30%

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

型。(10分)

2、下列问题，若成立请证明，若不成立请举出反例：(10分)

(1)已知4\/。08"。，问408成立吗？

(2)已知「40」8,问403成立吗？

3、如果厂方拒绝增加工资，那么罢工就不会停止，除非罢工超过一年并且工厂撤换了

厂长。问：若厂方拒绝增加工资，面罢工刚开始，罢工是否能够停止。(10分)

四、计算10%

1、设命题A”A2的真值为1,A3,A4真值为0,求命题

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

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

五、谓词逻辑推理15%

符号化语句：“有些人喜欢所有的花，但是人们不喜欢杂草，那么花不是杂草”。并推证

其结论。

六、证明：(10%)

设论域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、约束变元；5、三也(幻=>4>),y为D的某些元素。

H—、选择25%(每小题2・5分)

题目1