杭州师范大学钱江学院2013 —2014 学年第二学期期末试卷
_ _《 离散数学 》(A)卷
命题教师_田正平_
一、判断题(对的打∨,错的打?;每空2分,共20分)
1、 “如果南京大学不在上海,那么上海大学在南京。”是假命题。( ∨ )
2、 命题)(q p p ?∨→是矛盾式。( ? )
3、 B x xA B x A x →??→?)())((。( ∨ )
4、 设集合},,{c b a X =上的关系R 的关系矩阵是???
?
?
??=000101111R M ,则关系R 是传
递关系( ? )
5、 对称关系一定不是反对称关系。( ? )
6、 有限偏序集),(≤X 必定存在最小元。( ? )
7、 在复数集合C 上关系}),{(2
2
22d c b a di c bi a R +=+++=是等价关系。
( ∨ )
8、 无向连通图),(E V G =的每一个顶点的度数)(v d 都是偶数,则图G 是欧拉图。( ? )
9、 无向图),(E V G =的每一个顶点的度数2
)(V v d ≥
,则图G 是哈密顿图。( ? )
10、在顶点个数不小于2的简单无向图中,必有度数相同的顶点。( ∨ )
二、填空题(每空4分,共28分)
1、将命题:“下个星期我将去上海或苏州出差。”符号化。
设命题P :下个星期我将去上海出差,Q :下个星期我将去苏州出差。则命题:“下个星期我将去上海或苏州出差。”可以符号化为:)()(Q P Q P ∧?∨?∧
2、若个体域为全总个体域,将命题:“没有不犯错误的人。”符号化。
设谓词x x P :)(是人,x x Q :)(犯错误。命题:“没有不犯错误的人。”可以符号化为: ))()((x Q x P x →? 或者 ))()((x Q x P x ?∧?? 4、欧拉图),(E V G =。
包含G 的所有边的简单回路称为G 的欧拉回路。具有欧拉回路的图称为欧拉回路。
5、轮图n W 的色数?
??===even n odd n W n ,3,4)(χ
6、集合A={1, 2, 3}上的关系)}3,3(),1,3(),3,2(),3,1(),1,1{(=R 的关系矩阵
???
?
? ??=101100101R M
7、图G 有10条边,4个度数为3的顶点,其余顶点度数都不大于2,则G 的顶点个数8≥V
三、选择题(每题4分,共20分)
1、下面命题公式中,矛盾式是( C )
(A ))(Q P P ∨→ (B)P P P ?→?→)(
(C) )()(R Q Q P P ∧?∧→?∨ (D) )()(Q P Q P ???→?
2、设集合}10,6,4,5,3,2,1{=X 上的关系R 是整除关系,则关系R ( C ) (A )有最大元,有最小元 (B)有最大元,无最小元
(C) 无最大元,有最小元 (D) 无最大元,无最小元
3、下图( D )
(A )无欧拉回路,无哈密顿通路 (B)有欧拉回路,无哈密顿通路
(C) 无欧拉通路,无哈密顿回路 (D) 有欧拉通路,有哈密顿回路
4、设*
R 是非零实数集,下面关系中是等价关系的是( C )
(A )}0),{(>+y x y x (B) }0),{(<+y x y x
(C) }0),{(>xy y x (D) }0),{( (1))}3,3(),3,1(),2,1(),1,1{(1=R (2))}3,3(),2,2(),1,2(),2,1(),1,1{(2=R (3))}3,2(),3,1(),2,1(),1,1{(3=R (4)?=4R (5)A A R ?=5 中同时是对称关系和传递关系的是( B ) (A )431,,R R R (B) 542,,R R R (C ) 532,,R R R (D) 321,,R R R 四、计算题(每题5分,共20分) 1、 化简命题公式))((p q p q ?→→→?。 解: 1 )(1)()()())(1())()(() )(())(())(())((=?∨∨=?∨∨?∨=?∨?∨=?∨?∧∨=?∨?∧?∨∨=?∨?∧∨=?∨?∧??∨=?∨∨??∨??=?→→→?p q p q q q p q q p q q p q p p q p q p q p q p q p q p q p q p q 2、给出谓词公式),(),(y x xA y y x yA x ??=??不能成立的一个解释I 。 解:设个体域为实数集合。谓词),(y x A 表示y x =,则),(y x yA x ??表示有这样的实数 0y 存在,它等于所有的实数x ,这显然是一个假命题;而),(y x xA y ??表示对所有的实数x 都存在实数y ,使得它等于实数x ,这显然是一个真命题。所以这个解释I 说明谓词公式 ),(),(y x xA y y x yA x ??=??不能成立。 3、设集合}10,6,4,5,3,2,1{=X 上的关系R 是整除关系,写出关系R 的传递闭包)(R t 。 解:因为整除关系是传递关系,所以R R t =)( 4、完全偶图n m K ,的mn K E n m =)(, 五、证明题(每题6分,共12分) 1、写出下列推理的逻辑证明: ))()(())()(()),()((x P x R x x Q x R x x Q x P x ?→??→?∧?? 证明:1.))()((x Q x P x ∧?? (前提引入) 2.))()(())()(())()((x Q x P x x Q x P x x Q x P x ?∨??=∧??=∧?? 3.)()(y Q y P ?∨? (US 规则) 4. ))()((x Q x R x →? (前提引入) 5. )()(y Q y R → (US 规则) 6. )()(y Q y P ?∨?,)()()()(y P y R y Q y R ?→?→ 7.))()((x P x R x ?→? (UG 规则) 2、证明:在任意偏序集),(≤X 中最小元的个数最多只有一个。 证明:设21,a a 是偏序集),(≤X 的最小元,因为1a 是最小元,所以有21a a ≤成立。又因为2a 也是最小元,所以也有12a a ≤成立。由于偏序集是反对称关系,所以必有21a a =。这说明了如果偏序集),(≤X 有最小元,则最小元是唯一的。所以在任意偏序集),(≤X 中最小元的个数最多只有一个。