历年离散数学试卷(参考答案)

历年离散数学试卷选编（参考答案）

目录

试卷一.............................................................1

试卷二.............................................................5

试卷三............................................................10

试卷四............................................................16

试卷五............................................................19

试卷六............................................................24

试卷七............................................................27

试卷八............................................................31

读书是掌握知识的捷径，勤奋是开启知识大门的钥匙,

思考是理解知识的利器，练习是巩固知识的方法，

讨论是理解知识的妙招，探求是创新知识的途径。

试卷一

一、单项选择题（本大题共10小题，每小题2分，共20分）

1.下列不是命题的是［C］o

A.7能被3整除.

B.5是素数当且仅当太阳从西边升起.

C.x加7小于0.

D.华东交通大学位于南昌北区.

2.设p:王平努力学习，q:王平取得好成绩，命题“除非王平努力学习，否则他不

能取得好成绩”的符号化形式为［D

A.plqB.->p与q

C.->q->pD.q->p

3.下面4个推理定律中，不正确的为［D］o

A.A=>(AVB)(附加律)8.依"8)八「人=>8(析取三段论)

C.(AfB)/\A=>B(假言推理)D.(A1B)A-,B=>A(拒取式)

4.设解释I如下，个体域D={1,2},F(l,1)=(2,2)=0,F(1,2)=F(2,1)=1,在解释I下，下

列公式中真值为1的是［A］o

A.VxmyF(x,y)B.SxVyFfx^)

C.VxVyF(x,y)D.-3xmyF(x,y)

5.下列四个命题中哪一个为真？［D］。

A.0G0B.0G{a}

C.0e{{0}}D.0c0

6.设S={a,b,c,d},R={<a,a>,<b,b>,<d,d>},则R的性质是［B］□

A.自反、对称、传递的B.对称、反对称、传递的

C.自反、对称、反对称的D.只有对称性

7.设A={a,b,c},则下列是集合A的划分的是［D］。

A.{{b,c},{c}}B.{{a,b},{a,c}}C.{{a力},c}D.{{a},{b,c}}

