离散数学复习思考题

离散数学复习思考题一、选择题对于公式，下列说法正确的是（）。,ZXRZXQYPXAY是自由出现的；BX是约束出现的；C的辖域是；,ZXZXYD的辖域是X,PA设，下列正确的是（）。,8765,432,1AA；B；C；DA,A3,21D设AB，则有（）。AB；BB；CAB；DABC设N是自然数集合，函数是（）。1,NFNF，A满射，不是单射；B单射，不是满射；C双射；D非单射非满射B设R为实数集，函数FRR，FX，则F是（）。XEA满射函数；B单射函数；C双射函数；D非单射非满射B设Z是整数集合，N是自然数集合，则函数是（）。XFNZF，A满射，不是单射；B单射，不是满射；C双射；D非单射非满射A设函数FNN（N为自然数集），FNN1，下面四个命题为真的是（）。AF是满射；BF是单射；CF是双射的；DF非单射非满射B谓词公式XPXYRYQX中的变元X是（）。A自由出现的；B约束出现的；C既不是自由出现也不是约束出现；D既是自由出现也是约束出现D下列不是谓词公式的是（）。AAXYP（X，Y）；BXPXXQXAX，Y；CXP（X）R（Y）；DXP（X）Q（Y，Z）下列句子为命题的是（）。A全体起立BX0；C你会抽烟吗D张三生于1886年的春天D下列命题正确的是（）。A；B；CAA，B，C；DA，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平面图B下列图中不是平面图的为（）。ABCDC下列为公式的是（）。A；B；SRQSRPC；DQPQPC下列语句中，（）是命题。A下午有会吗B这朵花多好看呀C2是偶数；D请把门关上C下列语句中是假命题的是（）。CA5是素数；B太阳从东方升起；C；D正在下雨呢123下列语句中是命题的是（）。A天气真暖和呀B请别激动C还记得我吗D地球是运动的D下面既是哈密顿图又是欧拉图的是（）。B一个连通图G具有以下何种条件时，能一笔画出即从某结点出发，经过图中每边仅一次回到该结点（）。AG没有奇数度的结点；BG有1个奇数度的结点；CG有2个奇数度的结点；DG没有或有2个奇数度的结点A在自然数集合上，下列运算满足结合律的是（）。ABABMIN,ABCDB二、填空题令P今天下雪了，Q路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为_。PQ设明天上午8点下雨，明天上午8点下雪，我去学校，则命R题“如果明天上午8点不下雨并且也不下雪，我就去学校”可符号化为。R设是偶数，是素数，则命题“存在着偶素数”可符号XFXG化为_。XGFXN个顶点的无向完全图记为，当N满足条件_时,不是平KNK面图。4设我们勤奋，我们好学，我们取得好成绩，则命题“我们只PQR要勤奋好学，就能取得好成绩”符号化为。RQP设A（X）X是人，B（X）X犯错误，命题“没有不犯错误的人”符号化为_。XBAX或设G是连通的平面图，已知G中有6个顶点，8条边，则G有_个面。4设P他聪明，Q他用功，则命题“他虽聪明,但不用功”可符号化为_。PQ设集合，则。3,21A5,4BBA2,1设集合，则。CBADCDA设集合，则A的幂集。,P,设集合，则A的幂集。21答案,设是人，要吃饭，则命题“人都是要吃饭的”XMXP可符号化为_。答案XX设是跳高运动员，A小张，则命题“小张不是跳高运动员”可符号化为_。AM无向图G如右所示，则图G的最大度数G_。4无向图G中有16条边，且每个结点的度数都是2，则G的结点数是_个。16无向完全图中有_条边。5K10已知关系,1DBAR,2CCBDA则_。1答案,DAC已知关系,则。,DBR2R,DABA已知关系，,1CBABR,2ABR则。2答案,CA已知关系,则。,BCDCBDR3R答案,C三、计算题构造命题公式（PQ）Q的真值表，并判断其类型。解真值表PQPQ（PQ）（PQ）Q00100011001001011100因此公式（PQ）Q为矛盾式对某单位的100名员工进行调查，结果发现他们喜欢看球赛、电影和戏剧其中58人喜欢看球赛，52人喜欢看电影，38人喜欢看戏剧，既喜欢看球赛又喜欢看戏剧的有18人，既喜欢看电影又喜欢看戏剧的有16人，三种都喜欢看的有12人，求只喜欢看电影的有多少人。解设喜欢看球赛、电影和戏剧的人的集合分别为A,B,C，那么58，52，38，ABC18，16,12，只喜欢看电影的有22人构造命题公式（PQ）R的真值表，并判断其类型。ABC261422612416解真值表为PQRPQR（PQ）R000001010011100101110111111100111010101010100010公式（PQ）R为可满足式构造命题公式的真值表，并判断其类型。RQP解真值表为RRQP0000010100111001011101110000001110101011公式为可满足式RQP集合上的关系，3,2A3,2,1,32,2,R试写出关系矩阵M，并讨论R的性质。解关系矩阵，R是自反的和传递的10集合上的关系，3,21A3,23,2,试写出关系矩阵M，并讨论R的性质。解关系矩阵，R具有反对称性和传递性10M集合上的关系，3,21A3,1,2,1,试写出关系矩阵M，并讨论R的性质。解关系矩阵，10R是自反的，反对称的和传递的集合上的关系4,321A，4,3,4,3,1,试写出关系矩阵M，并讨论R的性质。解关系矩阵，10R具有自反性和对称性今有工人甲、乙、丙去完成三项任务A、B、C已知甲能胜任A、B、C三项任务；乙能胜任A、B二项任务；丙能胜任B、C二项任务试给出一种方案，使每个工人各去完成一项他们能胜任的任务。解工人与任务的胜任关系的二部图为甲乙丙ABC一种方案是甲完成A，乙完成B，丙完成C（注本题答案不唯一，还可以给出其它的方案）某班有学生50人，有26人在第一次考试中得优，有21人在第二次考试中得优，有17人两次考试都没有得优，试求两次考试都得优的学生人数。解设两次考试都得优的学生人数为X人，由下列文氏图可知1726XX21X50，解得X14，两次考试都得优的学生人数为14人某大学计算机专业的80名学生在期末考试中，PASCAL语言课有58人达到优秀，数据结构课有30人达到优秀，离散数学课有25人达到优秀并且，PASCAL语言和数据结构两门课都达到优秀的有20人，PASCAL语言和离散数学两门课都达到优秀的有19人，数据结构和离散数学两门课都达到优秀的有17人，还有10人一门优秀都没得到求三门课都达到优秀的人数。解设期末考试中PASCAL语言课、数据结构课、离散数学课达到优秀的学生集合分别为A,B,C，那么58，30，25，C20，19，17AB由题意，至少有一门课达到优秀的学生人数为8070于是，三门课都达到优秀的学生数为CBAABC7058302520191713求图中A到其余各顶点的最短路径的权（要求列表）。B5D12A433F35C1E解用用标号法解题过程如下BCDEF1726XX21X01311364236436494685813648求图中A点到其余各顶点的最短路径的权（要求列表）。B7C12A253D46E1F解用用标号法解题过程如下BCDEF014118362834371044795917934求下面所示带权图中顶点A到其余各顶点的最短路径的权（要求列表）。1125648BCDEF解用用标号法解题过程如下BCDEF0812131722373233734535531532求下面所示带权图中顶点A到其余各顶点的最短路径的权（要求列表）。142589263ABCDEF解用用标号法解题过程如下BCDEF042132101123811381014410135133281013设，定义A上的二元运算如下对，（表示XY4,21AAYX,5MODXY除以5的余数），试求的运算表。解运算表如下12341432设，定义A上的二元运算如下对，的最大公约0,5AAYX,YX与数，试给出的运算表。解运算表如下1052101052设，定义A上的二元运算如下对，的最小公倍,AAYX,YX与数，试给出的运算表。解运算表如下101055210设，试给出A上运算的运算表。,A解运算表如下10设个体域为1，2，1P02A求公式的真值。XA解212PP010设个体域为1，2，求公式的真值AAPX解APX101021设无向图G有4个顶点，度数分别为1，2，2，3，问G中有几条边依据是什么并画出一个符合上述条件的图。解图G有4条边，依据是握手定理12232M，M4下面的图就符合上述条件设无向图G有5个顶点，度数分别为1，1，2，2，4，问G中有几条边依据是什么并画出一个符合上述条件的图。解图G有5条边，依据是握手定理112242M，M5下面的图就符合上述条件题公式（PP）Q的真值表，并判断其类型。解真值表为PQPPP（PP）Q00101011001000111000因此公式（PP）Q为可满足式现有三个课外小组物理组、化学组、生物组，今有张、王、李、赵、陈5名同学，已知张、王为物理组成员，张、李、赵为化学组成员，李、陈为生物组成员，问在这种情况下能否选出3名不兼职的组长若能选出，试给出一种方案。解可以选出3名不兼职的组长物理组化学组生物组张王李赵陈一种方案是张任物理组的组长，李任化学组的组长，陈任生物组的组长（注本题答案不唯一，还可以给出其它的方案）一棵无向树有1个2度的顶点，3个3度的顶点，其余点都是树叶，求该树的叶子数并画出一棵符合上述条件的树。解设该树的叶子数为X个，则29X2（4X1）解得X5，即有5个树叶子下面的这棵树就符合上述条件一棵无向树有4个树叶，1个2度的顶点，其余的点度数都为3，该树共有几个点画出一棵符合上述条件的树。解设该树中3度的点有X个，则423X2（41X1）解得X2，从而该树共有7个点下面的这棵树就符合上述条件已知公式，其中，XGFX1XF2XG且个体域为1，2，求该式的真值。解21XX010已知公式，其中，且个体域为XBRX3XR4XB3，4，求该式的真值。解43XX110有150人至少喜欢游泳或跑步中的一种若85人喜欢游泳，60人同时喜欢游泳和跑步，问有多少人喜欢跑步解由下列文氏图可知256065喜欢跑步而不喜欢游泳的人数为1508565因此喜欢跑步的人数为6560125有四个信息C，AC，BD，ABD，现想分别用组成每个信息的字母中的一个来表示该信息，这是否可能如果可能，应如何表示解可以做到CACBDABD一种方案是C表示C，A表示AC，B表示BD，D表示ABD有张、王、李、赵四位教师，要分配他们教数学、物理、化学、英语等四门课程张熟悉物理和英语，王熟悉数学和化学，李熟悉数学、物理和英语，赵只熟悉英语。（1）画出关于教师熟悉课程的二部图；（2）如何分配，才能使每位教师都教一门自己熟悉的课程解（1）画出二部图张王李赵数学物理化学英语（2）张物理；王化学；李数学；赵英语四、证明构造下列推理的证明前提，结论。SPRQP,Q证明（1）前提引入SR（2）前提引入（3）（1），（2）析取三段论（4）前提引入RQPABCD（5）（3），（4）拒取式QP（6）（5）置换（7）前提引入（8）（6），（7）析取三段论设Z表示整数集,在Z上定义二元运算，证明Z关于运算构3,BAZBA成群。证根据群的定义，需证明运算满足结合律、有么元和每个元素都有逆元对,有ABCABC3AB3C3ABC6，ZCBA,而ABCABC3ABC33ABC6，故ABCABC,结合律成立3是么元,事实上,A3A33A,3A3A3A,对，A6AA6A33,6AA6AA33,可知6A是A的逆元Z因此，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上定义ABAB9,证明是一个群。,证显然是二元运算,根据群的定义，需证明运算满足结合律、有幺元和每个元素都有逆元。对,有ABCABC9AB5C9ABC18C而ABCABC9ABC99ABC18故ABCABC,结合律成立。9是幺元,事实上A9A99A,9A9A9A,Z对，A18AA18A99,18AA18AA99,可知18A是A的逆元。Z构造下列推理的证明前提PQ,QR,PS,S，结论RPQ证明PS前提引入S前提引入P拒取式PQ前提引入Q析取三段论QR前提引入R假言推理RPQ合取设，其中R为实数集，定义1SABA证明构成群。,证根据群的定义，需证明运算满足结合律、有么元和每个元素都有逆元