离散数学(a)答案

《离散数学(a)答案》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、杭州师范大学钱江学院2013-2014学年第二学期期末试卷《离散数学》（A）卷命题教师田正平题目二三四五总分分值2028202012100得分一、判断题（对的打s错的打x；每空2分，共20分）得分1>“如果南京大学不在上海，那么上海大学在南京是假命题。（V)2、命题p（/?v-i（?）是矛盾式。（x）3、Vx(A(x)tB)=>BxA(a-)tB。(v)<1104、设集合X=｛aM上的关系R的关系矩阵是Mr=101,则关系/?是传.00丿递关系（X）5＞对称关系一定不是反对称关系。（X）6、有限偏序集（X,S）必定存在最小元。（X）27

2、、在复数集合C上关系/?=｛（。+勿疋+劲”+方2=工+/｝是等价关系。（7）8、无向连通图G=（V,E）的每一个顶点的度数d（v）都是偶数，则图G是欧拉图。（x）IVI9、无向图G=（V,E）的每一个顶点的度数J（v）＞^，则图G是哈密顿图。（x）210、在顶点个数不小于2的简单无向图中，必有度数相同的顶点。（v）二、填空题(每空4分，共28分)得分1、将命题：“下个星期我将去上海或苏州出差。”符号化。设命题P：下个星期我将去上海出差，Q：下个星期我将去苏州出差。则命题：“下个星期我将去上海或苏州出差。”可以符号化为：2、若个体域为全总个

3、体域，将命题：“没有不犯错误的人。”符号化。设谓词P(x):x是人，Q(x):x犯错误。命题：“没有不犯错误的人。”可以符号化为：Vx(P(x)tQ(Q)或者-3兀(P(x)人-i0(x))4、欧拉图G=(V,E)°包含G的所有边的简单冋路称为G的欧拉冋路。具有欧拉冋路的图称为欧拉图。｛4,n=odd3,n=even6、集合A二｛1,2,3｝上的关系/?=｛(1,1),(1,3),(2,3),(3,1),(3,3)｝的关系矩阵‘10r心=001JoJ7、图G有10条边，4个度数为3的顶点，其余顶点度数都不大于2,则G的顶点个数

4、V

5、>8得分

6、(B)(PT-1P)T-1P(D)("。—(「心虫)三、选择题(每题4分，共20分)1、下面命题公式中，矛盾式是(C)(A)P(P/Q)(C)(P“P)i(Qa「QaR)2、设集合X=｛l,2,3,5,4,6」0｝上的关系7?是整除关系，则关系7?(C)(A)有最大元，有最小元(B)有最大元，无最小元(C)无最大元，有最小元(D)无最大元，无最小元3、下图(D)(A)无欧拉回路，无哈密顿通路(C)无欧拉通路，无哈密顿回路(B)有欧拉回路，无哈密顿通路(D)有欧拉通路，有哈密顿回路4、设/T是非零实数集，下面关系中是等价关系的是(C)(A)

7、{(兀，刃

8、x+y>0}(B){(兀,刃

9、x+y<0}(C)[(x9y)xy>0}5、集合A={1,2,3}上的五个关系(I)&二{(1,1),(1,2),(1,3),(3,3)}(3)尺3={(1，1)，(1，2),(1,3),(2,3)}中同时是对称关系和传递关系的是(B(A)心/?3'/?4(C)r2,r.,r5(D){(x,y)

10、xy<0}(2)/?2二{(1，1)，(1，2),(2,1),(2,2),(3,3)}(4)7?4=0(5)R5=AxA)⑻r2,r4,r5(D)心/?2，尺3四、计算题(每题5分，共20分)得分解:-i

11、?T((/?~>q)T-n/?)=-i-iQ7(「(「°7Q)V切=q7((-1-1/2A-iq)V-ip)=^v((pA—)g)V-n/?)=qv((py-ip)A(—7-1°))=V(1A(—)qV—>p))=qv(—v—ip)=(^v—it/)7(q7—p)=1V(^V-!/?)=12、给出谓词公式Vx3}^(x,y)=3)^VxA(x,y)不能成立的一个解释I.解：设个体域为实数集合。谓词A(x,y)表示兀=y,则/x3yA(x,y)表示有这样的实数旳存在，它等于所有的实数兀，这显然是一个假命题；而3yVxA(x,y)表示对所有的

12、实数x都存在实数y,使得它等于实数x,这显然是一个真命题。所以这个解释I说明谓词公式X/x3yA(x,y)=3y/xA(x,y)不能成立。3、设集合X={1,2,3,5,4,6,10}上的关系R是整除关系，写出关系R的传递闭包/(R)。解：因为整除关系是传递关系，所以t(R)=R4、完全偶图K“的E(K加=mn得分五、证明题(每题6分，共12分)1、写出下列推理的逻辑证明：—i3x(P(x)a(2(x)),Vx(/?(x)T2(x))nVx(/?(x)T-1P(X))证明：1.^3x(P(x)a2(x))(前提引入)2.-3x(P(x)a

13、Q(x))=Vx—i(P(x)aQ(x))=Vx(—iP(x)v-iQ(x))3・-iP(y)v-ig(j)(US规则)4.Vx(/?(x)Q(x))(前提引入)5・R(y)Q(