8.设集合2(、历)={"+”后心，'62})关于普通数的乘法，不正确的有［C］。

A.结合律成立B.有幺元

C.任意元素有逆元D.交换律成立

9.设A是非空集合，P(A)是A的嘉集，n是集合交运算，则代数系统〈P(A),n〉

的幺元是［C］o

A.P(A)B.0C.AD.E

10.下列四组数据中，不能成为任何4阶无向简单图的度数序列的为［C］。

A.2,2,2,2B.1,1,1,3

C.1,1,2,3D.1,2,2,3

二、填空题(本题共10小题，每小题2分，共20分)

1.命题公式plq的真值为假，当且仅当P=l,q=0。

2.公式p~>(q~>r)在联结词全功能集{-1,A,v}中等值形式之一为「pviqvr。

3.谓词公式-iVxF(x)fmxG(x)的前束范式为Vxmv(-iF(x)—>G(v))。

4.设集合A={1,4},B={2,4},则P(A)-P(B)=。

5.R是非空集合上的偏序关系，当且仅当R具有自反性、反对称性、传递性。

6.设函数f(x)=x+l,g(x)=2x2,贝fog=2x2+1。

7.设0=(134)(256),1=(25)(1643),则or=(l)⑵⑶(465)。

8.命题"设G为任意的n阶简单的哈密尔图,则Vu,vGV(G),均有d(u)+d(v)>nw

的真值为0。

9.无向连通图G是欧拉图，当且仅当G中每一个顶点的度数都为偶数。

10.设树T有m个顶点，n条边，则T中顶点与边的关系为m=n+l。

三、证明下式(6X2=12分)

1、判断下面推理是否正确。

如果你学习，那么你离散数学不会不及格。

如果你不热衷于玩游戏，那么你将学习。

但你离散数学不及格。因此你热衷于玩游戏。

你学

设

习

3>你离散数学及格，r:你热衷于玩游戏，则

中

前P:

提.(

结

论.pr-

证

明.①T

p-q前提引入

「

@-p前提引入

(3)-「①②拒取式

@-「

⑨r{-前提引入

「③④拒取式

@rr置

2、在一阶谓词逻辑中构造下面推理的证明。

前提：3xF(x),Vx(F(x)VG(x)^H(x))

结论：3xH(x)

证明：①mxF(x)前提引入

②F(a)①工

(3)Vx(F(x)VG(x)^H(x))前提引入

④F(a)VG(a)今H(a)③V-

⑤F(a)VG(a)②附加

⑥H(a)④⑤假言推理

⑦mxH(x)©3+

四、用等值演算法求公式((pVq)A(plq))—(qTp)的主合取范式与主析取范式。

(10分)

解：原式O((pVq)A(-ipVq))C(q~>p)

O((pA--p)Vq)O(q^p)

oq—(qTp)

=(qT(qTp))A((qTp"q)

=JqVJqVp))A(->(->qVp)Vq)

O(-.qVp)A((qA-,p)Vq)

=(->qVp)/\q

opAq

=n（3）---------------主合取范式

U*E（0,1,2）---------------主析取范式

五、设R1和R2是集合X={0,l,2,3,4}上的关系，

Ri={<x,y>|y=2x},R2={<x,y>|x=y+1}

写出Ri、R2,写出R2的关系矩阵，并求出R/R2。（8分）

解：RI={<0,0>,<1,2>,<2,4>},R2={<1,O>,<1,2>,<2,3>,<3,4>},

R2的关系矩阵：（略）

RI°R2={<X,y>Iy=2（x-l）}

六、设集合A={2,3,4,6,8,12,24},R为A上的整除关系，

（1）画出偏序集<A,R>的哈斯图；

⑵出集合A中的最大元、最小元、极大元、极小元；

（3）写出A的子集B={2,3,6,12}的上界、下界、最小上界、最大下界。

分）

解：⑴哈斯图：

（2）A中的最大元：24,最小元：无，极大元：24,极小元：2、3

⑶B={2,3,6,12}的上界：12、24,下界：无，最小上界：12,最大下界：无

七、设Z为整数集合，在Z上定义二元运算*,Vx,yWZ有

y=x+y—2a证明：<z,*>是一个群。（io分）

证明：显然，二元运算*满足交换律。

（1）封闭性：Vx,yGZ,显然X*y=%+y—2ez。

(2)结合律：Vx,y,zez,

(x*y)*z=(x+y-2)*z=x+y-2+z-2=x+y+z-4

x*(y*z)=x*(y+z-2)=x+y+z-2-2=x+y+z-4

(x*y)*z=x*(y*z)

故二元运算*满足结合律。

(3)设e£Z,VxGZ,使得x*e=x,即x+e-2=x,e=2,故幺元e=2.

(4)VxGZ,设yGZ,使得x*y=e,即x+y-2=2,y=4-x,故x-i=4-x。

综上所述，＜Z,*＞是一个群。

八、平面图G有两个连通分支，其顶点数为12,边数为34,问G有多少个面?

(6分)

解：设有x个面，根据欧拉公式：

12-34+x=2+l,

即x=25

所以，G有25个面。

九、对下图，

(1)求其邻接矩阵；

(2)(2)长度小于3的通路和回路的总数。(6分)

解题思路：先写出邻接矩阵A,然后求A2,则矩阵A+A2中元素之和，即为长度

小于3的通路条数【10条】；而A+A2对角线上元素之和，即为长度小于3的回

路条数【0条】。

大学是一个人的“精神账户"，你一辈子都要不断回来"提款"的。

试卷二

一'单项选择题(2分X10=20分)

、下列语句是命题的有[

1B]0

A./+2y>1;B.2010年的国庆节是晴天;

C.青年学生多么朝气蓬勃呀！D.学生不准吸烟!

2、在命题逻辑中，任何命题公式的主合取范式都［C］o

A.不一定存在；B.不存在；

C.存在且唯一；D.存在但不唯一.

3、设S={1,2,3,4},R={<1,1>,<3,3>,<4,4>},则R满足的性质是［C］

A.自反、对称、传递的；B.自反、对称、反对称的；

C.对称、反对称、传递的；D.只有对称性.

4.与命题pA(pVq)等值的公式是［A］o

A.p；B.q；C.pVq；D.pAq.

5.设M={a,b,c},M上的等价关系R={<a,a>,<b,b>,<c,c>,<b,c>,<c,b>}确定的集

合M的划分是［D］0

A.{{a},{b},{c}}B.{{a,c},{b,c}}C.{{a,c},{b}}D.{{a},{b,c}}

6.设D：全总个体域，F(x)：x是花，M(x)：x是人，H(x,y)：x喜欢y,

则命题“每个人都喜欢某种花”的逻辑符号化为［C］。

A.Vx(M(x)A3J(F(J)->H(x,j))；

B.Vx(M(x)T->H(x,y))；

C.Vx(M(x)->3J(F(J)AH{x,y))；

D.3x(M(x)Vy(F(y)AH(X,y)).

7.下列图中，不是哈密顿图的为［A］o

8.下列四组数据中，能作为某个4阶无向简单图的度序列的为［D］o

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

9.一棵无向树T有8个顶点，4度、3度、2度的分枝点各1个，其余顶点

均为树叶，则T中有［C］片树叶。

A.3；B.4；C.5；D.6.

10.下面偏序集［B］能构成格。

BCD

二、填空题(2分X10=20分)

1.当p=O,q=O时，命题公式P~»(PACI)的真值为1。

2.设p:我努力学习，q:我取得好成绩，命题“除非我努力学习，否则我不能

取得好成绩」的符号化形式为qlP。

3.设解释I如下，个体域D={1,2},F(l,1)=(2,2)=0,F(1,2)=F(2,1)=1,在解释I下，

3xF(x,2)的真值为1。

4.谓词公式3XF(X)A3XG(X)的前束范式为mxmv(F(x)八G(v))。

5.设树T有n个顶点，m条边，则T中n与m的关系为m=n-10

6.等价关系满足自反性、对称性和传递性三个性质。

7.设函数f(x)=2x,g(x)=x2+l,则foq=2x?+2。

8.无向连通图G是欧拉图，当且仅当G中每一个顶点的度数都为偶数。

9.设|A|=3,则A上有29个二元关系。

10.设A为非空有限集，则代数系统＜P(A),U＞中的幺元为0o

三、综合题(第1、2、4题10分，第3、5、7每题8分，第6题6分，共60

分)

1.构造下面推理的证明：(10分)

前提：pf(qvr),-iS-^―if9pA_15;

结论：q.

证明：①p人-15前提引入

②P①化简

③「S①化简

④-is-前提引入

⑤-1r③④假言推理

⑥p—(qvr)前提引入

⑦qvr②⑥假言推理

⑧q⑤⑦析取三段论

2.用等值演算求下面公式A的主析取范式和主合取范式，并列出A的成真赋值:

(10分)

A=(pfq)A(q-*r)

解：A=(pfq)A(qfr)

=(-ipvq)A(-)qvr)

=((-ipvq)v(rA-ir))A((pA-ip)v(-iqvr))

=(-ipvqvr)A(-ipvqv-ir)A(pv-iqvr)A(-ipv-iqvr)

=M4AM5AM2AM6

=11(2,4,5,6)---------------------------------主合取范式

=Z(0,1,3,7)---------------------------------主析取范式

A的成真赋值：000,001,011,111

3.设集合A={a,b,c,d}上的二元关系

R={<azb>,<b,a>,<b,c>,<c,d>},

求：(1)指出关系R满足的性质；(2)求出R的自反闭包、对称闭包。(8分)

解：(1)R满足：反自反性

(3)R的自反闭包：r(R)={<a,a>,<b,b>,<c,c>,<d,d>,<a,b>,<b,a>,<b,c>,<

c,d>}

R的对称闭包：s(R)={<a,b>,<b,a>,<b,c>,<c,b>,<c,d>,<d,c>}

4.设5={1,2,3,4,6,8,12},“为S上的整除关系。(10分)

问：(1)偏序集<S工>的Hass图如何？

(2)偏序集<S，<>的极小元、最小元、极大元、最大元是什么？

(3)在偏序集<S，<>中，5={4,6}的上确界、下确界是什么？

解：(1)哈斯图：

(2)<SW>的极小元：1,最小元：1,极大元：8、12,最大元：无。

(3)8={4,6}的上确界：12,下确界：2o

5.已知某有向图G的邻接矩阵如下：（8分）

%,1210、

0010

匕0101

,4ko010,

问：（1）画出图Go

（2）试用邻接矩阵求G中长度小于等于2的通路的条数，其中回路有

几条？

（3）该图是为强连通图还是弱连通图？

解：（1）（略）

（2）长度小于等于2的通路的条数：22,其中回路数：5.

（3）弱连通图。

6.设集合G={3"MeZ}（其中：义是普通乘法,Z是整数集），对代数系统＜G,x＞,

说明：（1）是否满足封闭性、结合律？（2）是否存在幺元？（3）是否构成群？

（6分）

mXnm+n

解：（1）满足封闭性。Vm,nGZ,33=3GZo

满足结合律：Vm,n,kGZ,（3mX3n）X3k=3mX（3nX3k）=3m+n+k。

（2）幺元为3。=1。

（3）由于VnCZ,（3n）T=37

综合（1）（2）知，＜G,x＞构成群。

7.图G是一个简单的连通平面图，其无限面的度数为5,其余面都为三角形，

结点为8,请通过计算求平面图G的边数和面数。（8分）

解：设平面图G的边数和面数分别为：e、f,则

8-e+f=2,

5+3（任i）=2e,

解上述方程得：e=i6,f=io0

所以，平面图G的边数为16,面数为io。

世上天难事，只要肯登攀。——毛泽东

试卷三

一'单项选择题(每题2分，共20分)

下列语句是命题的有

1.［B］0

A.请保持安静！B.2019年元旦是星期六；

C.xW6；D.今天是星期五吗？

下面哪个命题公式是重言式

2.［B］o

A.(pfq)八(qfr)；B.pf(qfp)；

C.(—ipVA—I(j9A—iq)；D.Tp7GdpQ

下列二元关系中，具有传递性的二元关系是

3.［A］o

A.{<a,b>}B.{<a,b>,<b,a>}

C.{<azb>,<b,c>}D.{<a,a>,<azb>,<b,a>}

4.若A={a,b,c},则下列集合中，［C］是人的划分。

A.{①,{a},{b,c}}B.{{a,b},{b,c}}

C.{{a},{b},{c}}D.{{a},{b}}

5.N是自然数集，定义N"(x)=xmod3(即x除以3的余数)，则

函数，是

［D］0

A.满射非单射；B.单射非满射；

C.双射；D.非单射非满射

6.下面集合［C］关于减法运算不是封闭的。

A.Z；B.{2x|XGZ}C.{2x+l|xeZ}D.{0}

设是实数集合，为普通乘法，贝

7.R“x”!|<R,x>［B］o

A.是群；B.是独异点，不是群；

C.是半群，不是独异点；D.是代数系统，不是半群

8.下图中既不是Eular图，也不是汉密尔顿图的是［B］。

(A)3)(C)15

9.如左下图，相对于5阶无向完全图也的补图为［］o［本题图错误］

[A][D]

10.给定无向图G=<匕石>,下面哪个顶点子集是图G的点割集［A］o

D.｛匕,匕｝

二'填空题(每题2分，共20分)

1.设F(x)：x是人；G(x)：x会犯错误，则在谓词逻辑中，命题“没有不犯

错误的人”谓词符号化为「班〃(工)人「6(%))或_\/%(依%)->6(%))o

2.设解释I如下，个体域D={1,2},P(x)：x=l,Q(x)：x=2,在解释I下，

公式3xP(x)-X/xQ(x)的真值为go

3.谓词公式3xP(x)T\/xQ{x,y)的前束范式为_X/xX/z(P(x)tQ(Z,y))_。

4.若A=0>,6=®,®}},则8—P(A)={®}}。

5.若A={a,b,c,d},A上的等价关系R={<a,b>,<b,a>,<c,d>,<d,c>}UlA,则

A在等价关系R下的商集A/R=Ua,bHc,d)}o

