离散数学复习思考题.doc

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