离散数学复习题与参考答案

离散数学复习题与参考答案

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

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

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

偶数)贝U。

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

3.设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.设A={1,2,3,4},A上关系图为

则R2=

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

贝ijR=

a

8.图的补图为

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

*abcd

aabcd

bbcda

ccdab

ddabc

那么代数系统＜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、设人={1,2,3},则A上的二元关系有（）个。

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

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|=[^|}则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上包含关系的哈斯图为()

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

{1,2,3}

■{1,3}fib

(J)

(C)(D)

7、下列函数是双射的为()

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

8、图中从”到V3长度为3的通路有()条。

0；B.1；D.3o

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

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都是群＜G|＞★＞到＜62,*＞的同态映射，证明＜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规则证明下题(每小题8分)

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

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

五、计算18%

I、设集合A={a,b,c,d}上的关系R={va,b>,<b,a>,<b,c>,<c,d>}用矩阵运

算求出R的传递闭包t（R）。（9分）

2、如下图所示的赋权图表示某七个城市匕，匕，…，匕及预先算出它们之间的一些直接

通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。（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(a)*尸㈤=g(a)*g(b~l)=g(a^b-')

•"★L€C.-.<c,★>是<6],*>的子群。

3、证：

2e=£d(Fj)Nrk.丝

①设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

⑥DvET⑤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)算法求产生的最优树。算法略。结果如图：

树权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、设S={a］，a?,ag},Bj是S的子集，则由B31所表达的子集是

/?

3、设A={2,3,4,5,6}上的二元关系={<%，^>1%<y丫》是质数},则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、公式（PvJPAQ））人（（「PvQ）A的根树表示为

二、选择20%（每小题2分）

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

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

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

2、命题公式（「P一。）-（「Qv尸）中极小项的个数为（）,成真赋值的个

数为（）o

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

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

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

4、设5={1,2,3},定义SxS上的等价关系

R={«a,b>,<c,d>\<a,b>eSXjd>£SxS,a+d=b+c}贝“山R产

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

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

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

则R具有（）性质。

A.自反性、对称性、传递性；B.反自反性、反对称性;

C.反自反性、反对称性、传递性：D.自反性。

6、设+，。为普通加法和乘法，则（）＜$，+，。＞是域。

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、下面偏序集（）能构成格。

8、在如下的有向图中，从V1到V4长度为3的道路有（）条。

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

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

三、证明46%

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

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

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

2、用逻辑推理证明：

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

（11分）

3、若-8是从A到B的函数，定义一个函数g2"对任意be8有

gS）={x|（xeA）△（/（k）=0},证明：若f是A到B的满射，则g是从B到

2A的单射。（10分）

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

—1）（〃—2）+2

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

Hamilton图（8分）

四、计算14%

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

试求出<Z6,+6>的所有子群及其相应左陪集•（7分）

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

2、11分

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

上述句子符号化为：

前提:Vx(P(x)->2(x))>S(a)AP(a)结论：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)，由于偃函数，，。尸。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分

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

连通分支G|、G2,使得u和v分别属于Gi和G2，于是Gi和G2中各含有1个奇数

度结点，这与图论基本定理矛盾，因而u,v一定连通。

5、8分

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

反证法:若存在两结点u,v不相邻且4(〃)+火式”"-1,令匕={〃)},则6与1

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

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

n-22

,1、

m2—(n—2)(〃-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]}，{口]};{[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、设f，g是自然数集N上的函数VxeN，/(x)=x+l,g(x)=2x,

则/。g(x)=.

2^设人={@,b,c},A上二元关系R={〈a,a>,<a,b>,<a,c>,<c,c>},

则s(R)=o

3、A={1,2,3,4,5,6},A上二元关系7={<元>>1x+y是素数},则用列举

法

T=；

T的关系图为

____________________________________;

T具有性质。

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、设P(x)：x是素数，E(x)：x是偶数，0(x)：x是奇数N(x,y)：x可以整数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「的主析取范式中含极小项的个数为()。

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

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

5

5={<%,>|工,,6/八犬是丁的母亲}则5-1。/?表示关系（）o

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

B、{<x,y>|x,y€PAX是y的孙子或孙女}；

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

6、下面函数（）是单射而非满射。

2

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

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

C、于：RfZ,/（x）=[x],[x]表示不大于x的最大整数；

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

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

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

©@

则R具有（）的性质。

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

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

8、设5={中,{1},{1,2}},则有（）=5。

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

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

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

10、全体小项合取式为（）。

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

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

2、（10分）设函数g：SIT证明/—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、

反对称性、反自反性；4、{①,{{①，2}},{{2}},{{①,2},{2}}}；5、1；

6、（PviQvR）八LPYQVR）八（PvQvR）；7、任意x,如果x是素数

则存在一个y,y是奇数且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

当<",4>,<x2,y2>>e/?时即玉+乃+必也即%2+必=再+力

故<<%2，%>，</，为》€宠…R有对称性

v<

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

当<<花，%>,<x2,y2»e??K«x2,y2>,<x3,y3>>eR时

即卜+乃=+H(1)

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

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

即为+为=七+M

故<<Xi，M>,<当,力>>e«…R有传递性

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

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

九、10%

’0100、

1010

MR=

0001

<°00°J；关系图

"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)是函数，有y=>2即Wxedomh有唯一>使得y=h[x}

二/eg也是函数。

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为/左逆函数。

试卷四试题与答案

填空10%（每小题2分）

1、若P,Q,为二命题，P一0真值为0当且仅当。

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

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

为。

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

为O

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

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

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

则

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

为ES«

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

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

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

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

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

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

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

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

C、当且仅当4人42△…△A.ABOP；D、当且仅当

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、下列等价关系正确的是()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、设命题A1,A2的真值为1,A3,A4真值为0,求命题

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

2、利用主析取范式，求公式[(PfQ)AQAR的类型。(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(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