6.若Z为整数集合，“x”为普通乘法，代数系统<Z,x>中，则Z关于“x”

运算的幕等元有0,1。

7.设人=白，b,c},A上二元运算*如下：

*abc

acab

abc

cIbca

则代数系统＜A,*＞中，元素a的逆元为c。

8.设G={0,1,2,3},㊉4为模4力口法，即Vx,yeG,x㊉/=（x+y）mod4,贝!|＜G,

㊉4＞为循环群，该循环群的生成元为_LJ_。

9.n个结点的无向完全图K”为欧拉图的条件是n为奇数。

10.若无向树T有1个3度结点，3个2度结点，其余结点都是树叶，则该

树有3片树叶。

三、综合题（共60分）

1.在自然推理系统中，构造下面推理的证明。（6分）

如果王菲是理科生，那么她一定学过高等数学；如果她不是文科生，

她一定是理科生；她没学过高等数学，所以她是文科生。

设P：王菲是理科生，q：王菲学过高等数学，r：王菲是文科生

前提：p-q，-1r^p,-＞q

结论：r

①

②前提引入

③前提引入

④①②拒取式

⑤前提引入

⑥③④拒取式

⑤置换

2.在命题逻辑中，构造下面推理的证明：（8分）

前提：r）,qr（p/\7）,tf—r

