《离散数学复习思考题——2022年整理.pdf》由会员分享，可在线阅读，更多相关《离散数学复习思考题——2022年整理.pdf（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 2023 年整理优质考试试题资料，欢迎下载 1/16 离散数学复习思考题离散数学复习思考题 一、一、选择题选择题 对于公式),(),(),(zxzRzxQyxPx，下列说法正确的是（）。A y是自由出现的；Bx是约束出现的；Cx的辖域是),(),(),(zxzRzxQyxP；Dx的辖域是),(yxP A 设,8,7,6,5,4,3,2,1A，下列正确的是（）。AA1；BA3,2,1；CA；DA3,2,1 D 设 A-B=，则有（）。AB=；BB；CAB；DAB C 设 N 是自然数集合，函数1,)(nnnfNNNf，：是（）。A 满射，不是单射；B单射，不是满射；C双射；D非单射非满射 B
2、设 R 为实数集，函数f：RR，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)中的变元 x 是（）。A自由出现的；B约束出现的；C既不是自由出现也不是约束出现；D既是自由出现也是约束出现 D 下列不是谓词公式的是（）。AxyP（x，y）
3、；Bx(P(x)x(Q(x)A(x，y)；CxP（x）R（y）；DxP（x）Q（y，z）A 下列句子为命题的是（）。A全体起立!Bx=0；C你会抽烟吗？D张三生于 1886 年的春天 D 下列命题正确的是（）。A=；B=；Caa，b，c；Da，b，c A 下列命题正确的是（）。Al，21，2，l，2，3，1；B 2023 年整理优质考试试题资料，欢迎下载 2/16 B1，21，l，2，l，2，3，2；C1，21，2，1，2；D1，21，2，2，l，2，3 下列图形是（）。A完全图；B哈密顿图 ；C欧拉图；D平面图 B 下列图中不是平面图的为（）。A.A.B B C C D D C 下列为公式的
4、是（）。Asrq；B)(srp；C)()(pqqp；Dqprs C 下列语句中，（）是命题。A下午有会吗？B这朵花多好看呀！C2 是偶数；D请把门关上!C 下列语句中是假命题的是（）。A5 是素数；B太阳从东方升起；C1235；D正在下雨呢！C 下列语句中是命题的是（）。A天气真暖和呀！B请别激动！C还记得我吗？D地球是运动的 D 下面既是哈密顿图又是欧拉图的是（）。B 2023 年整理优质考试试题资料，欢迎下载 3/16 一个连通图 G 具有以下何种条件时，能一笔画出：即从某结点出发，经过图中每边仅一次回到该结点（）。AG 没有奇数度的结点；BG 有 1 个奇数度的结点；CG 有 2 个奇数
5、度的结点；DG 没有或有 2 个奇数度的结点 A 在自然数集合上，下列运算满足结合律的是（）。A2a bab Bmin,a ba b Ca bab Da bab B 二、二、填空题填空题 令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为_。pq 设p：明天上午 8 点下雨，q：明天上午 8 点下雪，r：我去学校，则命题“如果明天上午 8 点不下雨并且也不下雪，我就去学校”可符号化为 。rqp)(设)(xF：x是偶数，)(xG：x是素数，则命题“存在着偶素数”可符号化为_。)()(xGxFx n 个顶点的无向完全图记为nK，当 n 满足条件_时,nK不是平面图。4n 设
6、p：我们勤奋，q：我们好学，r：我们取得好成绩，则命题“我们只要勤奋好学，就能取得好成绩”符号化为 。rqp)(设 A（x）：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 2023 年整理优质考试试题资料，欢迎下载 4/16 设集合2,1A，则A的幂集)(AP 。2,1,2,1,
7、设集合2,1A，则A的幂集)(AP 。答案：2,1,2,1,设xxM:)(是人，xxP:)(要吃饭，则命题“人都是要吃饭的”可符号化为_。答案：)()(xPxMx 设xxM:)(是跳高运动员，a：小张，则命题“小张不是跳高运动员”可符号化为_。)(aM 无向图 G=如右所示，则图 G 的最大度数 (G)=_。4 无向图 G 中有 16 条边，且每个结点的度数都是 2，则 G 的结点数是_个。16 无向完全图5K中有_条边。10 已知关系,1dbbaaaR,2bcdbcbdaR,则12RR=_。答案：,daca 已知关系,dbbaaaR,则2R=。,dabaaa 已知关系,1cbcabaR，,2
8、aabaR，则21RR=。答案：,baca 已知关系,bcdbcbdaR,则3R=。答案：,dbcbbc 三、三、计算题计算题 2023 年整理优质考试试题资料，欢迎下载 5/16 构造命题公式（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 人，既喜欢看电影又喜欢看戏剧的有 16 人
9、，三种都喜欢看的有 12 人，求只喜欢看电影的有多少人。解：设喜欢看球赛、电影和戏剧的人的集合分别为 A,B,C，那么 A=58，B=52，C=38，AC=18，BC=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 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 公式（PQ）R为可满足式 构造命题公式rqp的真值表，并判断其类型。解：真值表为 rqp qp rq
10、p A B C 26 14 22 6 12 4 16 2023 年整理优质考试试题资料，欢迎下载 6/16 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,1R，试写出关系矩阵 M，并讨论 R 的性质。解：关系矩阵111011011M，R 是自反的和传递的 集合3,2,1A上的关系3,3,3,2,3,1,2,1R，试写出关系矩阵 M，并讨论 R 的性质。解：关系矩阵100100110M，
11、R 具有反对称性和传递性 集合3,2,1A上的关系3,3,1,3,2,2,1,2,1,1R，试写出关系矩阵 M，并讨论 R 的性质。解：关系矩阵101011001M，R 是自反的，反对称的和传递的 集合4,3,2,1A上的关系4,4,3,4,4,3,3,3,1,3,2,2,3,1,1,1R，试写出关系矩阵 M，并讨论 R 的性质。解：关系矩阵1100110100100101M，R 具有自反性和对称性 2023 年整理优质考试试题资料，欢迎下载 7/16 今有工人甲、乙、丙去完成三项任务a、b、c已知甲能胜任a、b、c 三项任务；乙能胜任a、b 二项任务；丙能胜任b、c 二项任务试给出一种方案，
12、使每个工人各去完成一项他们能胜任的任务。解：工人与任务的胜任关系的二部图为：甲 乙 丙 a b c 一种方案是：甲完成a，乙完成 b，丙完成 c（注：本题答案不唯一，还可以给出其它的方案）某班有学生 50 人，有 26 人在第一次考试中得优，有 21 人在第二次考试中得优，有 17 人两次考试都没有得优，试求两次考试都得优的学生人数。解：设两次考试都得优的学生人数为x人，由下列文氏图可知 17+(26-x)+x+(21-x)=50，解得：x=14，两次考试都得优的学生人数为 14 人 某大学计算机专业的 80 名学生在期末考试中，Pascal 语言课有 58 人达到优秀，数据结构课有 30 人
13、达到优秀，离散数学课有 25 人达到优秀并且，Pascal 语言和数据结构两门课都达到优秀的有 20 人，Pascal 语言和离散数学两门课都达到优秀的有 19 人，数据结构和离散数学两门课都达到优秀的有 17 人，还有 10 人一门优秀都没得到 求三门课都达到优秀的人数。解：设期末考试中 Pascal 语言课、数据结构课、离散数学课达到优秀的学生集合分别为A,B,C，那么 A=58，B=30，C=25，AB=20，AC=19，BC=17 由题意，至少有一门课达到优秀的学生人数为 CBA=80-)(CBA=70 于是，三门课都达到优秀的学生数为：CBA=17 26-x x 21-x 2023
14、年整理优质考试试题资料，欢迎下载 8/16 CBA-(A+B+C-AB-AC-BC)=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 B C C D D E E F F 0 0 1 1 3 3 1 1 1*1*3 3 6 6 4 4 2 2 3*3*6 6 4 4 3 3 6 6 4*4*9 9 4 4 6*6*8 8 5 5 8*8*1 1 3 3 6 6 4 4 8 8 求图中 A 点到其余各顶点的最短路径的权（要求列表）。B 7 C 1 2 A
15、2 5 3 D 4 6 E 1 F 解：用用标号法解题过程如下：B B C C D D E E F F 0 0 1 1 4 4 1 1 1*1*8 8 3 3 6 6 2 2 8 8 3*3*4 4 3 3 7 7 1010 4*4*4 4 7*7*9 9 5 5 9*9*1 1 7 7 9 9 3 3 4 4 求下面所示带权图中顶点 A 到其余各顶点的最短路径的权（要求列表）。2023 年整理优质考试试题资料，欢迎下载 9/16 112256248ABCDEF 解：用用标号法解题过程如下：B B C C D D E E F F 0 0 8 8 1 1 2 2 1 1 3 3 1*1*7 7
16、2 2 2 2 3 3 7 7 3 3 2*2*3 3 3*3*7 7 3 3 4 4 5 5 3*3*5 5 5*5*3 3 1 1 5 5 3 3 2 2 求下面所示带权图中顶点 A 到其余各顶点的最短路径的权（要求列表）。解：用用标号法解题过程如下 B B C C D D E E F F 0 0 4 4 2 2 1 1 3 3 2*2*1010 1111 2 2 3*3*8 8 1111 3 3 8*8*1010 1414 4 4 10*10*1313 5 5 13*13*3 3 2 2 8 8 1010 1313 设4,3,2,1A，定义 A 上的二元运算*如下：对Ayx,，5mod)
17、(xyyx（表示xy除以 5 的余数），试求*的运算表。1 4 2 5 8 9 2 6 3 A B C D E F 2023 年整理优质考试试题资料，欢迎下载 10/16 解：运算表如下：123442413331422432114321 设10,5,2,1A，定义 A 上的二元运算*如下：对Ayx,，yxyx与的最大公约数，试给出*的运算表。解：运算表如下：105211055115212121111110521 设10,5,2,1A，定义 A 上的二元运算*如下：对Ayx,，yxyx与的最小公倍数，试给出*的运算表。解：运算表如下：1010101010105105510102221052111
18、0521 设1,0A，试给出 A 上运算的运算表。解：运算表如下 10111010 设个体域为1，2，1)1(P，0)2(P，2a，求公式)()(xxPaP的真值。解：)2()1()2()()(PPPxxPaP 110)01(0 2023 年整理优质考试试题资料，欢迎下载 11/16 设个体域为1，2，0)1(P，1)2(P，1a，求公式)()(aPxxP的真值 解：)()(aPxxP 1000)10()1()2()1(PPP 设无向图 G 有 4 个顶点，度数分别为 1，2，2，3，问G中有几条边？依据是什么？并画出一个符合上述条件的图。解：图 G 有 4 条边，依据是握手定理：1+2+2+
19、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 Q P PP （PP）Q 0 0 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 0 0 0 因此公式（PP）Q 为可满足式 现有三个课外小组：物理组、化学组、生物组，今有张、王、李、赵、陈 5 名同学，已知张、王为物理组成员，张、李、赵为化学组成员，李、陈为生物组成
20、员，问在这种情况下能否选出 3 名不兼职的组长？若能选出，试给出一种方案。解：可以选出 3 名不兼职的组长 2023 年整理优质考试试题资料，欢迎下载 12/16 物理组 化学组 生物组 张 王 李 赵 陈 一种方案是：张任物理组的组长，李任化学组的组长，陈任生物组的组长（注：本题答案不唯一，还可以给出其它的方案）一棵无向树有 1 个 2 度的顶点，3 个 3 度的顶点，其余点都是树叶，求该树的叶子数并画出一棵符合上述条件的树。解：设该树的叶子数为x个，则2+9+x=2（4+x-1）解得x=5，即有 5 个树叶子 下面的这棵树就符合上述条件：一棵无向树有 4 个树叶，1 个 2 度的顶点，其余
21、的点度数都为 3，该树共有几个点？画出一棵符合上述条件的树。解：设该树中 3 度的点有x个，则 4+2+3x=2（4+1+x-1）解得x=2，从而该树共有 7 个点 下面的这棵树就符合上述条件：已知公式)()(xGxFx，其中1)(xxF：，2)(xxG：，且个体域为1，2，求该式的真值。解：)2()2()1()1()()(GFGFxGxFx 000)10()01(已知公式)()(xBxRx，其中3)(xxR：，4)(xxB：，且个体域为 3，4，求该式的真值。解：)4()4()3()3()()(BRBRxBxRx 111)10()01(有 150 人至少喜欢游泳或跑步中的一种若 85 人喜欢
22、游泳，60 人同时喜欢游泳和跑步，问 2023 年整理优质考试试题资料，欢迎下载 13/16 有多少人喜欢跑步？解：由下列文氏图可知 喜欢跑步而不喜欢游泳的人数为：150-85=65 因此喜欢跑步的人数为：65 60=125 有四个信息c，ac，bd，abd，现想分别用组成每个信息的字母中的一个来表示该信息，这是否可能？如果可能，应如何表示？解：可以做到：c ac bd abd 一种方案是：c 表示 c，a表示ac，b表示bd，d表示abd 有张、王、李、赵四位教师，要分配他们教数学、物理、化学、英语等四门课程张熟悉物理和英语，王熟悉数学和化学，李熟悉数学、物理和英语，赵只熟悉英语。（1）画出
23、关于教师熟悉课程的二部图；（2）如何分配，才能使每位教师都教一门自己熟悉的课程？解：（1）画出二部图 张 王 李 赵 数学 物理 化学 英语 （2）张：物理；王：化学；李：数学；赵：英语 四、四、证明证明 构造下列推理的证明前提：spsrrqp,)(，结论：q。证明：a b c d 25 60 65 2023 年整理优质考试试题资料，欢迎下载 14/16（1）sr 前提引入（2）s 前提引入（3）r （1），（2）析取三段论 （4）rqp)(前提引入 （5）)(qp （3），（4）拒取式 （6）qp （5）置换（7）p 前提引入（8）q （6），（7）析取三段论 设 Z 表示整数集,在 Z 上
24、定义二元运算:3,babaZba，证明:Z 关于运算构成群。证：根据群的定义，需证明运算满足结合律、有么元和每个元素都有逆元.对Zcba,有(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 是么元,事实上：Za,a*(-3)=a+(-3)+3=a,(-3)*a=(-3)+a+3=a,对Za，a*(-6-a)=a+(-6-a)+3=-3,(-6-a)*a=(-6-a)+a+3=-3,可知-6-a是a的逆元因此，Z 关于运算构成群.构造下列推理
25、的证明：前提：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,Zba,证明:是一个群。证 显然*是二元运算,根据群的定义，需证明运算满足结合律、有幺元和每个元素都有逆元。对Zcba,有(a*b)*c=(a*b)+c-9=(a+b-5)+c-9=a+b+c-18 而 a*(b*c)=a+(b*c)-9=a+(b+c-9)-9=a+b+c-18 故(a*b)*c=a*(b*c)
26、,结合律成立。9 是幺元,事实上：a*9=a+9-9=a,9*a=9+a-9=a,Za 对Za，a*(18-a)=a+(18-a)-9=9,(18-a)*a=(18-a)+a-9=9,可知 18-a 是 a 的逆元。构造下列推理的证明：前提：pq,qr,ps,s，结论：r(pq)证明：ps 前提引入 2023 年整理优质考试试题资料，欢迎下载 15/16 s 前提引入 p 拒取式 pq 前提引入 q 析取三段论 qr 前提引入 r 假言推理 r(pq)合取 设1 RS，其中R为实数集，定义abbaba 证明,S构成群。证：根据群的定义，需证明运算满足结合律、有么元和每个元素都有逆元.对Szyx
27、,有 zxyyxzxyyxzxyyxzyx)()()()(xyzyzxzxyzyx xyzyzxzxyzyxyzzyxyzzyxyzzyxzyx)()()()(故(x*y)*z=x*(y*z),结合律成立.0 是么元,事实上：x*0=x,0*x=x,Sx Sx，xxxx11都有逆元，逆元为 因此，,S构成群 构造下列推理的证明：前提：p(qr),sq,ps，结论：r 证明：ps 前提引入 p 化简 s 化简 p(qr)前提引入 qr 假言推理 sq 前提引入 q 假言推理 r 析取三段论 在集合RR上定义运算如下：byaxbayx,，试证明,RR是群。证：根据群的定义，需证明运算满足结合律、有么元和每个元素都有逆元.因为vbyuaxvubayx,),(，而vbyuaxvubayx,),(,所以，*运算满足结合律 2023 年整理优质考试试题资料，欢迎下载 16/16 因为yxyxyx,0,00,0,，yxyxyx,0,0,0,0 所以，关于*运算存在幺元为0,0 因为0,0)(),(,yyxxyxyx，0,0)(,)(,yyxxyxyx 所以，yxyx,1 因此，,RR是群