1、离散数学复习思考题 一、 选择题 对于公式 ),(),(),( zxzRzxQyxPx ,下列说法正确的是 ( )。 A y 是自由 出现的 ; B x 是约束 出现的; C x 的辖域是 ),(),(),( zxzRzxQyxP ; D x 的辖域是 ),( yxP A 设 ,8,7,6,5,4,3,2,1A ,下列正确的是( ) 。 A A1 ; B A3,2,1 ; C A ; D A3,2,1 D 设 A-B=,则有 ( )。 A B=; B B ; C A B; D A B C 设 N 是自然数集合,函数 1,)( nnnfNNNf ,: 是 ( )。 A 满射,不 是单射 ; B单
2、射,不是满射; C双射 ; D非单射非满射 B 设 R 为实数集,函数 f: R R, f(x)= xe ,则 f 是( )。 A满射函数 ; B单射函数; C双射函数 ; D非单射非满射 B 设 Z 是整数集合, N 是自然数集合,则函数 xxfNZf )(,: 是( )。 A 满射,不是单射 ; B单射,不是满射; C双射 ; D非单射非 满射 A 设函数 f: NN ( N 为自然数集), f(n)=n+1,下面四个命题为真的是 ( )。 A. f 是 满射 ; B. f 是 单 射 ; C. f 是双射的 ; D. f 非单射非满射 B 谓词公式 x(P(x) yR(y) Q(x)中的
3、变元 x 是( )。 A 自由出现的; B 约束出现的; C 既不是自由出现也不是约束出现; D 既是自由出现也是约束出现 D 下列 不 是 谓词公式的是 ( )。 A x y P( x, y) ; B x(P(x) x(Q(x) A(x, y); C xP( x) R( y) ; D xP( x) Q( y, z) A 下列句子为命题的是 ( )。 A 全体起立 ! B x=0; C 你会抽烟吗? D 张三生于 1886 年的春天 D 下列命题正确的是 ( )。 A = ; B =; C aa, b, c ; D a, b, c A 下列命题正确的是 ( )。 A l, 2 1, 2, l,
4、 2, 3, 1; B 1, 2 1, l, 2, l, 2, 3, 2; C 1, 2 1, 2, 1, 2; D 1, 2 1, 2, 2, l, 2, 3 B 下列图形是( )。 A 完全图 ; B哈密顿图 ; C欧拉图 ; D平面图 B 下列图中不是平面图的为( )。 A. B C D C 下列为公式的是( )。 A srq ; B )( srp ; C )()( pqqp ; D qprs C 下列语句中,( )是命题。 A下午有会吗? B这朵花多好看呀! C 2 是偶数; D请把门关上 ! C 下列语句中是假命题的是( )。 A 5 是素数; B太阳从东方升起; C 1235 ;
5、D正在下 雨呢! C 下列语句中是命题的是( )。 A天气真暖和呀! B请别激动! C还记得我吗? D地球是运动的 D 下面既是 哈 密顿图又是欧拉图的是 ( )。 B 一个连通图 G 具有以下何种条件时,能一笔画出:即从某结点出发,经过图中每边仅一次回到该结点 ( )。 A G 没有奇数度的结点; B G 有 1 个奇数度的结点; C G 有 2 个奇数度的结点; D G 没有或有 2 个奇数度的结点 A 在自然数集合上,下列运算满足结合律的是( )。 A 2a b a b B min , a b a b C a b a b D a b a b B 二、 填空题 令 p:今天下雪了, q:路
6、滑,则命题“虽然今天下雪了,但是路不滑”可符号化为 _。 p q 设 p :明天上午 8 点下雨, q :明天上午 8 点下雪, r :我去学校,则命题“如果明天上午 8 点不下雨并且也不下雪,我就去学校”可符号化为 。 rqp )( 设 )(xF : x 是偶数, )(xG : x 是素数,则命题“存在着偶素数”可符号化为 _。 )()( xGxFx n 个顶点的无向 完全图 记为 nK ,当 n 满足条件 _时 , nK 不是平面图。 4n 设 p :我们勤奋, q :我们好学, r :我们取得好成绩,则命题“我们只要勤奋好学,就能取得好成绩”符号化为 。 rqp )( 设 A( x):
7、x 是人, B( x): x 犯错误,命题“没有不犯错误的人”符号化为 _。 )()( xBxAx 或)()( xBxAx 设 G 是连通的平面图,已知 G 中有 6 个顶点, 8 条边,则 G 有 _个面。 4 设 P:他聪明, Q:他用功,则命题“他虽聪明 ,但不用功” 可符号化为_。 P Q 设集合 3,2,1A , 5,4,3B ,则 BA 。 2,1 设集合 , cbaA , , dcbB ,则 BA 。 , da 设集合 2,1A ,则 A 的幂集 )(AP 。 2,1,2,1, 设集合 2,1A , 则 A 的幂集 )(AP 。 答案: 2,1,2,1, 设 xxM :)( 是人
8、, xxP :)( 要吃饭,则命题“人都是要吃饭的” 可符号化为 _。 答案: )()( xPxMx 设 xxM :)( 是跳高运动员, a:小张,则命题“小张不是跳高运动员”可符号化为 _。 )(aM 无向图 G=如右所示, 则图 G 的最大度数 (G)= _。 4 无向图 G 中有 16 条边,且每个结点的度数都是 2,则 G 的结点数是 _个 。 16 无向 完全图 5K 中有 _条边。 10 已知关系 ,1 dbbaaaR , ,2 bcdbcbdaR , 则 12 RR =_。 答案: , daca 已知关系 , dbbaaaR , 则 2R = 。 , dabaaa已知关系 ,1
9、cbcabaR , ,2 aabaR , 则 21 RR = 。 答案: , baca 已知关系 , bcdbcbdaR ,则 3R = 。 答案: , dbcbbc 三、 计算题 构造命题公式 ( PQ) Q 的 真值表 ,并判断其类型。 解 :真值表 P Q PQ ( PQ) ( PQ) Q 0 0 1 0 0 0 1 1 0 0 1 0 0 1 0 1 1 1 0 0 因此公式 ( PQ) Q 为矛盾式 对某单位的 100 名员工进行调查,结果发现他们喜欢看球赛、电影和戏剧其中 58 人喜欢看球赛, 52 人喜欢看电影, 38 人喜欢看戏剧,既喜欢看球赛又喜欢看戏剧的有 18 人,既喜欢
10、看电影又喜欢看戏剧的有 16 人,三种都喜欢看的有 12 人,求只喜欢看电影的有多少人。 解: 设 喜欢看球赛、电 影和戏剧的人的 集合分别为 A , B , C,那么 A = 58, B = 52, C = 38, A C = 18, B C = 16, CBA =12, 只喜欢看电影的有 22 人 构造命题公式 ( PQ) R 的 真值表 ,并判断其类型。 解: 真值表 为: P Q R PQ R ( PQ) R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 1 1 0 0 1 0 1 0 1 0 1 0 1 0 0 0 A B C 26 14 22 6
11、12 4 16 1 1 0 1 1 1 1 1 1 0 1 0 公式 ( PQ) R 为可满足式 构造命题公式 rqp 的 真值表 ,并判断其类型。 解 : 真值表 为 rqp qp rqp 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 1 1 公式 rqp 为可满足式 集合 3,2,1A 上的关系 3,3,2,3,1,3,2,2,1,2,2,1,1,1 R , 试写出关系矩阵 M,并讨论 R 的 性质。 解:关系矩阵111011011M , R 是自反的和传递的 集合 3,2,1A 上的
12、关系 3,3,3,2,3,1,2,1 R , 试写出关系矩阵 M,并讨论 R 的性质。 解: 关系矩阵100100110M , R 具有反对称性和传递性 集合 3,2,1A 上的关系 3,3,1,3,2,2,1,2,1,1 R , 试写出关系矩阵 M,并讨论 R 的性质。 解:关系矩阵101011001M , R 是自反的,反对称的和传递的 集合 4,3,2,1A 上的关系4,4,3,4,4,3,3,3,1,3,2,2,3,1,1,1 R , 试写出关系矩阵 M,并讨论 R 的性质。 解: 关系矩阵1100110100100101M , R 具有自反性和对称性 今有工人甲、乙、丙去完成三项任务
13、 a、 b、 c已知甲能胜任 a、 b、 c 三项任务;乙能胜任a、 b 二项任务;丙能胜任 b、 c 二项任务试给出一种方案,使 每个工人各去完成一项他们能胜任的任务。 解:工人与任务的胜任关系的二部图为: 甲 乙 丙 a b c 一种方案是:甲完成 a,乙完成 b,丙完成 c (注:本题答案不唯一,还可以给出其它的方案) 某班有学生 50 人,有 26 人在第一次考试中得优,有 21 人在第二次考试中得优,有 17 人两次考试都没有得优,试求两次考试都得优的学生人数。 解:设两次考试都 得优的学生人数为 x 人,由下列文氏图可知 17+(26-x)+x+(21-x)=50,解得: x=14
14、, 两次考试都得优的学生人数为 14 人 某大学计算机专业的 80 名学生在期末考试中, Pascal 语言课有 58 人达到优秀,数据结构课有 30 人达到优秀,离散数学课有 25 人达到优秀并且, Pascal 语言和数据结构两门课都达到 优秀 的有 20 人, Pascal 语言和离散数学两门课都达到 优秀 的有 19 人,数据结构和17 26-x x 21-x 离散数学两门课都达到 优秀 的有 17 人 , 还有 10 人一门优秀都没得到 求三门课都达到优秀的人 数。 解 : 设期末考试中 Pascal 语言课、数据结构课、离散数学课达到优秀的学生集合分别为A , B , C,那么 A
15、 = 58, B = 30, C = 25, A B = 20, A C = 19, B C = 17 由题意, 至少有 一 门课达到优秀的学生 人数为 CBA = 80- )( CBA = 70 于是,三 门课都达到优秀的学生数为: CBA = CBA - (A +B +C - A B - A C - B C ) =70 -58 -30 -25 +20 +19 +17= 13 求图中 A 到其余各顶点的最短路径的权(要求列表)。 B 5 D 1 2 A 4 3 3 F 3 5 C 1 E 解:用用标号法解题过程如下 B C D E F 0 1 3 1 1* 3 6 4 2 3* 6 4 3
16、6 4* 9 4 6* 8 5 8* 1 3 6 4 8 求图中 A 点到其余各顶点的最短路径的权(要求列表)。 B 7 C 1 2 A 2 5 3 D 4 6 E 1 F 解:用用标号法解题过程如下: B C D E F 0 1 4 1 1* 8 3 6 2 8 3* 4 3 7 10 4* 4 7* 9 5 9* 1 7 9 3 4 求下面所示带权图中顶点 A 到其余各顶点的最短路径的权(要求列表)。 1 12256248ABCDEF解:用用标号法解题过程如下: B C D E F 0 8 1 2 1 3 1* 7 2 2 3 7 3 2* 3 3* 7 3 4 5 3* 5 5* 3 1 5 3 2 求下面所 示带权图中顶点 A 到其余各顶点的最短路径的权(要求列表)。 解:用用标号法解题过程如下 B C D E F 0 4 2 1 3 2* 10 11 2 3* 8 11 3 8* 10 14 4 10* 13 5 13* 1 4 2 5 8 9 2 6 3 A B C D E F
Copyright © 2018-2021 Wenke99.com All rights reserved
工信部备案号:浙ICP备20026746号-2
公安局备案号:浙公网安备33038302330469号
本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。