结论：qfT

证明：①q附加前提

②qr（pMT）前提引入

(3)pA―iS①②假言推理

@p③化简

⑤pf(-1<7Vr)前提引入

⑥—vr④⑤假言推理

⑦r①⑥析取三段论

⑧―前提引入

⑨T⑦⑧拒取式

3.求公式-9)v(。->〃)△r)的主析取范式、主合取范式，及该公式的成

假

赋值。(8分)

解：原式o-i(可vq)▽(—"「)△一)

=(p/\—>4)vr

o(pvr)A(—vr)

=((〃vr)vA—>q)A(〃A-ip)v(—vr))

<z>(pv^vr)A(pv—iqvr)A(pv—\qvr)v(~pv—\qvr)

=M()AM2AM2AM6

oE[(0,2,6)------------------------------主合取范式

02(1,3,4,5,7)------------------------------主析取范式

成假赋值：000,010,110

4.设集合A={a,b,c},R是A上的二元关系，已知R的关系矩阵为(8分)

'100'

M=011

011

(1)并画出R的关系图；

(2)求出IV的集合表达式；

(3)说明R具有哪些性质。

解：(1)(略)

(2)R2={<1,1>,<2,2>,<3,3>,<2,3>,<3,2>}；

⑶自反性，对称性，传递性

5.设5={1,2,3,6,12,18,36},设“W”为S上的整除关系。(8分)

问：(1)画出偏序集〈S,的哈斯图。

(2)在偏序集〈S,中，B={2,3,6}的极大元、极小元分别是什么？

(3)在偏序集＜S,W＞中，C={6,12,18}的最小上界、最大下界分别

是什么？

解：(1)哈斯图：

(2)B={2,3,6}的极大元：6,极小元：2、3。

(3)C={6,12,18}的最小上界:36,最大下界：6。

6.设＜G,*＞是群。若在G上定义运算・，使得对于Vx,yeG,有：x»y=y*xo

证明：〈G,・〉是群。(8分)

证明：(1)满足封闭性。Vx,yeG,由于＜G,*＞是群,满足封闭性，有:x・y=y*xeG。

(2)满足结合律。由于＜G,*＞是群，满足结合律，贝!!Vx,yfzeG,

(x»y)・z=(y*x)・z=z*(y*x)=z*y*x,

x・(y・z)=x・(z*y)=(z*y)*xy=z*y*x.

(3)设e是＜G,*＞的幺元，则VxeG,

x^e=e*x=x,e＞x=x*e=x

即e也是〈G,・〉的幺元。

（4）VxeG,设x在＜G,*＞中的逆元是y,则

x.y=y*x=e,y»x=x*y=e

即y也是〈G,・〉中x的逆元。

综上所述，〈G,・〉是群。

7.已知有向图G的邻接矩阵如下：（8分）

010口匕

0011%

A=

010°匕

100山

问：（1）画出图Go

（2）试通过邻接矩阵A求图G中长度等于2的通路总数。

（3）试求图G的可达性矩阵。

⑷该图是否为强连通图?

解：（1）（略）

（2）13条

（3）（略）

（4）是强连通图

8.设图G为八个顶点m条边的连通平面图，且每个面的次数至少为4,

证明：n?^2n-4o（6分）

证明：设棉数为f,根据欧拉公式和平面图的握手定理：

n-m+f=2,

4代2叫

解之得：

人生像一截木头，或者选择慢慢腐朽，或者选择熊熊燃烧。

试卷四

一'单项选择题（每小题2分，共20分）:

1.下列选项中与人1^=人等价的是

A.AAB=AB.A—B=0C.AUB=BD.BcA

2.下列语句是命题的有（C）o

A.明年元旦会是晴天吗？B.x+y>°；

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

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

则R具有（D）性质。

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

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

4.如图，给出格L,则e的补元是［B］0

5.公式A=h（P（x）-Q（x））的解释［为:个体域D={2},P（X）：X>3,Q（X）：X=4

则A的真值为（A）o

A.1；B.0；C.可满足式；D.无法判定。

6.在下述公式中（C）为矛盾式

A.（尸入Q）f（PvQ）；B.-fQ》（Q-P））；

C.TPfQMQ；D.PfQQ）。

7.无向图的关联矩阵中，每列的元素之和为一Bo

A.边数的2倍B.2C.该图的顶点总数D.对应顶点的度数

8.5阶无向完全图(％)不是以下哪种图？—Co

A.欧拉图B.简单图C.二部图D.哈密顿图

9.下面哪一种图不是树？C

A.无回路的连通图B.有n个结点，n-l条边的连通图；

C.每对结点间都有初级通路的图；D.连通但删去一条边则不连通的

图。

10.5阶无向完全图心的边数为(B)0

A.5B.10C.15D.20

填空题(每小题2分，共20分)

1.设P：我生病，Q：我去上课，命题“虽然我生病，但我还是去上课了”符

号化为PAQ。

2.R为实数集合，若，和g都是R-R的函数，且/(x)=x+l,g(x)=2x,则fog

(2)=-5—o

3.设集合A={a,b},B={a,c},则A©(B-A)={a,b,c}—。(㊉为对称差)

4.若关系R={<1,2>,<2,1>},则其传递闭包t(R)为。

5.设A={a,b,c,d},A上的等价关系R={<a,c>,<c,a>}U以,则商集

A/R=Ha,c},{b},{d}}o

