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

华东师范大学《离散数学》2023-2024学年第一学期期末试卷考试对象：本科相关专业考试时间：120分钟满分：100分注意事项：1.答题前请填写姓名、学号、班级，字迹清晰工整；2.所有答案写在答题纸上，写在试卷上无效；3.严禁作弊，作弊者本次考试按零分处理。一、选择题（每题3分，共30分）1.下列语句中，哪一个不是命题（）A.2是素数且是偶数B.离散数学是计算机专业的核心课程C.请认真答题！D.若x>3，则x>22.设P：明天天晴，Q：我们去郊游，则命题“除非明天天晴，否则我们不去郊游”可符号化为（）A.¬P→¬QB.P→QC.¬Q→¬PD.Q→P3.下列谓词公式中，属于有效式的是（）A.∃x(P(x)∧Q(x))→∀xP(x)B.∀x(P(x)∨Q(x))↔∀xP(x)∨∀xQ(x)C.∀xP(x)∨∀xQ(x)→∀x(P(x)∨Q(x))D.∃xP(x)∧∃xQ(x)→∃x(P(x)∧Q(x))4.设集合A={1,2,3}，下列关系中，不是等价关系的是（）A.{(1,1),(2,2),(3,3)}B.{(1,1),(2,2),(3,3),(1,2),(2,1)}C.{(1,1),(2,2),(3,3),(1,3),(3,1)}D.{(1,2),(2,1),(2,3),(3,2)}5.设集合A={a,b,c}，则A的幂集P(A)的元素个数为（）A.3B.6C.8D.96.下列关于函数的说法，正确的是（）A.若f:A→B，g:B→C都是满射，则f∘g:A→C是单射B.若f:A→B是双射，则f的逆函数f⁻¹:B→A也是双射C.若f:A→B是单射，则f一定是满射D.若f:A→B，g:B→C都是单射，则f∘g不一定是单射7.无向图G有8个顶点，若G是连通图且不含回路，则G的边数为（）A.6B.7C.8D.98.下列图中，不是欧拉图的是（）A.每个顶点度数均为偶数的连通无向图B.有且仅有两个顶点度数为奇数的连通无向图C.完全图K₄D.回路图C₅9.设<G,∘>是群，下列性质中不成立的是（）A.对任意a,b∈G，(a∘b)⁻¹=b⁻¹∘a⁻¹B.对任意a∈G，a∘a=e（e为单位元）C.对任意a,b,c∈G，(a∘b)∘c=a∘(b∘c)D.对任意a∈G，存在唯一的b∈G，使得a∘b=e10.下列集合中，是可数集的是（）A.实数集RB.区间(0,1)内的所有实数C.所有整系数多项式集合D.所有从N到N的函数集合二、填空题（每题4分，共20分）11.命题公式¬(P∨Q)∧(P∨¬Q)的主析取范式为__________。12.设集合A={1,2,3,4}，关系R={(1,2),(2,3),(3,4)}，则R的传递闭包t(R)=__________。13.无向图G的顶点度数之和为24，则G的边数为__________。14.设<Z₅,+₅>是模5加法群，其中Z₅={0,1,2,3,4}，则元素3的阶为__________。15.命题“如果天下雨，那么我不去公园”的逆否命题是__________。三、计算题（每题10分，共20分）16.求命题公式(P→Q)∧(Q→R)的主合取范式，并判断该公式的类型。17.设集合A={a,b,c,d}，关系R={(a,a),(a,b),(b,c),(c,d),(d,b)}，（1）画出R的关系图；（2）判断R是否具有自反性、对称性、传递性，并说明理由。四、证明题（每题10分，共30分）18.证明：∀x(P(x)→Q(x))∧∃xP(x)⇒∃xQ(x)（用自然推理系统证明）。19.证明：若无向图G有n个顶点，边数m>(n-1)(n-2)/2，则G是连通图（用反证法证明）。20.设<L,∧,∨>是一个格，证明：对任意a,b,c∈L，有a∧(b∨c)≥(a∧b)∨(a∧c)。参考答案及评分标准（附页）一、选择题（每题3分，共30分）1.C2.A3.C4.D5.C6.B7.B8.B9.B10.C二、填空题（每题4分，共20分）11.(¬P∧Q)12.{(1,2),(2,3),(3,4),(1,3),(1,4),(2,4)}13.1214.515.如果我去公园，那么天没有下雨三、计算题（每题10分，共20分）16.解：(P→Q)∧(Q→R)⇔(¬P∨Q)∧(¬Q∨R)（2分）⇔(¬P∨Q∨R)∧(¬P∨Q∨¬R)∧(P∨¬Q∨R)∧(¬P∨¬Q∨R)（6分）主合取范式为M₁∧M₃∧M₄（8分），该公式为可满足式（10分）。17.（1）关系图：以a、b、c、d为顶点，a指向a、a指向b，b指向c，c指向d，d指向b（4分）；（2）自反性：不具有，因为b、c、d没有自环（2分）；对称性：不具有，因为a→b但b↛a（2分）；传递性：不具有，因为a→b、b→c，但a↛c（2分）。（共10分）四、证明题（每题10分，共30分）18.证明：1.∃xP(x)前提引入（2分）2.P(c)存在量词消去（1分）（c为个体常量）3.∀x(P(x)→Q(x))前提引入（2分）4.P(c)→Q(c)全称量词消去（1分）5.Q(c)假言推理（2分）（由2、4）6.∃xQ(x)存在量词引入（2分）证毕。19.证明：假设G不连通，则G至少有两个连通分支（2分）。设其中一个分支有k个顶点（1≤k≤n-1），另一个分支有n-k个顶点（1≤n-k≤n-1）（2分）。此时G的最大边数为C(k,2)+C(n-k,2)=[k(k-1)+(n-k)(n-k-1)]/2（2分），化简得(n²-2nk+2k²-n)/2≤(n-1)(n-2)/2（2分），与题设m>(n-1)(n-2)/2矛盾，故假设不成立，G是连通图（2分）。证毕。20.证明：在格中，a∧b≤a，a∧b≤b；a∧c≤a，a∧c≤c（2分）。由b≤b∨