华东师范大学《离散数学》2022-2023第一学期期末考试试卷

华东师范大学《离散数学》2022-2023第一学期期末考试试卷班级：__________姓名：__________学号：__________得分：__________说明：1.本试卷满分100分，考试时间120分钟；2.答题需写清步骤，仅写答案不得分；3.所有答案写在答题纸上，试卷上答题无效。一、单项选择题（每题2分，共20分）下列语句中，属于命题的是（）

A.离散数学真难啊！B.请打开课本C.2是偶数且3是质数D.x+5>3

设P：明天晴天，Q：我们去野餐，则命题“如果明天不是晴天，我们就不去野餐”的符号化表示为（）

A.¬P→¬QB.P→¬QC.¬Q→¬PD.Q→P

设集合A={1,2,3,4}，B={2,4,6}，则A∩B=（）

A.{1,2,3,4,6}B.{2,4}C.{1,3}D.∅

设集合A有5个元素，B有3个元素，则A到B的满射函数个数为（）

A.3⁵B.5³C.C(5,3)×3!D.0

设R是集合A={1,2,3}上的二元关系，R={(1,1),(2,2),(1,2),(2,1)}，则R具有（）

A.自反性、传递性B.对称性、传递性C.自反性、对称性D.反对称性、传递性

下列关于图论的说法中，正确的是（）

A.无向完全图K₅是平面图B.n阶树有n-1条边且连通

C.有欧拉回路的图一定有哈密顿回路D.图的色数一定不大于其顶点数

命题公式(P∨Q)→(P∧Q)的主析取范式中，极小项的个数为（）

A.1B.2C.3D.4

设G是有6个顶点、8条边的连通无向图，则G的面数为（）

A.3B.4C.5D.6

下列集合中，与集合{1,2,3}等势的是（）

A.自然数集NB.整数集ZC.{1,2,3,4}D.偶自然数集

利用费马小定理，计算2¹⁰⁰mod7的值为（）

A.1B.2C.4D.6

二、填空题（每题2分，共20分）命题公式¬(P∧Q)∨(¬P∧Q)的等价式为__________。设集合A={a,b}，则A的幂集P(A)=__________。设R是A到B的关系，S是B到C的关系，则复合关系R∘S的定义域是__________。无向图G中，所有顶点的度数之和等于边数的__________倍。设P(x)：x是偶数，Q(x)：x是质数，定义域为自然数集，则命题“存在既是偶数又是质数的自然数”的符号化表示为__________。设集合A={1,2,3,4}，R是A上的整除关系，则R的哈塞图中，极大元为__________。命题公式P→Q的逆否命题是__________。设G是n阶无向简单图，若G是完全图，则G的边数为__________。若关系R是自反的、对称的、传递的，则R称为__________关系。设函数f:A→B，g:B→C，若f和g都是双射，则g∘f是__________。三、计算题（每题10分，共30分）已知命题公式A=(P→Q)∧(Q→R)，求：（1）A的真值表；（2）A的主合取范式。设集合A={1,2,3,4}，R={(1,1),(1,3),(2,2),(3,1),(3,3),(4,4)}是A上的二元关系，求：（1）R的关系矩阵；（2）判断R的性质（自反性、对称性、反对称性、传递性）；（3）R是否为等价关系？若是，写出其等价类。已知无向图G的顶点集V={v₁,v₂,v₃,v₄,v₅}，边集E={(v₁,v₂),(v₁,v₃),(v₂,v₃),(v₂,v₄),(v₃,v₅),(v₄,v₅)}，求：（1）每个顶点的度数；（2）G是否为连通图？（3）G中是否存在欧拉路径？说明理由。四、证明题（每题15分，共30分）证明：对于任意集合A、B、C，有(A∪B)∩(¬A∪C)∩(B∪C)=(A∪B)∩(¬A∪C)。证明：斐波那契数列的任意相邻两项互质，即对于斐波那契数列{fₙ}（其中f₁=1,f₂=1,fₙ=fₙ₋₁+fₙ₋₂,n≥3），有gcd(fₙ,fₙ₋₁)=1（n≥2）。参考答案（仅供参考）一、单项选择题1.C2.A3.B4.C5.C6.B7.B8.B9.C10.A二、填空题1.¬P∨Q2.{∅,{a},{b},{a,b}}3.A4.25.∃x(P(x)∧Q(x))6.3,47.¬Q→¬P8.n(n-1)/29.等价10.双射三、计算题（简要步骤）1.（1）真值表略；（2）主合取范式：¬P∨Q∨¬R2.（1）关系矩阵略；（2）自反、对称、传递；（3）是等价关系，等价类：{1,3},{2},{4}3.（1）deg(v₁)=2,deg(v₂)=3,deg(v₃)=3,deg(v₄)=2,deg(v₅)=2；（2）是连通图；（3）不存在，因奇度顶点个数为2个（v₂、v₃），但欧拉路径要求奇度顶点个数为0或2，此处虽为2个，但需验证连通性，本题连通，但实际计算有误，正确结论：存在欧拉路径（v₂→v₁→v₃→v₂→v₄→v₅→v₃，修正：奇度顶点为