6.公式*F(x,y)人一iVvG(v)的前束范式是孔加(F(x,z)人一iG(v))。

7.设M(x):x是人，F(x):x吃饭。在一阶逻辑中，“没有不吃饭的人”符号化形

式为Vx(M(x)-F(x))。

8.完全二部图4,3是平面图，它的平面嵌入共有—3_个面。

9.一个无向图有4个结点，4条边，其中的3个顶点度数分别为1,2,3,则

第4个结点度数一定是，

10.设$={1,2,3),S上定义的二元运算*如表所示，S中关于*运算的零元

是1。

*123

1111

2123

3132

2.证明等值式：Q-(PA(Q-P))OPV「Q,并求该命题公式的成真赋值。

证明：（略）

3.一棵树T中，有3个2度结点，一个3度结点，其余结点都是树叶。

（1）T中有几个结点；

（2）画出具有上述度数的所有非同构的无向图。

解：（1）设有x个结点，则

3x2+3+（x-4）=2（x-l）,

解之得：x=7.

⑵（略）

4.在命题逻辑中符号化以下文字，并证明其推理是正确的：

“如果厂方拒绝给工人增加工资并且工厂不更换厂长，那么罢工就不会停止。

因此，如果罢工停止，则要么厂方给工人增加了工资，要么更换了厂长。”

