离散数学复习思考题-2022年整理

优质资料word版本——下载后可编辑优质资料word版本——下载后可编辑16/16优质资料word版本——下载后可编辑《离散数学》复习思考题一、选择题对于公式，下列说法正确的是（）。y是自由出现的；B．x是约束出现的；C．的辖域是；D．的辖域是．A设，下列正确的是（）。A．；B．；C．；D．．D设A-B=，则有（）。A．B=；B．B≠；C．AB；D．AB．C设N是自然数集合，函数是（）。满射，不是单射；B．单射，不是满射；C．双射；D．非单射非满射．B设R为实数集，函数f：R→R，f(x)=，则f是（）。A．满射函数；B．单射函数；C．双射函数；D．非单射非满射．B设Z是整数集合，N是自然数集合，则函数是（）。满射，不是单射；B．单射，不是满射；C．双射；D．非单射非满射．A设函数f：N→N（N为自然数集），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下列不是谓词公式的是（）。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．{a}{a，b，c}；D．{a，b，c}．A下列命题正确的是（）。A．{l，2}{{1，2}，{l，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．；B．；C．；D．．C下列语句中，（）是命题。A．下午有会吗？B．这朵花多好看呀！C．2是偶数；D．请把门关上!C下列语句中是假命题的是（）。A．5是素数；B．太阳从东方升起；C．；D．正在下雨呢！C下列语句中是命题的是（）。A．天气真暖和呀！B．请别激动！C．还记得我吗？D．地球是运动的．D下面既是哈密顿图又是欧拉图的是（）。B一个连通图G具有以下何种条件时，能一笔画出：即从某结点出发，经过图中每边仅一次回到该结点（）。A．G没有奇数度的结点； B．G有1个奇数度的结点；C．G有2个奇数度的结点；D．G没有或有2个奇数度的结点．A在自然数集合上，下列运算满足结合律的是（）。A．B．C．D．B二、填空题令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为_______。p∧┐q设：明天上午8点下雨，：明天上午8点下雪，：我去学校，则命题“如果明天上午8点不下雨并且也不下雪，我就去学校”可符号化为。设：是偶数，：是素数，则命题“存在着偶素数”可符号化为_______。n个顶点的无向完全图记为，当n满足条件__________时,不是平面图。设：我们勤奋，：我们好学，：我们取得好成绩，则命题“我们只要勤奋好学，就能取得好成绩”符号化为。设A（x）：x是人，B（x）：x犯错误，命题“没有不犯错误的人”符号化为_______。或设G是连通的平面图，已知G中有6个顶点，8条边，则G有_______个面。4设P：他聪明，Q：他用功，则命题“他虽聪明,但不用功”可符号化为_______。P∧Q设集合，，则。设集合，，则。设集合，则A的幂集。设集合，则A的幂集。答案：设是人，要吃饭，则命题“人都是要吃饭的”可符号化为_______。答案：设是跳高运动员，a：小张，则命题“小张不是跳高运动员”可符号化为_______。无向图G=<V,E>如右所示，则图G的最大度数Δ(G)=_______。4无向图G中有16条边，且每个结点的度数都是2，则G的结点数是_______个。16无向完全图中有________条边。10已知关系,,则=_______。答案：已知关系,则=。已知关系，，则=。答案：已知关系,则=。答案：三、计算题构造命题公式（PQ）Q的真值表，并判断其类型。解：真值表PQPQ（PQ）（PQ）Q00100011001001011100因此公式（PQ）Q为矛盾式．对某单位的100名员工进行调查，结果发现他们喜欢看球赛、电影和戏剧．其中58人喜欢看球赛，52人喜欢看电影，38人喜欢看戏剧，既喜欢看球赛又喜欢看戏剧的有18人，既喜欢看电影又喜欢看戏剧的有16人，三种都喜欢看的有12人，求只喜欢看电影的有多少人。解：设喜欢看球赛、电影和戏剧的人的集合分别为A,B,C，那么=58，=52，=38，=18，=16,=12，ABC261422612416只喜欢看电影的有22人．构造命题公式（PQ）∧R的真值表，并判断其类型。解：真值表为：PQRPQR（PQ）∧R000001010011100101110111111100111010101010100010公式（PQ）∧R为可满足式．构造命题公式的真值表，并判断其类型。解：真值表为0000010100111001011101110000001110101011公式为可满足式．集合上的关系，试写出关系矩阵M，并讨论R的性质。解：关系矩阵，R是自反的和传递的．集合上的关系，试写出关系矩阵M，并讨论R的性质。解：关系矩阵，R具有反对称性和传递性．集合上的关系，试写出关系矩阵M，并讨论R的性质。解：关系矩阵，R是自反的，反对称的和传递的．集合上的关系，试写出关系矩阵M，并讨论R的性质。解：关系矩阵，R具有自反性和对称性．今有工人甲、乙、丙去完成三项任务a、b、c．已知甲能胜任a、b、c三项任务；乙能胜任a、b二项任务；丙能胜任b、c二项任务．试给出一种方案，使每个工人各去完成一项他们能胜任的任务。解：工人与任务的胜任关系的二部图为：甲乙丙abc一种方案是：甲完成a，乙完成b，丙完成c．（注：本题答案不唯一，还可以给出其它的方案．）某班有学生50人，有26人在第一次考试中得优，有21人在第二次考试中得优，有17人两次考试都没有得优，试求两次考试都得优的学生人数。解：设两次考试都得优的学生人数为x人，由下列文氏图可知171726-xx21-x17+(26-x)+x+(21-x)=50，解得：x=14，两次考试都得优的学生人数为14人．某大学计算机专业的80名学生在期末考试中，Pascal语言课有58人达到优秀，数据结构课有30人达到优秀，离散数学课有25人达到优秀．并且，Pascal语言和数据结构两门课都达到优秀的有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到其余各顶点的最短路径的权（要求列表）。B5D12A433F35C1E解：用用标号法解题过程如下BCDEF01311*36423*64364*946*858*13648求图中A点到其余各顶点的最短路径的权（要求列表）。B7C12A253D6E1F解：用用标号法解题过程如下：BCDEF01411*836283*437104*47*959*17934求下面所示带权图中顶点A到其余各顶点的最短路径的权（要求列表）。解：用用标号法解题过程如下：BCDEF0812131*7223732*33*73453*55*3153214258142589263ABCDEF解：用用标号法解题过程如下BCDEF042132*101123*81138*1014410*13513*3281013设，定义A上的二元运算*如下：对，（表示xy除以5的余数），试求*的运算表。解：运算表如下：设，定义A上的二元运算*如下：对，的最大公约数，试给出*的运算表。解：运算表如下：设，定义A上的二元运算*如下：对，的最小公倍数，试给出*的运算表。解：运算表如下：设，试给出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的真值表，并判断其类型。解：真值表为：PQPPP（PP）Q00101011001000111000因此公式（PP）Q为可满足式．现有三个课外小组：物理组、化学组、生物组，今有张、王、李、赵、陈5名同学，已知张、王为物理组成员，张、李、赵为化学组成员，李、陈为生物组成员，问在这种情况下能否选出3名不兼职的组长？若能选出，试给出一种方案。解：可以选出3名不兼职的组长．物理组化学组生物组张王李赵陈一种方案是：张任物理组的组长，李任化学组的组长，陈任生物组的组长．（注：本题答案不唯一，还可以给出其它的方案．）一棵无向树有1个2度的顶点，3个3度的顶点，其余点都是树叶，求该树的叶子数．并画出一棵符合上述条件的树。解：设该树的叶子数为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人同时喜欢游泳和跑步，问有多少人喜欢跑步？解：由下列文氏图可知25256065喜欢跑步而不喜欢游泳的人数为：150-85=65因此喜欢跑步的人数为：65＋60=125有四个信息c，ac，bd，abd，现想分别用组成每个信息的字母中的一个来表示该信息，这是否可能？如果可能，应如何表示？解：可以做到：cacbdabddcbadcba一种方案是：c表示c，a表示ac，b表示bd，d表示abd．有张、王、李、赵四位教师，要分配他们教数学、物理、化学、英语等四门课程．张熟悉物理和英语，王熟悉数学和化学，李熟悉数学、物理和英语，赵只熟悉英语。（1）画出关于教师熟悉课程的二部图；（2）如何分配，才能使每位教师都教一门自己熟悉的课程？解：（1）画出二部图张王李赵数学物理化学英语（2）张：物理；王：化学；李：数学；赵：英语．四、证明构造下列推理的证明．前提：，结论：。证明：（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),结合律成立.-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,,证明:<Z,*>是一个群。证显然*是二元运算,根据群的定义，需证明运算满足结合律、有幺元和每个元素都有逆元。对,有(a*b)*c=(a*b)+c-9=(a+b-5)+c-9=a+b+c-18而a*(b*c)=a+(b*c)-9=a+