离散数学复习思考题2016.06

1、离散数学复习思考题一、选择题对于公式，下列说法正确的是（ ）。A y是自由出现的 ； Bx是约束出现的；C的辖域是； D的辖域是A设，下列正确的是（ ）。A ； B ； C ； DD设A-B=，则有（ ）。AB=；BB；CAB；DABC设N是自然数集合，函数是（ ）。A 满射，不是单射 ； B单射，不是满射； C双射 ； D非单射非满射B设R为实数集，函数f：RR，f(x)=，则f是（ ）。A满射函数 ； B单射函数；C双射函数 ； D非单射非满射B设Z是整数集合，N是自然数集合，则函数是（ ）。A 满射，不是单射 ； B单射，不是满射； C双射 ； D非单射非满射A设函数f：NN（N 为自然

2、数集），f(n)=n+1，下面四个命题为真的是（ ）。A. f是满射；B.f是单射 ； C. f是双射的； D. f非单射非满射B谓词公式x(P(x)$yR(y)Q(x)中的变元x是（ ）。A自由出现的；B约束出现的；C既不是自由出现也不是约束出现；D既是自由出现也是约束出现D下列不是谓词公式的是（ ）。Ax$yP（x，y）； Bx(P(x)$x(Q(x)A(x，y)；CxP（x）R（y）； D$xP（x）Q（y，z）A下列句子为命题的是（ ）。A全体起立! Bx=0；C你会抽烟吗？ D张三生于1886年的春天D下列命题正确的是（ ）。Aff=f ； Bff=f； Caa，b，c ； Dfa，

3、b，cA下列命题正确的是（ ）。Al，21，2，l，2，3，1；B1，21，l，2，l，2，3，2；C1，21，2，1，2；D1，21，2，2，l，2，3B下列图形是（ ）。A完全图 ； B哈密顿图 ； C欧拉图 ； D平面图h h h h h h B下列图中不是平面图的为（ ）。 A. B C DC下列为公式的是（ ）。A ； B；C ； DC下列语句中，（ ）是命题。A下午有会吗？ B这朵花多好看呀！ C2是偶数； D请把门关上!C下列语句中是假命题的是（ ）。A5是素数； B太阳从东方升起； C ； D正在下雨呢！C下列语句中是命题的是（ ）。A天气真暖和呀！ B请别激动！ C还记得我吗

4、？ D地球是运动的D下面既是哈密顿图又是欧拉图的是（ ）。B一个连通图G具有以下何种条件时，能一笔画出：即从某结点出发，经过图中每边仅一次回到该结点（ ）。AG没有奇数度的结点； BG有1个奇数度的结点；CG有2个奇数度的结点； DG没有或有2个奇数度的结点A在自然数集合上，下列运算满足结合律的是（ ）。A B C DB二、填空题令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为_。pq设：明天上午8点下雨，：明天上午8点下雪，：我去学校，则命题“如果明天上午8点不下雨并且也不下雪，我就去学校”可符号化为 。 设：是偶数，：是素数，则命题“存在着偶素数”可符号化为_。n

5、个顶点的无向完全图记为，当n满足条件_时,不是平面图。设：我们勤奋，：我们好学，：我们取得好成绩，则命题“我们只要勤奋好学，就能取得好成绩”符号化为 。 设A（x）：x是人，B（x）：x犯错误，命题“没有不犯错误的人”符号化为_。 或设G是连通的平面图，已知G中有6个顶点，8条边，则G有_个面。4设P：他聪明，Q：他用功，则命题“他虽聪明,但不用功” 可符号化为_。P Q设集合，则 。设集合，则 。 设集合，则A的幂集 。设集合，则A的幂集 。答案：设是人，要吃饭，则命题“人都是要吃饭的”可符号化为_。答案：设是跳高运动员，a：小张，则命题“小张不是跳高运动员”可符号化为_。无向图G=如右所示

6、，则图G的最大度数(G)= _。4无向图G中有16条边，且每个结点的度数都是2，则G的结点数是_个。16无向完全图中有_条边。10已知关系, 则=_。 答案：已知关系, 则= 。已知关系，则= 。 答案：已知关系,则= 。答案：三、计算题构造命题公式（PQ）Q的真值表，并判断其类型。解 ：真值表P QPQ （PQ） （PQ）Q0 01 0 00 11 0 01 00 1 01 11 0 0 因此公式（PQ）Q为矛盾式对某单位的100名员工进行调查，结果发现他们喜欢看球赛、电影和戏剧其中58人喜欢看球赛，52人喜欢看电影，38人喜欢看戏剧，既喜欢看球赛又喜欢看戏剧的有18人，既喜欢看电影又喜欢看

7、戏剧的有16人，三种都喜欢看的有12人，求只喜欢看电影的有多少人。解： 设喜欢看球赛、电影和戏剧的人的集合分别为A , B , C，那么 = 58， = 52， = 38， = 18，= 16, =12， A B C26 14 226 12 4 16只喜欢看电影的有22人构造命题公式（PQ）R的真值表，并判断其类型。解：真值表为：P Q RPQR（PQ）R0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1111100111010101010100010公式（PQ）R为可满足式构造命题公式的真值表，并判断其类型。解 ：真值表为0 0 00 0 10 1 00 1 1

8、1 0 01 0 11 1 01 1 10000001110101011公式为可满足式集合上的关系，试写出关系矩阵M，并讨论R的性质。解：关系矩阵， R是自反的和传递的集合上的关系，试写出关系矩阵M，并讨论R的性质。解：关系矩阵，R具有反对称性和传递性集合上的关系，试写出关系矩阵M，并讨论R的性质。解：关系矩阵， R是自反的，反对称的和传递的集合上的关系，试写出关系矩阵M，并讨论R的性质。解：关系矩阵，R具有自反性和对称性今有工人甲、乙、丙去完成三项任务a、b、c已知甲能胜任a、b、c三项任务；乙能胜任a、b二项任务；丙能胜任b、c二项任务试给出一种方案，使每个工人各去完成一项他们能胜任的任务

9、。解：工人与任务的胜任关系的二部图为： 甲乙丙 a b c 一种方案是：甲完成a，乙完成b，丙完成c（注：本题答案不唯一，还可以给出其它的方案）某班有学生50人，有26人在第一次考试中得优，有21人在第二次考试中得优，有17人两次考试都没有得优，试求两次考试都得优的学生人数。解：设两次考试都得优的学生人数为x人，由下列文氏图可知1726-xx 21-x 17+(26-x)+x+(21-x)=50，解得：x=14，两次考试都得优的学生人数为14人某大学计算机专业的80名学生在期末考试中，Pascal语言课有58人达到优秀，数据结构课有30人达到优秀，离散数学课有25人达到优秀并且，Pascal语

10、言和数据结构两门课都达到优秀的有20人，Pascal语言和离散数学两门课都达到优秀的有19人，数据结构和离散数学两门课都达到优秀的有17人，还有10人一门优秀都没得到求三门课都达到优秀的人数。解： 设期末考试中Pascal语言课、数据结构课、离散数学课达到优秀的学生集合分别为A , B , C，那么 = 58， = 30， = 25， = 20，= 19，= 17由题意，至少有一门课达到优秀的学生人数为= 80-= 70于是，三门课都达到优秀的学生数为：=- (+-) =70 -58 -30 -25 +20 +19 +17= 13求图中A到其余各顶点的最短路径的权（要求列表）。 B 5 D 1

11、 2 A 4 3 3 F3 5 C 1 E解：用用标号法解题过程如下 B C D E F 0 1 3 1 1* 3 6 4 2 3* 6 4 3 6 4* 9 4 6* 8 5 8* 1 3 6 4 8求图中A点到其余各顶点的最短路径的权（要求列表）。 B 7 C 1 2 A 2 5 3 D4 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 59* 1 7 9 3 4求下面所示带权图中顶点A到其余各顶点的最短路径的权（要求列表）。解：用用标号法解题过程如下： B C D E F 0 8 1 2

12、1 3 1* 7 2 2 3 7 3 2* 33* 7 3 45 3* 55* 3 1 5 3 2142589263ABCDEF求下面所示带权图中顶点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* 3 2 8 10 13设，定义A上的二元运算*如下：对，（表示xy除以5的余数），试求*的运算表。解：运算表如下：设，定义A上的二元运算*如下：对，的最大公约数，试给出*的运算表。解：运算表如下：设，定义A上的二元运算*如下：对，的最小公倍数，试给出

13、*的运算表。解：运算表如下：设，试给出A上运算的运算表。解：运算表如下设个体域为1，2，求公式的真值。解： 设个体域为1，2，求公式的真值解： 设无向图G有4个顶点，度数分别为1，2，2，3，问G中有几条边？依据是什么？并画出一个符合上述条件的图。解：图G有4条边，依据是握手定理：1+2+2+3=2m，m=4下面的图就符合上述条件：设无向图G有5个顶点，度数分别为1，1，2，2，4，问G中有几条边？依据是什么？并画出一个符合上述条件的图。解：图G有5条边，依据是握手定理：1+1+2+2+4=2m，m=5. 下面的图就符合上述条件：题公式（PP）Q的真值表，并判断其类型。解 ：真值表为：P QP

14、 PP （PP）Q0 01 0 10 11 0 01 00 0 11 10 0 0 因此公式（PP）Q为可满足式现有三个课外小组：物理组、化学组、生物组，今有张、王、李、赵、陈5名同学，已知张、王为物理组成员，张、李、赵为化学组成员，李、陈为生物组成员，问在这种情况下能否选出3名不兼职的组长？若能选出，试给出一种方案。解：可以选出3名不兼职的组长 物理组化学组生物组 张王李 赵陈一种方案是：张任物理组的组长，李任化学组的组长，陈任生物组的组长（注：本题答案不唯一，还可以给出其它的方案）一棵无向树有1个2度的顶点，3个3度的顶点，其余点都是树叶，求该树的叶子数并画出一棵符合上述条件的树。解：设该

15、树的叶子数为x个，则2+9+x=2（4+x-1） 解得x=5，即有5个树叶子 下面的这棵树就符合上述条件：一棵无向树有4个树叶，1个2度的顶点，其余的点度数都为3，该树共有几个点？画出一棵符合上述条件的树。解：设该树中3度的点有x个，则4+2+3x=2（4+1+x-1） 解得x=2，从而该树共有7个点 下面的这棵树就符合上述条件：已知公式，其中，且个体域为1，2，求该式的真值。解：已知公式，其中，且个体域为3，4，求该式的真值。解：有150人至少喜欢游泳或跑步中的一种若85人喜欢游泳，60人同时喜欢游泳和跑步，问有多少人喜欢跑步？解：由下列文氏图可知2560 65 喜欢跑步而不喜欢游泳的人数为

16、：150-85=65 因此喜欢跑步的人数为： 65 60=125 有四个信息c，ac，bd，abd ，现想分别用组成每个信息的字母中的一个来表示该信息，这是否可能？如果可能，应如何表示？解：可以做到： cac bdabd dcba一种方案是：c表示c，a表示ac，b表示bd，d表示abd有张、王、李、赵四位教师，要分配他们教数学、物理、化学、英语等四门课程张熟悉物理和英语，王熟悉数学和化学，李熟悉数学、物理和英语，赵只熟悉英语。（1）画出关于教师熟悉课程的二部图；（2）如何分配，才能使每位教师都教一门自己熟悉的课程？解：（1）画出二部图 张王李赵 数学物理化学英语 （2） 张：物理 ；王：化学

17、；李：数学；赵：英语 四、证明构造下列推理的证明前提：，结论：。证明：（1） 前提引入（2） 前提引入（3） （1），（2）析取三段论 （4） 前提引入 （5） （3），（4）拒取式 （6） （5）置换（7） 前提引入（8） （6），（7）析取三段论设Z表示整数集,在Z上定义二元运算:，证明:Z关于*运算构成群。证：根据群的定义，需证明运算满足结合律、有么元和每个元素都有逆元.对, 有(a*b)*c= (a*b)+c+3=(a+b+3) +c+3=a+b+c+6， 而a*(b*c)= a+(b*c) +3=a+(b+c +3) +3=a+b+c+6 ， 故(a*b)*c= a*(b*c), 结

18、合律成立.-3是么元, 事实上：, a*(-3)=a+(-3)+3=a , (-3)*a=(-3)+a+3=a , 对，a*(-6-a)=a+(-6-a)+3=-3, (-6-a)* a =(-6-a)+ a +3= -3, 可知-6-a是a的逆元.因此，Z关于*运算构成群.构造下列推理的证明：前提：P（QR），SP，Q，S结论：R证明：（1）SP 前提引入（2）S 前提引入（3）P （1），（2）析取三段论 （4）P（QR） 前提引入 （5）QR （3），（4）假言推理 （6）Q 前提引入（7）R （5），（6）假言推理在整数集Z上定义: a*b=a+b-9,证明: 是一个群。证 显然*是二元运算,根据群的定义，需证明运算满足结合律、有幺元和每个元素都有逆元。 对, 有(a*b)*c=