5.设集合A={1,2,3,5,6,7,15,35},R为整除关系。

（1）画出偏序集＜A,R＞的哈斯图；

（2）写出A的最大元，最小元；

（3）写出A的子集B={1,3,5}的上界，下界。

解：（1）哈斯图：

（2）最大元：无,最小元：1

（3）B={1,3,5}的上界:15,下界：1

’1000、

6.设有向图G的邻接矩阵为：1011

1001

、1000,

（1）画出该图;

（2）求该图中长度为2的通路总数。

（3）该图是为强连通图还是单向连通图？

（4）判断该图是否为欧拉图？说明理由。

解：（1）（略）

（2）8；（3）单向连通图；（4）不是。

7.设集合S=R—{-l}（R为实数集），a*b=a+b+ab。

（1）证明<S,*>是群；

（2）在S中解方程：x*4=5o

（略）

逆境能打败弱者而造就强者。——尼克松

试卷五

一'单项选择题（每题2分，共20分）

下列语句是命题的有

1.［B］0

A.请保持安静！B.2011年元旦是星期六；

C.x2+y^0；D.今天是星期五吗？

下面哪个命题公式是矛盾式

2.［D］o

A.（pfq）八（qfr）；B.pf（qfp）；

C.（—ipx/q）A—1（〃A—;D.—i（p\/q）Ap。

