离散数学试题库

精品文档设D的结点数大于1,D=<V,E>是强连通图，当且仅当()15.A.D中至少有一条

通路中至少有一条回路B.D中有通过每个结点至少一次的回路D.DC.D中有通过每个结点至少

一次的通路

在室内运动”可符合化,Q1.设P：天下大雨：他在室内运动，命题”除非天下大雨，否则他不.为

()Q-A.7PAQB.7PQ

?—?Q

D.PfC.?P2.下列命题联结词集合中，是最小联结词组的是()A.{?,}B.{?,V,A}

D.{?,A}

A,f}

C.{)3.下列命题为假命题的是(.是偶数，那么一个公式的析取范式惟一A.如果2是偶

数，那么一个公式的析取范式不惟一B.如果2是奇数，那么一个公式的析取范式惟一C.如果2是

奇数，那么一个公式的析取范式不惟一D.如果2Q(x))中变元x是()yR(y))4.谓词公式x(P(x)

V?f?A.自由变元B.约束变元C.既不是自由变元也不是约束变元D.既是自由变元也是约束变

元5.若个体域为整数集，下列公式中值为真的是()

A.x?y(x+y=O)B.?yx(x+y=O)??D.C.xy(x+y=O)

??x?y(x+y=O)

??)6.下列命题中不正确的是(.B.{x}A.xd{x}-{{x}}

?{x}-{{x}}

A=BD.A-B=??eA且x?A

xC.A={x}Ux,则22+1625x},则下列选项正确的是()7.设P={x|(x+l)Q={x|xW4},A.P?QB.P?Q

D.Q=P

P

C.Q?)8.下列表达式中不成立的是(.C)B)n?c)(An?nB.A(BC)=(AB)A.AU(B?C)=(A

U?(AUC)B)C=(AD.(A-B)XXXC)-(BXC=(AXC)?(BXC)C.(A?

((xy?(x)(?)(P()A0)L?x))y(x,),下列说法正确的是(R.对于公式5y是约束变元.BA.y

是自由变元)？的辖域是)

,R()?.C(x的辖域是孙x(D.?)(yx?f))yQA)(P)(x((x(R)y,精品文档.

精品文档))等价的是(？{1,2},与公式(x)/(x6.设论域为A./(1)V/(2)B.41尸/(2)

D(2)

.工⑵一⑴

C./(1)A/14.下列图是欧拉图的是()

BCD

)度，那么这棵树的边数是(度点，4个2度点，其它的都是115.一棵树的3个414..13

BA16

.C.15D

、填空题。A?B=则A?A=___________,16.设A={1,2,3},

B={3,4,5}o的自反闭包r(R)=,<3,4>,<2,2>},则R设A={1,2,3,4,5},R?AXA,

R={<1,2>17.o对称闭包t(R)=。为两个命题，德摩根律

可表示为，吸收律可表示为18.设P、Q时，其真值为当论域为{1,2}：x=l,Q(x)：x=2,19.对于公

式x(P(x)VQ(x)),其中P(x)?o当论域为{0,1,2}时，其真值为

,1010????1101??-?A>,(v},若G的邻接矩阵deg,则,v,v23.设图

G<V,E>,V=[v,vi243i??0011??0010??+odeg(v)=4R={<1,2>,<3,4>,<2,2>},

上定义两种关系：A={1,2,3,4,5},在集合A25.给定集合,。则S={<4,2>,<2,5>,<3,1>,<1,3>}.

?□SQR?SR

二空超(本大1■共I。小髓.药小题2分，共20分)

c

16.0冏：.："*

|<1.2>.<2.1).(3,4).(4.3).(2.2)|0

瓜1(PVQ)O〕PA1Q或1(PAQ)O1PV1QPV(PAQ)e»P或PA(PVQ)oP

19.1020.2工+42xt721.416

立4223.3I24.五角格钻石格

25.1(1.5).(2,5).(3.2)11(1.4).(3.2).(4.2)|

精品文档.

精品文档B.A))=,4X20.设/=?f={2,4},则P(P(,

则,S={<1,3>,<2,4>,<4,2>}={1,2,3,4},上的二元关系A={<1,2>,<2,4>,<3,3>}21.设A22-1

R=)。R?S=,(均不相同，称为迹。25.若一条

中，所有的

1丸门由、处处代入2Q.ie.：(t>l1,4

Z】二22,阿贝尔”.华舜

23.3J1,2,4124.偏序侵，帧小上界初段人下界

25.路必

分，30题8题各5分，第28、296分，第、三、计算题(本大题共5小题，第2627题各共30

分)的关系图，并，画出R上的等价关系A={a,b,c,d},AR={<a,b>,<b,a>,<c,d>,<d,c>}UI26.设AA

中各元素的等价类。求出)的真值表。AQ(?P构造命题公式？(VQP)27.))PAQ-求

下列公式的主析取范式和主合取范式：P-((QP)A(?28.<a,b>,<a,e>,<b,e>,<c,e>,<d,,,

<a,c>A,R为上的关系，R={<a,d>A={a,b,c,d,e}29.设中的最大元，最小元,极大元，极小元。

A,R>的哈斯图，并求<AUe>}L试画A的G的路有几条？其中有几条回路？(2)写出4Gl如

图所示，给定图30.G()中长度为可达矩阵。

精品文档.

精品文档

三、计算题(本大共5小题,第26.27题各5分,第28、29J1各6分.第？0题8分,其3c

分)

26.解:R的关系图

*分)

[*]*[^]a1*.^.

(2分)

[c]=[dj=ic.di

27.解：

PQPVQl(PVQ)1PA1Ql(PVQ)ti(lPA；Q)(I分

分

o6011I<1

分

01收00

1给

10100

1(1分

।J'100

学.解:值式olPV((lQVP)A(lPAQ))

«1PV(1QV1PAQ)V(PA1PAQ)

01PV(OAO)

总〕PV(QAIQ)

e>GPVQ)A(lPVlQ)

.oM2.3)(3分)

«S(O.I)。分)

29.解,A的哈斯图如下,

极大元:e极小元a

最大元:e最小元津(4分)

«2)C的可达矩阵P=\\\\(2分)

30分)三、计算题(本大题共6小题，每小题5分，共求式,GTG双苞片{1,2}给定论域26.D,

(1)=2,(2)=1,(1)=(2)=(1,2)=(2,1)=T在该赋值下，精品文档.

精品文档

子?x(S(«r))AG(x,火x)))的真值。

27.请通过等值演算法求1(P/\Q)一(PV0)的主析取范式。

28.设月={1,2,3,4},给定/上二元关系五={<1』>,<1,2>,<2,4>,<4,2>},求五的传递闭包。

30.用矩阵的方法求题30图中结点〃，〃之间长度为2的路径的数目。5i

题30图

图的最小生成树。3131.求题

精品文档.

精品文档

三、计算题(本火口共6小题，每小J®5分，共30分)

26-原犬—AC<1/(1)))VAC(252)))《2分)

«->(«(2>AC(l.2))VG5(J)AG(2,l))(2分)

J>(rAT)V<FAT)iT(I分)

27.AQ)T，Va〉r(PAQ)V《『VQ)

ceVPV0)A(QV〃£。)

=PVQ(2分)

<=>(/*ACQV(?))V(CA('rV/*))

g(>>AW)V«P八Q)V(Q八W)V(pAP)

p「PA(?)V<PA；Q)V(/>AC>

EE(1.2.3)(3分)

fl10Q\

SI00/

UM

（3分）

00uVoI0