1、离散数学试卷(第 1 页,共 5 页) 1 杭州师范大学钱江学院 2013 2014 学年第二学期期 末 试卷 _ _ 离散数学 (A)卷 命题教师 _田正平 _ 一、 判断题( 对的打 , 错的打 ; 每空 2分,共 20分 ) 1、 “如果南京大学不在上海,那么上海大学在南京。”是假命题。( ) 2、 命题 )( qpp 是矛盾式。( ) 3、 BxxABxAx )()( 。 ( ) 4、 设集合 , cbaX 上的关系 R 的关系矩阵是000101111RM,则关系 R 是传递关系 ( ) 5、 对称关系一定不是反对称关系。( ) 6、 有限偏序集 ),( X 必定存在最小元。( ) 7
2、、 在复数集合 C 上关系 ),( 2222 dcbadicbiaR 是等价关系。( ) 8、 无向连通图 ),( EVG 的每一个顶点的度数 )(vd 都是偶数 ,则图 G 是欧拉图。( ) 9、 无向图 ),( EVG 的每一个顶点的度数 2)( Vvd ,则图 G 是哈密顿图。( ) 10、在顶点个数不小于 2的简单无向图中,必有度数相同的顶点。 ( ) 题目 一 二 三 四 五 总分 分值 20 28 20 20 12 100 得分 得分 班级:学号:姓名:装订线离散数学试卷(第 2 页,共 5 页) 2 二、填空题( 每空 4分,共 28分 ) 1、 将命题:“下个星期我将去上海或苏
3、州出差。” 符号化。 设命题 P: 下个星期我将去上海出差 , Q: 下个星期我将去苏州出差 。则 命题:“下个星期我将去上海或苏州 出差。” 可以 符号化为: )()( QPQP 2、若个体域为全总个体域, 将命题:“没有不犯错误的人。” 符号化。 设谓词 xxP :)( 是人, xxQ :)( 犯错误。 命题: “没有不犯错误的人。” 可以 符号化为: )()( xQxPx 或者 )()( xQxPx 4、 欧拉图 ),( EVG 。 包含 G的所有边的简单回路称为 G的欧拉回路。具有欧拉回路的图称为欧拉回路。 5、 轮图 nW 的色数 evenn oddnW n ,3 ,4)(6、 集合
4、 A=1, 2, 3上的关系 )3,3(),1,3(),3,2(),3,1(),1,1(R 的关系矩阵 101100101RM7、图 G有 10条边, 4个度数为 3的顶点,其余顶点度数都不大于 2,则 G的顶点个数 8V 三、选择题( 每题 4 分,共 20 分 ) 1、 下面命题公式中,矛盾式是( C ) ( A) )( QPP (B) PPP )( (C) )()( RQQPP (D) )()( QPQP 2、设集合 10,6,4,5,3,2,1X 上的关系 R 是整除关系,则关系 R ( C ) ( A)有最大元,有最小元 (B)有最大元,无最小元 得分 得分 离散数学试卷(第 3 页
5、,共 5 页) 3 (C) 无最大元,有最小元 (D) 无最大元,无最小元 3、 下图( D ) ( A)无欧拉回路,无哈密顿通路 (B)有欧拉回路,无哈密顿通路 (C) 无欧拉通路,无哈密顿回路 (D) 有欧拉通路,有哈密顿回路 4、设 R 是非零实数集,下面关系中是等价关系的是( C ) ( A) 0),( yxyx (B) 0),( yxyx (C) 0),( xyyx (D) 0),( xyyx 5、 集合 A=1,2,3上的五个关系 ( 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) )
6、3,2(),3,1(),2,1(),1,1(3 R ( 4) 4R ( 5) AAR 5 中同时是对称关系和传递关系的是( B ) ( A) 431 , RRR (B) 542 , RRR (C ) 532 , RRR (D) 321 , RRR 四、计算题( 每题 5 分,共 20 分 ) 1、 化简命题公式 )( pqpq 。 得分 离散数学试卷(第 4 页,共 5 页) 4 解: 1)(1)()()()(1()()()()()()(pqpqqqpqqpqqpqppqpqpqpqpqpqpqpqpq2、 给出谓词公式 ),(),( yxxAyyxyAx 不能成立的一个解释 I。 解:设个体
7、域为实数集合。谓词 ),( yxA 表示 yx ,则 ),( yxyAx 表示有这样的实数0y 存在,它等于所有的实数 x ,这显然是一个假命题;而 ),( yxxAy 表示对 所有的实数 x都存在 实数 y ,使得它等于实数 x ,这显然是一个真命题。所以 这个 解 释 I 说明 谓词公式),(),( yxxAyyxyAx 不能成立 。 3、 设集合 10,6,4,5,3,2,1X 上的关系 R 是整除关系, 写出 关系 R 的传递闭包 )(Rt 。 解:因为 整除关系 是传递关系,所以 RRt )( 4、 完全偶图 nmK, 的 mnKEnm )( ,五、证明题( 每题 6分,共 12分)
8、 1、 写出下列推理的逻辑证明: )()()()(),()( xPxRxxQxRxxQxPx 证明: 1. )()( xQxPx (前提引入) 2. )()()()()()( xQxPxxQxPxxQxPx 3. )()( yQyP (US 规则) 4. )()( xQxRx (前提引入) 5. )()( yQyR (US 规则) 6. )()( yQyP , )()()()( yPyRyQyR 得分 离散数学试卷(第 5 页,共 5 页) 5 7. )()( xPxRx ( UG 规则) 2、 证明:在任意偏序集 ),( X 中最小元的个数最多只有一个。 证明:设 21,aa 是偏序集 ),( X 的最小元,因为 1a 是最小元,所以有 21 aa 成立。又因为 2a 也是最小元,所以也有 12 aa 成立。由于偏序集是反对称关系,所以必有 21 aa 。这说明了如果偏序集 ),( X 有最小元,则最小元是唯一的。所以在任意偏序集 ),( X 中最小元 的个数最多只有一个。