离散数学(A)答案.pdf

《离散数学(A)答案.pdf》由会员分享，可在线阅读，更多相关《离散数学(A)答案.pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、班级：学号：姓名：装订线杭州师范大学钱江学院杭州师范大学钱江学院 20132013 20142014 学年第二学期期末试卷学年第二学期期末试卷_ _ _ 离散数学离散数学(A)(A)卷卷命题教师_ _田正平_ _题目分值得分一20二28三20五12总分100四20一、判断题（对的打，错的打；每空2分，共20分）1、“如果南京大学不在上海，那么上海大学在南京。”是假命题。（）得分2、命题p (p q)是矛盾式。（）1113、设集合X a,b,c上的关系R的关系矩阵是MR101，则关系R是传递关系000（）4、对称关系一定不是反对称关系。（）5、有限偏序集(X,)必定存在最小元。（）2226、在复

2、数集合C上关系R(a bi,c di)a b c d 是等价关系。（2）7、无向连通图G (V,E)的每一个顶点的度数d(v)都是偶数，则图G是欧拉图。（）8、无向图G (V,E)的每一个顶点的度数d(v)V2，则图G是哈密顿图。（）10、在顶点个数不小于2的简单无向图中，必有度数相同的顶点。（第 1 页二、填空题（每空4分，共28分）1、将命题：“下个星期我将去上海或苏州出差。”符号化。得分设命题P：下个星期我将去上海出差，Q：下个星期我将去苏州出差。则命题：“下个星期我将去上海或苏州出差。”可以符号化为：(PQ)(PQ)2、若个体域为全总个体域，将命题：“没有不犯错误的人。”符号化。设谓词

3、P(x):x是人，Q(x):x犯错误。命题：“没有不犯错误的人。”可以符号化为：x(P(x)Q(x)或者x(P(x)Q(x)4、欧拉图G(V,E)。包含G的所有边的简单回路称为G的欧拉回路。具有欧拉回路的图称为欧拉图。5、轮图Wn的色数(Wn)4,nodd3,neven6、集合A=1,2,3上的关系R(1,1),(1,3),(2,3),(3,1),(3,3)的关系矩阵 7、图G有10条边，4个度数为3的顶点，其余顶点度数都不大于2，则G的顶点个数三、选择题（每题 4 分，共 20 分）1、下面命题公式中，矛盾式是（C）（A）P得分V8(PQ)(B)(PP)P(C)(PP)(QQR)(D)(PQ

4、)(PQ)2、设集合X1,2,3,5,4,6,10上的关系R是整除关系，则关系R（C）（A）有最大元，有最小元 (B)有最大元，无最小元(C)无最大元，有最小元 (D)无最大元，无最小元3、下图（D）（A）无欧拉回路，无哈密顿通路 (B)有欧拉回路，无哈密顿通路 (C)无欧拉通路，无哈密顿回路 (D)有欧拉通路，有哈密顿回路4、设R是非零实数集，下面关系中是等价关系的是（C）第 2 页（A）(x,y)x y 0 (B)(x,y)x y 0 0 (D)(x,y)xy 0(C)(x,y)xy5、集合 A=1,2,3上的五个关系（1）R1（3）R3(1,1),(1,2),(1,3),(3,3)（2）

5、R2(1,1),(1,2),(2,1),(2,2),(3,3)(1,1),(1,2),(1,3),(2,3)（4）R4（5）R5 A A中同时是对称关系和传递关系的是（B）（A）R1,R3,R4 (B)R2,R4,R5(C)R2,R3,R5 (D)R1,R2,R3四、计算题（每题 5 分，共 20 分）1、化简命题公式q (p q)p)。解：2、给出谓词公式xyA(x,y)解：设个体域为实数集合。谓词得分 yxA(x,y)不能成立的一个解释I I。A(x,y)表示x y，则xyA(x,y)表示有这样的实数y0存在，它等于所有的实数x，这显然是一个假命题；而yxA(x,y)表示对所有的实数x都存

6、在实数它等于实数x，这显然是一个真命题。所以这个解释I I说明说明谓词公式xyA(x,y)能成立。y，使得 yxA(x,y)不3、设集合X 1,2,3,5,4,6,10上的关系R是整除关系，写出关系R的传递闭包t(R)。解：因为整除关系是传递关系，所以t(R)4、完全偶图Km,n的RE(Km,n)mn五、证明题（每题6分，共12分）1、写出下列推理的逻辑证明：得分证明：1.x(P(x)Q(x)（前提引入）2.x(P(x)Q(x)x(P(x)Q(x)x(P(x)Q(x)第 3 页 3.P(y)Q(y)(US 规则）4.x(R(x)Q(x)（前提引入）5.R(y)Q(y)(US 规则）6.P(y)Q(y),R(y)Q(y)R(y)P(y)7.x(R(x)P(x)（UG 规则）2、证明：在任意偏序集(X,)中最小元的个数最多只有一个。证明：设a1,a2是偏序集(X,)的最小元，因为a1是最小元，所以有a1是最小元，所以也有a2 a2成立。又因为a2也 a1成立。由于偏序集是反对称关系，所以必有a1 a2。这说明了如果偏序集(X,)有最小元，则最小元是唯一的。所以在任意偏序集(X,)中最小元的个数最多只有一个。第 4 页