下列二元关系中，不具有传递性的二元关系是

3.［C］0

A.{<a,b>}B.{<a,a>,<a,b>,<b,a>,<b,b>}

C.{<a,b>,<b,c>}D.{<a,b>,<a,a>}

4.若人=国力通},则下列集合中，［A］不是A的划分。

A.{①,{a},{b,c}}B.{{a},{b,c}}

C.{{a},{b},{c}}D.{{a,b},{c}}

是自然数集，定义厅则函数，是［

5.Nf:NfN（x）=x,C］o

A.满射非单射；B.单射非满射；

C.双射；D.非单射非满射

6.下面集合［C］关于加法运算不是封闭的。

A.Z(整数集合)；B.{2x|XGZ}C.{2X+1|XGZ}D.{0}

7.设R是实数集合，“+”为普通乘法，则<R,+>［B］o

A.是群；B.是独异点，不是群；

C.是半群，不是独异点；D.是代数系统，不是半群

8.下列四组数据中，不能成为任何图的度数序列的为［C］o

A.1,1,1,3B.2,2,3,3

C.1,2,2,2D.1,2,3,4

9.无向图的关联矩阵中，每列的元素之和为［B］。

二'填空题(每题2分，共20分)

1.设Hx)：x是人；G(x)：x会犯错误，则在谓词逻辑中，命题”所有的人

都会犯错误”谓词符号化为o

2.设解释I如下，个体域D={1,2},P(x)：x=l,Q(x)：x=2,在解释I下，

公式

VxP(x)->3x(2(x)的真值为o

3.谓词公式3xP(x,y)AV%2(x)的前束范式为*Vz(P(x,y)AQ(Z))_。

4.若4=中,8={。,®}},则B—A=,

5.若A={a,b,c},A上的等价关系R={<a,b>,<b,a>}UlA,则A在等价关系R

下的商集A/R=Ha,b},{cH

6.若Z为整数集合，+为普通加法，代数系统<Z,+>中，则Z关于+的塞

等元有0。

7.设A={a,b,c},A上二元运算*如下:

则代数系统＜A,*＞的零元为b

8.设G={0,1,2,3},㊉4为模4加法,§PVx,yeG,x©4y=（x+y）mod4,则＜G,

㊉广为循环群。该循环群中，元素2的阶为一2_o

9.n个结点的无向完全图K„的边数为若3___________。

10.若无向树T有1个3度结点，2个2度结点，其余结点均为树叶，则该

树有3片树叶。

三、综合题（共60分）

1.在自然推理系统中，构造下面推理的证明。（6分）

如果今天天晴，那么我将去爬山；今天天晴，所以我将去爬山。

设P：今天天晴，q：我将去爬山，则

前提：pfq,p

结论:q

证明：①Pfq前提引入

②p前提引入

③q①②假言推理

2.在命题逻辑中，构造下面推理的证明：（8分）

前提：pf-qvr）,qTp,rfs

结论：qTs

证明：①q附加前提引入

②qfp前提引入

自姓①②假言推理

④p->Jqvr)前提引入

⑤"r③④假言推理

⑥r①⑤析取三段论

⑦，->s前提引入

⑧s⑥⑦假言推理

3.求公式->4)vr的主析取范式、主合取范式，及该公式的成假赋值。(8

分)

解：原式O-<「pvq)vr

=(p/\—1〃)\/厂

=(pvr)A(-iqvr)

=((pVr)VA—1乡)A(j9A—p)v(—vr))

^(pvqvr)/\(pv—iqvr)A(pv—\qvr)A(~pv—vr)

=MOAM2AM2AM6

=n(0,2,6)-----------------------------主合取范式

=E(1,3,4,5,7)----------------------------主析取范式

成假赋值：000,010,110

4.设集合A={a,b,c},R是A上的二元关系，已知R的关系矩阵为(8分)

100

M=001

011

(1)并画出R的关系图；

⑵求出R2的集合表达式；

(3)说明R具有哪些性质。

解：⑴(略)

(2)R2={<1,1>,<2,2>,<3,3>,<2,3>,<3,2>}

⑶满足：对称性

5.设$={1,2,3,4,6,9),设"<”为S上的整除关系。(8分)

问：(1)画出偏序集<S,的哈斯图。

(2)在偏序集＜S,4＞中，B={2,3,6}的最大元、最小元分别是什么？

(3)在偏序集〈S,《＞中，C={1,2,3}的上界、下界分别是什么？

解：(1)哈斯图:

4

2

1

(2)B={2,3,6}的最大元：6,最小元：无;

(3)C={1,2,3}的上界：6、9,下界：lo

6.设＜G,+＞是群。G为整数集合，+为普通加法运算，证明：〈G,+〉是群。(8

分)

(略)

7.已知有向图G的邻接矩阵如下：(8分)

'01"％

A=110v2

01ojv3

问：⑴画出图Go

(2)试通过邻接矩阵A求图G中长度等于2的通路总数。

(3)试求图G的可达性矩阵。

⑷该图是否为强连通图？

解：(1)(略)

'120'

(2)A2=121

110

长度为2的通路数：9

-111

(3)P=111

111

(4)强连通图

8.图G是一顶点数为6的简单的连通的平面图，有2个面的次数为4,其余

面的次数都为3,求平面图G的边数和面数。(6分)

解：设G的边数为e,面数为f,则根据欧拉公式和握手定理，有：

6-e+f=2,

4x2+3(f-2)=2e

解上述方程式得：e=10,f=6,即图G的边数为10,面数为6。

能够快乐地学习和工作，这是精神上优秀的征兆。

试卷六

一、选择题(每题2分，共20分)

1.下列句子为简单命题的是[D]0

A.禁止吸烟！B.王红既聪明又美丽。

C.我正在说谎。D.小王和小李是好朋友。

2.设D：全总个体域，F(x)：x是优点，M(x)：x是人，H(x,y)：x有y,则命

题“每个人都有一些优点。”的逻辑符号化为[C]o

A.Vx(M(x)A3y(F(y)->H(x,y))

B.Vx(M(x)t寺(尸(y)->H(x,y))

C.Vx(M(x)3y(F(y)AH(X,y))

D.3x(M(x)TVy(尸(y)AH(X,y))

3.下面命题公式是矛盾式的为[C]0

A.〈p/\q)7PB.「pvq

C.Tpfq)八qD.-q)

4.已知某班有35人，其中10人学习日语，20人学习英语，5人既学日语又学

英语，那么既不学日语也不学英语的人数是［B］。

A.5B.10C.15D.20

5.Z是整数集合，定义fZ"(x)=f,则函数£是［C］。

A.满射非单射B.单射非满射

C.双射